基于邊緣梯度特征的目標定位算法

南京郵電大學電子與光學工程學院 陳志彭

1 引言

目標定位廣泛應用于計算機視覺和圖像處理的相關領域，例如目標跟蹤、目標檢測等。針對目標識別和定位這一問題，已經形成了一系列的相關理論和技術，現在流行的目標定位的方法主要有兩種，一種是基于區域的目標匹配，另一種時基于局部幾何特征的目標匹配[1]。

典型的模板匹配就是計算模板和搜索圖像滑動窗口內的子圖像在每一個像素點上的像素值相似度，并將相似度高于閾值的區域作為目標在圖像上的位置，這種方法對于模板或被搜索圖像的尺度變化以及圖像旋轉等問題的適用性不夠好。

針對傳統上基于灰度相似性度量的模板匹配算法在圖像旋轉情況下適用性不高以及容易受到環境光照影響的局限性，本文采用一種基于邊界梯度特征的目標定位方法。該算法主要思想是在圖像金字塔逐步求精的基礎上采用邊界梯度而非像素點處的像素值進行相似性度量，使得算法能夠針對圖像旋轉情況具有其匹配準確性和適用性。另外，針對目標定位的多目標問題，本文算法在遍歷整個搜索圖像的同時，將所有高于設定閾值的匹配得分以及對應的坐標和旋轉角都保存在一個鏈表里，在遍歷結束之后根據匹配得分對整個鏈表進行排序，得到所要確定的多個目標位置以及相對旋轉角。

2 基于邊界梯度特征的匹配方法

2.1 基于構建圖像金字塔的匹配方法

傳統的模板匹配是計算搜索圖像每幅子圖像在各種旋轉角度下的灰度值相似度量值，這是一個十分耗時的過程，雖然通過使用終止條件可以加快算法處理的速度，但是并不能降低算法的復雜度[5]。

為了能夠更加滿足實時性的要求，就要采用更加快速有效的搜索策略。考慮到計算灰度相似度量的運行時間取決于搜索圖像的大小、模板像素點個數以及模板旋轉的次數，那么由粗到精的搜索策略就可以有效的降低算法的復雜度[2]。

實現這一過程的比較有效的辦法是構建圖像金字塔，構建圖像金字塔時，對圖像隔i行i列進行重采樣。對搜索圖像和模板進行降采樣操作，得到低分辨率的圖像后，通過計算模板和搜索圖像子圖像的相似度量值來獲取與模板相似圖像的大概位置。接著，使用間隔小一點，如i/2的重采樣圖像，在上一分辨率得到的大致位置的領域內進行相似度量計算并判斷，獲得精確一點的匹配位置。以此類推，逐步求精，直到得到原分辨率下精確的匹配位置[3]。

2.2 基于梯度信息的相似性度量函數

上一節介紹圖像金字塔逐步求精的過程中，通過降采樣的方式分別在不同的金字塔層級計算模板圖像與搜索圖像子圖的灰度值相似性度量值，從而逐步確定目標圖像在搜索圖像中的目標位置。但是通過計算灰度值的相似性度量值對環境變化、圖像旋轉等情況魯棒性不高，所以本文采用用圖像邊界特征的梯度信息作為相似性度量因素，在圖像金字塔分層搜索過程中計算模板圖像與搜索圖像在邊界特征點處的梯度信息相似性來確定是否為目標位置。

針對圖像會發生的旋轉情況，同樣可以采用圖像金字塔的思想：首先，通過使模板以一定角度步長旋轉遍歷一次金字塔最頂層的圖像。在計算相似度量值的時候，可以適當加入合理的停止標準，加快判斷效率。然后，將在最頂層找到的大致位置映射到下一層，在該位置的一定領域內進行更加角度步長更精細的匹配，依次直到圖像金字塔的最底層，這樣就能得到圖像旋轉時最高分辨率匹配精度[4]。

采用基于邊界特征點的匹配算法，需要對模板圖像邊界特征點進行篩選提取得到邊界特征點坐標及其對應的梯度向量，i=1，2……,n（n表示特征點個數）。還有搜索圖像的邊緣特征點坐標以及每個子圖像中的梯度向量，這里的分別是特征點（a,b）處的橫向梯度方向分量和縱向梯度方向分量。在得到邊界特征點坐標以及特征點處的梯度向量信息之后，通過計算模板圖像中所有特征點與搜索圖像的所有特征點的梯度相關性的總和作為相似度，表示梯度相關性的相似度量函數為：

這里的搜索圖中與模板特征點梯度相對應的梯度向量。公式(1)[2]容易受到非線性噪聲的影響，因此對其進行歸一化處理：

歸一化后的梯度相似性度量表示的是歸一化后模板與搜索圖像的所有特征點處梯度信息相似性度量均值，通過該公式計算相似性可以得到一個小于等于1的匹配得分。當該匹配得分越高，表示搜索圖像該子圖區域與模板圖像越匹配。當該式等于1時，為該子圖區域與模板圖像完全匹配。

根據上述關于邊界特征點的梯度相似性度量函數的介紹，接著詳細介紹算法設計實現的過程，包括模板和搜索圖像特征點提取及篩選、金字塔模型創建、匹配過程的梯度信息相似性度量計算和多目標定位等。

2.3 算法設計與實現

2.3.1 特征點提取及篩選

首先，需要通過邊緣檢測提取模板圖像特征點x方向和y方向的梯度信息和，并通過公式(3)和公式(4)計算得到梯度幅值和梯度方向：

為了減少邊緣特征點提取到的偽特征點對梯度信息相似性度量的影響，減少偽特征點處不必要的計算量。在進行偽特征點剔除之前，為了方便非最大值抑制過程的實現，需要將梯度方向修正到0度、45度、90度、135度方向。通過非最大值抑制以及雙閾值篩選剔除偽特征點，將低于低閾值的特征點以及介于低閾值和高閾值之間但與高于高閾值的特征點不連通的特征點確定為偽特征點，給與剔除，不參與匹配過程中的相似性度量計算。

2.3.2 構建模板圖像和搜索圖像金字塔模型

在搜索圖像上直接進行匹配運算是一個十分耗時的過程，本文通過構建圖像金字塔的方式以實現逐步求精的匹配過程，可以適當提高算法的速度。首先根據設定的金字塔層數，本文設置為3層，對模板進行降采樣構建金字塔。在構建好圖像金字塔之后，需要按照3.2.1小節的方法在每一層提取模板梯度信息，并保存模板在同一角度下不同金字塔層級的梯度信息，方便匹配過程中的相似性計算。針對搜索圖像可能出現的旋轉情況，按照Δ?的步長旋轉模板圖像，該步長也要依據圖像金字塔逐步求精的思想，設置為依據金字塔層數的遞進逐步細分，并采用與上述相同的過程保存不同角度下的模板梯度信息。

為了給圖像匹配過程做好準備，對搜索圖像也要采用與模板圖像相同的處理方法，構建與模板圖像金字塔相同層數的搜索圖像金字塔。不同地方在于，已經對模板圖像進行旋轉處理得到不同角度下的模板梯度信息，就不需要去搜索圖像再做重復處理。

2.3.3 匹配過程的實現

構建好搜索圖像金字塔之后，就是匹配過程的實現。從圖像金字塔頂層開始，在圖像金字塔每一層都對模板和搜索圖像子圖像中所有特征點進行梯度信息相似性計算并歸一化得到的就是每個子圖像與模板圖像的匹配得分。當梯度信息相似度量值高于設置閾值時就認為是目標位置，隨即也就可以確定出最佳匹配位置坐標和相對旋轉角。

在程序設計時，在金字塔每一層中，從圖像金字塔頂層開始計算公式(2)的梯度信息相似度量值，該公式得到的計算結果就是每個搜索圖像的每個子圖與模板圖像的匹配得分。得到匹配得分之后，將該得分與事先設置的閾值做比較，若該得分高于閾值，將目前的得分作為搜索圖像下一個子圖像與模板圖像匹配的閾值，并保存其坐標以及旋轉角。若低于閾值則認為該子圖像不匹配并舍棄。以此類推，當整個搜索圖像金字塔模型被遍歷完成之后，保存下來的閾值就是當前搜索圖像的子圖像（匹配得到的目標位置）與模板圖像的匹配得分打分，而該匹配得分對應的信息就是匹配的目標位置和相對旋轉角。

2.3.4 多目標匹配的實現

采用計算梯度信息相似度的全局最大值只能實現單目標匹配，而通常在進行目標定位時，搜索圖像中可能存在多個與模板相匹配的目標位置，這個時候通過查找全局最大值來確定目標位置就不適用了。這時可以在遍歷整個搜索圖像的同時，將所有高于設定閾值的匹配得分以及對應的坐標和旋轉角信息都保存在一個鏈表里，這里保存的信息也包含了最佳匹配位置附近的匹配得分。在遍歷結束之后，依據匹配得分對整個鏈表進行排序，再根據設定的目標個數就可以確定相應的排序在前的那幾個得分就是目標點匹配得分，從而就可以確定多個匹配位置的坐標和旋轉角度。

3 算法實驗設計與結果分析

3.1 實驗設計

康耐視的PatMax目標定位算法是機器視覺領域中成熟穩定的算法，并且有相應的InSight圖片處理軟件。為了驗證本文目標定位算法針對圖像旋轉情況是否能夠正確進行目標定位，在PC端進行軟件算法設計，工具是Visual Studio 2013，編程實現本文采用的基于邊界特征梯度相似性度量的目標定位算法，并將兩者的匹配結果與康耐視InSight處理軟件上的匹配結果做比較。如圖1(a)、(b)分別是本文驗證算法采用的搜索圖像和模板圖像：

圖1 實驗采用的搜索圖像和模板圖像

3.2 實驗結果及分析

通過上面的實驗設計，并在PC端進行編程實現的結果記錄如圖2和表1所示：

圖2 本文算法的匹配結果圖

表1 兩種算法的匹配輸出坐標對比表

根據圖2(a)，我們可以看出，即使在圖像發生旋轉的情況下，本文算法也能正確定位到目標圖像。從圖2(b)可以看出，在角度搜索范圍內，本文的算法都能正確進行目標定位，并且能夠給出搜索圖像中的目標區域與模板圖像的匹配得分以及相對應的目標位置坐標。另外，本算法還給出搜索圖像中目標相對于模板的旋轉角度，分別為-69°、-26°和13°（規定順時針旋轉角度為正角度，逆時針旋轉為負角度），即代表其能夠在誤差接受范圍內確定出搜索圖像相對于模板圖像的旋轉角度。最后，搜索圖像中存在三個目標位置，采用本文的目標定位算法能夠定位處多個目標位置，從而也驗證了針對多目標場景的可行性。

通過表1可以看出，采用本文算法進行PC端進行代碼實現得到的匹配結果與康耐視相機處理結果相當，說明本文算法進行目標定位具有其準確性。針對不同旋轉角度下的多個目標位置，本文算法也能夠給出目標位置，說明該算法在圖像旋轉情況下具有其實用性，并且能夠實現多目標定位。

4 結束語

本文在金字塔逐步求精的基礎上，用邊界特征點處的梯度信息代替傳統上以像素點的灰度值來計算相似性度量。另外，考慮到搜索圖像中可能存在的多目標位置的情況，采用針對匹配得分為標準進行排序篩選從而能夠實現多目標定位。經過理論的分析以及實驗結果的驗證，可以本文基于邊界特征點梯度信息的目標定位算法能夠在圖像旋轉情況下具有其適用性和準確性，并且能夠在多目標的場景下也是可行的。