魯棒的新型特征提取和匹配算法

王海羅，汪 渤

(北京理工大學自動化學院，北京100081)

圖像匹配是通過一定的匹配算法在兩幅或多幅影像之間識別同名點的過程，主要分為以灰度為基礎的匹配和以特征為基礎的匹配。基于特征的匹配算法被廣泛應用于計算機視覺領域，例如圖像描述、目標識別與匹配，3D景象重建和運動跟蹤［1］，都依賴于穩定的、有代表性的圖像特征。特征匹配的方法不但減少了匹配過程的計算量，而且對位置的變化比較敏感，可提高匹配的精確程度;同時，特征點的提取過程可減少噪聲的影響，對灰度變化，圖像形變以及遮擋等都有較好的適應能力［2］。

目前基于特征描述的研究在國際上取得了許多令人矚目的成就。SIFT(Scale Invariant Feature Transform)算法［3］，是Lowe在2004年總結了現有的基于不變量技術的特征檢測算法，并提出的基于尺度空間的圖像局部特征描述算子，該算子具有很好的旋轉不變性、尺度不變性以及強的魯棒性和抗噪性。SIFT算子由于效果出眾得到了較廣泛的應用，但也因其算法復雜，計算量大，耗時長等問題使其應用受到了限制。SURF［4－5］算法可看為SIFT算法的加速版，運行速度提升了3倍。近年來，基于二進制字符串比較的新型特征匹配算法得到越來越多的關注和研究，如BRIEF［6］、BRISK［7］、ORB［8］等，由于采用了二進制字符串的存儲和運算方式，使得這些算法極大的節省了存儲空間和計算耗時，但卻以犧牲了性能為代價，尚未得到廣泛的應用。

筆者在結合BRISK特征描述算法的基礎上，對其進行了改進。實驗證明改進后的算法有很強的魯棒性，與SIFT算法［9］相比，在尺度、旋轉不變性以及強抗噪性等方面都能到達相當的性能，但在實時性方面，該算法要明顯優于SIFT算法，運行速度提升近5倍。

1 BRISK特征匹配算法

1.1 特征點檢測

特征點檢測是特征匹配算法的前提，為使特征點具有尺度不變性，該算法在不同尺度中對特征點進行檢測。

建立尺度空間金字塔，方式不同于SIFT算法中的構建方法。取此尺度空間金字塔包含n層，設為Ki，和n個夾層Ji，i={0，1，…，n－1}。取n=4。設原圖像為K0，Ki由對前一副圖像進行半采樣得到的。Ji介于Ki和Ki+1之間，J0由K0降采樣得到。采樣因子為1.5，其余Ji由J0半采樣得到。定義t為空間尺度，那么t(Ki)=2i，而t(Ji)=2i×1.5。圖1給出了尺度空間金字塔示意圖。

在每一層和夾層圖像上在同一閾值T下采用FAST－9進行特征點檢測。

1.2 特征點描述

為提高特征點的匹配效率，特征點采用二進制位串進行描述，二進制位串通過比較灰度來得到。這里使用一種同心圓采樣模式，如圖2所示。

圖1 尺度空間特征點檢測Fig.1 Scale-space key-point detection

圖2 特征點采樣模式Fig.2 Sampling pattern of key-point

中心圓圈表示一個特征點，在特征點周圍不同的半徑位置選取了60個采樣點，小圓圈代表采樣位置，大虛線圓圈代表用來平滑灰度值的高斯核σ大小，σ正比于采樣點到中心的距離。

設F為所有采樣點對集合，fi，fj為采樣模式中任意兩個采樣點，則

定義集合短距離對集S和長距離對集L:

其中▽max=9.75t;▽min=13.67t;t為特征點所在的尺度大小。特征點方向計算如下:

設

其中g(fi，fj)為梯度計算公式;σi為fi點的高斯核。則有特征點方向

特征點的描述子dk可由下式得到:

其中b為描述子的任一二進制數位;r為特征點的方向。最終形成128位的二進制字符串向量作為該特征點的描述子。

特征點描述子匹配采用Hamming距離比較方法，這種方法匹配速度快，效率高，實時性好。

2 算法改進

2.1 特征點選取

由于FAST特征點檢測方法具有速度快的優點，所以Brisk算法采用FAST特征點檢測方法在尺度空間進行特征點檢測。但是FAST特征點檢測算法對圖像邊緣有強烈響應，所以在圖像紋理突出的區域會影響特征點的檢測。

為保證特征點的精確，改用Harris角點檢驗方法。通過較低閾值獲取到足夠多的FAST特征點;按FAST特征點的 Harris角點響應大小對FAST角點進行排序，根據排序選取Harris響應值大的前N個點作為實驗用的特征點。

2.2 特征點方向

在特征點確定之后，為使得到的特征點具有旋轉不變性，需要為特征點分配方向。該算法采用一種簡單有效的方向測量方法，即灰度圖心法。

定義一個圖像塊的矩為:

根據矩的定義，可確定圖像塊的形心:

這樣從角點中心O道形心C可構建向量OC，即可作為此圖像塊的方向，而圖像塊的方向大小為

得到的圖像塊的方向即可作為特征點的方向，用于描述子的匹配過程。在計算過程中借用了矩和積分圖的計算方法，由于這兩種方法的計算過程都相對簡單，所以與原始BRISK算子通過計算圖像梯度得到長距離對集，再從長距離對集中去計算特征點方向的計算量相比，灰度圖心法更為快速有效。

3 實驗結果

算法開發基于Visual C++2008軟件和OpenCV庫，在Inter(R)Core(TM)2 duo CPU T6600@2.20 GHz 2.19 GHz，內存為2 GByt的 PC機上運行;用于實驗該算法的圖片均來自于Google earth軟件的衛星地圖。

3.1 尺度不變性

尺度的變化是景象匹配過程中所必須要面對的問題，如果不能保證算法的尺度不變性，最終會導致匹配算法的失敗。所以算法對尺度變換甚至劇烈變換的適應性越強，匹配的效果就越好。該算法針對尺度不變性的實驗結果如圖3所示。

圖3(a)中左圖像是某區域的高空俯瞰地形圖，圖像大小為512×512像素，圖3(a)中右邊為其縮小2.13倍尺度的圖像，大小為240×240像素。實驗表明，即使圖像有較大尺度變化，該算法也能得到精確的匹配結果。左圖檢測到的特征點數為420，右圖檢測到的特征點數為120，匹配點對數為68，匹配率為56.67%，共用時4 351.38 ms。圖3(b)中左邊為同一機場的低空俯瞰地形圖，圖像大小為512×512像素，圖3(b)中右圖仍為其縮小2.13倍尺寸的圖像，大小為240×240像素。實驗顯示左圖檢測到特征點數為236，右圖檢測到的特征點數為39，匹配點對數為12，匹配率為30.76%，共用時4 349.72 ms。

圖3 不同尺度圖像匹配結果Fig.3 M atching results of images in different scale

3.2 旋轉不變性

景象匹配過程中，除了要解決尺度變化的問題，還要解決的一個難題是旋轉不變性。由于攝像頭在急速下降的過程中，隨著導引頭肯定會有一定角度的旋轉，這種旋轉非常容易導致目標圖像與模板圖像無法匹配，為保證景象匹配的準確度，算法要能適應圖像的旋轉所帶來的困難。針對景象匹配算法所要求的旋轉不變性，進行了許多實驗(見圖4，圖5)。

圖4 旋轉15°的圖像匹配結果Fig.4 M atching results of images in 15 degree rotation

圖4中左邊依然為512×512像素的參考圖，右圖為順時針旋轉了15°的圖像，并且在旋轉條件下，仍保持縮小2.13倍的圖像尺度。實驗結果顯示出很好的匹配效果，匹配率為35.14%。這是因為在該算法中為每一個特征點分配了方向，這個方向值是每一個特征點所特有的，且互不相同，這樣就可把不同的特征點描述子進行區分，所以在匹配過程中，就會減少很多的誤匹配，以保證較高的匹配率。

圖5是圖像縮放后順時針旋轉30°的特征點匹配效果圖，匹配率為33.64%。該實驗充分證明該算法對于圖像旋轉和縮放都有很強的魯棒性，這對于景象匹配算法的要求來說是特別關鍵的。

為更好驗證筆者提出的景象匹配算法的性能，將其與SIFT算法在抗噪性、精確度以及實時性3個方面進行了比較，并通過多次的實驗，得出以下數據。

其中在尺度不變性實驗中的兩副小尺度圖像進行加噪處理，圖3(a)中加入方差為0.01的高斯噪聲，在圖3(b)中加入方差為0.02的乘性斑點噪聲。

由實驗結果可見，改進后的算法有很好的尺度不變性、旋轉不變性和強抗噪性。在尺度劇烈變化和高斯噪聲或者斑點噪聲干擾的情況下，依然能達到20%以上的匹配率，雖不及SIFT，但也具備了很好的抗噪性，并且在用時上要比SIFT少約14 s。當有尺度又有旋轉的情況下，該算法能到到30%以上的匹配率，和SIFT有相差不多的性能，但在時間上該算法一共執行了不到4.4 s，而SIFT需要近20 s。這充分說明了該算法在保證匹配性能的前提下，實時性要比SIFT快很多。

4 結論

針對圖像匹配算法高可靠性、高計算速度的要求，筆者給出一種快速、準確、強魯棒性的基于局部關鍵點的特征匹配算法。該算法通過建立多尺度空間，通過有效的擇優手段選取特征點，在一定程度上提高了匹配的準確度;并采用灰度圖心方法為特征點分配方向，該方法簡便而又快速;最后借助一種特殊的采樣模式形成特征描述子，具有很多優異的特性。實驗結果與分析證明了該算法的有效性，驗證了該算法的尺度不變性、旋轉不變性以及良好的抗噪性，并在實時性上有了較大的進步。

［1］曾慧，穆志純.一種魯棒的圖像局部特征區域的描述方法［J］.自動化學報，2011，37(6):17－21.

Zeng Hui，Mu Zhi－chun.Description of a robust image local feature regions［J］.Acta Automation Sinica，2011，37(6):17－21.

［2］王永明，王貴錦.圖像局部不變性特征與描述［M］.北京:國防工業出版社，2009.

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

［4］Herbert B，Tinne T.SURF:speeded up robust features［J］.Computer Vision and Image Understanding，2006，110(3):346－359.

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

［6］Michael Calonder.BRIEF:Binary robust independent elementary features［J］.Lecture Notes in Computer Science，2010，63(14):778－792.

［7］Leutenegger S.BRISK:Binary robust invariant scalable keypoints［C］//IEEE International Conference on Computer Vision.2011:2548－2555.

［8］Rublee E.ORB:An efficient alternative to SIFT or SURF［C］//IEEE International Conference on Computer Vision.2011:2564－2571.

［9］Yan Ke.PCA－SIFT:A more distinctive representation for local image descriptors［J］.Proceedings of IEEE Computer Society Conference on Computer Viesion and Pattern Recognition，2004(2):506－513.