ICP系列算法的描述與對比

摘? 要：根據(jù)當前計算機技術的發(fā)展，實體模型數(shù)字化產(chǎn)出得到了越來越廣泛的應用。該文主要是針對這一應用研究了ICP算法的原理以及使用場景。實踐驗證ICP算法產(chǎn)出實體模型的過程，并加深了對ICP算法的理解。在經(jīng)典ICP算法的基礎上，研究了基于鄰域的ICP算法的特性以及優(yōu)點。在該文中，也研究了GA（遺傳算法）的原理。它主要是基于生物遺傳進化特性進行高效精確查找的算法。GA與ICP特性相結合，可以通過遺傳算法原理精確找到點云中匹配的點的集合所構成的幾何體。

關鍵詞：ICP? GA? 遺傳算法? 鄰域

中圖分類號：G423? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻標識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1672-3791（2019）03（b）-0024-02

經(jīng)典ICP算法是將不同坐標系中的點云數(shù)據(jù)轉換為同一坐標系，并以最小的存儲成本，獲得精確的幾何結構或拓撲結構。

在物體模型采集的過程中，因為各種各樣的情況，如采集物體的體積較大或者本來就是破損為多各部分的物體無法單次完成，需要在多次采集后進行集成，然后需要將不同坐標系中的點集成到一個坐標系中，并精準地得到幾何結構。

ICP算法是建立在有特征的點云基礎上的算法，其是一個理想狀態(tài)下的對應點云算法。使用四元數(shù)旋轉模型點云數(shù)據(jù)并平移得到新的點云。對應的點集注冊算法主要是計算qR和qT，知道這兩者后遍可以匹配點云。然而，對應點集匹配算法的前提條件是計算中的點云數(shù)據(jù)PB和PR元素是一一對應的。由于諸如現(xiàn)實中的錯誤之類的問題，這種情況不太可能是實線，因此存在了ICP算法。

1? 算法描述

1.1 GA算法

GA算法（Genetic Algorithm）即遺傳算法。顧名思義，遺傳算法其實源自于生物學所應用到的生物界遺傳與進化機制的計算模型。該算法的本質就是通過類似于自然遺傳進化的過程搜索出最優(yōu)的結果。它首先根據(jù)一個可能有問題的組，再通過每個染色體對應的遺傳規(guī)則算法制定解決方案。因此，從基因組到其解決方案的映射形成了一個映射。遺傳算法的過程可以看作是在多變量函數(shù)中找到最優(yōu)解的過程?？梢試L試構想一下，在一個多維的表面上有無數(shù)的“山峰”，這些峰對應于局部最優(yōu)解。而且還會有一個海拔最高的“山峰”，那么這就是全球最優(yōu)解決方案。遺傳算法的宗旨就是根據(jù)遺傳規(guī)則盡可能地爬到最高峰，盡量避開干擾，不去落到一些小峰。此處需要留意的是遺傳算法并不是一定要找到“最高峰”。如果問題的評估是盡可能小的話，那么全局最優(yōu)解就應該是函數(shù)的最小值。當前情況下，遺傳算法有許多有趣的應用，例如：尋路問題、8個數(shù)字問題、囚徒困境、找到圓的中心（在不規(guī)則的多邊形中，查找多邊形中包含的最大圓的中心）、人工生命模擬、TSP問題、運動控制、生產(chǎn)調(diào)度問題等。

GA算法的步驟是在特定編碼方案下隨機生成初始組，并使用相應的編碼方法將編碼的個體轉換為問題空間的決策變量。并根據(jù)某種選擇（即適者生存的原則）找到個體的適應值，選擇一些個體形成交配池，由兩個遺傳算子交叉和變異操作，以隨機配對交配池中的兩個個體。從一些現(xiàn)有的父親和后代中形成新一代人口，選擇一些最好的人作為新父母，重復步驟2到4，將它們代代相傳，直到滿足收斂判斷。

遺傳算法中，主要有以下3種類型的操作：選擇，交叉，變異。其中最基本的操作為選擇和交叉，這兩種操作就可以基本上完成遺傳算法的大部分搜索功能了。變異功能則提高了遺傳算法找到最優(yōu)解的能力，屬于錦上添花的功效，變異后被選中的可能性就越大。仔細描述下來，交叉其實是指“替換”和“重組”父類部分的結構，從而產(chǎn)生一個新個體的操作?？梢酝ㄟ^交叉操作，極大地提高遺傳算法的搜索效率。變異操作的基本過程則是在[0，1]之間rand生成隨機數(shù)，如果rand [Pm]，則執(zhí)行變異操作。交叉操作又保證了遺傳算法的有效性，相對應的得到保證了遺傳算法具有局部隨機搜索的能力。同時又使遺傳算法能夠保持群體的多樣性，可以防出現(xiàn)錯誤的收斂。結合選擇和交叉運算符，可以避免由于選擇和交叉的操作而導致一些信息不可恢復的丟失。

1.2 ICP算法

ICP算法的本質實際上是基于最小二乘法的最佳配準方法。該算法重復選擇對應的點對并計算最優(yōu)點，直到滿足正確配準的收斂精度要求。ICP算法的目的是找到待登記的點云數(shù)據(jù)與參考云數(shù)據(jù)之間的旋轉參數(shù)R和平移參數(shù)T，從而在兩個數(shù)據(jù)點之間滿足特定度量下的最優(yōu)匹配。首先計算目標點云的每個點與源點云上的每個點的距離。將每個點與目標云的最近點匹配，從而滿足對應點云ICP算法的前提條件，并且每個點具有對應的映射點。然后可以根據(jù)相應的點集注冊算法計算，但由于這是一個假設，因此有必要重復迭代以運行上述過程。直到均方差誤差小于某個閥值。也就是說，每次迭代時，整個模型都接近一個點，每次它再次找到最近的點，然后根據(jù)相應的點集批準算法對其進行計數(shù)，并比較均方誤差并繼續(xù)迭代。

ICP算法關鍵點。

首先是原始點集的采集要保證均勻采樣，隨機采樣和法向矢量采樣。其次確定對應點集：點到點、點到投影、點到面。計算變化矩陣GA與ICP特性相結合，可以通過遺傳算法原理精確找到點云中匹配的點的集合所構成的幾何體。二者的相同之處在于該兩種算法核心都是快速精準的查找。區(qū)別之處在于ICP算法主要是基于二叉樹的查找，而遺傳算法是基于生物的遺傳規(guī)則進行多次“優(yōu)勝劣汰”的比對后輸出最優(yōu)解。鑒于二者核心宗旨都為快速查找，則可將二者結合，找到點云中最優(yōu)點，形成最終的拓撲圖形。

1.3 基于鄰域特征的ICP算法

基于鄰域的ICP算法可以提高點搜索率并提高匹配點的準確性?？臻g中的點云數(shù)據(jù)，如果只有三維坐標的信息而沒有其他的拓撲信息，那么空間中的點云無法發(fā)揮最充分的利用。因此，在應用ICP算法時，應首先找到與該點相鄰的多個點以構建一個小鄰域。再通過這個鄰域來提取對應的幾何信息。點鄰域的確定方式有3種：樹形存儲法、k-d tree法、空間柵格法。

相鄰點的計算是整個過程中最長的一步。其過程是：首先找到最近的點并使用k-d樹去進行加速搜索，在根據(jù)二叉樹規(guī)則生成構建k-d樹的過程。空間會被分成兩部分，x的值最接近平均值，然后在分割的子空間中找到Y軸的邊界。將它們分成兩部分，劃分的子空間除以X軸......依此類推，最后在分割區(qū)域中只有一點。該分割過程對應于二叉樹，并且二叉樹的每個葉節(jié)點對應于一個點，二叉樹的分支節(jié)點對應于一條分割線，一個完整的拓撲關系就建立了。

2? 結語

該文主要研究了ICP系列算法的應用，以及算法是如何將兩個坐標系的點云擬合成同一坐標系的幾何體。通過此次研究更理解了ICP的實際用途和原理，也理解了基于鄰域特性的ICP算法的優(yōu)點。研究ICP算法的同時也理解了GA（遺傳算法）的原理和使用它們的優(yōu)點——GA算法基于生物優(yōu)勝劣汰規(guī)則進行一系列篩選對比后輸出最優(yōu)解;ICP算法則是通過對比點云的最優(yōu)距離等方式形成最小鄰域，相似且共通，拓寬了知識面，提高了實踐能力和知識結合能力。

參考文獻

[1] 王磊，邢淵.反向工程中數(shù)據(jù)點云的拼合[J].模具技術，2004，6（1）：47-49.

[2] 王蕊，李俊山，劉玲霞，等.基于幾何特征的點云配準算法[J].華東理工大學學報，2009，35（5）：768-773.

[3] 高珊珊.基于三維激光掃描儀的點云配準[D].南京理工大學，2008.

[4] 陸秋.基于MapReduce的決策樹算法并行化[J].計算機應用，2012，32（9）：2463-2469.①作者簡介：劉美池（1995—），女，朝鮮族，遼寧沈陽人，本科在讀，研究方向：算法研究。