基于粒子群優(yōu)化及多結(jié)構(gòu)估計(jì)的ASIFT特征提取算法

曹雪蓮，陳水利

(1．福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福建 福州 350108;2．集美大學(xué)理學(xué)院，福建 廈門 361021)

0 引言

圖像特征提取是圖像分析、模式識(shí)別以及機(jī)器視覺(jué)等領(lǐng)域的研究熱點(diǎn)．理想的圖像局部特征能表達(dá)圖像局部區(qū)域的信息，對(duì)視角變化、光照變化、尺度縮放、旋轉(zhuǎn)等情況具有不變性．局部特征的研究成果已經(jīng)被廣泛應(yīng)用于寬基線特征匹配[1]、物體識(shí)別[2]、紋理識(shí)別[3]、圖像檢索[4]、機(jī)器人定位[5]、視頻數(shù)據(jù)挖掘[6]、全景圖像拼接[7]等領(lǐng)域．

一些經(jīng)典的特征檢測(cè)子，如Harris角點(diǎn)檢測(cè)子[8]可以對(duì)圖像旋轉(zhuǎn)保持不變性，Harris－Laplace和Hessian－Laplace檢測(cè)子[9]可以對(duì)圖像旋轉(zhuǎn)和尺度縮放保持不變性．而Harris－Affine和Hessian－Affine檢測(cè)子[9]，MSER(最大穩(wěn)定極值)檢測(cè)子[10]等都是為解決仿射不變性而提出的．2005年，Mikola-jczky[11]對(duì)SIFT、GLOH、PCA－SIFT等10種不同的特征描述子從尺度縮放、視角變換、光照變化等6個(gè)方面進(jìn)行了實(shí)驗(yàn)和性能比較，結(jié)果表明，SIFT性能最好、最穩(wěn)定．2009年，Jean－Michel Morel等[12]提出了ASIFT(Affine－SIFT)算法，在SIFT算法的基礎(chǔ)上，解決了仿射不變性問(wèn)題．ASIFT算法通過(guò)離散采樣搜索圖像之間的最優(yōu)變換模型，而實(shí)際上ASIFT中兩個(gè)旋轉(zhuǎn)角度參數(shù)是連續(xù)的，通過(guò)離散采樣得到的解一般不是實(shí)際的最優(yōu)采樣角度．

雖然上述算法能夠得到大量的特征匹配點(diǎn)對(duì)，但是不可避免會(huì)存在很多錯(cuò)誤的匹配對(duì)．如何解決特征錯(cuò)配，正確估計(jì)圖像變換參數(shù)及多結(jié)構(gòu)估計(jì)是本文的重要目標(biāo)．特征去錯(cuò)配與結(jié)構(gòu)估計(jì)可以轉(zhuǎn)化為模型擬合問(wèn)題，即在噪音數(shù)據(jù)中提取特征的變換模型 (結(jié)構(gòu))．常用的模型擬合方法包括最小二乘法[13]、Hough變換[14]、RANSAC[15]等．最小二乘法是以殘差平方和最小的原則作為直線參數(shù)估計(jì)結(jié)果，但是當(dāng)存在嚴(yán)重噪聲時(shí)，該方法將不能正確估計(jì)模型．Hough變換利用點(diǎn)與線的對(duì)偶性，將原始圖像空間給定的曲線通過(guò)曲線表達(dá)形式變?yōu)閰?shù)空間中的一個(gè)點(diǎn)．該方法的缺點(diǎn)是參數(shù)過(guò)多而導(dǎo)致組合爆炸．RANSAC方法雖然能夠簡(jiǎn)單而巧妙地去除部分錯(cuò)誤匹配對(duì)，但是該方法潰點(diǎn)低，無(wú)法實(shí)現(xiàn)多結(jié)構(gòu)提?。硗?，RANSAC需要明確inliers的尺度，而這往往需要先驗(yàn)知識(shí)，因而在許多領(lǐng)域中并不可行．要解決特征去錯(cuò)配，正確估計(jì)圖像的變換模型，就要實(shí)現(xiàn)多結(jié)構(gòu)提?。壳岸嘟Y(jié)構(gòu)估計(jì)的方法有很多，包括 PROSAC[16－17]、ITKSF[18－19]及 Multi-GS[20]等．

因此，本文擬首先用粒子群優(yōu)化算法 (Particle Swarm Optimization，PSO)對(duì)ASIFT的采樣進(jìn)行優(yōu)化，使參數(shù)在更廣闊的連續(xù)空間中搜索最優(yōu)解，然后得到更大量的特征匹配對(duì)，再用Multi-GS方法對(duì)PSO優(yōu)化后的ASIFT算法的匹配結(jié)果進(jìn)行多結(jié)構(gòu)估計(jì)，去除錯(cuò)誤的匹配點(diǎn)對(duì)，以期最終提取出盡可能多而且精準(zhǔn)的匹配點(diǎn)對(duì)．

1 ASIFT算法原理

1.1 ASIFT算法流程

定理1[12]任意的非對(duì)稱仿射矩陣，若滿足其行列式是嚴(yán)格的正值，則都有唯一的分解:

其中，λ〉0，λ2t是矩陣A的行列式，Ri是旋轉(zhuǎn)矩陣，φ∈[0，π]，Tt表示傾斜矩陣，t〉1是絕對(duì)傾斜參數(shù)．圖1是公式 (1)的幾何解釋．其中，U指被拍攝的平面物體，角度φ和θ分別表示相機(jī)光軸的經(jīng)度和緯度，ψ表示相機(jī)的旋轉(zhuǎn)角度，λ是縮放參數(shù)．

ASIFT算法的基本流程如下:

1)對(duì)每幅待匹配的圖像，通過(guò)改變相機(jī)光軸與正面視圖的經(jīng)度和緯度來(lái)仿真所有可能的仿射變換情況．圖像先經(jīng)過(guò)φ度旋轉(zhuǎn)，接著通過(guò)參數(shù)進(jìn)行傾斜變換．如圖2所示．

圖1 公式(1)的幾何解釋Fig.1 Geometric interpretation of the Equ.1

2)所有的這些旋轉(zhuǎn)和傾斜變換都是在一個(gè)有限的小范圍內(nèi)改變參數(shù)φ和θ值得到的，而且，對(duì)這些參數(shù)的采樣步長(zhǎng)要確保使不同的φ值和θ值得到的仿射圖像之間盡可能相似．對(duì)得到的所有仿射圖像使用SIFT算法進(jìn)行特征點(diǎn)提?。?/p>

3)對(duì)提取完特征點(diǎn)的仿射圖像兩兩之間使用SIFT算法進(jìn)行匹配，如圖2所示．

1.2 粒子群優(yōu)化的ASIFT算法

粒子群算法的數(shù)學(xué)描述[21]如下:

設(shè)粒子群的種群數(shù)量為M，搜索空間為d維，其中第i個(gè)粒子在第n次迭代中的位置可以表示為:粒子i的速度為每次迭代中粒子i移動(dòng)的距離，用表示，則第i個(gè)粒子在第n+1代的第j(j=1，2，…，d)維子空間中的速度和位置:

圖2 ASIFT算法的概覽圖Fig.2 Overview of the ASIFT

其中，ω為慣性權(quán)值，c1和c2為加速因子，r1和r2是在[0，1]范圍內(nèi)的兩個(gè)隨機(jī)數(shù)，常量vmax即最大速度用來(lái)限制粒子的速度，pij是當(dāng)前粒子的歷史最優(yōu)位置，gj則表示整個(gè)群體的歷史最優(yōu)位置．

本文采用了文獻(xiàn) [22]提出的變異粒子群優(yōu)化算法，對(duì)參數(shù)t和φ進(jìn)行編碼．變異粒子群算法中加入了變異因子R，對(duì)每一個(gè)粒子設(shè)置一個(gè)隨機(jī)數(shù)ri，在每一次迭代中，若某個(gè)粒子的隨機(jī)數(shù)ri的值超過(guò)了R的值，則該粒子就發(fā)生變異，否則，粒子就進(jìn)行正常的更新．

粒子群優(yōu)化的ASIFT算法具體過(guò)程如下:

Step1 初始化所有粒子，在允許范圍內(nèi)隨機(jī)設(shè)置每個(gè)粒子的初始位置和速度，每個(gè)粒子的局部最優(yōu)解pbest設(shè)為其初始位置，全局最優(yōu)解gbest設(shè)為空．

Step2 計(jì)算每個(gè)粒子的適應(yīng)值．粒子的編碼方式為:

ti1 φi1 ti2 φi2

其中，ti1，ti2分別表示粒子i對(duì)應(yīng)的兩幅圖像的傾斜參數(shù)，φi1，φi2分別表示粒子i的兩幅圖像的相機(jī)光軸的經(jīng)度，d=4．對(duì)應(yīng)每個(gè)粒子的編碼值，使用SIFT算法對(duì)相應(yīng)的仿射圖像提取特征點(diǎn)，粒子的適應(yīng)值為對(duì)應(yīng)圖像的SIFT匹配數(shù)．

Step3 更新每個(gè)粒子所經(jīng)過(guò)的最好位置pbest及群體所經(jīng)歷的最好位置gbest．

Step4 檢查每個(gè)粒子的隨機(jī)數(shù)ri，若ri大于R值，則轉(zhuǎn)Step5，否則，轉(zhuǎn)Step6．

Step5 在允許的范圍內(nèi)隨機(jī)設(shè)置當(dāng)前粒子的位置．

Step6 根據(jù)公式 (2)— (4)更新當(dāng)前粒子的速度和位置．

Step7 若滿足終止條件 (達(dá)到最大迭代次數(shù))則終止迭代，否則返回Step2．

2 多結(jié)構(gòu)估計(jì)Multi-GS算法

文獻(xiàn)[18]提出了Multi-GS多結(jié)構(gòu)估計(jì)算法，該算法主要利用有指導(dǎo)的采樣來(lái)代替隨機(jī)采樣，即利用特征點(diǎn)之間的相似關(guān)系來(lái)指導(dǎo)采樣，由此引入了殘差的概念:以透視變換為例，假設(shè)輸入圖像中的一點(diǎn)A(x，y)的對(duì)應(yīng)點(diǎn)坐標(biāo)為B(x'，y')，而在透視變換模型M的作用下A的實(shí)際對(duì)應(yīng)點(diǎn)為A'，因此稱理想坐標(biāo)點(diǎn)B與實(shí)際對(duì)應(yīng)點(diǎn)A'的距離r為點(diǎn)A在模型M下的殘差．

特征點(diǎn)的相似度函數(shù)可以用來(lái)指導(dǎo)模型采樣，主要采用條件概率的方法選擇特征點(diǎn)，從而構(gòu)造優(yōu)化的結(jié)構(gòu)．假設(shè) S={xs1，xs2，…，xsp}? χ是構(gòu)成模型的最小點(diǎn)集，其中，{s1，s2，…，sp}? {1，2，…，N}．隨機(jī)選擇第一個(gè)點(diǎn)xs1，而第二個(gè)點(diǎn)的選擇概率有賴于與第一個(gè)點(diǎn)的相似度，相似度越高的點(diǎn)被選中的概率越大:

其中，α1是歸一化因子，同理，第三個(gè)點(diǎn)的選擇概率有賴于與第一個(gè)點(diǎn)及第二個(gè)點(diǎn)的相似度．假設(shè)選擇每個(gè)點(diǎn)是獨(dú)立的，根據(jù)貝葉斯原則，后續(xù)點(diǎn)的選擇有賴于與被選中點(diǎn)之間的概率乘積，即第k+1個(gè)點(diǎn)的選擇概率服從:

得到條件概率之后，可以根據(jù)統(tǒng)計(jì)學(xué)原理，通過(guò)小樣本 (如之前所述的M個(gè))訓(xùn)練得知數(shù)據(jù)之間的關(guān)聯(lián) (相似度)，進(jìn)而根據(jù)這類關(guān)聯(lián)引導(dǎo)產(chǎn)生新的樣本，新樣本將不斷添加進(jìn)模型集合，特征之間的相似度也將不斷更新．為了加速算法，每產(chǎn)生k個(gè)新模型后再融入模型集M(采用折半插入)．

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

3.1 實(shí)驗(yàn)設(shè)置

PSO優(yōu)化ASIFT實(shí)驗(yàn)以VS 2010作為平臺(tái)，主要對(duì)本文算法與ASIFT算法的匹配結(jié)果進(jìn)行比較．其中，PSO算法種群規(guī)模M=10，最大迭代次數(shù)為100代．慣性權(quán)值ω隨迭代次數(shù)線性遞減，遞減公式為ω =ωstart-((ωstart-ωend)×gcrt)/gmax，ωstart和ωend分別為ω的初始值和終止值．gcrt為當(dāng)前迭代次數(shù)，gmax為最大迭代次數(shù)．加速因子c1=c2=2，變異參數(shù)R隨迭代次數(shù)線性遞減的公式為R=Rstart-((Rstart-Rend)×gcrt)/gmax，Vmax設(shè)置為搜索空間的1/6．

Multi-GS算法進(jìn)行多結(jié)構(gòu)提取的實(shí)驗(yàn)以MATLAB7.0為平臺(tái)，對(duì)PSO－ASIFT算法得到的匹配結(jié)果進(jìn)行多結(jié)構(gòu)提取，并與隨機(jī)采樣算法RANSAC的結(jié)果做對(duì)比．兩種算法均設(shè)置10 s的CPU運(yùn)行時(shí)間限制．

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

為了驗(yàn)證本文算法的有效性，采用圖3所示的集美大學(xué)尚大樓圖像進(jìn)行特征點(diǎn)匹配實(shí)驗(yàn)，待匹配圖像相對(duì)參考圖像具有一定程度的尺度和旋轉(zhuǎn)變化．圖4分別給出了ASIFT算法和PSO－ASIFT算法的特征匹配結(jié)果，其中圖4a表示ASIFT算法得到225對(duì)匹配點(diǎn)對(duì)，圖4b表示PSO－ASIFT算法得到471對(duì)匹配點(diǎn)對(duì)，是ASIFT匹配結(jié)果的兩倍．可見(jiàn)，本文改進(jìn)后的ASIFT算法的確能夠顯著提高原ASIFT算法的特征提取數(shù)量，驗(yàn)證了改進(jìn)算法的有效性．

利用PSO－ASIFT算法的上述匹配結(jié)果，使用Multi-GS多結(jié)構(gòu)估計(jì)算法進(jìn)行單應(yīng)性矩陣結(jié)構(gòu)提取實(shí)驗(yàn)．首先將PSO－ASIFT算法的匹配結(jié)果轉(zhuǎn)換為Multi-GS算法的輸入圖像形式，如圖5所示，再分別用不同顏色的符號(hào)標(biāo)識(shí)出屬于不同結(jié)構(gòu)的點(diǎn)對(duì) (紅藍(lán)綠三種顏色標(biāo)識(shí)了三種結(jié)構(gòu))，而無(wú)效的點(diǎn)對(duì)用黃色的+號(hào)標(biāo)識(shí)出．本文分別使用隨機(jī)采樣RANSAC算法和Multi-GS算法對(duì)上述輸入數(shù)據(jù)進(jìn)行多結(jié)構(gòu)提?。畧D6和圖7分別給出兩種算法的多結(jié)構(gòu)提取結(jié)果，對(duì)比圖5—圖7可知，10s的CPU時(shí)間內(nèi)，RANSAC算法只得到兩種有效的結(jié)構(gòu)，第三種結(jié)構(gòu) (圖5中綠色標(biāo)識(shí))無(wú)法得到，而Multi-GS算法命中全部三種結(jié)構(gòu) (無(wú)效點(diǎn)已經(jīng)被刪除，無(wú)標(biāo)出)，且三種結(jié)構(gòu)的分類比較準(zhǔn)確．

得到上述Multi-GS多結(jié)構(gòu)提取結(jié)果后，原始特征匹配結(jié)果 (圖4b)中把所有無(wú)效的匹配點(diǎn)對(duì)去除，剩余的即為有效匹配點(diǎn)對(duì)．去除錯(cuò)誤匹配點(diǎn)對(duì)后的結(jié)果如圖8所示，共去除89對(duì)錯(cuò)誤點(diǎn)對(duì)，最終匹配點(diǎn)對(duì)382對(duì)．

圖3 輸入圖像Fig.3 Input images

圖4 ASIFT和PSO-ASIFT算法的匹配結(jié)果Fig.4 The matches of the ASIFT and PSO-ASIFT methods

圖5 多結(jié)構(gòu)估計(jì)中的輸入匹配點(diǎn)對(duì)（無(wú)效點(diǎn)用黃色的+標(biāo)出）Fig.5 Input points of the Multi-structure estimating（the useless points maked by yellow+）

圖6 隨機(jī)采樣算法RANSAC的多結(jié)構(gòu)提取結(jié)果Fig.6 The results of random sampling RANSAC

圖7 Multi-GS算法的多結(jié)構(gòu)提取結(jié)果Fig.7 The results of Multi-GS

圖8 去除錯(cuò)配點(diǎn)對(duì)后的最終匹配效果Fig.8 The ending matches after removing the wrong points

從實(shí)驗(yàn)結(jié)果可知，本文提出的PSO－ASIFT算法能比原算法提取到更大量的特征匹配點(diǎn)對(duì)，在此基礎(chǔ)上利用Multi-GS多結(jié)構(gòu)估計(jì)算法進(jìn)行了多結(jié)構(gòu)提取，進(jìn)而去除了錯(cuò)誤的匹配點(diǎn)對(duì)，最終得到了大量且精確的特征匹配點(diǎn)對(duì)．可見(jiàn)，本文算法是一種有效的特征提取算法．

4 結(jié)束語(yǔ)

本文先用變異粒子群算法對(duì)ASIFT特征提取算法進(jìn)行優(yōu)化，在得到大量特征匹配點(diǎn)的基礎(chǔ)上又通過(guò)Multi-GS多結(jié)構(gòu)估計(jì)算法對(duì)特征匹配結(jié)果進(jìn)行多結(jié)構(gòu)提取并且去除錯(cuò)誤的匹配點(diǎn)，最終得到大量且精確的特征匹配對(duì)．通過(guò)實(shí)驗(yàn)結(jié)果說(shuō)明本文算法是一種有效的特征提取算法，但同時(shí)發(fā)現(xiàn)該算法在時(shí)間效率方面還有不足，因此，如何在本文基礎(chǔ)上盡可能提高時(shí)間效率，將是今后要繼續(xù)研究的方向及重要內(nèi)容．

[1]SCHAFFALITZKY F，ZISSERMAN A．Multi-view matching for unordered image sets[C]//Proceedings of the 7th European Conference on Computer Vision．Copenhagen，Denmark:Springer-Verlag，2002:414-431．

[2]FERRARI V，TUYTELAARS T，VAN GOOL L．Simultaneous object recognition and segmentation by image exploration[C]//Proceeding of the 8th European Conference on Computer Vision．Prague，Tcheque Republic:Springer-Verlag，2004:40-54．

[3]LAZEBNIK S，SCHMID C，PONCE J．Sparse texture representation using affine-invariant neighborhoods [C]//Proceedings of the Conference on Computer Vision and Pattern Recognition．Madison，Wisconsin，USA:IEEE，2003:319-324．

[4]MIKOLAJCZY K，SCHMID C．Indexing based on scale invariant interest points[C]//Proceeding of the 8th International Conference on Computer Vision．Vancouver，Canada:IEEE，2001:525-531．

[5]SE S，LOWE D，LITTLE J．Global localization using distinctive visual features[C]//International Conference on Intelligent Robots and Systems，IROS 2002．Lausanne，Switzerland:IEEE，2002:226-231．

[6]SIVIC J，ZISSERMAN A．Video google:a text retrieval approach to object matching in videos[C]//Proceedings of the 9th International Conference on Computer Vision．Nice，F(xiàn)rance:IEEE，2003:1470-1478．

[7]BROWN M，LOWE D．Recognising panoramas[C]//Proceedings of the 9th International Conference on Computer Vision．Nice，F(xiàn)rance:IEEE，2003:1218-1227．

[8]HARRIS C，STEPHENS M．A combined corner and edge detector[C]//Alvey Vision Conference．Manchester，UK:[s.n.]，1988:15-50．

[9]MIKOLAJCZYK K，SCHMID C．Scale and affine invariant interest point detectors[J]．International Journal of Computer Vision，2004，60(1):63-86．

[10]MATAS J，CHUM O，URBAN M，et al．Robust wide-baseline stereo from maximally stable extremal regions [J]．Image and Vision Computing，2004，22(10):761-767．

[11]MIKOLAJCZYK K，SCHMID C．A performance evaluation of local descriptors [J]．IEEE Trans PAMI，2005，27(10):1615-1630．

[12]MOREL J M，YU G．ASIFT:a new framework for fully affine invariant image comparison[J]．SIAM Journal on Imaging Sciences，2009，2(2):438-469．

[13]AKYILMAZ．Total least squares solution of coordinate transfor-mation [J]．Survey Review，2007，39(303):68-80．

[14]LINGWORTH J，KITTLER J．A Survey of the Hough Transform [J]．CVGIP，1988，44:87-116．

[15]MILLER V S．Use of elliptic curves in cryptography [C]//Advances in Crptology CRYPTO85．Berlin:Springer，Lecture Notes in Computer Sci，1986，218:417-428．

[16]CHUM O，MATAS J．Matching with PROSAC-progressive sample consensus[C]//CVPR．San Diego，CA，USA:IEEE，2005:1-7．

[18]WONG H S，TAT J CHIN，YU J，et al．Efficient multi-structure robust fitting with incremental top-k lists comparison[C]//Asian Conference on Computer Vision(ACCV)．Queenstown，New Zealand:Springer，Lecture Notes in Computer Sci，2010:553-564．

[20]CHIN T J，YU J，SUTER D．Accelerated hypothesis generation for multi-structure robust fitting [C]//European Conference on Computer Vision．Berlin:Spinger Berlin Heidelberg，2010:533-546．

[21]KENNEDY，EBERHART R C．Particle swarm optimization [C]//Proceeding of IEEE International Conference on Neural Networks．Piscataway:IEEE，1995:1942-1948．

[22]YOU B Y，CHEN G L，GUO W Z．Topology control in wireless sensor networks based on discrete particle swarm optimization [C]//Proceeding of IEEE International Conference on Intelligent Computing and Intelligent Systems．Piscataway，NJ，USA:IEEE，2009:269-273．