基于混合特征的非剛性點陣配準算法

湯昊林 楊揚,2 楊昆,2 羅毅,2 張雅瑩 張芳瑜

基于混合特征的非剛性點陣配準算法

湯昊林1楊揚1,2楊昆1,2羅毅1,2張雅瑩1張芳瑜1

提出一種基于混合特征的非剛性點陣配準算法.該算法包含了對應關系評估與空間變換更新兩個相互交替的步驟.首先定義了兩個特征描述法用于描述兩個點陣之間的全局和局部幾何結構特征差異,隨后合并這兩個特征描述法建立一個基于混合特征的能量優(yōu)化方程.該能量優(yōu)化方程可以利用線性分配技術進行求解,同時可以靈活地選擇使用最小化全局結構特征差異或最小化局部結構特征差異來評估兩個點陣之間的對應關系.為了增強前述兩個步驟之間的協(xié)調性,我們利用能量權重調節(jié)在整個配準過程中控制能量優(yōu)化從最小化局部結構特征差異逐步轉變?yōu)樽钚』纸Y構特征差異,同時控制用于空間變換的薄板樣條函數(Thin plate spline)的更新從剛性變換逐步轉變?yōu)榉莿傂宰儞Q.我們在二維輪廓配準、三維輪廓配準、序列圖像配準和圖像特征點配準下對本文算法進行了各項性能測試,同時也與當前8種流行算法進行了性能比較.本文算法展現(xiàn)了卓越的非剛性配準性能,并在大部分實驗中超越了當前的相關算法.

非剛性,點陣配準,混合特征,對應關系評估,空間變換更新

非剛性點陣配準(Non-rigid point set registration)是將某一點陣(稱為源點陣)與其發(fā)生形變后的點陣(稱為目標點陣)進行匹配的過程.該技術在計算機視覺、機器學習、醫(yī)學圖像處理、模式識別以及地理信息系統(tǒng)中扮演著極其重要的角色.基于當前算法的特點,非剛性點陣配準算法大體可以分為兩大類:基于迭代或非迭代的算法和基于學習或非學習的算法.由于本文算法主要涉及基于迭代的問題,所以我們主要從基于迭代或非迭代的角度來介紹當前的非剛性點陣配準算法.

在基于非迭代的非剛性點陣配準算法中,兩組點陣之間的對應關系是通過使用某種高級結構特征(High level structural features)僅進行一次相似性評估后直接找回兩組點陣之間的對應關系.在基于非迭代的配準模型中,直線[1]、曲線[2]、表面結構[3]、Shape context[4?5]和圖論(Graphs)[6?7]等特征被用于兩個點陣之間相似度的評估.在非迭代算法中,Shape context和Graphs是最受歡迎的兩種特征描述法,其核心是通過最小化兩個點陣之間的分布差異(使用Shape context時)或者拓撲結構差異(使用Graphs時)來找回點陣之間的對應關系[4?9].最近,一部分研究人員[10?14]在傳統(tǒng)的基于Graphs特征算法的基礎上加入了學習要素,通過在配準前使用適當的學習樣本進行學習來優(yōu)化算法中的參數設置,從而提高了算法的配準精度.但是這類算法由于使用了Shape context或Graphs特征,當相鄰點較為接近時該類特征則變得非常相似以至于這類算法并不能達到較好的配準效果[8,15?16].

基于迭代的算法通常包括兩個相互交替的過程:對應關系評估(Correspondence estimation)和空間變換更新(Transformation updating).相對于基于非迭代的算法,基于迭代的算法的優(yōu)勢在于它們在迭代過程中逐步地調整源點陣的初始幾何形狀和空間位置使得源點陣在幾何形狀和空間位置上變得越來越接近目標點陣,從而使得通過幾何結構特征尋找它們之間的對應關系變得更加容易. TPS-RPM[17]是第一個利用迭代技術來進行非剛性點陣配準的算法.它通過使用點陣到點陣的距離、Softassign[18?19]和退火算法[20?21]來評估點陣之間的對應概率和控制薄板樣條函數(Thin plate spline,TPS)[22]的更新.Myronenko等[23]在TPSRPM 算法框架基礎上提出了在空間變換更新中增加運動一致性約束條件(Motion coherence constraint)[24]來提高配準過程中空間變換的穩(wěn)定性,并利用最大似然法(Maximum likelihood)來評估點陣之間的對應關系.之后,Myronenko等[25]在文獻[23]的基礎上發(fā)表了著名的CPD算法(Coherent points drift algorithm),他們改良了空間變換模型使之既可以適用于剛性和非剛性的點陣配準問題,并可以在配準精度要求相對不高的情況下通過使用快速高斯變換(Fast Gauss transform)[26]和矩陣低秩逼近(Low-rank matrix approximation)[27]技術減少計算量來提升算法的配準速度.近期, Jian等[16]提出了一種基于高斯混合模型(Gaussian mixture model)的非剛性點陣配準算法(稱為GMMREG).該算法不直接在幾何空間中配準兩個點陣,而是把兩個點陣先轉變成為兩個高斯混合模型,然后在這基礎上進行對應關系評估,空間變換更新基于最小化兩個高斯混合模型的L2距離[28].最近,國內的Ma等[29]提出了一種基于Shape context特征和L2E評估[30]的算法,Wang等[31]通過使用不對稱的高斯模型捕捉空間點陣的不對稱分布,并用其作為特征描述進行點陣的非剛性配準.

本文中,我們提出了一種基于混合特征的非剛性點陣配準算法.本算法的主要貢獻體現(xiàn)在以下3個方面:

1)全局結構特征描述算法:我們提出了一種利用和向量來描述點陣中各點的全局結構特征的描述算法.

2)局部結構特征描述算法:我們提出了一種利用點陣之間的局部區(qū)域相鄰點的距離和描述點陣中各點的局部結構特征的描述算法.

3)基于混合特征的點陣對應評估算法:我們通過混合全局和局部結構特征描述算法提出了一種基于混合特征的能量方程,該方程允許使用混合特征進行點陣對應評估,使得在配準過程中所使用的特征不再單一化,使配準精度得到了提高并在大部分實驗中超越了當前相關算法.

1 方法

我們首先定義了全局和局部特征描述法以及混合特征能量優(yōu)化方程,然后對本文算法的兩個核心步驟進行介紹.在本章的后面部分,我們將對本文算法的參數設定以及本文算法與當前相關方法的差異進行說明.假設和是兩組需要進行配準的點陣,分別為源點陣和目標點陣.

1.1 全局和局部結構特征差異

1.1.1 全局結構特征差異

全局幾何結構特征差異被定義為

1.1.2 局部結構特征差異

局部結構特征差異被定義為

在這里,我們使用Linear assignment技術來最小化全局結構特征差異矩陣與局部結構特征差異矩陣我們將會獲得兩種對應關系,它們分別是基于最小化的全局結構特征差異和局部結構特征差異計算而來的.

1.2 基于混合特征的能量優(yōu)化方程

本文中提出的基于混合特征的能量優(yōu)化方程被定義為

1.3 配準過程

1.3.1 步驟1:對應關系評估

對于線性分配中的Integer cost問題,在配準前我們首先將需要配準的點陣坐標縮放至[0,1]之間,然后在每一次迭代中把計算出的全局與局部結構特征差異矩陣通過使用和?進行數值處理,其中R被設為106.對于非方形矩陣問題(點陣b bb包含冗余點),非方形矩陣和可以通過分配虛擬項(Dummy entries)[33]來轉換為方形矩陣,而且不會影響整體能量優(yōu)化.轉換后E(M)則可以使用通常手段求解,并且仍然給出最優(yōu)解.雖然我們提供了一種針對目標點陣包含冗余點的配準解決方案,但是本文算法并不能很好地處理包含冗余點的配準問題.原因是用于描述各點全局結構特征的和向量容易受冗余點的影響.

通過使用Jonker-Volgenant算法求解的對應關系矩陣M確保了從點陣到點陣的一一對應關系.當前迭代的對應點集由式(7)進行更新

本文提出的基于混合特征的能量優(yōu)化方程為使用混合特征來評估對應關系提供了一個靈活方法.例如,當α非常大時,最小化E等于最小化局部結構特征差異求出的點對點的對應關系是基于最小化兩個點陣之間的局部結構特征差異.當α逐漸變小時,對應關系評估開始轉向使用最小化全局結構特征差異,求出的點對點的對應關系是基于最小化兩個點陣之間的全局結構特征差異.

1.3.2 步驟2:空間變換更新

其中正規(guī)化參數λ用于調節(jié)非剛性形變系數w,同時它也被前述使用在式(6)中用來控制權重參數α的能量權重調節(jié)所控制.Φ是TPS內核矩陣,由前述TPS內核方程φ(a aa)計算而來.

為了計算d和w的最小二乘解,矩陣的QR分解技術[34]被用于分離點陣的仿射和非剛性形變空間

其中,Q1∈RN×D,Q2∈RN×(N?D),R1∈RD×D.此外,Q1與Q2擁有相同的正交列.所以式(9)可以轉換為

其中w=Q2γ,γ∈R(N?D?1)×(D+1).式(11)的最小二乘解可以通過先最小化γ,然后最小化d來求解.w和d的解為

1.4 算法偽代碼及參數設置

算法1給出了本文算法的偽代碼.

算法1.基于混合特征的非剛性配準算法

預處理.初始化參數Tinit,Tfinal,r,λinit和αinit.設定K并且確定點陣的相鄰點集

開始.能量權重調節(jié)計劃.

步驟2.使用式(12)和(13)更新TPS空間變換.

通過調節(jié)減小T,然后更新參數α和λ.

結束.直至滿足T≤Tfinal.

本文提出的基于混合特征的非剛性點陣配準算法包含四組重要參數:調節(jié)參數Tinit,Tfinal和r,權重參數α,正規(guī)化參數λ以及相鄰點個數參數K.每組參數的詳細設定如下

1)調節(jié)參數:能量權重調節(jié)中所使用的T[20?21]在配準開始前被設定為一個較高的值Tinit,隨后在每次迭代中利用一個線性調節(jié)計劃T=T×r使得T值在配準過程中被逐步降低,其中r為調節(jié)率.當到達一個較低的設定值Tinit時,調節(jié)計劃停止.本文中設計該線性調節(jié)計劃的目的主要有2方面:首先利用T來逐步減小式(6)中的權重參數α,使得式(6)的能量優(yōu)化問題可以從首先最小化局部結構特征差異逐步過度到最小化全局結構特征差異;其次利用T來逐步減小式(9)和(12)中的正規(guī)化參數λ,使得TPS空間變換可以從更加剛性的形變更新逐漸轉化為更加非剛性的形變更新.由于調節(jié)參數從根本上決定了算法迭代的次數,所以Tinit,Tfinal和r的參數設定原則為滿足配準所需的足夠迭代次數.基于前期使用Fish 1點陣[17]進行的試錯實驗(Trial-and-error experiment),起始Tinit值被設為點陣到最大距離平方的1/10,終止Tfinal值被設為點陣中各點到其最近點平均距離平方的1/8,調節(jié)率r通常被設為0.7.

2)權重參數:權重參數α在每次迭代中,通過使用α=αinit×T被逐漸減小,α的初始值設定原則為能夠保證在配準前期整個算法可以集中在利用最小化局部結構特征差異來評估點陣的對應關系.初始值αinit被設為相鄰點個數的平方K2.

3)正規(guī)化參數:正規(guī)化參數λ在每次迭代中,通過使用λ=λinit×T被逐漸減小,由于λ主要用來控制TPS變換中的剛性和非剛性形變(λ較大時, TPS呈現(xiàn)出剛性變換;λ較小時,TPS轉為呈現(xiàn)非剛性形變),所以λ的初始值設定原則為能夠確保在配準前期TPS處于剛性變換.初始值λinit被設為點陣a a

a中點的數量.

4)相鄰點數量參數:參數K的默認值設定是基于用于區(qū)別局部結構差異所需的最少相鄰點數.例如,當我們需要區(qū)別角(Corner,其中包含2個相鄰點)和十字(Cross,其中包含4個相鄰點)時,我們至少需要借助4個相鄰點來判斷.基于上述考慮,我們將參數K在二維和三維配準情況下的默認值設為5.

2 相關研究

當前主要有TPS-RPM[17],CPD[25],GMMREG(L2+TPS)[16],Ma等[29]和Wang等[31]5種算法與本文算法相似,表1詳細列舉了本文算法與上述5種算法之間存在的差異.

表1 本文算法與相關算法的不同Table 1 Methodological differences between our method and the current methods

1)對應關系評估:與上述基于單一特征配準的5種算法不同,本文算法是一種基于混合特征的能量優(yōu)化問題,且允許使用混合特征進行點陣之間的對應關系評估.因為本文算法與Ma等使用了線性分配技術求解對應關系,所以我們都提供了一個二值對應關系,即在對應關系矩陣Mij中僅使用0和1來描述對應關系.在TPS-RPM,CPD,GMMREG和Wang等[31]算法中,空間變換方程是建立在模糊對應(Fuzzy correspondences,即對應概率)關系基礎上的,所以在指導代理點陣改變其空間位置和幾何形狀時會發(fā)生模糊更新,同時也會需要更多的迭代次數才能完成配準.在本文算法中,建立在最小化全局或局部結構特征差異的二值對應關系可以為代理點陣提供一個正確且清晰的空間位置與幾何形狀的更新指導.

2)空間變換更新:本文算法使用的是標準TPS能量方程.TPS-RPM 在式(6)中增加了λ2tr[d?I]T[d?I]項用于控制仿射參數.由于本文算法在每次迭代中提供了一個較為精確的二值對應關系給TPS空間變換,所以我們僅需要使用λ來控制w系數在剛性和非剛性變換上的作用.同時一個自由的仿射變換(也就是不受控制的仿射系數d)可以幫助代理點陣快速(使用更少的迭代次數)地找到更加接近目標點陣的空間位置和幾何形狀來完成接下來的非剛性配準.此外,與CPD中強制相鄰點集保持運動一致性不同,本文算法通過在整個配準過程中固定相鄰點集和來保護代理點陣的拓撲結構特征.

3 實驗

我們使用Matlab實現(xiàn)了本文算法的主要過程,其中Jonker-Volgenant算法使用C++編寫并利用Matlab mex function調用Jonker-Volgenant算法的C++函數.我們首先基于以下四種配準模式測試了本文算法的各項性能,

1)輪廓配準(2D synthetic point set);

2)3D輪廓配準(3D face point set);

3)序列圖像(CMU house and CMU hotel sequence);

4)真實圖像特征點配準(Pascal 2007 challenge datasets).

而且,本文算法還與下列當前典型的8種算法進行了性能比較實驗,

1)基于迭代的算法:TPS-RPM[17],CPD[25], GMMREG(L2+TPS)[16],Wang等[31];

2)基于Graph的學習算法:Caetano等[10], Leordeanu等[13],Torresani等[14];

3)基于Graph的非學習算法:Zhou等[9].

最后,我們評估了本文算法的計算復雜度并且討論了如何降低本文算法的計算復雜度.

3.1 實驗設計

Line[17]、Fish 1[17]、Fish 2[25]、Chinese character[17]和3D face[25]是非剛性點陣算法在輪廓點陣配準測試中普遍使用的幾個流行點陣,它們分別來自TPS-RPM[17]和CPD[25].本文首先使用這5個點陣作為源點陣,并使用下面人工合成的方法創(chuàng)建了一系列豐富的目標點陣與TPS-RPM,CPD和GMMREG進行了性能對比實驗.為了達到公平的實驗對比,在目標點陣的生成、誤差測量和性能評估上我們遵循了TPS-RPM[17]和CPD[25]中所用的方法.由于本文中提出的全局特征描述法(見第1.1.1節(jié))是由和向量設計而來,當配準目標點陣中包含冗余點時,本文算法并不能很好地處理包含冗余點的配準問題,所以在本實驗中我們不進行包含冗余點的配準模式性能測試.

目標點陣:

1)形變級別:我們設置8個控制點(三維配準情況是為6個控制點)在每組輪廓點陣邊緣.為了創(chuàng)建一系列不同形變級別且適合的目標點陣,每個控制點擁有上、下、左、右4個方向的自由移動以及0.2的移動步長.8個(或6個)控制點的移動循序以及方向被隨機設定.在本實驗中,TPS空間變換被用于使用這8個(或6個)控制點使前述源點陣發(fā)生形變創(chuàng)建新目標點陣.因為被移動的控制點數量反映了點陣的形變大小,所以本實驗中形變級別被定義為移動控制點的數量(二維和三維情況下的最大形變級別分別為8和6).

2)噪音比:我們通過利用均值為0且標準偏差從0.01至0.05的高斯白噪聲(Gaussian white noise)創(chuàng)建了5個噪音級別的目標點陣.

3)旋轉角度:我們認為在適當旋轉下的配準性能測試是必要的,因為通常形變發(fā)生時都會伴隨著旋轉.但是過大旋轉會導致相關算法產生不穩(wěn)定或無價值的配準結果,所以我們主要專注于在以15°為間隔,旋轉?30°到30°的情況下的配準性能測試.在三維配準實驗中,源點陣被沿Z軸旋轉來創(chuàng)建新目標點陣.

誤差測量:在誤差測量中,通?？梢赃x擇的測量方法很多.例如,正確匹配百分比、配準后點陣之間的平均距離等.為了保證直接和公平的比較,我們遵循了TPS-RPM與CPD中的誤差測量法,即代理點陣與目標點陣之間平均距離的平方.

性能評估:平均誤差(即100次測試中的平均距離平方與標準偏差)在本實驗中被用來比較不同算法之間的配準性能.對于每組點陣,在每種形變級別、噪音比、旋轉角度下執(zhí)行了100次的隨機實驗.

3.2 二維輪廓點陣的配準結果

在第一系列的實驗中,我們在不同的二維人造輪廓點陣上評估了本文算法的性能.與后面的序列圖像(CMU sequences and Pascal 2007 challenge)以及真實圖像特征點(Pascal 2007 challenge)配準相比,這些二維輪廓點陣擁有更多的點數以及較密的點陣分布.在這類點陣配準中,由于相鄰點彼此靠近且擁有相似的局部結構特征,所以在評價各點的局部特征結構相似度時變得更加困難.本文算法與相關算法的比較結果如下.

3.2.1 Line

在點陣Line的配準測試中,本文算法僅與TPS-RPM 進行對比測試.因為其他算法并沒有在該點陣上進行測試并公布相關的參數設定.性能測試統(tǒng)計數據(平均誤差與標準偏差)展示在圖1的第1行.本文算法在所有的實驗中展現(xiàn)了準確的配準結果,并且在所有形變級別、噪音比、旋轉角度的測試中,給出了最優(yōu)的配準結果.圖2給出了本文算法的一個配準實例.

3.2.2 Fish 1

在點陣Fish 1的配準測試中,我們測試了本文算法與CPD,TPS-RPM和GMMREG的性能,圖1的第2行展示了測試結果.這4種算法均給出了準確的配準結果,本文算法在所有的形變級別和所有旋轉角度的測試中展現(xiàn)了最優(yōu)的性能結果.在目標點陣含有噪音的配準測試中,這四種算法均展現(xiàn)了準確的配準結果,GMMREG表現(xiàn)得更好.圖3給出了本文算法的一個配準實例.

3.2.3 Chinese character

在點陣Chinese character的配準測試中,本文算法僅與TPS-RPM進行對比實驗.因為CPD與GMMREG并未在非剛性配準中測試過該點陣(GMMREG僅在剛性配準中測試過該點陣).本文算法在所有形變級別、噪音比從0.01至0.03、所有旋轉角度的測試中給出了最優(yōu)的配準結果.圖4給出了一個本文算法的配準實例.

3.2.4 Fish 2

本文算法與CPD的性能測試結果展示在圖1的第4行.本文算法在所有的實驗中展現(xiàn)了準確的配準結果,并且在所有形變級別、噪音比以及旋轉角度的測試中給出了最優(yōu)的配準性能.圖5給出了本文算法的一個配準實例.

圖1 二維輪廓點陣配準下的性能對比(誤差線表示了100次隨機測試中平均誤差的標準偏差值.從第1行至第4行分別為點陣Line,Fish 1,Chinese character以及Fish 2的實驗結果.)Fig.1 Comparison of our results against CPD,TPS-RPM and GMMREG on 2D contour point set registration(The error bars indicate the standard deviations of the mean errors in 100 random experiments.From the top row to bottom row are:Line,Fish 1,Chinese character and Fish 2,respectively.)

在二維輪廓點陣配準測試中,所有的算法均給出了準確的配準結果,但是本文算法在形變與旋轉測試中明顯地超越了相關算法.

3.3 三維人臉點陣的配準結果

在第二系列的實驗中,我們評估了本文算法在三維配準中的性能.本實驗中使用的3D face點陣已被CPD和GMMREG等算法用于測試其在三維配準中的性能.圖6給出了本文算法與CPD、GMMREG算法的性能測試結果.本文算法在所有實驗中給出了準確的配準結果,同時在所有形變級別、噪音比從0.01至0.04以及所有旋轉角度的實驗中給出了最優(yōu)的性能結果.圖7給出了一個本文算法的配準實例.

3.4 序列圖像的配準結果

在第三系列的實驗中,我們測試了本文算法在序列圖像特征點配準問題上的性能.與二維和三維人造點陣相比,序列圖像擁有更少的特征點,這些點稀疏地分布在圖像中.CMU house和CMU hotel序列圖像是目前用于測試基于Graph的學習算法最流行的實驗數據.兩個序列圖像分別由111和101幅圖組成,每幅圖擁有30個標記的特征點.在本實驗中,我們使用正確配準點數的百分比(稱為配準率)為誤差測量法.

圖2 本文算法的配準實例:LineFig.2 Registration examples on Line point set

圖3 本文算法的配準實例:Fish 1Fig.3 Registration examples on Fish 1 point set

圖4 本文算法的配準實例:Chinese characterFig.4 Registration examples on Chinese character point set

圖5 本文算法的配準實例:Fish 2Fig.5 Registration examples on Fish 2 point set

圖6 三維Face輪廓點陣配準下的性能對比(誤差線表示了100次隨機測試中平均誤差的標準偏差值.)Fig.6 Comparison of our results against CPD and GMMREG on 3D face contour point set registration (The error bars indicate the standard deviations of the mean errors in 100 random experiments.)

圖7 3D face點陣配準實例Fig.7 Registration examples on 3D face point set

本文算法與三種基于 Graph的學習算法[10,13?14],一種基于Graph的非學習算法[9],和三種基于迭代的算法[16,25,31]分別在這兩組序列圖像的所有配準可能中進行了性能對比實驗.

表2展示了實驗結果.在House序列圖像的配準中,對于Caetano等[10]與Zhou等[9],我們報告了他們公布的配準率的上限值,對于Leordeanu等[13]、Torresani等[14]和Wang等[31],我們給出了他們公布的配準率.本文算法,Wang等[31]和Torresani等[14]給出了完美的配準結果,也超越了其他算法.但是從算法運行時間角度來看,本文算法的運行時間(平均0.049秒)比Torresani等公布的平均運行時間4.8秒[14]快了很多(該對比也考慮了使用電腦的性能問題).在CMU hotel序列圖像的配準中,Wang等[14,31]與Zhou等[9]沒有提供他們的實驗結果.與CPD,GMMREG,Leordeanu等[13]和Caetano等[10]相比較,本文算法展現(xiàn)了更好的配準精度.圖8給出了本文算法的兩個配準實例.

表2 CMU house和CMU hotel序列圖像中所有可能的圖像配準結果(%)Table 2 Matching rates on the CMU house and CMU hotel for all possible image pairs(%)

圖8 CMU house與CMU hotel配準實例Fig.8 Registration examples on CMU house and CMU hotel

3.5 圖像特征點的配準結果

在第四系列的實驗中,我們使用Leordeanu等[13]的測試數據測試了本文算法的性能.這套測試數據集從Pascal 2007 challenge數據庫中挑選出來的,包含30對汽車圖像與20對摩托車圖像.每對圖像中包含30～60個特征點.本文算法與CPD, GMMREG,Zhou等[9]和Leordeanu等[13]進行了性能對比,其結果在表3中列出,對于Zhou等[9](A)和Leordeanu等[13](B),我們報告了他們公布的實驗結果.本文算法給出了最優(yōu)的配準率.圖9給出了本文算法的兩個配準實例.

表3 汽車與摩托車圖像庫的配準結果(%)Table 3 Matching rates on cars and motorbikes(%)

3.6 計算復雜度

本文算法的計算復雜度主要與兩個方面相關: 1)決定收斂性的能量權重調節(jié)參數Tinit,Tfinal與r;2)用于求解基于混合特征的能量優(yōu)化方程的線性分配算法.

3.6.1 收斂范圍

收斂范圍主要與形變級別和能量權重調節(jié)參數設定相關.在其他相關算法中,TPS-RPM的收斂范圍由退火算法決定,CPD和GMMREG則分別由容差停止準則(Tolerance stopping criterion)以及最大迭代次數所決定.我們調查了上述這四種算法在點陣Chinese character形變實驗中的收斂范圍.本文算法、TPS-RPM、CPD與GMMREG的參數設定值遵循前述Fish1實驗中的設定值.CPD和TPS-RPM分別平均需要43次與85次迭代來完成整個配準過程,而GMMREG則需要最大迭代次數(100次)才能完成配準.原因是由于容差停止準則被設定為10?10,GMMREG在配準中最小化后的L2距離很難達到該標準.本文算法僅需要17次迭代就可以完成配準.

圖9 Pascal 2007 challenge配準實例Fig.9 Registration examples on Pascal 2007 challenge

此外,我們也調查了本文算法在不同能量權重調節(jié)參數設定下的收斂范圍.圖10給出了在Chinese character點陣形變實驗中的例子.對于每一個能量權重調節(jié)參數設定值,我們在每一個形變級別下運行了100次隨機實驗.基于圖10展示的實驗結果,隨著調節(jié)初始值Tinit降低為默認值的1/10時,本文算法的性能發(fā)生了輕微的退化,配準所需迭代次數減少了41%(平均迭代次數從17次減少至10次);隨著最終值Tfinal增加為默認值的10倍時,本文算法的性能發(fā)生了退化,配準所需迭代次數減少了41%(平均迭代次數從17次減少到10次);隨著調節(jié)速率r減少為默認值的1/2,本文算法的性能輕微退化,配準所需迭代次數減少了65%(從17次減少至僅需6次).即便能量權重調節(jié)參數被顯著地改變了,所有的實驗依舊展現(xiàn)了非常高的配準精度(也就是誤差低于0.0013且標準偏差在±0.0015之內).基于這些結果,本文算法的計算復雜度可以通過調整能量權重調節(jié)參數設定大幅降低,同時算法依舊維持了很高的配準精度.

圖10 不同能量權重調節(jié)參數設定下的配準性能Fig.10 Relationships between performances and different energy tradeoff adjustment parameter settings

3.6.2 Jonker-Volgenant算法性能

為了使用線性分配技術求解二值對應矩陣M,本文算法使用了Jonker-Volgenant算法[32],該算法提供了O(N3)的計算復雜度.我們在一臺4GB內存和2.67GHz Intel(R)Xeon(R)CPU的電腦上使用Matlab mex function功能測試了C++代碼的Jonker-Volgenant算法性能.表4給出了使用Jonker-Volgenant算法求解不同大小的二值對應矩陣所需時間.Jonker-Volgenant算法展現(xiàn)了快速的求解能力,同時也為本文算法實現(xiàn)快速非剛性點陣配準提供了支撐.

表4 Jonker-Volgenant算法性能(測試矩陣由Matlab的rand函數自動生成.)Table 4 Performance of Jonker-Volgenant algorithm (The cost matrices were generated by Matlab rand function.)

4 結論

我們已經介紹了一種基于混合特征的非剛性點陣配準算法:1)設計出了一種基于和向量特征的全局結構特征描述算法;2)提出了一種利用點陣之間的局部區(qū)域相鄰點的距離和描述點陣中各點的局部結構特征的描述算法;3)提出一種基于混合特征的能量方程并設計了該方程的能量權重調節(jié),該方程允許使用混合特征進行點陣對應評估.最后將本文算法與8種當前典型算法進行了性能對比測試,本文算法在絕大多數的形變和旋轉配準情況中展現(xiàn)了最好的配準結果.

致謝

感謝Chui Hai-Li,Rangarajan Anand,Myronenko Andriy,Song Xu-Bo,Jian Bing,Vemuri Baba,Zhou Feng,De la Torre Fernando, Leordeanu Marius,Torresani Lorenzo和Caetano Tiberio提供了他們的算法源代碼和測試數據.這極大地促進了對比實驗.我們無償提供本文算法的Matlab源代碼供學術研究.

1 Park S H,Lee K M,Lee S U.A line feature matching technique based on an eigenvector approach.Computer Vision and Image Understanding,2000,77(3):263?283

2 Kong W X,Kimia B B.On solving 2D and 3D puzzles using curve matching.In:Proceedings of the 2001 IEEE Conference on Computer Vision and Pattern Recognition.Kauai, HI,USA:IEEE,2001.II-583?II-590

3 Cochran S D,Medioni G.3-D surface description from binocular stereo.IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(10):981?994

4 Belongie S,Malik J,Puzicha J.Shape matching and object recognition using shape contexts.IEEE Transactions on Pattern Analysis and Machine Intelligence,2002,24(4): 509?521

6 Balakrishnan V.Graph Theory(lst Edition).New York: McGraw-Hill,1997.

7 Sundar H,Silver D,Gagvani N,Dickinson S.Skeleton based shape matching and retrieval.In:Proceedings of the 2003 Shape Modeling International(SMI'03).Seoul,South Korea:IEEE,2003.130?139

8 Zheng Y F,Doermann D.Robust point matching for nonrigid shapes by preserving local neighborhood structures. IEEE Transactions on Pattern Analysis and Machine Intelligence,2006,28(4):643?649

9 Zhou F,De la Torre F.Factorized graph matching.In:Proceedings of the 2012 IEEE Conference on Computer Vision and Pattern Recognition.Providence,RI:IEEE,2012. 127?134

10 Caetano T S,Cheng L,Le Q V,Smola A J.Learning graph matching.In:Proceedings of the 11th IEEE International Conference on Computer Vision.Rio de Janeiro,Brazil: IEEE,2007.1?8

11 Leordeanu M,Hebert M.Smoothing-based optimization.In: Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition.Anchorage,AK:IEEE,2008. 1?8

12 Caetano T S,McAuley J J,Cheng L,Le Q V,Smola A J.Learning graph matching.IEEE Transactions on Pattern Analysis and Machine Intelligence,2009,31(6):1048?1058

13 Leordeanu M,Sukthankar R,Hebert M.Unsupervised learning for graph matching.International Journal of Computer Vision,2012,96:28?45

14 Torresani L,Kolmogorov V,Rother C.A dual decomposition approach to feature correspondence.IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(2): 259?271

15 Xiao D,Zahra D,Bourgeat P,Berghofer P,Tamayo O A, Wimberley C,Gregoire M C,Salvado O.An improved 3D shape context based non-rigid registration method and its application to small animal skeletons registration.Computerized Medical Imaging and Graphics,2010,34(4):321?332

16 Jian B,Vemuri B C.Robust point set registration using Gaussian mixture models.IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(8):1633?1645

17 Chui H L,Rangarajan A.A new point matching algorithm for non-rigid registration.Computer Vision and Image Understanding,2003,89(2?3):114?141

18 Rangarajan A,Chui H,Bookstein F L.The softassign procrustes matching algorithm.In:Proceedings of the 15th International Conference on Information Processing in Medical Imaging.Poultney,Vermont,USA:Springer,1997. 29?42

19 Chui H L,Rambo J,Duncan J,Schultz R,Rangarajan A. Registration of cortical anatomical structures via robust 3D point matching.In:Proceedings of the 16th International Conference on Information Processing in Medical Imaging. Visegrd,Hungary:Springer,1999.168?181

20 Gold S,Rangarajan A,Lu C P,Pappu S,Mjolsness E.New algorithms for 2D and 3D point matching:pose estimation and correspondence.Pattern Recognition,1998,31(8): 1019?1031

21 Yuille A L.Generalized deformable models,statistical physics,and matching problems.Neural Computation,1990, 2(1):1?24

22 Bookstein F L.Principal warps:thin-plate splines and the decomposition of deformations.IEEE Transactions on Pattern Analysis and Machine Intelligence,1989,11(6): 567?585

23 Myronenko A,Song X B,Carreira-Perpin M.Non-rigid point set registration:coherent point drift.In:Proceedings of the 2006 Advances in Neural Information Processing Systems 19.Cambridge,MA:MIT Press,2006.1009?1016

24 Yuille A L,Grzywacz N M.A mathematical analysis of the motion coherence theory.International Journal of Computer Vision,1989,3(2):155?175

25 Myronenko A,Song X B.Point set registration:coherent point drift.IEEE Transactions on Pattern Analysis and Machine Intelligence,2010,32(12):2262?2275

26 Greengard L,Strain J.The fast Gauss transform.SIAM Journal of Scientific and Statistical Computing,1991,12(1): 79?94

27 Markovsky I.Structured low-rank approximation and its applications.Automatica,2008,44(4):891?909

29 Ma J Y,Zhao J,Tian J W,Tu Z W,Yuille A L.Robust estimation of nonrigid transformation for point set registration. In:Proceedings of the 2013 IEEE Conference on Computer Vision and Pattern Recognition.Portland,OR:IEEE,2013. 2147?2154

30 Scott D W.Parametric statistical modeling by minimum integrated square error.Technometrics,2001,43(3):274?285

31 Wang G,Wang Z C,Chen Y F,Zhao W D.A robust nonrigid point set registration method based on asymmetric Gaussian representation.Computer Vision and Image Understanding,2015,141:67?80

32 Jonker R,Volgenant A.A shortest augmenting path algorithm for dense and sparse linear assignment problems. Computing,1987,38(4):325?340

33 Miller M L,Stone H S,Cox I J.Optimizing Murty's ranked assignment method.IEEE Transactions on Aerospace and Electronic Systems,1997,33(3):851?862

34 Wahba G.Spline Models for Observational Data.Philadelphia:SIAM,1990.

湯昊林 云南師范大學信息學院本科生.主要研究方向為圖像配準以及醫(yī)學圖像處理.

E-mail:m18487107138@163.com

(TANGHao-Lin Undergraduate student at the School of Information Science and Technology,Yunnan Normal University. His research interest covers non-rigid point set registration and medical imaging.)

楊 揚 云南師范大學信息學院講師. 2007年獲得日本早稻田大學計算機碩士學位,2013年獲得新加坡國立大學NGS博士學位.主要研究方向為醫(yī)學圖像處理,圖像配準,地理空間信息技術,人體咀嚼系統(tǒng).本文通信作者.

E-mail:yyang_ynu@163.com

(YANG Yang Lectureratthe School of Information Science and Technology,Yunnan Normal University.He received his master degree from Waseda University,Japan in 2007,and Ph.D.degree from National University of Singapore,Singapore in 2013.His research interest covers medical image processing,image registration,geography information system and human masticatory system.Corresponding author of this paper.)

楊 昆 云南師范大學信息學院教授, 1998年獲得澳大利亞新南威爾士大學碩士學位.主要研究方向為地理信息系統(tǒng),遙感圖像處理.

E-mail:kmdcynu@163.com

(YANG Kun Professoratthe SchoolofInformation Science and Technology,Yunnan Normal University.He received his master degree from University of New South Wales,Australia in 1998.His research interest covers geographic information system(GIS)and remote sensing image processing.)

羅 毅 云南師范大學信息學院軟件工程系講師.2014年獲得哈爾濱理工大學博士學位.主要研究方向為無線傳感器網絡,微弱信號拾取,視覺檢測技術.

E-mail:luoyi861030@163.com

(LUO Yi Lecturer in the Department of Software Engineering,Yunnan Normal University. He received his Ph.D.degree from Harbin University of Science and Technology in 2014.His research interest covers wireless sensor networks,weak signal detection,and visual detection.)

張雅瑩 云南師范大學信息學院本科生.主要研究方向為非剛性點陣配準和醫(yī)學圖像處理.

E-mail:nw_zhyaying@163.com

(ZHANG Ya-Ying Undergraduate student at the School of Information Science and Technology,Yunnan Normal University.Her research interest covers non-rigid point set registration and medical imaging.)

張芳瑜 云南師范大學信息學院本科生.主要研究方向為非剛性點陣配準和醫(yī)學圖像處理.

E-mail:zhfangyu_ynu@163.com

(ZHANG Fang-Yu Undergraduate student at the School of Information Science and Technology,Yunnan Normal University.Her research interest covers non-rigid point set registration and medical imaging.)

Non-rigid Point Set Registration with Mixed Features

TANG Hao-Lin1YANG Yang1,2YANG Kun1,2LUO Yi1,2ZHANG Ya-Ying1ZHANG Fang-Yu1

We present a novel non-rigid point set registration method with mixed features.The proposed method is designed by an alternating two-step process:correspondence estimation and transformation updating.We first design a global and a local feature descriptors for assessing the global and local structural differences between two point sets, respectively.The two feature descriptors are then combined for forming a mixed feature based energy function,so as to provide a flexible way to estimate correspondences by minimizing global or local structural differences using a linear assignment solution.To improve the interactions between the two steps,a tradeoff of energy adjustment is used to gradually adjust the energy minimization from local to global structural differences and the thin plate spline transformation from rigid to non-rigid during registration.We evaluate the performances of our method in contour registration,sequence images and real images;through comparision with other eight state-of-the-art methods,our method shows the best alignments in most deformation and rotation scenarios.

Non-rigid,point set registration,mixed features,correspondence estimation,transformation updating

湯昊林,楊揚,楊昆,羅毅,張雅瑩,張芳瑜.基于混合特征的非剛性點陣配準算法.自動化學報,2016,42(11): 1732?1743

Tang Hao-Lin,Yang Yang,Yang Kun,Luo Yi,Zhang Ya-Ying,Zhang Fang-Yu.Non-rigid point set registration with mixed features.Acta Automatica Sinica,2016,42(11):1732?1743

2015-10-10 錄用日期2016-05-16

Manuscript received October 10,2015;accepted May 16,2016

國家高技術研究發(fā)展計劃(863計劃)(2012AA121402),云南省教育廳科學研究項目 (2015Z069),云南師范大學博士科研啟動基金 (01000205020503065),云南師范大學大學生科研訓練基金(0100060502006)資助

Supported by National High Technology Research and Development Program of China(863 Program)(2012AA121402),Key Scientific Research Project of Education Department of Yunnan Province(2015Z069),Doctoral Scientific Research Foundation of Yunnan Normal University(01000205020503065),College Students'Scientific Research Training Project of Yunnan Normal University(0100060502006)

本文責任編委朱軍

Recommended by Associate Editor ZHU Jun

1.云南師范大學信息學院昆明650092 2.西部資源環(huán)境地理信息技術教育部工程研究中心昆明650092

1.School of Information Science and Technology,Yunnan Normal University,Kunming 650092 2.The Engineering Research Center of GIS Technology in Western China,Kunming 650092

DOI 10.16383/j.aas.2016.c150618