南京郵電大學(xué)電子與光學(xué)工程學(xué)院 陳志彭

1 引言

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

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

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

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

2.1 基于構(gòu)建圖像金字塔的匹配方法

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

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

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

2.2 基于梯度信息的相似性度量函數(shù)

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

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

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

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

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

根據(jù)上述關(guān)于邊界特征點(diǎn)的梯度相似性度量函數(shù)的介紹，接著詳細(xì)介紹算法設(shè)計實現(xiàn)的過程，包括模板和搜索圖像特征點(diǎn)提取及篩選、金字塔模型創(chuàng)建、匹配過程的梯度信息相似性度量計算和多目標(biāo)定位等。

2.3 算法設(shè)計與實現(xiàn)

2.3.1 特征點(diǎn)提取及篩選

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

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

2.3.2 構(gòu)建模板圖像和搜索圖像金字塔模型

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

為了給圖像匹配過程做好準(zhǔn)備，對搜索圖像也要采用與模板圖像相同的處理方法，構(gòu)建與模板圖像金字塔相同層數(shù)的搜索圖像金字塔。不同地方在于，已經(jīng)對模板圖像進(jìn)行旋轉(zhuǎn)處理得到不同角度下的模板梯度信息，就不需要去搜索圖像再做重復(fù)處理。

2.3.3 匹配過程的實現(xiàn)

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

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

2.3.4 多目標(biāo)匹配的實現(xiàn)

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

3 算法實驗設(shè)計與結(jié)果分析

3.1 實驗設(shè)計

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

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

3.2 實驗結(jié)果及分析

通過上面的實驗設(shè)計，并在PC端進(jìn)行編程實現(xiàn)的結(jié)果記錄如圖2和表1所示：

圖2 本文算法的匹配結(jié)果圖

表1 兩種算法的匹配輸出坐標(biāo)對比表

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

通過表1可以看出，采用本文算法進(jìn)行PC端進(jìn)行代碼實現(xiàn)得到的匹配結(jié)果與康耐視相機(jī)處理結(jié)果相當(dāng)，說明本文算法進(jìn)行目標(biāo)定位具有其準(zhǔn)確性。針對不同旋轉(zhuǎn)角度下的多個目標(biāo)位置，本文算法也能夠給出目標(biāo)位置，說明該算法在圖像旋轉(zhuǎn)情況下具有其實用性，并且能夠?qū)崿F(xiàn)多目標(biāo)定位。

4 結(jié)束語

本文在金字塔逐步求精的基礎(chǔ)上，用邊界特征點(diǎn)處的梯度信息代替?zhèn)鹘y(tǒng)上以像素點(diǎn)的灰度值來計算相似性度量。另外，考慮到搜索圖像中可能存在的多目標(biāo)位置的情況，采用針對匹配得分為標(biāo)準(zhǔn)進(jìn)行排序篩選從而能夠?qū)崿F(xiàn)多目標(biāo)定位。經(jīng)過理論的分析以及實驗結(jié)果的驗證，可以本文基于邊界特征點(diǎn)梯度信息的目標(biāo)定位算法能夠在圖像旋轉(zhuǎn)情況下具有其適用性和準(zhǔn)確性，并且能夠在多目標(biāo)的場景下也是可行的。