基于HOG特征描述的輪廓匹配算法

童小彬， 孟 婥， 孫以澤， 張 豪

(東華大學 機械工程學院， 上海 201620)

輪廓匹配是模式識別、機器視覺領域的關鍵技術，是基于輪廓的目標檢測中的重要方法。不同于顏色、紋理等其他特征，輪廓形狀具有較好的不變性[1]，很多情況下僅通過對物體輪廓的分析即可實現對目標的識別[2]。輪廓匹配算法通常包含輪廓描述和輪廓匹配兩個部分，其中輪廓描述發揮更關鍵的作用。

在近年來的輪廓匹配研究中，基于輪廓點空間位置分布的輪廓描述方法表現出較好的效果，它通過統計輪廓點空間位置分布關系來描述輪廓。其中，由Suhas等[3]提出的形狀上下文(shape context,SC)方法，通過建立對數極坐標直方圖來描述任意采樣點與輪廓上其他采樣點的空間分布情況。這雖然兼顧了采樣點之間的角度和距離兩種信息，但是在極坐標系下定義直方圖中的塊使得近處采樣點比遠處采樣點更加敏感[4]。在此基礎上，Shu等[5]提出了輪廓點分布直方圖(contours points distribution histogram, CPDH)，即一種新的二維形狀描述方法，其在匹配效果和運行時間上都得到了改善。基于形狀上下文和基于輪廓點分布直方圖算法都是在空間域對輪廓進行描述，能夠簡單有效地描述輪廓的幾何信息，但其只能處理簡單閉合的輪廓。為了使描述更加精確，研究者開始嘗試在頻域對輪廓進行描述，Bartolini等[6]提出基于傅里葉變換的描述子，其結合了傅里葉系數的振幅信息和相位信息，取得了較好的效果，但是難以描述部分缺失或遮擋的輪廓。以上方法都只考慮到輪廓點的空間位置分布關系，而忽視了輪廓點的梯度信息,因此用梯度大小和方向來描述輪廓是本文研究的重點。

輪廓匹配的過程是運用適合的方法在特征空間中尋找圖像變換數據的最優估計，常見的方法有動態規劃法、模擬退火算法、蟻群算法、窮盡式搜索法和金字塔分層式搜索法。窮盡式搜索法的計算量非常大且速度較慢，算法的復雜度為O(whn)，w和h分別為待匹配圖像的寬和高，n為匹配模板像素點的數量[7]。金字塔分層式搜索法是對配區圖像先粗后精的分層搜索方法，它通過成倍縮小待匹配圖像的寬w、高h，以及模板像素點的數量n，達到減小圖像匹配算法復雜度O(whn)的目的。為了提高匹配速度，本文采用金字塔分層式搜索策略。

匹配結果一般用輪廓相似度來度量，輪廓相似度越高，表明匹配度越高。常采用Hausdorff距離(Hausdorff distance, HD)來度量模板與待匹配圖的相似程度，該方法在閉合輪廓匹配上取得了不錯的效果，但容易受到背景和邊緣噪聲的影響[8]。相關系數能夠對輪廓間的相似程度進行量化，并具有尺度縮放不變性，但同樣對噪聲點敏感，且計算量大于Hausdorff距離度量[9]。角度相似性度量公式涉及乘法和除法，而距離相似性度量公式只涉及乘法和減法，相較而言更為簡單，本文選取歐氏距離作為輪廓相似性度量的方法。

1 基于HOG特征的輪廓匹配算法

1.1 HOG特征提取

HOG特征是在機器視覺和圖像處理中用來描述物體檢測特征的描述子。通過統計像素在梯度方向上的分布密度來描述局部區域的表象和形狀。具體實現方法：將圖像切分成多個等大的小塊，作為細胞單元，然后計算和統計每個細胞單元的梯度方向直方圖，最后將這些直方圖有序組合起來，以便降低光照和陰影的影響，在更大的范圍內對各個細胞單元進行對比度歸一化處理，得到最終的HOG特征。本研究是對指定輪廓的匹配，不需要對圖像進行分塊，只需將輪廓作為一個細胞單元，提取其HOG特征即可。

對于一幅灰度圖像I，其輪廓HOG特征提取流程：設置ROI(region of interest)區域，通過邊緣檢測法提取模板圖像輪廓；先將輪廓曲線點離散化并保存坐標；然后，計算模板圖像的梯度，得到梯度幅值矩陣M(I)和梯度方向矩陣O(I)。拉普拉斯算子對噪聲很敏感，prewitt算子沒有考慮鄰域像素的權重，sobel算子不僅考慮了空間位置帶來的像素權重，還是一階差分算子，算法簡單高效，對連續性不高的邊緣輪廓具有較好的魯棒性。因此本文將采用sobel算子計算模板圖像的梯度，以及x和y方向的卷積模板Mx和My，并求得梯度幅值和梯度方向矩陣M(I)、O(I)。

(1)

(2)

(3)

O(I)=arctan(I?My./I?Mx)

(4)

根據保存的圖像輪廓點坐標計算各點的梯度大小和方向，并在梯度方向上進行直方圖統計，如圖1所示。由圖1可知，采用9個柱的直方圖統計輪廓的梯度信息，將輪廓點在梯度方向上分成9個對稱扇形塊，Z為一個個小的扇形區域。為進一步用到梯度大小信息，將梯度幅值作為權值投影到直方圖中，比如某一離散點的梯度方向在0°～20°，梯度大小為3，則梯度幅值為對應直方圖柱的計數加上該離散點梯度大小3，而不是對應直方圖柱的計數加上該離散點個數1。如圖2(a)所示的輪廊，其對應的梯度方向直方圖如圖2(b)所示。

圖1 梯度方向分塊圖Fig.1 Gradient direction block graph

(a) 輪廓圖

(b) 梯度方向直方圖

1.2 金字塔分層搜索

構建圖像金字塔分層，需要先對圖像進行平滑處理，一般通過對圖像進行均值濾波或高斯濾波達到平滑的目的。為了避免金字塔圖像發生偏移，需使用奇數的卷積模板，相比5×5的高斯模板，3×3的均值模板速度更快，可平滑二次抽樣的鋸齒問題并避免頻率響應的問題[10]。圖像金字塔分層不斷地進行二次抽樣，使得圖像分辨率逐層降低，圖像分辨率過低會導致在圖像金字塔頂層識別不出目標輪廓。某印花鞋面圖像如圖3(a)所示，其輪廓金字塔圖像如圖3(b)所示。由圖3可以看出，該印花鞋面輪廓的金字塔圖像構建至第6層時，大部分輪廓已經丟失，因此本文選擇構建5層金字塔。在第5層金字塔對模板輪廓以一定角度步長旋轉，并進行一定比例的縮放，然后依次在待匹配圖像的對應金字塔層進行匹配，獲得目標位置坐標后，再將此狀態下的模板圖像映射到下一層,映射過程其實是將金字塔高層匹配結果的兩倍作為下一層的預匹配位置。由于得到的位置坐標受分辨率影響，存在不確定性，可將下一層的匹配位置及其周邊一定鄰域范圍作為新的搜索區域，這大大減少了搜索區域，達到了加速算法的目的。隨著圖像金字塔層數的減少，圖像分辨率越來越高，匹配的效果也越來越精準。

(a) 印花鞋面圖像

(b) 輪廓金字塔圖像

1.3 歐氏距離度量

歐氏距離是最容易理解的一種距離計算方法，計算簡單高效，定義如下:

記二維平面上兩點A(x1,y1)與B(x2,y2)間的歐氏距離為

(5)

記三維平面上兩點A(x1,y1,z1)與B(x2,y2,z2)間的歐氏距離為

(6)

兩個n維向量A(x11,x12,…,x1n)與B(x21,x22,…,x2n)間的歐氏距離為

(7)

求取兩向量間的歐氏距離相當于提取兩向量差向量的最大奇異值，可用差向量的二范數來表示，即norm(A-B, 2)。歐氏距離越小則代表兩輪廓越相似，越大則代表越不相似，歐氏距離為0時代表完全匹配。1.1節已經舉例提取了模板輪廓的HOG特征，得到一個9維特征向量H,在金字塔圖像中滑動模板窗口搜索時，在每個位置都會得到一個與之對應的9維特征向量H，此時兩輪廓間的歐氏距離D為

D=norm(H-H′, 2)

(8)

滑動窗口并計算模板輪廓與待匹配圖像的相似度，找到相似度最大即歐氏距離D最小時的位置，將匹配到的位置坐標逐層映射到下一層，逐步縮小搜索區域，由粗到精，直到在最底層圖像中找到與模板輪廓最相似的目標輪廓。

2 試驗與分析

為驗證該算法在復雜背景下的有效性，選取某印花鞋面圖像，設置ROI區域，再對其進行邊緣檢測，將得到的模板輪廓作為試驗對象。某印花鞋面提取模板輪廓的示意圖如圖4所示。

圖4 印花鞋面圖像預處理Fig.4 Pre-processing of printed upper image

2.1 直方圖柱數量對匹配結果的影響

直方圖柱的數量決定了輪廓HOG特征向量的維數，從而反應了描述輪廓的精度，這個精度會對匹配結果造成一定影響。在保證運算速度滿足實際需要的前提下，設置直方圖柱的數量為本試驗的研究目標。

分別選取缺失輪廓和噪聲輪廓的兩組印花鞋面圖像作為試驗對象與模板輪廓進行匹配。通過不斷增加直方圖柱數量的方法計算對應輪廓間的歐氏距離。局部輪廓示意圖及其試驗數據曲線如圖5所示。由圖5可知，隨著柱數量的增加，兩輪廓之間的歐氏距離值趨于減小，即輪廓相似度越高。

(a) 模板輪廓與缺失輪廓匹配結果

(b) 模板輪廓與噪聲輪廓匹配結果

在輪廓比較理想的情況下，設置較多的直方圖柱可更精細地描述輪廓的局部信息，從而得到更精準的匹配結果。設置適當數量的柱能夠更好地抵抗噪聲的干擾，且對微小變形或輪廓局部遮擋、缺失有較好的容錯能力；但當柱數量設置極少時，匹配效果通常很差，精度往往達不到要求，甚至還會誤匹配。比如，當柱數量低至1時，相當于只考慮了輪廓點的梯度大小而完全忽略了輪廓點的方向信息，在復雜背景下會造成較多的誤匹配。由圖5可知，當柱數量超過20時，輪廓相似度逐漸趨于穩定，因此在保證算法有效性的前提下，為進一步提高算法運行速度，柱數量選取20～60。

2.2 試驗可視化結果比較

為進一步驗證本文算法對輪廓匹配的綜合性能，將梯度方向直方圖的柱數量設為20，以印花鞋面左邊第一個黑框邊緣為模板輪廓(第一個黑框與下面兩個黑框并不是等比例縮放關系，屬于不同輪廓)。該算法在鞋面實際應用中要實現的功能，即每次匹配到第一個黑框，通過定位第一個黑框的位置信息從而得到整個鞋面輪廓的位置信息，如果匹配到第二個黑框，則認定匹配錯誤。選擇4組不同情況下的印花鞋面與模板輪廓進行匹配，并與HD算法比較，分別為第1組缺失輪廓、第2組噪聲輪廓、第3組非線性光照、第4組旋轉縮放。匹配結果如圖6所示，每組圖中左邊為HD算法匹配結果，右邊為本文算法匹配結果，各自所耗時間如表1所示。

(a) 1# 缺失輪廓

(b) 2# 噪聲輪廓

(c) 3# 非線性光照

(d) 4# 旋轉縮放

表1 不同算法的性能比較

2.3 結果分析

由表1可知，對于圖像輪廓存在部分缺失、邊緣噪聲、非線性光照、旋轉了方向并存在縮放處理的印花鞋面，本文算法都能匹配成功，因采用歐氏距離相似性度量方法，無法對匹配精度進行量化，但從圖6匹配的情況來看，沒有出現明顯的偏差。由于缺失輪廓致使缺失部分輪廓點的位置完全發生了改變，邊緣噪聲輪廓在噪聲處的輪廓點也發生了一定的變化。HD算法對缺失輪廓和邊緣噪聲輪廓產生了錯誤匹配。這是因為HD算法對采樣點的空間位置要求較為嚴格，當輪廓點位置發生變化后，其匹配結果變差。本文算法是綜合了輪廓點梯度大小和方向信息的統計方法，對空間位置不敏感，通過提取合理維數的HOG特征，能夠減小甚至消除缺失輪廓和噪聲輪廓的輪廓點變化帶來的影響。從算法執行速度上看，雖然本文算法所耗時間約是HD算法的2倍，但是平均時間不超過0.7 s，能夠滿足應用需要。另外，通過減小搜索時模板輪廓的縮放比例和旋轉范圍，可進一步縮短運行時間。

3 結 語

考慮輪廓點的梯度信息能夠較好地反應目標的輪廓信息，本文提出一種基于HOG特征描述的輪廓匹配算法。通過計算輪廓點的梯度大小和方向，再根據方向劃分，統計不同區域間內輪廓點的個數，并以各梯度幅值作為權重加權投影，建立對應的梯度方向直方圖，融合了輪廓的全局信息和局部信息。通過調整直方圖柱的數量，控制算法運行速度和匹配精度，能解決圖像輪廓存在部分缺失、邊緣噪聲、非線性光照的輪廓匹配問題。采用金字塔分層式搜索策略，極大地加快了算法運行速度，能夠滿足應用需要。