基于LDQPSO算法的非剛體配準(zhǔn)

顏翠翠++王浩軍++袁觀娜

DOI：10.16661/j.cnki.1672-3791.2017.22.236

摘 要：如何快速準(zhǔn)確地實現(xiàn)匹配一直是非剛體配準(zhǔn)領(lǐng)域極具挑戰(zhàn)性的問題。針對該問題，該文提出一種快速、高精度的非剛體配準(zhǔn)方法——基于LDQPSO的非剛體配準(zhǔn)算法。首先針對QPSO算法過早收斂的缺點，采用線性自適應(yīng)策略對QPSO慣性權(quán)重因子進行更新，提出了LDQPSO算法。在此基礎(chǔ)上，用LDQPSO實現(xiàn)非剛體點云配準(zhǔn)參數(shù)的優(yōu)化確定，最終實現(xiàn)了快速高精度的非剛體點云配準(zhǔn)。文中選擇不同的非剛體配準(zhǔn)實例驗證算法有效性，并與原有算法進行對比。實驗表明該文提出的算法具有更好的尋優(yōu)性能。

關(guān)鍵詞：非剛體 LDQPSO 優(yōu)化

中圖分類號：TN91 文獻標(biāo)識碼：A 文章編號：1672-3791（2017）08（a）-0236-04

基于點的特征匹配問題一直是計算機視覺、模式識別等領(lǐng)域中一個基礎(chǔ)而重要的課題。在實際應(yīng)用中，如目標(biāo)跟蹤，常常需要對存在非剛性形變的場合進行快速精確的配準(zhǔn)，進而實現(xiàn)高效的目標(biāo)跟蹤，因此，如何實現(xiàn)準(zhǔn)確快速的配準(zhǔn)尤其是非剛體配準(zhǔn)顯得尤為重要。

2003年，Chui等[1]提出的基于TPS構(gòu)造能量函數(shù)，用于非剛體點云配準(zhǔn)中，然而該算法是基于SA算法實現(xiàn)的，實際求解對于多峰函數(shù)尋優(yōu)具有局限性。PSO算法需控制的參數(shù)少，易實現(xiàn)且對多峰函數(shù)尋優(yōu)具有很好的效果。2004年，馮林[2]提出基于PSO算法的點匹配方法。但標(biāo)準(zhǔn)PSO算法并不能以絕對概率尋得全局最優(yōu)，故文獻[2]算法易陷入局部最優(yōu)。

一個好的優(yōu)化算法，必須能夠很好地平衡算法的“開發(fā)能力”和“探索能力”。種群多樣性是衡量算法“開發(fā)能力”和“探索能力”的重要依據(jù)。2011年，Shi等[3]給出了多樣性的定義，并指出量子粒子群優(yōu)化算法本質(zhì)上是一種PSO多樣性控制的算法。因此，多樣性控制研究中，對量子粒子群優(yōu)化算法進行研究，具有實際的價值和意義。基于此，該文對QPSO算法的慣性權(quán)重系數(shù)采用線性+自適應(yīng)的策略進行更新，提出了LDQPSO算法（Linear adaptive QPSO），有效地解決了標(biāo)準(zhǔn)PSO算法過早收斂到局部最優(yōu)的問題。并進一步將LDQPSO應(yīng)用于非剛體配準(zhǔn)的一一對應(yīng)關(guān)系和映射函數(shù)參數(shù)的優(yōu)化中，有效地提高了非剛體點云配準(zhǔn)問題的精確性性和快速性。

1 非線性自適應(yīng)QPSO算法原理

該節(jié)首先簡要介紹標(biāo)準(zhǔn)QPSO的基本原理，接著詳細介紹該文所提出的LDQPSO算法原理及實現(xiàn)步驟。

1.1 標(biāo)準(zhǔn)QPSO算法原理簡介

2004年，Sun[6]從量子力學(xué)的角度提出了QPSO算法，粒子的位置方程為：

（1）

其中，u為在[0，1]之間的隨機數(shù)，L由式（2）確定：

·β· （2）

最后，得到QPSO算法的進化方程為：

（3）

（4）

其中，D表示粒子的維數(shù)，表示所有粒子的平均最優(yōu)值，N表示粒子數(shù)目，u是在[0， 1]均勻分布的隨機數(shù)。第i個粒子的最優(yōu)。β是算法收斂的重要且唯一參數(shù)。

1.2 LDQPSO算法原理

參數(shù)對于算法尋優(yōu)性能至關(guān)重要，如何選擇最優(yōu)策略確定最佳參數(shù)促進算法尋優(yōu)性能是相當(dāng)復(fù)雜的問題。受SA啟發(fā)，分析式（3）容易發(fā)現(xiàn)，β較大時算法以較快速度在全局尋優(yōu)，但此時的解往往不是最精確的；β較小時算法以較慢速度在局部尋優(yōu)，此時更易尋得全局最優(yōu)解。因此，可設(shè)置隨著迭代進行β在一定范圍內(nèi)逐步遞減，最終搜索到最優(yōu)解。

該文提出的LDQPSO算法基本思想為：初期為粗匹配，對β控制采用式（6）策略，此時β值較大，算法收斂速度較快，側(cè)重于促進算法在全局搜索所有的解，粒子之間進行信息交互，向當(dāng)β前全局最優(yōu)解“聚攏”；當(dāng)達到預(yù)設(shè)值時算法進入精匹配，對β控制采用式（7）策略，算法尋優(yōu)速度較初始有所降低，粒子集中在局部搜索更精準(zhǔn)的最優(yōu)值。

β=f （a，e）=β-s·β01+a·β02 （6）

（7）

其中，β0和β1分別為β的最大、最小值；t表示算法當(dāng)前的迭代次數(shù)；表示算法的最大迭代次數(shù)；s為進化速度因子，s的取值范圍為0

（8）

（9）

上式中，表示當(dāng)前迭代的全局最優(yōu)，表示上一次迭代的全局最優(yōu)，表示當(dāng)前迭代所有粒子最優(yōu)的均值，見式（10）：

（10）

綜上所述，基于式（6）、式（7）所示策略，改進算法在初期尋優(yōu)過程中，探索能力增強，有效促進了算法的全局搜索能力；在末期尋優(yōu)過程中，開發(fā)能力增強，使得算法能夠更有效的尋得全局最優(yōu)解，進而平衡算法探索能力和開發(fā)能力。

2 基于NLAPSO算法的非剛體配準(zhǔn)原理

該部分首先簡要介紹非剛體點云配準(zhǔn)，接著對該文所提出的基于LDQPSO算法的非剛體點云配準(zhǔn)算法原理及流程進行介紹。

2.1 基于TPS的非剛體配準(zhǔn)

基于TPS的非剛體配準(zhǔn)思想是：在確定點集之間對應(yīng)關(guān)系后，通過最小化TPS函數(shù)，嵌入合適的優(yōu)化算法框架中，對空間映射函數(shù)f和對應(yīng)矩陣H進行交替求解，最終確定最優(yōu)的f和H值，進而實現(xiàn)點云配準(zhǔn)?；赥PS的非剛體配準(zhǔn)算法的函數(shù)表示如下：

（11）

選擇適當(dāng)?shù)膬?yōu)化算法對應(yīng)矩陣H和映射函數(shù)f （c，d）進行求解，進而即可實現(xiàn)非剛體配準(zhǔn)。

2.2 基于LDQPSO的非剛體配準(zhǔn)原理

基于LDQPSO的非剛體配準(zhǔn)算法原理為：將式（11）目標(biāo)函數(shù)的最優(yōu)化求解嵌入到LDQPSO算法中，求解參數(shù)值。基于LDQPSO算法的非剛體配準(zhǔn)算法流程見圖1。

此處，和初值分別設(shè)置為。

3 仿真研究

該節(jié)共選擇兩組典型點云數(shù)據(jù)進行非剛體配準(zhǔn)仿真，驗證該文算法的有效性。仿真圖中模板點集均為圓圈，目標(biāo)點集均為十字。圖2中模板點集為閉合曲線，而待匹配的目標(biāo)點集是一組與模板點集相似但在底部存在形變的閉合曲線；圖3中模板點集和目標(biāo)點集均為手寫“?！弊值狞c云，兩組數(shù)據(jù)看起來相似，但實際存在較大非剛體形變。分別采用基于SA的非剛體配準(zhǔn)算法（DA-NR）[1]和該文提出的基于LDQPSO的非剛體配準(zhǔn)算法（LDQPSO-NR）對這些數(shù)據(jù)進行配準(zhǔn)，分別采用主觀和客觀兩種評價方式進行性能評價。

3.1 主觀評價

（1）閉合曲線點云仿真實例。

圖4（a）為DA-NR配準(zhǔn)結(jié)果，圖4（b）為該文提出LDQPSO-NR配準(zhǔn)結(jié)果。配準(zhǔn)結(jié)果表明LDQPSO-NR在DA-NR不能很好實現(xiàn)配準(zhǔn)的位置也取得了較好的匹配結(jié)果。

（2）手寫字體點云仿真實例。

圖5（a）為DA-NR配準(zhǔn)結(jié)果，圖5（b）為該文提出LDQPSO-NR配準(zhǔn)結(jié)果。結(jié)果表明，本文算法和DA-NR均取得了精準(zhǔn)的配準(zhǔn)結(jié)果。

3.2 客觀評價

表1中列出了DA-NR[1]和該文LDQPSO-NR下，經(jīng)過30次測試得到的式（11）函數(shù)最優(yōu)值均值和方差，分別用mean和var表示最優(yōu)值均值和方差，T表示達到配準(zhǔn)時所需時間。

由表1可知，LDQPSO-NR算法求得的函數(shù)均值、方差均優(yōu)于DA-NR算法，該數(shù)據(jù)驗證了該文算法的高精度和高穩(wěn)定性。此外，從程序運行時間上看，該文算法明顯優(yōu)于DA-NR算法，驗證了該文算法的快速性。

4 結(jié)語

該文提出了一種LDQPSO非剛體配準(zhǔn)算法。通過對QPSO參數(shù)改進，迭代初期粒子在全局范圍內(nèi)進行粗尋優(yōu)，側(cè)重于提高算法收斂速度；隨著迭代次數(shù)增加，粒子趨向于精尋優(yōu)，側(cè)重于提高算法精度。實驗部分選擇兩組典型非剛體點云數(shù)據(jù)對基于該文算法的配準(zhǔn)結(jié)果和基于SA算法的配準(zhǔn)結(jié)果進行對比，由結(jié)果可知，該文算法在精確性、穩(wěn)定性和快速性方面均表現(xiàn)出更好的配準(zhǔn)結(jié)果。下一步工作可將該文算法用于一些實時配準(zhǔn)問題中。

參考文獻

[1] Chui Haili， Rnagarajna A. A new point matching algorithm for non-rigid registration[J].Computer Visionand Image Understanding，2003，89（2-3）：114-141.

[2] 馮林，張名舉.基于粒子群優(yōu)化技術(shù)的點匹配算法[J].系統(tǒng)仿真學(xué)報，2004，8（16）：193-194.

[3] Shi Cheng and Yuhui Shi.Diversity control in particle swarm optimization. In Proceedings of 2011 IEEE Symposium on Swarm Intelligence （SIS 2011）[M].Paris，F(xiàn)rance，2011：110-118.

[4] 鄭立華，麥春艷，廖崴，等.基于Kinect相機的蘋果樹三維點云配準(zhǔn)[J].農(nóng)業(yè)機械學(xué)報，2016（5）：134-135.endprint