摘? 要：迭代最近點（ICP）配準(zhǔn)算法需要兩點云處于良好的初始位置，否則在配準(zhǔn)時容易陷入局部最優(yōu)。針對該問題，提出了一種基于內(nèi)部形狀描述子（ISS）特征點與改進描述子的粗配準(zhǔn)方法，使得低重疊度或無公共重疊部分的點云獲取良好的初始位置。首先，利用ISS特征點提取點云的特征點;其次，基于特征點與其鄰域點法向量夾角提出改進的描述子，根據(jù)描述子的歐氏距離將點云特征進行匹配;第三，通過單次最優(yōu)變換進行粗配準(zhǔn);最后，對兩點云進行精配準(zhǔn)ICP迭代。實驗表明，在點云模型完整的情況下，本文方法可為精配準(zhǔn)提供良好的初始位置，且粗配準(zhǔn)精度比傳統(tǒng)點云配準(zhǔn)精度高三個量級，配準(zhǔn)效率提升23.7%。

關(guān)鍵詞：點云粗配準(zhǔn);ISS特征點;改進描述子;ICP算法

中圖分類號：TP391.1? ? ?文獻標(biāo)識碼：A

文章編號：2096-1472（2022）-01-01-05

Abstract： Iterative closest point registration algorithm （ICP） requires two point clouds to be in a good initial position， otherwise it is easy to fall into a local optimum during registration. In view of this problem， this paper proposes a coarse registration method based on Intrinsic Shape Signatures （ISS） feature points and improved descriptors， which makes point clouds with low overlap or without common overlap obtain a good initial position. Firstly， ISS feature points are used to extract the feature points of the point cloud. Secondly， an improved descriptor is proposed based on the angle between the feature points and the normal vector of the neighboring points， and the point cloud features are matched according to the Euclidean distance of the descriptor. Then， rough registration is carried out by single optimal transformation. Finally， precision registration ICP iteration is conducted for the two-point clouds. Experimental results show that the proposed method provide a good initial position for fine registration under the condition of complete point cloud model; the coarse registration accuracy is three orders of magnitude higher than that of traditional point cloud registration， and the registration efficiency is improved by 23.7%.

Keywords： point cloud coarse registration; ISS feature points; improved descriptor; ICP algorithm

1? ?引言（Introduction）

隨著三維傳感器設(shè)備的發(fā)展，點云配準(zhǔn)廣泛應(yīng)用于三維重建、三維定位與姿態(tài)估計等方面。點云配準(zhǔn)的目標(biāo)在于獲取待配準(zhǔn)兩點云的位姿變換關(guān)系，將不同角度下采集得到的點云變換到同一坐標(biāo)系下。傳統(tǒng)的點云配準(zhǔn)算法是由BESL等[1]提出的迭代最近點（ICP）算法，該算法需要兩點云具有良好的初始位置，即點云重疊度高，點云數(shù)據(jù)量相近。

針對該問題，許多學(xué)者對ICP算法進行了改進和創(chuàng)新，并提出了新的配準(zhǔn)算法以解決位姿差異較大的點云匹配問題。鐘瑩等[2]使用主成分分析法（Principal Component Analysis， PCA）對點云進行粗配準(zhǔn)以獲取良好的初始位姿，避免ICP陷入局部最優(yōu)。宋成航等[3]基于從法向量角度對特征點對的約束并結(jié)合快速點特征直方圖（FPFH）[4]，提出了利用采樣一致性改進ICP的配準(zhǔn)算法。正態(tài)分布配準(zhǔn)（Normal Distribution Transformation， NDT）算法[5]利用點云的正態(tài)分布，通過最優(yōu)化方法求出使概率密度之和最大的變換參數(shù)。結(jié)合NDT算法，荊路等[6]提出了基于SAC和NDT融合的配準(zhǔn)算法;王慶閃等[7]提出了基于NDT與ICP結(jié)合的配準(zhǔn)算法。但是，上述算法運行時間較長或?qū)?shù)的調(diào)節(jié)較多，需要重復(fù)地實驗來確定理想的參數(shù)。

綜上，本文提出一種基于內(nèi)部形狀描述子（ISS）[8]特征點檢測與改進描述子匹配的點云配準(zhǔn)算法。首先對下采樣后的兩點云提取ISS特征點;然后結(jié)合改進的描述子計算特征向量并匹配對應(yīng)點對，對點云進行粗配準(zhǔn);最后，利用ICP算法進行精配準(zhǔn)。本文實驗驗證了改進描述子的特征點對的匹配率為91.67%，同時與文獻中的點云配準(zhǔn)算法進行了對比試驗。

2? ?算法介紹（Algorithm introduction）

針對傳統(tǒng)ICP算法存在收斂速度慢，容易陷入局部最優(yōu)且需要良好的初始位姿及較高的重疊度等問題，本文提出一種基于ISS特征點與改進描述子的點云配準(zhǔn)方法，算法流程圖如圖1所示。首先，對兩點云進行下采樣以減小點云復(fù)雜度。其次，對點云進行ISS特征點檢測并計算點云法向量，接著對特征點應(yīng)用改進的描述子計算特征值向量，為提高特征點對的匹配準(zhǔn)確度，設(shè)置并基于歐氏距離對特征向量進行匹配。第三，在匹配的對應(yīng)特征點的基礎(chǔ)上運用單次最優(yōu)化變換求解粗配準(zhǔn)變換矩陣。最后，采用K維樹近鄰搜索算法加速對應(yīng)點的查找，對兩點云應(yīng)用ICP迭代算法，完成點云精配準(zhǔn)。

3? ?點云粗配準(zhǔn)（Coarse registration of point clouds）

3.1? ?ISS特征點提取

在傳統(tǒng)點云配準(zhǔn)ICP中，需要得到待匹配兩點云的對應(yīng)點對。由于點云數(shù)量較大，一般提取點云中幾何特征明顯的點來代表整體點云。常見的點云特征點檢測算法有3D-Harris[9]關(guān)鍵點算法、3D-SIFT[10]算法、內(nèi)部描述子（ISS）算法等。本文實驗驗證，ISS特征點檢測算法與改進描述子對點云粗配準(zhǔn)效果較好。內(nèi)部描述子（ISS）是一種表示立體幾何形狀的方法，該算法具有豐富的幾何信息，可以完成高質(zhì)量的點云配準(zhǔn)。ISS特征點算法檢測原理如下。

設(shè)點云中含有n 個點，，ISS關(guān)鍵點算法具體流程如下：

Step 1：對點云中的每個點建立一個局部坐標(biāo)系，如圖2所示，并對每個點設(shè)定一個搜索半徑r。

Step 2：利用KD樹確定點云中每個以為中心、r為半徑區(qū)域內(nèi)的所有點，并計算這些點的權(quán)值，權(quán)值表達式為：

Step 3：計算每個點的協(xié)方差矩陣：

Step 4：計算每個點的協(xié)方差矩陣的特征值，將特征值按從大到小的順序排列。

Step 5：設(shè)置閾值與，滿足以下條件的點即為ISS特征點。

3.2? ?改進描述子

對兩點云分別應(yīng)用ISS特征點檢測算法提取關(guān)鍵點后，需要將關(guān)鍵點進行匹配并形成兩點云的特征點匹配對。本文基于2D-SIFT算法對特征點的描述提出改進特征點描述符算法，并采用描述符特征值向量的歐氏距離進行特征點對的匹配。為提高點云粗配準(zhǔn)的精準(zhǔn)度，設(shè)置一個閾值（本文設(shè)為0.3），對匹配點對的描述子歐式特征距離小于該值的進行刪除。算法具體流程如下：

Step 1：計算點云的法向量，利用KD樹搜索距離ISS特征點周圍512 個3D點并存儲其法向量。

Step 2：將ISS特征點周圍512 個3D點劃分為16 個三維空間并將其按距離排序，如圖3所示。

Step 3：對每個三維子空間分配一個坐標(biāo)系，該坐標(biāo)系將360°分為32 個區(qū)段，每個區(qū)段的角度范圍為11.25°。在每個三維子空間中計算每個點與ISS特征點的法線夾角并將其映射至坐標(biāo)系中。注意，每個點的法向量是有正負差別的，需要在計算前對法線方向進行調(diào)整，使之朝向一致。

Step 4：統(tǒng)計落入坐標(biāo)系每個區(qū)段的個數(shù)，則每個子坐標(biāo)系為32 維向量，最后將16 個子空間進行合并，一共形成512 維向量的特征描述符。

Step 5：基于特征描述符之間的歐氏距離對ISS特征點進行匹配。預(yù)設(shè)閾值（本文預(yù)設(shè)為0.3），剔除兩點云ISS特征點特征描述符之間的歐氏距離大于閾值的特征點對，提高點對配準(zhǔn)的成功率。

該方法主要考慮了特征點鄰域的法向量與特征點的法向量角度差。相較于其他算法只統(tǒng)計周圍三維點與特征點的關(guān)系致使大部分角度差信息融合在一個區(qū)段，本文算法對特征點鄰域的距離進行分類并排序，總共分為16 個子空間，結(jié)合距離與角度差的信息使得特征點的辨識度提高。在提高對應(yīng)特征點對的配準(zhǔn)率上，經(jīng)過實驗分析，預(yù)設(shè)了閾值來確保對應(yīng)點對的正確性。

3.3? ?粗配準(zhǔn)

基于ISS特征點檢測與改進描述符特征點對的匹配，待配準(zhǔn)的兩點云對應(yīng)點對已基本確定。ICP精配準(zhǔn)需要良好的初始位置或重疊度較高的兩點云，其目的在于確定基于歐氏距離的對應(yīng)點對以進行迭代優(yōu)化。本文基于ISS特征點檢測與改進特征描述符確定了兩點云中的對應(yīng)點對，故在點云的粗配準(zhǔn)階段使用ICP的單次迭代以獲取初始變換矩陣。對于點對點迭代最近點（Point-to-Point ICP）問題，求解點云的最優(yōu)變換有封閉式解，變換矩陣可以借助SVD分解得到。算法具體計算過程如下：

Step 1：設(shè)兩組點云和，點云數(shù)量分別為、。首先計算兩組點云的中心、的坐標(biāo)。

Step 2：對兩點云進行歸一化，并得到點云的協(xié)方差矩陣。

Step 3：對點云的協(xié)方差矩陣進行SVD分解得到，則Point-to-Point ICP的最優(yōu)旋轉(zhuǎn)矩陣如下：

Step 4：對矩陣作方向驗證，以確保是一個旋轉(zhuǎn)矩陣而不是一個映射矩陣，將優(yōu)化結(jié)果確定一個的約束。

將上一步得到的剛體變換矩陣應(yīng)用于源點云，得到新點云。粗配準(zhǔn)階段利用的是點云的對應(yīng)點對進行匹配，本文算法允許點云零重疊即二者相距一定距離，相較于傳統(tǒng)粗配準(zhǔn)算法有一定優(yōu)勢，且由于對應(yīng)點對的正確匹配，粗配準(zhǔn)效果較好，點云重疊度高，利于接下來的點云精配準(zhǔn)ICP的迭代優(yōu)化。

4? ?ICP精配準(zhǔn)（ICP fine registration）

經(jīng)過ISS特征點檢測、改進描述子匹配與點云粗配準(zhǔn)，變換后的源點云與目標(biāo)點云的重疊度已經(jīng)較高，具有良好的初始位姿。ICP算法是利用KD樹以點對間的歐氏距離為標(biāo)準(zhǔn)尋找對應(yīng)點對，點云位姿差異過大會導(dǎo)致算法陷入局部最優(yōu)從而無法匹配成功。而經(jīng)過本文算法的處理，點云位姿基本保持一致，適用于ICP算法的精配準(zhǔn)。精配準(zhǔn)ICP主要流程如下。

Step 1：將粗配準(zhǔn)后的點云與目標(biāo)點云作為精配準(zhǔn)的原始點集。

Step 2：基于點對間的歐氏距離，利用KD樹搜索對應(yīng)點對。

Step 3：求解點云的旋轉(zhuǎn)矩陣與平移矩陣，其目標(biāo)函數(shù)如下，其中和是源點云與目標(biāo)點云中的匹配點對：

Step 4：設(shè)定閾值與迭代次數(shù)，如果兩次迭代的矩陣變化量小于閾值或總迭代次數(shù)大于，則迭代結(jié)束。

5? 實驗結(jié)果與分析（Experimental results and analysis）

5.1? ?改進描述子辨識度實驗

為驗證本文提出的改進形狀描述子對不同特征點檢測算子的魯棒性，分別選取3D-Harris、ISS、3D-SIFT-Z（Z方向梯度約束）和3D-SIFT-N（曲率不變特征約束）進行點云粗配準(zhǔn)的匹配。本文采用的點云模型為斯坦福兔子（Bunny），將源點云模型旋轉(zhuǎn)30°并平移0.3 m作為目標(biāo)點云模型。實驗在AMD Ryzen7-4800H@2.90 GHz、16 GB RAM、Windows 10 64 位家庭版操作系統(tǒng)、VS 2017開發(fā)平臺、PCL 1.8.1版本環(huán)境下運行，采用C++編程語言。實驗效果如圖4所示。

經(jīng)過對不同特征點檢測算子的實驗比較，發(fā)現(xiàn)ISS與改進的描述子契合度最高。如表1所示，ISS+改進描述子的粗配準(zhǔn)算法時間最少且對應(yīng)特征點對的匹配程度最高。為了單純檢測改進描述子的魯棒性，在上述Bunny點云模型的對應(yīng)點對匹配中未設(shè)置閾值。在實際點云配準(zhǔn)整體算法中，由于點云數(shù)量較多而產(chǎn)生誤匹配問題，對算法需要設(shè)置閾值以提高對應(yīng)點對的匹配成功率。

5.2? ?基于ISS特征點+改進描述子的點云配準(zhǔn)

基于以上實驗，最終確定了ISS特征點+改進描述子+ICP的點云配準(zhǔn)整體路線。為了體現(xiàn)算法對不同模型的適配性，分別選用Bunny、Armadillo、Buddha及Dragon四個點云模型，并在此基礎(chǔ)上分別做旋轉(zhuǎn)和平移以獲取目標(biāo)點云模型。實驗結(jié)果如圖5所示。

從實驗結(jié)果可以看出，本文提出的算法較好地完成了點云配準(zhǔn)，具體數(shù)據(jù)如表2所示。與傳統(tǒng)ICP算法需要待匹配的兩點云部分重疊且具有良好的初始位姿相比，本文算法可以在無重疊的情形下進行點云的配準(zhǔn)且算法時間較短。

5.3? ?面向Bunny模型的不同配準(zhǔn)算法實驗比較

為了驗證本文算法的運算時間與精度優(yōu)勢，將本文算法與以往的點云配準(zhǔn)算法進行對比。對Bunny模型分別旋轉(zhuǎn)45°和22.5°并同時移動0.4 m得到兩組目標(biāo)點云，分別為目標(biāo)點云1（Bunny_R225_04）與目標(biāo)點云2（Bunny_R45_04），如圖6所示。實驗分為兩組，第一組點云輸入Bunny和Bunny_R225_04，第二組點云輸入Bunny和Bunny_R45_04。

將本文算法與“基于NDT與ICP結(jié)合的點云配準(zhǔn)算法”“基于SAC-IA和NDT融合的點云配準(zhǔn)方法”和“利用特征點采樣一致性改進ICP算法點云配準(zhǔn)方法”三種方法進行對比，分別輸入上述兩組點云。上算法與本文算法均在VS 2017、PCL 1.8.1及C++環(huán)境中運行，點云配準(zhǔn)誤差由均方根誤差表征。實驗結(jié)果如表3所示，實驗結(jié)果可視化如圖7所示。

通過實驗結(jié)果可知，本文方法無論從配準(zhǔn)時間還是精度方面都較其他配準(zhǔn)方法有優(yōu)勢，與配準(zhǔn)效果較好的SAC-IA+NDT算法相比，其配準(zhǔn)效率提升了17.4%，配準(zhǔn)精度提高了三個量級。由此可知，在兩點云模型是經(jīng)過旋轉(zhuǎn)平移而得到的情況下，本文算法的特征點對匹配度相對較高，因此基于正確對應(yīng)點對的配準(zhǔn)迭代所取得的變換矩陣精度高，配準(zhǔn)速度快。

6? ?結(jié)論（Conclusion）

針對傳統(tǒng)點云配準(zhǔn)ICP需要兩點云具有相對良好的初始位姿，否則算法容易陷入局部最優(yōu)而導(dǎo)致配準(zhǔn)失敗的問題，本文從兩點云的對應(yīng)特征點匹配對的思路出發(fā)，提出ISS特征點檢測與改進形狀描述子的配準(zhǔn)。通過將ISS特征點與其周圍空間三維點進行距離分區(qū)，并各自統(tǒng)計每個分區(qū)三維點與特征點的法向量角度差并形成512 維的特征向量來進行點云對應(yīng)點對的匹配。通過特征向量閾值的約束，點云的特征點對匹配度較高，提高了點云的初始匹配度，為最終點云的ICP提供了良好的初始位姿。但仍需注意的是，本文提出的改進形狀描述子匹配對點云的完整性要求較高，特征關(guān)鍵點處的點云缺失會影響特征點的特征向量匹配，進而帶來配準(zhǔn)誤差。

參考文獻（References）

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

[2] 鐘瑩，張蒙.基于改進ICP算法的點云自動配準(zhǔn)技術(shù)[J].控制工程，2014，21（01）：37-40.

[3] 宋成航，李晉儒.利用特征點采樣一致性改進ICP算法點云配準(zhǔn)方法[J].北京測繪，2021，35（03）：317-322.

[4] RUSU R B， BLODOW N， BEETZ M. Fast point feature histograms （FPFH） for 3D registration[C]// IEEE. IEEE International Conference on Robotics and Automation. Kobe： IEEE， 2009：3212-3217.

[5] BIBER P， STRASSER W. The normal distributions transform： A new approach to laser scan matching[C]// IEEE/RSJ. Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems. Las Vegas： IEEE， 2003：2743-2748.

[6] 荊路，武斌.基于SAC-IA和NDT融合的點云配準(zhǔn)方法[J].大地測量與地球動力學(xué)，2021，41（04）：378-381.

[7] 王慶閃，張軍.基于NDT與ICP結(jié)合的點云配準(zhǔn)算法[J].計算機工程與應(yīng)用，2020，56（07）：88-95.

[8] ZHONG Y. Intrinsic shape signatures： A shape descriptor for 3D object recognition[C]// ICCV. Proceedings of the 12th IEEE International Conference on Computer Vision Workshops（ICCV Workshops）. Kyoto： IEEE， 2009：689-696.

[9] HARRIS C， STEPHENS M. A combined corner and edge detector[C]// AVC. Proceedings of the Alvey Vision Conference. Heidelberg： Springer， 1988：147-151.

[10] LOWE D G. Distinctive image features from scale-invariant keypoints[J]. International Journal of Computer Vision， 2004， 60（2）：91-110.

作者簡介：

夏坎強（1996-），男，碩士生.研究領(lǐng)域：機器視覺，圖像處理.