一種動(dòng)態(tài)跟蹤尺度補(bǔ)償?shù)腛RB特征點(diǎn)提取算法

王傳傳，周雪云，吳其濱

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

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

1 引言(Introduction)

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

ORB算法的缺點(diǎn)是沒有很好地解決尺度不變的問題。換言之，用ORB算法對(duì)兩幅擁有相同目標(biāo)物且有尺度差別的圖像提取特征點(diǎn)后，匹配點(diǎn)對(duì)的數(shù)量和質(zhì)量會(huì)因尺度變化而下降。為了解決這一問題，利用帶圖像金字塔的LK光流算法對(duì)跟蹤尺度進(jìn)行補(bǔ)償，進(jìn)而優(yōu)化ORB算法，實(shí)現(xiàn)動(dòng)態(tài)跟蹤目標(biāo)物的目的。為了驗(yàn)證該方案的有效性，本文利用OpenCV視覺庫(kù)進(jìn)行實(shí)驗(yàn)，在算法的運(yùn)行時(shí)間和特征點(diǎn)提取數(shù)量方面與原始ORB等算法進(jìn)行性能對(duì)比評(píng)估。結(jié)果表明，優(yōu)化后的算法能以較小的時(shí)間代價(jià)，提高圖像特征點(diǎn)的采集數(shù)量。

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

2.1 O-FAST角點(diǎn)檢測(cè)算法

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

圖1 FAST算子檢測(cè)Fig.1 FAST operator detection

為了便于辨識(shí)，F(xiàn)AST 算法根據(jù)N值不同，標(biāo)記為FAST-N算法。當(dāng)采用FAST-3時(shí)，Bresenham圓共由16 個(gè)像素點(diǎn)組成。令點(diǎn)的灰度值為，檢測(cè)閾值為。若Bresenham圓上的16 個(gè)像素點(diǎn)中有連續(xù)個(gè)點(diǎn)都大于或都小于，則把該點(diǎn)作為FAST特征角點(diǎn)。

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

經(jīng)試驗(yàn)證明，當(dāng)取9時(shí)的效果最好，本文采用了FAST-9特征方法，如圖2所示。

圖2 FAST特征角點(diǎn)Fig.2 FAST feature corner

由于FAST算法不能保持特征點(diǎn)的旋轉(zhuǎn)不變性，所以O(shè)-FAST算法在FAST算法的基礎(chǔ)上，用強(qiáng)度質(zhì)心[1]方法添加方向?qū)傩?，其具體做法如下。

先假設(shè)圖像中某一區(qū)域的質(zhì)心和幾何中心為不同點(diǎn)，利用質(zhì)心和幾何中心所構(gòu)成的向量刻畫方向，則該區(qū)域的矩表示如下：

2.2 R-BRIEF特征點(diǎn)描述算法

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

Step1:進(jìn)行定義測(cè)試。

在高斯平滑處理后的圖像上選取一塊大小為S×S的局部區(qū)域，在區(qū)域上進(jìn)行測(cè)試：

選取BRIEF-64[4]進(jìn)行介紹，即BRIEF特征串的存儲(chǔ)空間占64 個(gè)字節(jié)，共需64×8=512 bits。

Step2:進(jìn)行點(diǎn)對(duì)的選擇。

由公式(5)可知，構(gòu)建一個(gè)512 bits的特征串需要512 個(gè)有序點(diǎn)對(duì)。

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

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

為了加速計(jì)算過程，預(yù)先構(gòu)建一張查找表，將角度離散化，步進(jìn)單位設(shè)為，只要離散化的O-FAST特征角點(diǎn)方向與上述角度標(biāo)尺相符，則可以通過查找表查找對(duì)應(yīng)的點(diǎn)集，并計(jì)算描述符。

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

圖3 R-BRIEF測(cè)試集Fig.3 R-BRIEF test sets

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

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

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

3 ORB算法的改進(jìn)(Improved ORB algorithm)

3.1 光流動(dòng)態(tài)跟蹤法

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

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

條件1：灰度保持不變。

視頻中運(yùn)動(dòng)的目標(biāo)物在相鄰幀間的灰度保持不變，則

也就是說，運(yùn)動(dòng)目標(biāo)物的灰度不隨時(shí)間的變化而發(fā)生改變，那么：

條件2：“小運(yùn)動(dòng)”。

運(yùn)動(dòng)目標(biāo)物體在連續(xù)幀間的位移較小，即屬于“小運(yùn)動(dòng)”。由公式(11)、公式(12)和鏈?zhǔn)椒▌t，可得到：

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

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

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

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

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

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

條件3：運(yùn)動(dòng)區(qū)域的空間連續(xù)性。

在運(yùn)動(dòng)場(chǎng)中，由于目標(biāo)物在圖像中的投影是區(qū)域性的，表現(xiàn)為連續(xù)幀之間位移的像素點(diǎn)，其鄰域的像素點(diǎn)也具有類似的位移趨勢(shì)。本文通過建立中心點(diǎn)鄰域像素的方程組增加約束條件，從而避免了孔徑問題的出現(xiàn)。如果采用5×5的鄰域描述中心點(diǎn)的運(yùn)動(dòng)狀態(tài)，則

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

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

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

3.2 基于動(dòng)態(tài)跟蹤的尺度補(bǔ)償策略

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

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

圖9 消逝點(diǎn)方向相對(duì)運(yùn)動(dòng)產(chǎn)生尺度上的變化Fig.9 Scale changes produced by the relative movement of the vanishing point

圖10 光流法對(duì)ORB算法的尺度補(bǔ)償Fig.10 Scale compensation of ORB algorithm by optical flow method

本文通過帶圖像金字塔的LK光流算法對(duì)視頻中的物品進(jìn)行動(dòng)態(tài)跟蹤實(shí)驗(yàn)。在視頻的同一幀，分別利用原始ORB算法和經(jīng)尺度補(bǔ)償后的ORB算法提取特征點(diǎn)，對(duì)比采集結(jié)果，如圖11所示。

圖11 特征點(diǎn)提取對(duì)比實(shí)驗(yàn)Fig.11 Comparative experiment of feature point extraction

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

此外，通過攝像頭采集視頻數(shù)據(jù)，選擇采集視頻前30 幀的數(shù)據(jù)，運(yùn)用OpenCV視覺庫(kù)進(jìn)行實(shí)驗(yàn)，對(duì)尺度補(bǔ)償后的ORB算法的運(yùn)行時(shí)間和特征提取數(shù)量進(jìn)行對(duì)比統(tǒng)計(jì)，結(jié)果詳見表1。

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

由表1可知，原始的ORB算法比SIFT算法快兩個(gè)數(shù)量級(jí)，比SURF算法快一個(gè)數(shù)量級(jí)。經(jīng)動(dòng)態(tài)跟蹤尺度補(bǔ)償后的ORB算法和SURF算法的時(shí)間損耗基本相當(dāng)，但補(bǔ)償后的ORB算法提取的特征點(diǎn)數(shù)量約是SIFT算法的2.44 倍、SURF算法的2.24 倍、原始ORB算法的1.47 倍。結(jié)果表明，經(jīng)動(dòng)態(tài)跟蹤尺度補(bǔ)償后的ORB算法性能更優(yōu)。

4 結(jié)論(Conclusion)

本文介紹了ORB算法的特征提取和特征描述算法，指出ORB算法不具有尺度不變性。在全景拼接中，為了確保圖像匹配的準(zhǔn)確性，需要對(duì)原始的ORB算法進(jìn)行改進(jìn)。由于帶圖像金字塔的LK光流算法，可以解決多尺度下“大運(yùn)動(dòng)”的跟蹤問題，即該算法對(duì)“大運(yùn)動(dòng)”、多尺度下的動(dòng)態(tài)跟蹤有著良好的效果?；诖耍疚倪\(yùn)用動(dòng)態(tài)跟蹤的方法對(duì)ORB算法進(jìn)行尺度補(bǔ)償，分析了該設(shè)計(jì)思路的可行性。為了驗(yàn)證動(dòng)態(tài)尺度補(bǔ)償后的ORB算法性能，在Windows系統(tǒng)下，通過攝像頭采集視頻數(shù)據(jù)，利用OpenCV視覺庫(kù)進(jìn)行實(shí)驗(yàn)，在算法的運(yùn)行時(shí)間和特征點(diǎn)提取數(shù)量上與原始ORB等算法進(jìn)行對(duì)比，結(jié)果表明：經(jīng)過動(dòng)態(tài)尺度補(bǔ)償后的算法能以較短的時(shí)間代價(jià)，提高特征點(diǎn)的采集數(shù)量，實(shí)驗(yàn)結(jié)果符合預(yù)期，為提高圖像特征點(diǎn)提取性能提供了一種理論支持。