基于樹形檢測器的多標志識別

　　0引言

　　自動的電視臺標檢測和識別已經在多媒體領域獲得非常高的關注度。如今，多數的手機都具備了攝像頭功能，所以人們可以隨心所欲地拍攝各種事物，然后利用各種算法去分析處理獲得的圖像。本文中，展示一個系統一利用手機內置攝像頭幫助人們識別電視頻道信息。日常觀看的電視頻道就有幾十個不同的臺標，所以可以把這個問題看作是一個多類檢測問題，而單類的檢測即識別，最終就實現了多類識別。

　　對于單類檢測問題，Viola和Jones給出了state-of-the-art算法。他們先訓練了一系列節點分類器去檢測圖像里的每一個子窗口，只有那些能夠通過所有節點分類器的子窗口圖像才被認為是正樣本。吳將Voila的工作簡單地拓展到了多視角人臉檢測上，為每個獨立的人臉視角訓練了一個不同的cascade結構，并且并行地運用它們進行檢測。但是當正樣本的類型數量增加時，這個方案所花費的檢測時間也是線性增長的，而這個代價是我們無法負擔的。Torrobla提出了一種新的boosting框架，命名為jointboosting。他將N類分類問題轉化為N-1個兩類分類問題，然后自動地共享相同的弱分類器。盡管它的檢測器可以共享特征，但是當檢測目標時，它仍然需要計算全部特征，所以它并不是一個快速檢測框架。

　　近些年來，樹形檢測器被引入了多視角人臉檢測應用中。許多研究者更加偏愛于這種樹形結構，例如，Fleuret和Geman的scalartree，Li等人的金字塔結構，還有Huangchang的廣度優先搜索樹。在他們的工作里，Huang的工作最有新意，他提出來一種新的輸出一個布爾矢量的boosting算法，取名為vectorboosting。由于它具有良好的性能，本文選用它作為分叉樹的部分。有別于多視角人臉的并行結構，經驗證明直接構建一個由粗到精的樹是比較困難的。故此，本文設計了一種根據不同組合的誤報率來構建分叉樹的方法。詳細的方案會在1．3中闡述。

　　本文的其他部分是這樣組織的：在1．1小節中，本文介紹所采用的特征集，然后簡要地描述下普通cascade結構和softcascade結構。在實驗過程中，作者測試了本文算法的精確度和檢測所需的平均特征數。

　　1檢測器框架

　　在實驗中，本文采用了一架攝像機來拍攝電視節目的全屏幕圖像。考慮到此方法的通用性，不假設關于臺標位置的先驗信息（盡管臺標通常會出現在屏幕的上部）。為了可以檢測出臺標，本文先使用了一個分類器對大量的不同尺度和位置的子窗口進行掃描。因為多數的子窗

　　口都是背景，而背景的輪廓特征不明顯，所以可以將任務分割成兩個部分：首先是盡可能早的拒判掉非臺標的子窗口，然后是區別每個臺標屬于哪個頻道。接下來描述下算法的第一部分。

　　1．1通用檢測器

　　Viola在他的人臉檢測中成功地運用了adaboost結構和由haar特征構成的弱分類器。OpenCV也給出了該算法的代碼。許多目標檢測的問題也經常用到Viola的檢測框架，有時也只是用別的特征集替換了haar特征。

　　如圖2所示，電視臺標的主要屬性就是它的輪廓特征。在行人檢測中，基于梯度方向直方圖（HOG）的特征是一種描述輪廓的十分有效的特征。這個特征的缺點是它的輸出是一個矢量，所以需要用一個基于支持向量機的弱分類器，但是它要花費大量的計算時間。文獻提出了一個EHOG特征，它只輸出一個值，并可以很容易地被Adaboost算法使用。

　　因此在本文的臺標檢測器中，使用了EHOG特征。對于一副訓練圖像，計算一個塊Rb里的梯度直方圖，然后在n個方向分別統計梯度幅度的總和。

　　n是HOG特征的維數（在中，n=9），本文中設置為6。

　　然后，本文使用了中定義的主方向梯度D概念，D是上述區間集的一個子集，即，并計算對應D方向的EHOG特征：

　　為了快速地計算特征，本文也應用了積分直方圖方法。

　　本文采用了EHOG特征和gentleadaboost訓練了一個普通cascade結構，然后在所有樁分類器中收集全部的弱分類器，并用校正算法重新排序它們，得到一個新的“softcascade”檢測器。

　　本文定義為前t個弱分類器的響應值的和。運用了校正算法后，可以得到一個跡數組trace=（r1，r2，…，rN）。當對一個樣本x做決策時，加上每一個弱分類器的響應值ht（x），然后就將ht（x）和rt進行比較，如果低于，就立刻拒絕該樣本。Softcascade結構的性能要優于Viola的Cascade，在獲得相當的檢測性能時，它需要較少的特征數。這些將會在后面的實驗中展示。

　　第一層的普通檢測器可以拒判大量的背景圖像，卻還不能區別不同類的臺標。為了做進一步處理，仍需要一個可以解決多類別分類問題的算法結構。

　　1．2分叉樹

　　在Huang的工作里，他構建了一棵由粗到精標注了人臉的不同視角的樹。分叉樹上的每個節點分類器采用了矢量boosting算法訓練得到，依靠假設輸出空間的矢量化來解決多類問題。舉例說明，在一個節點分類器上，有四個可能的輸出矢量（（0，O），（0，1），（1，0），（1，1））：（0，0）代表著該樣本的檢測將終止于當前節點。（0，1），（1，0），（1，1）代表著該樣本將會通過哪個孩子節點。

　　在文獻中，相鄰的視角在分叉樹里的距離也很近。全部15個不同視角是根據旋轉角度平分成15份得到的。由于在本文的多臺標檢測中沒有關于某兩個臺標是近鄰的先驗知識，所以不能依靠經驗來構建一棵由粗到精的分叉樹。例如，當面對圖2中的6類臺標時，在分叉樹的根節點上，不知道該如何將它們劃分成兩個子節點。如果將明顯不同的臺標放在同一個節點里，訓練算法將會耗費更多的特征才能獲得一個相對較好的分類。基于這樣的想法，作者認為一個較好的劃分應該是在固定的迭代次數上利用矢量boosting訓練得到一個更好的分類結果。

　　假設有N類正樣本集，在第一層分叉節點上，就有2N-1-1種組合數可以將一個包含N類的集合劃分成兩個正樣本子集。

　　如果盲目地尋找一個合適的樹，總的時間復雜度會是log（N）*2N，這是無法實現的。為了解決這個問題，以下本文將引入一個貪婪搜索算法。

　　在一個二維矢量boosting算法里，正樣本數據被標示為（O，1）或者（1，0），負樣本數據被標示為（-1，-1）。本文用{S1，S2，…，SN}來表示所有的數據，那么左邊子節點的數據集就是，右邊子節點的數據集就是，這里Dleft和Dright是（1，2，…，N）的子集。