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

1 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3.3 匹配過(guò)程的實(shí)現(xiàn)

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

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

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

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

3 算法實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

3.1 實(shí)驗(yàn)設(shè)計(jì)

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

圖1 實(shí)驗(yàn)采用的搜索圖像和模板圖像

3.2 實(shí)驗(yàn)結(jié)果及分析

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

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

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

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

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

4 結(jié)束語(yǔ)

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