基于區(qū)域分割的低覆蓋點云配準算法

湯慧 周明全 耿國華

摘 要：針對低覆蓋點云配準的時間復雜度高、收斂速度緩慢以及對應(yīng)點匹配易錯等問題，提出一種基于區(qū)域分割的點云配準算法。首先，利用體積積分不變量計算點云上點的凹凸性，并提取凹凸特征點集;然后，采用基于混合流形譜聚類的分割算法對特征點集進行區(qū)域分割，并采用基于奇異值分解（SVD）的迭代最近點（ICP）算法對區(qū)域進行配準，從而實現(xiàn)點云的精確配準。實驗結(jié)果表明，所提算法通過區(qū)域分割可以大幅提高點云區(qū)域的覆蓋率，并且無需迭代即可計算剛體變換的最佳旋轉(zhuǎn)矩陣，其配準精度比已有算法提高了10%以上，配準時間降低了20%以上。因此，所提算法是一種精度高、速度快的低覆蓋點云配準算法。

關(guān)鍵詞：點云配準;體積積分不變量;區(qū)域分割;奇異值分解;迭代最近點

中圖分類號：TP391

文獻標志碼：A

Low coverage point cloud registration algorithm based on region segmentation

TANG Hui1，2， ZHOU Mingquan1，3*， GENG Guohua1

1.College of Information Science and Technology， Northwest University， Xian Shaanxi 710127， China;

2.Experimental Training Teaching Center， Xian University of Finance and Economics， Xian Shaanxi 710010， China;

3.College of Information Science and Technology， Beijing Normal University， Beijing 100875， China

Abstract：

Aiming at the problems of high time complexity， slow convergence speed and errorprone matching of low coverage point cloud registration， a point cloud registration algorithm based on region segmentation was proposed. Firstly， the volume integral invariant was used to calculate the concavity and convexity of points on the point cloud， and then the concavity and convexity feature point sets were extracted. Secondly， the regions of the feature points were partitioned by the segmentation algorithm based on the mixed manifold spectral clustering， and the regions were registered by the Iterative Closest Point （ICP） algorithm based on Singular Value Decomposition （SVD）， so that the accurate registration of point clouds could be achieved. The experimental results show that the proposed algorithm can greatly improve the coverage of point clouds by region segmentation， and the optimal rotation matrix of rigid body transformation can be calculated without iteration. The algorithm has the registration accuracy increased by more than 10% and the registration time reduced by more than 20%. Therefore， the proposed algorithm can achieve fast and accurate registration of point clouds with low coverage.

Key words：

point cloud registration; volume integral invariant; area segmentation; Singular Value Decomposition （SVD）; Iterative Closest Point （ICP）

0?引言

點云配準是點云數(shù)據(jù)處理的一個重要研究內(nèi)容，是后續(xù)三維點云重建的技術(shù)基礎(chǔ)。由于受環(huán)境和三維數(shù)據(jù)采集設(shè)備分辨率等多種因素的影響，在對實物數(shù)字化時采集到的每個點云數(shù)據(jù)往往只覆蓋了實物模型表面的部分數(shù)據(jù)信息，而且還存在旋轉(zhuǎn)和平移等剛體變換問題。因此，為了獲取物體表面的完整點云數(shù)據(jù)信息，必須通過點云配準將不同角度的點云數(shù)據(jù)變換到同一坐標系下。

點云配準的算法有很較多，主要有重心重合法[1]、標定點法[2]以及特征提取法[3-4]等。重心重合法通過將兩個點云的重心重合來實現(xiàn)點云配準;標定點法是一種通過在物體表面貼上標定點并利用標定點進行點云配準的方法;特征提取法則是利用物體表面上的一些幾何特征，如特征點、曲率、表面紋理以及邊緣等，對特征進行提取和描述，通過確定特征之間的對應(yīng)關(guān)系來實現(xiàn)點云配準。

目前應(yīng)用最廣泛的點云配準算法是由Besl 等[5]提出的迭代最近點（Iterative Closest Point， ICP）算法。ICP 算法計算簡便直觀、配準精度高，但對待配準點云的初始位置的依賴性較強，并要求兩個點云之間存在一定的包含關(guān)系，因此在實際配準中容易陷入局部最優(yōu)，導致配準效率不高。為了克服 ICP 算法的局限性，國內(nèi)外學者對ICP 算法進行了改進研究，相繼提出PICP（Probability ICP）算法[6]、IAICP（IntensityAssisted ICP）算法[7]、MICP（Modified ICP）算法[8]以及CICP（Cluster ICP）算法[9]等多種改進的ICP算法。這些配準算法并不具有普適性，特別是對低覆蓋率點云的配準效果不佳。

對于低覆蓋率的點云，邵紅旭[10]提出了一種基于重疊區(qū)域的改進ICP配準算法，提高了低覆蓋點云的配準精度;Xu等[11]采用結(jié)合顏色和深度信息的低覆蓋點云配準算法實現(xiàn)了工業(yè)機器人的姿態(tài)估計; Ding等[12]提出了一種基于自適應(yīng)距離函數(shù)的點云配準算法，通過描述最短點面距離實現(xiàn)低覆蓋點云的配準; Wu等[13]提出一種基于X射線斷層掃描的點云配準算法，可以實現(xiàn)不同覆蓋率的砂粒碎片的斷裂面匹配;Liu等[14]通過分析深度測量誤差模型和權(quán)重函數(shù)實現(xiàn)了低覆蓋點云的精確配準。雖然這些低覆蓋點云配準算法在一定程度上提高了點云配準的精度，但是仍然存在算法耗時長、魯棒性低等缺點。

針對低覆蓋點云配準的時間復雜度高、收斂速度緩慢、對應(yīng)點匹配易錯等問題，本文提出一種基于區(qū)域分割的點云配準算法。首先，采用體積積分不變量計算點的凹凸性，并提取凹凸特征點;然后，對特征點集進行區(qū)域分割，并將奇異值分解（Singular Value Decomposition， SVD）應(yīng)用到ICP算法中，以此實現(xiàn)區(qū)域特征點集的配準。該算法無需迭代即可計算兩個特征點集的剛體變換，具有較高的配準精度和配準速度。

1?提取凹凸特征點

由于體積積分不變量可以穩(wěn)定且多尺度地描述點云表面的凹凸程度[10]，因此采用體積積分不變量可以判斷其點的凹凸性，并提取凹的和凸的特征點。設(shè)Q代表一個單位球，p+rQ表示半徑是r、中心是點p的球。那么體積積分不變量Vr（p）定義為

Vr（p）=∫p+rQg（x）w（p-x）dx（1）

式中： g（x）表示特征函數(shù)，w（p-x）表示權(quán)重函數(shù)。

將式（1）中的特征函數(shù)g（x）換成ID（x），并令w（p-x）=1，則體積積分不變量Vr（p）的計算式轉(zhuǎn)化為：

Vr（p）=∫p+rQID（x）dx（2）

特征函數(shù)ID（x）的含義為：當x在曲面外側(cè)，ID（x）=1;當x在曲面內(nèi)側(cè)，ID（x）=0。Vr（p）的幾何意義就是球p+rQ在曲面外側(cè)的體積，如圖1所示。

由圖1可知，Vr（p）反映了曲面在p點處的凹凸程度。當Vr（p）=2πr3/3 時，即Vr（p）是球體積的一半時，p在半徑r鄰域內(nèi)為平面頂點。當半徑r越大，Vr（p）越大，且p+rQ內(nèi)部噪聲與Vr（p）無關(guān)。

頂點的凹凸程度采用點的體積積分不變量與球體積的比值來定義，定義式為：

charV（p）=Vr（p）V（Q）=34πr3∫p+rB1D（x）dx（3）

于是有，當charV（p）=0.5時，點p位于平坦面;當charV（p）>0.5，點p位于凸面;charV（p）<0.5，點p位于凹面。

本文提取的特征點即為以上計算的凹凸特征點。

2?特征點區(qū)域分割

對于上述提取的凹凸特征點，采用一種基于混合流形譜聚類的分割算法[15]對其進行區(qū)域分割。該算法通過對特征點構(gòu)建鄰接矩陣實現(xiàn)特征點向無向圖中節(jié)點的轉(zhuǎn)換，并將點的對應(yīng)關(guān)系轉(zhuǎn)換成無向圖中的連線，從而將特征點的區(qū)域分割問題轉(zhuǎn)換為譜空間的聚類問題。

首先利用混合概率主成分分析（Mixtures of Probabilistic Principal Component Analysis， MPPCA）法[16]提取特征點之間的幾何關(guān)系，并構(gòu)造鄰接矩陣。MPPCA采用M個線性主成分分析（Principal Component Analysis， PCA）來描述點云結(jié)構(gòu)，可以有效避免PCA對特征點集的類橢圓分布的要求，同時增強對復雜幾何結(jié)構(gòu)點云的分析能力。MPPCA利用最大期望（Expectation Maximization， EM）算法[17]得到最優(yōu)描述點云分布的M個線性主成分分析器和每個點xi對應(yīng)于M個線性主成分分析器的概率密度分布。

對于第m個線性主成分分析器，假設(shè)任意一個點xi對應(yīng)于一個降維后的點yi， 計算式為：

xi=Vmyi+μm+εm（4）

式中： Vm表示第m個主成分分析器的主子空間，μm表示分布于第m個分析器的所有點的均值;εm表示噪聲。

假設(shè)yi和εm均服從高斯分布，那么xi關(guān)于m的條件概率為

p（xi|m）=（2π）-32|U|-12exp[-12ZTU-1Z]（5）

式中：Z=xi-μm，U=σ2mI+VmVmT。

目標函數(shù)FMPPCA就是第m個主成分分析器上任意點xi的最大似然估計，計算式為：

FMPPCA=∑Ni=1ln[∑Mm=1πm p（xi|m）]（6）

式中，πm為各個主成分分析器的混合比例，πm≥0，Mm=1πm=1。

描述點云的最佳參數(shù)通過利用EM算法使目標函數(shù)FMPPCA最大化來求解。將混合比例最大的主成分分析器作為點的所在流形，那么點i與點j之間的相似關(guān)系計算式為

2）將SVD用于測量模式矩陣，即Ap=SVDUApΣApVApT，并計算旋轉(zhuǎn)矩陣R（j）=VApUM（j）T;

3）創(chuàng)建旋轉(zhuǎn)模式（j）p=R（j）TAp[p1，p2，…，pN]，并根據(jù)B（j）q的最近點qj構(gòu)建（j）q=[（j）1，（j）2，…，（j）qN];

4）計算配準誤差ε（j）=‖（j）q-（j）p‖F(xiàn)。若ε（j）小于給定閾值則說明兩個點云區(qū)域{Ap，Bq}配準成功，否則區(qū)域?qū)Ap，Bq}為不可配準的區(qū)域。

采用上述的特征點區(qū)域?qū)ε錅史椒?，采用窮舉法將區(qū)域集合{A1，A2，…，As}和{B1，B2，…，Bt}中區(qū)域進行兩兩配準即可實現(xiàn)初始點云點云M和D的最終配準。

4?實驗與結(jié)果分析

本文算法在Visual studio 2010環(huán)境下，Intel Core i7 3.33GHz的CPU、16GB內(nèi)存的Windows 7 64位PC上進行了實現(xiàn)，并且應(yīng)用到了不同覆蓋率的公共點云數(shù)據(jù)模型bunny和dragon的配準，以及文物碎塊點云數(shù)據(jù)模型的斷裂面匹配中。實驗所用數(shù)據(jù)均為采用三維激光掃描儀獲取的點云數(shù)據(jù)模型或由三角網(wǎng)格數(shù)據(jù)模型轉(zhuǎn)化的點云數(shù)據(jù)模型，模型均滿足簡單的三維剛體變換。

4.1?公共點云配準

待配準的三組公共點云數(shù)據(jù)模型分別如圖2所示，每組點云的覆蓋率均低于60%，并且第2組點云的覆蓋率低于第1組，第3組點云的覆蓋率又低于第2組。采用本文所提的基于區(qū)域分割的點云配準算法，首先提取點云的凹凸特征點，然后對特征點進行區(qū)域分割，最后對區(qū)域進行兩兩配準，從而實現(xiàn)點云模型的配準。公共點云的最終配準結(jié)果如圖3所示，顯然，該基于區(qū)域分割的點云配準算法可以實現(xiàn)公共點云的準確配準。

為了進一步驗證所提區(qū)域分割配準算法在配準精度和耗時等方面的性能，針對圖2三組公共點云，再分別采用ICP算法、文獻[19]算法、文獻[20]算法和文獻[13]算法進行配準，五種算法的配準結(jié)果如表1所示。

從表1可見，該基于區(qū)域分割的配準算法最有最高的配準精度和最快的配準速度。與ICP算法相比，基于區(qū)域分割的配準算法的配準精度和速度分別提高了約35%和50%;與文獻[19]算法相比，基于區(qū)域分割的配準算法的配準精度和速度分別提高了約25%和38%;與文獻[20]算法相比，基于區(qū)域分割的配準算法的配準精度和速度分別提高了23%和35%;與文獻[13]算法相比，基于區(qū)域分割的配準算法的配準精度和速度分別提高了約12%和22%。這是由于：ICP 算法對點云的初始相對位置要求較高，且要求待配準點云之間存在包含關(guān)系;文獻[19]算法是一種基于迭代因子的點云配準算法，該迭代因子可以提高點云配準的迭代速度，但是不能提高低覆蓋率點云的配準精度;文獻[20]算法是一種基于內(nèi)部形態(tài)描述子（Intrinsic Shape Signature， ISS）特征點的點云配準算法，該算法通過對點云上特征點的特征序列的匹配來實現(xiàn)點云配準，取得了較精確的匹配結(jié)果，但是對覆蓋率低于60%的點云配準效果不佳;文獻[13]算法是一種基于X射線斷層掃描的點云配準算法，通過基于距離誤差評價的ICP 算法實現(xiàn)了點云配準，但是該算法對密度較高點云的配準效果較好，對低覆蓋點云配準效果不佳。而基于區(qū)域分割的配準算法通過區(qū)域分割有效避免了低覆蓋區(qū)域?qū)c云配準的影響，可以實現(xiàn)點云的快速精確配準。

4.2?文物斷裂面匹配

本文基于區(qū)域分割的點云配準算法可以用于文物碎塊點云數(shù)據(jù)模型的斷裂面匹配，首先采用文獻[21]算法提取碎塊的斷裂面，然后采用該配準算法將斷裂面進行匹配。4組待匹配文物碎塊如圖4所示，碎塊的點云數(shù)據(jù)大小、原始面數(shù)目和斷裂面數(shù)目如表2所示，采用該基于區(qū)域分割的點云配準算法對碎塊斷裂面進行匹配的結(jié)果如圖5所示。從圖5可見，該點云配準算法可以實現(xiàn)文物碎塊斷裂面的有效配準。

為了進一步驗證所提配準算法在配準精度和耗時等方面的性能，針對圖4所示的四組文物碎塊數(shù)據(jù)模型，再分別采用ICP算法、文獻[19]算法、文獻[20]算法和文獻[13]算法對其斷裂面進行匹配，五種算法的匹配結(jié)果如表3所示。表3中的匹配誤差是指可以正確匹配的兩個斷裂面的匹配誤差，耗時是指可以正確匹配的兩個斷裂面的匹配耗時。

從表3可見，本文基于區(qū)域分割的點云配準算法最有最高的匹配精度和最快的匹配速度。與ICP算法相比，區(qū)域分割配準算法的匹配精度和速度分別提高了約35%和50%;與文獻[19]算法相比，區(qū)域分割配準算法的匹配精度和速度分別提高了約24%和37%;與文獻[20]算法相比，區(qū)域分割配準算法的匹配精度和速度分別提高了約22%和35%;與文獻[13]算法相比，區(qū)域分割配準算法的匹配精度和速度分別提高了約13%和23%。

這是由于：ICP 算法對點云的初始相對位置要求較高，且要求待配準點云之間存在包含關(guān)系，因此對文物碎塊斷裂面的匹配效果不佳;文獻[19]算法雖然可以通過動態(tài)調(diào)整迭代因子提高算法的收斂速度，但是對低覆點云的配準效果不佳，而文物碎塊斷裂面大多存在缺損，覆蓋率較低，因此匹配誤差較大;文獻[20]算法通過提取ISS特征點的實現(xiàn)點云配準，但是由于是對文物碎塊的整個斷裂面進行特征點提取，因此對缺損文物的斷裂面匹配效果不佳;文獻[13]算法采用基于距離誤差評價的ICP 算法實現(xiàn)了破損砂粒斷裂面的匹配，但算法是非特征提取算法，不利于缺損文物碎塊粗糙斷裂面的匹配;而提出的基于區(qū)域分割的點云配準算法通過區(qū)域分割有效避免了低覆蓋區(qū)域?qū)嗔衙嫫ヅ涞挠绊?，可以實現(xiàn)文物碎塊斷裂面的有效匹配。

綜上，所提基于區(qū)域分割的點云配準算法不僅適用于公共點云數(shù)據(jù)模型的配準，而且對文物類剛體文物碎塊的斷裂面匹配效果良好。因此說，所提配準算法是一種快速、高精度的低覆蓋率點云模型配準算法。

5?結(jié)語

點云配準研究已久，其應(yīng)用領(lǐng)域涉及工業(yè)設(shè)計、醫(yī)學研究、顱面復原以及文物修復等諸多方面。本文針對低覆蓋率的點云數(shù)據(jù)模型，提出一種基于區(qū)域分割的點云配準算法。該算法通過對點云模型上的特征點進行區(qū)域劃分，不僅大幅降低了點云配準的規(guī)模，而且有效提高了配準區(qū)域的覆蓋率，從而提高了點云配準的時間效率和配準精度。但是本文算法所用的數(shù)據(jù)模型均為低噪聲的采樣均勻的點云數(shù)據(jù)模型，算法并未考慮大量噪聲對點云配準結(jié)果的影響。在今后的研究中，要進一步考慮噪聲和點云密度對點云配準的影響，提出更加普適性的點云配準算法，以提高點云配準算法的應(yīng)用范圍。

參考文獻 （References）

[1]郭延杰，白福忠，張鐵英，等. 基于 Radon 變換與灰度重心法的環(huán)形目標直徑測量方法[J]. 激光與光電子學進展， 2015， 52（8）：209-213. （GUO Y J， BAI F Z， ZHANG T Y， et al. Ring object diameter measuring method based on Radon transform and gray gravity algorithm[J]. Laser and Optoelectronics Progress， 2015， 52（8）：209-213.）

[2]馮筠，陳雨，仝鑫龍，等. 三維顱骨特征點的自動標定[J]. 光學精密工程， 2014， 22（5）：1388-1394. （FENG J， CHEN Y， TONG X L， et al. Automatic feature point extraction for threedimensional skull[J]. Optics and Precision Engineering， 2014， 22（5）：1388-1394.）

[3]張琮毅，魏子莊，徐昊文，等. 尺度可變的快速全局點云配準方法[J]. 計算機學報， 2019， 42（9）：1939-1952. （ZHANG Z Y， WEI Z Z， XU H W， et al. Scale variable fast global point cloud registration[J]. Chinese Journal of Computers， 2019， 42（9） ：1939-1952.）

[4]藺素珍，王棟娟，鐘家讓，等. 利用曲率特征虛擬拼接青銅器小碎塊的方法[J]. 西安電子科技大學學報（自然科學版）， 2016， 43（6）： 141-146. （LIN S Z， WANG D J， ZHONG J R， et al. Approach to reassembling virtual small bronze fragments using the curvature feature[J]. Journal of Xidian University （Natural Science）， 2016， 43（6）： 141-146.）

[5]BESL P J， MCKAY N D. A method for registration of 3D shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1992， 14（2）：239-256.

[6]DU S， LIU J， ZHANG C. Probability iterative closest point algorithm for mD point set registration with noise[J]. Neurocomputing， 2015， 157：187-198.

[7]LI S， LEE D. Fast Visual odometry using intensityassisted iterative closest point[J]. IEEE Robotics and Automation Letters， 2016， 1（2）： 992-999.

[8]MARANI R， REN V， NITTI M， et al. A modified iterative closest point algorithm for 3D point cloud registration[J]. ComputerAided Civil and Infrastructure Engineering， 2016， 31（7）： 515-534.

[9]LAMINE TAZIR M， GOKHOOL T， CHECCHIN P， et al. CICP： Cluster iterative closest point for sparsedense point cloud registration[J]. Robotics and Autonomous Systems， 2018，108：66-86.

[10]邵紅旭. 低重疊率點云配準技術(shù)研究[D]. 哈爾濱： 哈爾濱工程大學， 2018：43-45. （SHAO H X. Research on point cloud registration technology with small overlap[D]. Harbin： Harbin Engineering University， 2018：43-45.）

[11]XU H， CHEN G， WANG Z， et al. RGBDbased pose estimation of workpieces with semantic segmentation and point cloud registration[J]. Sensors， 2019， 19（8）： No.1873.

[12]DING J， LIU Q， SUN P. A robust registration algorithm of point clouds based on adaptive distance function for surface inspection[J]. Measurement Science and Technology， 2019， 30（7）： No. 075003.

[13]WU M， WANG J. Registration of point cloud data for matching crushed sand particles[J]. Powder Technology， 2019， 347：227-242.

[14]LIU S， GAO D， WANG P， et al. A depthbased weighted point cloud registration for indoor scene[J]. Sensors， 2018， 18（11）：No.3608.

[15]王帥，孫華燕，郭惠超. 適用于激光點云配準的重疊區(qū)域提取方法[J]. 紅外與激光工程， 2017， 46（S1）： 137-142. （WANG S， SUN H Y， GUO H C. Overlapping region extraction method for laser point clouds registration[J]. Infrared and Laser Engineering， 2017， 46（S1）： 137-142.）

[16]巢淵，戴敏，陳愷，等. 基于廣義反向粒子群與引力搜索混合算法的多閾值圖像分割[J]. 光學精密工程， 2015， 23（3）：879-886. （CHAO Y， DAI M， CHEN K， et al. Image segmentation of multilevel threshold using hybrid PSOGSA with generalized oppositionbased learning[J]. Optics and Precision Engineering， 2015， 23（3）：879-886.）

[17]夏棒， EMILION R，王惠文. Dirichlet 混合樣本的 EM 算法與動態(tài)聚類算法比較[J]. 北京航空航天大學學報， 2019， 45（9）：1805-1811.（XIA B， EMILION R， WANG H W. A comparison between EM algorithm and dynamical clustering for Dirichlet mixture samples[J]. Journal of Beijing University of Aeronautics and Astronautics， 2019， 45（9）：1805-1811.）

[18]WU Z， LEAHY R. An optimal graph theoretic approach to data clustering： theory and its application to image segmentation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence， 1993， 15（11）：1101-1113.

[19]朱麗品，劉曉寧，劉雄樂，等. 加入迭代因子的層次化顱骨配準方法[J]. 中國圖象圖形學報， 2017， 22（4）： 523-531. （ZHU L P， LIU X N， LIU X L， et al. Hierarchical skull registration method with an iterative factor[J]. Journal of Image and Graphics， 2017， 22（4）： 523-531.）

[20]趙夫群，耿國華. 基于特征點的秦俑斷裂面匹配方法[J]. 激光與光電子學進展， 2018，55（4）： 122-128. （ZHAO F Q， GENG G H. Fracture surface matching method for Terracotta based on feature points[J]. Laser and Optoelectronics Progress， 2018，55（4）： 122-128.）

[21]李群輝，周明全，耿國華. 破碎剛體三角網(wǎng)格模型的斷裂面分割[J]. 計算機應(yīng)用， 2011， 31（8）：2204-2206， 2216. （LI Q H， ZHOU M Q， GENG G H. Fractured surface segmentation of triangular mesh of fragments for solid reconstruction[J]. Journal of Computer Applications， 2011， 31（8）： 2204-2206， 2216.）

This work is partially supported by the National Natural Science Foundation of China （61673319， 61731015）， the Major Special Project of Independent Innovation in Qingdao （2017-4-3-2xcl）， the Special Project of Scientific Research Program of Shaanxi Education Department （19JK0842）.

TANG Hui， born in 1982， Ph. D. candidate， experimentalist. Her research interests include graphics and image processing.

ZHOU Mingquan， born in 1954， M. S.， professor. His research interests include computer visualization， software engineering， Chinese information processing.

GENG Guohua， born in 1955， Ph. D.， professor. Her research interests include graphics and image processing，threedimensional reconstruction.