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

王海羅，汪 渤

(北京理工大學(xué)自動(dòng)化學(xué)院，北京100081)

圖像匹配是通過一定的匹配算法在兩幅或多幅影像之間識(shí)別同名點(diǎn)的過程，主要分為以灰度為基礎(chǔ)的匹配和以特征為基礎(chǔ)的匹配?；谔卣鞯钠ヅ渌惴ū粡V泛應(yīng)用于計(jì)算機(jī)視覺領(lǐng)域，例如圖像描述、目標(biāo)識(shí)別與匹配，3D景象重建和運(yùn)動(dòng)跟蹤［1］，都依賴于穩(wěn)定的、有代表性的圖像特征。特征匹配的方法不但減少了匹配過程的計(jì)算量，而且對(duì)位置的變化比較敏感，可提高匹配的精確程度;同時(shí)，特征點(diǎn)的提取過程可減少噪聲的影響，對(duì)灰度變化，圖像形變以及遮擋等都有較好的適應(yīng)能力［2］。

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

筆者在結(jié)合BRISK特征描述算法的基礎(chǔ)上，對(duì)其進(jìn)行了改進(jìn)。實(shí)驗(yàn)證明改進(jìn)后的算法有很強(qiáng)的魯棒性，與SIFT算法［9］相比，在尺度、旋轉(zhuǎn)不變性以及強(qiáng)抗噪性等方面都能到達(dá)相當(dāng)?shù)男阅埽趯?shí)時(shí)性方面，該算法要明顯優(yōu)于SIFT算法，運(yùn)行速度提升近5倍。

1 BRISK特征匹配算法

1.1 特征點(diǎn)檢測(cè)

特征點(diǎn)檢測(cè)是特征匹配算法的前提，為使特征點(diǎn)具有尺度不變性，該算法在不同尺度中對(duì)特征點(diǎn)進(jìn)行檢測(cè)。

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

在每一層和夾層圖像上在同一閾值T下采用FAST－9進(jìn)行特征點(diǎn)檢測(cè)。

1.2 特征點(diǎn)描述

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

圖1 尺度空間特征點(diǎn)檢測(cè)Fig.1 Scale-space key-point detection

圖2 特征點(diǎn)采樣模式Fig.2 Sampling pattern of key-point

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

設(shè)F為所有采樣點(diǎn)對(duì)集合，fi，fj為采樣模式中任意兩個(gè)采樣點(diǎn)，則

定義集合短距離對(duì)集S和長距離對(duì)集L:

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

設(shè)

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

特征點(diǎn)的描述子dk可由下式得到:

其中b為描述子的任一二進(jìn)制數(shù)位;r為特征點(diǎn)的方向。最終形成128位的二進(jìn)制字符串向量作為該特征點(diǎn)的描述子。

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

2 算法改進(jìn)

2.1 特征點(diǎn)選取

由于FAST特征點(diǎn)檢測(cè)方法具有速度快的優(yōu)點(diǎn)，所以Brisk算法采用FAST特征點(diǎn)檢測(cè)方法在尺度空間進(jìn)行特征點(diǎn)檢測(cè)。但是FAST特征點(diǎn)檢測(cè)算法對(duì)圖像邊緣有強(qiáng)烈響應(yīng)，所以在圖像紋理突出的區(qū)域會(huì)影響特征點(diǎn)的檢測(cè)。

為保證特征點(diǎn)的精確，改用Harris角點(diǎn)檢驗(yàn)方法。通過較低閾值獲取到足夠多的FAST特征點(diǎn);按FAST特征點(diǎn)的 Harris角點(diǎn)響應(yīng)大小對(duì)FAST角點(diǎn)進(jìn)行排序，根據(jù)排序選取Harris響應(yīng)值大的前N個(gè)點(diǎn)作為實(shí)驗(yàn)用的特征點(diǎn)。

2.2 特征點(diǎn)方向

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

定義一個(gè)圖像塊的矩為:

根據(jù)矩的定義，可確定圖像塊的形心:

這樣從角點(diǎn)中心O道形心C可構(gòu)建向量OC，即可作為此圖像塊的方向，而圖像塊的方向大小為

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

3 實(shí)驗(yàn)結(jié)果

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

3.1 尺度不變性

尺度的變化是景象匹配過程中所必須要面對(duì)的問題，如果不能保證算法的尺度不變性，最終會(huì)導(dǎo)致匹配算法的失敗。所以算法對(duì)尺度變換甚至劇烈變換的適應(yīng)性越強(qiáng)，匹配的效果就越好。該算法針對(duì)尺度不變性的實(shí)驗(yàn)結(jié)果如圖3所示。

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

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

3.2 旋轉(zhuǎn)不變性

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

圖4 旋轉(zhuǎn)15°的圖像匹配結(jié)果Fig.4 M atching results of images in 15 degree rotation

圖4中左邊依然為512×512像素的參考圖，右圖為順時(shí)針旋轉(zhuǎn)了15°的圖像，并且在旋轉(zhuǎn)條件下，仍保持縮小2.13倍的圖像尺度。實(shí)驗(yàn)結(jié)果顯示出很好的匹配效果，匹配率為35.14%。這是因?yàn)樵谠撍惴ㄖ袨槊恳粋€(gè)特征點(diǎn)分配了方向，這個(gè)方向值是每一個(gè)特征點(diǎn)所特有的，且互不相同，這樣就可把不同的特征點(diǎn)描述子進(jìn)行區(qū)分，所以在匹配過程中，就會(huì)減少很多的誤匹配，以保證較高的匹配率。

圖5是圖像縮放后順時(shí)針旋轉(zhuǎn)30°的特征點(diǎn)匹配效果圖，匹配率為33.64%。該實(shí)驗(yàn)充分證明該算法對(duì)于圖像旋轉(zhuǎn)和縮放都有很強(qiáng)的魯棒性，這對(duì)于景象匹配算法的要求來說是特別關(guān)鍵的。

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

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

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

4 結(jié)論

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

［1］曾慧，穆志純.一種魯棒的圖像局部特征區(qū)域的描述方法［J］.自動(dòng)化學(xué)報(bào)，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］.北京:國防工業(yè)出版社，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.