基于K-means++的多視圖點云配準技術

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

(1.廣西大學計算機與電子信息學院，廣西 南寧 530004； 2.廣西多媒體通信與網絡技術重點實驗室，廣西 南寧 530004)

0 引 言

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

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

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

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

1 本文方法

1.1 基于K-means++的點云聚類

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

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

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

(1)

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

(2)

其中，a為當前已有的質心個數(shù)。

(3)

Step5更新質心，公式如下：

(4)

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

1.2 基于K-means++的多視圖點云配準

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

(5)

算法1 基于K-means++聚類的多視圖點云配準

Begin:

1 對P添加初始的剛性變換，得到多視圖點集P′;

2q=0;

Repeat:

3.1h=0;q=q+1;

3.2 Repeat:

3.2.1h=h+1;

3.2.4 計算質心的位移差值E;

UntilE達到收斂條件或h>H;

3.3 fori=2:N

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

3.3.2 對多視圖點集進行剛性變換;

End

End

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

2 實驗與結果分析

2.1 實驗建立與評價指標

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

圖1 點云模型

圖2 Armadillo模型的多視圖點集可視化

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

(6)

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

(7)

2.2 對比試驗與結果分析

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

2.2.1 多視圖點集配準精度

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

圖3 不同算法在多視圖點集的配準結果橫截面

圖4 不同算法在多視圖點集的配準結果

表1 不同算法在多視圖點集的配準精度的比較

2.2.2 多視圖點集配準魯棒性

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

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

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

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

3 結束語

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