一種基于Shi-Tomasi和改進(jìn)LBP的特征匹配及目標(biāo)定位快速算法

張 震, 張照崎, 朱留存, 劉濟(jì)塵, 魏金占, 蔡旭航, 趙成龍

(1. 北部灣大學(xué) 先端科學(xué)技術(shù)研究院, 廣西 欽州 535001；2. 大連理工大學(xué)-立命館大學(xué)國際信息與軟件學(xué)院, 遼寧 大連 116085；3. 吉林大學(xué) 軟件學(xué)院, 長春 130012)

0 引 言

圖像局部特征點(diǎn)在不同的拍攝場(chǎng)景下具有不變性, 廣泛應(yīng)用于目標(biāo)定位與識(shí)別[1-3]、 同時(shí)定位及導(dǎo)航(simultaneous localization and mapping, SLAM)[4-5]、 圖像配準(zhǔn)與圖像拼接[6-8]等領(lǐng)域. 這類方法首先利用灰度圖像的一階或二階導(dǎo)數(shù)檢測(cè)特征點(diǎn)； 然后根據(jù)特征點(diǎn)描述子之間的相似度尋找匹配點(diǎn)對(duì)； 最后通過特征匹配關(guān)系估計(jì)圖像間的變換矩陣[8-9]. Harris等[10]提出了經(jīng)典的Harris特征點(diǎn)檢測(cè)算法; Shi等[11]對(duì)Harris算法進(jìn)行了優(yōu)化改進(jìn), 取得了更好的檢測(cè)效果, 對(duì)圖像旋轉(zhuǎn)、 光線變化、 噪聲和視點(diǎn)變換不敏感. 上述算法主要研究特征點(diǎn)檢測(cè), 并未關(guān)注描述子的定義和匹配問題. 之后, 能適應(yīng)尺度變化的特征檢測(cè)算法被相繼提出, 較經(jīng)典的是尺度不變特征變換(SIFT)算法[12]和SURF算法[13], SURF是SIFT的改進(jìn)算法. 這類算法需要用Gauss差分算子或Laplace 算子構(gòu)建尺度空間, 適應(yīng)性更好, 但增加了計(jì)算復(fù)雜度, 實(shí)時(shí)性較差. SIFT算法[12]先將以特征點(diǎn)為中心的16×16鄰域劃分為4×4個(gè)子區(qū)域, 再針對(duì)每個(gè)子區(qū)域計(jì)算8個(gè)方向梯度, 最終得到的128維向量定義為描述子. SURF[13]則以特征點(diǎn)為中心取一個(gè)具方向的正方形鄰域, 先將其劃分為16個(gè)子區(qū)域, 再針對(duì)每個(gè)子區(qū)域計(jì)算4個(gè)Haar小波特征, 最終得到64維向量作為描述子. 上述兩個(gè)描述子信息豐富, 但運(yùn)算代價(jià)高、 占用內(nèi)存大. Calonder等[14]提出了BRIEF描述子, 其占用內(nèi)存少, 得到廣泛認(rèn)可. Rublee等[15]對(duì)BRIEF描述子進(jìn)行了改進(jìn), 提出了ORB算法[15], 該算法根據(jù)角度參數(shù)提取BRIEF描述子, 實(shí)時(shí)性好且具有更好的旋轉(zhuǎn)不變性.

本文源于解決機(jī)器人視覺伺服抓取問題, 對(duì)定位精度和實(shí)時(shí)性均要求較高. 經(jīng)典的SIFT,SURF算法定位精度高, 但實(shí)時(shí)性較差. ORB算法速度快, 但定位精度不滿足要求. 因此, 本文算法在保證算法穩(wěn)定性的前提下, 期望在實(shí)時(shí)性和定位精度間尋找平衡點(diǎn). 首先, 選擇Shi-Tomasi算法[11]提取特征點(diǎn); 其次, 以特征點(diǎn)為中心截取局部子圖像, 利用Gauss函數(shù)的兩個(gè)偏導(dǎo)數(shù)計(jì)算特征方向, 再根據(jù)特征方向旋轉(zhuǎn)局部圖像, 提取旋轉(zhuǎn)后標(biāo)準(zhǔn)局部圖像的局部二值模式(local binary pattern, LBP)特征[16]作為描述子; 再次, 通過計(jì)算特征點(diǎn)描述子之間的Hamming距離確定相似度, 實(shí)現(xiàn)特征匹配; 最后, 根據(jù)匹配結(jié)果定位目標(biāo)在場(chǎng)景中的位置. 算法流程如圖1所示.

圖1 本文算法流程Fig.1 Flow chart of proposed algorithm

1 Shi-Tomasi特征檢測(cè)算法

Shi-Tomasi算法[11]思想： 以待檢測(cè)點(diǎn)為中心加窗, 通過移動(dòng)窗口, 計(jì)算移動(dòng)前后窗口內(nèi)像素強(qiáng)度差. 如果沿任意方向移動(dòng)窗口, 強(qiáng)度差值都較大, 則待檢測(cè)點(diǎn)為特征點(diǎn).

根據(jù)上述算法思想, 強(qiáng)度差可抽象為

(1)

其中W(x,y)為采樣窗口,I(x,y)為像素值,u,v為以待測(cè)點(diǎn)為中心的偏移量.

由Taylor公式, 有

I(x+u,y+v)=I(x,y)+Ixu+Iyv+O(u2,v2),

其中Ix,Iy為偏導(dǎo)數(shù).于是

(2)

從而式(1)可近似為

(3)

1) 當(dāng)λ1,λ2值都很小時(shí), 待檢測(cè)點(diǎn)落入圖像平坦區(qū)域, 非特征點(diǎn)；

2) 當(dāng)λ1?λ2或λ1?λ2時(shí), 待檢測(cè)點(diǎn)落在圖像邊緣上, 非特征點(diǎn)；

3) 當(dāng)λ1,λ2值都很大時(shí)(較小值大于某閾值), 待檢測(cè)點(diǎn)為特征點(diǎn).

Shi-Tomasi算法特征檢測(cè)結(jié)果如圖2所示, 其中: (A)為標(biāo)準(zhǔn)圖像； (B)為標(biāo)準(zhǔn)圖像檢出的特征點(diǎn)； (C)和(D)分別為(A)旋轉(zhuǎn)10°,-10°后檢出的特征. 實(shí)驗(yàn)中, 閾值選取為最大特征響應(yīng)強(qiáng)度的0.1倍. 由圖2可見, Shi-Tomasi特征檢測(cè)算法具有良好的旋轉(zhuǎn)不變性.

圖2 Shi-Tomasi算法特征檢測(cè)結(jié)果Fig.2 Feature detection results of Shi-Tomasi algorithm

2 基于LBP的特征描述子

特征描述子應(yīng)具有較好的區(qū)分度, 且當(dāng)圖像發(fā)生平移、 旋轉(zhuǎn)變化時(shí), 具有不變性. 本文描述子定義方法充分利用了圖像像素間位置、 大小關(guān)系以及數(shù)字圖像的離散性特點(diǎn), 盡可能簡化描述子, 減小匹配代價(jià), 并滿足伺服定位抓取中的定位精度和實(shí)時(shí)性要求, 算法步驟如下.

1) 以特征點(diǎn)為中心截取局部圖像I21×21. 取樣窗口如圖3(A)所示, 窗口尺寸為21×21, 局部圖像如圖3(B)和(C)中小圖所示(為便于觀察, 做了放大處理).

2) 獲取7×7大尺度局部圖像I7×7.將I21×21劃分為7×7個(gè)區(qū)域, 區(qū)域尺寸為3×3, 如圖3(A)中粗線所示, 對(duì)每個(gè)區(qū)域像素值求和, 作為大尺度圖像的像素值, 得到大尺度局部圖像I7×7, 本文采用積分圖像法, 以提高運(yùn)行速度.

3) 由大尺度局部圖像I7×7, 利用Gauss函數(shù)的兩個(gè)偏導(dǎo)數(shù)

(4)

設(shè)計(jì)方向?yàn)V波器, 確定特征點(diǎn)方向角θ.取σ=1, 得到兩個(gè)方向?yàn)V波器fx,fy為

方向?yàn)V波器fx,fy邊角位置取0, 目的是確定方向時(shí)削弱旋轉(zhuǎn)產(chǎn)生的影響.將大尺度局部圖像I7×7分別與fx,fy做卷積(濾波), 得到Gx,Gy, 則特征點(diǎn)方向角θ=arctan(Gy/Gx).特征方向確定結(jié)果如圖3(B)和(C)中由各特征點(diǎn)引出的白線所示.

4) 由大尺度局部圖像I7×7和方向角θ, 獲取5×5標(biāo)準(zhǔn)化局部圖像I5×5.將原坐標(biāo)系xoy旋轉(zhuǎn)θ角, 構(gòu)建新坐標(biāo)系x′oy′, 如圖3(D)所示.在x′oy′坐標(biāo)系下取5×5個(gè)整數(shù)位置點(diǎn)得到標(biāo)準(zhǔn)化局部圖像I5×5, 則各點(diǎn)(x′,y′)在xoy坐標(biāo)系下的位置(x,y)由

(5)

確定.顯然, 點(diǎn)(x,y)通常落在xoy坐標(biāo)系下的非整數(shù)點(diǎn)位置, 例如x′oy′坐標(biāo)系下點(diǎn)(2,2)落在xoy坐標(biāo)系下A,B,C,D四個(gè)整數(shù)位置點(diǎn)之間, 如圖3(D)所示.本文采用雙線性插值法, 確定I5×5中各點(diǎn)像素值.例如, 可根據(jù)xoy坐標(biāo)系下A,B,C,D四點(diǎn)像素值求x′oy′坐標(biāo)系下點(diǎn)(2,2)的像素值.

圖3 描述子生成過程Fig.3 Generation process of descriptors

圖4 LBP原理Fig.4 LBP principle

5) 提取標(biāo)準(zhǔn)化局部圖像I5×5的LBP特征作為特征描述子. LBP特征以3×3圖像塊的中心像素灰度值作為閾值, 與8個(gè)相鄰像素灰度值進(jìn)行對(duì)比, 大于該閾值取1, 否則取0, 得到的8位二進(jìn)制串作為LBP特征, 其原理[16]如圖4所示. LBP特征較好地刻畫了數(shù)字圖像像素間位置及像素值大小的關(guān)系, 具有速度快、 不受光照變化影響的優(yōu)點(diǎn). 標(biāo)準(zhǔn)化局部圖像I5×5可提取到3×3個(gè)8位二進(jìn)制串作為特征點(diǎn)的描述子, 描述子提取結(jié)果如圖3(B)和(C)中矩陣所示.

3 特征匹配及目標(biāo)定位算法

特征匹配的依據(jù)是特征點(diǎn)描述子間的距離, 本文采用Hamming距離作為度量標(biāo)準(zhǔn), 即待匹配的兩個(gè)描述子間9個(gè)8位二進(jìn)制串中(共72個(gè)二進(jìn)制位)不相同位的個(gè)數(shù). 特征匹配步驟如下：

1) 選定標(biāo)準(zhǔn)圖像中任意一個(gè)描述子G[m];

2) 在場(chǎng)景圖中尋找與其匹配的描述子G′[n], 使得d(G[m],G′[n])最??；

3) 若d(G[m],G′[n])<τ(τ為設(shè)定的閾值), 則判定標(biāo)準(zhǔn)圖像特征點(diǎn)m與場(chǎng)景圖像特征點(diǎn)n匹配.

特征匹配結(jié)果如圖5所示, 其中各連線對(duì)應(yīng)的兩點(diǎn)表示匹配的特征點(diǎn).目標(biāo)定位過程如下：

1) 尋找兩組匹配特征點(diǎn)對(duì)之間的變換矩陣, 即估計(jì)歸一化單應(yīng)性矩陣：

(6)

滿足

(7)

2) 輸入標(biāo)準(zhǔn)圖像的4個(gè)頂點(diǎn)坐標(biāo), 利用式(7)計(jì)算出與之對(duì)應(yīng)場(chǎng)景圖像4個(gè)頂點(diǎn)的坐標(biāo), 定位目標(biāo)位置.

目標(biāo)定位效果如圖5所示, 其中紅色框圈定了標(biāo)準(zhǔn)圖像在場(chǎng)景圖像中的位置. 機(jī)器人伺服抓取時(shí), 根據(jù)式(7)確定旋轉(zhuǎn)量和平移量, 平移尺寸由像素距離和實(shí)際距離的比例關(guān)系確定.

圖5 旋轉(zhuǎn)10°(A)和170°(B)后特征匹配及目標(biāo)定位結(jié)果Fig.5 Results of feature matching and target location after rotating 10° (A) and 170° (B)

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

實(shí)驗(yàn)環(huán)境： 操作系統(tǒng)Win10 64位, 開發(fā)平臺(tái)VSC++, 計(jì)算機(jī)CPU為3.6 GHz, 內(nèi)存16 GB. 為驗(yàn)證本文算法的有效性, 選擇經(jīng)典算法SIFT[12],SURF[13]和ORB[15], 對(duì)算法的運(yùn)行速度、 定位精度、 穩(wěn)定性進(jìn)行對(duì)比實(shí)驗(yàn). 參與對(duì)比的SIFT,SURF和ORB算法通過調(diào)用Opencv庫函數(shù)實(shí)現(xiàn). 由于SIFT和SURF算法已申請(qǐng)專利, 不能在發(fā)布模式下運(yùn)行, 因此為使實(shí)驗(yàn)結(jié)果具有可比性, 對(duì)比實(shí)驗(yàn)均在DEBUG模式下運(yùn)行.

圖6和圖7分別為不同算法對(duì)Flower圖像和Crowd圖像的匹配及定位效果對(duì)比, 分別進(jìn)行了旋轉(zhuǎn)、 平移處理作為場(chǎng)景圖像, 通過調(diào)整算法參數(shù), 使4種算法特征匹配數(shù)量基本相當(dāng).

圖6 不同算法對(duì)Flower圖像的匹配及定位效果對(duì)比Fig.6 Comparison of Flower image matching and location effect by different algorithms

圖7 不同算法對(duì)Crowd圖像的匹配及定位效果對(duì)比Fig.7 Comparison of Crowd image matching and location effect by different algorithms

由圖6和圖7可見, 只有圖7(C)定位偏差較大, 其他圖片定位效果均較好, 差異不明顯. 以圖7中Crowd圖像為例, 做實(shí)驗(yàn)數(shù)據(jù)量化對(duì)比. 在定位精度對(duì)比中, 由于機(jī)器人視覺伺服抓取過程中相機(jī)位置是固定的, 工件只會(huì)發(fā)生位置偏移和角度旋轉(zhuǎn), 不存在尺度和仿射變換, 因此本文重點(diǎn)對(duì)平移及旋轉(zhuǎn)誤差進(jìn)行對(duì)比.

表1列出了圖7中Crowd圖像各角度下定位過程運(yùn)行時(shí)間的對(duì)比結(jié)果. 由表1可見, 平均耗時(shí)分別為ORB算法37 ms, 本文算法144 ms, SURF算法380 ms, SIFT算法950 ms.

表1 不同算法的運(yùn)行時(shí)間(ms)對(duì)比

平移誤差定義為： 定位中估計(jì)的4個(gè)頂點(diǎn)坐標(biāo)與場(chǎng)景中實(shí)際頂點(diǎn)坐標(biāo)之間距離的最大值. 表2列出了Crowd圖像定位過程在各旋轉(zhuǎn)角度下平移誤差的對(duì)比結(jié)果. 由表2可見： SIFT算法定位精度最高, 平移誤差均值為0.52, 平移誤差最大值為0.76； 本文算法平移誤差均值為0.67, 平移誤差最大值為1.51； SURF算法平移誤差均值為0.68, 平移誤差最大值為1.64； ORB算法定位精度最差, 平移誤差的均值為3.93, 平移誤差的最大值為12.73, 穩(wěn)定性較差.

表2 不同算法的定位精度(像素)對(duì)比

旋轉(zhuǎn)誤差定義為： 定位中估計(jì)的4條邊界線與場(chǎng)景實(shí)際邊界線角度偏差絕對(duì)值的最大值. 表3列出了Crowd圖像定位過程在各角度下旋轉(zhuǎn)誤差的對(duì)比結(jié)果. 由表3可見: SIFT算法定位精度最高, 旋轉(zhuǎn)誤差均值為0.01, 旋轉(zhuǎn)誤差最大值為0.02； 本文算法定位精度略差于SIFT算法, 旋轉(zhuǎn)誤差均值為0.06, 旋轉(zhuǎn)誤差最大值為0.11； SURF算法旋轉(zhuǎn)誤差均值為0.07, 旋轉(zhuǎn)誤差最大值為0.15； ORB算法旋轉(zhuǎn)誤差均值為0.31, 旋轉(zhuǎn)誤差最大值為0.86, 旋轉(zhuǎn)定位精度最差.

表3 不同算法的定位精度(°)對(duì)比

綜上所述, 本文在獲取描述子過程中, 由21×21子圖像獲取7×7大尺度子圖像, 并由7×7大尺度子圖像確定特征方向, 提取標(biāo)準(zhǔn)子圖像及描述子, 主要因?yàn)椋?1) 由于提取的特征點(diǎn)坐標(biāo)有偏差, 且該坐標(biāo)由浮點(diǎn)數(shù)取整過程中還會(huì)累計(jì)誤差, 將影響后期的特征匹配, 而采用大尺度方式, 會(huì)極大削弱這種影響, 使算法更穩(wěn)定； 2) 大尺度方式下確定特征方向、 提取標(biāo)準(zhǔn)子圖像及描述子時(shí), 極大減少了參與運(yùn)算點(diǎn), 從而縮短了運(yùn)算時(shí)間. 在確定特征方向時(shí)采用的兩個(gè)方向?yàn)V波器中, 各點(diǎn)對(duì)方向貢獻(xiàn)大小由其到中心點(diǎn)的距離決定更合理, 確定的方向也更準(zhǔn)確. 在定義描述子階段采用的LBP特征, 簡單易行, 且Hamming距離計(jì)算速度快. 實(shí)驗(yàn)結(jié)果表明, 本文算法在定位精度上略差于SIFT算法, 與SRUF算法基本相當(dāng), 明顯優(yōu)于ORB算法； 在定位速度上, 本文算法明顯慢于ORB算法, 但遠(yuǎn)好于SIFT和SURF算法, 能滿足實(shí)時(shí)性要求； 本文算法的穩(wěn)定性較好, 最大平移誤差小于2個(gè)像素, 最大旋轉(zhuǎn)誤差小于0.2°. 因此, 本文算法綜合性能更好.