王 穎 王愛民

(東南大學(xué)儀器科學(xué)與工程學(xué)院，南京 210096)

一種魯棒的二進制圖像特征點描述子

王 穎 王愛民

(東南大學(xué)儀器科學(xué)與工程學(xué)院，南京 210096)

為了提高特征點匹配的速度，采用二進制方法生成特征點描述，并對描述子進行了尺度和旋轉(zhuǎn)適應(yīng)性改進.使用特征點鄰域小塊中隨機點的強度對比生成描述，描述子的相似度以Hamming距離度量，以二進制運算提高算法的時間性能.為了檢驗算法在視角、旋轉(zhuǎn)及尺度變化時的性能，采用Wall和Graffiti圖像集及相應(yīng)的旋轉(zhuǎn)和尺度變換圖像集對算法進行測試，得到該算法在各圖像集上的匹配準(zhǔn)確率，并與SURF算法得到的結(jié)果進行比較.結(jié)果表明，在2幅圖像間進行特征點匹配時，該算法的特征點描述生成時間和匹配時間分別為1 043.67和4 313.36 ms，而使用SURF算法時的相應(yīng)時間分別為3 950.34和9 951.03 ms，說明該算法的時間特性明顯優(yōu)于SURF算法.此外，在絕大多數(shù)測試集上，該算法的匹配準(zhǔn)確率明顯高于SURF算法.

特征點;特征匹配;SURF算法

隨著算法精度的不斷提高，特征點提取與匹配技術(shù)越來越多地應(yīng)用于圖像拼接、三維場景重建以及物體的檢測、識別、跟蹤等領(lǐng)域.部分應(yīng)用場景(如機器人即時定位與地圖構(gòu)建、增強現(xiàn)實的配準(zhǔn)和跟蹤等)對實時處理的要求較高，因此需要在保證準(zhǔn)確性的情況下，盡可能提高特征點提取與匹配算法的運行速度.目前，應(yīng)用范圍較廣的此類算法包括尺度不變特征變換SIFT(scale-invariant fea-ture transform)算法［1-2］和使用近似 Hessian提取算子的 SURF(speeded up robust feature)算法［3］等.

SIFT算法使用差分高斯(difference of Gauss，DoG)近似拉普拉斯高斯(Laplace of Gauss，LoG)提取特征點，采用梯度直方圖形式的特征點描述子.該算法匹配精度高、魯棒性好，能處理2幅圖像大視角變化時的匹配問題，其缺點在于特征點提取與匹配時間過長、難以實現(xiàn)實時處理.Mikolajczyk等［4］將SIFT算法中的特征點描述變換到極坐標(biāo)下，從而提高了算法的性能.Ke等［5］對SIFT算法的特征點描述子進行主成分分析，提出了PCA-SIFT算法.Bay等［3］基于簡化思想提出了SURF算法，以Haar小波近似Hessian算子，并使用積分圖像(integral image)縮短了計算時間.SURF算法能較好地平衡算法速度和精度，應(yīng)用較為廣泛，但仍無法滿足實時處理的要求.以上各種特征描述算法都需要生成高維的特征描述子，描述的生成和特征點的匹配較為費時，成為提高算法速度的瓶頸.

本文提出了一種能夠快速生成描述、實現(xiàn)匹配的二進制特征點描述子，并對算子進行改進，使其適應(yīng)尺度和旋轉(zhuǎn)變換.

1 二進制特征點描述子

1.1 相關(guān)原理

用二進制數(shù)據(jù)描述圖像特征點的思想來源于Lepetit等［6-7］的相關(guān)研究.其基本思想是將特征點的匹配看作分類問題，構(gòu)建隨機分類樹，通過學(xué)習(xí)來實現(xiàn)特征點的識別.圖1為隨機分類樹及其改進結(jié)構(gòu)的示意圖.隨機分類樹由根節(jié)點及其下的各個節(jié)點組成，每個節(jié)點包含1個分類測試ti，葉節(jié)點用于存儲訓(xùn)練得到的后驗概率.Ozuysal等［8］對隨機分類樹的結(jié)構(gòu)進行了調(diào)整，在分類樹的每一層中采用相同的測試，并去掉層級結(jié)構(gòu).在此基礎(chǔ)上，Calonder等［9］進一步去除了分類器和訓(xùn)練過程，僅保留測試結(jié)果作為二進制特征點描述子.

圖1 隨機樹結(jié)構(gòu)的改進

1.2 定義

二進制特征點描述子是一種二進制向量，可通過比較特征點鄰域小塊中隨機點的強度得到，每1個二進制位記錄1個比較結(jié)果.

式中，I(u)為經(jīng)過平滑的圖像在點u=(x，y)T處的強度.選擇n組不同位置的點對(u，v)，比較每一組點的像素強度I(u)和I(v)，將結(jié)果保存為n位二進制數(shù)據(jù).由此可將二進制特征點描述子定義為如下的n維二進制數(shù)據(jù)串:

在式(2)中，測試點ui和vi的坐標(biāo)服從二維高斯分布;n的選擇取決于實際應(yīng)用的要求，為了平衡精度和時間，通常取128，256或512.

在二進制特征點描述中，由于僅對像素強度進行比較，得到的結(jié)果受噪聲影響較為嚴(yán)重.需要先對圖像進行平滑處理，提高特征點描述的穩(wěn)定性與可重復(fù)性.

二進制特征點描述子的匹配使用Hamming距離度量.具體做法如下:將2個二進制數(shù)據(jù)按位異或，根據(jù)結(jié)果中1數(shù)量的多寡判定特征點描述子是否匹配.

2 適應(yīng)性改進

2.1 尺度不變性

Lindeberg［10］于1998年提出了尺度空間理論，并在多尺度中對圖像進行處理，其方法類似于生物視覺中由粗到精(coarse to fine)的處理方式.尺度空間理論解決了尺度變化時圖像特征點的提取問題.將若干幅經(jīng)過不同程度高斯平滑的圖像構(gòu)成尺度空間，在尺度空間中篩選符合條件的特征點，并定義該特征點所在尺度為特征尺度.其具體過程如下:首先將圖像I(x，y)與高斯函數(shù)卷積，即

式中，L(x，y，t)為得到的平滑圖像;G(x，y，t)為二維高斯函數(shù)，其表達(dá)式為

式中，t和σ分別為高斯函數(shù)的標(biāo)準(zhǔn)差和方差.將圖像與方差為σi的高斯函數(shù)卷積，并用結(jié)果圖像建立尺度空間.

然后，在多尺度下進行圖像特征點判別，其判別法則如下:

對坡腳進行垂直切坡處理后，斜馬道寬度拓展為4.85 m，即上壩道路初期壩下游壩面段實際寬度達(dá)到4.85 m，增強了道路的安全通行條件。

式中，F(xiàn)為判別函數(shù);Th和Tl分別為響應(yīng)上、下限;MW為特征點M在尺度空間上鄰域W中的一點.

在二進制特征點描述中引入尺度s，s與σ成正比.根據(jù)s調(diào)整測試點的分布，從而解決圖像尺度變化下的特征點描述問題.

2.2 旋轉(zhuǎn)不變性

向特征點賦予特征方向是實現(xiàn)旋轉(zhuǎn)不變性的一種途徑［3］.本文通過在局部區(qū)域計算Haar小波響應(yīng)得到特征點的特征方向(見圖2).該方法的具體計算過程如下:首先，在圖像中建立一個以特征點為中心，半徑為6s的圓形區(qū)域，在該區(qū)域內(nèi)計算邊長為4s的Haar小波響應(yīng)，并賦予其參數(shù)為2s的高斯權(quán)值;然后，建立一個圓心角為π/3的扇形滑動窗，并統(tǒng)計x，y方向上Haar小波響應(yīng)的矢量和;最后，選擇矢量長度最大的方向為特征方向，其表達(dá)式為

式中，weight(x，y)表示權(quán)值;wh(x，y)表示方向為h時的窗函數(shù);dx，dy分別表示x，y方向上的Haar小波響應(yīng).

圖2 特征方向示意圖

得到特征方向后，對生成測試點的坐標(biāo)進行插值，即可使圖像發(fā)生旋轉(zhuǎn)時得到的特征點描述子固定不變.

3 測試數(shù)據(jù)及算法評價

為了對算法的性能做出準(zhǔn)確評估，采用標(biāo)準(zhǔn)圖像庫進行測試.這里選取文獻(xiàn)［4］中的2組視角變化的測試圖像集Wall和Graffiti圖像集(見圖3).每組測試圖像集中包含6幅圖像，以第1幅為基準(zhǔn)，其余每幅圖像的視角在20°～60°之間變化.這2組測試圖像集代表2種不同的場景類型.其中，Graffiti圖像集為平面繪圖，含有明顯的線條界限;Wall圖像集為粗糙磚砌墻面照片，包含了重復(fù)的紋理.已知每幅圖像到基準(zhǔn)圖像的單應(yīng)性矩陣，通過點的坐標(biāo)換算即可驗證特征點的匹配是否正確.

圖3 測試圖像集中的基準(zhǔn)圖像

為了分別研究算法在旋轉(zhuǎn)和尺度變換下的工作特性，對基準(zhǔn)圖像(即Wall，Graffiti圖像集中的第1幅圖像)進行旋轉(zhuǎn)和縮放，生成Wall和Graffiti的旋轉(zhuǎn)、縮放測試圖像集.

在算法評價方面，主要分析算法的匹配準(zhǔn)確率，其表達(dá)式為

式中，N為返回的匹配點總數(shù);R為正確匹配點數(shù)量.

4 實驗與結(jié)果

4.1 實驗設(shè)置

在Wall圖像集和Graffiti圖像集上分別對本文算法和SURF算法進行測試.特征點提取采用快速Hessian算子.特征點提取及SURF算法的特征描述部分使用了計算機視覺類庫 OpenCV［11］(open source computer vision)中的相關(guān)函數(shù).實驗中，快速Hessian算子的參數(shù)設(shè)置如下:Hessian閾值為200，階數(shù)為3，每階為4層.在尺度圖像集上進行測試時，由于圖像較大，將Hessian閾值設(shè)定為1 000.SURF算法的特征描述子為64維.二進制描述子為256位，采用的特征點鄰域小塊為48×48像素.編程語言為C++.

特征點匹配采取最近鄰策略:若2個特征點描述子的距離互為最短，則判定為匹配點.

4.2 實驗結(jié)果與分析

為檢驗算法運行效率，考察了2種算法在2幅圖像間進行特征點匹配的處理時間.實驗中，基準(zhǔn)圖像為Wall圖像集中的第1幅圖像，其大小為1 000×700像素，提取的特征點數(shù)量為7 366.匹配對象為Wall圖像集中的第2幅圖像，特征點數(shù)量為5 993.采用雙核處理器 PC，CPU主頻為2.20 GHz.實驗結(jié)果表明:本文算法和SURF算法的描述生成時間分別為1 043.67和3 950.34 ms，特征點匹配時間分別為4 313.36和9 951.03 ms.

圖4為2種算法在Wall和Graffiti視角變換圖像集上的匹配準(zhǔn)確率.由圖可知，在2組視角變換圖像集上，采用改進二進制描述子時匹配準(zhǔn)確率高于SURF算法.此外，利用同一算法時Wall圖像集上的匹配準(zhǔn)確率高于Graffiti圖像集上的匹配準(zhǔn)確率，說明這2種算法更適用于紋理豐富的圖像集.

圖4 不同視角時的測試結(jié)果

圖5和圖6分別為2種算法在Wall和Graffiti尺度變換和旋轉(zhuǎn)變換圖像集上的匹配準(zhǔn)確率.由圖5可知，尺度不變性測試在2個圖像集上的結(jié)果幾乎沒有差別，表明單純尺度變化下圖像的類型對實驗結(jié)果沒有影響，本文算法的特征點匹配準(zhǔn)確率仍然高于SURF算法.在旋轉(zhuǎn)測試的結(jié)果中，2種算法得到的結(jié)果無明顯差別(見圖6).

綜上所述，在大多數(shù)情況下本文算法的匹配準(zhǔn)確率明顯高于SURF算法.從算法的運行時間來看，本文算法的特征點描述子生成時間約為SURF算法的1/4，匹配時間約為SURF算法的1/2，說明本文算法具有明顯的速度優(yōu)勢.

圖5 不同尺度時的測試結(jié)果

圖6 不同旋轉(zhuǎn)角度時的測試結(jié)果

5 結(jié)語

本文提出了一種魯棒的二進制圖像特征點描述子.實驗結(jié)果表明，在各類圖像上使用該特征點描述子進行特征點匹配時的匹配準(zhǔn)確率精度均高于SURF算法.與梯度直方圖類的特征點描述子相比，二進制特征點描述子占用內(nèi)存少，SURF算法的64維特征點描述子需要256 byte的存儲空間，而256位的二進制描述子僅占用32 byte的存儲空間.此外，二進制特征點描述子的生成與匹配速度較快.因此，本文算法適用于手機等存儲空間較小、計算能力受限制的硬件平臺以及增強現(xiàn)實等一些實時性要求較高的應(yīng)用場合.與隨機樹等機器學(xué)習(xí)類的算法相比，本文算法不需要學(xué)習(xí)訓(xùn)練階段，適于需要添加新特征點的SLAM等應(yīng)用場景.下一步的工作重點在于結(jié)合快速特征點提取，進一步擴大算法的速度優(yōu)勢.

［1］ Lowe D G.Object recognition from local scale-invariant features［C］//Proceedings of the7th IEEE International Conference on Computer Vision.Los Alamitos，USA，1999:1150-1157.

［2］ Lowe D G.Distinctive image features from scale-invariant keypoints［J］.International Journal of Computer Vision，2004，60(2):91-110.

［3］ Bay Herbert，Tuytelaars Tinne，Van Gool Lue.SURF:speeded up robust features［C］//Proceedings of the9th European Conference on Computer Vision.Graz，Austria，2006:404-417.

［4］Mikolajczyk K，Schmid C.A performance evaluation of local descriptors［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2005，27(10):1615-1630.

［5］ Ke Y，Sukthankar R.PCA-SIFT:a more distinctive representation for local image descriptors［C］//Proceedings of the2004IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington DC，USA，2004:506-513.

［6］ Lepetit V，Pilet J，F(xiàn)ua P.Point matching as a classification problem for fast and robust object pose estimation［C］//Proceedings of the2004IEEE Computer Society Conference on Computer Vision and Pattern Recognition.Washington DC，USA，2004:244-250.

［7］ Lepetit V，F(xiàn)ua P.Keypoint recognition using randomized trees［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2006，28(9):1465-1479.

［8］Ozuysal M，Calonder M，Lepetit V，et al.Fast keypoint recognition using random ferns［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2010，32(3):448-461.

［9］ Calonder M，Lepetit V，Strecha C，et al.BRIEF:binary robust independent elementary features［C］//Proceedings of the11th European Conference on Computer Vision.Berlin，Germany，2010:778-792.

［10］ Lindeberg T.Feature detection with automatic scale selection［J］.International Journal of Computer Vision，1998，30(2):79-116.

［11］ Willow Garage.OpenCV［EB/OL］.(2010-04-10)［2010-06-03］.http://opencv.willowgarage.com.

Robust binary feature point descriptor

Wang Ying Wang Aimin
(School of Instrument Science and Engineering，Southeast University，Nanjing 210096，China)

In order to improve the speed of feature point matching，a binary method is used to generate feature point description，and the descriptor’s adaptability to different scales and rotations is improved.The descriptor is computed using intensity difference tests.The descriptor similarity is evaluated by using Hamming distance，and the time performance of the algorithm is improved by binary operation.The Wall and Graffiti image sets as well as their transformed image sets are used to test the performance of the proposed algorithm for the different perspectives，rotations and scales.The matching accuracies on each image set are obtained.The comparison results of the proposed algorithm and the speeded up robust feature(SURF)algorithm show that during the feature point matching between the two images，the construction time and the matching time of the descriptors of the proposed algorithm are 1 043.67 and 4 313.36 ms，respectively，while the corresponding data of the SURF algorithm are 3 950.34 and 9 951.03 ms，indicating that the time characteristics of the proposed algorithm are better than those of the SURF algorithm.In addition，on most image sets，the matching accuracy of the proposed algorithm is higher than that of the SURF algorithm.

feature point;feature matching;speeded up robust feature(SURF)algorithm

TP391.4

A

1001－0505(2012)02-0265-05

10.3969/j.issn.1001 －0505.2012.02.014

2011-08-20.

王穎(1985—)，女，博士生;王愛民(聯(lián)系人)，男，博士，教授，博士生導(dǎo)師，wangam@seu.edu.cn.

國家高技術(shù)研究發(fā)展計劃(863計劃)資助項目(2009AA01Z311).

王穎，王愛民.一種魯棒的二進制圖像特征點描述子［J］.東南大學(xué)學(xué)報:自然科學(xué)版，2012，42(2):265-269.［doi:10.3969/j.issn.1001 －0505.2012.02.014］