（1.海軍航空工程學(xué)院兵器科學(xué)與技術(shù)系 煙臺 264001）（2.91055部隊(duì)6分隊(duì) 臺州 318050）

1 引言

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

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

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

2 BRISK 算法

2.1 角點(diǎn)特征提取

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

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

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

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

2.2 尺度空間關(guān)鍵點(diǎn)檢測

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

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

2.3 BRISK 描述子建立

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

圖1 BRISK 采樣點(diǎn)分布

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

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

3 改進(jìn)的BRISK 算法

3.1 改進(jìn)原則

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

3.2 特征描述子建立

3.2.1 點(diǎn)對選擇策略

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

圖2 FREAK 采樣區(qū)域

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

3.2.2 雙二進(jìn)制串描述子

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

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

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

3.3 特征匹配算法

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

通過上面建立的雙二進(jìn)制串描述子，設(shè)待匹配兩個(gè)特征點(diǎn)（Pa，Pb）的特征點(diǎn)幅度和角度二進(jìn)制描述子分別為

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

3.3.2 優(yōu)化方法

1）漢明重量閾值

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

2）部分描述子匹配

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

4 實(shí)驗(yàn)結(jié)果及分析

實(shí)驗(yàn)程序使用最新公布的OPenCV 2.4版本，實(shí)驗(yàn)硬件平臺為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 及本文算法速度進(jìn)行了對比，使用典型的castle，fountain以及herzjesu圖像庫中的兩幅圖像，統(tǒng)一進(jìn)行縮放，計(jì)算平均耗時(shí)，結(jié)果如表1所示。由于BRISK 與本文算法均使用了尺度空間關(guān)鍵點(diǎn)特征點(diǎn)檢測算法，因此，檢測的特征點(diǎn)數(shù)量以及檢測耗時(shí)均較為相近，而FAST 算法只利用周圍像素比較的信息就可以得到特征點(diǎn)，運(yùn)算簡單，高效，比SIFT 和SURF在速度上有了大幅提高。在描述子生成階段，與SIFT 或SURF 不同，BRISK 與本文算法只是利用點(diǎn)對選擇策略，通過比較高斯平滑后的灰度值，速度也有明顯提升。而本文算法，由于省掉了原BRISK 算法中主方向計(jì)算，旋轉(zhuǎn)，再采樣的一系列過程，直接生成二進(jìn)制串描述子，速度提升將近一倍。在匹配階段，BRISK 與本文算法均使用二進(jìn)制漢明距離，通過位操作完成匹配，較SIFT 以及SURF速度快。在匹配階段，本文算法由于涉及到兩步位操作，執(zhí)行速度有所降低，但使用了改進(jìn)的加速算法后，通過部分匹配及檢測漢明重量閾值的預(yù)先處理過程，剔除了大量的非匹配點(diǎn)，提高了執(zhí)行效率，與BRISK 匹配速度基本一致。最終，由本文算法匹配的圖像如圖4所示?？傮w耗時(shí)水平上，本文算法更具速度優(yōu)勢，如表1所示。

表1 算法效率對照表

5 結(jié)語

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

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

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

［3］馬芳芳，徐天樂.圖像特征提取算法仿真研究［J］.計(jì)算機(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.