基于BRISK改進的快速角點特征算法＊

（1.海軍航空工程學院兵器科學與技術系 煙臺 264001）（2.91055部隊6分隊 臺州 318050）

1 引言

在計算機視覺領域，區(qū)分性強、對多種幾何及光照變化具有不變性的局部特征，特別是其中較為重要的角點特征，由于具有旋轉不變性和不隨光照條件變化而變化的特點，廣泛應用于基線匹配、特定目標識別、目標類別識別、圖像及視頻檢測、機器人導航、場景分類、紋理識別和數(shù)據(jù)挖掘等多個領域內。角點特征檢測及描述算法一直是研究的熱點［1～3］。

近幾年，在滿足對尺度、旋轉，噪聲具有魯棒性的前提下，為了實時處理和降低硬件需求，特征檢測匹配的研究重點為算法計算復雜性和內存占用量等方面。經過國內外學者的努力，已經有大量的速度較快且具有魯棒性的相關算法，包括尺度不變性特征轉換（SIFT）［4］，加速魯棒特征（SURF）［5］，定向快速旋轉Brief特征（ORB）［6］以及近期由Strfan等人提出的二值化魯棒尺度不變特征（BRISK）［7］等。其中，BRISK 特征算子是一種新的具有尺度不變性和旋轉不變性的角點檢測和描述算法，與其他的特征檢測與描述算法（SIFT，SURF等）相比，由于其采用二進制描述子以及Hamming距離匹配，使運算速度以及內存占用量有了明顯改善。

本文首先對BRISK 中較為耗時的角點特征描述子建立算法進行改進，在提出采樣點對選擇策略后，不對BRISK算法中主方向確定，旋轉，再采樣的一系列過程進行計算，直接生成二進制串描述子；然后，在特征點匹配階段，提出兩步位操作特征匹配算法，為了加快算法執(zhí)行速度，使用了部分匹配及檢測漢明重量閾值的方法。實驗結果表明，較原有的BRISK 算法，該改進方法具有更快的運算速度，更加滿足嵌入式實時系統(tǒng)要求。

2 BRISK 算法

2.1 角點特征提取

BRISK 采用由Mair等人提出的AGAST 角點探測算法來提取角點特征。AGAST 算法又是對FAST（features from accelerated segment test）特征點檢測算法的擴展，進一步提高了其運行速度。為此，本小節(jié)在分析FAST 的基礎上，討論其優(yōu)缺點進而引出BRISK 對其改進之處。

FAST 特征檢測算法來源于Corner的定義，這個定義基于特征點周圍的圖像灰度值。對于灰度圖像來說，F(xiàn)AST檢測候選特征點為圓心的離散化Breaenham 圓周上的像素值，如果候選點周圍領域內有足夠多的像素點與該候選點的灰度值差別夠大（足夠“亮”或足夠“暗”），則認為該候選點為一個特征點［8］，如式（1）所示。

式中，x取值離散化Breaenham 圓周上的像素點，p為圓心點即候選角點，Ⅰ（x）為該像素點的灰度值，Ⅰ（p）為圓心像素點的灰度值，εd為給定的閾值。通過上式，可以求出圓周上滿足式（1）的像素點個數(shù)N，當N大于某一閾值時，就可以判斷該候選點為角點。為了獲得更快的結果，還采用了額外的加速辦法。從上面的分析可以看出，F(xiàn)AST 算法只利用周圍像素比較的信息就可以得到特征點，運算簡單，高效，實時性好。但顯而易見的，F(xiàn)AST 也存在不可避免的缺點，包括：對噪聲敏感，不具備旋轉不變性以及不具備尺度不變性。

因此，為了去除噪聲影響，BRISK 采用不同尺度高斯平滑去掉部分噪聲干擾，通過使用FAST 值（FAST Score）作為度量局部最大性的指標，將點灰度測試轉變?yōu)榫植繀^(qū)域最值比較；為了具有尺度不變性，采用了多尺度AGAST 算法，在多尺度空間上，以FAST 值（FAST Score）作為顯著性指標，尋找最值；為了適應旋轉不變性，在描述子建立過程中，利用長距離點對的梯度累加估計角點主方向，并旋轉角度。下面簡單敘述BRISK 尺度空間關鍵點檢測與描述子建立的基本思想。

2.2 尺度空間關鍵點檢測

與其他具有尺度不變性的特征算法相同，BRISK 也是從構建尺度空間金字塔開始的。尺度空間金字塔由n層（octave）ci以及n-1個中間層（inter-octave）di（i＝1，2…）構成，中間層位于相鄰兩層之間，與SIFT 算法相同，文獻［5］中n＝4。每一層從原始圖像（對應于c0）開始由上一層0.5倍下采樣得到，每一個中間層di位于層ci和層ci＋1之間。第一個中間層d0通過對原始圖像c0進行1.5倍下采樣，其他的中間層則是對上一個中間層進行0.5下采樣得到。

關鍵點檢測主要通過以下兩步來實現(xiàn)。首先，具有相同閾值T的FAST 算子應用于每一層以及每一中間層，用于識別潛在的感興趣區(qū)域。第二步，對這些潛在區(qū)域中的點在尺度空間進行非極大值抑制：1）在同一層待檢測點FAST 值必須大于與它相鄰的其他八個點；2）上一層和下一層的其他所有點的FAST 值都必須要低于該點的FAST值。滿足這兩個條件的點稱為關鍵點。對于c0層的關鍵點檢測，采用FAST-8關鍵點檢測算法。考慮到圖像顯著性不僅對于圖像是連續(xù)的，而且對于尺度維而言也是連續(xù)的。因此，對每一個檢測出的極大值進行亞像素和連續(xù)尺度校正。亞像素級校正使用最小二乘意義上的2D 二次函數(shù)擬合，而連續(xù)尺度校正使用了沿尺度坐標擬合1D 拋物線的方法。在這里不展開敘述。

2.3 BRISK 描述子建立

受BRIEF 算法的啟發(fā)，BRISK 也使用了由Calondor等人提出的二進制串［9］來描述每個特征點，其優(yōu)點是采用漢明距離來計算匹配程度，即將特征先按位異或（XOR），然后統(tǒng)計結果中1的個數(shù)，若其較小，表明匹配程度較高。正如文獻［7］證明的一樣，這種算法在運算速度上比一般的歐式距離算法有明顯優(yōu)勢。與其他二值化特征描述算法（如BRIEF，ORB等）不同，BRISK 不是利用隨機點對，而是使用幾個同心Bresenham 圓上均勻分布的點（如圖1中所示的60個點，共計59×30＝1770個點對），由長距離采樣點和短距離采樣點對分別估計特征點方向和生成二進制描述子。

圖1 BRISK 采樣點分布

BRISK 描述子采用了鄰域采樣模式，即在以特征點為中心的每個離散化Breaenham同心圓上，取均勻分布的N個點。為了減少噪聲的影響，利用標準差的高斯函數(shù)進行平滑濾波，標準差σ正比于每個同心圓上點之間的距離。考慮所有的采樣點對構成的集合，記為A，如式（2）。所有采樣點構成的點對中的一對，記為（pi，pj），平滑后的灰度值分別為Ⅰ（pi，σi）和Ⅰ（pj，σj）。定義短距離采樣點對構成的集合S以及長距離采樣點對構成的集合L如下

由于長距離采樣點對包含更多的特征點角度信息，BRISK 利用兩點之間的梯度g（pi，pj）公式（4），通過計算其總體模式方向為（5），旋轉角度θ＝arctan2 （gy，gx）然后再次 采 樣。設Ⅰ（Piθ，σi），Ⅰ（Pθj，σj）為旋轉并高斯平滑后的采樣點灰度值，通過短距采樣點對按照式（6）就生成了二進制描述子。

3 改進的BRISK 算法

3.1 改進原則

通過上面分析，BRISK 算法建立描述子過程涉及到點對選擇，主方向確定，采樣區(qū)域旋轉，重采樣等一系列階段，所需時間較多。時間主要花費在如下兩個階段：一是描述子生成時，由于在待測特征點周圍使用了較多的采樣點（60個），造成采樣點對數(shù)量較大，且相關性會比較大，從而降低描述子的判別性。通過降低采樣點數(shù)，并優(yōu)化點對選購策略是減少點對數(shù)量，降低相關性，提高算法速度的有效方法；二是為了滿足旋轉不變，通過遠距離采樣點對梯度和來確定主方向，然后又將特征點旋轉，花費了大量的運算時間。實際上，依據(jù)主模式方向角度并旋轉來實現(xiàn)旋轉不變性，在特定場合（如連續(xù)圖像序列）是不必要或是精度要求較低的。另外，Calonder在文獻［9］中也指出，角度方向的檢測過程還會減低后續(xù)圖像識別過程中的識別率。同時，在實際的嵌入式運行環(huán)境中，一般設備，如便攜電子設備（手機、平板電腦等）或是軍用設備上，均可以通過其他傳感器獲得視點變化帶來的特征方向角度信息。為此，本文在生成描述子的同時，只根據(jù)特征點周圍距離較遠的點來生成粗略的角度信息。

3.2 特征描述子建立

3.2.1 點對選擇策略

文獻［10］中FREAK 算法模擬人眼功能，利用不同標準差高斯函數(shù)構建平滑重疊區(qū)域，中間密集，四周稀疏，模擬人眼視網膜細胞的分布，減少采樣點數(shù)量，進而減少用于建立特征描述子的點對數(shù)量。由BRISK 的60 個采樣點（59×30＝1770對）變成43個采樣點（43×21＝903對）。在提高速度的同時，內存占用量也大大降低。本文也采用其定義的“視網膜”采樣區(qū)定義的43個采樣點，如圖2。

圖2 FREAK 采樣區(qū)域

點對選擇策略上，BRISK 將所有屬于短距離采樣點對均進行了計算，進而生成二進制串，帶來的問題是采樣點對具有較高相關性。為此，在ORB 算法中，離線下計算測試數(shù)據(jù)，利用小相關性（均值0.5）的方法得到點對選擇策略。按照上面思路，對測試圖像中的采樣點，首先構建二維矩陣，矩陣每一行為某點遍歷其他所有采樣點形成的二進制描述子；然后考慮該矩陣的每一列，只有其均值在0.5附近，表明該列的0，1分布數(shù)量較為相同，該采樣點對相關性低。據(jù)此，按照均值排序，選擇相關性較低的點對組成。最終，選擇了排序后相關性較小的前128個點對。

3.2.2 雙二進制串描述子

雙二進制串描述子指的是特征點幅度和角度二進制描述子。在尺度空間關鍵點檢測后，得到關鍵點坐標，然后利用FREAK 使用的高斯函數(shù)，對“視網膜”采樣區(qū)進行平滑，再選擇上述離線確定出的128個點對，不經過主模式確定及旋轉過程，直接按照式（7）生成128維特征點二進制描述子，其中，Ⅰ（Pi，σi），Ⅰ（Pj，σj）為高斯平滑后的采樣點灰度值，A128為128個點對構成集合。由于該描述子反映的是特征角點周圍采樣區(qū)域的灰度情況，稱它為特征點幅度二進制描述子。

通過上面方法生成的特征點二進制描述子中，較遠距離采樣點對數(shù)量無法確定，導致其中含有的特征點角度信息不明顯，如果據(jù)此通過下面介紹的循環(huán)移位指令直接模擬角度旋轉，并進行特征點匹配，有可能造成角度信息匱乏使誤配較高。為此，本文在采樣區(qū)高斯平滑后，于關鍵點周圍64個采樣點中，選取距離較遠的點，同關鍵點組成點對，比較灰度生成特征點角度二進制描述子。這里，以順時針方向，按照距離中心位置遠近，從遠至近，從關鍵點正上方開始，順時針依次提取18 個采樣點。圖3中為了直觀顯示，提取點位于不同半徑Bresenham 黑色圓點，高斯平滑區(qū)域用不同顏色表示。采樣點加上關鍵點共19點，形成點對規(guī)模為19×9＝171，同樣按照上文描述方法，離線找到相關性較小的128對點，按照式（8）生成128位二進制角度信息數(shù)據(jù)，其中Ⅰ（P0，σ0）為關鍵點（圖3中心點）平滑后的灰度值。

圖3 計算角度二進制描述子所用的采樣區(qū)域

3.3 特征匹配算法

3.3.1 兩步位操作特征匹配算法

通過上面建立的雙二進制串描述子，設待匹配兩個特征點（Pa，Pb）的特征點幅度和角度二進制描述子分別為

本文建立的兩步位操作特征匹配算法Two Step Bits Operation Matching（TSBOM）。按照時間先后的兩步驟是指旋轉角度匹配位操作與特征幅值匹配位操作。其核心是在考慮尺寸變換基礎上，考慮到采樣點均勻分布在同心Bresenham 圓上，將角度二進制描述子按位循環(huán)位移來模擬角度旋轉。具體來說，對于角度描述子，共需移位128次，每循環(huán)移位后，計算兩個特征點角度漢明距離，找到最匹配（即最小距離）位移操作位數(shù)（即旋轉角度信息）M，然后移動幅度描述子M次，再完成兩個特征點幅值匹配工作。如式（11），（12）所示，其中函數(shù)Fi（）表示對二進制串循環(huán)左移i次，?為按位“異或”操作。

3.3.2 優(yōu)化方法

1）漢明重量閾值

若兩幅圖像中，兩個特征點為匹配點，不論如何按位“移位”（旋轉），不考慮噪聲干擾，在一定誤差情況下，二者上述兩種描述子中1的個數(shù)相近，否則可以判定不為匹配點。漢明重量是字符串中非零的元素個數(shù)，對于二進制字符串，是指其中1的個數(shù)，設統(tǒng)計字符串中漢明重量的函數(shù)為FHWeight（）。設置差異度函數(shù)為的定義按照式（13）），若此值大于設定的閾值（本文為7），則兩特征點不為匹配點，不需進行如下的移位，再匹配等指令，降低了運算量。

2）部分描述子匹配

TSBOM 算法含有多位二進制運算，能否只比較256位中的部分，來剔除大量待匹配點，進而降低位運算總次數(shù)，有效提高算法運算效率？其實，按照提取策略，提取順序靠前的點對，相關性最小，最具有辨別力，其對應雙二進制串描述子的前幾位。為此，對每個待匹配特征點，預處理128位幅值描述子的前幾位，可以剔除大量的待匹配點，達到加速目的。大多數(shù)CPU，一個指令周期就能完成16位的二進制操作。由此，使用幅值描述子的前16位，作為“預先”匹配描述子。

4 實驗結果及分析

實驗程序使用最新公布的OPenCV 2.4版本，實驗硬件平臺為Intel Pentium E5300，2G RAM，開發(fā)環(huán)境使用Visual Studio 2010，測試的圖像來自于Computer Vision Laboratory圖像測試數(shù)據(jù)庫（http：／／www.robots.ox.ac.uk／～vgg／research／affine／）。將SIFT，SURF，BRISK 及本文算法速度進行了對比，使用典型的castle，fountain以及herzjesu圖像庫中的兩幅圖像，統(tǒng)一進行縮放，計算平均耗時，結果如表1所示。由于BRISK 與本文算法均使用了尺度空間關鍵點特征點檢測算法，因此，檢測的特征點數(shù)量以及檢測耗時均較為相近，而FAST 算法只利用周圍像素比較的信息就可以得到特征點，運算簡單，高效，比SIFT 和SURF在速度上有了大幅提高。在描述子生成階段，與SIFT 或SURF 不同，BRISK 與本文算法只是利用點對選擇策略，通過比較高斯平滑后的灰度值，速度也有明顯提升。而本文算法，由于省掉了原BRISK 算法中主方向計算，旋轉，再采樣的一系列過程，直接生成二進制串描述子，速度提升將近一倍。在匹配階段，BRISK 與本文算法均使用二進制漢明距離，通過位操作完成匹配，較SIFT 以及SURF速度快。在匹配階段，本文算法由于涉及到兩步位操作，執(zhí)行速度有所降低，但使用了改進的加速算法后，通過部分匹配及檢測漢明重量閾值的預先處理過程，剔除了大量的非匹配點，提高了執(zhí)行效率，與BRISK 匹配速度基本一致。最終，由本文算法匹配的圖像如圖4所示。總體耗時水平上，本文算法更具速度優(yōu)勢，如表1所示。

表1 算法效率對照表

5 結語

本文改進了BRISK 中較為耗時的角點特征描述子生成算法，提出了采樣點對選擇策略和幅值-旋轉兩級描述子建立方法；另外，在特征點匹配階段，提出兩步位操作特征匹配算法，并通過部分匹配及檢測漢明重量閾值的方式進一步加快算法執(zhí)行速度。實驗結果表明，較原有的BRISK算法，該改進方法由于剔除了描述子建立階段的主模式確定及旋轉過程，因此具有更快的運算速度，更加滿足嵌入式實時系統(tǒng)要求。

［1］孫浩，王程，王潤生.局部不變特征綜述［J］.中國圖象圖形學報，2011，16（1）：141-151.

［2］章為川，程冬，朱磊.基于各向異性高斯核的多尺度角點檢測［J］.電子測量與儀器學報，2012，26（1）：37-43.

［3］馬芳芳，徐天樂.圖像特征提取算法仿真研究［J］.計算機仿真，2012，29（8）：227-230.

［4］Mikolajczyk，schmid.Scale ＆affine Invariant Interest Point Detectors［J］.International Journal of Computer Vision，60（1），2004：63-86.

［5］H.Bay，T.Tuytelaars，and L.Van Gool.SURF：Speeded up robust features［C］／／In Proceedings of the European Conference on Computer Vision（ECCV），2006：1113-1126.

［6］Ethan Rublee，Vincent Rabaud，Kurt Konolige，Gary R.Bradski：ORB：An efficient alternative to SIFT or SURF［C］／／In Proceedings of the IEEE International Conference on Computer Vision（ICCV），2011：318-327.

［7］Stefan Leutenegger，Margarita Chli and Roland Siegwart，BRISK：Binary Robust Invariant Scalable Keypoints［C］／／In Proceedings of the IEEE International Conference on Computer Vision（ICCV），2011：269-279.

［8］E.Rosten and T.Drummond.Machine learning for high speed corner detection［C］／／In Proceedings of the European Conference on Computer Vision（ECCV），2006：412-429.

［9］M Calonder，V Lepetit，C Strecha，P Fua.BRIEF：Binary Robust Independent Elementary Features［C］／／In Proceedings of the European Conference on Computer Vision（ECCV），2010：812-826.

［10］A.Alahi，R.Ortiz，P.Vandergheynst.FREAK：Fast Retina Keypoint［C］／／In IEEE Conference on Computer Vision and Pattern Recognition（CVPR），2012：263-286.