尺度可變的快速全局點云配準方法分析

覃錫森

廣東省國土資源測繪院 廣東 廣州 510599

1 研究背景

通過查閱相關資料，處理三維點云模型配準的研究非常廣泛，迭代最近點“Iterative Closest Point，ICP”是使用最廣泛最經典的形式[1]。但是這一優化過程中有非凸性質，基于局部的搜索不夠全面，局部獲取信息有限，在信息的限制下局部配準不全面，無法滿足精準性，加上噪聲存在，明顯地影響了配準結果，基于全局優化的角度出發，以點云配準方式就可以解決上述問題，但是解決空間會隨著點云規模增大，導致迭代算法的使用效率低下，甚至無法得到目標結果。

2 配準方式

2.1 局部配準方式

局部配準中，以ICP為主，這種局部搜索為迭代方式的配準方式整體呈現出非線性特征，如果使用中初值不確定，很難得到最優配準，且對噪聲、重合區域等都很敏感。在后續的研究中，需要逐步進行改進從而克服這些缺陷，借助Robust Kernel函數對目標函數進行非線性優化可以改變所存在的缺陷，且其配準性能具備良好的抗噪能力。除了Robust Kernel之外也可以加入點云法向量、顏色等輔助信息提升配準結果，另外正態分布變換方法Normal Distributions Transform,NDT也可以實現配準。基于統計學算法的配準將配準問題轉化為概率密度函數，并得到優化后的高斯混合模型，該點云配準方式的優勢在于不用建立兩片點云模型間的點點對應，從而避免了噪聲等錯誤問題，提升了Robust Kernel性。

2.2 全局配準

為避免初值等因素對配準所產生的影響，因此出現了全局配準研究，該研究的范圍比較廣，如Branch-and-Bound, BnB、模擬退火法等，全局配準都是找到兩片點云的配準誤差度量函數最小值，雖然效果良好，但是缺陷在于全局優化需要消耗更多時間，以及大量數據的處理很難完成。為實現這一方面，人們采用在原本的研究基礎上進行特征空間的初始配準，建立其對應關系來解決配準的問題。雖然人們提出了不同的解決方式，但是由于尺度不一致等問題，導致點云匹配的問題仍舊存在，無法得到精準配準后的結果。

3 算法

假設數集P、Q，兩者之間可以建立對應關系，其對應關系為K={(p、q)|p∈P,q∈Q}，計算中最佳縮放用s表示、旋轉為R、平移用T表示，通過對應點的均方誤差計算Mean Squared Error最小表示為：

考慮實際物體建模的需要，配準中的K值并不確定，運用最小二乘的意義下優化會因為受到噪聲的限制導致優化不理想。為兼顧魯棒性與優化效率，顧慮全局配準可能會減少這些不理想因素，因此優化函數的計算形式為：

4 配準中局部特征的降維、配準

其特征對應關系K由所描述子集來決定，這里論述其細節；假設點云P、Q，其特征描述為

其匹配可以分為三步：①將L2距離最近的F（q）的最近點設置為集合K2；②在集合K1里加入每一個子集，如果F（q）是最近點，也加入到K2中；③在K2中隨機選擇三個子集，將其標記形成對應三角，分別記為Tp、Tq，根據匹配關系導出對應，計算其比例，對其進行驗證。由于尺度不一致，正確的匹配管理可以保證對應的三角形，驗證其相似性。運用分類法來進行分析，可以分為Signature、Histogram兩類，其中Signature的描述極強，但Histogram的魯棒性特征更強，因此配準更全面，但是因為描述性不強而存在錯誤配準的可能，Signature的描述性更強，配準成功概率也更高[2]。針對不同類型的點云數據選取不同的特征描述子部來得到足夠多的配準數目，能夠得到正確的比例關系，確保后續推算的精準。為得到更好的效果使用高效的優先搜索算法，通過加速分析計算，該方式建樹與查詢復雜度均與子維數成正比，要求建樹復雜度與點云成正比，而完成大規模點云的CSHOT描述子配準需要消耗大量時間，這是三維建模中端到端處理的瓶頸。

兩片點云表現三維圖形的過程存在相似性，CSHOT描述運用在高維空間分布呈現出明顯的可循規律，因此用來進行降維處理將會取得更快的配準效果。

5 目標函數計算

在不考慮尺度變化對上述公式的優化，但是引入尺度縮放變量之后無法以線性方程來表示空間變換增強，因此必須考慮尺度的方式。通過優化步驟，不增加算法復雜度的基礎上對所放量優化。通過將線過程與穩健統計相結合給出求解方式，以構造特征的對應關系K的權重結合L＝｛lp、q｝，將得到優化后的變量與聯合目標函數：

為優化E，將關于化整為零，整理得到目標函數最小數值，目標函數最小用lp、q來表示：

其中，s、R、T均是迭代步的值，是為固定相。從上述表示可以看出lp、q來表示的數值與點云對應點距離間呈現反相關，視為對應點的權重趨向于錯誤匹配點的無效化。在研究中，逐漸減少的數值，可以在配準優化中減少噪聲與異常點所產生的影響。

在計算中，合成數據集中進行測試，得到了優化之后的配準情況，實驗中的25組數據計算之后，標準差配準重疊區域47%～90%之間[3]。由于該數據的分析不考慮顏色信息等，這以數據集的測試數據間沒有尺度差異，在無尺度差異中取得了極好的精度、時間效率。

6 結束語

綜上，在設計分析中，尺度可變的全局快速配準算法能夠得到理想成果，且與最終的計算目標相近，最終獲得數據證明尺度可變的全局配準方式可以取得理想效果。但是在研究中應注意配準結果依賴特征匹配結果，因此選擇好的特征描述也是決定配準質量的關鍵。在充分借助計算機技術的基礎上，仍舊需要研究針對局部特征描述探索好的配準結果，解決這一問題需要具備理論作為基礎。