基于LDQPSO算法的非剛體配準

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

DOI：10.16661/j.cnki.1672-3791.2017.22.236

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

關鍵詞：非剛體 LDQPSO 優化

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

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

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

一個好的優化算法，必須能夠很好地平衡算法的“開發能力”和“探索能力”。種群多樣性是衡量算法“開發能力”和“探索能力”的重要依據。2011年，Shi等[3]給出了多樣性的定義，并指出量子粒子群優化算法本質上是一種PSO多樣性控制的算法。因此，多樣性控制研究中，對量子粒子群優化算法進行研究，具有實際的價值和意義?；诖耍撐膶PSO算法的慣性權重系數采用線性+自適應的策略進行更新，提出了LDQPSO算法（Linear adaptive QPSO），有效地解決了標準PSO算法過早收斂到局部最優的問題。并進一步將LDQPSO應用于非剛體配準的一一對應關系和映射函數參數的優化中，有效地提高了非剛體點云配準問題的精確性性和快速性。

1 非線性自適應QPSO算法原理

該節首先簡要介紹標準QPSO的基本原理，接著詳細介紹該文所提出的LDQPSO算法原理及實現步驟。

1.1 標準QPSO算法原理簡介

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

（1）

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

·β· （2）

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

（3）

（4）

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

1.2 LDQPSO算法原理

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

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

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

（7）

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

（8）

（9）

上式中，表示當前迭代的全局最優，表示上一次迭代的全局最優，表示當前迭代所有粒子最優的均值，見式（10）：

（10）

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

2 基于NLAPSO算法的非剛體配準原理

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

2.1 基于TPS的非剛體配準

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

（11）

選擇適當的優化算法對應矩陣H和映射函數f （c，d）進行求解，進而即可實現非剛體配準。

2.2 基于LDQPSO的非剛體配準原理

基于LDQPSO的非剛體配準算法原理為：將式（11）目標函數的最優化求解嵌入到LDQPSO算法中，求解參數值?；贚DQPSO算法的非剛體配準算法流程見圖1。

此處，和初值分別設置為。

3 仿真研究

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

3.1 主觀評價

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

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

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

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

3.2 客觀評價

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

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

4 結語

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

參考文獻

[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] 馮林，張名舉.基于粒子群優化技術的點匹配算法[J].系統仿真學報，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，France，2011：110-118.

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