朱春麗,雷秀軍,申 遠(yuǎn)

(1.合肥師范學(xué)院 電子信息系統(tǒng)仿真設(shè)計(jì)安徽省重點(diǎn)實(shí)驗(yàn)室，安徽 合肥 230601；2.合肥富煌君達(dá)高科信息技術(shù)有限公司，安徽 合肥 230031)

隨著攝像技術(shù)和圖像處理技術(shù)的發(fā)展，視覺(jué)測(cè)量技術(shù)引起了人們的關(guān)注，它具有非接觸式、遠(yuǎn)距離測(cè)量、測(cè)量范圍大、測(cè)量精度高和價(jià)格便宜等優(yōu)點(diǎn)，且無(wú)附加質(zhì)量，不會(huì)對(duì)測(cè)量物體的動(dòng)態(tài)特性產(chǎn)生影響[1-3]。視覺(jué)測(cè)量技術(shù)利用相機(jī)拍攝物體的運(yùn)動(dòng)視頻，并使用數(shù)字圖像處理技術(shù)對(duì)視頻圖像分析、處理，從而實(shí)現(xiàn)物體的運(yùn)動(dòng)估計(jì)[4-6]。對(duì)于物體的運(yùn)動(dòng)估計(jì)，除了需要具備一定的硬件設(shè)備之外，還要具有高速、高精度、魯棒性的圖像匹配算法。其中模板匹配是圖像處理中最基本、最常用的匹配方法，在機(jī)器視覺(jué)中有著廣泛的運(yùn)用。早期的模板匹配主要應(yīng)用于遙感圖像的配準(zhǔn)[7]，現(xiàn)階段已廣泛應(yīng)用于智能交通、視頻監(jiān)控、目標(biāo)跟蹤、視覺(jué)檢測(cè)以及人機(jī)交互等[8-10]。

一般來(lái)說(shuō)，可以用多種方法獲得物體的運(yùn)動(dòng)信息，但為了實(shí)現(xiàn)較優(yōu)的模板匹配，需要得到一個(gè)標(biāo)量值作為匹配結(jié)果，再使用相關(guān)函數(shù)計(jì)算匹配結(jié)果即可得到運(yùn)動(dòng)的提取結(jié)果。本文以零均值歸一化標(biāo)準(zhǔn)互相關(guān)準(zhǔn)則(Zero-normalized Cross-correlation,ZNCC)作為模板匹配的評(píng)價(jià)標(biāo)準(zhǔn)。由于歸一化因子的存在，ZNCC準(zhǔn)則的計(jì)算結(jié)果在[-1,1]范圍內(nèi)，能夠直觀(guān)顯示模板匹配的效果和可靠性，并能夠進(jìn)行更深一步的計(jì)算，還能夠完美地避開(kāi)光照和噪聲所產(chǎn)生的干擾，魯棒性很強(qiáng)，因而，針對(duì)運(yùn)動(dòng)估計(jì)的圖像匹配，尤其在有光照變化等干擾存在的情況下，ZNCC反而是首選[11]。常用的基于模板匹配的位移提取算法有全局搜索(Full Search, FS)算法等[12-13]，本研究以ZNCC準(zhǔn)則作為模板匹配的評(píng)價(jià)標(biāo)準(zhǔn)，以做較大位移為主的橢圓和較小位移為主的螺旋線(xiàn)兩種運(yùn)動(dòng)的灰圓為計(jì)算示例，對(duì)以上四種位移算法的提取精度和速度進(jìn)行了比較分析。

模板匹配通過(guò)比較兩幅數(shù)字圖像之間的偏移從而獲得位移信息，無(wú)法滿(mǎn)足實(shí)際測(cè)量的高精度要求。另一種解決方案是改進(jìn)位移提取算法的定位精度，該方法簡(jiǎn)單、有效且成本低。在結(jié)構(gòu)動(dòng)態(tài)測(cè)量中，要求位移算法具有高響應(yīng)速度和高精度的特點(diǎn)，因此，在上述基于模板匹配的快速位移提取算法中引入曲面擬合法和梯度法兩種常用的亞像素定位方法[14-15]，并對(duì)其定位性能進(jìn)行了比較分析?；谀０迤ヅ涞目焖佟⒏呔任灰铺崛∷惴ê?jiǎn)單、有效且成本低，對(duì)于實(shí)際應(yīng)用中的動(dòng)態(tài)運(yùn)動(dòng)估計(jì)具有一定的參考價(jià)值。

1 算法簡(jiǎn)介

1.1 FS算法

FS是一種搜索精度很高的算法，步驟如下：

(1)以ZNCC為匹配準(zhǔn)則，從搜索區(qū)域的中心點(diǎn)開(kāi)始，按照由近及遠(yuǎn)的順序，計(jì)算目標(biāo)圖像中每個(gè)像素點(diǎn)與模板圖像的相關(guān)值CZNCC(xi,yi)；

(2)對(duì)比CZNCC(xi,yi)的大小，找到最大相關(guān)值所對(duì)應(yīng)的位置，則該位置即為所求的最佳匹配位置。

1.2 TSS算法和NTSS算法

TSS算法采用漸進(jìn)的搜索模式來(lái)尋找最佳匹配位置，具體搜索步驟如下：

(1)以ZNCC為匹配準(zhǔn)則，以搜索范圍的一半為搜索步長(zhǎng)，對(duì)于搜索區(qū)域的中心點(diǎn)以及與其相距距離為步長(zhǎng)的8個(gè)點(diǎn)，從中心點(diǎn)開(kāi)始，計(jì)算這9個(gè)點(diǎn)與模板圖像的相關(guān)值CZNCC(xi,yj)，對(duì)比CZNCC(xi,yj)的大小，找到最大相關(guān)值所對(duì)應(yīng)的位置；

(2)以上一步步長(zhǎng)的一半為搜索步長(zhǎng)，以上一步找到的最大相關(guān)值所對(duì)應(yīng)位置作為新的中心點(diǎn)，對(duì)于新的中心點(diǎn)以及與其相距距離為步長(zhǎng)的8個(gè)點(diǎn)，從中心點(diǎn)開(kāi)始，計(jì)算這9個(gè)點(diǎn)與模板圖像的相關(guān)值CZNCC(xi,yj)，對(duì)比CZNCC(xi,yj)的大小，找到最大相關(guān)值所對(duì)應(yīng)的位置；

(3)重復(fù)步驟2，直到步長(zhǎng)減少到1，此時(shí)，最大相關(guān)值所對(duì)應(yīng)的位置即為所求的最佳匹配位置。

TSS算法不需要遍歷目標(biāo)圖像中的所有像素點(diǎn)，搜索效率遠(yuǎn)高于FS算法，但第一步搜索步長(zhǎng)較大，采用固定的搜索路徑進(jìn)行搜索，易陷入局部最優(yōu)，對(duì)靜止或微小位移的提取效果不好。于是，提出了具有自適應(yīng)的NTSS算法，其改進(jìn)之處如下：

(1)搜索點(diǎn)除了中心點(diǎn)以及與其相距距離為步長(zhǎng)的8個(gè)點(diǎn)之外，還要增加搜索區(qū)域中心點(diǎn)的8鄰域點(diǎn)；

(2)對(duì)于靜止或者微小位移的提取：若最大相關(guān)值在中心點(diǎn)處，則停止搜索；若最大相關(guān)值出現(xiàn)在中心點(diǎn)的8鄰域，則以最大相關(guān)值所對(duì)應(yīng)位置作為新的中心點(diǎn)，計(jì)算新中心點(diǎn)的8鄰域，找出最大相關(guān)值，重復(fù)以上步驟，直到最大相關(guān)值出現(xiàn)在新的中心點(diǎn)處；

(3)對(duì)于相對(duì)較大位移的提?。鹤畲笙嚓P(guān)值出現(xiàn)在與搜索中心點(diǎn)相距距離為步長(zhǎng)的8個(gè)點(diǎn)處，執(zhí)行TSS算法的步驟2和步驟3。

對(duì)于相對(duì)較大位移的搜索路徑，NTSS算法和TSS算法的搜索原理一致。此外，它還兼顧了靜止或微小位移的提取。

1.3 DS算法

不同于TSS算法所采用的固定搜索路徑，DS算法針對(duì)相對(duì)較大位移和靜止或者微小位移的提取，采用大范圍搜索(搜索9個(gè)點(diǎn))和小范圍搜索(搜索5個(gè)點(diǎn))兩種搜索路徑，搜索過(guò)程穩(wěn)定，且不易陷入局部最優(yōu)。DS算法的具體搜索步驟如下：

(1)以ZNCC為匹配準(zhǔn)則，從搜索區(qū)域的中心點(diǎn)開(kāi)始，進(jìn)行大范圍菱形搜索，若最大相關(guān)值在中心點(diǎn)處，執(zhí)行步驟3，否則執(zhí)行步驟2；

(2)以上一步找到的最大相關(guān)值所對(duì)應(yīng)位置作為新的中心點(diǎn)，進(jìn)行大范圍菱形搜索，若最大相關(guān)值在新的中心點(diǎn)處，執(zhí)行步驟3，否則重復(fù)執(zhí)行步驟2；

(3)以上一步找到的最大相關(guān)值所對(duì)應(yīng)位置作為新的中心點(diǎn)，進(jìn)行小范圍搜索，找到最大相關(guān)值所對(duì)應(yīng)的位置，則該位置即為所求的最佳匹配位置。

1.4 曲面擬合法

進(jìn)行模板匹配時(shí)，最大相關(guān)系數(shù)點(diǎn)(整像素點(diǎn))附近為一光滑曲面，該曲面的極值點(diǎn)所在位置即為圖像的最佳匹配位置。因此，可以利用相關(guān)系數(shù)矩陣擬合曲面，然后計(jì)算曲面函數(shù)的極值點(diǎn)，從而得到亞像素等級(jí)的位移估計(jì)。

實(shí)際應(yīng)用于位移估計(jì)時(shí)，為了減少計(jì)算量，本文選擇最大相關(guān)系數(shù)點(diǎn)及其周?chē)?個(gè)點(diǎn)進(jìn)行曲面擬合。由于曲面變化較為平緩，采用二元二次多項(xiàng)式擬合曲面。具體步驟如下：

(1)用二元二次多項(xiàng)式擬合曲面，擬合窗口大小選為3×3，獲得9個(gè)等式；

(2)用最小二乘法完成該二次曲面系數(shù)的求解；

(3)對(duì)二次曲面函數(shù)進(jìn)行微分，求出曲面極值點(diǎn)的位置。

1.5 梯度法

基于梯度的亞像素定位算法最早是由 Davis 等提出的[15], 其基本思想是假設(shè)圖像平移前后沒(méi)有發(fā)生變化。利用基于梯度的亞像素位移算法求解位移時(shí)只需要計(jì)算出模板圖像的灰度梯度，相對(duì)來(lái)說(shuō)易于實(shí)現(xiàn)。

2 結(jié)果

2.1 計(jì)算示例

為了防止出現(xiàn)局部最優(yōu)等現(xiàn)象干擾對(duì)FS、TSS、NTSS、DS四種算法計(jì)算精度和速度的判斷，采用相關(guān)函數(shù)分辨特性較好的灰圓作為計(jì)算示例。另外，為了比較四種位移提取算法對(duì)不同位移尺度的適應(yīng)性，令灰圓做不同位移尺度的運(yùn)動(dòng)，這里令其作較大位移尺度為主的橢圓運(yùn)動(dòng)和較小位移尺度為主的螺旋線(xiàn)運(yùn)動(dòng)，運(yùn)動(dòng)周期為2 s，運(yùn)動(dòng)軌跡如圖1中的深色路線(xiàn)所示。

圖1 圓模板的運(yùn)動(dòng)軌跡圖

2.2 四種位移提取算法的對(duì)比分析

灰圓模板作較大位移為主的橢圓運(yùn)動(dòng)時(shí)，搜索區(qū)域是以圓心為中心，范圍為[-15像素,15像素]的方形區(qū)域。四種搜索算法提取出的灰圓沿x和y方向的位移矢量如圖2所示，可以看出四種搜索算法的提取結(jié)果基本重疊，均能較好地提取出灰圓的運(yùn)動(dòng)軌跡。另外，通過(guò)比較提取的位移矢量和灰圓的運(yùn)動(dòng)軌跡，發(fā)現(xiàn)每一種搜索算法的計(jì)算精度均在[-0.5像素，0.5像素]之間。因?yàn)榛谙嚓P(guān)函數(shù)進(jìn)行模板匹配時(shí)，計(jì)算精度為像素量級(jí)，四種搜索算法均采用ZNCC準(zhǔn)則，因此從理論上來(lái)講，它們的計(jì)算精度等級(jí)都是一樣的，和圖2所示的計(jì)算結(jié)果相一致。

圖2 利用四種搜索算法提取橢圓軌跡

四種搜索算法均采用ZNCC準(zhǔn)則，采用不同搜索算法計(jì)算一個(gè)像素點(diǎn)的相關(guān)值所需的時(shí)間是相同的，因此可以用提取位移信息整個(gè)過(guò)程所需搜索的點(diǎn)數(shù)來(lái)評(píng)價(jià)計(jì)算速度。FS算法對(duì)目標(biāo)圖像中的所有像素點(diǎn)進(jìn)行相關(guān)性運(yùn)算，所需要搜索的點(diǎn)數(shù)遠(yuǎn)遠(yuǎn)大于其它幾種搜索算法，計(jì)算速度最慢，下面將不再作統(tǒng)一比較。隨著灰圓作橢圓運(yùn)動(dòng)時(shí)間的增加，TSS、NTSS、DS三種搜索算法所需的搜索點(diǎn)數(shù)如圖3所示。可以看出，隨著灰圓作橢圓運(yùn)動(dòng)時(shí)間的增加，TSS和NTSS算法的搜索點(diǎn)數(shù)均不變，DS算法的搜索點(diǎn)數(shù)劇烈變化。

圖3 利用三種搜索算法提取橢圓軌跡所需的搜索點(diǎn)數(shù)

另外，NTSS算法的搜索點(diǎn)數(shù)大于TSS算法，DS算法的平均搜索點(diǎn)數(shù)也大于TSS算法，因?yàn)樵赥SS算法的基礎(chǔ)上，NTSS算法還兼顧了靜止或微小位移的提取，DS算法針對(duì)相對(duì)較大位移和靜止或者微小位移的提取，采用了大范圍搜索和小范圍搜索兩種搜索路徑。對(duì)于位移較大的橢圓運(yùn)動(dòng)，NTSS和DS算法會(huì)浪費(fèi)一些搜索時(shí)間，TSS算法反而是最適合的搜索方法。

為了驗(yàn)證運(yùn)動(dòng)軌跡以小位移為主時(shí)四種算法的適應(yīng)性，本文計(jì)算了灰圓模板作小范圍螺旋線(xiàn)運(yùn)動(dòng)時(shí)的位移提取結(jié)果和搜索點(diǎn)數(shù)。相對(duì)于較大位移為主的橢圓運(yùn)動(dòng)，縮小了螺旋線(xiàn)軌跡的運(yùn)動(dòng)范圍和搜索范圍，搜索區(qū)域是以圓心為中心，范圍為[-7像素,7像素]的方形區(qū)域，四種搜索算法提取出的灰圓沿x和y方向的位移矢量如圖4所示。同樣，四種搜索算法均能較好地提取出灰圓的運(yùn)動(dòng)軌跡，且計(jì)算精度均在[-0.5像素,0.5像素]之間。

圖4 利用四種搜索算法提取螺旋線(xiàn)軌跡

隨著灰圓作螺旋線(xiàn)運(yùn)動(dòng)時(shí)間的增加，TSS、NTSS、DS三種搜索算法所需的搜索點(diǎn)數(shù)如圖5所示。

圖5 利用三種搜索算法提取螺旋線(xiàn)軌跡所需的搜索點(diǎn)數(shù)

可以看出，隨著灰圓作螺旋線(xiàn)運(yùn)動(dòng)時(shí)間的增加，TSS算法的搜索點(diǎn)數(shù)不變，均為33個(gè)點(diǎn)。對(duì)于NTSS算法，位移較小的一段時(shí)間內(nèi)，搜索點(diǎn)數(shù)為17，位移逐漸增大的一段時(shí)間內(nèi)，搜索點(diǎn)數(shù)增加為25，位移更大時(shí)，搜索點(diǎn)數(shù)便大于TSS算法了，與大范圍橢圓運(yùn)動(dòng)時(shí)的結(jié)果一致。對(duì)于DS算法，搜索點(diǎn)數(shù)依然波動(dòng)劇烈，但平均來(lái)看，在位移較小的一段時(shí)間內(nèi)，搜索點(diǎn)數(shù)遠(yuǎn)小于TSS和NTSS算法，位移逐漸增大后，搜索點(diǎn)數(shù)與TSS算法相當(dāng)。因此，對(duì)于小位移為主的螺旋線(xiàn)運(yùn)動(dòng)，DS算法更為合適。

2.3 亞像素位移測(cè)量算法的性能比較

同樣以灰圓作為仿真對(duì)象，使其做步長(zhǎng)為0.05像素的平移運(yùn)動(dòng)，位移范圍為[-0.5像素，0.5像素]。為了看清楚模板大小對(duì)精度和效率的影響，選擇了三種計(jì)算模板，大小分別為 21像素×21像素、51像素×51像素和81像素×81像素，兩種算法的平均計(jì)算誤差如表1所示。

由表1可以看出，模板較小時(shí)，曲面擬合的誤差遠(yuǎn)大于梯度法的誤差，隨著模板的增大，兩種算法的定位誤差均逐漸減小，且差別也越來(lái)越小。

表1 兩種亞像素定位算法的平均計(jì)算誤差(×10-3像素)

為了獲得亞像素精度的位移結(jié)果，需在原有基于模板匹配的位移提取算法基礎(chǔ)上，加上亞像素定位算法。在此，只比較加上亞像素定位算法之后，位移提取算法額外增加的計(jì)算時(shí)間，統(tǒng)計(jì)結(jié)果如表2所示。曲面擬合法額外增加的時(shí)間便是擬合曲面和計(jì)算極值所需的時(shí)間，從表2可以看出，該時(shí)間與模板大小無(wú)關(guān)，均為0.007 s。梯度法額外增加的時(shí)間便是求解目標(biāo)函數(shù)梯度和亞像素位移所需的時(shí)間，可以看出，計(jì)算時(shí)間遠(yuǎn)遠(yuǎn)大于曲面擬合法額外增加的計(jì)算時(shí)間，且隨著模板的增大而增大。

表2 兩種亞像素定位算法額外增加的計(jì)算時(shí)間 s

實(shí)際應(yīng)用中，需綜合考慮算法精度和計(jì)算時(shí)間，因而曲面擬合法更加適用。在基于模板匹配的DS位移提取算法基礎(chǔ)上，利用曲面擬合法求解圖1(b)中灰圓的螺旋線(xiàn)運(yùn)動(dòng)，其中模板大小為51×51像素，y方向的位移矢量結(jié)果如圖6所示?？梢钥闯觯肈S算法的提取結(jié)果呈階梯狀，誤差大小為[-0.5像素，0.5像素]，加上曲面擬合算法之后，位移結(jié)果能夠比較完美的接近實(shí)際運(yùn)動(dòng)曲線(xiàn)。

圖6 利用曲面擬合法提取螺旋線(xiàn)y方向位移矢量的結(jié)果

3 結(jié)論

以作橢圓和螺旋線(xiàn)兩種運(yùn)動(dòng)的灰圓模板為計(jì)算示例，比較分析了基于模板匹配的FS、TSS、NTSS、DS四種搜索算法對(duì)位移信息的提取精度和速度的影響。四種搜索算法均以ZNCC為匹配準(zhǔn)則，計(jì)算精度一樣，均為像素量級(jí)。FS算法要遍歷目標(biāo)圖像中的每一個(gè)點(diǎn)，最為耗時(shí)，不適合解決實(shí)際應(yīng)用中的實(shí)時(shí)性問(wèn)題。TSS、NTSS、DS三種搜索算法的搜索速度均遠(yuǎn)遠(yuǎn)超過(guò)了FS算法，可分別適用于解決不同實(shí)際應(yīng)用中的實(shí)時(shí)性問(wèn)題。TSS算法采用漸進(jìn)的搜索模式來(lái)尋找最佳匹配位置，但TSS算法的第一步搜索步長(zhǎng)較大，采用固定的搜索路徑進(jìn)行搜索，易陷入局部最優(yōu)，對(duì)靜止或微小位移的提取效果不好，適于范圍較大位移的提取。NTSS算法具有自適應(yīng)性，它在TSS算法的基礎(chǔ)上，還兼顧了靜止或微小位移的提取，相對(duì)于TSS算法，更適于小位移存在的運(yùn)動(dòng)估計(jì)。DS算法針對(duì)相對(duì)較大位移和靜止或者微小位移的提取，采用大范圍搜索和小范圍搜索兩種搜索路徑，搜索過(guò)程穩(wěn)定，是搜索性能最為優(yōu)異的快速匹配算法之一，對(duì)于小位移為主的運(yùn)動(dòng)估計(jì)，DS算法最為合適。為了獲得亞像素級(jí)的定位精度，本文還比較分析了常用的曲面擬合法和梯度法兩種亞像素定位算法的性能。在原基于模板匹配的位移提取算法基礎(chǔ)上，曲面擬合法額外增加的時(shí)間便是擬合曲面和計(jì)算極值所需的時(shí)間，遠(yuǎn)小于梯度法額外增加的時(shí)間。實(shí)際應(yīng)用中，綜合考慮算法精度和計(jì)算時(shí)間，曲面擬合法更加適用。本文的比較分析結(jié)果對(duì)基于視覺(jué)的實(shí)際運(yùn)動(dòng)估計(jì)的算法選擇具有一定的參考價(jià)值。