點云配準RANSAC算法研究改進

吳俊秀，陳桂芬，李岳，朱海忱

（長春理工大學 電子信息工程學院，長春 130022）

近年來，得益于三維點云數據技術的發展，機器視覺技術獲得了迅猛發展，三維點云數據實際應用也越來越受到各方的關注，目前在逆向工程、計算機視覺、文物數字化等領域三維點云數據處理技術已得到了廣泛推廣。三維點云數據配準是點云數據處理的關鍵技術，它的主要原理是把不同位置的點云通過重疊部分的信息，變換到同一個位置［1-2］。三維點云配準技術從點云位置來分可分為粗配準技術和精配準技術。粗配準技術主要用于配準兩個位置相差很大的點云，在粗配準技術方面曾有Fischler提出了RANSAC算法［1］，主要思想是不考慮點云位置間距離的相差大小，都能實現配準，但該算法運算復雜度高、運算時間長、配準精度差、配準效率低，并不適合大規模點云配準。精配準技術用于已經粗配準好的點云，其中包括Besl等人提出了的ICP［3-17］算法，以及Zhang等在它的基礎上的改進算法，Granger等［3］把EM（Expectation Maximization algorithm）算法應用到ICP上的改進，Gold等人［4］也提出Softassign的配準算法。這一類算法雖然在搜尋特征點方面有些進步，但還是無法做到將無關點及誤匹配點剔除和校正。

鑒于上述問題，本文從配準精度和配準效率等方面進行研究，在點云配準過程中通過交比不變的約束方式，將無關點進行剔除，將錯誤點進行校正，改進了RANSAC求解仿射變換矩陣的方法。提出一種改進的RANSAC快速點云配準算法，提高了配準速度和精度，節省了配準時間。

1 點云配準RANSAC算法

求源點云和目標點云的旋轉平移矩陣（剛性矩陣或歐式變換）是點云配準過程［7］的核心，將源點云變換到目標點云相同的坐標系下，通常可以表示為：

其中，pt,ps就是源點云和目標點云中的一對對應點。圖1為點云配準原理圖，點云一與點云二相互重疊，重疊部分中臨近點之間的變換關系就是其中的R與T旋轉平移矩陣，即兩個集中點的對應關系，也是配準的核心問題。

圖1 點云配準的原理圖

RANSAC算法首先選擇少而有效的初始數據集合，再從一定容差范圍中盡可能地擴大初始數據集合。

2 交比不變模型相關定理

在射影變換中，有一個基本的不變量，稱為交比不變量，在剔除和校正錯誤的點云匹配點對中［6］，需要用到交比（Equality of Cross Ratio）恒定性原理［1］，也就是射影變換保持點列的交比不變性。

定理1 已知A,B,C，三點在直線l上，把C作為參考點，于是有點A,B與點C之間的距離比值就是一個位置比值，如圖2所示，即：

圖2 定理示意圖

定理2 已知在直線上的A,B,C,D，C,D四點作為參考點，同理由式（2）得到兩個簡單比值的比值，即為交比比值：

定理3 以投影中心O為參考條件下，在三維空間中的四個點A,B,C,D存在四個對應點A1,B1,C1,D1，他們也是共線的。而且點A,B,C,D的交比在三維空間投影下基本不受影響，即交比比值恒定。即：

推理 由定理3可知，圖像中的不變點通常用到交比比值恒定原理。平面標定模板內有四個點在一條直線上：q1=(x1,y1),q2=(x2,y2),q3=(x3,y3),q4=(x4,y4)，從而得到四個點的交比：

RANSAC算法雖然是應用最為廣泛的點云配準方法，但是由于RANSA算法是按照幾何關系一致性來隨機選擇多對對應點作為控制點將點云配準，然后再將以上過程迭代多次，以此來確保最大概率獲得較優的匹配效果，這樣計算過程頗為耗時，誤匹配率較高，因此RANSAC點云配準算法一般只能獲得一個不準確的配準結果。鑒于此，本文提出基于交比不變原理選取樣本集改進RANSAC算法。

3 基于交比不變的改進RANSAC實現

將交比不變的性質應用在RANSAC算法中，作為采集目標圖像局內點的約束條件。針對誤匹配點多，計算效率低的問題，在檢測得出目標圖像中的局內點坐標后，通過交比不變原則對目標圖像中配準錯誤的局外點坐標進行校正，增加局內點的個數，有效地解決傳統算法找尋最優仿射矩陣效率低下的缺點。

交比不變的RANSAC改進算法配準目標點云的具體步驟如下：

（1）假設隨機選擇一組個數為n的匹配點作為參考樣本，N為全部數據點數，θ為這n個數據點符合該模型的概率，即：

（2）通過上述參考樣本得到參考模型M，用全部數據點檢驗模型參數，得到該模型的局內點數n′。

（3）預先設定誤差閾值δ，小于δ，該模型區域為目標點云特征點區域；大于δ，重新計算目標點云特征點區域。

（4）根據所選目標點云區域兩特征點間的梯度值，設源點云圖像中第i個特征點的坐標為(xi,yi)，i=1,2,...,n，中心特征點坐標為(xc,yc)，兩特征點間的距離可表示為：

源點云圖像中n個特征點坐標間的距離矩陣為：

通過設置目標點云的中心點坐標與源點云的中心點坐標之間的距離閾值，來評估配準誤差，當目標點云的中心點坐標與源點云的中心點坐標之間的距離大于設定閾值時，重復上述第（3）步到第（4）步，直到滿足設定閾值。

（5）對目標點云中各特征點的坐標位置進行評定。設新的配準目標點云中的特征點坐標為各特征點坐標間的距離為，計算方法同步驟（4）。則新的配準目標各特征點間的距離比與源點云各特征點間的距離比的比值：

若eij=0，則表示新配準的目標點云特征點定位錯誤，需要對其進行坐標位置校正。

（6）若目標點云與源點云臨近兩點的距離比大于設定的閾值時，即認為定位錯誤，同時對目標點云的點坐標距離比做一次遍歷檢查，對不符合條件的點，通過交比不變原則進行校正，即將符合交比條件的點重新設置為特征點。假設配準的目標圖像有m個點定位正確，n個點定位錯誤。r,s,t為m個正確定位點中的3個隨機的互異共線的點，v為n個錯誤定位點中與r,s,t共線的點。r,s,t,v分別對應源點云中第1、2、3、4四個點。則由定理1得：

根據交比不變原則，可以對錯誤配準的目標點云坐標點進行校正，對校正后的點再次進行評定，若符合要求則進行下一步，否則重復第（5）步操作。

（7）經過K次重復操作之后，在校正完成后的匹配點對中選取6對對應點，計算旋轉平移矩陣初值H。

（8）再利用迭代最近點算法ICP（Iterative Cloest Point，），在已知旋轉平移矩陣初值H的情況下，進一步精配準，得到更加精確的旋轉平移矩陣［12］。假設P、M是兩個點集，P為目標點云的點集，M為源點云的點集，其基本步驟如下［2］：

（1）匹配模型中進行匹配的數據點的選取采樣，即從P中取點集pi。

（2）兩模型中有對應關系的匹配點的選擇，再在M中找出距離pi最近的對應點集mi。

（3）匹配點對的估計誤差的選取，通過最小二乘法計算mi中最近點之間最小二乘意義下的配準參數R和t，并計算估計誤差d：

（4）更新數據遠匹配的點對，使用R和t對數據點集pi中所有點進行更新，獲得更新后的數據點集pk。

（5）迭代停止度量準則的選擇，對數據點集合Pk重復上述（2）-（4），直到兩次迭代之間的估計誤差d變化小于閾值δ，停止迭代。

（6）通過最優化方法的重復迭代，此時可以得到兩個點云的配準結果，從中選取6對對應點，計算精確的旋轉平移矩陣H′。

4 仿真實驗及其結果分析

4.1 仿真實驗

本節通過對來自斯坦福大學的點云數據庫中的點云數據進行實驗，來評估本文算法的性能。實驗平臺為Windows7 64位操作系統，Visual Studio 2013 Visual C++win32控制臺應用程序，開源點云庫pcl1.8.0。本實驗平臺為開放式平臺，適用于一切實驗環境。實驗中點云數據來源于斯坦福大學點云數據庫中bunny0和bunny045點云數據，表1為點云數量及實驗參數，表2為改進RANSAC算法和SAC-IA+ICP算法配準過程所獲得的旋轉平移矩陣。

表1 實驗參數

4.2 實驗結果與分析

從實驗結果表3可見，對于同一點云樣本且實驗參數設置相同時，使用SAC-IA+ICP配準算法，平均配準時間為5.5449s，粗配準時間為2.837s；而使用改進RANSAC算法通過對相應誤匹配點對的校正和去除，提高了運算速度和精度，所以平均配準時間縮短為4.344s，粗配準時間減少到2.043s。

表2 點云轉換仿射矩陣

表3 準確度和時間的實驗結果對比

由表4可知，使用SAC-IA+ICP配準算法，平均誤差距離為0.526cm，而使用改進RANSAC算法平均誤差距離減少到0.500cm；而且改進RANSAC算法配準過程中在x、y、z方向上旋轉角度也比傳統算法減小了不少。可見本文算法在配準過程中配準角度有所減小，配準時間有所減少。

表4 精配準旋轉角度及配準平均誤差距離對比

圖3與圖4是隨著閾值的增加，兩種算法的平均誤差距離以及精準配準時間的關系曲線圖。從圖中可以看出，閾值與配準速度先成正比關系，隨著閾值的減小，精配準時間減小，在閾值到1.3左右時達到最小，之后開始增大。但在任何閾值下，改進RANSAC算法的平均誤差距離和精準配準時間均比傳統算法要小，可見本文算法的魯棒性和配準效率均比SAC-IA+ICP算法要好。

圖3 閾值與平均誤差距離關系曲線圖

圖4 閾值與精配準時間距離關系曲線圖

圖5是隨著配準次數的增加，SAC-IA+ICP算法和本文算法在配準時間上的比較。可以看出，隨著配準迭代次數的增加，改進RANSAC算法配準所需的時間在逐步下降，而SAC-IA+ICP算法所需的時間正在加大；且從整體上看，在任何配準迭代次數下，本文算法所需時間都比所以SAC-IA+ICP少。加大配準次數是降低配準平均時間的決定因素，改進RANSAC算法的配準效率更高，而且在在多次配準下具有一定優勢。

圖5 配準次數與配準時間曲線圖

5 結語

本文通過提出一種基于交比不變的RANSAC快速點云配準算法，解決點云配準過程中經常出現的誤配準點和無關配準點問題。實驗表明，通過校正誤匹配點對和剔除無關匹配點對，改進RANSAC快速點云配準算法減少了不必要的特征點匹配過程，有效縮短配準目標在復雜場景中配準時間，成功減小配準誤差距離，使得配準的效率和精度得到有效提高。本文所闡述的算法對提高點云配準的準確性具有重要意義，同時在機器視覺運用中，可有效提高機器視覺在復雜環境下的配準效率，在逆向工程中，同樣可大大提高其重構精度。