一種基于Shi-Tomasi和改進LBP的特征匹配及目標定位快速算法

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

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

0 引 言

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

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

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

1 Shi-Tomasi特征檢測算法

Shi-Tomasi算法[11]思想： 以待檢測點為中心加窗, 通過移動窗口, 計算移動前后窗口內像素強度差. 如果沿任意方向移動窗口, 強度差值都較大, 則待檢測點為特征點.

根據上述算法思想, 強度差可抽象為

(1)

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

由Taylor公式, 有

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

其中Ix,Iy為偏導數.于是

(2)

從而式(1)可近似為

(3)

1) 當λ1,λ2值都很小時, 待檢測點落入圖像平坦區域, 非特征點；

2) 當λ1?λ2或λ1?λ2時, 待檢測點落在圖像邊緣上, 非特征點；

3) 當λ1,λ2值都很大時(較小值大于某閾值), 待檢測點為特征點.

Shi-Tomasi算法特征檢測結果如圖2所示, 其中: (A)為標準圖像； (B)為標準圖像檢出的特征點； (C)和(D)分別為(A)旋轉10°,-10°后檢出的特征. 實驗中, 閾值選取為最大特征響應強度的0.1倍. 由圖2可見, Shi-Tomasi特征檢測算法具有良好的旋轉不變性.

圖2 Shi-Tomasi算法特征檢測結果Fig.2 Feature detection results of Shi-Tomasi algorithm

2 基于LBP的特征描述子

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

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

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

3) 由大尺度局部圖像I7×7, 利用Gauss函數的兩個偏導數

(4)

設計方向濾波器, 確定特征點方向角θ.取σ=1, 得到兩個方向濾波器fx,fy為

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

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

(5)

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

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

圖4 LBP原理Fig.4 LBP principle

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

3 特征匹配及目標定位算法

特征匹配的依據是特征點描述子間的距離, 本文采用Hamming距離作為度量標準, 即待匹配的兩個描述子間9個8位二進制串中(共72個二進制位)不相同位的個數. 特征匹配步驟如下：

1) 選定標準圖像中任意一個描述子G[m];

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

3) 若d(G[m],G′[n])<τ(τ為設定的閾值), 則判定標準圖像特征點m與場景圖像特征點n匹配.

特征匹配結果如圖5所示, 其中各連線對應的兩點表示匹配的特征點.目標定位過程如下：

1) 尋找兩組匹配特征點對之間的變換矩陣, 即估計歸一化單應性矩陣：

(6)

滿足

(7)

2) 輸入標準圖像的4個頂點坐標, 利用式(7)計算出與之對應場景圖像4個頂點的坐標, 定位目標位置.

目標定位效果如圖5所示, 其中紅色框圈定了標準圖像在場景圖像中的位置. 機器人伺服抓取時, 根據式(7)確定旋轉量和平移量, 平移尺寸由像素距離和實際距離的比例關系確定.

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

4 實驗結果分析

實驗環境： 操作系統Win10 64位, 開發平臺VSC++, 計算機CPU為3.6 GHz, 內存16 GB. 為驗證本文算法的有效性, 選擇經典算法SIFT[12],SURF[13]和ORB[15], 對算法的運行速度、 定位精度、 穩定性進行對比實驗. 參與對比的SIFT,SURF和ORB算法通過調用Opencv庫函數實現. 由于SIFT和SURF算法已申請專利, 不能在發布模式下運行, 因此為使實驗結果具有可比性, 對比實驗均在DEBUG模式下運行.

圖6和圖7分別為不同算法對Flower圖像和Crowd圖像的匹配及定位效果對比, 分別進行了旋轉、 平移處理作為場景圖像, 通過調整算法參數, 使4種算法特征匹配數量基本相當.

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

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

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

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

表1 不同算法的運行時間(ms)對比

平移誤差定義為： 定位中估計的4個頂點坐標與場景中實際頂點坐標之間距離的最大值. 表2列出了Crowd圖像定位過程在各旋轉角度下平移誤差的對比結果. 由表2可見： SIFT算法定位精度最高, 平移誤差均值為0.52, 平移誤差最大值為0.76； 本文算法平移誤差均值為0.67, 平移誤差最大值為1.51； SURF算法平移誤差均值為0.68, 平移誤差最大值為1.64； ORB算法定位精度最差, 平移誤差的均值為3.93, 平移誤差的最大值為12.73, 穩定性較差.

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

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

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

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