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

南京航空航天大學航天學院微小衛(wèi)星研究中心，南京 210000

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

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

1 SAC-IA算法概述

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

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

2 改進的SAC-IA算法

2.1 傳統(tǒng)SAC-IA算法存在的問題

根據(jù)圖1的原算法流程圖，主要發(fā)現(xiàn)如下幾個問題：

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

圖2 樣點隨機和共線

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

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

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

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

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

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

2.2 改進的特征點選取

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

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

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

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

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

圖6 掃描角的選取

2)限定特征點投影形狀

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

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

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

1)誤匹配的修正

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

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

圖8 誤匹配修正算法原理

2)誤差評定方法

圖9 誤差評定標準

3 仿真驗證和分析

3.1 仿真環(huán)境設置

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

表1 仿真軟硬件環(huán)境參數(shù)

表2 仿真所用數(shù)據(jù)及參數(shù)

3.2 仿真結(jié)果及分析

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

通過Matlab對傳統(tǒng)SAC-IA算法和本文研究改進算法的配準結(jié)果進行比較。圖10是原始輸入的點云模型，圖11是傳統(tǒng)SAC-IA算法的配準結(jié)果，圖12為本文改進算法的配準結(jié)果。對比圖11和12，本文研究算法能夠?qū)崿F(xiàn)良好的配準結(jié)果。

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

圖10 原始輸入的點云模型

圖11 傳統(tǒng)SAC-IA算法匹配結(jié)果

圖12 本文改進算法的配準結(jié)果

圖13 傳統(tǒng)SAC-IA與改進的SAC-IA算法時間消耗對比

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

表3 仿真結(jié)果精度分析

4 結(jié)語

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