基于優(yōu)化ORB算法的圖像角點特征匹配方法*

朱 標

(1.中航華東光電有限公司，安徽 蕪湖 241002； 2.安徽省現(xiàn)代顯示技術重點實驗室，安徽 蕪湖 241002；3.國家特種顯示工程技術研究中心，安徽 蕪湖 241002； 4.特種顯示國家工程實驗室，安徽 蕪湖 241002)

0 引 言

圖像角點特征匹配作為計算機視覺領域的重點研究方向之一，其普遍應用于機器人[1]、無人機[2]與SLAM(Simultaneous Localization and Mapping)[3]等領域。首先，調(diào)研了國外科研者提出的圖像角點特征匹配算法，例如， SUSAN(Smallest Univalue Segment Assimilating Nucleus)算法[4]、Trajkovic算法[5]和FAST (Features from Accelerated Segment Test)算法[6-7]， SIFT(Scale Invariant Feature Transform)算法[8-9]、SURF(Speeded up Robust Feature)算法[10]、ORB(Oriented FAST and Rotated BRIEF)算法[11]等，其中，SUSAN算法、Trajkovic算法與FAST算法作為依次優(yōu)化的經(jīng)典圖像角點特征檢測算法，其具備檢測位置準確、抗噪聲能力強的特性，但不具備對光照、尺度和旋轉(zhuǎn)不變性，SIFT算法與SURF算法具備光照、尺度和旋轉(zhuǎn)不變性，但執(zhí)行速度不高，ORB算法具備執(zhí)行速度快的特性，但存在配準精度不高的問題。重點針對Ethan Rublee等于2011年提出的ORB算法進行研究，發(fā)現(xiàn)該算法對目標平移、旋轉(zhuǎn)與一定視角和光照等變化保持一定的不變性，但存在對尺度變換敏感和圖像角點特征匹配精度不高的問題，國內(nèi)科研者為了解決ORB算法存在的問題提出了許多優(yōu)化算法，例如，白雪冰等[12]利用Hessian矩陣檢測角點特征，使得檢測出的角點特征具有尺度不變性，然后使用ORB算法生成角點特征描述子向量，解決了ORB算法對尺度變換敏感問題；曾慶化等[13]將ORB算法融入ASIFT(Affine-SIFT)算法中，加快ASIFT算法的運行速度；馬丹等[14]使用SURF算法檢測出具有尺度不變性的特征點，然后使用ORB算法對特征點進行描述，從而使改進ORB算法具備尺度不變性；江澤濤等[15]將ORB算法應用到異源圖像的匹配，為異源圖像的匹配提供了一種解決途徑；楊炳坤等[16]使用Shi-Tomasi算法剔除大部分的偽角點特征，將Shi-Tomasi算法和ORB算法相結合提升了角點特征匹配精度[17]；通過對國內(nèi)的調(diào)研可知，傳統(tǒng)ORB算法普遍存在尺度變換敏感和圖像角點特征匹配精度不高的問題，國內(nèi)科研工作者主要利用其他圖像角點特征檢測和匹配算法的優(yōu)勢來對傳統(tǒng)ORB算法進行優(yōu)化，以解決傳統(tǒng)ORB算法的劣勢。最后，針對傳統(tǒng)ORB算法圖像角點特征匹配精度不高的問題，使用Shi-Tomasi算法、BRIEF(Binary Robust Independent Element Feature)[18]和SURF相融合算法、隨機投影原理與優(yōu)化的相似性距離算法對傳統(tǒng)ORB算法進行優(yōu)化，得到Shi-Tomasi- SURFORB算法。

1 Shi-Tomasi-SURFORB算法

Shi-Tomasi-SURFORB算法按照實現(xiàn)流程分成3個階段：檢測階段，包括待匹配圖像的采集和使用Shi-Tomasi算法檢測角點特征兩個階段；描述子階段，包括兩個階段，一是生成128維BRIEF描述子向量和64維SURF描述子向量，共192維角點特征描述子向量，二是使用隨機投影原理將64維SURF描述子向量降維到24維SURF描述子向量，最終得到共152維角點特征描述子向量；匹配階段，使用優(yōu)化的匹配算法進行角點特征的匹配。Shi-Tomasi-SURFORB算法的實現(xiàn)流程框圖如圖1所示。

圖1 Shi-Tomasi-SURFORB算法的實現(xiàn)流程框圖Fig.1 Implementation process diagram of Shi-Tomasi-SURFORB algorithm

1.1 圖像角點特征的檢測

Shi-Tomasi-SURFORB算法在檢測階段使用Shi-Tomasi算法檢測角點特征，Shi-Tomasi算法是Shi和Tomasi于1994年提出的一種圖像角點特征檢測算法，是Harris 算法的改進算法，該算法不易受圖像旋轉(zhuǎn)、光照條件、角度變化和噪聲的影響，也可避免圖像角點特征聚類。

Shi-Tomasi算法實現(xiàn)原理如下：首先，假定待檢測像素點為P，計算其在X方向和Y方向的梯度；其次，計算利用X方向和Y方向的梯度計算像素點P的自相關矩陣M；再次，計算像素點P的響應量，響應量是自相關矩陣M的兩個特征值的最小值，如果響應量高于選定的閾值，則像素點P是候選角點特征；最后，遍歷圖像并進行局部非極大值抑制，剔除局部區(qū)域內(nèi)重復的角點特征，得到最終的角點特征集。

1.2 圖像角點特征的雙描述子序列

Shi-Tomasi-SURFORB算法在描述子階段首先使用BRIEF和SURF相融合算法生成128維BRIEF描述子向量和64維SURF描述子向量，然后使用隨機投影原理將64維SURF描述子向量降維到24維SURF描述子向量。

首先，計算角點特征的S×S大小的圖像鄰域P的準則τ(P；x，y)，計算表達式如下：

(1)

其中，τ(P；x，y)表示圖像鄰域P的準則，P(x)表示平滑后的圖像鄰域P在x處的像素灰度值，P(y)表示平滑后的圖像鄰域P在y處的像素灰度值，設定S的值為8。

再計算BRIEF描述子向量，BRIEF描述子向量為n維的二進制比特串，計算表達式如下：

(2)

其中，fn(P)表示n維的二進制比特串，τ(P；x，y)表示圖像鄰域P的準則，設定n的值為128。

其次，建立以角點特征為中心、沿角點特征主方向生成一個20×20的矩形區(qū)域，將其分成4×4個子塊，對每個子塊利用Haar小波模板進行響應值計算，最終形成64維SURF描述子向量。

(3)

(4)

1.3 圖像角點特征的匹配

Shi-Tomasi-SURFORB算法在匹配階段使用Ham距離和歐式距離相融合的相似性距離算法進行匹配，整個圖像角點特征的匹配分為兩個階段，先假定圖像A與圖像B為一對待匹配圖像，圖像A中圖像角點特征集為Ubrief_i(x1，x2，x3，…，x126，x127，x128)與Usurf_i(x1，x2，x3，…，x22，x23，x24)，圖像B中圖像角點特征集為Vbrief_j(y1，y2，y3，…，y126，y127，y128)與Vsurf_j(y1，y2，y3，…，y22，y23，y24)。

首先，針對128維BRIEF描述子向量，使用Ham距離算法進行相似性度量，以角點特征集Ubrief_i中角點特征Ui為對象，使用Ham距離公式遍歷角點特征集Vbrief_j中角點特征，得到Ham的最小值與次最小值，Ham的最小值對應最近鄰特征點V1j，Ham的次最小值對應次最近鄰特征點V2j，Ham距離算法如式(5)所示：

(5)

其中，xm表示Ubrief_i中角點特征描述子向量中元素，ym表示Vbrief_j中角點特征描述子向量中元素，⊕表示異或運算，Ham()表示兩個角點特征描述子向量之間的Ham距離值。

如果Ham()的最小值與次最小值滿足Ham距離比較定義式，則角點特征集Ubrief_i中角點特征Ui與角點特征集Vbrief_j中角點特征V1j和V2j相匹配，遍歷圖像角點特征集Ubrief_i中所有角點特征，得到匹配角點特征集M和N，其中M為角點特征集Ubrief_i中角點特征Ui與角點特征集Vbrief_j中角點特征V1j的組合集，N為角點特征集Ubrief_i中角點特征Ui與角點特征集Vbrief_j中角點特征V2j的組合集，Ham距離比較定義式如下：

(6)

其中，Ham(Ui，V1j)、Ham(Ui，V2j)分別表示角點特征集Ubrief_i中角點特征Ui與角點特征集Vbrief_j中最近鄰角點特征V1j、次最近鄰角點特征V2j的Ham距離值，Th1表示設定的閾值，設定Th1的值為0.75。

然后，針對24維SURF描述子向量，使用歐式距離算法進行相似性度量，以匹配角點特征集M和N為對象，使用歐式距離算法遍歷計算匹配角點特征集M和N中每對角點特征的歐式距離，得到d的最小值與次最小值，歐式距離算法如下：

(7)

其中,xm表示Usurf_i中角點特征描述子向量中元素，ym表示Vsurf_j中角點特征描述子向量中元素，d(Ui，Vj)表示角點特征之間的歐式距離值。

歐式距離的最小值和次最小值滿足歐氏距離比較定義式組成的匹配圖像特征集為最終匹配角點特征集F，歐氏距離比較定義式如下：

(8)

其中，d(Ui，V1j)、d(Ui，V2j)分別表示角點特征集Usurf_i中的角點特征Ui與角點特征集Vsurf_j中的最近鄰角點特征V1j、次最近鄰角點特征V2j的歐式距離值，Th2表示設定的閾值，設定Th2的值為0.75。

2 仿真實驗

實驗仿真軟件為Visual Studio 2008，配置OpenCV2.4.4圖像處理庫，實驗仿真硬件為計算機，計算機的中央處理器配置是AMD A10-7300 Radeon R6 10 Compute Cores 4 CPU+6 GPU@1.90 GHz、內(nèi)存配置是4096MB RAM、操作系統(tǒng)配置是Windows 7 旗艦版32位。

仿真實驗采用Mikolajczyk圖像庫中boat、bikes、graf、leuven圖像作為仿真實驗圖像，如圖2—圖5所示，其中圖2是發(fā)生旋轉(zhuǎn)和縮放變化的boat圖像，大小為850×680像素，圖3是發(fā)生高斯模糊的bikes圖像，大小為1 000×700像素，圖4是發(fā)生視角變換的graf圖像，大小為800×640像素，圖5是發(fā)生光照變化的leuven圖像，大小為900×600像素。

(a) boat_A (b) boat_B (c) boat_C (d) boat_D (e) boat_E (f) boat_F

(a) bikes_A (b) bikes_B (c) bikes_C (d) bikes_D (e) bikes_E (f) bikes_F

(a) graf_A (b) graf_B (c) graf_C (d) graf_D (e) graf_E (f) graf_F

(a) leuven_A (b) leuven_B (c) leuven_C (d) leuven_D (e) leuven_E (f) leuven_F

仿真實驗使用傳統(tǒng)ORB算法和Shi-Tomasi- SURFORB算法對仿真實驗的待匹配圖像進行角點特征檢測與匹配，首先，對圖2(a)與圖2(b)、圖2(b)與圖2(c)、圖2(c)與圖2(d)、圖2(d)與圖2(e)、圖2(e)與圖2(f)共5對圖像進行角點特征檢測與匹配，其次，對圖3(a)與圖3(b)、圖3(b)與圖3(c)、圖3(c)與圖3(d)、圖3(d)與圖3(e)、圖3(e)與圖3(f)共5對圖像進行角點特征檢測與匹配，再次，對圖4(a)與圖4(b)、圖4(b)與圖4(c)、圖4(c)與圖4(d)、圖4(d)與圖4(e)、圖4(e)與圖4(f)共5對圖像進行角點特征檢測與匹配，最后，對圖5(a)與圖5(b)、圖5(b)與圖5(c)、圖5(c)與圖5(d)、圖5(d)與圖5(e)、圖5(e)與圖5(f)共5對圖像進行角點特征檢測與匹配，得到的圖像角點特征檢測結果圖如圖6—圖13所示，圖像角點特征匹配結果圖如圖14—圖21所示。

(a) boat_A (b) boat_ B (c) boat_C (d) boat_D (e) boat_E (f) boat_F

(a) bikes_A (b) bikes_B (c) bikes_C (d) bikes_D (e) bikes_E (f) bikes_F

(a) graf_A (b) graf_B (c) graf_C (d) graf_D (e) graf_E (f) graf_F

(a) leuven_A (b) leuven_B (c) leuven_C (d) leuven_D (e) leuven_E (f) leuven_F

使用傳統(tǒng)ORB算法對仿真實驗的待匹配圖像進行角點特征檢測，角點特征檢測結果圖如圖6—圖9所示，其中圖6表示對圖2中boat圖像的角點特征檢測結果圖，圖7表示對圖3中bikes圖像的角點特征檢測結果圖，圖8表示對圖4中graf圖像的角點特征檢測結果圖，圖9表示對圖5中l(wèi)euven圖像的角點特征檢測結果圖。

(a) boat_A (b) boat_ B (c) boat_C (d) boat_D (e) boat_E (f) boat_F

(a) bikes_A (b) bikes_B (c) bikes_C (d) bikes_D (e) bikes_E (f) bikes_F

(a) graf_A (b) graf_B (c) graf_C (d) graf_D (e) graf_E (f) graf_F

(a) leuven_A (b) leuven_B (c) leuven_C (d) leuven_D (e) leuven_E (f) leuven_F

使用Shi-Tomasi-SURFORB算法對仿真實驗的待匹配圖像進行角點檢測檢測，角點特征檢測結果圖如圖10—圖13所示，其中圖10表示對圖2中boat圖像的角點特征檢測結果圖，圖11表示對圖3中bikes圖像的角點特征檢測結果圖，圖12表示對圖4中graf圖像的角點特征檢測結果圖，圖13表示對圖5中l(wèi)euven圖像的角點特征檢測結果圖。

(a) boat A-B (b) boat B-C (c) boat C-D (d) boat D-E (e) boat E-F

(a) bikes A-B (b) bikes B-C (c) bikes C-D (d) bikes D-E (e) bikes E-F

(a) graf A-B (b) graf B-C (c) graf C-D (d) graf D-E (e) graf E-F

(a) leuven A-B (b) leuven B-C (c) leuven C-D (d) leuven D-E (e) leuven E-F

使用傳統(tǒng)ORB算法對仿真實驗的待匹配圖像進行角點特征匹配，圖像角點特征匹配結果圖如圖14—圖17所示，其中圖14表示對圖2中boat圖像的角點特征匹配結果圖，圖15表示對圖3中bikes圖像的角點特征匹配結果圖，圖16表示對圖4中graf圖像的角點特征匹配結果圖，圖17表示對圖5中l(wèi)euven圖像的角點特征匹配結果圖，其中boat A-B表示對圖2中boat_A與boat_B進行圖像角點特征匹配的結果圖，其他情況以此類推。

(a) boat A-B (b) boat B-C (c) boat C-D (d) boat D-E (e) boat E-F

(a) bikes A-B (b) bikes B-C (c) bikes C-D (d) bikes D-E (e) bikes E-F

(a) graf A-B (b) graf B-C (c) graf C-D (d) graf D-E (e) graf E-F

(a) leuven A-B (b) leuven B-C (c) leuven C-D (d) leuven D-E (e) leuven E-F

使用Shi-Tomasi-SURFORB算法對仿真實驗的待匹配圖像進行角點特征匹配，圖像角點特征匹配結果如圖18—圖21所示，其中圖18表示對圖2中boat圖像的角點特征匹配結果圖，圖19表示對圖3中bikes圖像的角點特征匹配結果圖，圖20表示對圖4中graf圖像的角點特征匹配結果圖，圖21表示對圖5中l(wèi)euven圖像的角點特征匹配結果圖，其中boatA-B表示對圖2中boat_A與boat_B進行圖像角點特征匹配的結果圖，其他情況以此類推。

仿真實驗為了比較傳統(tǒng)ORB算法與Shi- Tomasi-SURFORB算法之間的執(zhí)行效率，對圖像角點特征檢測數(shù)目、圖像角點特征匹配數(shù)目、圖像角點特征正確匹配數(shù)目、圖像角點特征匹配精度、圖像角點特征匹配精度率、圖像角點特征匹配時間和圖像角點特征匹配時間率共7個參數(shù)進行統(tǒng)計，其中圖像角點特征的匹配精度率、圖像角點特征的匹配時間率計算如下：

(9)

其中，Pm表示圖像角點特征的匹配精度率，MShi-Tomasi-SURFORB表示Shi-Tomasi-SURFORB算法的圖像角點特征的匹配精度，MORB表示傳統(tǒng)ORB算法的圖像角點特征的匹配精度。

(10)

其中，Pt表示圖像角點特征的匹配時間率，TShi-Tomasi-SURFORB表示Shi-Tomasi-SURFORB算法的圖像角點特征的匹配時間，TORB表示傳統(tǒng)ORB算法的圖像角點特征的匹配時間。

仿真實驗統(tǒng)計數(shù)據(jù)的對比分析如圖22所示，根據(jù)圖22(d)所知，與傳統(tǒng)ORB算法相比，Shi-Tomasi-SURFORB算法的角點特征匹配精度有一定的提升，根據(jù)圖22(e)所知，與傳統(tǒng)ORB算法相比，Shi-Tomasi-SURFORB算法的角點特征匹配時間有一定的提升，根據(jù)圖22(f)所知，與傳統(tǒng)ORB算法相比，圖像角點特征匹配時間率平均提升了9.46%，圖像角點特征匹配精度率平均提升了8.88%，Shi-Tomasi-SURFORB算法在圖像角點特征匹配精度和匹配時間兩方面更加均衡。

(a) 圖像角點特征檢測數(shù)目對比圖

(b) 圖像角點特征匹配數(shù)目對比圖

(c) 圖像角點特征正確匹配數(shù)目對比圖

(d) 圖像角點特征匹配精度對比圖

(e) 圖像角點特征匹配時間對比圖

(f) 相比傳統(tǒng)ORB算法的Shi-Tomasi-SURFORB算法的圖像角點特征匹配精度率、匹配時間率對比圖

其中，圖22(a)表示圖像角點特征檢測數(shù)目對比圖，圖22(b)表示圖像角點特征匹配數(shù)目對比圖，圖22(c)表示圖像角點特征正確匹配數(shù)目對比圖，圖22(d)表示圖像角點特征匹配精度對比圖，圖22(e)表示圖像角點特征匹配時間對比圖，圖22(f)表示相比傳統(tǒng)ORB算法的Shi-Tomasi-SURFORB算法的圖像角點特征匹配精度率、匹配時間率對比圖。

3 結束語

提出了Shi-Tomasi-SURFORB算法，針對傳統(tǒng)ORB算法存在的角點特征匹配精度不高的問題，使用Shi-Tomasi算法、BRIEF和SURF相融合算法、隨機投影原理與優(yōu)化的匹配算法進行優(yōu)化，得到的結論有3點：圖像角點特征匹配時間有一定提升；圖像角點特征匹配精度也有一定提升；圖像角點特征匹配時間與圖像角點特征匹配精度提升程度相當。綜上所述，Shi-Tomasi-SURFORB算法為在圖像角點特征匹配精度和耗時兩方面均衡的場景提供了一種均衡的解決方案，下一步研究重點是在圖像角點特征匹配時間相當甚至降低的情況下，提升圖像角點特征匹配精度。