杜輝，鄭長亮，苗春雨，張小孟

（1. 北京電子科技職業(yè)學(xué)院電信工程學(xué)院，北京 100176；2. 杭州安恒信息技術(shù)股份有限公司，浙江 杭州 310051）

1 引言

隨著無人機(jī)、激光雷達(dá)等技術(shù)的不斷發(fā)展，建筑物、山地、醫(yī)學(xué)、無人駕駛等場(chǎng)景都需要對(duì)實(shí)體進(jìn)行三維重建[1-3]。三維重建研究中點(diǎn)的云配準(zhǔn)與拼接技術(shù)是重點(diǎn)研究內(nèi)容，隨著用戶對(duì)三維模型精度需求的提升，點(diǎn)云處理算法的可靠性要求也逐步提高。由于測(cè)量設(shè)備（如激光雷達(dá)）很難一次性完成對(duì)一個(gè)三維物體的點(diǎn)云數(shù)據(jù)采集，因此需要在多個(gè)角度分別采集三維物體的不同面，最后將不同角度采集的點(diǎn)云配準(zhǔn)、拼接，才能得到一個(gè)完整的三維模型。綜上所述點(diǎn)云的配準(zhǔn)與拼接準(zhǔn)確率將直接決定建模的精度。高精度的三維重建算法在未來5G、6G 等通信領(lǐng)域具有重要的作用，如采用三維重建算法可應(yīng)用于5G、6G 等研究中的建模問題[4-5]。

目前國內(nèi)外學(xué)者在三維重建領(lǐng)域已取得豐厚的成果，如Karg 等[6]通過捕獲車輛第一、二矩陣邊界并確定第一、第二矩形是否為同一輛車的邊界，最后根據(jù)第一、二矩形和側(cè)面方向完成對(duì)車輛的三維重建。陳佳舟等[7]針對(duì)圖像點(diǎn)云存在噪聲干擾問題，提出一種文物三維重建點(diǎn)云誤差點(diǎn)的自動(dòng)剔除方法，利用三維重投影方法計(jì)算三維點(diǎn)在圖像中的可見概率并剔除噪聲點(diǎn)，然后基于空間擴(kuò)散聚類方法去除圖像冗余點(diǎn)，完成對(duì)文物的三維重建。Rao 等[8]提出了一種基于莫爾斯理論中的3 種臨界點(diǎn)的快速且精確的點(diǎn)云仿射不變特征檢測(cè)和匹配方法，該方法定量評(píng)估重建模型的準(zhǔn)確性。實(shí)驗(yàn)結(jié)果表明構(gòu)建的三維模型精確率更高。Lan 等[9]針對(duì)前端數(shù)據(jù)關(guān)聯(lián)中幸存的異常特征匹配和閉環(huán)會(huì)導(dǎo)致大規(guī)模點(diǎn)云三維重建局部最優(yōu)問題，提出了一種在出現(xiàn)異常值時(shí)進(jìn)行穩(wěn)健的后端優(yōu)化概率方法。該方法利用Cauchy 分布抑制離群特征匹配，以及利用Cauchy-Uniform 混合模型抑制離群閉環(huán)約束，實(shí)驗(yàn)結(jié)果表明在公共點(diǎn)云數(shù)據(jù)集上具有更好的重建效果。徐斌等[10]提出了殘肢表面三維重建算法，利用深度相機(jī)掃描殘肢得到點(diǎn)云數(shù)據(jù)，并計(jì)算該點(diǎn)云的特征直方圖（FPFH），然后利用采樣一致性初始配準(zhǔn)（SAC-IA）和迭代最近點(diǎn)算法（ICP）完成殘肢點(diǎn)云的粗配準(zhǔn)和精配準(zhǔn)，實(shí)現(xiàn)殘肢表面的三維重建。張一等[11]針對(duì)傳統(tǒng)SLAM 算法僅能重建稀疏點(diǎn)云等不足，提出一種特征法視覺SLAM 逆深度濾波的三維重建方法，利用視頻序列影像實(shí)時(shí)、增量式地構(gòu)建相對(duì)稠密的場(chǎng)景結(jié)構(gòu)。丁忠軍等[12]提出一種載人潛水器的深海地貌線結(jié)構(gòu)光三維重建方法，通過改進(jìn)Steger 算法，利用直接標(biāo)定法求得水下地形二維空間坐標(biāo)，再將獲得的二維點(diǎn)云與多元傳感器的數(shù)據(jù)進(jìn)行融合，并以姿態(tài)傳感器的數(shù)據(jù)矯正點(diǎn)云數(shù)據(jù), 最終獲得地貌的三維點(diǎn)云數(shù)據(jù)，最后對(duì)三維點(diǎn)云數(shù)據(jù)進(jìn)行配準(zhǔn)。

上述方法當(dāng)點(diǎn)云間重疊比例較大或點(diǎn)云間規(guī)模大小接近時(shí)能夠取得較好的三維重建效果，然而三維實(shí)體（如房子、街道等）的點(diǎn)云數(shù)據(jù)很難一次性采集，如果在點(diǎn)云數(shù)據(jù)采集過程中，激光雷達(dá)（點(diǎn)云采集設(shè)備）更換了位置或者角度進(jìn)行連續(xù)采集時(shí)，得到的點(diǎn)云數(shù)據(jù)可能存在角度或大小上的變化，尤其是點(diǎn)云間重疊率比較低時(shí)，后續(xù)就很難進(jìn)行點(diǎn)云的配準(zhǔn)與拼接，從而嚴(yán)重影響建模精度。本文利用歐氏距離分割法和動(dòng)態(tài)時(shí)間規(guī)整算法（DTW），能有效解決點(diǎn)云重疊率低和點(diǎn)云規(guī)模不一致的配準(zhǔn)問題。

2 相關(guān)概述

點(diǎn)云是通過測(cè)量儀器（如激光掃描儀等）得到的實(shí)物外觀表面的點(diǎn)數(shù)據(jù)集合，由一系列二維或三維的點(diǎn)組成，能夠真實(shí)地反映物體表面信息。悉尼城市目標(biāo)數(shù)據(jù)集[13]中的一個(gè)卡車點(diǎn)云如圖1所示。

圖1 點(diǎn)云示意圖

要獲得一輛卡車完整的點(diǎn)云，需要在卡車周圍選擇若干個(gè)位置進(jìn)行數(shù)據(jù)采集，然后將采集的點(diǎn)云幀進(jìn)行組合拼接。由于相鄰位置采集的兩幀點(diǎn)云存在部分重疊，如果找到這些重疊的點(diǎn)，然后對(duì)這兩幀點(diǎn)云進(jìn)行平移、旋轉(zhuǎn)操作，即可完成兩幀點(diǎn)云的拼接。點(diǎn)云拼接如圖2 所示，圖2 中使用兩個(gè)激光雷達(dá)掃描長方體，激光雷達(dá)1 可以掃描到的范圍為矩形RTaeh2，激光雷達(dá)2 可以掃描到的范圍為矩形RTbfgc，而矩形RTbehc可以同時(shí)被兩個(gè)激光雷達(dá)掃描，因此兩個(gè)激光雷達(dá)掃描的點(diǎn)云能夠覆蓋長方體的正前方和右側(cè)面，如果將兩個(gè)雷達(dá)掃描得到的點(diǎn)云進(jìn)行配準(zhǔn)和拼接，即可完成對(duì)長方體正前方和右側(cè)面的重建。而重建過程中最重要的就是找到這兩幀點(diǎn)云的重疊部分，即圖2 中RTbehc位置的點(diǎn)云，且重疊區(qū)域RTbehc的大小會(huì)影響點(diǎn)云拼接的效果。

圖2 點(diǎn)云拼接

3 點(diǎn)云處理

本節(jié)主要介紹如何完成兩幀點(diǎn)云重疊區(qū)域的映射問題。首先介紹了基于歐氏距離的點(diǎn)云分割方法；然后提取子點(diǎn)云的特征值，最后考慮不同位置獲取的點(diǎn)云規(guī)模不一致，采用DTW 算法完成子點(diǎn)云的映射。為降低點(diǎn)云映射的計(jì)算復(fù)雜度，將不同激光雷達(dá)采集的點(diǎn)云映射到二維平面上，點(diǎn)云二維平面映射過程如圖3 所示，以兩個(gè)激光雷達(dá)的水平中垂線為基準(zhǔn)，距離h處構(gòu)建二維投影平面XOY。將兩個(gè)激光雷達(dá)掃描得到的點(diǎn)云同時(shí)映射到二維平面上，以映射后的二維點(diǎn)云為拼接的基礎(chǔ)，完成重疊點(diǎn)云“關(guān)鍵位置”的所搜和匹配。

圖3 點(diǎn)云二維平面映射

3.1 點(diǎn)云分割

如果不對(duì)大面積的點(diǎn)云進(jìn)行分割，則無法有針對(duì)性地尋找到兩幀點(diǎn)云的重疊區(qū)域。為有效地對(duì)點(diǎn)云進(jìn)行劃分，采用基于歐氏距離的點(diǎn)云分割算法，該方法逐步掃描點(diǎn)云內(nèi)的點(diǎn)，如果當(dāng)前掃描點(diǎn)與聚類種子點(diǎn)之間的距離d小于設(shè)定的閾值D，則將當(dāng)前掃描點(diǎn)聚類到該種子點(diǎn)所屬的類中；否則將當(dāng)前掃描點(diǎn)設(shè)置為新的聚類種子，根據(jù)預(yù)設(shè)閾值D判斷下一個(gè)掃描點(diǎn)是否與新的種子點(diǎn)屬于同一類。重復(fù)以上步驟，直到所有的點(diǎn)都被聚到不同的類中。通過聚類，可以減少物體邊界點(diǎn)對(duì)特征點(diǎn)檢測(cè)的影響，同時(shí)，對(duì)于點(diǎn)云中不規(guī)則的離散點(diǎn)，往往其所在類的尺寸較小，很容易將其濾掉。點(diǎn)云分割流程方法見算法1，每個(gè)隊(duì)列表示分割得到的一個(gè)子點(diǎn)云，最終求取子點(diǎn)云的平均規(guī)模（即子點(diǎn)云內(nèi)平均包含點(diǎn)的數(shù)量），并將子點(diǎn)云規(guī)模小于平均規(guī)模的子點(diǎn)云濾除。

算法1基于歐氏距離的點(diǎn)云分割算法

輸入待分割的點(diǎn)云O

輸出分割后的子點(diǎn)云Qm

（1）設(shè)置多個(gè)隊(duì)列Qm(m表示隊(duì)列數(shù)量)，預(yù)設(shè)歐氏距離閾值D；

（2）i=1；

（3）隨機(jī)搜索點(diǎn)云O中某個(gè)點(diǎn)pi作為聚類種子點(diǎn)，即C=pi；

（7）i=i+1；

（8）判斷點(diǎn)云中的點(diǎn)是否都加入相關(guān)隊(duì)列，如果是，結(jié)束算法，如果否，則返回步驟4。

3.2 子點(diǎn)云特征提取

由于激光雷達(dá)掃描物體時(shí)，物體不同表面產(chǎn)生的點(diǎn)的數(shù)量、密度和組合都是不同的，每個(gè)位置產(chǎn)生的點(diǎn)云總體上是有區(qū)別的，由于不同點(diǎn)云中點(diǎn)分布存在差異，本文假設(shè)滿足二維正態(tài)分布，且概率密度函數(shù)能夠很好地描述點(diǎn)云中點(diǎn)分布的密度、位置等差異，因此采用二維正態(tài)分布的概率密度值作為點(diǎn)云的特征，該特征值較傳統(tǒng)的均值、方差等指標(biāo)具有更強(qiáng)的描述性。為后續(xù)進(jìn)行點(diǎn)云的配準(zhǔn)和拼接，需找到具有部分重疊的兩幀點(diǎn)云高度重合的位置（關(guān)鍵位置），反映在物體上，即不同位置的激光雷達(dá)掃描物體相同區(qū)域得到的點(diǎn)云。根據(jù)第2.1 節(jié)的點(diǎn)云分割方法，將兩幀具有重疊的點(diǎn)云進(jìn)行分割，然后將兩幀點(diǎn)云分割后的子點(diǎn)云進(jìn)行特征匹配，尋找到兩幀點(diǎn)云的“關(guān)鍵位置”。本節(jié)介紹一種子點(diǎn)云的特征提取方法，特征提取原理如圖4 所示，首先求取該子點(diǎn)云的重心重心坐標(biāo)如式（1）所示。然后以子點(diǎn)云的重心為中心構(gòu)建等距離g（unit）同心圓，直到最大的一個(gè)同心圓將該點(diǎn)云中所有的點(diǎn)全部囊括在內(nèi)，其中，1（unit）表示20 個(gè)像素。

其中，xi、yi分別表示點(diǎn)的橫縱坐標(biāo)，N表示子點(diǎn)云中點(diǎn)的數(shù)量。

圖4 特征提取原理

假設(shè)子點(diǎn)云內(nèi)部的點(diǎn)服從二維正態(tài)分布，即將每個(gè)點(diǎn)的坐標(biāo)(xi,yi)看作二維隨機(jī)變量，那么子點(diǎn)云的概率密度函數(shù)如式（2）所示。

其中，μ1、μ2為x和y的均值，見式（1），σ1和σ2為x和y的方差，ρ為x和y的相關(guān)系數(shù)，絕對(duì)值小于1。

為了提高子點(diǎn)云的匹配準(zhǔn)確性，使用二維正態(tài)分布模型的概率密度均值來表示子點(diǎn)云的特征。根據(jù)概率密度函數(shù)f(x,y)可求得點(diǎn)云中每個(gè)點(diǎn)的概率密度，求取目標(biāo)范圍內(nèi)所有點(diǎn)的概率密度值之后計(jì)算該目標(biāo)范圍內(nèi)點(diǎn)云的平均概率密度值，如式（3）所示，以平均概率密度值作為子點(diǎn)云的一個(gè)特征。

其中，G(x,y)表示點(diǎn)(x,y)位置的概率密度值，n表示目標(biāo)范圍內(nèi)點(diǎn)的數(shù)量。

其中，k表示點(diǎn)云劃分時(shí)同心圓區(qū)域的數(shù)量。

3.3 子點(diǎn)云映射

根據(jù)第2.1 和2.2 節(jié)的方法可以將激光雷達(dá)掃描得到的原始點(diǎn)云分割為若干子點(diǎn)云，然后求得子點(diǎn)云的特征序列。在進(jìn)行兩幀原始點(diǎn)云匹配時(shí)，主要是根據(jù)特征序列實(shí)現(xiàn)兩幀原始點(diǎn)云中某些相似度較高的子點(diǎn)云映射。

激光掃描可類比拍照，當(dāng)照相機(jī)位于不同位置拍攝同一個(gè)物體時(shí)，照片的大小也是有區(qū)別的。相同原理，激光雷達(dá)位于不同位置掃描同一個(gè)物體時(shí)，其得到物體表面的點(diǎn)云也存在大小的區(qū)分，本文稱為點(diǎn)云規(guī)模的大小不同。如果待拼接的兩幀點(diǎn)云存在規(guī)模上的差別，則得到的子點(diǎn)云特征序列長度也是不同的，不同規(guī)模子點(diǎn)云劃分如圖5所示，子點(diǎn)云p與子點(diǎn)云q形狀非常接近，點(diǎn)的分布也非常接近，但因?yàn)榧す饫走_(dá)所處的位置不同，導(dǎo)致點(diǎn)云規(guī)模存在差別，理論上這兩塊子點(diǎn)云是激光雷達(dá)位于不同位置掃描三維物體同一區(qū)域得到的數(shù)據(jù)。由于點(diǎn)云規(guī)模不同，而點(diǎn)云劃分的同心圓之間的距離相同且都為g，最終得到的子點(diǎn)云特征序列長度也存在差別，如子點(diǎn)云p的特征序列Fk長度為3，而子點(diǎn)云q的特征序列長度為5。針對(duì)這種情況，傳統(tǒng)的點(diǎn)云配準(zhǔn)方法很難解決該問題。

圖5 不同規(guī)模子點(diǎn)云劃分

為解決點(diǎn)云規(guī)模不一致的拼接問題，提出一種基于動(dòng)態(tài)時(shí)間規(guī)劃（DTW）的點(diǎn)云特征序列匹配方法[14-15]。DTW 通過將特征序列進(jìn)行延伸和縮短，計(jì)算兩個(gè)特征序列性之間的相似性。假設(shè)子點(diǎn)云p和子點(diǎn)云q的特征序列分別如式（5）、式（6）所示。

其中，m表示子點(diǎn)云p的特征序列長度，n表示子點(diǎn)云q的特征序列長度。

當(dāng)m＝n時(shí)，則可以采用特征序列之間的歐氏距離衡量兩幀子點(diǎn)云特征序列的相似性，而當(dāng)m≠n時(shí)，需要將其中一個(gè)特征序列進(jìn)行線性縮/放對(duì)齊，使得兩組特征序列的長度相同，才可以進(jìn)行相似性衡量。但線性縮放沒有考慮特征序列各個(gè)階段在不同情況下的長度變化，識(shí)別效果不可能最佳，更多地采用動(dòng)態(tài)規(guī)劃（2ynamic programming）的方法。DTW 序列對(duì)齊原理如圖6所示，利用兩組特征序列構(gòu)建一個(gè)網(wǎng)格矩陣，矩陣中每個(gè)元素di,j表示特征序列qnF的第i個(gè)元素與特征序列第j個(gè)元素之間的歐氏距離，每一個(gè)矩陣元素對(duì)應(yīng)的下標(biāo)(i,j)就表示兩組特征序列的對(duì)齊點(diǎn)。

圖6 DTW 序列對(duì)齊原理

從初始點(diǎn)d1,1到結(jié)束點(diǎn)d5,3有較多條路徑，且路徑的數(shù)量隨著矩陣規(guī)模呈指數(shù)增長，如何找到一條路徑使得代價(jià)最小，最小代價(jià)的一條路徑即為兩組特征序列的最佳對(duì)齊點(diǎn)，最小代價(jià)函數(shù)如式（7）所示。

基于上述方法對(duì)兩組特征序列進(jìn)行對(duì)齊，特征序列上的點(diǎn)能夠找到最佳對(duì)齊點(diǎn)，DTW 序列對(duì)齊原理如圖7 所示。根據(jù)對(duì)齊后的兩組特征序列之間的歐氏距離作為相似度，如式（8）所示。

圖7 DTW 序列匹配

利用原始點(diǎn)云的分割、特征提取和子點(diǎn)云映射方法即可尋找到兩塊原始點(diǎn)云中相似性較高的位置，以這些位置為基準(zhǔn)進(jìn)行點(diǎn)云的配準(zhǔn)將能夠有效地解決兩幀點(diǎn)云重疊率低以及點(diǎn)云規(guī)模不統(tǒng)一問題。本文利用上述點(diǎn)云映射方法所搜到兩幀原始點(diǎn)云中相似性最高的子點(diǎn)云完成映射。

4 點(diǎn)云配準(zhǔn)

對(duì)兩幀點(diǎn)云P和Q進(jìn)行分割，并獲得了互相映射的子點(diǎn)云p和q，然后基于子點(diǎn)云p、q采用ICP 算法進(jìn)行配準(zhǔn)，由于ICP 算法對(duì)點(diǎn)云的初始位置有較高的要求，這里需要采用SAC-IA[16-17]算法先對(duì)點(diǎn)云粗配準(zhǔn)，因此要配準(zhǔn)的兩幀點(diǎn)云具有較好的初始位置，再利用ICP[18-19]算法進(jìn)行精配準(zhǔn)，如式（9）所示。

其中，R、t分別表示旋轉(zhuǎn)和平移矩陣，由SAC-IA算法和ICP 算法得到，e為優(yōu)化誤差。求得的R和t再對(duì)P和Q進(jìn)行配準(zhǔn)，即可完成拼接。由于SAC-IA 算法和ICP 算法已經(jīng)非常成熟，本文不再做過多的介紹。點(diǎn)云配準(zhǔn)算法見算法2。

算法2原始點(diǎn)云配準(zhǔn)算法

輸入點(diǎn)云P和Q。

輸出旋轉(zhuǎn)矩陣R，平移矩陣t。

（1）對(duì)點(diǎn)云P和Q分割，得到子集pi和qi；

（2）對(duì)子集分別求取二維正態(tài)分布的概率密度均值；

（3）基于DTW 算法完成子點(diǎn)云的映射；

（4）配準(zhǔn)匹配的子集并獲得旋轉(zhuǎn)矩陣R，平移矩陣t，作用于P和Q；

（5）完成原始點(diǎn)云P和Q的配準(zhǔn)與拼接。

算法2 介紹了點(diǎn)云配準(zhǔn)算法的總體流程，該算法基于SAC-IA 算法和ICP 算法實(shí)現(xiàn)點(diǎn)云的粗配準(zhǔn)和精配準(zhǔn)。SAC-IA 算法與ICP 算法的總體實(shí)踐復(fù)雜度為O(sk2)，其中，s表示點(diǎn)云中點(diǎn)的數(shù)量，k表示點(diǎn)云被均分的份數(shù)，該值與變量g相關(guān)。而DTW 算法的實(shí)踐復(fù)雜度為O(mn)，其中，n和m分別表示兩幀點(diǎn)云特征向量的模。綜上所述，本文算法的總體復(fù)雜度為O(sk2)+O(mn)。

5 實(shí)驗(yàn)分析

5.1 點(diǎn)云重疊率對(duì)配準(zhǔn)影響

傳統(tǒng)的ICP 算法主要解決大規(guī)模重疊點(diǎn)云的配準(zhǔn)與拼接問題，而當(dāng)點(diǎn)云規(guī)模較小時(shí)，很難取得好的拼接效果。本文主要研究當(dāng)兩幀點(diǎn)云具有較低重疊率和點(diǎn)云規(guī)模不同時(shí)的配準(zhǔn)拼接問題。實(shí)驗(yàn)采用ASL Datasets 中的“?！秉c(diǎn)云作為實(shí)驗(yàn)對(duì)象，將該點(diǎn)云按一定比例重疊區(qū)域進(jìn)行分割，然后驗(yàn)證本文提出的方法在不同重疊率情況下的配準(zhǔn)與拼接效果，實(shí)驗(yàn)中點(diǎn)云的歐氏距離分割閾值D=15，點(diǎn)云劃分同心圓之間的間隔g=3。分割示意圖如圖8 所示。

圖8 分割示意圖

首先固定一個(gè)旋轉(zhuǎn)矩陣Ri和平移矩陣ti，分別如式（10）、式（11）所示，將這兩個(gè)矩陣作用于圖8 中分割后的“?！毕虏糠值狞c(diǎn)云，使得兩幀點(diǎn)云在位置上錯(cuò)開。兩幀點(diǎn)云位置錯(cuò)開后，利用本文提出的點(diǎn)云配準(zhǔn)方法（partial overlapping point clou2 registration metho2 base2 on 2ynamic feature matching，PPCR）和ICP 算法分別對(duì)兩幀點(diǎn)云進(jìn)行配準(zhǔn)，求取PPCR 和ICP 算法生成的旋轉(zhuǎn)矩陣Rj和平移矩陣tj，再與固定的旋轉(zhuǎn)矩陣Ri和平移矩陣ti進(jìn)行對(duì)比，計(jì)算旋轉(zhuǎn)誤差和平移誤差，分別如式（12）和式（13）所示。

PPCR 算法的實(shí)驗(yàn)結(jié)果如圖9 所示，表明隨著點(diǎn)云之間重疊率的降低，兩幀點(diǎn)云的拼接時(shí)的旋轉(zhuǎn)誤差ER和平移誤差Et都呈指數(shù)升高，因?yàn)橹丿B率越小，所以拼接算法能找到兩幀點(diǎn)云相似的區(qū)域的可靠性越差，導(dǎo)致拼接誤差較大。

圖9 點(diǎn)云重疊率對(duì)PPCR 拼接效果影響

PPCR 算法與ICP 算法的對(duì)比結(jié)果如圖10 所示，ICP 在點(diǎn)云重疊率高于20%時(shí)有效，否則無法完成點(diǎn)云的拼接，且ICP 算法的拼接誤差大于本文提出的PPCR 算法，因?yàn)镮CP 算法并未考慮點(diǎn)云重疊率時(shí)的拼接問題，其主要針對(duì)大面積重疊的點(diǎn)云之間的拼接，而PPCR 算法利用歐氏距離分割，提取了重疊部分點(diǎn)云的特征，且采用了DTW 曲線相似度動(dòng)態(tài)匹配算法，即使在重疊率較低時(shí)也能夠準(zhǔn)確地找到點(diǎn)云間的重疊區(qū)域，最后根據(jù)重疊區(qū)域進(jìn)行拼接，因此拼接誤差較ICP 算法更低。

圖10 PPCR 與ICP 拼接誤差對(duì)比

單獨(dú)采用ICP 算法進(jìn)行點(diǎn)云配準(zhǔn)存在收斂速度慢、配準(zhǔn)誤差大等問題。本文先采用SAC-IA算法實(shí)現(xiàn)點(diǎn)云的粗匹配，將位置錯(cuò)開的點(diǎn)云快速實(shí)現(xiàn)合攏，然后采用ICP 算法進(jìn)行精匹配，理論上能夠降低點(diǎn)云配準(zhǔn)的時(shí)間。本實(shí)驗(yàn)驗(yàn)證當(dāng)點(diǎn)云不同重疊率下，ICP 算法和PPCR 算法的配準(zhǔn)時(shí)間，結(jié)果見表1。

表1 時(shí)間復(fù)雜度分析（時(shí)間/s）

實(shí)驗(yàn)結(jié)果表明，PPCR 算法在所有重疊率下的配準(zhǔn)時(shí)間都低于ICP 算法，因?yàn)镻PCR 算法先采用SAC-IA 算法快速將兩幀位置偏差較大的點(diǎn)云快速的匹配并合攏，然后采用ICP 算法進(jìn)行精匹配，其中，SAC-IA 算法的效率較高。而ICP 算法在處理兩幀點(diǎn)云偏差較大情況時(shí)，收斂速度非常慢，因此導(dǎo)致配準(zhǔn)過程所需時(shí)間較長。

5.2 噪音對(duì)點(diǎn)云配準(zhǔn)影響

激光雷達(dá)發(fā)出的微波在真實(shí)環(huán)境中容易產(chǎn)生衍射、折射等現(xiàn)象，會(huì)導(dǎo)致采集的點(diǎn)云數(shù)據(jù)包含噪音，由于噪音的隨機(jī)性會(huì)影響點(diǎn)云配準(zhǔn)過程中的子點(diǎn)云映射，因此消除噪音有利于提高點(diǎn)云配準(zhǔn)的準(zhǔn)確率。噪音在點(diǎn)云中一般是以少量離散點(diǎn)的形式存在，而本文提出的PPCR 算法在點(diǎn)云分割階段將點(diǎn)云進(jìn)行聚類，因此可以根據(jù)聚類中包含點(diǎn)的數(shù)量來濾除噪音，當(dāng)類規(guī)模小于一定值時(shí)刪除該類，濾噪對(duì)比如圖11 所示，當(dāng)基于歐氏距離的點(diǎn)云分割得到的子點(diǎn)云所包含的點(diǎn)數(shù)量小于子點(diǎn)云平均包含的點(diǎn)數(shù)量的一半時(shí)，則刪除該子點(diǎn)云，實(shí)驗(yàn)中點(diǎn)云的歐氏距離分割閾值D=15。利用第4.1 節(jié)的方法將點(diǎn)云分為兩部分，重疊率為20%，驗(yàn)證不同程度的濾波情況下PPCR 算法拼接點(diǎn)云的誤差，實(shí)驗(yàn)結(jié)果見表2，表2 中拼接效果一欄表示兩幀點(diǎn)云拼接是否有效，為1 表示有效，為0 表示無效。S 為原始點(diǎn)云經(jīng)歐氏距離分割后得到若干子點(diǎn)云后，子點(diǎn)云平均包含點(diǎn)的數(shù)量，如式（14）所示。

圖11 濾噪對(duì)比

其中，n表示子點(diǎn)云的總數(shù)量，si表示點(diǎn)云i中包含點(diǎn)的數(shù)量。

表2 濾波對(duì)點(diǎn)云拼接的影響

實(shí)驗(yàn)中將小于濾波閾值的子點(diǎn)云刪除，結(jié)果見表2，隨著濾波閾值的增加，PPCR 算法的點(diǎn)云拼接誤差逐漸減小，總體誤差ER+t一直維持在0.5以下，因?yàn)闉V波閾值越大，能夠?yàn)V除的噪聲越多，所以待拼接的兩幀子點(diǎn)云之間的映射更準(zhǔn)確。

5.3 點(diǎn)云規(guī)模差異對(duì)子點(diǎn)云映射影響

PPCR 點(diǎn)云配準(zhǔn)與拼接算法采用動(dòng)態(tài)時(shí)間規(guī)則方法進(jìn)行點(diǎn)云特征序列匹配，理論上能夠有效解決待拼接的兩幀點(diǎn)云規(guī)模不一致的映射問題。如果能夠準(zhǔn)確地映射兩幀原始點(diǎn)云中相似性極高的子點(diǎn)云，則后續(xù)可以根據(jù)該子點(diǎn)云進(jìn)行原始點(diǎn)云的拼接。以“兔子”點(diǎn)云為實(shí)驗(yàn)對(duì)象，不同規(guī)模點(diǎn)云如圖12所示，為構(gòu)建不同規(guī)模點(diǎn)云，對(duì)原始點(diǎn)云進(jìn)行下采樣，使得下采樣后得到的點(diǎn)云與原始點(diǎn)云保持相同的結(jié)構(gòu)，但點(diǎn)的數(shù)量不同，然后將下采樣后的點(diǎn)云縮小到原始點(diǎn)云的1/2，實(shí)驗(yàn)中下采樣矩陣見表3。初始時(shí)刻兩幀點(diǎn)云處于相互完全重疊位置，然后利用已知的旋轉(zhuǎn)矩陣和平移矩陣作用于其中一個(gè)點(diǎn)云，使得兩幀點(diǎn)云位置錯(cuò)開（見第4.1 節(jié)的旋轉(zhuǎn)與平移），以第4.1 節(jié)的配準(zhǔn)誤差方法衡量兩幀點(diǎn)云的配準(zhǔn)精度，實(shí)驗(yàn)結(jié)果見表3，表3 中配準(zhǔn)效果一欄表示兩幀點(diǎn)云配準(zhǔn)是否有效，為1 表示有效，為0表示無效。實(shí)驗(yàn)中的下采樣方法為僅采集采樣矩陣中心位置的元素替代原采樣矩陣中所有值。

實(shí)驗(yàn)結(jié)果表明隨著下采樣矩陣的增加，配準(zhǔn)誤差會(huì)升高，下采樣矩陣為3×3 時(shí)，配準(zhǔn)誤差較小，僅為0.324，而下采樣矩陣為9×9 時(shí)，點(diǎn)云拼接誤差較大為0.979。因?yàn)橄虏蓸泳仃囋酱?，下采樣后得到的點(diǎn)云越稀疏，損失的特征越多，所以配準(zhǔn)誤差也就越高。但利用激光雷達(dá)處于不同位置掃描同一個(gè)三維實(shí)體時(shí)，其得到的點(diǎn)云之間的差距不可能達(dá)到3×3 下采樣這種損失，且實(shí)驗(yàn)誤差表明即使對(duì)原始點(diǎn)云進(jìn)行下采樣操作，在丟失大部分?jǐn)?shù)據(jù)時(shí)，兩幀點(diǎn)云的配準(zhǔn)仍具有較高的穩(wěn)健性，因此本文提出的利用DTW 算法進(jìn)行子點(diǎn)云特征序列的匹配方法能夠有效地應(yīng)對(duì)點(diǎn)云規(guī)模不同而導(dǎo)致拼接效果差的問題。

圖12 不同規(guī)模點(diǎn)云

表3 不同規(guī)模點(diǎn)云配準(zhǔn)誤差

5.4 分割距離g 與收斂性分析

在第2.2 節(jié)子點(diǎn)云特征提取階段提出采用變量g將點(diǎn)云進(jìn)行均勻分割。當(dāng)g的取值不同時(shí)，會(huì)得到長度不同的特征向量，這會(huì)影響點(diǎn)云的拼接效果。為驗(yàn)證g在不同取值時(shí)的點(diǎn)云拼接誤差，實(shí)驗(yàn)設(shè)定g的取值為2～10，其中兩幀點(diǎn)云的重疊率為20%，實(shí)驗(yàn)結(jié)果見表4。

實(shí)驗(yàn)結(jié)果表明隨著g的增加，點(diǎn)云拼接的總體誤差ER+t首先呈降低趨勢(shì)，因?yàn)間增加，提取同一幀點(diǎn)云的特征增加，從而降低了總體誤差。當(dāng)g大于5 時(shí)，總體誤差基本呈平穩(wěn)波動(dòng)趨勢(shì)，因?yàn)榇藭r(shí)點(diǎn)云被劃分的足夠精細(xì)，特征提取的比較全面。但g的取值并非越大越好，同時(shí)還要考慮算法的復(fù)雜度。

表4 變量g 對(duì)點(diǎn)云拼接的影響

6 結(jié)束語

針對(duì)目前點(diǎn)云配準(zhǔn)與拼接方法較難解決部分重疊、規(guī)模不一致的點(diǎn)云配準(zhǔn)與拼接問題，提出一種動(dòng)態(tài)特征匹配的部分重疊點(diǎn)云配準(zhǔn)方法，利用點(diǎn)之間的歐氏距離進(jìn)行子點(diǎn)云的分割，然后以二維正態(tài)分布模型提取子點(diǎn)云的特征序列并利用DTW 算法完成特征序列的相似性匹配，接著將相似度最高的子點(diǎn)云進(jìn)行映射，最后利用SAC-IA算法和ICP 算法完成點(diǎn)云的配準(zhǔn)與拼接。實(shí)驗(yàn)結(jié)果表明該方法在點(diǎn)云低重疊率和點(diǎn)云規(guī)模不一致情況下均能以較小的誤差完成配準(zhǔn)和拼接。