基于k近鄰算法優化的最小二乘3D表面匹配算法

王 鵬，李少達，趙 雪

（1.成都理工大學 地球科學學院，四川 成都 610059；2.西南交通大學 地球科學與環境工程學院，四川 成都 611756）

點云匹配是激光點云重建三維模型的關鍵步驟。目前的匹配算法包括迭代最近鄰點（ICP）[1]，最小二乘3D表面匹配算法（LS3D）[2]和三維正態分布變換算法（3D-NDT）[3]等。國內外學者對ICP、3D-NDT提出了很多改進優化方法[4-13]，但對LS3D的研究較少。

LS3D是一種高精度、高效率的點云匹配算法，可應用于任意三維表面數據，是二維圖像最小二乘匹配的一種延伸。Gruen最早利用該技術解決了攝影測量中面片匹配的問題。Gruen和Acka將廣義高斯 - 馬爾科夫模型運用到LS3D算法中，以估算變換參數。其中，k近鄰搜索花費的時間是影響LS3D算法計算效率的主要因素[14-15]。

LS3D使用盒子劃分結構（BS）進行k近鄰搜索，得到同名點進行三維坐標轉換的參數（3個旋轉角、3 個平移參數和1個尺度因子）。譚俊祥[16]將無序三維散亂點云的空間劃分方法歸為樹結構劃分法和空間分塊策略法兩類；同時提出一種正交軸格網劃分（OGP）的搜索算法，在對比已有的k近鄰算法中達到最優；在空間分塊策略法中，主軸搜索樹（PAT）在精度和效率上最優；但未對LS3D使用的BS算法進行實驗分析。基于此，本文根據不同k近鄰搜索算法（kNN）對LS3D進行實驗，對比分析了不同搜索算法下的LS3D性能。

1 LS3D的算法原理

1.1 算法原理

f (x, y, z)和g (x, y, z)分別為待匹配數據與目標點云之間的重疊區域。三維表面配準其實就是估算變換參數，利用待匹配數據表面的點云f (x, y, z)調整目標表面g (x, y, z)上的點云。若兩個表面點云的匹配建立，則應滿足：

由式（1）可知，待匹配數據中包含與目標數據對應的點云。若假設e (x, y, z)為待匹配數據與目標數據間的一個真矢量誤差，則可推導出：

式（2）為LS3D的觀測方程。通過最小二乘算法最小化目標函數實現匹配過程，表示模板表面和搜索表面同名點之間的歐氏距離平方和：

式中，d為歐氏距離，根據g (x, y, z)的初始位置類估計最終位置。

1.2 LS3D的實現過程

1）搜索目標點云和待匹配點云間的同名點對。

2）利用同名點對，建立高斯—馬爾科夫模型：

式中，A為設計矩陣；I為單位矩陣；l=f (x, y, z)-g0(x, y, z)為常數向量；lb為系統參數向量；x=[dtx dty dtz dm dω dφ dκ]T為參數向量；P為先驗相關權重系數矩陣；Pb為系統參數相關權重系數矩陣。

3）求解參數向量x?=(ATPA+Pb)-1(ATPl+Pblb)。

4）迭代求解參數向量，當參數向量小于設定閾值時，停止迭代。

2 實驗與分析

本文以Matlab 2014a作為算法程序開發和實驗平臺，使用 Windows 7操作系統，Inter? Core(TM) i5-2450M CPU @ 2.5GHz處理器，采用在樹結構劃分法和空間分塊策略法中最優的搜索算法PAT、OGP進行實驗。實驗數據采用模擬點云數據，如圖1所示。

圖1 實驗采用點云數據

由表1可知，3種搜索算法對LS3D的迭代次數和精度幾乎沒有影響，但在迭代所花費的時間上卻有很大差距。BS算法的迭代時間最短，優于OGP和PAT算法，但PAT算法與BS、OGP算法的迭代時間差距太大，因此在實驗過程中，同時統計了3種算法每次迭代所需的時間。PAT算法第一次迭代消耗了400 s，而在剩下的迭代過程中，每次迭代所花時間與BS、OGP算法差距不是很大。綜上所述，BS算法優于OGP算法，PAT算法迭代時間長的原因在于第一次迭代消耗大量時間，導致整體的匹配效率下降。

表1 不同搜索算法下的LS3D算法收斂效率與精度

3 結 語

本文通過樹結構劃分法和空間分塊策略法中的典型算法與BS算法進行測試，對比分析了不同k近鄰搜索算法下LS3D算法的性能。實驗結果表明，不同搜索算法對LS3D算法的匹配精度幾乎沒有影響，BS算法優化的LS3D算法在相同迭代次數下效率最優，是PAT算法的4.5倍，而造成PAT算法效率較低的原因在于第一次迭代中消耗的時間過多，幾乎達到了整個迭代過程的一半，在匹配過程中需要較好的初始值才能提高效率。匹配效率和精度是三維重建過程中的關鍵因素，期待能對點云匹配精度進行進一步研究。

[1] Besl P J, Mckay N D. A Method for Registration of 3D Shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,1992,14(2):239-256

[2] Gruen A, Akca D. Least Squares 3D Surface and Curve Matching[J]. ISPRS Journal of Photogrammetry and Remote Sensing,2005,59(3):151-174

[3] Magnusson M. The Three-dimensional Normal-distributions Transform :an Efficient Representation for Registration,Surface Analysis, and Loop Detection[J]. Renewable Energy,2012,28(4):655-663

[4] CHEN Y, Medioni G. Object Modeling by Registration of Multiple Range Images[J]. Image and Vision Computing,1991,10(3):145-155

[5] ZHANG Z.Iterative Point Matching for Registration of Freeform Curves and Surfaces[J]. International Journal of Computer Vision,1994,13(2):119-152

[6] 嚴劍鋒,鄧喀中.基于特征點提取和匹配的點云配準算法[J].測繪通報,2013(9):62-65

[7] 侯東興,王耀華,李宗春.剔除誤同名點的約束改進ICP算法[J].測繪科學,2015,40(8):103-107

[8] 鐘瑩,張蒙.基于改進ICP算法的點云自動配準技術[J].控制工程,2014,21(1):37-40

[9] 秦緒佳,徐菲,王建奇,等.基于法向量直方圖特征描述的點云ICP拼接[J].小型微型計算機系統,2016,37(3):593-597

[10] 王瑞巖,姜光,高全學.結合圖像信息的快速點云拼接算法[J].測繪學報,2016,45(1):96-102

[11] 周文振,陳國良,杜珊珊,等.一種聚類改進的迭代最近點配準算法[J].激光與光電子學進展,2016(5):202-208

[12] 張曉,張愛武,王致華.基于改進正態分布變換算法的點云配準[J].激光與光電子學進展,2014(4):100-109

[13] 胡修祥,張良,HUXiu-xiang,等.結合NARF特征的改進型3D-NDT多視點云配準[J].信號處理,2015,31(12):1 674-1 679

[14] LIU Y H. Constraints for Closest Point Finding[J].Pattern Recognition Letters,2008,29(7):841-851

[15] LI B, Holstein H. Using k-d Trees for Robust 3D Point Pattern Matching[C]. International Conference on 3D Digital Imaging and Modeling,2003:95-102

[16]譚駿祥.地面LiDAR散亂點云配準關鍵技術研究[D].成都:成都理工大學,2014:22-26