朱奇光　王梓巍　陳　穎

1.燕山大學(xué)，秦皇島，0660042.河北省特種光纖與光纖傳感重點(diǎn)實(shí)驗(yàn)室，秦皇島，066004

?

基于全局特征與局部特征的圖像分級(jí)匹配算法研究及應(yīng)用

朱奇光1,2王梓巍1陳穎1

1.燕山大學(xué)，秦皇島，0660042.河北省特種光纖與光纖傳感重點(diǎn)實(shí)驗(yàn)室，秦皇島，066004

移動(dòng)機(jī)器人基于拓?fù)涞貓D導(dǎo)航時(shí)要求圖像特征提取與匹配算法具有高的精度和魯棒性、良好的實(shí)時(shí)性，針對(duì)此，提出了基于全局特征和局部特征的圖像分級(jí)匹配算法。首先對(duì)輸入的待匹配圖像應(yīng)用改進(jìn)的形狀上下文算法提取全局特征與圖像庫(kù)中圖像進(jìn)行遍歷粗匹配，得到與當(dāng)前待匹配圖像相似度最高的3幅圖像并構(gòu)建臨時(shí)圖像庫(kù)；然后利用改進(jìn)的SIFT算法提取輸入圖像局部特征與臨時(shí)圖像庫(kù)中3幅圖像的局部特征進(jìn)行精確匹配，最終得到與待匹配圖像相似度最高的圖像作為匹配結(jié)果輸出。所提出的圖像分級(jí)匹配算法將基于全局特征的改進(jìn)形狀上下文算法和基于局部特征的改進(jìn)SIFT算法相結(jié)合，從而達(dá)到優(yōu)勢(shì)互補(bǔ)的目的。實(shí)驗(yàn)結(jié)果表明，該算法在機(jī)器人基于拓?fù)涞貓D導(dǎo)航過(guò)程中有效地提高了圖像匹配效率，縮短了運(yùn)行時(shí)間。

移動(dòng)機(jī)器人；圖像匹配；改進(jìn)形狀上下文；改進(jìn)SIFT

0　引言

在未知的環(huán)境中機(jī)器人依靠自身攜帶的傳感器創(chuàng)建環(huán)境模型是當(dāng)前機(jī)器人研究領(lǐng)域的一個(gè)熱點(diǎn)問(wèn)題[1]。拓?fù)涞貓D是目前常用的一種環(huán)境模型。拓?fù)涞貓D中，最重要的是節(jié)點(diǎn)的創(chuàng)建與識(shí)別。機(jī)器人將提取的具有較強(qiáng)識(shí)別性的環(huán)境特征與拓?fù)涔?jié)點(diǎn)綁定，在進(jìn)行環(huán)境特征互相匹配時(shí)，需要有效地識(shí)別不同拓?fù)涔?jié)點(diǎn)，最終實(shí)現(xiàn)機(jī)器人拓?fù)涞貓D的創(chuàng)建和導(dǎo)航。

通過(guò)研究基于圖像特征進(jìn)行圖像匹配的文獻(xiàn)發(fā)現(xiàn)，大部分學(xué)者均是將彩色圖像轉(zhuǎn)換為灰度圖像，僅僅利用亮度信息提取圖像特征[2]。在實(shí)際應(yīng)用中應(yīng)充分將亮度特征與顏色、紋理和形狀等特征相結(jié)合，提高圖像匹配的精確度和魯棒性。劉佳等[3]提出了基于多分辨率小波分解的改進(jìn)尺度不變特征變換(scaleinvariantfeaturetransform,SIFT)[4]圖像匹配算法，改進(jìn)后的算法提高了匹配精度，具有較好的定位效果，但是實(shí)時(shí)性較差，不滿(mǎn)足機(jī)器人導(dǎo)航的要求；Lu等[5]提出了基于顏色矩的改進(jìn)SIFT圖像匹配算法，該改進(jìn)算法提高了圖像匹配的速度，但顏色特征丟失了空間的位置信息，且顏色特征受光照變化影響較大，魯棒性較差；陳抒瑢等[6]提出全局紋理特征與SIFT特征相結(jié)合的圖像匹配算法，該算法對(duì)圖像尺度、旋轉(zhuǎn)、光照、視角等變化具有很強(qiáng)的魯棒性，但是計(jì)算量較大，無(wú)法滿(mǎn)足機(jī)器人導(dǎo)航的實(shí)時(shí)性要求；Zhong等[7]提出了融合局部形狀信息與SIFT特征的圖像匹配算法，改進(jìn)后的算法能有效地降低錯(cuò)配概率，獲得良好的仿射不變性，但是其計(jì)算量過(guò)大，降低了算法的匹配效率；高晶等[8]提出了一種基于曲率尺度空間提取關(guān)鍵點(diǎn)的角點(diǎn)檢測(cè)的圖像匹配算法，在噪聲干擾、尺度縮放、亮度變化的情況下具有較好的匹配效果，但是圖像特征匹配的速度有待提高。

移動(dòng)機(jī)器人基于拓?fù)涞貓D導(dǎo)航時(shí)要求圖像特征提取與匹配算法具有高的精度和魯棒性，且有較好的實(shí)時(shí)性，針對(duì)此，提出了基于全局特征和局部特征的圖像分級(jí)匹配算法。該算法將圖像匹配分為粗匹配和精匹配兩個(gè)階段，融合全局特征和局部特征，從而達(dá)到優(yōu)勢(shì)互補(bǔ)的目的。

1　改進(jìn)的圖像匹配算法

1.1改進(jìn)的圖像匹配算法粗匹配

在圖像匹配過(guò)程中，相比于紋理特征和顏色特征，形狀特征是一種高級(jí)別的視覺(jué)信息，它所描述的視覺(jué)信息層次更高，范圍更大[9]。

形狀上下文特征是一種經(jīng)典的輪廓描述子，該描述子從輪廓點(diǎn)的空間位置出發(fā)，利用對(duì)數(shù)極坐標(biāo)直方圖對(duì)圖像中的物體輪廓分布情況進(jìn)行統(tǒng)計(jì)以實(shí)現(xiàn)圖像匹配[10]。但是原始的形狀上下文描述子并不能準(zhǔn)確地反映輪廓的全局特征，它只能計(jì)算出每個(gè)區(qū)域內(nèi)所含特征點(diǎn)的數(shù)量，著重描述整體輪廓分割后的局部輪廓，缺少全局信息。同時(shí)對(duì)平面進(jìn)行分割時(shí)涉及參數(shù)(距離與角度)的確定，降低了算法的適應(yīng)性。最重要的是形狀上下文算法忽略了輪廓點(diǎn)之間的重要信息——順序關(guān)系。

針對(duì)形狀上下文算法存在的問(wèn)題，本文采用改進(jìn)的形狀上下文算法。采用改進(jìn)的形狀上下文算法可得到以vi為參考點(diǎn)的由N個(gè)點(diǎn)構(gòu)成的輪廓空間，利用輪廓的順序關(guān)系將所有的上下文信息組合起來(lái)形成一個(gè)特征序列。

改進(jìn)的形狀上下文算法前期處理與原始形狀上下文算法一致，得到以采樣點(diǎn)vi為原點(diǎn)的其余N-1個(gè)點(diǎn)在極坐標(biāo)系中的相對(duì)極坐標(biāo)l(vi,vj)：

l(vi,vj)=li,j=(vi,vj)j=1,2,…,N；j≠i

(1)

因?yàn)檩喞c(diǎn)在形狀中具有自然的順序關(guān)系，根據(jù)此順序關(guān)系將式(1)表示的所有相對(duì)坐標(biāo)數(shù)據(jù)li,j改寫(xiě)成序列Li：

Li=(li,i+1,li,i+2,…li,N,li,1,…,li,i-2,li,i-1)T

(2)

式(2)即改進(jìn)的形狀上下文描述子。

與原始的形狀上下文描述子相比，改進(jìn)的形狀上下文描述子在包含輪廓點(diǎn)上下文信息的同時(shí)，還可以利用輪廓點(diǎn)的先后順序關(guān)系，準(zhǔn)確地描述形狀的全局信息；對(duì)二維平面不需要進(jìn)行分割，從而免除了確定若干分割參數(shù)的麻煩，減小算法計(jì)算量，同時(shí)提高了算法的通用性。

為了保證改進(jìn)的形狀上下文描述子具有尺度不變性，對(duì)其進(jìn)行局部歸一化處理。將每個(gè)輪廓點(diǎn)的形狀上下文描述子Li按順序進(jìn)行排列，組成(N-1)×N的矩陣:

A=A(V)=[L1L2L3…LN-1LN]

(3)

分別對(duì)矩陣A的每一行進(jìn)行歸一化：

(4)

若所有的輪廓點(diǎn)都計(jì)算其形狀上下文特征，則會(huì)導(dǎo)致對(duì)輪廓的描述過(guò)于精細(xì)，對(duì)形狀變形過(guò)于敏感。為了平衡描述子在準(zhǔn)確性和敏感性之間的矛盾，提高其魯棒性，我們對(duì)改進(jìn)的形狀上下文描述子進(jìn)行平滑化處理[11]。

改進(jìn)的形狀上下文描述子可表示為

(5)

式(5)包括N-1個(gè)序列，將此序列劃分為若干個(gè)互不相交的子序列:[1，t],[t+1，2t],[2t +1，3t],…。其中t是設(shè)定的正整數(shù)。然后分別對(duì)于每一個(gè)子序列計(jì)算其分量的均值：

(6)

其中,c=1，2，…，W，c表示劃分后第c個(gè)子序列的序號(hào)，W=(N-1)/t。由此W個(gè)均值構(gòu)成了平滑化處理后的改進(jìn)上下文描述子：

(7)

改進(jìn)的上下文描述子經(jīng)過(guò)平滑化處理后提高了魯棒性，同時(shí)降低了描述子維度，有效提高了算法運(yùn)行效率。兩個(gè)輪廓首先進(jìn)行形狀匹配，然后再進(jìn)行相似性度量。形狀匹配問(wèn)題的實(shí)質(zhì)就是通過(guò)計(jì)算形狀之間的匹配代價(jià)(對(duì)應(yīng)點(diǎn)之間的歐氏距離)，然后應(yīng)用動(dòng)態(tài)規(guī)劃算法尋找兩個(gè)輪廓點(diǎn)序列之間最佳對(duì)應(yīng)關(guān)系(匹配代價(jià)最小)。相似性度量時(shí)，分別計(jì)算輪廓的形狀復(fù)雜性，然后再求取形狀復(fù)雜性之間的歐氏距離。

1.2改進(jìn)的圖像匹配算法精確匹配

針對(duì)SIFT算法因計(jì)算量大而導(dǎo)致在圖像匹配階段實(shí)時(shí)性較差的問(wèn)題，本文提出了改進(jìn)的SIFT算法。該算法通過(guò)減法聚類(lèi)剔除冗余的特征點(diǎn)，將得到的特征描述子二值化，根據(jù)hash函數(shù)生成索引，以漢明距離進(jìn)行相似性度量。改進(jìn)后的算法實(shí)時(shí)性較好，匹配效率較高。

原始SIFT算法大量的特征點(diǎn)中含有許多相似度非常高的特征點(diǎn)，在圖像匹配中作用非常小，卻增加了后續(xù)運(yùn)算的復(fù)雜度。在改進(jìn)的SIFT算法中，應(yīng)用減法聚類(lèi)剔除冗余的特征點(diǎn)。

減法聚類(lèi)是一種密度聚類(lèi)的算法，可以快速查找數(shù)據(jù)的數(shù)目和中心[12]。假設(shè)檢測(cè)出n個(gè)特征點(diǎn)組成的集合{x1,x2,…,xn}。改進(jìn)的SIFT特征點(diǎn)檢測(cè)步驟如下：

(1)首先根據(jù)下式計(jì)算特征點(diǎn)集合中每個(gè)特征點(diǎn)的密度，得到密度指標(biāo)M(xi)：

(8)

其中，r1為鄰域半徑，d(xk,xi)為xk與xi的歐氏距離。根據(jù)文獻(xiàn)[13]及多次實(shí)驗(yàn)驗(yàn)證可知取r1=1.6為最優(yōu)值，實(shí)驗(yàn)效果最理想。

(2)將尋找到的密度指標(biāo)值最大的特征點(diǎn)作為首個(gè)聚類(lèi)中心，然后除去該特征點(diǎn)的密度，再計(jì)算其他特征點(diǎn)的密度指標(biāo)值Mk(xi)。

(9)

其中，r2=1.5 r1。

(3)按照上述步驟再次尋找密度指標(biāo)的最大值，并把該特征點(diǎn)作為聚類(lèi)中心，直到?jīng)]有新的聚類(lèi)中心產(chǎn)生，則迭代終止。

SIFT算法的128維特征描述子匹配能力較強(qiáng)，但其數(shù)據(jù)量過(guò)大。改進(jìn)SIFT算法對(duì)特征描述子進(jìn)行二值化處理，保留特征描述子信息的同時(shí)大幅度減小數(shù)據(jù)量，從而提高了算法運(yùn)行速度[14]。

將減法聚類(lèi)運(yùn)算處理后的特征點(diǎn)所生成的特征描述子進(jìn)行二值化，把128維特征向量轉(zhuǎn)化為128位的二進(jìn)制字符串。假設(shè)128維特征向量S=(S0，S1,…S127)。

(1)首先根據(jù)下式計(jì)算同一向量中Si(Si是特征描述子某一維的數(shù)值)和Si+1差的絕對(duì)值：

(2)根據(jù)Qi值，按下式計(jì)算128位二進(jìn)制特征向量中每位數(shù)值bi，得到二值化的特征描述子b={b0, b1,…，b127}：

(11)

式(11)中R為差值的閾值，其作用是將式(10)所得的差值均勻分成兩部分。本文取R=14。

針對(duì)改進(jìn)的特征描述子本文利用hash值作為索引，以漢明距離度量特征描述子之間的相似度。改進(jìn)后的特征匹配方法提高了檢索效率。

首先根據(jù)hash函數(shù)計(jì)算出代表特征點(diǎn)的128位二進(jìn)制字符串的hash值。令

Ni=bi×8×20+bi×8×21+…+bi×8×27

(12)

其中i=0,1，…,15，并且N16= N0。同時(shí)：

(13)

hash函數(shù)定義如下：

H(h0,h1，…,h15)=h0×20+h1×21+…+h15×215

(14)

其計(jì)算結(jié)果即hash值，變化范圍為0～65 535。

在匹配階段首先對(duì)待查詢(xún)圖像執(zhí)行改進(jìn)的特征點(diǎn)檢測(cè)步驟并生成描述子，將生成的二值化特征描述子根據(jù)式(14)計(jì)算其hash值并在hash庫(kù)中進(jìn)行檢索。

ni代表圖像i與當(dāng)前查詢(xún)圖像之間相似特征描述子的數(shù)量，初始化ni=0。計(jì)算兩個(gè)特征描述子之間的漢明距離，若小于閾值則ni←ni+1，表示兩個(gè)圖像之間存在一對(duì)匹配成功特征。當(dāng)待匹配圖像所有的特征均在hash庫(kù)中進(jìn)行了檢索，則根據(jù)ni最大值決定匹配成功的圖像。

1.3圖像分級(jí)匹配算法總體流程

移動(dòng)機(jī)器人基于拓?fù)涞貓D導(dǎo)航時(shí)，節(jié)點(diǎn)識(shí)別采用基于全局特征與局部特征的圖像分級(jí)匹配算法。該算法總體流程如圖1所示。

圖1　算法流程圖

首先對(duì)輸入的待匹配圖像應(yīng)用改進(jìn)的形狀上下文算法提取全局特征與圖像庫(kù)中圖像進(jìn)行遍歷粗匹配，得到與當(dāng)前待匹配圖像相似度最高的3幅圖像并構(gòu)建臨時(shí)圖像庫(kù)；然后利用改進(jìn)的SIFT算法提取輸入圖像和臨時(shí)圖像庫(kù)中3幅圖像的局部特征，并進(jìn)行精確匹配，最終得到與待匹配圖像相似度最高的圖像作為匹配結(jié)果輸出。

2　實(shí)驗(yàn)與仿真研究

本文實(shí)驗(yàn)和仿真研究采用Pioneer3TM平臺(tái)，其中視覺(jué)系統(tǒng)的單目攝像頭為CanonVC-C50i，其垂直方向旋轉(zhuǎn)范圍為±30°，水平方向旋轉(zhuǎn)范圍為±100°，最大分辨率為704pixel×576pixel。實(shí)驗(yàn)仿真部分均基于配置為i3-2310MCPU2.10GHZ、內(nèi)存2GB的PC機(jī)，并以MATLAB8.1為平臺(tái)進(jìn)行。移動(dòng)機(jī)器人平臺(tái)和視覺(jué)攝像頭分別如圖2和圖3所示。

圖2　移動(dòng)機(jī)器人平臺(tái) 　　　 圖3　視覺(jué)攝像頭

2.1實(shí)驗(yàn)參數(shù)的設(shè)定

改進(jìn)的形狀上下文算法主要涉及三個(gè)參數(shù)的設(shè)定:輪廓采樣點(diǎn)數(shù)N；平滑化處理參數(shù)t；形狀描述子長(zhǎng)度W。

改進(jìn)的形狀上下文算法輪廓采樣點(diǎn)數(shù)的設(shè)置與許多常見(jiàn)形狀輪廓描述子相同，取N=100。經(jīng)過(guò)多次仿真實(shí)驗(yàn)驗(yàn)證，當(dāng)N=100時(shí)，能夠得到一個(gè)運(yùn)算速度和準(zhǔn)確率平衡的實(shí)驗(yàn)結(jié)果。

若改進(jìn)的算法采納所有采樣點(diǎn)的數(shù)據(jù)，則對(duì)形狀的描述過(guò)于精細(xì)，從而降低了算法對(duì)局部形變的魯棒性。為了在精確性與魯棒性之間取得良好的折中，本文采用平滑化處理技術(shù)對(duì)采樣點(diǎn)進(jìn)行處理。根據(jù)本文所提出算法在實(shí)驗(yàn)所需的圖像庫(kù)中進(jìn)行檢索，得到如圖4所示的圖像檢索準(zhǔn)確率η與平滑化處理參數(shù)t的關(guān)系。由圖4可知，當(dāng)t=6時(shí)，圖像檢索準(zhǔn)確率η最高，實(shí)驗(yàn)效果最佳。

圖4　圖像檢索精度與平滑化處理參數(shù)的關(guān)系

本文算法的形狀描述子特征向量維數(shù)W=(N-1)/t，即特征向量的維數(shù)由采樣點(diǎn)數(shù)量和平滑化參數(shù)確定。根據(jù)N=100，t=6，可得W=16。由于每個(gè)特征向量都描述一個(gè)二維坐標(biāo)數(shù)據(jù)，因此改進(jìn)后的形狀描述子特征向量實(shí)際維數(shù)為2W=32。與形狀上下文描述子特征向量60維[15]，內(nèi)距離形狀上下文描述子[16]特征向量90維相比，改進(jìn)的算法特征向量維數(shù)較低，運(yùn)算效率較高。

改進(jìn)的SIFT算法的主要參數(shù)是閾值R。R的作用是將式(10)所得的差值均勻分成兩部分。實(shí)驗(yàn)隨機(jī)選取圖像庫(kù)9幅圖像作為實(shí)驗(yàn)圖像，統(tǒng)計(jì)同一特征符128維數(shù)值間相鄰數(shù)值差的絕對(duì)值信息。通過(guò)對(duì)實(shí)驗(yàn)數(shù)據(jù)(圖5)進(jìn)行分析可知：S1區(qū)域共包含96 535個(gè)差值，S2區(qū)域共包含96 557個(gè)差值。即R=14時(shí)，可以將所有差值的絕對(duì)值分成數(shù)量相等的兩組。

圖5　差值絕對(duì)值的數(shù)量分布圖

2.2圖像匹配實(shí)驗(yàn)

改進(jìn)的形狀上下文算法幾何意義明確、易于計(jì)算、描述性強(qiáng)，圖像的匹配效果較好。相對(duì)于原始的形狀上下文算法，改進(jìn)算法避免了直方圖計(jì)算、參數(shù)選取等問(wèn)題，保留了較為準(zhǔn)確的輪廓點(diǎn)相對(duì)位置信息，通過(guò)輪廓點(diǎn)的順序關(guān)系增加了描述子的全局形狀信息。根據(jù)2.1節(jié)可知改進(jìn)后的形狀上下文描述子維數(shù)為32。與形狀上下文描述子特征向量60維、SIFT描述子特征向量128維相比，改進(jìn)的形狀上下文圖像匹配算法描述子維數(shù)較低，運(yùn)算效率較高。與使用SIFT算法相此，改進(jìn)的形狀上下文算法將待匹配與圖像庫(kù)進(jìn)行粗略遍歷匹配，縮減了大量運(yùn)算時(shí)間，避免了精確遍歷匹配整個(gè)圖像庫(kù)，提高了算法的運(yùn)行效率，有利于機(jī)器人實(shí)時(shí)性導(dǎo)航。

圖像粗匹配實(shí)驗(yàn)采用由Pioneer3TM視覺(jué)系統(tǒng)的單目攝像頭在筆者實(shí)驗(yàn)室拍攝的大量環(huán)境圖像中的9幅作為圖像庫(kù)，分別標(biāo)記為A、B、C、D、E、F、G、H、I，如圖6所示。

圖6　實(shí)驗(yàn)圖像庫(kù)

假設(shè)A為待匹配圖像，表1為僅使用本文所提出的改進(jìn)SIFT算法將待匹配圖像與圖像庫(kù)遍歷匹配得到的實(shí)驗(yàn)數(shù)據(jù)；表2為使用改進(jìn)的形狀上下文算法將待匹配圖像與圖像庫(kù)進(jìn)行遍歷粗匹配得到的實(shí)驗(yàn)數(shù)據(jù)，圖7為粗匹配返回的圖像構(gòu)建的臨時(shí)圖像庫(kù)。根據(jù)表1和表2可知：僅使用改進(jìn)的SIFT算法進(jìn)行圖像匹配所需時(shí)間為11.914s；若使用本文提出的圖像分級(jí)匹配算法，所需時(shí)間為改進(jìn)的形狀上下文算法匹配的時(shí)間與待匹配圖像A應(yīng)用改進(jìn)的SIFT算法遍歷匹配臨時(shí)圖像庫(kù)時(shí)間之和，即0.707s+1.892s+1.576s+1.389s=5.564s。

表1　改進(jìn)SIFT算法圖像匹配實(shí)驗(yàn)數(shù)據(jù)

表2　改進(jìn)的形狀上下文算法圖像匹配實(shí)驗(yàn)數(shù)據(jù)

圖7　粗匹配返回結(jié)果

(a)SIFT算法　　　　　　(b)I-SIFT算法圖8　尺度和視角變換

(a)SIFT算法　　　　　　(b)I-SIFT算法圖9　光照變換

(a)SIFT算法　　　　　　(b)I-SIFT算法圖10　加入混合噪聲

本文提出的基于全局特征和局部特征的圖像分級(jí)匹配算法在精確匹配階段采用改進(jìn)的SIFT算法(I-SIFT算法)。為了驗(yàn)證I-SIFT算法的性能，隨機(jī)挑選機(jī)器人真實(shí)運(yùn)行環(huán)境里的三組圖像，在尺度與視角變換、光照變換、加入混合噪聲三種情況下進(jìn)行對(duì)比試驗(yàn)。圖8兩分圖中的圖像是前后移動(dòng)0.5m，同時(shí)左右旋轉(zhuǎn)20°拍攝的；圖9兩分圖中的圖像是機(jī)器人在不同光照環(huán)境下拍攝的；圖10兩分圖中左側(cè)為移動(dòng)機(jī)器人視覺(jué)攝像頭正常拍攝的圖像，右側(cè)為加入混合噪聲的圖像，混合噪聲由均值為0、方差為0.01的高斯噪聲和噪聲密度為0.5椒鹽噪聲組成。圖8～圖10是I-SIFT算法與原始的SIFT算法進(jìn)行對(duì)比實(shí)驗(yàn)的匹配結(jié)果，表3為實(shí)驗(yàn)所得數(shù)據(jù)。

表3　改進(jìn) SIFT與原始SIFT算法圖像匹配性能比較

表3中SIFT代表原始的SIFT算法。特征點(diǎn)數(shù)量代表樣本圖像和待匹配圖像的特征點(diǎn)數(shù)量，匹配對(duì)數(shù)即兩幅圖像成功匹配的對(duì)數(shù)，匹配率為正確匹配對(duì)數(shù)與匹配對(duì)數(shù)的比值，總時(shí)間即整個(gè)匹配過(guò)程的總時(shí)間。根據(jù)表中數(shù)據(jù)，與SIFT相比，I-SIFT中各組圖像特征點(diǎn)數(shù)量減少30%～40%；匹配對(duì)數(shù)基本維持不變；匹配率增長(zhǎng)6%～12%；匹配時(shí)間降低60%～70%。原因在于本文在提取完特征點(diǎn)之后采用減法聚類(lèi)算法，將存在于大量特征點(diǎn)中的冗余點(diǎn)進(jìn)行了剔除。同時(shí)二值化后的特征描述符依據(jù)hash函數(shù)生成索引值，采用漢明距離進(jìn)行相似性度量，由于計(jì)算機(jī)本身以二進(jìn)制作為內(nèi)部運(yùn)算邏輯，在運(yùn)算過(guò)程中有很大的優(yōu)勢(shì)，且避免了度量階段計(jì)算歐氏距離所需的開(kāi)平方運(yùn)算，從而提高了算法的運(yùn)行速度，降低了誤匹配率。

2.3圖像分級(jí)匹配算法性能分析

基于局部特征的改進(jìn)SIFT算法魯棒性較好、精度高，對(duì)旋轉(zhuǎn)、光照、尺度等環(huán)境改變不變性較好，但是描述子維度高，匹配耗時(shí)大，不適合對(duì)圖像庫(kù)進(jìn)行遍歷匹配。基于全局特征的改進(jìn)形狀上下文算法描述的信息層次更高、范圍更大，融入了輪廓的順序關(guān)系，簡(jiǎn)化了描述子的定義和計(jì)算過(guò)程，匹配效率非常高。但是對(duì)形狀的輪廓比較敏感、易受噪聲影響，且輪廓點(diǎn)是均勻提取，對(duì)形狀的描述還有局限。本文提出的圖像分級(jí)匹配算法將基于局部特征的改進(jìn)SIFT算法和基于全局特征的改進(jìn)形狀上下文算法相結(jié)合，從而達(dá)到優(yōu)勢(shì)互補(bǔ)的目的。

為了驗(yàn)證本文所提出的基于全局特征和局部特征的圖像分級(jí)匹配算法的優(yōu)勢(shì)，構(gòu)建5個(gè)分別由4幅、8幅、12幅、16幅、20幅環(huán)境圖像組成的圖像庫(kù)，依次利用原始SIFT算法、基于顏色矩的改進(jìn)SIFT圖像匹配算法(該算法首先根據(jù)顏色矩將圖像庫(kù)進(jìn)行排序，再由基于Sobel算子和迭代搜索的改進(jìn)SIFT算法對(duì)排序后的圖像序列進(jìn)行精確匹配)、本文算法進(jìn)行圖像匹配。每組實(shí)驗(yàn)均進(jìn)行10次，然后取平均值作為實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)結(jié)果如圖11所示。其中，SIFT代表原始的SIFT算法，C-SIFT代表基于顏色矩的改進(jìn)SIFT圖像匹配算法，S-SIFT即本文提出的基于全局特征和局部特征的圖像分級(jí)匹配算法。

(a)匹配總時(shí)間

(b)平均匹配正確率圖11　SIFT、C-SIFT和S-SIFT在不同圖像庫(kù)的性能對(duì)比

移動(dòng)機(jī)器人在基于拓?fù)涞貓D導(dǎo)航過(guò)程中，應(yīng)用本文所提出的圖像匹配算法，在時(shí)間和匹配正確率方面均優(yōu)于上述兩種算法。隨著圖像庫(kù)中圖像數(shù)量增加，三種算法的運(yùn)行總時(shí)間均增加，平均匹配正確率均下降。但本文所提出算法運(yùn)行總時(shí)間上升趨勢(shì)緩慢且運(yùn)行速度較快，平均匹配正確率保持在90%以上。

3　結(jié)語(yǔ)

針對(duì)移動(dòng)機(jī)器人基于拓?fù)涞貓D導(dǎo)航時(shí)對(duì)圖像特征提取與匹配算法的要求，提出了圖像分級(jí)匹配算法，將基于全局特征的改進(jìn)形狀上下文算法和基于局部特征的改進(jìn)SIFT算法相結(jié)合，實(shí)現(xiàn)了拓?fù)涞貓D節(jié)點(diǎn)的識(shí)別，最終實(shí)現(xiàn)機(jī)器人基于拓?fù)涞貓D的導(dǎo)航。實(shí)驗(yàn)結(jié)果表明該算法在基于圖像匹配的移動(dòng)機(jī)器人導(dǎo)航研究中是有效的。

[1]王殿軍.雙目視覺(jué)在移動(dòng)機(jī)器人定位中的應(yīng)用[J].中國(guó)機(jī)械工程，2013，24(9)：1155-1158.

Wang Dianjun. Application on Binocular Vision System of a Mobile Robot[J]. China Mechanical Engineering，2013，24(9)：1155-1158.

[2]陳衛(wèi)東，張興家，朱奇光，等. 基于混合特征的移動(dòng)機(jī)器人圖像匹配算法[J]. 中國(guó)機(jī)械工程, 2015,26(9): 1137-1141.

Chen Weidong， Zhang Xingjia， Zhu Qiguang， et al. An Image Matching Algorithm for Mobile Robot Localization Based on Hybrid Features[J]. China Mechanical Engineering, 2015, 26(9): 1137-1141.

[3]劉佳, 傅衛(wèi)平, 王雯,等. 基于改進(jìn)SIFT算法的圖像匹配[J]. 儀器儀表學(xué)報(bào), 2013, 34(5):1107-1112.

Liu Jia，F(xiàn)u Weiping, Wang Wen, et al. Image Matching Based on Improved SIFT Algorithm[J]. Chinese Journal of Scientific Instrument, 2013, 34(5):1107-1112.

[4]Lowe D G. Distinctive Image Features from Scale- Invariant Keypoints[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[5]Lu B, Whangbo T K. A SIFT-Color Moments Descriptor for Object Recognition[C]// 2014 International Conference on IT Convergence and Security (ICITCS). Beijing, 2014:1-3.

[6]陳抒瑢, 李勃, 董蓉,等. Contourlet-SIFT特征匹配算法[J].電子與信息學(xué)報(bào), 2013,35(5): 1215-1221.

Chen Shurong, Li Bo, Dong Rong, et al. Contourlet-SIFT Feature Matching Algorithm[J]. Journal of Electronics & Information Technology, 2013,35(5): 1215-1221.

[7]Zhong Jinqin， Tan Jieqing， Gu Lichuan. SIFT Feature Matching Algorithm with Local Shape Context [J]. International Journal of Applied Mathematics & StatisticsTM, 2013, 46(16):93-101.

[8]高晶, 吳育峰, 吳昆,等. 基于角點(diǎn)檢測(cè)的圖像匹配算法[J]. 儀器儀表學(xué)報(bào), 2013, 34(8): 1717-1725.

Gao Jing, Wu Yufeng, Wu Kun, et al. Image Matching Method Based on Corner Detection[J]. Chinese Journal of Scientific Instrument, 2013, 34(8):1717-1725.

[9]周瑜, 劉俊濤, 白翔. 形狀匹配方法研究與展望[J]. 自動(dòng)化學(xué)報(bào), 2012, 38(6):889-910.

Zhou Yu, Liu Juntao, Bai Xiang. Research and Perspective on Shape Matching[J]. Acta Automatica Sinica, 2012, 38(6):889-910.

[10]鮑文霞, 梁棟, 程志友,等. 一種基于圖理論的非剛體形狀匹配算法[J]. 儀器儀表學(xué)報(bào), 2009, 30(10):2027-2032.

Bao Wenxia, Liang Dong, Cheng Zhiyou,et al. Graph Theory Based Non-rigid Shape Matching Algorithm[J]. Chinese Journal of Scientific Instrument, 2009, 30(10):2027-2032.

[11]史思琦. 基于輪廓特征的目標(biāo)識(shí)別研究[D].西安：西安電子科技大學(xué), 2012.

[12]李洪波. 基于減法聚類(lèi)和快速緊密性函數(shù)的 SF-FCM[J]. 控制與決策, 2011, 26(7): 1074-1078.

Li Hongbo. SF-FCM Based on Fast Close Function and Subtractive Clustering[J].Control and Decision, 2011, 26(7): 1074-1078.

[13]Alitappeh R J, Saravi K J, Mahmoudi F. Key Point Reduction in SIFT Descriptor Used by Subtractive Clustering[C]// Information Science, Signal Processing and their Applications (ISSPA), 11th International Conference on IEEE. Montreal, 2012:906 - 911.

[14]毋立芳, 侯亞希, 周鵬,等. 基于最大位平均熵的SIFT描述子二值化及相似度匹配方法[P]. 中國(guó)專(zhuān)利: 103617431A, 2014-03-05.

[15]Belongie S J, Malik J, Puzicha J. Shape Matching and Object Recognition Using Shape Contexts[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2002, 24(4):509-522.

[16]Haibin L, Jacobs D W. Shape Classification Using the Inner-distance[J]. IEEE Transactions on Pattern Analysis & Machine Intelligence, 2007, 29(2):286-299.

(編輯盧湘帆)

InvestigationandApplicationonImageHierarchicalMatchingAlgorithmBasedonGlobalFeatureandLocalFeature

ZhuQiguang1,2WangZiwei1ChenYing3

1.YanshanUniversity，Qinhuangdao，Hebei,066004 2.TheKeyLaboratoryforSpecialFiberandFiberSensorofHebeiProvince,Qinhuangdao，Hebei,066004

Aimingattheproblemsthattheimagefeatureextractionandmatchalgorithmshouldhavehighaccuracy,goodperformanceinreal-timeandrobustnesswhenthemobilerobotnavigatedbasedontopologicalmap,thepaperproposedanewimagehierarchicalmatchingalgorithmbasedontheglobalfeatureandlocalfusion.First,theimprovedshapecontextalgorithmwasappliedtotheinputimagestobematchedtoextracttheglobalfeatureswhichwerematchedroughlywiththeimagesinthedatabase,obtaining3imagesthathadthehighestsimilaritytothecurrentimagewhichconstitutedatemporaryimagedatabase.Then,theimprovedSIFTalgorithmwereusedtoextractlocalfeatureoftheinputimageswhichwerematchedaccuratelywiththelocalfeatureofthe3imagesinthetemporaryimagedatabase,finallyobtainingtheimagewithhighestsimilarityasthematchresults.TheimagehierarchicalmatchingalgorithmbasedontheglobalfeatureandlocalfeaturecombinedtheimprovedshapecontextalgorithmbasedonglobalfeaturesandtheimprovedSIFTalgorithmbasedonlocalfeatures,soastoachievethepurposeofcomplementaryadvantages.Theexperimentalresultsshowthatthisalgorithmcaneffectivelyimprovethematchingefficiencyandreducetherunningtimewhenthemobilerobotsnavigatebasedontopologicalmap.

mobilerobot;imagematching;improvedshapecontext;improvedSIFT

2016-04-22

國(guó)家自然科學(xué)基金資助項(xiàng)目(61201112)；河北省自然科學(xué)基金資助項(xiàng)目(F2016203245)；河北省普通高等學(xué)校青年拔尖人才計(jì)劃資助項(xiàng)目(BJ2014056)

TP391

10.3969/j.issn.1004-132X.2016.16.015

朱奇光，男，1978年生。燕山大學(xué)信息科學(xué)與工程學(xué)院副教授。主要研究方向?yàn)闄C(jī)器人智能控制及應(yīng)用。發(fā)表論文30余篇。王梓巍，男，1992年生。燕山大學(xué)信息科學(xué)與工程學(xué)院碩士研究生。陳穎，女，1980年生。燕山大學(xué)電氣工程學(xué)院教授。