梁正友，王 璐，李軒昂，楊 鋒

(1.廣西大學(xué)計(jì)算機(jī)與電子信息學(xué)院，廣西 南寧 530004； 2.廣西多媒體通信與網(wǎng)絡(luò)技術(shù)重點(diǎn)實(shí)驗(yàn)室，廣西 南寧 530004)

0 引 言

在大多數(shù)情況下，深度數(shù)據(jù)在采集過程中無法一次性獲取目標(biāo)對(duì)象的全貌，因此，需要一種將同一場(chǎng)景的2個(gè)或2個(gè)以上的點(diǎn)云數(shù)據(jù)疊加至同一坐標(biāo)系中的技術(shù)，即點(diǎn)云配準(zhǔn)技術(shù)。該技術(shù)目前已被廣泛應(yīng)用于假體設(shè)計(jì)、文物修復(fù)及地質(zhì)勘探等領(lǐng)域[1-3]，可根據(jù)數(shù)據(jù)集的規(guī)模分為成對(duì)配準(zhǔn)和多視圖配準(zhǔn)[4-5]。1992年，Besl和Mckay[6]提出的迭代最近點(diǎn)(Iterative Closest Point， ICP)算法是一種常見且變體最多的配準(zhǔn)算法[7]，其基本思想是通過計(jì)算最近歐氏距離建立對(duì)應(yīng)的點(diǎn)對(duì)關(guān)系，并迭代地調(diào)整點(diǎn)云間的剛性變換參數(shù)(R,T)使點(diǎn)云間的空間偏差最小化，從而獲得配準(zhǔn)結(jié)果。其變體例如Chetverikov等人[8]提出的裁剪ICP算法(Trimmed Iterative Closest Point， TrICP)，該方法可用于存在部分重疊的點(diǎn)云間的配準(zhǔn)，但只適用于重疊率為50%以下的點(diǎn)集；Li等人[9]利用K-D樹結(jié)構(gòu)存儲(chǔ)點(diǎn)云數(shù)據(jù)并用于領(lǐng)域搜索中，使大量的點(diǎn)云數(shù)據(jù)得到高效管理，從而同時(shí)提升了配準(zhǔn)的精度和效率。然而，在數(shù)據(jù)集的視圖規(guī)模較大時(shí)，將這些方法運(yùn)用于成對(duì)配準(zhǔn)，會(huì)使各視圖的配準(zhǔn)誤差不斷累積，且配準(zhǔn)過程中存在初次掃描的視圖和末次掃描的視圖無法進(jìn)行配準(zhǔn)的問題，從而導(dǎo)致配準(zhǔn)精度下降[10-11]。

多視圖配準(zhǔn)則可以減少誤差積累的情況，通過依次對(duì)所有視圖進(jìn)行一致配準(zhǔn)，使成對(duì)配準(zhǔn)造成的誤差均勻地分布到所有視圖中[12]。受到機(jī)器學(xué)習(xí)的啟發(fā)，研究者將深度學(xué)習(xí)方法引入多視圖配準(zhǔn)技術(shù)中。Chang等人[13]提出采用2個(gè)連續(xù)卷積神經(jīng)網(wǎng)絡(luò)(Convolutional Neural Networks， CNN)模型估計(jì)點(diǎn)云間的剛性變換，改進(jìn)了配準(zhǔn)技術(shù)中存在的耗時(shí)問題；Kurobe等人[14]提出了基于CorsNet連接局部及全局特征集成更多的信息用于回歸點(diǎn)云的對(duì)應(yīng)關(guān)系，從而得到準(zhǔn)確且高效的結(jié)果。

聚類算法作為無監(jiān)督學(xué)習(xí)中常見的分類算法[15]，在配準(zhǔn)問題中取得了較好的效果。Zhou等人[16]提出了一種利用K-means算法最小化積分誤差和優(yōu)化融合點(diǎn)位置的方法，將鄰近視圖重疊部分的數(shù)據(jù)進(jìn)行雙向移動(dòng)，但該方法并未涉及點(diǎn)云間剛性變換的更新；Evangelidis等人[17]提出了一種基于聚類的聯(lián)合配準(zhǔn)方法，使用批處理和增量期望最大化方法估計(jì)高斯混合模型的參數(shù)和最優(yōu)集合用以配準(zhǔn)，但該方法的魯棒性和精度有限；Ji等人[18]通過修正加權(quán)平均法向量節(jié)點(diǎn)，并利用均值漂移聚類算法得到局部最大值模型，其配準(zhǔn)速度較快，但準(zhǔn)確率有限；Zhu等人[19]利用K-means算法對(duì)多視圖進(jìn)行配準(zhǔn)，能夠提升多視圖點(diǎn)集的配準(zhǔn)效率。

本文針對(duì)多視圖點(diǎn)集中可能存在噪聲、離群點(diǎn)及遮擋等影響點(diǎn)云配準(zhǔn)結(jié)果的問題，提出一種基于K-means++[20]的多視圖點(diǎn)云配準(zhǔn)算法。首先，利用K-means++算法的隨機(jī)播種技術(shù)[21]對(duì)各視圖點(diǎn)集求取質(zhì)心并進(jìn)行聚類，然后根據(jù)K-D樹的最近鄰近點(diǎn)算法(K-NearestNeighbor， KNN)[22]建立各視圖的對(duì)應(yīng)點(diǎn)集，最后根據(jù)各視圖聚類結(jié)果對(duì)整體點(diǎn)云進(jìn)行成對(duì)配準(zhǔn)，依照掃描次序運(yùn)用ICP算法求取點(diǎn)集間的剛性變換矩陣，從而得到配準(zhǔn)結(jié)果。在Stanford三維點(diǎn)云數(shù)據(jù)集中的實(shí)驗(yàn)結(jié)果表明，本文提出的方法在配準(zhǔn)精度上優(yōu)于其他方法，且對(duì)添加噪聲、存在數(shù)據(jù)缺失的點(diǎn)集具有魯棒性。

1 本文方法

1.1 基于K-means++的點(diǎn)云聚類

K-means++算法作為一種高效聚類算法，已廣泛應(yīng)用于各個(gè)領(lǐng)域，其基本思想是：首先，從數(shù)據(jù)集中隨機(jī)選取一個(gè)點(diǎn)作為初始質(zhì)心；其次，通過隨機(jī)播種技術(shù)選取其他的質(zhì)心，并認(rèn)為與當(dāng)前已存在的質(zhì)心距離最遠(yuǎn)的點(diǎn)，具有更高的概率成為新的質(zhì)心；最后迭代地對(duì)數(shù)據(jù)集進(jìn)行分簇與質(zhì)心的更新，直至達(dá)到收斂條件則停止。

對(duì)于多視圖點(diǎn)集，本文先對(duì)每個(gè)視圖進(jìn)行下采樣，并給定初始的剛性變換，則基于K-means++的點(diǎn)云聚類算法過程描述如下：

p′i,j=Ri×pi,j+ti

(1)

Step3根據(jù)隨機(jī)播種技術(shù)，將與已有質(zhì)心點(diǎn)最遠(yuǎn)的點(diǎn)作為新的質(zhì)心，即通過重復(fù)遍歷點(diǎn)集P′中的每個(gè)點(diǎn)，并根據(jù)公式(2)，分別計(jì)算其與目前質(zhì)心的歐氏距離，從而選取出初始的質(zhì)心集合。

(2)

其中，a為當(dāng)前已有的質(zhì)心個(gè)數(shù)。

(3)

Step5更新質(zhì)心，公式如下：

(4)

Step6計(jì)算質(zhì)心集合的位移差值，若其小于設(shè)定閾值或達(dá)到預(yù)定最大迭代次數(shù)時(shí)，得到最終的聚類結(jié)果，否則回到Step4。

1.2 基于K-means++的多視圖點(diǎn)云配準(zhǔn)

在近幾年的研究中，已有學(xué)者將聚類算法用于多視圖配準(zhǔn)。本文將多視圖配準(zhǔn)問題看作是一種擴(kuò)展的聚類問題，即假設(shè)所有參與的配準(zhǔn)點(diǎn)集均由聚類后的點(diǎn)云數(shù)據(jù)提取，其質(zhì)心能夠組成一個(gè)精確的模型。因此，本文將基于K-means++的點(diǎn)云聚類應(yīng)用于多視圖配準(zhǔn)中，通過K-means++算法從各視圖的點(diǎn)云數(shù)據(jù)中提取質(zhì)心，從而得到配準(zhǔn)算法所需的點(diǎn)集。

(5)

算法1 基于K-means++聚類的多視圖點(diǎn)云配準(zhǔn)

Begin:

1 對(duì)P添加初始的剛性變換，得到多視圖點(diǎn)集P′;

2q=0;

Repeat:

3.1h=0;q=q+1;

3.2 Repeat:

3.2.1h=h+1;

3.2.4 計(jì)算質(zhì)心的位移差值E;

UntilE達(dá)到收斂條件或h>H;

3.3 fori=2:N

3.3.1 根據(jù)ICP算法計(jì)算各聚類點(diǎn)云與點(diǎn)集間的剛性變換矩陣;

3.3.2 對(duì)多視圖點(diǎn)集進(jìn)行剛性變換;

End

End

由算法1分析可得本文方法的每次迭代中不同操作的時(shí)間復(fù)雜度：設(shè)M為N個(gè)視圖的總點(diǎn)云數(shù)量，K為聚類質(zhì)心的數(shù)量，則建立K-D樹的時(shí)間復(fù)雜度為O(KlogK),點(diǎn)集分簇的時(shí)間復(fù)雜度為O(MlogK)，更新聚類中心和計(jì)算剛性變換的時(shí)間復(fù)雜度都為O(M)。

2 實(shí)驗(yàn)與結(jié)果分析

2.1 實(shí)驗(yàn)建立與評(píng)價(jià)指標(biāo)

本文的數(shù)據(jù)集采用Stanford三維點(diǎn)云數(shù)據(jù)集中的模型，分別是Bunny、Armadillo、Buddha和Dragon，各模型如圖1所示。其中，Bunny模型包括10個(gè)視圖，共362272個(gè)點(diǎn)；Armadillo模型包括12個(gè)視圖，共307652個(gè)點(diǎn)；Buddha模型包括15個(gè)視圖，共1099005個(gè)點(diǎn)；Dragon模型包括15個(gè)視圖，共469193個(gè)點(diǎn)。這些模型的各個(gè)視圖存在一定數(shù)量的離群點(diǎn)以及由遮擋造成的數(shù)據(jù)缺失。以Armadillo模型為例的多視圖點(diǎn)集可視化結(jié)果如圖2所示。

圖1 點(diǎn)云模型

圖2 Armadillo模型的多視圖點(diǎn)集可視化

為了驗(yàn)證所提出方法的配準(zhǔn)結(jié)果，實(shí)驗(yàn)環(huán)境為Windows 10(64位)操作系統(tǒng)、Intel(R)Core(TM)i5-8250U CPU@1.60 GHz計(jì)算機(jī)，代碼在Matlab 2018b上實(shí)現(xiàn)。為了消除實(shí)驗(yàn)過程中的隨機(jī)性，分別對(duì)各方法進(jìn)行了50次蒙特卡洛實(shí)驗(yàn)，并取其旋轉(zhuǎn)誤差ER和平移誤差Et×10-3m的均值。設(shè)多視圖點(diǎn)集添加的隨機(jī)真實(shí)值為(Ri,g,ti,g)，通過配準(zhǔn)算法得到的剛性變換矩陣為(Ri,w,ti,w)，則通過Forbenius范數(shù)計(jì)算旋轉(zhuǎn)誤差ER，度量公式表示為：

(6)

平移誤差Et×10-3m的度量公式表示為：

(7)

2.2 對(duì)比試驗(yàn)與結(jié)果分析

為充分描述本文方法的性能，采用4種配準(zhǔn)算法與其進(jìn)行對(duì)比，包括：基于ICP的多視圖配準(zhǔn)算法、基于TrICP的多視圖配準(zhǔn)方法[19]、基于K-means的多視圖配準(zhǔn)方法[24]和基于遺傳算法(Genetic Algorithm, GA)的多視圖點(diǎn)云配準(zhǔn)方法(GA-TrICP)[25]。在實(shí)驗(yàn)中，將點(diǎn)云聚類的平均點(diǎn)數(shù)設(shè)置為num=25，設(shè)X為總點(diǎn)云數(shù)，則質(zhì)心的數(shù)量K=X/num。

2.2.1 多視圖點(diǎn)集配準(zhǔn)精度

圖3和圖4分別描述了不同算法在4個(gè)多視圖點(diǎn)集進(jìn)行實(shí)驗(yàn)的隨機(jī)配準(zhǔn)結(jié)果的橫截面圖和整體模型的可視化結(jié)果，表1為詳細(xì)的配準(zhǔn)精度。可以看出：為多視圖點(diǎn)集分別添加隨機(jī)的空間變換后，基于ICP的多視圖配準(zhǔn)算法的平移誤差較大，這是由于ICP算法本身易于陷入局部最優(yōu)解，往往不能獲得良好的配準(zhǔn)結(jié)果；基于TrICP的多視圖配準(zhǔn)算法的配準(zhǔn)結(jié)果與本文相比略差，在Dargon和Buddha模型的配準(zhǔn)中平移誤差較大，無法獲得較好的效果；基于K-means的多視圖配準(zhǔn)方法和基于GA算法的多視圖點(diǎn)云配準(zhǔn)方法在部分模型上配準(zhǔn)效果欠佳，且基于GA算法的多視圖點(diǎn)云配準(zhǔn)方法需要大量的參數(shù)設(shè)置。綜上所述，本文方法利用K-means++算法將多視圖配準(zhǔn)問題看作一個(gè)拓展的聚類問題，對(duì)多視圖點(diǎn)集進(jìn)行聚類，并利用質(zhì)心組成的模型對(duì)各視圖交替地計(jì)算其對(duì)應(yīng)的剛性變換矩陣，在各個(gè)模型的配準(zhǔn)中都能夠獲得滿足配準(zhǔn)需求的結(jié)果，且具備較好的配準(zhǔn)精度。

圖3 不同算法在多視圖點(diǎn)集的配準(zhǔn)結(jié)果橫截面

圖4 不同算法在多視圖點(diǎn)集的配準(zhǔn)結(jié)果

表1 不同算法在多視圖點(diǎn)集的配準(zhǔn)精度的比較

2.2.2 多視圖點(diǎn)集配準(zhǔn)魯棒性

為了更好地描述本文方法的魯棒性，表2、表3、表4分別為不同算法在分別添加[-0.01f,0.01f]、[-0.02f,0.02f]和[-0.03f,0.03f]的高斯噪聲后得到的配準(zhǔn)結(jié)果。從表中可以看出：在添加高斯噪聲后，相比基于TrICP算法、K-means算法和GA-TrICP算法的多視圖配準(zhǔn)算法，本文方法依然能夠達(dá)到較好的精度。綜上所述，本文方法結(jié)合K-means++算法應(yīng)用于多視圖配準(zhǔn)，在添加隨機(jī)的初始空間變換及噪聲的多視圖數(shù)據(jù)集中，均能取得較好的配準(zhǔn)結(jié)果，與其他同類算法比較，本文為多視圖配準(zhǔn)技術(shù)提供了一種更具魯棒性的方法。

表2 不同算法在添加[-0.01f,0.01f]高斯噪聲后，點(diǎn)集的配準(zhǔn)精度的比較

表3 不同算法在添加[-0.02f,0.02f]高斯噪聲后，點(diǎn)集的配準(zhǔn)精度的比較

表4 不同算法在添加[-0.03f,0.03f]高斯噪聲后，點(diǎn)集的配準(zhǔn)精度的比較

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

對(duì)存在噪聲、離群點(diǎn)的大規(guī)模點(diǎn)集進(jìn)行配準(zhǔn)具有挑戰(zhàn)性，本文針對(duì)這一問題提出了一種基于K-means++的多視圖點(diǎn)云配準(zhǔn)方法。通過K-means++算法對(duì)各視圖點(diǎn)云數(shù)據(jù)有效地提取質(zhì)心，并根據(jù)其基本思想對(duì)點(diǎn)云完成聚類，其次利用K-D樹結(jié)構(gòu)存儲(chǔ)大規(guī)模數(shù)據(jù)，從而提升對(duì)應(yīng)點(diǎn)集的搜索效率，最后按照掃描順序?qū)⒏饕晥D聚類后的點(diǎn)云數(shù)據(jù)作為源點(diǎn)集，再采用成對(duì)配準(zhǔn)的方法計(jì)算源點(diǎn)集與其他視圖間的剛性變換參數(shù)，從而獲得更好的配準(zhǔn)結(jié)果。本文方法在Stanford三維點(diǎn)云數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，其配準(zhǔn)結(jié)果的精度和魯棒性優(yōu)于近年提出的多視圖配準(zhǔn)算法。