基于改進SAC-IA算法的激光點云粗配準

張 晗 康國華 張 琪 張文豪 徐偉證

南京航空航天大學航天學院微小衛星研究中心，南京 210000

目前的點云配準算法中，應用最為廣泛的是由BESL和 MCKAY[12]提出的迭代最近點算法[13-14](iterative closest point, ICP)，此算法通常要求較好的初值[15]。目前，國內外也出現很多改進ICP算法[16-18]，并得到廣泛應用[19]。文獻[16]通過對對應點對施加曲率和點距雙重約束，驗證算法對角度差異較大模型的拼接處理的有效性。文獻[17]通過設置動態估計方法對誤匹配點對進行刪除，以均方根誤差作為配準誤差，實現了三維顱骨的精確配準。文獻[18]利用點到最近三點組成的面的垂足作為最近點，點進行分類約束改進，剔除了點落在面外造成虛假配準的情況，提高了算法的迭代精度。文獻[19]利用快速ICP算法結合TSDF點云融合算法和基于多特征融合的三維目標識別算法，降低了非合作目標近距離相對位姿測量系統對先驗信息的依賴，提高了系統自主性。

ICP算法實現的是對點云的精配準，其重要前提是點云的粗配準過程，粗配準的好壞直接影響精配準的效率。目前，粗配準方法主要包括：基于特征的方法[20-21]、基于隨機抽樣一致算法(random sample consensus，RANSAC)[22]和采樣一致性初始配準算法(Sample Consensus Initial Aligment, SAC-IA)[23-24]。其中，SAC-IA算法是針對初始的變換矩陣，估計存在計算復雜度較高的問題所提出的改進算法，該算法可以從候選對應關系中進行大量的采樣，通過查看非常大量的對應關系，快速找到一個好的變換。文獻[21]利用特征間距離和方向為元素構成三維特征描述集合，引入集合相似理論判別特征是否匹配，與FPFH特征直方圖含義相近，均是提取有效特征。文獻[23]利用基于特征點的SAC-IA算法實現了兩點云的初始變換，使兩點云集有相對較好的初始位姿，有利于點云的精確配準。文獻[24]采用SAC-IA算法對點云進行初配準，為三維地圖的重建奠定了基礎。前人利用基于特征的方法和傳統的SAC-IA算法實現了點云的粗配準，能夠為精確配準提供較好的初始旋轉矩陣，但仍存在精度不夠高、易出現誤配準與響應時間緩慢的問題，針對以上問題，本文結合基于特征的方法在SAC-IA方法上做出改進。

1 SAC-IA算法概述

采樣一致性初始配準算法(SAC-IA算法)是一種基于點云特征的粗配準方法，通過利用3D特征描述符計算點云局部特征，根據局部特征進行兩站點云的特征匹配，最終找出同名特征點云之間的對應關系，求解出兩站點云變換矩陣。

圖1 基于FPFH特征的SAC-IA算法

2 改進的SAC-IA算法

2.1 傳統SAC-IA算法存在的問題

根據圖1的原算法流程圖，主要發現如下幾個問題：

1)特征點選取隨機性大，未考慮樣點共線與形成局部樣點集合的情況，如圖2；特征點配準時僅滿足點對距離約束和FPFH特征描述子約束，易出現誤配準；

圖2 樣點隨機和共線

2)誤差評定時，僅對樣點之間的歐氏距離閾值進行設定，存在當歐氏距離偏差很小時，點特征的差異卻很大的情況，陷入局部最優解；同時，通過設定迭代次數尋找大事件中的最優結果，會浪費大量的時間，如圖3所示[25]。在設定迭代次數后，其誤差配準計算部分占算法整體時間的消耗比例最大。在該部分算法中，由于特征點的誤匹配，導致傳統SAC-IA算法仍對錯誤的配準結果進行誤差值的計算，降低整體配準的效率與準確率。

圖3 SAC-IA初始配準時間消耗圖

3)整個流程耗時過大。在隨機采樣點時，需要對兩站點云中的全部點進行FPFH直方圖的計算，但進行配準時只需要樣點即可。

第三，建立有關于國有企業財務風險的內部預警預控制度，對此，可以使用財務信息系統，加強對成本費用、債務風險和投資模塊進行控制。

針對以上問題，本文研究算法主要改進特征點的選取和誤差評定，經改進后的算法在快速性和準確性上有所提高，如圖4所示。

圖4 改進后的SAC-IA算法流程圖

2.2 改進的特征點選取

特征點的匹配，是基于點云的特征信息通過幾何學與統計學等比較特征點之間的相似性，特征信息的選取通常因點云的形狀、分布的不同而改變。FPFH點特征直方圖描述子可用于邊界、拐角、平面點云的分類算法，且Rusu[26]也實現了上述算法。但在實際仿真中，由于特征點的選取隨機性較大，仍會由于特征點選取錯誤或不佳導致誤匹配，所以本小節在特征點的選取上，添加了幾何約束進行篩選。

1)限定特征集合掃描角度

首先需要建立目標本體三維坐標系，將目標的中心位置定義為坐標系原點O，這樣，目標的每一點P坐標(x,y,z)均有對應值，如圖5所示。

圖5 點在三維坐標系下的表達

現將1個圓360°等分，定義掃描角sA={0°，±22.5°,±45°，±67.5°,±90°,±112.5°,±135°,±157.5°,180°}，如圖6所示；將原始點云數據信息從P(x,y,z)擴展為P(x,y,z,ω)；俯仰角ω與集合sA中任意掃描角si比較，當|si-ω|≤A,ω∈sA。

圖6 掃描角的選取

2)限定特征點投影形狀

至此，特征點的選取范圍由隨機轉換為在限定掃描角的數組中進行進一步篩選，初步解決了局部樣點的情況。再取si=0，在該數組中隨機選取一點P0(x0,y0,z0)，在si=±22.5°的2個數組集合中取DH>y1-y0>DL的2點，其中DL和DH分別為設定的閾值下上限，再在si=±45°的數組集合中取DH>y2-y1>DL的2點，依次類推。使選取的特征點投影至某坐標軸上近似與如圖7所示。

圖7 改進的特征點選取近似三角形

2.3 基于改進SAC-IA的誤差評定

1)誤匹配的修正

傳統的SAC-IA算法中，配準誤差指配準后兩站點云之間的歐氏距離差值。這種方法未考慮待配準站中包含基站點云不存在的點這種情況，引入了新的誤差。所以在本節改進算法中，選取配準后兩站點云的特征點歐氏距離差值作為一個評判標準，同時引入這部分特征點的斜率差值作為幾何評判的標準；且粗配準算法是精配準的前提，所以粗配準的結果是否可行，完全取決于是否達到了精配準的初始條件。

如圖8所示，在誤匹配修正器設計了3個評判標準，其中，FPFH值差值、坐標2-范數差值與幾何斜率差值均是針對輸入為P′與Q中的特征點，不對所有點云進行評判。滿足修正器3個標準后表示匹配成功，匹配失敗后進行重新選點。

圖8 誤匹配修正算法原理

2)誤差評定方法

圖9 誤差評定標準

3 仿真驗證和分析

3.1 仿真環境設置

為了對所提出改進方法進行仿真分析驗證，利用Matlab構建算法改進程序，整個仿真運行環境如下表1所示。

表1 仿真軟硬件環境參數

表2 仿真所用數據及參數

3.2 仿真結果及分析

為了驗證本文算法的有效性和優化結果，采用了表3中的斯坦福兔子Bunny開源數據源點云(原始與精簡)和利用Meshlab軟件將航天器模型轉換為三維點云數據源Spacecraft。同時，模擬粗配準使用環境，使待配準站點云添加隨機噪聲，兩站點云的坐標無對應值。

通過Matlab對傳統SAC-IA算法和本文研究改進算法的配準結果進行比較。圖10是原始輸入的點云模型，圖11是傳統SAC-IA算法的配準結果，圖12為本文改進算法的配準結果。對比圖11和12，本文研究算法能夠實現良好的配準結果。

為了驗證本文提出的改進算法是否有效，對算法進行了時間消耗和精度的驗證。如圖13(a)所示，在Bunny和Spacecraft點云集上，本文所提改進SAC-IA算法在初始配準時間總消耗上均比傳統算法提高了一倍以上。由圖13(b)、(c)和(d)可以看出在點云矩陣變換上本文算法相較于傳統算法差別不大，分析原因為該部分僅與點云數據量有關，而在誤差配準過程，本文算法效率高出傳統算法效率2倍以上。另外，在特征描述子計算、特征點匹配和變換矩陣計算上，均在一定程度上縮短了時耗。

圖10 原始輸入的點云模型

圖11 傳統SAC-IA算法匹配結果

圖12 本文改進算法的配準結果

圖13 傳統SAC-IA與改進的SAC-IA算法時間消耗對比

根據表3可以看出，經ICP算法驗證后，在Bunny和Spacecraft數據集上，傳統SAC-IA算法饒三軸的旋轉角大多在2°以上，存在較大誤差。 本文所提改進算法較好地彌補了這一不足，對于原始Bunny點云集，粗配準饒三軸的旋轉角低至10-2量級，對于精簡Bunny點云集，粗配準繞三軸的旋轉角低至10-6量級，對于Spacecraft點云集，粗配準繞三軸的旋轉角低至10-34量級，近似于0。通過對比原始Bunny與精簡Bunny點云集，說明該算法對于數據量少的點云粗配準具有較好的效果；通過對比精簡Bunny與Spacecraft點云集，說明該算法對于坐標值大的點云粗配準具有較好的效果。同時，對于Bunny點云集，粗配準沿三軸的平移量與傳統算法的結果相差10倍；對于Spacecraft點云集，粗配準沿三軸的平移量高出傳統算法的結果3個數量級以上。由此可見，本文算法對于坐標值大、數據量小的點云具有更好的匹配效果，可以實現高精度、高效率的點云粗配準。

表3 仿真結果精度分析

4 結語

通過優化特征點選取的約束規則和誤差評定標準，本文算法的運行效率比傳統的SAC-IA算法有所提高，分別在大小差異較大的Bunny和Spacecraft數據進行驗證，改進的算法均可有效完成粗配準工作。使用基于幾何特征的掃描角限定與FPFH直方圖描述子疊加形成的特征，通過提高特征匹配的約束條件，有效解決了特征點樣點共線、局部樣點導致的算法收斂速度慢的問題，同時避免點云的誤匹配，從而提高配準時效性和準確性。使用FPFH直方圖差值、歐氏距離差值與幾何斜率差值作為誤匹配修正標準，規避迭代循環，有效縮短了算法地收斂時間。本改進算法雖然相比于傳統算法在時效性和精確性上有所提高，但是運行時間仍然較長，未來將繼續致力提高算法運行效率。