基于HOG特征的優化區域模板匹配檢測*

王溪波，王 彬，趙 海，朱宏博，葛宏帥，樸春赫

（1.沈陽工業大學信息科學與工程學院，沈陽 110870；2.東北大學 信息科學與工程學院，沈陽 110819）

基于HOG特征的優化區域模板匹配檢測*

王溪波1，王 彬1，趙 海2，朱宏博2，葛宏帥1，樸春赫2

（1.沈陽工業大學信息科學與工程學院，沈陽 110870；2.東北大學 信息科學與工程學院，沈陽 110819）

針對HOG算法滑動窗口檢測效率低和目標特征描述不精確的問題，提出了一種基于

梯度方向直方圖；可變形部件模型；滑動窗口；外形相似性；邊緣特征；根濾波器；部件濾波器；支持向量機

隨著數字圖像技術的廣泛使用，人們對圖像內容方面的處理越來越重視.目標檢測是最近比較熱門的一個課題，它是一種基于目標幾何和統計特征的圖像分割，將目標的分割和識別合二為一，其準確性和實時性是整個系統的一項重要能力［1－3］.

近年來，目標檢測領域出現了許多優秀的算法.其中，使用最廣泛的一種算法就是通過提取HOG特征［4］來描述感興趣目標，同時采用支持向量機（SVM）分類器對HOG特征進行訓練和分類，最后運用分類器對測試圖像進行檢測.但是，該算法也存在很多問題需要改善.首先，HOG算法的向量維數比較高，使得檢測計算量比較大，而且濾波器檢測圖像中的目標時，比較常用的檢測方法是滑動窗口（sliding window）方法，需要遍歷所有像素，造成了計算量的進一步增大；另外，由于HOG精度不夠高，通過 HOG特征訓練出的分類器對于外形比較相似的物體可能會產生誤檢和漏檢的現象.

針對上述問題，本文首先根據對大量圖片的觀察發現，目標出現的位置比較具有規律性，目標更可能出現在圖片的中心，并且檢測結果更傾向于存在性的圖片，比如路面上行人檢測，而對于處于邊緣的像素，可以考慮降低對其檢測的可能性，以減少計算量；其次，針對檢測評分處于閾值比較小的鄰域內的區域，利用可變形部件模型進行相似性確認檢測以保證檢測的正確性.本文方法主要針對靜態圖片，而不是連續的幀圖像.通過在PASCAL VOC 2007數據集上試驗得出的結果可以發現，與滑動窗口相比，本文算法在該數據集的20個類別中有13個類別獲得更快檢測速度.

1 相關工作

本文在傳統 Dalal-Triggs模型基礎上引入了可變形部件模型［5］（deformable part model）.通過使用可變形部件模型可以更加精準、靈活地對檢測區域進行評價.與傳統的可變形部件模型使用方法不同的是，本文算法并不是在圖像的每個區域都使用該模型進行評價，而是僅對可能存在目標的概率達到閾值時進一步對部件進行評價［6］，從而可以大大提高算法的檢測效率.

1.1 HOG特征

梯度方向直方圖（histogram of oriented gradients，HOG）是由Dalal等人提出的，它可以通過多維向量來表示目標特征，通過訓練形成豐富的特征集.

HOG特征的計算是利用每個像素點與周圍相鄰像素點的灰度差，在單位區域內進行梯度方向統計，進而形成梯度向量.劃分單位區域時，圖片首先被分割成指定大小的無重疊的像素區域，稱為cell.算法針對每一個 cell統計其中的梯度直方圖.每個像素的梯度被離散化為9個方向 bin中的一個，每個像素為它的梯度方向增加權值，權值根據梯度值的大小決定.所有 cell統計成直方圖以后，多個 cell組成一個bock.例如，假設檢測窗口大小是64×64像素，分成 8×8＝64個 cell，每個cell的大小是8×8個像素點.將相鄰的2×2＝4個單元格組合成一個 bock，需要注意的是，每個bock之間存在相互重疊的部分，可以通過歸一化梯度值來減少光照的影響［7－9］.

通過以上步驟，得到了一個高維度的向量，這樣 HOG對于圖像的描述向量就生成了.

1.2 可變形部件模型

盡管 HOG特征具有良好的描述效果，但是對于局部特征而言，檢測效果有限.為了獲得更好的檢測效果，本文使用可變形部件模型來對檢測提供進一步的保障.

本文定義的目標模型是由一個覆蓋了目標整體的較為粗糙的根濾波器和較為精細的部件濾波器組成，其中，部件濾波器只覆蓋物體中的較小部分.部件濾波器的特征是以根濾波器分辨率的兩倍來計算的，例如，如果在第l層通過根濾波器獲得了比較高的評分，那么就需要在 l＋2層使用部件模型進行檢測.因此，部件濾波器可以呈現出更好的邊緣效果，與根濾波器相比，可以更精準地定位目標［10－11］.例如，考慮為臉部建立一個模型，根濾波器可以捕獲粗糙的邊緣，例如人臉輪廓，而部件濾波器可以捕獲細節，例如眼睛、鼻子和嘴.

為了解決圖像尺度不統一的問題，本文采用了HOG特征金字塔，它是通過計算標準圖像金字塔的每一層 HOG特征來定義的.金字塔頂層特征捕獲相對粗糙的梯度，主要用于根濾波器；而底層特征捕獲較精細的梯度，主要用于部件濾波器.

根濾波器和部件濾波器都是通過與滑動窗口中的HOG特征向量做點積（dot product）來評價目標.檢測窗口的總評分（score）是窗口的根濾波器評分與結果子窗口中的部件濾波器評分之和，再加上區域評估.算法將具有 n個部件的目標模型定義為一個根濾波器 F0和一組部件模型（P1，P2，…，Pn），其中，Pi＝（Fi，vi，si，ai，bi），i＝1，2，…，n，Fi為第i個部件的濾波器；vi為一個二維向量，用來確定第i個部件相對于根濾波器的可能區域；si給出了該區域的大小；ai和bi均為二維向量，用來確定方程系數.計算對第i個部件可能區域的評分，其表達式為

2 HOG算法改進

2.1 檢測區域選取

由于檢測窗口的覆蓋區域為當前的檢測區域，則檢測窗口位置的選取效率會影響到算法執行效率.當前的趨勢是使用滑動窗口的窮舉方式來尋找目標，該方法雖然準確度較高，不會漏掉目標，但是窮舉的方式會大大影響檢測的效率.如果把圖片的檢測區域分出優先級，也就是說，如果檢測窗口的檢測位置能夠先檢測那些目標出現概率更大的區域，那么就能盡快地找到目標，從而使算法的收斂速度得到較大的提升［11］.

如果想從一幅圖片中分析出目標的可能分布區域，主要有以下兩種方式：

1）對圖像進行預分割，把圖像中的內容進行初步的分離.由于分離出來的部分很有可能是感興趣目標，因此可以優先檢測這部分.

2）通過統計，優先檢測目標出現較大概率區域.對于一幅圖片，中間的位置是感興趣目標比較容易出現的位置.

本文用紅框標出圖片的中心區域，如圖1所示.圖1a中的主要內容為家具，可以看出屋中絕大部分的家具都在紅框范圍內；圖1b中的主要內容為馬術比賽，馬、人及其他關鍵目標都在紅框范圍內；圖1c中的主要內容為汽車，圖中最為明顯的一輛汽車處于紅框范圍內.根據上述現象可以推斷，檢測窗口的位置應該優先尋找圖片中間的區域，降低比較靠近圖片邊緣區域的優先級，這樣就可以更快速地找到目標.

圖1 優化區域標定Fig.1 Calibration for optimized region

通過對比以上兩個特點可以發現，預分割的方法對圖像目標的定位比較準確，但是分割速度通常耗時較多.由于本文使用相似模板確認的方法對結果進行確定，考慮效率問題，算法不適合使用圖像預分割的方法，因此，本文算法使用大概率區域檢測方法來提高檢測速度.

2.2 模板相似性確認

在濾波器檢測出評分接近檢測閾值的區域之后，需要對這種不確定的區域進行進一步確認，而本文主要確認的內容就是目標的相似性.

檢測目標在形狀上具有相似性，會對算法的檢測結果產生干擾.例如，假設目標圖中的內容為長度較短的火車，如果用巴士的模板進行檢測，也可能會獲得接近閾值的評分，但最終就可能得到錯誤的結果.

對于上述問題，本文采用關聯分類的方法對這種干擾因素進行特殊處理.本文使用的數據集為PASCAL VOC 2007，其中包含20個分類.通過對這20個分類進行觀察發現，從形狀上可能產生相似性干擾的類別為：1）鳥和飛機；2）貓和狗；3）自行車和摩托車；4）牛、馬和羊；5）巴士和轎車；6）巴士和火車；7）椅子和桌子；8）椅子和沙發.這些分類在提取邊緣之后呈現出相似的邊緣特性，如圖2所示.圖2a為自行車提取邊緣后的結果，圖2b為摩托車提取邊緣后的結果，通過對比可以發現，自行車與摩托車的邊緣特征是非常相似的.另外，對于這些數據集之外的其他分類也可能對檢測結果產生干擾.例如，假設檢測的目標是行人，但是待檢測圖片中包含猴子，由于猴子的外形與小孩相似，這可能產生把猴子錯誤地檢測成小孩的情況，這樣就會造成誤檢.

圖2 自行車與摩托車的邊緣對比Fig.2 Comparison in edge of bike and motorbike

通過以上分析可以得出，如果目標的檢測評分高于閾值較多，說明檢測出的目標特征比較明顯，正確的概率較大，此時出現相似性誤檢的概率較小，則認為該檢測不需要進行相似性確認.如果檢測評分出現在閾值較小范圍的鄰域內時，就可能出現因外形相似而造成誤檢.判斷是否需要進行相似模板的確認，其表達式為

式中：sco表示對可能區域的總評分；thresh表示判斷閾值；neig表示判斷鄰域的大小.PD（sco）的結果如果為0表示需要進行相似模板的確認，結果為1表示不需要.

對于相似模板的確認，本文使用可變形部件模型.該模型通過將待檢測目標分成各個部件來提高檢測的準確度，可以很好地解決模板相似的問題.例如，飛機和鳥外形相似，在根濾波器下評分接近，但是通過對敏感部位的檢測，如鳥的腿部和飛機機身，可以得到相對較大的評分差距，進而增加最終結果的準確度.

由于PASCAL VOC 2007只有20個分類，并且具有相似性的分類集合最大為3，那么對于時間上的額外消耗也就處在了可控的范圍內，不會對算法的速度產生太大影響.

2.3 模板訓練

本文遵循傳統的HOG算法，使用線性支持向量機（SVM）作為分類判別器，并且使用PASCAL VOC 2007作為訓練數據集.該數據集含有大量訓練圖片，這些圖片中的檢測目標都由邊框標注出來.初始的根濾波器是通過PASCAL VOC 2007數據集中帶邊框的圖片產生的，部件濾波器由根濾波器初始化得到.

本文算法的具體學習過程主要分為兩個階段：第一階段是進行正樣本訓練和負樣本訓練，其中正樣本圖片包含待檢測目標，負樣本圖片不包含待檢測目標，從而得到初步的分類判別器；第二階段使用已經得到的初步分類器對負訓練圖像進行掃描，把掃描結果有誤的圖片作為誤測樣本，然后用正樣本、負樣本和誤測樣本組成一個總的集合，再次學習得到最終的分類判別器.分類器的分類界面表達式為

式中，w、b為平面參數.這樣就可以使用得到的分類判別器對待檢測圖像進行分類［11］.

3 基于HOG的模板匹配檢測算法

本文算法主要分成兩個階段：訓練階段和檢測階段.由于數據集變得越來越復雜，使用簡單的訓練方法往往就可以達到比較好的效果，因此，本文使用線性支持向量機（SVM）來進行分類.檢測部分的算法流程如圖3所示.

圖3 算法總體流程圖Fig.3 Overall flow chart of algorithm

算法的檢測首先是從圖片的中心區域開始，可以盡可能快速地找到目標.如果某個區域評分非常高，可直接認定該區域為待檢測目標，如果圖片中出現了評分比較接近閾值的區域，則需要使用可變形部件模型進行更加精確地評分.由于可變形部件模型只用于評分較為模糊的區域，減少了不必要的計算，這對算法速度的提高有較大幫助.

如果檢測過程中發現中心區域確實沒有待檢測目標，算法也會對圖像中出現概率小的地方進行檢測，防止對目標的遺漏.

在檢測過程中，算法首先使用HOG算法的根濾波器進行檢測并計算評分.如果評分明顯大于或小于閾值，則認定該區域是否為待檢測目標.如果不能認定，則使用可變形部件模型進行檢測.由于使用可變形部件模型非常耗時，但又具有很高的準確性，所以對于可變形部件模型的使用時機十分關鍵.在普通情況下，使用根濾波器處理結果分明的圖片，也就是評分較高或較低的圖片，不使用可變形部件可以節省大量的檢測時間.

通過上述描述可以發現，本文方法主要檢測對象是針對靜態圖片的，由于靜態圖片中的場景相對規范，更容易找到目標.另外，本文方法更傾向于確定目標是否存在，而不是統計目標數量.

4 實驗結果與分析

為了驗證算法的可行性，本文對算法進行了測試，并提供各個步驟的結果.程序的運行環境是W indows 7操作系統下的Matlab R2013a，硬件環境中CPU為Intel Core I7 4770k，內存8GB.測試環境使用PASCAL VOC 2007數據集，該數據集包括9 963張圖片，共分成20個目標類.

圖4為3組圖片的實驗結果.3組圖片中，第1組的檢測目標為羊，第2組的檢測目標為鳥，第3組的檢測目標為火車.每組包含圖片處理3個階段的結果，分別為原始圖像、對圖像中心區域的標注、根濾波器對中心區域的評分，圖像中亮度越暗，表示評分越高.

圖4 各階段實驗結果對比Fig.4 Com paring in experimental results in each stage

通過實驗可以看出，前 2組圖片根濾波器評分中黑白對比比較模糊，說明根濾波器評分比較接近閾值；而第3組根濾波器評分的對比比較明顯，說明評分比較高.這就需要對前兩組圖片進行下一步的檢測，而第3組圖片的檢測結果可以作為最后的結果.

圖5為3組圖片的最終檢測結果.由于前兩組圖片的檢測使用了可變形部件模型以及相似模板，因此檢測結果是通過分散的部件評估出來的整體結果.

圖5 實驗最終結果對比Fig.5 Comparing in final experimental results

表1給出了本文算法與文獻［11－12］中算法的平均準確率（average precision，AP）的對比. AP是對不同召回率特定點上的正確率進行求平均值的計算，其表達式為

式中：t為對召回率所有值分成的份數；Qi為每個召回率中每個特定點對應的準確率.例如，計算AP時首先把召回率從0～1分成10等份，根據召回率分別為0，0.1，0.2，…，1.0的11個邊界點上的正確率求平均值，則AP就等價于這11個點的平 均值［13］.

表1 平均準確率對比Tab.1 Comparison in average accuracy

由表1可以看出，本文算法對于邊緣輪廓有相似性的分類，如自行車、飛機、羊和火車的效果比較好，而對于相似性不大的分類，如船和轎車等的檢測效果提升不明顯，說明本文算法通過對模板相似性進行檢測起到了提高準確率的作用，但是僅對圖片中心大概率部分進行檢測會丟失圖片中的其他檢測目標，從而降低準確率.

為了分析各種算法的效率，表2給出了本文算法與文獻［11－12］中算法的運行時間對比.從表2中可以看出，本文算法對于船、人和轎車等分類的檢測速度提高較大，而對于其他分類效果不明顯，例如自行車和飛機.通過分析可以發現，自行車與摩托車，以及飛機與鳥的相似度較大，檢測過程中更有可能進行相互評分對比，由此造成檢測速度降低.而船和人沒有相似的模板，因此在每次的檢測中都會節省大量的時間.

表2 運行時間對比Tab.2 Comparison in running time s

通過上述實驗對比可以發現，本文算法對于大部分類別在速度上有穩定保證，但是該算法也存在一定的問題，對圖片邊緣地帶會出現漏檢現象.因此，本文算法對檢測結果準確度和速度同時都有需求的情況下比較適用.

5 結 論

本文提出了一種基于傳統 HOG算法的區域優化模板檢測算法.該算法通過檢測圖像大概率區域并使用相似模板確認檢測的方法，改進了傳統的檢測窗口效率低下和相似模板誤檢的問題，而且該算法還能夠分辨邊緣相似類別的同時提高算法的檢測速度，提升了算法總體效率.通過對實驗中各個類別的統計可以發現，文獻［11－12］的算法對這些類別的檢測平均AP分別為0.288、0.317，使用時間分別為4.59、4.64 s，而本文算法的平均 AP為0.293，平均時間為4.28 s.結果表明，本文算法在時間上提升比較明顯，在 AP的對比上低于文獻［12］.由此可以推斷，該方法在對檢測結果要求不嚴格的情況下可以起到比較明顯的快速檢測效果.

（

）：

［1］孫銳，侯能干，陳軍.基于特征融合和交叉核 SVM的快速行人檢測方法［J］.光電工程，2014，41（2）：53－62.（SUN Rui，HOU Neng-gan，CHEN Jun.Fast pedestrian detection method based on features fusion and intersection kernel SVM［J］.Opto-Electronic Engineering，2014，41（2）：53－62.）

［2］魏巖，涂錚錚，鄭愛華，等.結合RGB顏色特征和紋理特征的消影算法［J］.計算機技術與發展，2013，23（10）：72－74.（WEI Yan，TU Zheng-zheng，ZHENG Ai-hua，et al. Shadow elimination algorithm of combination of RGB color feature and texture feature［J］.Computer Technology and Development，2013，23（10）：72－74.）

［3］于成龍.基于PCA的特征選擇算法［J］.計算機技術與發展，2011，21（4）：123－125.（YU Cheng-long.Features selection algorithm based on PCA ［J］.Computer Technology and Development，2011，21（4）：123－125.）

［4］Dalal N，Triggs B.Histograms of oriented gradients for human detection［C］／／Proceedings of the 2005 IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington D C，USA，2005：886－893.

［5］Felzenszwalb P，McAllester D，Ramanan D.A discriminatively trained，multiscale，deformable part model［C］／／IEEE Conference on Computer Vision and Pattern Recognition.Anchorage，USA，2008：1－8.

［6］Yuhi G，Koichiro Y，Hironobu F.CS-HOG：color similarity-based HOG［C］／／2013 19th Korea-Japan Joint Workshop on Frontiers of Computer Vision. Incheon，Korea，2013：266－271.

［7］劉威，段成偉，遇冰，等.基于后驗 HOG特征的多姿態行人檢測［J］.電子學報，2015，43（2）：217－224.（LIUWei，DUAN Cheng-wei，YU Bing，et al.Multipose pedestrian detection based on posterior HOG feature［J］.Acta Electronica Sinica，2015，43（2）：217－224.）

［8］Plath N，Toussaint M，Nakajima S.Multi-class image segmentation using conditional random fields and global classification［C］／／Proceedings of the 26th Annual International Conference on Machine Learning. Quebec，Canada，2009：817－824.

［9］姚雪琴，李曉華，周激流.基于邊緣對稱性和HOG的行人檢測算法方法［J］.計算機工程，2012，8（5）：179－182.（YAO Xue-qin，LIXiao-hua，ZHOU Ji-liu.Pedestrian detection method based on edge symmetry and HOG［J］.Computer Engineering，2012，8（5）：179－182.）

［10］宮義山，董晨.基于貝葉斯網絡的缺失數據處理［J］.沈陽工業大學學報，2010，32（1）：79－83.（GONG Yi-shan，DONG Chen.Data patching method based on Bayesian network［J］.Journal of Shenyang University of Technology，2010，32（1）：79－83.）

［11］Felzenszwalb P F，M cAllester D，Ramanan D.Object detection with discriminatively trained part-based models［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32（9）：1627－1645.

［12］Zhu L，Chen Y H，Yuille A L，et al.Latent hierarchical structural learning for object detection［C］／／The Twenty-Third IEEE Conference on Computer Vision and Pattern Recognition.San Francisco，USA，2010：1062－1069.

［13］常娥，侯漢清.平均檢準率研究［J］.情報科學，2006，24（4）：627－631.（CHANG E，HOU Han-qing.Study on average precision in information retrieval［J］.Information Science，2006，24（4）：627－631.）

（責任編輯：鐘 媛 英文審校：尹淑英）

Template matching detection for optimized region based on HOG features

WANG Xi-bo1，WANG Bin1，ZHAO Hai2，ZHU Hong-bo2，GE Hong-shuai1，PAK Chun-hyok2
（1.School of Information Science and Engineering，Shenyang University of Technology，Shenyang 110870，China；2.School of Information Science and Engineering，Northeastern University，Shenyang 110819，China）

In order to solve the problem that the the detection efficiency of sliding window in HOG algorithm is low and the feature description of target is not accurate，an improved algorithm based on HOG was proposed，which could improve the detection efficiency of sliding window and reduce the influence of the target template similarity on the results.The entire target and each part were described with HOG features in the algorithm，and the area with high appearing probability of target would be preferentially detected.For the area whose score got near to the threshold，the deformable part model was used to carry out the accurate detection，which could avoid the inaccurate detection of templates with contour similarity. The results show that the proposed algorithm has higher accuracy for static images，and exhibits faster detection speed in many categories with low similarity.

histogram in gradient direction；deformable part model；sliding window；shape similarity；edge feature；root filter；part filter；support vector machine

TP 391.4

A

1000－1646（2016）06－0667－07

10.7688／j.issn.1000－1646.2016.06.13

2015－10－20.

遼寧“百千萬人才工程”培養基金資助項目（2012921041）；中央高校基本科研業務費優秀科技人才培育基金資助項目（N140405004）.

王溪波（1964－），男，遼寧沈陽人，教授，博士，主要從事智能信息處理等方面的研究.

09－07 16∶08在中國知網優先數字出版.

http：∥www.cnki.net／kcms／detail／21.1189.T. 20160907.1608.038.htm l

HOG的改進算法，提高了滑動窗口的檢測效率并減少了目標模板相似性對結果帶來的影響.該算法利用HOG特征來描述目標的整體和各個部件，優先檢測圖像中目標出現概率較大的區域.對于檢測評分比較接近閾值的區域使用可變形部件模型進行精確檢測，從而可以避免具有輪廓相似性的模板檢測結果的不準確.結果表明，該算法對于靜態圖片有較高的準確率，且對于很多相似度不高的分類具有較快的檢測速度.