一種動態跟蹤尺度補償的ORB特征點提取算法

王傳傳，周雪云，吳其濱

(廣州工商學院工學院，廣東 廣州 510800)

997459445@qq.com;zhouxy@gzgs.edu.cn;570760876@qq.com

1 引言(Introduction)

SIFT算法和SURF算法無法滿足對實時性要求較高的圖像處理任務，針對該問題，RUBLEE等[1]提出了ORB(Oriented FAST and Rotated BRIEF)算法，極大地提高了特征點的提取速度。ORB算法是在FAST角點提取算法[2]和BRIEF描述算子的基礎上改進得來的，具有旋轉不變性，且能抗噪聲。ORB算法在速度方面比SIFT算法快兩個數量級，比SURF算法快一個數量級，在有些圖像數據上的表現更好。

ORB算法的缺點是沒有很好地解決尺度不變的問題。換言之，用ORB算法對兩幅擁有相同目標物且有尺度差別的圖像提取特征點后，匹配點對的數量和質量會因尺度變化而下降。為了解決這一問題，利用帶圖像金字塔的LK光流算法對跟蹤尺度進行補償，進而優化ORB算法，實現動態跟蹤目標物的目的。為了驗證該方案的有效性，本文利用OpenCV視覺庫進行實驗，在算法的運行時間和特征點提取數量方面與原始ORB等算法進行性能對比評估。結果表明，優化后的算法能以較小的時間代價，提高圖像特征點的采集數量。

2 ORB特征點檢測與描述算法(The algorithm of ORB feature point detection and description)

2.1 O-FAST角點檢測算法

FAST(Features from Accelerated Segment Test)特征檢測[2]算法認為如果圖像中某一像素點與其鄰域內多數像素點的屬性不同，則該像素點可能為一個特征角點[3]。為了檢測某一像素點是否是FAST特征角點，利用布雷森漢姆(Bresenham)直線算法畫一個以該像素點為圓心的半徑為N個像素單位的圓，FAST算子檢測如圖1所示。

圖1 FAST算子檢測Fig.1 FAST operator detection

為了便于辨識，FAST 算法根據N值不同，標記為FAST-N算法。當采用FAST-3時，Bresenham圓共由16 個像素點組成。令點的灰度值為，檢測閾值為。若Bresenham圓上的16 個像素點中有連續個點都大于或都小于，則把該點作為FAST特征角點。

上述方法的缺點是必須循環遍歷16 個像素點才能做出判斷，本文采取了一種加速特征點的獲取方法：在16 個點中任意選取一個點作為起始點，沿順時針方向，每隔90°選取一點，如果這四個點中有三個都大于或都小于，就把此中心點作為FAST特征候選點；反之，此中心點不是FAST特征角點。

經試驗證明，當取9時的效果最好，本文采用了FAST-9特征方法，如圖2所示。

圖2 FAST特征角點Fig.2 FAST feature corner

由于FAST算法不能保持特征點的旋轉不變性，所以O-FAST算法在FAST算法的基礎上，用強度質心[1]方法添加方向屬性，其具體做法如下。

先假設圖像中某一區域的質心和幾何中心為不同點，利用質心和幾何中心所構成的向量刻畫方向，則該區域的矩表示如下：

2.2 R-BRIEF特征點描述算法

針對基于梯度直方圖的特征描述符，SIFT和SURF算法無法滿足對實時性要求很高的系統，Michael Calonder等人提出了一種基于BRIEF算子[4]的特征描述算法，其實現步驟如下。

Step1:進行定義測試。

在高斯平滑處理后的圖像上選取一塊大小為S×S的局部區域，在區域上進行測試：

選取BRIEF-64[4]進行介紹，即BRIEF特征串的存儲空間占64 個字節，共需64×8=512 bits。

Step2:進行點對的選擇。

由公式(5)可知，構建一個512 bits的特征串需要512 個有序點對。

由于BRIEF算法不具備旋轉不變性，所以需要將BRIEF改造成具有旋轉感知性(Rotation-Aware)的R-BRIEF算法。ORB算法采用BRIEF-32，即描述符的串長度為256 bits。本文選取了組測試點對，組成一個的矩陣：

所以，受控的BRIEF算子(steered BRIEF)可定義如下：

為了加速計算過程，預先構建一張查找表，將角度離散化，步進單位設為，只要離散化的O-FAST特征角點方向與上述角度標尺相符，則可以通過查找表查找對應的點集，并計算描述符。

BRIEF描述符采用點對的方式進行測試，這種方法雖然簡單易行，但是無法較好地抑制噪聲。為了解決這一問題，ORB算法采用點集對的方法。如圖3所示，以特征角點為中心選取一個邊長為的正方形鄰域，在該鄰域中用邊長為的正方形子窗口(點集)代替BRIEF描述符中的點，用點集對代替BRIEF描述符中的點對。這樣該鄰域中應有個子窗口。從中任取兩個構成點集對，那么點集對的數量為，去掉窗口相互覆蓋的點集對，真正可用的點集對的數量為。

圖3 R-BRIEF測試集Fig.3 R-BRIEF test sets

未添加旋轉特性的BRIEF具有的一個優點是二進制特征描述符有較大的方差且均值在0.5附近，可以很好地對特征點進行區分；而添加旋轉特性的steered BRIEF卻喪失了這一特性。本文采用高斯BRIEF點對100 k個樣本特征點進行描述，得到均向量的位響應均值分布。同時，ORB算法通過如下操作提高steered BRIEF的辨識度。

(2)將測試結果按照與0.5做差，得到的值按從大到小排序，得到隊列T。

(3)應用貪婪算法：①將隊列T的隊首移入結果集R中；②隊列T的新隊首與結果集R中的所有結果進行比較，若它們的相關性大于預設閾值，則放棄隊首，減少結果集R的冗余信息，否則添加到R中；③當結果集R有256 個元素時，將R作為描述符，若R中的元素個數不及256 個，則提高預設閾值，然后重復前兩個步驟。

3 ORB算法的改進(Improved ORB algorithm)

3.1 光流動態跟蹤法

運動物體在視頻中表現為相關目標特征像素點在連續幀的移動，而由于人眼的視覺暫留現象，因此像素點的移動可以用“光流”刻畫，用光流的矢量速度對圖像中物體的運動信息進行描述。帶圖像金字塔的LK(Lucas-Kanade)光流算法[5]可以解決多尺度下“大運動”的跟蹤問題[6]。原始的LK算法(假設條件如圖4所示)的實現必須具備下面三個假定條件[7]。

圖4 LK算法的條件Fig.4 Condition of the LK algorithm

條件1：灰度保持不變。

視頻中運動的目標物在相鄰幀間的灰度保持不變，則

也就是說，運動目標物的灰度不隨時間的變化而發生改變，那么：

條件2：“小運動”。

運動目標物體在連續幀間的位移較小，即屬于“小運動”。由公式(11)、公式(12)和鏈式法則，可得到：

實際場景中，不能完全保證滿足前兩個假定條件，導致計算的光流速度會有微小的偏差。因此，只要按照上述方法求得的光流速度足夠接近真實的速度，就可以利用牛頓法迭代得到相對準確的收斂解。如圖5所示，將首次獲得的有偏差的光流速度作為初始值并進行下一次迭代，之后重復該過程。依據第一假定條件可知，空域導數始終保持不變，而時域導數每次迭代前都要重新計算，正常經過5 次迭代收斂即可獲得滿意的光流速。

圖5 牛頓法求光流速度的收斂解Fig.5 Convergence solution of optical flow velocity by Newton method

如圖6所示，由于已知條件少，導致無法求出二維空間下的光流速度，只能獲取垂直運動分量，這也被稱作孔徑問題[7]。通過小孔，觀察不到物體的下移運動，只能觀察到物體的右向運動，如圖7所示。

圖6 二維光流速度的求解Fig.6 Solution of two dimensional optical flow velocity

圖7 孔徑問題Fig.7 The aperture problem

為了解決孔徑問題，就需要用到第三個假設條件。

條件3：運動區域的空間連續性。

在運動場中，由于目標物在圖像中的投影是區域性的，表現為連續幀之間位移的像素點，其鄰域的像素點也具有類似的位移趨勢。本文通過建立中心點鄰域像素的方程組增加約束條件，從而避免了孔徑問題的出現。如果采用5×5的鄰域描述中心點的運動狀態，則

當兩條或兩條以上的邊緣出現在5×5的窗口鄰域中，可利用最小二乘法求解該系統方程。通過公式(17)求解得殘差平方和的最小值：

實際場景中，視頻獲取到的動態目標相對于圖像尺度來說位移較大，導致LK算法處理跟蹤問題所得的結果也不理想。當用大尺度窗口跟蹤“大運動”時，又會破壞第三條運動連貫性的假設條件。本文引入圖像金字塔模型，采用由粗至精的方式(Coarse-to-Fine)對光流進行估計，金字塔頂層的一個像素點可以表征其最底層的若干個像素點，從金字塔最頂層對光流進行估計，并將估算的結果作為下一層估計的初始值。這不僅避免了“小運動”的約束限制，而且隨著計算的向下進行，計算精度也會提高[8]。算法演示過程如圖8所示。

圖8 帶圖像金字塔的LK光流算法Fig.8 LK optical flow algorithm with image pyramid

3.2 基于動態跟蹤的尺度補償策略

由于ORB算法中的O-FAST角點檢測和R-BRIEF特征描述都沒有解決尺度問題，也就是說ORB算法不具備尺度不變性，在全景拼接的過程中，場景的尺度通常不會發生劇烈的變化，為了避免視圖場景中(比如在高速公路上行駛的汽車)突發的極端情況，對尺度不變性的保證還是必要的，而且這么做可以很好地提高拼接的準確度和精確性。

本文利用帶圖像金字塔的LK光流算法對跟蹤尺度進行補償[9-10]，并進行實驗。視頻中產生的尺度變化是由目標物與背景產生消逝點方向的相對運動導致，如圖9所示。靜止場景往往不會發生尺度變化，當目標物的尺度發生變化時，ORB算法所檢測到的特征點數可能會下降，當添加運動跟蹤算法后，目標物可以最大限度地保留原始的特征點，這樣就保證了ORB算法檢測的特征點不因尺度變化而丟失。如圖10(a)中，汽車的部分特征信息因尺度變化而丟失，圖10(b)中，帶圖像金字塔的LK算法對ORB進行補償，保留了上一幀中汽車的部分特征信息。

圖9 消逝點方向相對運動產生尺度上的變化Fig.9 Scale changes produced by the relative movement of the vanishing point

圖10 光流法對ORB算法的尺度補償Fig.10 Scale compensation of ORB algorithm by optical flow method

本文通過帶圖像金字塔的LK光流算法對視頻中的物品進行動態跟蹤實驗。在視頻的同一幀，分別利用原始ORB算法和經尺度補償后的ORB算法提取特征點，對比采集結果，如圖11所示。

圖11 特征點提取對比實驗Fig.11 Comparative experiment of feature point extraction

從圖11(a)和(b)可以看出，圖片尺度上有明顯的差異，從A、B區域提取的特征點密集程度可以看出，經尺度補償后的ORB算法提取的特征點數量要明顯多于原始ORB算法。

此外，通過攝像頭采集視頻數據，選擇采集視頻前30 幀的數據，運用OpenCV視覺庫進行實驗，對尺度補償后的ORB算法的運行時間和特征提取數量進行對比統計，結果詳見表1。

表1 特征提取算法性能對比Tab.1 The performance comparison of feature extraction algorithms

由表1可知，原始的ORB算法比SIFT算法快兩個數量級，比SURF算法快一個數量級。經動態跟蹤尺度補償后的ORB算法和SURF算法的時間損耗基本相當，但補償后的ORB算法提取的特征點數量約是SIFT算法的2.44 倍、SURF算法的2.24 倍、原始ORB算法的1.47 倍。結果表明，經動態跟蹤尺度補償后的ORB算法性能更優。

4 結論(Conclusion)

本文介紹了ORB算法的特征提取和特征描述算法，指出ORB算法不具有尺度不變性。在全景拼接中，為了確保圖像匹配的準確性，需要對原始的ORB算法進行改進。由于帶圖像金字塔的LK光流算法，可以解決多尺度下“大運動”的跟蹤問題，即該算法對“大運動”、多尺度下的動態跟蹤有著良好的效果。基于此，本文運用動態跟蹤的方法對ORB算法進行尺度補償，分析了該設計思路的可行性。為了驗證動態尺度補償后的ORB算法性能，在Windows系統下，通過攝像頭采集視頻數據，利用OpenCV視覺庫進行實驗，在算法的運行時間和特征點提取數量上與原始ORB等算法進行對比，結果表明：經過動態尺度補償后的算法能以較短的時間代價，提高特征點的采集數量，實驗結果符合預期，為提高圖像特征點提取性能提供了一種理論支持。