基于全局最優(yōu)的快速一致性點漂移算法

趙 鍵 孫即祥 周石琳 李智勇 王亮亮

(國防科學(xué)技術(shù)大學(xué)電子科學(xué)與工程學(xué)院 長沙 410073)

1 引言

點模式(或稱點集)匹配廣泛應(yīng)用于圖像配準(zhǔn)[1]，圖像分類[2]與檢索[3]，目標(biāo)識別[4]，形狀匹配[5]和立體視覺[6]等領(lǐng)域。其任務(wù)是尋找點集之間的對應(yīng)關(guān)系和求解點集之間的變換關(guān)系，但由于形變、噪聲、出格點以及缺失點等因素的影響始終難以完全解決，因而研究有效且魯棒的點模式匹配算法已經(jīng)成為目前模式識別和機器視覺等領(lǐng)域的研究熱點之一。目前，點模式匹配算法大致可以分為兩大類，一是基于變換關(guān)系求解的算法，是通過估計點模式之間的空間變換參數(shù)，利用該參數(shù)恢復(fù)或模擬點模式間的變換，從而求解點模式匹配問題，也稱之為基于變換參數(shù)估計的算法。這類算法主要有一致性點漂移算法[7]，迭代最近點算法[8]，基于薄板樣條的魯棒點模式匹配算法[9]，等。二是基于匹配關(guān)系求解的算法，是通過提取點集中點的特征而后運用匹配識別方法獲得點模式間的匹配關(guān)系，從而求解點模式匹配問題，或更形象地稱為基于特征的匹配算法。這類算法主要有基于形狀上下文的方法[10]，基于不變量特征的方法[11]以及基于譜圖論的方法[12]等。

迭代最近點(Iterative Closest Point,ICP)算法[8]構(gòu)造簡單、計算復(fù)雜度低，是應(yīng)用廣泛的點集匹配算法之一。ICP算法的基本思想是：基于最近距離準(zhǔn)則，通過指派點集間點與點的對應(yīng)關(guān)系，求解點集間的變換模型。然后，再通過估計的變換模型來重新確定對應(yīng)關(guān)系，如此迭代達(dá)到局部最小值。盡管ICP算法直觀簡潔，但其對于點集間的初始化校準(zhǔn)以及點集中所存在的出格點、缺失點較為敏感。基于薄板樣條的魯棒點模式匹配算法(TPS-RPM)算法[9]通過結(jié)合軟指派方法和確定性退火機制，來迭代的估計變換關(guān)系和更新對應(yīng)關(guān)系。相比于ICP算法，TPS-RPM不僅適用于非剛體變換，而且其對于噪聲、出格點的魯棒性更強。盡管采用了確定性退火機制來避免陷入部分局部最優(yōu)解，但是TPS-RPM算法也無法保證能達(dá)到全局最優(yōu)，而且其迭代速度較慢?；谧V圖論的方法是一類利用鄰接矩陣或者與其密切相關(guān)的Laplace矩陣的特征值和特征矢量來刻畫點集全局結(jié)構(gòu)的方法[12]。經(jīng)典譜圖論方法的顯著優(yōu)點是構(gòu)造簡單、計算量小，但由于它們是精確點模式匹配算法，因此，若待匹配的兩個點集大小不同以及存在位置噪聲時性能較差?；谛螤钌舷挛牡乃惴╗10]要求點集間對應(yīng)點的鄰域結(jié)構(gòu)保持相似，而基于不變量特征的方法[11]則需要保持點集的凸殼結(jié)構(gòu)保持不變，因而它們均對于噪聲、出格點以及遮擋導(dǎo)致的缺失點等情況魯棒性較差。

一致性點漂移算法[7](Coherent Point Drift,CPD)是一種魯棒的基于高斯混合模型的點集匹配算法。該算法適用于剛體以及非剛體變換下的多維點集配準(zhǔn)問題，對于噪聲、出格點以及缺失點的影響具有較強魯棒性。但由于采用的是EM算法框架，其存在兩個缺陷：(1)對于迭代的初始點選取十分敏感，如果選取不當(dāng)，極易陷入局部最優(yōu)解，從而導(dǎo)致算法的最終匹配結(jié)果較差；(2)CPD算法的收斂速度與待匹配點集大小成反比，從而導(dǎo)致在解決大規(guī)模點集匹配問題時，該算法的運行速度較慢。針對上述問題，本文提出了基于全局最優(yōu)的快速一致性點漂移算法(Global Optimal ＆ Fast CPD,GOFCPD)。本文首先將待匹配點集進(jìn)行正交標(biāo)準(zhǔn)形約簡，再證明當(dāng)初始旋轉(zhuǎn)角度與真實旋轉(zhuǎn)角度間隔小于π/4以及高斯混合模型中協(xié)方差等于點集間均方距離時，EM算法迭代能達(dá)到全局最優(yōu)?；谏鲜鼋Y(jié)論，本文采取多重初始化EM算法策略，實現(xiàn)了全局優(yōu)化。針對單重初始化CPD算法的收斂速度隨點集大小增大而減小以及在全局優(yōu)化時所采用的多重初始化所帶來的計算復(fù)雜度成倍數(shù)增加的問題，本文提出了基于置信域的全局收斂平方迭代期望最大化(TR-gSQUAREM)算法，從而最終實現(xiàn)超線性的收斂速度。

2 基于全局最優(yōu)的快速一致性點漂移算法(GOF-CPD)

本節(jié)首先對原始的一致性點漂移算法(CPD)進(jìn)行簡單介紹，然后提出點集的正交標(biāo)準(zhǔn)形約簡方法，利用約簡后點集的重要性質(zhì)，證明在高斯混合模型參數(shù)最大似然估計問題中，不完全觀測數(shù)據(jù)的對數(shù)似然函數(shù)在約簡后參數(shù)空間中的全局最優(yōu)解附近區(qū)域是凸函數(shù)，并給出了該區(qū)域的邊界值，再以凸區(qū)域邊界值作為多重初始點來達(dá)到全局最優(yōu)。最后，為實現(xiàn)快速的全局最優(yōu)算法，提出基于置信域的二次迭代EM算法來取代原始EM算法框架。

2.1 一致性點漂移算法(CPD)

一致性點漂移算法(CPD)本質(zhì)上是將點集配準(zhǔn)過程轉(zhuǎn)化為高斯混合模型(Gaussian Mixture Model,GMM)概率密度函數(shù)的參數(shù)估計問題[7]。其中，將模板點集中各點視作高斯混合模型中各個高斯分量質(zhì)心，而目標(biāo)點集則代表了混合模型所生成的觀測樣本數(shù)據(jù)。通過觀測數(shù)據(jù)的對數(shù)似然函數(shù)最大化將GMM質(zhì)心擬合至目標(biāo)點集中的對應(yīng)點。在最優(yōu)情況下，不僅實現(xiàn)了點集之間的配準(zhǔn)，而且通過GMM中高斯成分的后驗概率得到了點集之間的匹配對應(yīng)關(guān)系。在點集配準(zhǔn)過程中，CPD算法將模板點集作為整體按一定的變換關(guān)系向目標(biāo)點集進(jìn)行保持拓?fù)浣Y(jié)構(gòu)一致性的漂移運動。

設(shè)YM×D=[y1,y2,…,yM]T為模板點集，XN×D=[x1,x2,…,xN]T為目標(biāo)點集，其中M為模板點集大小，N為數(shù)據(jù)點集大小，D為點的維數(shù)。以模板點集中各點作為各個混合高斯成分質(zhì)心而組成高斯混合模型，定義該GMM的概率密度函數(shù)為

將GMM的各個高斯分量質(zhì)心按變換參數(shù)集φ進(jìn)行幾何變換，同時其協(xié)方差σ2也隨之變化。設(shè)GMM總的參數(shù)集為Θ=(φ,σ2)，匹配關(guān)系可用后驗概率矩陣來定義P=[P(m|xn)]M×N。最后，通過極大化不完全觀測數(shù)據(jù)的對數(shù)似然函數(shù)L(Θ)來估計參數(shù)集Θ和P：

CPD算法采用了期望最大化(EM)算法來求解式(3)的極大化問題，即分別以求期望值(E-步)和求最大值(M-步)兩步進(jìn)行迭代循環(huán)來分別求解P和Θ。雖然EM算法能收斂到對數(shù)似然函數(shù)的穩(wěn)定點，但是不能保證收斂到全局極大值點。因此，CPD算法本質(zhì)上是一種局部最優(yōu)算法，其對于初始點的選取十分敏感。

2.2 點集的正交標(biāo)準(zhǔn)形約簡

本文主要討論的是一般仿射變換下2維點集匹配的問題，相比于剛體和相似變換，仿射變換更具一般性，但由于仿射變換參數(shù)空間維數(shù)較高(6個自由度)，從而導(dǎo)致全局尋優(yōu)的過程較為復(fù)雜。因此，本文首先將點集進(jìn)行正交標(biāo)準(zhǔn)形約簡，將一般仿射變換問題約簡為僅有旋轉(zhuǎn)的剛體變換問題。

設(shè)模板和目標(biāo)點集的維數(shù)D=2。不失一般性，首先考慮精確點集(待匹配點集中點的數(shù)目相同且一一對應(yīng))的匹配問題，則正交標(biāo)準(zhǔn)形約簡分為以下3 步：

原始點集經(jīng)過上述約簡后所得到的正交標(biāo)準(zhǔn)形具有如下4個重要的性質(zhì)：

性質(zhì) 1 正交標(biāo)準(zhǔn)形的二階矩矩陣為單位陣，即有：YT?Y=I,XT?X=I，其中I為單位矩陣；

性質(zhì) 4 存在一般仿射變換關(guān)系的原始點集在經(jīng)過上述正交標(biāo)準(zhǔn)形約簡后，所得到的正交標(biāo)準(zhǔn)形之間僅存在旋轉(zhuǎn)變換關(guān)系。即：設(shè)原始點集X和Y之間存在一般仿射變換關(guān)系：X=Y?+1N×1在分別進(jìn)行了正交標(biāo)準(zhǔn)形約簡后得到X′和Y′，兩者僅存在旋轉(zhuǎn)變換關(guān)系：

由性質(zhì)4可知，經(jīng)過正交標(biāo)準(zhǔn)形約簡后的精確點集之間所存在的一般仿射變換可被約簡為正交旋轉(zhuǎn)變換，即此時仿射變換參數(shù)集φ={a11,a12,a21,a22,tx,ty}簡化為φ={θ}。

需要特別說明的是：上述性質(zhì)是在精確點集匹配問題中成立，而當(dāng)點集中存在出格點、缺失點以及噪聲時，也即在非精確點集匹配問題中，兩個存在仿射變換關(guān)系的點集，在經(jīng)過了正交標(biāo)準(zhǔn)形約簡后，它們之間仍然保持仿射變換關(guān)系。此時，可將仿射變換矩陣AY′X′進(jìn)行SVD分解[13]：

2.3不完全觀測數(shù)據(jù)對數(shù)似然函數(shù)的全局極值附近凸區(qū)域邊界

Wu[14]證明了在局部極值附近區(qū)域，如果對數(shù)似然函數(shù)是凸函數(shù)時，EM算法保證能收斂到該局部極值。因此，本節(jié)將確定對數(shù)似然函數(shù)的全局極值附近凸區(qū)域及其邊界值范圍。

設(shè)正交約簡后的精確模板與目標(biāo)點集分別為Y和X。則由第2.2小節(jié)可知，此時兩者存在正交旋轉(zhuǎn)變換：X=Y?RT(θ*),θ*為真實旋轉(zhuǎn)角度(也即全局最優(yōu)解)。因此，可將xn在第m個高斯分量中的概率密度p(xn|m)用 Δθ=(θ-θ*)來表示：

由式(3)和式(5)可得到不完全觀測數(shù)據(jù)的對數(shù)似然函數(shù)關(guān)于Δθ以及σ2的偏導(dǎo)數(shù)分別為

式(6)和式(7)中的

通過式(6)，式(7)以及2.2小節(jié)中4個性質(zhì)可得到下面的推論1。

推論1 在精確點集匹配情況下時，取2σ=則有當(dāng)M→+∞，在其中θ*為真實的旋轉(zhuǎn)角度。

由推論1可知，與真實旋轉(zhuǎn)角度θ*間隔π/4的θ為對數(shù)似然函數(shù)L(Θ)在角度參數(shù)維上的駐點，又由式(7)可知，對于任意的σ2均滿足因此，真實解Θ*={θ*,0}附近的凸區(qū)域邊界值可設(shè)為：

圖1(a)為500個隨機模板點集以及由該模板經(jīng)過隨機仿射變換所生成的目標(biāo)點集所構(gòu)成的不完全觀測數(shù)據(jù)對數(shù)似然函數(shù)的3維曲面圖，其X軸為相對于真實旋轉(zhuǎn)角度的角度間隔,∈[- 1 80°,180°],Y軸為GMM的協(xié)方差σ2,σ2∈[0,2/500],Z軸為對數(shù)似然函數(shù)值L(Θ)。從圖1(a)中可看出，Δθ=0°,σ2=0 為全局最優(yōu)解，在該全局最優(yōu)解附近L(Θ)呈現(xiàn)出凸函數(shù)特性，為了更直觀顯示出該凸區(qū)域的邊界，現(xiàn)將L(Θ)轉(zhuǎn)化為2維平面曲線圖。如圖1(b)所示，圖中X軸為Δθ,Y軸為L(Θ)，而每條曲線表示在某一固定的σ2下的對數(shù)似然函數(shù)隨角度間隔變化的曲線，其中位于最下方的曲線其協(xié)方差σ2=2 /M=2 /500，隨著σ2的減少，曲線也逐漸向上分布即L(Θ)逐漸增大，也進(jìn)一步證明了dL(Θ)/dσ2＜0的正確性，從圖1(b)可知，當(dāng)取σ2=2/M時，Δθ=± 4 5°為該曲線離真實解Δθ=0°附近最近的駐點，因此以這兩個駐點作為真實解附近凸區(qū)域的邊界值也是正確直觀的。

2.4 基于全局最優(yōu)的快速CPD算法

由第2.3小節(jié)可知，對數(shù)似然函數(shù)的真實解附近凸區(qū)域邊界值可以確定下來，而當(dāng)初始點位于真實解附近的凸區(qū)域內(nèi)時，EM算法能確保最終收斂于該真實解[15]。因此，本文采用基于多重初始化的策略來實現(xiàn)CPD算法的全局優(yōu)化，從而提出了基于全局最優(yōu)的CPD算法(Global Optimal CPD,GOCPD)。GO-CPD算法核心在于如何選取多個初始點：首先由推論1可知，為了能達(dá)到全局最優(yōu)，初始旋轉(zhuǎn)角度與真實旋轉(zhuǎn)角度之間的間隔不能大于45°，也即初始點的旋轉(zhuǎn)角度之間的間隔不能大于90°，由此可知，初始點的個數(shù)至少為4。設(shè)4個初始點的集其中第i個初始點其中初始角度其余的參數(shù)為：=2 /M。然后，在4個初始點下各自執(zhí)行EM迭代循環(huán)直至收斂。最后比較所得到的4個對數(shù)似然函數(shù)的局部極值L={L(i)(Θ)=1,2,3,4}，以其中最大值所對應(yīng)的解作為最終的全局最優(yōu)解：Θ*=argmax(L)。

上述的GO-CPD算法雖能達(dá)到全局最優(yōu)，但其所采用的是原始EM算法求解似然函數(shù)極值，而原始EM算法收斂速度與缺失數(shù)據(jù)信息量是成反比的[15]，因此隨著點集大小的增加，原始EM算法的收斂速度也會隨之迅速下降。此外，GO-CPD算法需要進(jìn)行多重初始化下的EM迭代循環(huán)，因此算法總的迭代次數(shù)會隨著點集大小的增加而成倍增加?？紤]到算法的效率問題，須對GO-CPD算法進(jìn)行加速，本文擬對其單重初始化中的原始EM算法進(jìn)行加速。

文獻(xiàn)[16]提出了基于平方迭代的加速EM(SQUAREM)算法，該算法是一種簡單的、全局收斂的EM加速算法，在保持原始EM算法的單調(diào)性基礎(chǔ)上，又結(jié)合數(shù)值外推方法達(dá)到超線性的收斂速度。其基本原理是：將原始EM算法定義為參數(shù)空間上Θ的不動點映射F，即F：Θ?Θ，則原始EM算法的迭代過程可表示為

圖1 不完全觀測數(shù)據(jù)對數(shù)似然函數(shù)的3維曲面圖和2維曲線圖

相比于傳統(tǒng)的Newton方法以及Steffensen方法[16]，SQUAREM算法利用迭代誤差的平方來近似迭代的步長和方向，從而得到其迭代公式為

其中αn,rn和vn的定義為

式(12)中的g(Θn)為F在Θn處的梯度：g (Θn)=F(Θn)-Θn。

當(dāng)初始點遠(yuǎn)離局部極值點時，SQUAREM并不能保證最終收斂于該局部極值點，為了達(dá)到全局收斂性，文獻(xiàn)[16]提出了SQUAREM的全局收斂方法(gSQUAREM)，其核心思想為：當(dāng)α＞-1時，即SQUAREM算法迭代中的對數(shù)似然函數(shù)不滿足單調(diào)遞增時，需要通過回溯方法來自適應(yīng)調(diào)整步長使α=-1(即恢復(fù)原始EM算法迭代)；反之，當(dāng)α＜-1時，則不需要調(diào)整步長α。因此，gSQUAREM既能保持對數(shù)似然函數(shù)單調(diào)遞增，又能進(jìn)一步提高收斂速度。

在實際應(yīng)用中，上述gSQUAREM雖然能保證在似然函數(shù)遞增的方向上收斂，卻極有可能“舍近求遠(yuǎn)”地收斂至離初始點較遠(yuǎn)的局部極值，從而導(dǎo)致其最終不能收斂至真正的全局最優(yōu)解。為克服上述缺陷，結(jié)合第2.3小節(jié)中的凸區(qū)域邊界值，本文提出了基于置信域的全局收斂平方迭代EM算法(Trust Region gSQUAREM,TR-gSQUAREM)，并將其替換GO-CPD算法中的原始EM算法，最終形成了基于全局優(yōu)化的快速CPD算法(Global Optimal ＆ Fast CPD,GOF-CPD)。GOF-CPD算法的具體流程如表1 所示。

表1 GOF-CPD算法流程

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

本節(jié)進(jìn)行了模擬仿真和真實數(shù)據(jù)兩種實驗。在模擬仿真實驗中，首先在剛體變換下驗證了本文算法的全局尋優(yōu)能力，再將本文算法與其他幾種算法分別進(jìn)行了抗噪聲和抗出格點以及抗缺失點能力的比較。在真實圖像數(shù)據(jù)實驗中則驗證了本文算法解決實際圖像特征點匹配問題的能力。

3.1 模擬仿真實驗

模擬點集數(shù)據(jù)的生成方式為：模板點集Y為在單位平面內(nèi)服從均勻分布的隨機點模式，其大小為M。目標(biāo)點集X是由Y經(jīng)過隨機的仿射變換后產(chǎn)生的，兩者大小相同即N=M，本文稱Y與X分別為精確模板點集和精確目標(biāo)點集。加噪聲的非精確點集Yn與Xn是分別在精確點集Y與X內(nèi)每個點位置上疊加高斯噪聲，其均值為零，標(biāo)準(zhǔn)差為精確點集內(nèi)任意兩點之間最小歐式距離的f倍(本文稱f為噪聲水平因子)。加出格點的非精確點集Yo和Xo則是分別在精確目標(biāo)點集所在區(qū)域內(nèi)隨機增加Ro?M和Ro?N個點后所構(gòu)成的點集(本文稱Ro為出格點比率)。存在缺失點的非精確點集Ym和Xm則是分別在精確點集中隨機減少Rm?M和Rm?N個點后所構(gòu)成的點集(本文稱Rm為缺失點比率)。每組模擬仿真實驗均進(jìn)行了100次蒙特卡洛實驗，所采用的實驗平臺為：Pentium Dual-Core CPU 2.93G，內(nèi)存2.0 G。

3.1.1 算法全局優(yōu)化能力比較實驗下面將本文所提出的GOF-CPD算法與CPD算法[7]，ICP算法[8]和TPS-RPM 算法[9]進(jìn)行了在僅存在旋轉(zhuǎn)的剛體變換下各種算法的全局優(yōu)化能力比較實驗，即令180°，其中模板點集與目標(biāo)點集均為模擬的精確點集，點集大小均為400。圖2給出了4種算法的正確匹配率Pc隨旋轉(zhuǎn)角度θ的變化曲線，從圖2可看出，ICP算法僅在[- 1 5°,15°]小角度范圍內(nèi)能保持較高的正確匹配率，CPD算法只能在[-4 5°,45°]范圍內(nèi)達(dá)到85%以上的匹配正確率，TPS-RPM算法在[-4 5°,45°]內(nèi)達(dá)到98%以上的匹配正確率。而本文的GOF-CPD算法能在[- 1 80°,180°]的全角度區(qū)間內(nèi)保持100%的匹配正確率，從而驗證了本文算法具備全局優(yōu)化的能力。

3.1.2 算法魯棒性比較實驗將本文算法與其他3種算法分別進(jìn)行了魯棒性的綜合比較實驗，即：抗噪聲和抗出格點以及抗缺失點能力的綜合比較。

其中精確模擬點集之間的隨機仿射變換參數(shù)分別是在 - 180°≤θ,φ≤180°,0.1 ≤λx,λy≤ 1 0,-5≤tx,ty≤ 5 范圍內(nèi)服從均勻分布的隨機值，而精確點集大小取為：N=M=3 0。每種魯棒性實驗中分成兩組進(jìn)行統(tǒng)計實驗：第1組為非精確模板點集與精確目標(biāo)點集之間的匹配；第2組則為精確模板點集與非精確目標(biāo)點集之間的匹配。

在上述的非精確模板點集與精確目標(biāo)點集的匹配實驗中，魯棒性權(quán)值設(shè)為ω=0；而在精確模板點集與非精確目標(biāo)點集的匹配實驗中，魯棒性權(quán)值設(shè)為ω=0.5。從圖3和圖4可知，在隨機仿射變換下，本文的GOF-CPD算法對于噪聲、出格點以及缺失點的魯棒性均要明顯強于其他3種算法。

圖2 不同算法在剛體旋轉(zhuǎn)變換下的全局優(yōu)化能力比較實驗結(jié)果

3.1.3 算法時間復(fù)雜度比較實驗將本文算法與其他幾種算法進(jìn)行了算法平均耗時的比較實驗，其中模擬點集之間仿射變換參數(shù)分別是在 - 1 80° ≤θ,φ≤ 1 80°,0.1 ≤λx,λy≤ 1 0,- 5 ≤tx,ty≤ 5 范圍內(nèi)服從均勻分布的隨機值，而模板與目標(biāo)點集均為精確點集，點集大小取值滿足：{M=N=10? 2i-1|i=1,2,…,8 }。

從圖5(a)可看出，本文的GOF-CPD算法在點集大小少于160時，其平均耗時比CPD算法稍多，但是當(dāng)點集大小多于160后，兩者之間的平均耗時則相差無幾，而從圖5(b)中可知，本文的GOF-CPD算法要比CPD算法的平均迭代次數(shù)少，而且隨著點集大小的增加呈現(xiàn)出超線性的收斂速度；GO-CPD算法無論從平均耗時還是平均迭代次數(shù)上都明顯多于本文的GOF-CPD算法；而ICP和TPS-RPM算法的平均耗時也要多于本文算法。

3.2 真實圖像數(shù)據(jù)實驗結(jié)果

為了驗證GOF-CPD算法解決實際圖像特征點匹配問題的能力，本文采用了兩幅從不同視角拍攝的建筑物圖像進(jìn)行實驗，如圖6(a),6(b)所示，兩幅圖像之間存在一定的仿射變換關(guān)系。首先在兩幅圖像中各自提取Harris角點，模板與目標(biāo)圖像中所提取的Harris角點分別用圓圈和十字符號表示，其中模板圖像中有347個角點，而目標(biāo)圖像中有393個角點。圖6(c)為配準(zhǔn)前的模板點集與目標(biāo)點集。本文GOF-CPD算法的最終匹配結(jié)果為303對匹配點(魯棒性權(quán)值設(shè)為ω=0.5)，圖6(d)給出了本文算法的最終配準(zhǔn)結(jié)果?？梢姰?dāng)模板和目標(biāo)點集中均存在較多的出格點、缺失點以及較強的噪聲時，本文算法能達(dá)到較高的匹配正確率。相比之下，由于點集間存在著較大的仿射旋轉(zhuǎn)角度從而導(dǎo)致CPD算法，TPS-RPM 算法，ICP算法在上述真實復(fù)雜情況下均匹配失效。

圖3 非精確模板點集與精確目標(biāo)點集匹配情況下算法魯棒性統(tǒng)計比較實驗結(jié)果 (ω=0)

圖4 精確模板點集與非精確目標(biāo)點集匹配情況下算法魯棒性統(tǒng)計比較實驗結(jié)果 (ω=0.5)

圖5 不同算法平均耗時以及平均迭代次數(shù)統(tǒng)計比較實驗結(jié)果

圖6 真實圖像數(shù)據(jù)下本文GOF-CPD算法的匹配結(jié)果示意圖

4 結(jié)論

一致性點漂移算法[7]對于初始點的設(shè)置十分敏感，僅能達(dá)到局部最優(yōu)，而且算法的收斂速度隨著點集大小增加而下降較快。針對這些問題，本文提出了一種新的點模式匹配算法基于全局最優(yōu)的快速一致性點漂移算法。首先，提出了點集的正交標(biāo)準(zhǔn)形約簡方法，利用約簡后點集的重要性質(zhì)，證明了在高斯混合模型參數(shù)最大似然估計問題中，不完全觀測數(shù)據(jù)的對數(shù)似然函數(shù)在約簡后參數(shù)空間中的全局最優(yōu)解附近區(qū)域是凸函數(shù)，并給出了該區(qū)域的邊界值，再以凸區(qū)域邊界值作為多重初始點來達(dá)到全局最優(yōu)。最后，為實現(xiàn)快速的全局最優(yōu)算法，提出了基于置信域的二次迭代EM算法來取代原始EM 算法框架。模擬仿真與真實數(shù)據(jù)實驗驗證了在仿射變換下本文算法的全局最優(yōu)性以及對于噪聲、出格點以及缺失點均有較強的魯棒性。

[1]Jackson B P and Goshtasby A A.Registering aerial video images using the projective constraint[J].IEEE Transactions on Image Processing,2010,19(3)：795-804.

[2]Nasreddine K,Benzinou A,and Fablet R.Variational shape matching for shape classification and retrieval[J].Pattern Recognition Letters,2010,31(12)：1650-1657.

[3]Jamieson M,Fazly A,Stevenson S,et al..Using language to learn structured appearance models for image annotation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(1)：148-164.

[4]Baloch S and Krim H.Object recognition through topo-geometric shape models using error-tolerant subgraph isomorphisms[J].IEEE Transactions on Image Processing,2010,19(5)：1191-1200.

[5]Noma A,Pardo A,and Roberto M.Structural matching of 2D electrophoresis gels using deformed graphs[J].Pattern Recognition Letters,2011,32(1)：3-11.

[6]McKeon R T and Flynn P J.Three-dimensional facial imaging using a Static Light Screen (SLS)and a dynamic subject[J].IEEE Transactions on Instrumentation and Measurement,2010,59(4)：774-783.

[7]Myronenko A and Song X B.Point-set registration：coherent point drift[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(12)：2262-2275.

[8]Besl P J and Mckay N D.A method for registration of 3-D shapes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2)：239-256.

[9]Chui H and Rangarajan A.A new point matching algorithm for non-rigid registration[J].Computer Vision and Image Understanding,2003,89(2)：114-141.

[10]Belongie S,Malik J,and Puzicha J.Shape matching and object recognition using shape contexts[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(4)：509-522.

[11]Gope C and Kehtarnavaz N.Affine invariant comparison of point-sets using convex hulls and hausdorff distances[J].Pattern Recognition,2007,40(1)：309-320.

[12]Caetano T S,McAuley J J,Cheng L,et al..Learning graph matching[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(6)：1048-1058.

[13]Hartley R and Zisserman A.Multiple View Geometry in Computer Vision[M].Second Edition,Cambridge：UK,Cambridge University Press,2004：39-40.

[14]Wu C F J.On the convergence properties of the EM algorithm[J].The Annals of Statistics,1983,11(1)：95-103.

[15]Ma J W,Xu L,and Jordan M I.Asymptotic convergence rate of the EM algorithm for gaussian mixtures[J].Neural Computation,2000,12(2)：2881-2907.

[16]Varadhan R and Roland C.Simple and globally convergent methods for accelerating the convergence of any EM algorithm[J].Scandinavian Journal of Statistics,2008,35(1)：335-353.