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

關(guān)鍵詞：ICP? GA? 遺傳算法? 鄰域

中圖分類號：G423? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 文獻(xiàn)標(biāo)識碼：A? ? ? ? ? ? ? ? ? ? ? ? ? 文章編號：1672-3791（2019）03（b）-0024-02

經(jīng)典ICP算法是將不同坐標(biāo)系中的點(diǎn)云數(shù)據(jù)轉(zhuǎn)換為同一坐標(biāo)系，并以最小的存儲成本，獲得精確的幾何結(jié)構(gòu)或拓?fù)浣Y(jié)構(gòu)。

在物體模型采集的過程中，因?yàn)楦鞣N各樣的情況，如采集物體的體積較大或者本來就是破損為多各部分的物體無法單次完成，需要在多次采集后進(jìn)行集成，然后需要將不同坐標(biāo)系中的點(diǎn)集成到一個坐標(biāo)系中，并精準(zhǔn)地得到幾何結(jié)構(gòu)。

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

1? 算法描述

1.1 GA算法

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

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

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

1.2 ICP算法

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

ICP算法關(guān)鍵點(diǎn)。

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

1.3 基于鄰域特征的ICP算法

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

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

2? 結(jié)語

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

參考文獻(xiàn)

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

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

[3] 高珊珊.基于三維激光掃描儀的點(diǎn)云配準(zhǔn)[D].南京理工大學(xué)，2008.

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