駱開慶， 楊 坤， 張 健， 肖 化

(華南師范大學物理與電信工程學院，廣州 510006)

特征點指的是圖像灰度值發(fā)生劇烈變化的點或者在圖像2個邊緣上的交點，是圖像中重要的局部特征，其提取效果的好壞將直接影響應用的結果.

原則上，優(yōu)秀的算法不僅保證在嚴格要求下的實驗精度，也要考慮其計算速度. 目前已有許多特征提取的算法. 如：SIFT(Scale-Invariant Feature Transform)算法[1]，該算法具有良好尺度、旋轉和亮度的不變性，但存在計算量大、運算時間長的問題；SURF(Speeded Up Robust Features)算法[2]，該算法利用積分圖像和盒狀濾波來近似高斯濾波的方法對SIFT算法進行改進，雖然比SIFT算法提取速度更快，但是仍需要較長時間構建描述子；ORB(Oriented FAST and Rotated BRIEF)算法[3]，該算法最大的優(yōu)勢在于計算速度非?？?，但是當圖像變化較大時效果不好；BRISK特征提取算法[4]，該算法平衡了高質量的描述子和低計算需求這2個相互矛盾的目標. 為了提高BRISK特征點的性能，近些年來，學者們做了大量的研究. 如：黃鈺雯等[5]提出了改進的SURF-BRISK的算法；趙婷等[6]提出了結合區(qū)域分塊的改進BRISK算法；CEN等[7]提出了基于GMS算法的改進BRISK算法. 這些改進的BRISK算法均提高了特征匹配的精度，但提取到的特征點都存在分布不均勻的現(xiàn)象，導致圖像局部信息丟失. 2015年，MUR-ARTAL等[8]首次指出使用四叉樹的方法來改善這種特征點分布不均勻的現(xiàn)象.

基于上述分析，為提取均勻分布的特征點、提高特征點匹配精度和降低算法的運行時間，本文提出了基于四叉樹的改進BRISK特征提取算法(Quad-BRISK算法)，并選取3個具有代表性的算法(SIFT、ORB、BRISK算法)與Quad-BRISK算法進行測試對比實驗.

1 Quad-BRISK特征提取算法

Quad-BRISK特征提取算法采用四叉樹均勻化FAST(Features from Accelerated Segment Test)算法[9]在圖像金字塔[10]上提取的特征點;運用灰度質心法[11]替換傳統(tǒng)BRISK算法，采用長距離點集計算特征點的方向；通過在圖像局部區(qū)域內建立BRISK特征描述符，最終用于圖像匹配.

1.1 提取特征點

FAST特征點檢測主要檢測局部像素灰度變化明顯的地方(圖1):取圖像中的某個像素點K，并以點K為圓心選取半徑為3的Bresenham圓上的16個像素點，如果這16個點中有連續(xù)12個點的灰度值I(x)與點K的灰度值I(K)的灰度距離大于設定的閾值T，那么點K為特征點. 如果圖像中每個像素點都與其Bresenham圓上的12個點的灰度值比較，會耗時較多. 因此，可以增加一個預測試步驟，以快速剔除大多數(shù)不是角點的像素：對每一個像素，先計算圓上序號為 1、5、9、13的4個像素點與像素點K的灰度值差的絕對值，其中至少要有3個點的結果大于閾值T，才接著檢測圓上其他像素點，否則舍棄點K.

圖1 FAST特征點檢測[9]

但是，特征點是具有尺度的，在不同尺度下對同一個點進行檢測，檢測的結果可能有所不同. 所以，需要構建圖像金字塔，在圖像金字塔的每層圖像上進行FAST特征點檢測，從而得到具有尺度的特征點.

1.2 劃分特征點

使用FAST算法提取的特征點存在扎堆的情況[12]，為了將圖像中提取的特征點均勻化，需要采用四叉樹對特征點進行劃分:在圖像二維空間上利用四叉樹的結構，將這個二維空間按特征點的分布情況進行分塊，再對每個塊中的特征點進行處理. 其處理步驟如下：第一步，設整幅圖像為一個大塊，則其為初始節(jié)點，可得到初始的四叉樹結構. 第二步，對圖像中所有的節(jié)點進行劃分操作：如果節(jié)點里面的特征點數(shù)為0，則刪去這個節(jié)點；否則，將這個節(jié)點分成4個子節(jié)點. 第三步，重復進行第二步，直到最終生成的節(jié)點個數(shù)不小于設置提取特征點的個數(shù)或者達到最大的節(jié)點個數(shù)，則結束劃分節(jié)點. 第四步，從每個節(jié)點中選取Harris響應值[13]最高的特征點.

對已經(jīng)提取FAST特征點的圖像，采用四叉樹方法劃分特征點，劃分前圖像中提取出的特征點明顯分布不均勻(圖2A). 按照上述步驟對圖像中的特征點進行四叉樹劃分后(圖2C)，每個節(jié)點中特征點至少大于1個，在節(jié)點中選取1個特征點作為該節(jié)點下的特征點，使得圖像中的特征點均勻分布(圖2D).

圖2 四叉樹方法劃分特征點

1.3 計算特征點的方向

FAST特征點檢測出來的特征點不具備旋轉不變性，當圖像發(fā)生旋轉時檢測效果較差. 為了使圖像發(fā)生旋轉后還能檢測出是同一個特征點，使用灰度質心法將提取到的特征點設置為帶方向的特征點，具體步驟如下：

(1)以特征點為中心的圖像塊B的矩為：

(1)

其中，p,q={0,1}，mpq為圖像塊的矩，qp為矩的階數(shù)的系數(shù)，x和y為圖像塊B中像素點的坐標值，I(x,y)為像素點(x,y)處的灰度值；

(2)通過以下公式計算該圖像塊的質心：

(2)

其中，m00是圖像塊的0階矩，m01和m10是圖像塊的1階矩；

(3)將圖像塊的幾何中心O與質心C相連，得到方向向量OC，于是特征點的方向定義為：

(3)

通過以上步驟，計算出特征點的方向. 在建立該特征點描述符的時候，采用此處計算的方向將該特征點進行旋轉，使該點具有旋轉的描述，從而提高了在不同圖像之間表達的穩(wěn)定性.

1.4 建立BRISK特征點描述符

通過FAST算法檢測確定了特征點在圖像中位置信息之后，為了能夠與另外一張圖片進行特征點匹配，需要提取特征點周圍的環(huán)境信息，即建立BRISK特征點描述符. 通過對比2張圖片中特征點的周圍環(huán)境信息的相似度來判定是否為同一個特征點.

1.4.1 采樣模式 BRISK特征點描述符是利用關鍵點的鄰域進行采樣，其采樣模式如圖3所示，一共采樣N個點.

為了避免混疊效果，對采樣模式中的采樣點Pi進行高斯平滑，標準差σi正比于每個采樣點對應于各自中心的距離，定位和擴展模式在圖像中相應地為關鍵點K模式化，考慮一個N(N-1)/2個采樣點對，用集合(Pi,Pj)表示. 這些點的平滑像素值分別為I(Pi,σi)和I(Pj,σj)，用于估計局部梯度值g(Pi,Pj)的公式為：

(4)

所有組合方式的集合稱為采樣點對：

A={(Pi,Pj)2×2|i

(5)

短距離點對子集S為：

(6)

其中，閾值距離設置為：δmax=9.75t，t是特征點K所在的尺度.

(7)

1.5 描述符匹配

將采樣的短距離子集中的512個點對，根據(jù)式(7)得到該特征點的512 Bit的二進制描述符. 在匹配2個BRISK特征點時，通過2個特征點描述符之間的漢明距離來表示這2個特征點周圍的環(huán)境信息的相似性：漢明距離越小，相似性越高.

1.6 Quad-BRISK算法步驟

Quad-BRISK算法與傳統(tǒng)BRISK算法的不同之處在于：提取BRISK特征點時采用四叉樹方法劃分特征點,使特征點均勻分布；特征匹配時采用分塊區(qū)域匹配，減小了匹配范圍，提高了匹配的精度；使用灰度質心法給每個特征點計算方向；使用旋轉一致性原則剔除部分誤匹配點，進一步提高了特征點的匹配精度. 主要步驟如下：

(1)將圖像構造8層尺度為1.2的圖像金字塔，設置圖像金字塔中每層圖像要提取的特征點數(shù)量；

(2)將圖像金字塔的每一層圖像劃分為N個邊長為30像素的矩形區(qū)域(圖像邊緣進行融合處理)，分別在這N個區(qū)域中做FAST關鍵點提取，當檢測到FAST關鍵點的數(shù)量為0時，降低算法閾值并重新進行關鍵點提取，使得在弱紋理區(qū)域也能提取到關鍵點；

(3)將圖像金字塔的每層圖像中提取到的特征點按層進行四叉樹劃分；

(4)剔除每個節(jié)點中Harris響應值非極大值的特征點；

(5)采用灰度質心法計算每個特征點的方向；

(6)計算特征點的BRISK描述符；

(7)將特征點劃分在圖像中對應的網(wǎng)格區(qū)域內，并在2幅圖像對應的網(wǎng)格區(qū)域內做特征點匹配；

(8)根據(jù)勞氏算法[1]，使用比較最近鄰距離與次近鄰距離的方法剔除誤匹配點，最后采用RANSAC算法[14]，得到精匹配圖像.

2 實驗結果與分析

為了驗證本文算法(Quad-BRISK算法)匹配精度的優(yōu)越性，選取3個近期具有代表性的算法(SIFT、ORB、BRISK算法)與Quad-BRISK算法進行測試對比，比較各種算法在不同圖像上的處理時間.

2.1 實驗數(shù)據(jù)

選擇Mikolajczyk和Schmid的特征對比試驗圖集[15]中的5組圖像(圖4)，每組6幅圖像. 其中：利用Graf圖像組測試各算法在仿射變化下的匹配效果；利用Boat圖像組測試各算法在尺度和旋轉變化下的匹配效果；利用Trees圖像組測試各算法在模糊變化下的匹配效果；利用Leuven圖像組測試各算法在光照變化下的匹配效果；利用UBC圖像組測試各算法在不同壓縮程度下的匹配效果.

圖4 Oxford標準圖集

2.2 實驗環(huán)境與評價標準

本文的實驗平臺為：操作系統(tǒng)為Linux 16.04 64位的臺式電腦，Intel(R) Core(TM)i7-7700 CPU@3.60 GHz 8 GB內存，運行環(huán)境為CLion 2.0和Opencv2.4.9.

本文的實驗評價指標為：(1)算法消耗的時間. 用此指標來評價算法進行特征檢測和匹配的速度,消耗的時間越短表明其速度越快. (2)特征點匹配正確率(Correct Matching Rate，CMR)[16]. 其計算公式為：

(8)

其中，mc為RANSAC之后正確匹配個數(shù)，m為最近鄰與次近鄰距離和旋轉一致性篩選后匹配個數(shù). CMR值越大，表示該算法的匹配效果越好.

2.3 結果分析

本文選擇5組測試圖像對各算法進行測試，以第1幅圖為標準圖像，后面5幅圖像為待匹配圖像. 以下各表中，組號1表示第1幅圖與第2幅圖的匹配結果，組號2表示第1幅圖與第3幅圖的匹配結果，以此類推. 其中，SIFT、ORB、Quad-BRISK算法提取每張圖像中的1 000個特征點，BRISK算法提取每張圖像中的所有特征點.

2.3.1 仿射不變性實驗 Graf圖像組的每個圖像具有不同的視角，故用于測試SIFT、ORB、BRISK、Quad-BRISK算法對于仿射變化的適應性.

從實驗結果(表1)可以看出：在第1組和第2組實驗中，Quad-BRISK算法的匹配率高于其他算法；在第3～5組的這些仿射變換較大的實驗組中，各種算法的魯棒性都不是很好. 由Graf圖像組中第1幅圖和第2幅圖的特征點匹配效果(圖5)可以看出：SIFT、ORB、Quad-BRISK算法同時提取相同個數(shù)的點，由于Quad-BRISK算法采取更加嚴格地剔除誤匹配點的方式，所以匹配點也減少了；雖然，BRISK算法提取的特征點較多，最終匹配的特征點也較多，但其匹配正確率最低.

表1 4種算法在圖像仿射變化下特征點的匹配正確率

Table 1 The correct matching rate of feature points in four algorithms under image affine changes %

組號SIFTORBBRISKQuad-BRISK182.3990.7582.0392.78267.1872.8266.4591.433----4----5----

注：“-”表示特征點匹配正確率過低或者算法失效，無意義.

2.3.2 尺度和旋轉不變性實驗 Boat圖像組的每個圖像具有不同的尺度和旋轉變換，故用于測試SIFT、ORB、BRISK、Quad-BRISK算法對于尺度和旋轉變化的適應性.

圖5 4種算法在Graf圖像中的特征點匹配效果

Figure 5 The feature point matching effect images of four algorithms in Graf images

由測試結果(表2)可以看出：在第1組和第2組實驗中，Quad-BRISK算法對尺度和旋轉不變性實驗圖像的匹配正確率分別為91.57%和100%，除在第1組實驗中略低于ORB算法，均高于其他算法；其他尺度和旋轉變化較大的實驗中，各種算法的魯棒性都不是很好. 由Boat圖像組中第1幅圖和第2幅圖的特征點匹配效果(圖6)可看出：Quad-BRISK算法提取的體征點分布更加均勻，不存在明顯的扎堆現(xiàn)象；其他3種算法提取的特征點均存在聚集的現(xiàn)象，且ORB算法提取的特征點的扎堆現(xiàn)象最明顯.

表2 4種算法在圖像尺度和旋轉變化下特征點的匹配正確率

Table 2 The correct matching rate of feature points in four algorithms under image scale and rotation changes

%

注：“-”表示特征點匹配正確率過低或者算法失效，無意義.

圖6 4種算法在Boat圖像中的特征點匹配效果

Figure 6 The feature point matching effect images of four algorithms in Boat images

2.3.3 光照不變性實驗 Leuven圖像組的每個圖像具有不同的光照強度，故用于測試SIFT、ORB、BRISK、Quad-BRISK算法對于光照變化的適應性.

由測試結果(表3)可以看出：SIFT、ORB、Quad-BRISK算法在不同光照的情況下都可以正常運行；Quad-BRISK算法的匹配正確率最高，其次為ORB算法. 由Leuven圖像組中第1幅圖和第2幅圖的特征點匹配效果(圖7)可以看出：Quad-BRISK算法提取的特征點分布更加均勻，不存在明顯的扎堆現(xiàn)象；SIFT算法和ORB算法在圖片的下方提取的特征點很少，都在圖片的上方提取，扎堆現(xiàn)象較明顯.

表3 4種算法在圖像光照變化下特征點的匹配正確率

Table 3 The correct matching rate of feature points in four algorithms under image lighting changes

%

注：“-”表示特征點匹配正確率過低或者算法失效，無意義.

圖7 4種算法在Leuven圖像中的特征點匹配效果

Figure 7 The feature point matching effect images of four algorithms in Leuven images

2.3.4 模糊不變性實驗 Trees圖像組的每個圖像具有不同的模糊程度，故用于測試SIFT、ORB、BRISK、Quad-BRISK算法對于模糊程度變化的適應性.

由測試結果(表4)可以看出：Quad-BRISK算法在不同模糊程度的情況下都可以較好地運行，特征點的匹配精度大部分時候高于其他算法. 由Trees圖像組中第1幅圖和第2幅圖的特征點匹配效果(圖8)可以看出：4種算法提取的特征點都沒有較嚴重的扎堆現(xiàn)象，其中Quad-BRISK算法提取的特征點分布更加均勻.

表4 4種算法在圖像模糊變化下特征點的匹配正確率

Table 4 The correct matching rate of feature points in four algorithms under image blur changes

%

注：“-”表示特征點匹配正確率過低或者算法失效，無意義.

2.3.5 壓縮不變性實驗 UBC圖像組的每個圖像具有不同的壓縮程度，故用于測試SIFT、ORB、BRISK、Quad-BRISK算法對于不同壓縮程度的適應性.

圖8 4種算法在Trees圖像中的特征點匹配效果

Figure 8 The feature point matching effect images of four algorithms in Trees images

由測試結果(表5)可以看出：在圖像具有不同壓縮程度的情況下，4種算法提取的特征點的匹配精度都較好，其中Quad-BRISK算法的匹配精度高于BRISK算法和SIFT算法，與ORB算法的匹配精度相似. 由UBC圖像組中第1幅圖和第2幅圖的特征點匹配效果(圖9)可以看出：SIFT算法和ORB算法提取的特征點存在明顯的聚集現(xiàn)象，而Quad-BRISK算法提取的特征點分布較均勻，不存在明顯的扎堆現(xiàn)象.

表5 4種算法在圖像壓縮下特征點的匹配正確率

Table 5 The correct matching rate of feature points in four algorithms under image compression %

組號SIFTORBBRISKQuad-BRISK185.6899.6797.5099.46280.2699.4495.3498.97375.6298.3191.0198.12465.3295.5780.5297.43557.7893.1759.2793.37

圖9 4種算法在UBC圖像中的特征點匹配效果

Figure 9 The feature point matching effect images of four algorithms in UBC images

2.3.6 運行時間分析 為評估Quad-BRISK算法與SIFT、ORB、BRISK算法的時間復雜度，選取Graf、Boat、Trees、Leuven和UBC圖像組的第1、2幅圖像(即第1組)，統(tǒng)計分析使用4種算法在每張圖片中提取1 000個特征點需消耗的平均時間. 由結果(表6)可知：SIFT算法耗時最多；ORB算法耗時最少；Quad-BRISK算法相比于傳統(tǒng)的BRISK算法耗時更少，因為Quad-BRISK算法是先將特征點劃分到圖像中相應的網(wǎng)格區(qū)域內，然后再對2幅圖像對應區(qū)域內的特征點做匹配，加速了特征點的匹配效率，所以，Quad-BRISK算法在提高精度的同時也減少了運行時間. 此外，對每個圖像組中的其他圖像的消耗時間也進行了對比分析實驗，最終的時間對比分析趨勢與此類似，不一一贅述.

表6 4種算法的運行時間分析

Table 6 The analysis of the running time of four algorithms ms

圖集SIFTORBBRISKQuad-BRISKGraf469.929.16121.983.89Boat564.439.38144.0113.80Trees746.656.16224.7154.90Leuven495.227.12118.076.47UBC498.232.82120.698.95

3 結論

本文提出了基于四叉樹的BRISK特征提取算法(Quad-BRISK算法)：針對原始BRISK算法提取的圖像特征點分布不均勻的缺點，采用了四叉樹方法劃分特征點；使用灰度質心法替換傳統(tǒng)BRISK采用長距離點集計算主方向的方法，提高了旋轉一致性的穩(wěn)定性；在粗匹配結果中采用旋轉一致性剔除誤匹配點，進一步提高特征匹配的精度. 在Mikolajczyk和Schmid的5組特征對比試驗圖集上，使用Quad-BRISK算法與SIFT、ORB、BRISK算法分別進行了5種不同變化場景下的對比實驗，并且分析了運行時間. 實驗結果表明：Quad-BRISK算法性能優(yōu)于其他算法，不僅能夠提取更加穩(wěn)定的特征點，同時提高了特征點匹配精度和計算速度. Quad-BRISK算法可進一步應用于更復雜或者更高一級的算法中，如圖像拼接算法、三維重建算法及SLAM算法.