基于ISS特征點和改進描述子的點云配準算法研究

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

關鍵詞：點云粗配準;ISS特征點;改進描述子;ICP算法

中圖分類號：TP391.1? ? ?文獻標識碼：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）

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

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

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

2? ?算法介紹（Algorithm introduction）

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

3? ?點云粗配準（Coarse registration of point clouds）

3.1? ?ISS特征點提取

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

設點云中含有n 個點，，ISS關鍵點算法具體流程如下：

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

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

Step 3：計算每個點的協方差矩陣：

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

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

3.2? ?改進描述子

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

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

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

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

Step 4：統計落入坐標系每個區段的個數，則每個子坐標系為32 維向量，最后將16 個子空間進行合并，一共形成512 維向量的特征描述符。

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

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

3.3? ?粗配準

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

Step 1：設兩組點云和，點云數量分別為、。首先計算兩組點云的中心、的坐標。

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

Step 3：對點云的協方差矩陣進行SVD分解得到，則Point-to-Point ICP的最優旋轉矩陣如下：

Step 4：對矩陣作方向驗證，以確保是一個旋轉矩陣而不是一個映射矩陣，將優化結果確定一個的約束。

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

4? ?ICP精配準（ICP fine registration）

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

Step 1：將粗配準后的點云與目標點云作為精配準的原始點集。

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

Step 3：求解點云的旋轉矩陣與平移矩陣，其目標函數如下，其中和是源點云與目標點云中的匹配點對：

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

5? 實驗結果與分析（Experimental results and analysis）

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

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

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

5.2? ?基于ISS特征點+改進描述子的點云配準

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

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

5.3? ?面向Bunny模型的不同配準算法實驗比較

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

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

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

6? ?結論（Conclusion）

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

參考文獻（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算法的點云自動配準技術[J].控制工程，2014，21（01）：37-40.

[3] 宋成航，李晉儒.利用特征點采樣一致性改進ICP算法點云配準方法[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融合的點云配準方法[J].大地測量與地球動力學，2021，41（04）：378-381.

[7] 王慶閃，張軍.基于NDT與ICP結合的點云配準算法[J].計算機工程與應用，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-），男，碩士生.研究領域：機器視覺，圖像處理.