點(diǎn)云配準(zhǔn)RANSAC算法研究改進(jìn)

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

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

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

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

1 點(diǎn)云配準(zhǔn)RANSAC算法

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

其中，pt,ps就是源點(diǎn)云和目標(biāo)點(diǎn)云中的一對對應(yīng)點(diǎn)。圖1為點(diǎn)云配準(zhǔn)原理圖，點(diǎn)云一與點(diǎn)云二相互重疊，重疊部分中臨近點(diǎn)之間的變換關(guān)系就是其中的R與T旋轉(zhuǎn)平移矩陣，即兩個(gè)集中點(diǎn)的對應(yīng)關(guān)系，也是配準(zhǔn)的核心問題。

圖1 點(diǎn)云配準(zhǔn)的原理圖

RANSAC算法首先選擇少而有效的初始數(shù)據(jù)集合，再從一定容差范圍中盡可能地?cái)U(kuò)大初始數(shù)據(jù)集合。

2 交比不變模型相關(guān)定理

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

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

圖2 定理示意圖

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

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

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

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

3 基于交比不變的改進(jìn)RANSAC實(shí)現(xiàn)

將交比不變的性質(zhì)應(yīng)用在RANSAC算法中，作為采集目標(biāo)圖像局內(nèi)點(diǎn)的約束條件。針對誤匹配點(diǎn)多，計(jì)算效率低的問題，在檢測得出目標(biāo)圖像中的局內(nèi)點(diǎn)坐標(biāo)后，通過交比不變原則對目標(biāo)圖像中配準(zhǔn)錯(cuò)誤的局外點(diǎn)坐標(biāo)進(jìn)行校正，增加局內(nèi)點(diǎn)的個(gè)數(shù)，有效地解決傳統(tǒng)算法找尋最優(yōu)仿射矩陣效率低下的缺點(diǎn)。

交比不變的RANSAC改進(jìn)算法配準(zhǔn)目標(biāo)點(diǎn)云的具體步驟如下：

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

（2）通過上述參考樣本得到參考模型M，用全部數(shù)據(jù)點(diǎn)檢驗(yàn)?zāi)Ｐ蛥?shù)，得到該模型的局內(nèi)點(diǎn)數(shù)n′。

（3）預(yù)先設(shè)定誤差閾值δ，小于δ，該模型區(qū)域?yàn)槟繕?biāo)點(diǎn)云特征點(diǎn)區(qū)域；大于δ，重新計(jì)算目標(biāo)點(diǎn)云特征點(diǎn)區(qū)域。

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

源點(diǎn)云圖像中n個(gè)特征點(diǎn)坐標(biāo)間的距離矩陣為：

通過設(shè)置目標(biāo)點(diǎn)云的中心點(diǎn)坐標(biāo)與源點(diǎn)云的中心點(diǎn)坐標(biāo)之間的距離閾值，來評估配準(zhǔn)誤差，當(dāng)目標(biāo)點(diǎn)云的中心點(diǎn)坐標(biāo)與源點(diǎn)云的中心點(diǎn)坐標(biāo)之間的距離大于設(shè)定閾值時(shí)，重復(fù)上述第（3）步到第（4）步，直到滿足設(shè)定閾值。

（5）對目標(biāo)點(diǎn)云中各特征點(diǎn)的坐標(biāo)位置進(jìn)行評定。設(shè)新的配準(zhǔn)目標(biāo)點(diǎn)云中的特征點(diǎn)坐標(biāo)為各特征點(diǎn)坐標(biāo)間的距離為，計(jì)算方法同步驟（4）。則新的配準(zhǔn)目標(biāo)各特征點(diǎn)間的距離比與源點(diǎn)云各特征點(diǎn)間的距離比的比值：

若eij=0，則表示新配準(zhǔn)的目標(biāo)點(diǎn)云特征點(diǎn)定位錯(cuò)誤，需要對其進(jìn)行坐標(biāo)位置校正。

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

根據(jù)交比不變原則，可以對錯(cuò)誤配準(zhǔn)的目標(biāo)點(diǎn)云坐標(biāo)點(diǎn)進(jìn)行校正，對校正后的點(diǎn)再次進(jìn)行評定，若符合要求則進(jìn)行下一步，否則重復(fù)第（5）步操作。

（7）經(jīng)過K次重復(fù)操作之后，在校正完成后的匹配點(diǎn)對中選取6對對應(yīng)點(diǎn)，計(jì)算旋轉(zhuǎn)平移矩陣初值H。

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

（1）匹配模型中進(jìn)行匹配的數(shù)據(jù)點(diǎn)的選取采樣，即從P中取點(diǎn)集pi。

（2）兩模型中有對應(yīng)關(guān)系的匹配點(diǎn)的選擇，再在M中找出距離pi最近的對應(yīng)點(diǎn)集mi。

（3）匹配點(diǎn)對的估計(jì)誤差的選取，通過最小二乘法計(jì)算mi中最近點(diǎn)之間最小二乘意義下的配準(zhǔn)參數(shù)R和t，并計(jì)算估計(jì)誤差d：

（4）更新數(shù)據(jù)遠(yuǎn)匹配的點(diǎn)對，使用R和t對數(shù)據(jù)點(diǎn)集pi中所有點(diǎn)進(jìn)行更新，獲得更新后的數(shù)據(jù)點(diǎn)集pk。

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

（6）通過最優(yōu)化方法的重復(fù)迭代，此時(shí)可以得到兩個(gè)點(diǎn)云的配準(zhǔn)結(jié)果，從中選取6對對應(yīng)點(diǎn)，計(jì)算精確的旋轉(zhuǎn)平移矩陣H′。

4 仿真實(shí)驗(yàn)及其結(jié)果分析

4.1 仿真實(shí)驗(yàn)

本節(jié)通過對來自斯坦福大學(xué)的點(diǎn)云數(shù)據(jù)庫中的點(diǎn)云數(shù)據(jù)進(jìn)行實(shí)驗(yàn)，來評估本文算法的性能。實(shí)驗(yàn)平臺為Windows7 64位操作系統(tǒng)，Visual Studio 2013 Visual C++win32控制臺應(yīng)用程序，開源點(diǎn)云庫pcl1.8.0。本實(shí)驗(yàn)平臺為開放式平臺，適用于一切實(shí)驗(yàn)環(huán)境。實(shí)驗(yàn)中點(diǎn)云數(shù)據(jù)來源于斯坦福大學(xué)點(diǎn)云數(shù)據(jù)庫中bunny0和bunny045點(diǎn)云數(shù)據(jù)，表1為點(diǎn)云數(shù)量及實(shí)驗(yàn)參數(shù)，表2為改進(jìn)RANSAC算法和SAC-IA+ICP算法配準(zhǔn)過程所獲得的旋轉(zhuǎn)平移矩陣。

表1 實(shí)驗(yàn)參數(shù)

4.2 實(shí)驗(yàn)結(jié)果與分析

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

表2 點(diǎn)云轉(zhuǎn)換仿射矩陣

表3 準(zhǔn)確度和時(shí)間的實(shí)驗(yàn)結(jié)果對比

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

表4 精配準(zhǔn)旋轉(zhuǎn)角度及配準(zhǔn)平均誤差距離對比

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

圖3 閾值與平均誤差距離關(guān)系曲線圖

圖4 閾值與精配準(zhǔn)時(shí)間距離關(guān)系曲線圖

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

圖5 配準(zhǔn)次數(shù)與配準(zhǔn)時(shí)間曲線圖

5 結(jié)語

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