基于投影的點云配準(zhǔn)算法

江 盟 ,蔡 勇，張建生

(1.西南科技大學(xué)制造科學(xué)與工程學(xué)院,四川 綿陽 621010；2.制造過程測試技術(shù)省部共建教育部重點實驗室,四川 綿陽 621010)

0 引言

點云配準(zhǔn)技術(shù)是逆向工程和產(chǎn)品檢測中非常重要的環(huán)節(jié)。目前，點云自動配準(zhǔn)算法中應(yīng)用廣泛的是迭代最近點(iterative closest point，ICP)算法及其改進(jìn)算法[1]。配準(zhǔn)點云的初始位置是ICP算法非常重要的限制條件。該條件影響ICP算法的配準(zhǔn)速度和全局收斂。粗配準(zhǔn)技術(shù)能有效解決ICP算法對初始配準(zhǔn)位置的要求。文獻(xiàn)[2]在逆向工程中，將多次掃描得到的點云數(shù)據(jù)先采用主成分分析(principal component analysis，PCA)粗配準(zhǔn)，再采用ICP算法實現(xiàn)精細(xì)化配準(zhǔn)。PCA算法的特點是粗配準(zhǔn)速度非常快，但魯棒性很差。為增強(qiáng)粗配準(zhǔn)的魯棒性，文獻(xiàn)[3]利用二維圖像提取特征點實現(xiàn)點云配準(zhǔn)，但提取特征的過程相當(dāng)耗時，且噪聲對算法的影響比較大。

點云配準(zhǔn)本質(zhì)是求優(yōu)化解的過程[4]。其中比較重要的兩個問題是：第一，設(shè)計一個可行的評價函數(shù)；第二，采用一種有效的搜索方法[5-7]。評價函數(shù)有空間分布熵[5]、表面融合[7]等。遺傳算法對于多變量多目標(biāo)的問題求解具有非常好的效果，因此許多學(xué)者在點云配準(zhǔn)中使用遺傳算法作為搜索方法[8-10]。此外，將隨機(jī)抽樣一致性算法引入點云配準(zhǔn)[11-12]，也能達(dá)到很好的配準(zhǔn)效果，但是其配準(zhǔn)速度比較慢。

本文提出了一種降維處理點云數(shù)據(jù)的配準(zhǔn)算法。首先，將配準(zhǔn)點云投影到三個坐標(biāo)平面，并且劃分平面以統(tǒng)計每一個格子中的點數(shù)；然后，分別求解每個投影平面的熵值，再利用遺傳算法來搜索使得三個投影平面熵值和最小的空間變換矩陣；最后，將最優(yōu)矩陣作用于目標(biāo)點云，實現(xiàn)配準(zhǔn)。

1 點云空間位置關(guān)系評價

快速、精確地評價點云的空間位置，是點云配準(zhǔn)中非常重要的環(huán)節(jié)。本文將點云數(shù)據(jù)的三維立體圖形經(jīng)過投影降低維度到二維，再經(jīng)過統(tǒng)計計算來評價兩片點云的空間位置關(guān)系。

1.1 信息熵的定義

對于包含N個點的點云P,將其投影到某平面得到二維投影點云P’。將投影平面的橫坐標(biāo)和縱坐標(biāo)均按間隔ΔL進(jìn)行柵格化，統(tǒng)計輸入點云數(shù)據(jù)的總點數(shù)N及每個非空柵格內(nèi)的點數(shù)ni，得到每個非空柵格的點云出現(xiàn)頻率pi為：

(1)

點云P在該平面的投影熵SE定義為：

(2)

1.2 投影

在工程制圖中，通常采用三視圖來表達(dá)物體的形狀和各部件的相對位置關(guān)系。因此，三視圖能完整地表達(dá)各部件的相對位置關(guān)系。一個物體確定后，其各個部件的相對位置關(guān)系也就確定。點云配準(zhǔn)本質(zhì)為找出點云之間的相對位置關(guān)系。因此，通過確定空間點云的投影位置，就能確定空間點云的位置關(guān)系?？臻g點云三坐標(biāo)平面投影如圖1所示。

圖1 空間點云三坐標(biāo)平面投影圖

由圖1可知：兩個錯位(未配準(zhǔn)的)點云模型在二維平面的投影是不重合的，兩重合(配準(zhǔn)后的)點云在二維平面的投影是重合的。本文基于此原理，提出了一種降維評價三維空間點云位置關(guān)系的新方法。

1.3 信息熵評價點云空間位置關(guān)系

對于待配準(zhǔn)的兩片點云，由圖1可以看出，當(dāng)兩片點云的角度沒有偏差的時候，其投影也沒有偏差。當(dāng)點云角度偏差為0°時，兩片點云在該平面上的投影相對聚集。此時，投影點云分布密度的不均勻性最大。當(dāng)點云角度偏差不為0°時，由于兩片點云不在同一坐標(biāo)系下，故投影點云將較為均勻分布在整個投影平面上。此時，投影點云分布密度的不均勻性較小。由不同點云偏差角度可得到不同的投影點云分布，因而有望利用投影點云分布密度估計點云的空間位置。

根據(jù)空間點云僅在一個平面的投影，不能非常精確地估計點云位置關(guān)系。如在點云位置相差90°時，利用一個平面的投影尚不能估計出點云空間位置關(guān)系。而利用三個坐標(biāo)平面投影熵之和，能消除點云錯位90°不能估計的情況。

將兩片點云投影到XY、YZ、XZ三坐標(biāo)平面，依據(jù)式(1)和式(2)計算得到點云在XY、YZ、XZ平面的投影熵，分別為SEXY、SEYZ、SEXZ。

定義總的點云投影熵E為：

E=SEXY+SEYZ+SEXZ

(3)

從式(3)可知，點云的投影分布越密集，總投影熵就越小。

2 基于投影的點云配準(zhǔn)

本文采用總投影熵作為遺傳算法的目標(biāo)函數(shù)，來尋找空間變換的最優(yōu)解。第一步是設(shè)置空間最大的變換空間；第二步是初始化目標(biāo)種群并計算其適應(yīng)度值；第三步是進(jìn)行個體選擇、交叉和變異以產(chǎn)生子代個體，直到滿足設(shè)定的遺傳代數(shù)或目標(biāo)函數(shù)收斂的條件來終止遺傳算法；第四步是得到最優(yōu)空間變換矩陣，并應(yīng)用于配準(zhǔn)點云，得到配準(zhǔn)結(jié)果。

2.1 變換空間

兩次掃描的點云空間坐標(biāo)系是任意的，而在遺傳算法中需要設(shè)置其變換空間最大范圍。因此，需要尋找出最大變換空間。算法的求解步驟如下。

①設(shè)點云P中有N個點，點云Q中有M個點，分別計算出中心。計算式為：

(3)

(4)

②中心化點云。

(5)

③計算出兩片點云在X、Y、Z方向上的最大值和最小值。

④旋轉(zhuǎn)矩陣R參數(shù)。

對于旋轉(zhuǎn)矩陣[α，β，γ]，如果確定了繞軸旋轉(zhuǎn)的角度α、β、γ,就能求解旋轉(zhuǎn)矩陣。在三維空間中，繞其中一個坐標(biāo)軸最大轉(zhuǎn)動角度為2π，因此選用旋轉(zhuǎn)角度取值區(qū)間為[-π，π]，則α∈[-π，π]、β∈[-π，π]、γ∈[-π，π]。

⑤平移矩陣T參數(shù)為：

(6)

(7)

(8)

2.2 編碼方案

本文使用給定長度的二進(jìn)制符號串來表示群體中的個體，其等位基因由二值符號集{0,1}所組成。

①編碼。設(shè)某一參數(shù)的取值范圍為[W1，W2]，采用長度為u的二進(jìn)制編碼符號來表示該參數(shù)，則它共能產(chǎn)生2u種不同的編碼，可使參數(shù)編碼時的對應(yīng)關(guān)系為：

0000L 00=0→W1

0000L 01=1→W1+σ

0000L 02=2→W1+ 2σ

… …

1111L 11=2u-1→W2

式中：W1為參數(shù)取值下限；W2為參數(shù)取值上限；u為編碼長度；σ為編碼間距。

②解碼。假如某一個體的編碼為bubu-1…b2b1，則對應(yīng)的解碼公式為：

(9)

2.3 適應(yīng)度函數(shù)

在遺傳算法中，個體的適應(yīng)度大小決定了該個體被淘汰的概率。個體的適應(yīng)度值越小，其越可能被淘汰。而在本文中，需要目標(biāo)函數(shù)值越小越好，適應(yīng)度值越大越好。所以，通過目標(biāo)函數(shù)構(gòu)造的適應(yīng)度函數(shù)為:

FitnV=CE

(10)

式中：E為總投影熵；C=0.618。

2.4 算法實現(xiàn)

本文遺傳算法的各進(jìn)化算子分別采用輪盤賭方法、單點交叉和單點變異，并將空間三坐標(biāo)平面的投影熵之和作為遺傳算法的目標(biāo)函數(shù)。算法步驟如下。

①最大變量域中初始化種群P，并設(shè)定最大遺傳代數(shù)G。

②種群P分別作用于目標(biāo)點云，求取每次初始變換空間的X、Y、Z坐標(biāo)方向最大最小值，確定最大變換空間位置。

③計算個體的目標(biāo)函數(shù)和適應(yīng)度值。

④選取種群中最優(yōu)個體，得到其總的點云投影熵E，令全局最小總的點云投影熵Emin=E。

⑤根據(jù)適應(yīng)度值進(jìn)行優(yōu)良個體選擇并使用最優(yōu)保存策略，對選擇的種群進(jìn)行交叉和變異操作，產(chǎn)生新一代進(jìn)化種群。

⑥求解新一代種群所有個體的適應(yīng)度值FitnV，比較該代最優(yōu)個體的總的點云投影熵SE′和全局最小總的點云投影熵Emin。如果E′

⑦檢查當(dāng)前代數(shù)是否達(dá)到最大代數(shù)G，以及E是否收斂。若沒有達(dá)到，則轉(zhuǎn)到步驟⑤，繼續(xù)求解；否則，輸出全局最優(yōu)個體，解碼得到空間最優(yōu)旋轉(zhuǎn)、平移矩陣。

⑧更新點云位置，輸出配準(zhǔn)點云。

基于投影的點云配準(zhǔn)算法流程如圖2所示。

圖2 基于投影的點云配準(zhǔn)算法流程圖

3 試驗結(jié)果與分析

為了驗證算法的可行性、魯棒性和有效性，在Intel Core-i5、8 GB內(nèi)存的Windows 7操作系統(tǒng)中，基于MATLAB平臺進(jìn)行配準(zhǔn)試驗。該試驗主要以有缺陷和有大量噪聲點的點云來進(jìn)行驗證。

3.1 點云空間位置關(guān)系

圖3 不同算法的空間位置評價示意圖

由圖3可知：MSE、SDE和總投影熵算法都能滿足空間位置的評價。當(dāng)點云完全配準(zhǔn)時，三種評價算法都是全局最小。但此過程中，MSE算法運(yùn)行時間為93.159 s，SDE算法運(yùn)行時間為3.135 s，本文算法(總投影熵)運(yùn)行時間為2.527 s。由此說明，本文算法耗時最少。由于遺傳算法尋優(yōu)時需要不斷評價個體的空間位置，因此需要頻繁的調(diào)用。而本文算法在滿足準(zhǔn)確性要求的條件下，具有快速性的特性,很適合作為遺傳算法目標(biāo)函數(shù)。

3.2 不同類型模型配準(zhǔn)結(jié)果分析

為了說明本文算法的有效性，將本文算法分別應(yīng)用于完整的、部分缺失的、有噪聲的點云模型。不同類型模型的配準(zhǔn)效果如圖4所示。由圖4可知：本文的粗配準(zhǔn)算法對于三種點云模型都具有很好的配準(zhǔn)效果，能夠為精配準(zhǔn)算法提供優(yōu)良的初始位置。設(shè)定最大遺傳代數(shù)G=80，初始種群的個體數(shù)為80，交叉概率為0.9，變異概率為0.09。

圖4 不同類型模型的配準(zhǔn)效果圖

以圖4中(a)模型為例，圖5為遺傳代數(shù)與適應(yīng)度值的變化關(guān)系圖。

圖5 遺傳代數(shù)與適應(yīng)度值變化關(guān)系圖

圖5顯示了每一代種群適應(yīng)度平均值和每一代種群中最優(yōu)個體的適應(yīng)度值。本文的配準(zhǔn)算法采用遺傳算法作為搜索策略。由圖5可知：隨著遺傳代數(shù)的增加，種群朝著最優(yōu)解的方向遺傳進(jìn)化，最優(yōu)個體也隨著遺傳進(jìn)化而趨近于全局最優(yōu)解。由此說明，本文采用遺傳算法求解最優(yōu)空間變換矩陣是有效的。

3.3 不同粗配準(zhǔn)算法效果比較

為了驗證本文算法的優(yōu)異性，選用四種粗配準(zhǔn)算法進(jìn)行比較。不同算法的配準(zhǔn)效果對比如圖6所示。圖6(b)為文獻(xiàn)[2]中的PCA算法；圖6(c)為文獻(xiàn)[12]中四點匹配法(4-point congrugent set，4PCS)；圖6(d)為文獻(xiàn)[6]中MSE算法；圖6(e)為文獻(xiàn)[5]中SDE算法。以下模型是西南科技大學(xué)獎杯，參考點云是完整的點云，目標(biāo)點云是含有部分噪聲的點云。設(shè)定最大遺傳代數(shù)G=50，初始種群的個體數(shù)為40，交叉概率為0.9，變異概率為0.05。由圖6可知：PCA算法配準(zhǔn)效果最差，4PCS和MSE算法配準(zhǔn)效果較好，SDE算法配準(zhǔn)效果不夠理想，本文算法效果最好。

圖6 不同算法的配準(zhǔn)效果對比圖

不同算法運(yùn)行時間對比如表1所示。

表1 不同算法運(yùn)行時間對比

Tab.1 Comparison of running timeof different algorithmss

模型算法PCA4PCSMSESDE本文獎杯1.21100.65110.6370.6560.32

由表1可知:PCA算法用時最少，本文算法相對4PCS、MSE和SDE算法用時較少。再結(jié)合圖6結(jié)果，可得本文算法的配準(zhǔn)性能最高。

4 結(jié)束語

本文通過計算三視圖中的投影熵來描述兩片點云的位置關(guān)系，提出了一種降維評價點云空間位置的方法。由于可以把點云配準(zhǔn)作為優(yōu)化問題處理，利用該評價方法簡單快速的特點，再采用遺傳算法作為搜索方法、投影熵作為目標(biāo)函數(shù)，可以準(zhǔn)確、快速地尋找出最優(yōu)的匹配。該配準(zhǔn)算法利用了遺傳算法，但還沒有充分挖掘遺傳算法的特性，在運(yùn)行效率方面可以進(jìn)一步提高。