融合空間聚類與結構特征的點集配準優化算法

胡 欣,向迪源,秦 皓,肖 劍

(1.長安大學 能源與電氣工程學院,陜西 西安 710064;2.長安大學 電子與控制工程學院,陜西 西安 710064)

1 引 言

點集配準是計算機視覺和模式識別領域的關鍵問題和瓶頸技術,將多源、多時段、多視場的圖像點集配準就是尋找空間變換能夠最優對準兩幅圖像[1-3]。為尋找準確的點與點的對應關系,點集配準根據變換方式的不同可分為剛性配準和非剛性配準[4]。剛性點集配準的變換方式包括縮放、平移和旋轉,屬于全局變換且涉及參數少。而非剛性點集配準的變換方式往往是未知的、復雜的,且難以建模,通常包含較多的變換參數,無法以簡單的參數化方式建模[5-6]。

近年來,將密度估計算法生成的模型引入到非剛性匹配中的方法被廣泛研究。TSIN等[7]和GLAUNES等[8]首先提出用函數對點集進行建模,函數中擁有平滑機制,使得算法在處理噪音和異常值時具有優勢,但模型函數的選擇依舊有待優化。在此基礎上,JIAN等[9]引入了高斯混合模型(Gaussian Mixed Model,GMM)搭建模型框架,但仍存在初始值敏感的問題。為此,CAMPBELL等[10]提出了使用支持向量參數擬合GMM模型數據,但算法性能在復雜變換函數中受限。由MYRONENKO等[11]首先提出的相干點漂移(Coherent Point Drift,CPD)算法是基于GMM和期望最大化(Expectation-Maximization,EM)算法,在點集配準中被越來越多的使用,其實質是將匹配問題轉換為最大似然估計問題,由于存在初始值敏感和局部極值問題,研究者基于CPD算法提出了許多改進算法[12-15]。JIAN等[16]將匹配的思想從擬合高斯混合模型擴展到對齊兩個高斯混合模型。MA等[17]提出了基于高斯混合模型的矢量場一致性(Vector Field Consensus,VFC)算法。以上算法在高斯混合模型解決點集對應問題中僅考慮了全局運動一致性約束條件,沒有考慮局部特征。隨后,YANG等[18]提出了混合特征的全局和局部混合距離-薄板樣條方法(Global and Local Mixture Distance-Thin Plate Spline,GLMDTPS)。MA等[19]提出了保持全局和局部結構特征的點集對齊算法(Point set Registration both Global and Local Structures,PR-GLS)。JIANG等[20]提出了基于離群點空間聚類的魯棒特征匹配算法(Robust Feature Matching using Spatial Clustering of Applications with Noise,RFM-SCAN)。彭磊等[21]提出了考慮鄰域信息和考慮全局與局部相似度測度的非剛性點集配準算法,算法利用點集局部特征的一致性作為先驗約束,將尋找正確匹配點過程轉化為概率密度來解決點集對齊問題。近年來,HIROSE[22]改進了CPD算法,并提出相干點漂移的貝葉斯公式(Bayesian formulation of Coherent Point Drift,BCPD),在貝葉斯公式中加入相干點漂移,增強了對目標旋轉的魯棒性。ZHU等[23]從期望最大化的角度提出了多視圖配準問題的新解決方案。WANG等[24]提出空間相干匹配(Spatially Coherent Matching,SCM)算法,保持局部鄰域結構的同時學習非剛性變換。以上算法中,樣本點的局部特征選擇和局部特征聚類是算法需要解決的關鍵性問題,當局部特征變化不穩定和變形嚴重導致大量異常值出現時,算法的性能和特征會產生差異。在混合模型的框架下,自適應地完成局部聚類和局部特征描述是基于GMM和EM算法完成點集配準的一種思路,也是筆者提出采用局部空間聚類和鄰域結構特征的點集配準優化算法(Point set Registration using Spatial Distance Clustering and Local Structural features,PR-SDCLS)的出發點。

文中提出了一種新穎的融合全局與局部特征的高斯混合點集配準算法。主要貢獻如下:

(1) 通過空間距離矩陣將預匹配聚類為多個運動一致性聚類和一個離群值聚類,并將離群值聚類中的匹配點刪除,減小了算法的復雜度。

(2) 對一致性聚類子集分別使用高斯混合模型擬合和EM算法參數估計,避免了復雜的建模,提高了匹配精度和效率。

(3) 模型擬合的過程中,將描述子與空間距離相結合自適應對混合系數賦值,避免了考慮全局特征時局部特征信息丟失的問題。

2 高斯混合模型

2.1 點集配準與高斯混合模型

采用高斯混合模型GMM求解,實質是轉換為概率密度估計問題。 令X={x1,…,xn}∈RD×N為模板點集,Y={y1,…,ym}∈RD×M為目標點集,將目標點集x作為高斯模型的質心,模板點集y為由GMM產生的數據點。高斯混合模型的概率密度函數為

(1)

其中,當模板點集xi與目標點集yj是D維時,μ為期望,Σ為協方差,則有

(2)

其中,當模板點集xi與目標點集yj是二維時,μ為期望,σ為方差,則有

(3)

由于以上的概率密度函數無法體現目標點集與模板點集中點的對應關系和變換關系,因此在高斯混合模型中引入隱變量Z對模板點集xi與目標點集yj的對應關系進行描述。具體如下:

Z={zm∈NN+1:m∈NN} ,

(4)

其中,

假設離群點的分布為均勻分布1/b。

引入變換函數f:RN→RN,作為模板點集中的點映射到目標點集中的點的函數,將每個高斯模型的質心由模板點xi替代為模板點映射到目標點集平面的點f(xi)。

綜上,由于模板點集xi與目標點集yj均為二維,因此點集對應關系和變換關系的混合模型的概率密度函數表示為

(5)

其中,θ={f,σ2,γ},為未知參數集;γ∈[0,1]代表隱變量的邊緣分布,即P(zm=N+1)=γ。混合系數πmn通常采用等概率賦值,即πmn=1/N。采用貝葉斯準則估計θ的一個最大后驗解,等價于最小化如下的負對數后驗:

(6)

對式(6)求取最大后驗解,變換函數f將從最優解θ*中直接獲取。

2.2 參數估計的EM算法

EM算法是通過迭代求L(θ)=log (Y|θ)的極大似然估計。每次迭代包含兩個步驟:①E步為求期望 ;②M步為求極大值。省略掉負對數后驗函數L(θ|Y)獨立于參數θ的項,得到完全數據對數后驗函數Q,具體表示為

(7)

(1) E步:采用θold求出隱變量的后驗概率。令PM×N為一個M×N的后驗概率矩陣,pmn指ym與xn在當前估計出的變換函數f下的吻合程度:

(8)

在Q函數中考慮與變換函數f相關的項,得到如下一個正則化風險泛函:

(9)

C(Γdiag(1TP)+λσ2I)=YP-xσ2diag(1TP) ,

(10)

其中,1表示一個全1的1×m列向量。將P,λ,σ2等參數帶入式(10),求出系數矩陣C后,即可求出位移函數v(x)和變換函數f(x)。

3 改進方法

非剛性配準中,針對數據退化程度增加導致算法性能下降嚴重的問題,文中提出在考慮全局和局部結構特征的高斯混合模型框架內,引入點集的空間距離聚類和鄰域結構特征,更好地解決點集配準問題。具體來說,就是通過距離進行分類,對每個子集估計混合密度來求解點集配準問題:任取一個點為中心點,并將這個點鄰域內的所有點合并為一個新的子集。分別對每個子集擬合一個高斯混合模型,使其高斯密度的中心與另一個對應子集保持一致。同時,采用點集描述子的局部特征結合特征點與中心點的距離對混合模型每個組成部分的混合系數進行賦值,從而使得在配準時既做到了全局結構特征的匹配,又保持了局部結構特征。

圖1 算法的配準過程

文中算法的匹配過程如圖1所示,對于兩幅存在非剛性數據退化的圖1(A)中,使用運動一致性矢量對其進行描述,如圖1(B)所示,其中實線的運動一致性矢量代表了至少有一個運動矢量與其一致的運動矢量集合,虛線的運動矢量代表了離群的不具備運動一致性的一類。在具有運動一致性的矢量集合中,通過空間距離求出每個運動矢量的鄰域,對每個鄰域分別擬合高斯混合模型,圖1(B)中運動矢量a擬合高斯混合模型的結果如圖1(a)所示,運動矢量b擬合高斯混合模型的結果如圖1(b)所示,剔除不具備運動一致性的運動矢量后的匹配結果如圖1(C)所示。

在圖1中,通過空間距離先剔除不具備運動一致性的運動矢量,同時求出每個運動矢量的鄰域,接著讓每個鄰域分別擬合高斯混合模型,在此基礎上,為了充分挖掘局部結構特征,引入形狀上下文特征,并將匈牙利算法、χ2度量及空間距離相結合修正了高斯混合模型的比例系數。該方案適用于對精度要求較高的點集對齊問題。此外,與現有的相關方案相比,該方案具有更好的魯棒性和效果。綜合性能分析和仿真結果驗證了該方案的有效性和魯棒性。

3.1 點集空間距離聚類

A={ai=(xi,yi,mi)T,i=1,…,H} 。

(11)

為了增強運動一致性,設計一個加權距離,表示如下:

d(ai,aj)=φ(xi,xj)+φ(yi,yj)+ωijφ(mi,mj) ,

(12)

其中,ωij為權重參數,定義為ωij=1+γexp(-min{φ(xi,xj),φ(yi,yj)}),γ為正數,用于增強相鄰點間的運動一致性,文中由經驗取γ=10。φ(x,y)為距離函數,文中采用歐式距離。

因此,可以計算出H×H的距離矩陣D:

Dij=d(ai,aj) 。

(13)

首先,令μ為每個中心點鄰域內的采樣點與圖片上總采樣點的比率。然后,對距離矩陣按列進行歸一化處理,把第i列中元素小于μ的元素所對應的行數的數據當作第i類分類,即第i個子集,共得到H個子集。

3.2 混合模型

令第i個子集內有Ni對點,其中模板點集為X′={x′1,…,x′Ni}∈RD×Ni,目標點集為Y′={y′1,…,y′Ni}∈RD×Ni,第i個子集配準的高斯混合模型的概率密度函數為

(14)

在式(5)中混合系數πmn表示目標點ym歸屬于高斯密度中心f(xn)的概率,通常采用等概率賦值,即πmn=1/N。但是,在非剛性點集配準問題中,挖掘局部結構特征并將局部結構特征融入混合模型也是至關重要的。因此文中采用形狀上下文(shape context)作為子集的特征描述子,將匈牙利算法結合χ2度量與子集內觀測點到中心點的距離相結合來初始化混合系數π′mn,目標點y′m有對應的模板點,具體表示為

(15)

其中,τ∈[0,1]為特征匹配可信度,I為y′m對應的模板點集,|I|為點集I的大小。

如果目標點y′m沒有對應的模板點,那么對混合系數π′mn等概率賦初值為π′mn=1/(NiDmn)。混合系數π′mn能在配準時同時保持點集的全局與局部結構特征。結合式(8),可獲得第i個子集的后驗概率矩陣Pi:

(16)

得到協方差和離群點的比率為

(17)

一旦EM算法收斂,就能得到最優的變換函數f,此外也能得到內點的一個估計。首先在此處設置一個閾值TH,然后找到每一個模板子集的中心點和其對應目標子集的所有點的后驗概率的最大值pimax。因此,一致集F表示為

F={i:pimax>TH,i∈NN} 。

(18)

由于改進的非剛性點集配準算法同時挖掘全局與局部結構特征,因此將其命名為基于空間距離聚類與局部特征的魯棒點集配準算法(PR-SDCLS)。算法的具體流程見算法1。

算法1基于距離分類與高斯混合模型點集配準算法。

輸入:兩個點集X和Y,參數γ,λ,β,μ,TH

輸出:一致集F

② 計算距離矩陣D

③ 根據比率μ求得H個子集

④ loopi=i+1

⑤ repeat

⑥ E步

⑦ 找到變形后模板點集f(X′)的特征描述子

⑧ 建立f(X′)與Y′之間的關系

⑨ 基于特征匹配和距離初始化混合系數π′mn

⑩ 更新后驗概率p′mn

3.3 基于空間聚類的加速算法

在PR-SDCLS中,需要對每一個點及其鄰域的子集擬合高斯混合模型,對于點集配準問題,尤其是三維點云來說,數據中點的數量極多,會造成計算復雜度過高導致計算上的不可行,為了解決這個問題,在算法2步驟②計算距離矩陣D之后,利用空間距離矩陣D,將假定的匹配自適應地聚類為多個運動一致性聚類和一個離群值聚類。在后續過程中,只需刪除離群值聚類,并對多個運動一致性聚類中的點所對應的子集擬合高斯混合模型,此時得到H′個子集(算法2步驟③,刪除了離群值聚類后,導致預匹配對減少,即H′≥H)。加速后算法具體流程見算法2。

算法2基于距離分類與高斯混合模型加速點集配準算法。

輸入:兩個點集X和Y,參數γ,λ,β,μ,TH,ε

輸出:一致集F。

② 計算距離矩陣D

③ 根據距離ε和距離矩陣D,將假定的匹配聚類為多個運動一致性聚類和一個離群值聚類,刪除離群值聚類

④ 根據比率μ求得H′個子集

⑤ loopi=i+1

⑥ repeat

⑦ E步

⑧ 找到變形后模板點集f(X′)的特征描述子

⑨ 建立f(X′)與Y′之間的關系

⑩ 基于特征匹配和距離初始化混合系數π′mn

4 實 驗

為了估計PR-SDCLS算法的性能,采用3個不同的實驗條件:非剛性點集、調整加權距離和調整混合系數。使用MATLAB代碼實現了改進的算法,實驗配置為2.50 GHz Intel(R) Core(TM) i5-7200U CPU,內存為4.00 GB的筆記本。

公共數據集采用兩個不同結構模型[25-26]:魚和漢字“福”。圖2所示為數據集在旋轉、變形、噪聲,遮擋和異常值5方面的數據退化結果。其中,旋轉退化是完成非線性變形,并使用地真校正,分為6級旋轉,即0°、30°、60°、90°、120°和180°;變形退化,分為5級變形,即0.02、0.035、0.05、0.065、0.08;噪聲退化,即為加入噪聲,分為6級噪聲級別,即0、0.01、0.02、0.03、0.04、0.05;遮擋退化,是完成適度非線性變形后隨機刪除一定量數據,分為6級遮擋級別,即0%、10%、20%、30%、40%和50%;異常值退化,是進行適度非線性形變后加入服從均勻分布的不同比例的異常值,分為5級異常值比例級別,即0、0.5、1、1.5、2。實驗每種退化類型對應生成100個樣本作為點集配準的目標數據。

圖2 不同結構模型數據集的數據退化結果

4.1 非剛性配準的結果

圖3 PR-SDCLS算法在不同退化類型下的配準結果

將文中PR-SDCLS算法與4類性能良好的PR-GLS、RFM-SCAN、VFC、CPD算法比較,圖4給出了在不同退化類型下算法配準結果的平均誤差,圖中每種退化類型使用退化參數作為橫坐標,平均誤差作為縱坐標。旋轉退化中PR-GLS、RFM-SCAN、CPD、PR-SDCLS算法在旋轉角度小于30°時可以取得相似的效果,但在旋轉角度大于30°時,PR-GLS、RFM-SCAN、VFC、CPD配準效果迅速退化,文中提出的PR-SDCLS算法卻并不受這類數據退化的影響。變形退化中,VFC的配準效果遠差于其他4類算法,RFM-SCAN在變形程度大于0.05時,配準效果迅速退化,PR-GLS、RFM-SCAN、PR-SDCLS在任意變形程度下,都能取得相似的結果,所提PR-SDCLS仍然能取得最優的結果。噪聲退化中,VFC并不受這類數據退化的影響,但它的配準效果明顯差于其他算法,RFM-SCAN在噪聲水平大于0.02時,配準效果迅速退化,PR-GLS、RFM-SCAN、PR-SDCLS在任意噪聲水平下,都能取得相似的結果,所提PR-SDCLS算法仍然能取得最優結果。遮擋退化中,PR-GLS、RFM-SCAN、VFC、CPD隨著遮擋比率的增大配準效果衰減明顯,所提PR-SDCLS表現出了很強的魯棒性。離群點退化中,VFC并不受這類數據退化的影響,但它的配準效果明顯差于其他算法,PR-GLS、RFM-SCAN、PR-SDCLS在任意離群點和樣本數量的比率下,取得的結果都相似,PR-SDCLS在任意比率下配準效果都明顯優于其他算法。因此,PR-SDCLS算法通過有效保持點集的全局與局部結構特征,其對各類非剛性點集配準問題——無論是形變、噪聲、離群點、旋轉,還是遮擋,均能很好地解決。表1給出了在不同退化類型下算法配準結果平均誤差的均值,文中PR-SDCLS算法至少降低了約1.477 1%的平均誤差,最多降低了約72.454 8%的平均誤差,驗證了算法在非剛性配準中具備良好的性能和魯棒性。

圖4 算法在不同退化類型配準結果誤差的平均統計性能

表1 算法在不同退化類型配準結果平均誤差的均值

4.2 調整加權距離

調整加權距離測試PR-SDCLS算法性能,算法中引入運動矢量增強了運動一致性,但帶來了冗余。為了測試加權距離的性能,調整4種不同的噪聲觀測數據集A和加權距離,分別為

(19)

圖5給出了對應的平均距離曲線(分別用D12,D13,D23,D123表示ai=(xi,yi)T,ai=(xi,mi)T,ai=(yi,mi)T,ai=(xi,yi,mi)T時的平均距離),在不同變形中的平均誤差的均值在表2中給出,文中PR-SDCLS算法不同A值時至少降低了約0.199 2%的平均誤差,最多降低了約51.640 2%的平均誤差,驗證了算法在非剛性配準中具備良好的性能和魯棒性。

圖5 PR-SDCLS算法在不同A值時在不同退化類型下配準結果誤差的平均統計性能

表2 PR-SDCLS算法中不同P值在不同退化類型下平均誤差的均值

顯然,在任意變換情況下使用Pi=(xi,yi,mi)T的性能最好。噪聲退化中Pi=(xi,mi)T和Pi=(yi,mi)T的性能相似,Pi=(xi,yi)T的性能最差,這和文中的預測一致,mi的引入增強了運動一致性。在其他退化中,Pi=(xi,mi)T和Pi=(yi,mi)T的性能相似,Pi=(xi,yi,mi)T的性能最好,但Pi=(xi,yi)T的性能并不是最差的。

可以得出結論:①特征點的空間位置xi和yi通常具有高度相關性。 使用運動矢量mi可以消除這種相關性,因此可以增加數據的可分性。 ②在同等維度1/2空間,mi的引入雖然可以增強運動一致性,但也造成了數據的冗余。 ③使用Pi=(xi,mi)T和Pi=(yi,mi)T能實現相似的性能,因為它們在數據空間中呈現相似的結構。 ④通過使用Pi=(xi,yi,mi)T,輸入數據被放入更高的維度空間,通常可以進一步增加數據的可分性。因此,它能實現最佳的性能。

4.3 調整模型混合系數

測試PR-SDCLS算法中混合系數的性能,大多數初始化混合系數πmn采用等概率賦值設定為系數1;HORAUD等[12]提出的保持全局和局部結構特征的點集對齊算法中,通過形狀上下文結合匈牙利算法對混合系數進行賦值,設定為系數2;文中采用π′mn,設定為系數3:圖6給出了3個系數在不同退化類型的配準結果的誤差統計。在不同變形中的平均誤差的均值在表3中給出。對圖6的結果分析,在數據形變程度不大時,3種系數可以取得相似的效果,但在數據形變程度較大時,使用系數3的性能最優,系數2的性能次之,系數1的性能最差。從表3可以看到,系數3在所有數據退化的情況下均明顯優于其它兩種系數,文中PR-SDCLS算法在不同混合系數的情況下至少降低了約0.138 9%的平均誤差,最多降低了約14.453 6%的平均誤差,驗證了算法在非剛性配準中具備良好的性能和魯棒性。

圖6 PR-SDCLS算法中不同混合系數在不同數據退化類型下配準結果誤差的平均統計性能

表3 PR-SDCLS算法中不同混合系數在不同退化類型下平均誤差的均值

可以得出:①系數2和系數3作為高斯混合模型的混合系數并不是以一個先驗進行賦值,而是依賴于具體數據進行賦值。因此系數2和系數3可以在配準時同時保持點集的全局與局部結構特征,從而達到更好的性能。但是系數1進行等概率賦初,沒有考慮到數據的局部結構特征,僅依靠PR-SDCLS算法中的基于距離進行局部分類,顯然不能取得最好的效果。②系數3跟系數2相比,系數3在保持局部結構特征時不僅引入了形狀上下文作為特征描述子和匈牙利算法χ2度量,還引入了觀測點到中心點的局部空間距離。因此系數3的性能優于系數1。

5 結束語

實驗中,通過調整兩類參數,在不同數據退化類型下算法至少降低了約1.477 1%的平均誤差,最多降低了約72.454 8%的平均誤差,且平均降低了約42.053 8%驗證了算法在非剛性配準中具備良好的性能和魯棒性。文中所提出的這種新穎的基于高斯混合模型的點集配準算法,融合了兩個對應點集間穩定的局部和全局約束。由于引入空間距離分類,所提算法可忽略點集的復雜程度,將復雜和難以建模的點集有效分解為多個簡單的點集擬合;同時采用了點集中特征描述符來提高模型擬合度。非剛性點集下配準的實驗結果表明,文中算法在面對不同數據退化的點集配準結果良好,算法性能魯棒性強、精度高。