基于多分辨率的快速迭代最近點配準算法

王 碩 王亞飛 李學華

(北京信息科技大學信息與通信工程學院 北京 100101)

0 引 言

點云配準是計算機視覺和圖像處理的一項重要研究課題。該技術廣泛應用于醫學[1]、移動機器人導航[2]、計算機輔助設計[3]、三維重建[4]等領域中。通過特定的幾何變換，點云配準旨在使兩組不同圖像的點達到空間一致性。換句話說，從參數未知的初始變換開始，它試圖找到一個最優的變換，使兩個不同相機坐標系下的點云轉換到同一個世界坐標系下。

關于點云配準的研究可以追溯到20世紀80年代早期，當時專門針對二次曲面提出了全局剛性點集配準算法。1992年Besl等[5]提出了經典的ICP算法，用于點云的精確配準，后續ICP算法的改進主要圍繞提高配準精度和加快配準速度兩個方面進行研究。為了改進ICP算法的配準精度問題，Rusu等[6]提出快速特征直方圖(FPFH)特征，目標是通過點周圍的平均曲率來編碼其鄰域的幾何屬性，該算法能很好地應對鄰域中存在不同采樣密度或不同噪聲水平的點，進而提升配準精度。Seal等[7]使用Hausdorff距離計算兩點云間誤差，降低收斂誤差。Ye等[8]將點的顏色和深度信息一起作為配準因素，提高了配準精度，并避免初始值的影響。文獻[9-12]提出了一種基于關鍵點的點云配準方法，根據關鍵點不變的特性實現精確配準，然而每個點的特征計算量很大，時間消耗較多。唐志榮等[13]，提出一種基于多維混合柯西分布的點云配準算法，該算法將點云數據模型轉換為多維混合柯西分布模型，用數據中心點進行配準，該算法配準效果較好，但配準效率有待提升。

以上方法由于要計算點云更多維度的特征，增加了點云配準時間。為加快配準速度，鐘瑩等[14]使用歐氏距離閾值和法矢量夾角閾值來選取正確的匹配點對，這種方法可降低點云間點對的噪聲帶來的干擾，減少迭代次數，但該算法過于依賴于閾值的選定，閾值設置不佳會導致精度的下降。楊秋翔等[15]根據每一點的法矢量角計算該點的關鍵度，依據關鍵度對點云數據進行精簡，提高了配準效率，但當點云中點數超過十萬時，關鍵度的計算成為主要的耗時部分。Ji等[16]利用遺傳算法將點云轉化為三角網搜尋最近點的方法實現點云配準，具有較高的配準效率，但配準精度有待提升。王暢等[17]使用全局結構特征做初始配準，之后利用局部結構特征做快速精確配準算法。該算法提高了配準速度，但當點云數較少的情況下，可能會使算法配準結果不理想。趙敏等[18]提出了一種基于lp空間力學模型的點云配準算法，其中：l表示線性賦范空間，p表示空間維度。該算法收斂速度快，但當物體形狀結構接近對稱時，會降低配準精度。陳旭等[19]提出一種基于校正點云主成分方向的線性計算方法，配合ICP算法實現高效精確的點云全局配準，但此算法在點云分布不均勻或有缺陷時結果可能有所偏差。傳統ICP算法的時間復雜度為O(mdnd)，m、n分別為d維空間里點的數量，即ICP算法的計算效率受點集數量和空間維數的影響[20]。

本文主要針對ICP算法配準效率問題進行研究，提出一種易于實現且魯棒性高的多分辨率ICP配準算法。首先使用本文提出的自適應體素網格濾波器對點云進行多分辨率采樣，然后使用提出的多分辨率思想，從低分辨率到高分辨率進行配準，利用低分辨率點云進行快速初始配準，再利用高分辨率點云提高配準精度，完成粗略到精細的匹配。實驗結果表明，本文算法簡單可行，改善了ICP算法計算效率低的問題。

1 傳統ICP算法

由Besl和McKay所提出的傳統ICP算法，是一種高效處理兩個點云間配準的方法。通常，剛性配準是確定兩個點云的點集之間的剛性變換的過程，可以匹配對應點。給定兩組3D點云：待配準點云P={p(1),p(2),…,p(n)}和目標點云Q={q(1),q(2),…,q(m)}，其中n和m分別表示兩組點云中點的數量。ICP算法的目標就是找到旋轉變換矩陣R和平移變換矩陣t，使得?i,q(i)=Rp(i)+t。然而由于實際配準過程中，存在噪聲、誤差、拍攝角度等問題的影響導致上式不會完美成立，即不存在一個R和t可以使所有點滿足上式。因此ICP算法的目標轉換為求旋轉R和平移t，使兩點云間對應點距離之和最小，目標函數f(R,t)表示為：

(1)

ICP算法以迭代的方式尋找最優值，其基本步驟如下：

1) 尋找待配準點云在目標點云中的對應點。根據待配準點云P的點坐標，在目標點云Q中搜索相應的最近點點集。

2) 根據點云匹配點對，求使對應點間平均距離最小的剛體變換參數。k對點可以得到k個方程組，使用最小二乘法求解出方程中的參數R和t。

3) 應用變換并計算新的對應點間距離。對點云P中每一個點應用轉換公式Pj=RPj+t，其中下標j表示第j輪迭代。之后重新計算新的對應點間距離Dj：

(2)

4) 判斷是否進行下一輪迭代。設定精度閾值σ和迭代最大次數N，若步驟3中求出的新的對應點間距離Dj小于閾值σ或迭代次數超過N，則停止迭代，否則重復步驟1-步驟3繼續迭代。

在ICP算法配準過程中，兩個點云里點的數量和迭代次數對計算時間有很大影響。傳統ICP算法中將所有點都納入到計算過程中，嚴重影響了配準效率。本文提出一種基于多分辨率配準的ICP算法，以改善配準效率低的問題。

2 多分辨率配準的ICP算法

2.1 體素網格濾波器

對點云進行多分辨率采樣時，應盡量保持原點云的曲面特征以及點的密度分布。若使用隨機采樣法，點云的輪廓信息將被削弱，并且會造成點分布不均勻。使用體素網格濾波器對原點云進行采樣處理，該方法可在減少點云里點的數量的同時，保持點云原來形態特征，但是采樣時體素立方體的邊長需要人為指定。因此，本文提出自適應體素網格濾波器，根據點云中包含的點數自動計算體素網格的邊長，可對不同規模的點云自動做出適合的多分辨率采樣。

2.1.1傳統體素網格濾波器

體素網格濾波器的基本原理是：將原始輸入點云分成多個相同大小的立方體，立方體的大小可根據實際需求進行調整。然后計算每個立方體中所有點的重心，以重心替代這個立方體中的所有點。具體計算方法如下所示：

1) 確定立方體邊長K，將點云按順序分成多個大小為K×K×K的立方體。K值越大，采樣后的點云的分辨率越低，反之，則分辨率越大。采樣立方體個數為A×B×C，計算方法如下：

(3)

式中：xmax、xmin、ymax、ymin、zmax、zmin分別為X、Y、Z三個坐標軸上點坐標的最大值、最小值。

2) 計算每個立方體包含點的重心(x′,y′,z′)，計算方法如下：

(4)

式中：m為該立方體中點的數目。

3) 以重心代替該立方體中所有點，并將所有立方體的重心重新合成為新的點云。

2.1.2自適應體素網格濾波器

針對不同點數的點云，本文提出的體素網格濾波函數中立方體的邊長自適應更新策略。

立方體邊長K的計算如下：

(5)

式中：l表示第l層濾波，l=0時為原始分辨率；Dori為原始分辨率點間平均距離。其計算如下：

(6)

式中：N為點云里點的總數；Hi為點云中第i個點；Hdi為距離Hi最近的點。

式(5)中β(s)為自適應比例因子，控制體素網格立方體邊長增長率，定義為：

(7)

2.2 改進的ICP算法

2.2.1整體思路

本文在ICP配準算法中引入多分辨率的思想。在ICP算法前幾輪迭代的初始配準中，首先使用較低分辨率的點云，快速獲得兩個點云之間的初始變換，提高匹配效率。然后使用初始變換的結果，以更高的分辨率實現更精確的配準。不同分辨率中點云的形狀基本保持一致，只有點云中點的數量不同，因此較低分辨率的配準結果，可作為高分辨率配準的初值。點云里點的數量越少，算法的計算速度越快，同時精度會有所下降；點的數量越多，匹配的精度會提升，但計算耗時會大幅增加。使用較低分辨率的兩個點云獲得的配準結果，比用原始分辨率獲得相同精度的配準結果的耗時顯著減少。該算法的優點是使用快速低分辨率配準代替高分辨率配準的初始迭代過程，減少了高分辨率下的配準迭代次數，從而提高計算效率。所提出的快速多分辨率ICP算法流程圖如圖1所示。

圖1 本文算法流程圖

2.2.2詳細流程

本文提出的多分辨率配準詳細流程如下：

1) 使用提出的自適應體素網格濾波器對兩點集P、Q進行多次不同分辨率采樣。

Hl=(Hl-1)l=1,2,…,L

(8)

(9)

(10)

3) 重復步驟2)直到dl不再減小為止。

4) 令l=l-1提升點云分辨率，得到Pl-1和Ql-1。

5) 重復步驟2)-步驟4)，直到l=0或均方根誤差(RMS)達到設定閾值為止。RMS計算方法如下：

(11)

3 實驗結果與分析

為了驗證所提出的方法的魯棒性和計算效率，分別與傳統ICP算法、文獻[14]、文獻[15]、文獻[18]和文獻[19]改進的ICP算法的配準時間和精度進行了仿真和比較。實驗使用斯坦福大學開放點云數據庫的兔和龍模型進行對比試驗。實驗平臺為Ubuntu 16.04系統，CLion 2016，運行在配置為Core i7-8700K CPU 3.8 GHz，16 GB RAM的臺式計算機上。

實驗中待配準點云模型初始位置如圖2所示，白色為目標點云、淺灰色為待配準點云。其中兔模型點云中點的數量為35 947，龍模型點的數量為437 645。

圖3和圖4分別為兔和龍模型在不同分辨率下的點云模型。采樣后點云最低包含點數設為1 000。由式⑸計算可得，兔模型點云下采樣計算1次，體素網格邊長K=0.005；龍模型點云下采樣計算2次，體素網格邊長K分別為0.001和0.005。表1為兔和龍模型在不同分辨率下的采樣點數和采樣耗時。可以看出使用體素網格濾波器采樣得到的不同分辨率的點云模型在降低點云點數后，仍保留了原始點云的形態特征，且由多分辨率采樣帶來的計算耗時極短。

(a) 兔模型 (b) 龍模型圖2 待配準點云

(a) K=0.005 (b) 原始分辨率圖3 兔模型多分辨率采樣結果

(a) K=0.005 (b) K=0.001

(c) 原始分辨率圖4 龍模型多分辨率采樣結果

表1 多分辨率采樣計算耗時

圖5為兔和龍模型配準實驗結果。可以看出傳統ICP、文獻[15]、文獻[18]、文獻[19]和本文算法都可以實現點云的精確配準，配準結果基本一致，從視覺上都可以認為點云正確配準；文獻[14]算法效果略差，出現了輕微重影的現象。

(a) 原始ICP配準結果

(b) 文獻[14]配準結果

(c) 文獻[15]配準結果

(d) 文獻[18]配準結果

(e) 文獻[19]配準結果

(f) 本文改進的ICP配準結果圖5 兔子及龍點云模型配準結果

表2為四種算法的配準誤差、迭代次數和運行時間的比較。配準誤差(RMS)停止閾值為1×10-4m。該結果表明在配準精度基本相同的情況下，本文算法相對于傳統ICP、文獻[14]、文獻[15]和文獻[18]算法大大縮短了配準時間。尤其是在龍模型配準實驗中，由于點數過多導致傳統ICP算法耗時成指數級增長，遠超配準時長所能接受的范圍，文獻[14]、文獻[15]的算法雖比原始ICP算法耗時降低一半左右，但時間仍很長。文獻[19]的算法已將耗時降低至可接受的范圍內，但本文改進的ICP算法將配準時間進一步縮短。

表2 算法性能比較

六種算法在兔模型上的配準過程如圖6所示。可以看出，本文算法配準耗時遠低于傳統ICP算法。在基本相同的配準精度下，傳統ICP需要近2.4 s；文獻[14]、文獻[15]的算法需近1.5 s；文獻[19]顯著降低配準時間；而本文算法可在前幾輪迭代中完成快速初始配準，在后幾輪迭代中對配準精度進一步提高，總時長控制在0.5 s內，耗時降低為原始ICP算法的20%左右，且比文獻[19]算法耗時更少。

圖6 兔模型配準時間比較

為進一步驗證本文算法在效率上的提升，選取了另外5組不同點數的點云進行配準實驗。配準誤差(RMS)停止閾值仍為1×10-4m，在各算法配準精度均到達這個標準后，將本文算法的配準耗時與傳統ICP、文獻[15]和文獻[19]的耗時進行對比，如表3所示。可以看出，本文算法相比傳統ICP算法，配準耗時僅為原來的15%及以下；相比文獻[19]的算法，在各個模型中，本文算法耗時均低于文獻[19]算法的耗時，且隨著點云規模的增大，配準所用時間降低的越多。實驗結果表明，本文提出的改進的ICP配準算法可以快速準確收斂。

表3 不同規模點云配準耗時 s

4 結 語

本文提出了一種多分辨率改進的ICP快速匹配算法用于兩點云間配準。該算法構造了一種用于點云匹配的多分辨率模型，并使用提出的自適應體素網格濾波器對點云進行多分辨率采樣。可以在低分辨率下快速獲得兩個點云之間的初始變換，然后使用先前變換以更高分辨率進行更精確的配準。通過這種方法降低了ICP算法在初始配準過程中需要處理的點數，從而降低配準時間。實驗表明，本文算法提高了ICP算法的配準效率，且隨點云規模增加，速度提升幅度遞增趨勢。