江 盟 ,蔡 勇，張建生

(1.西南科技大學(xué)制造科學(xué)與工程學(xué)院,四川 綿陽(yáng) 621010；2.制造過(guò)程測(cè)試技術(shù)省部共建教育部重點(diǎn)實(shí)驗(yàn)室,四川 綿陽(yáng) 621010)

0 引言

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

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

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

1 點(diǎn)云空間位置關(guān)系評(píng)價(jià)

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

1.1 信息熵的定義

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

(1)

點(diǎn)云P在該平面的投影熵SE定義為：

(2)

1.2 投影

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

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

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

1.3 信息熵評(píng)價(jià)點(diǎn)云空間位置關(guān)系

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

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

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

定義總的點(diǎn)云投影熵E為：

E=SEXY+SEYZ+SEXZ

(3)

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

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

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

2.1 變換空間

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

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

(3)

(4)

②中心化點(diǎn)云。

(5)

③計(jì)算出兩片點(diǎn)云在X、Y、Z方向上的最大值和最小值。

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

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

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

(6)

(7)

(8)

2.2 編碼方案

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

①編碼。設(shè)某一參數(shù)的取值范圍為[W1，W2]，采用長(zhǎng)度為u的二進(jìn)制編碼符號(hào)來(lái)表示該參數(shù)，則它共能產(chǎn)生2u種不同的編碼，可使參數(shù)編碼時(shí)的對(duì)應(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為編碼長(zhǎng)度；σ為編碼間距。

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

(9)

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

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

FitnV=CE

(10)

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

2.4 算法實(shí)現(xiàn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 不同算法的空間位置評(píng)價(jià)示意圖

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

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

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

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

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

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

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

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

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

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

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

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

Tab.1 Comparison of running timeof different algorithmss

模型算法PCA4PCSMSESDE本文獎(jiǎng)杯1.21100.65110.6370.6560.32

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

4 結(jié)束語(yǔ)

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