一種改進的RANSAC算法提取多模型圓弧特征點云

許燁璋，王鑫森，鄭德華，謝 波，王春林

（1．河海大學 地球科學與工程學院，江蘇 南京 210098；2．天津市勘察院，天津 300191）

目前點云數(shù)據(jù)的特征提取大多是直接在三維空間中進行的［1］。特征提取算法基本可分為基于邊界的算法和基于面域的算法兩大類，另外還有綜合使用兩種方法的混合算法［2］。前者主要是提取點云數(shù)據(jù)表面形態(tài)變化劇烈的點，通常利用法矢、曲率等微分幾何變量的突變來提取特征。這種方法對噪聲比較敏感，故抗差性較弱。后者主要在于尋找點云數(shù)據(jù)中具有相同屬性的點集，構造出可靠的生長區(qū)域進行生長，最終實現(xiàn)分割和特征提取。這類方法主要有RANSAC（隨機抽樣一致算法）、M估計、最小中值算法、遺傳算法和霍夫變換等［3］。這些方法本身具有良好的抗差估計性能，因此在提取特征時能有效抵御噪聲。

RANSAC（Rando m Sample Consensus）算法是1981年由Fischler和Bolles［4］最先提出。該方法能夠在含有大量粗差點的情況下估計出正確的模型，較經(jīng)典的最小二乘法具有明顯優(yōu)勢。但隨著局外點的增多，算法的迭代次數(shù)會呈現(xiàn)指數(shù)式增長，算法耗時急劇增加。另外RANSAC算法只能實現(xiàn)單個模型的識別。本文提出一種改進的RANSAC算法，能夠有效地克服傳統(tǒng)RANSAC的不足。

1 掃描線點云特點及其二維化

1．1 掃描線點云特點

掃描線式點云由一組掃描線組成，每條掃描線點云數(shù)據(jù)是按照掃描儀與激光腳點的仰角大小依次存儲的[5]。本文采用的數(shù)據(jù)為Tri mble GX200三維激光掃描儀采集的掃描線式點云數(shù)據(jù)，每條掃描線都是掃描光刀平面與目標物體的交線。由于本文所掃描的對象為球體目標，因此所要提取的圓弧特征點云都位于每條掃描線上。同一條掃描線中的掃描點基本共面，對于單獨一條掃描線數(shù)據(jù)，完全可以在二維平面內(nèi)進行特征點的提取，這樣就可以把復雜的三維點云的問題簡化到二維平面內(nèi)處理［6］，故本文以掃描線為單位進行圓弧點云的提取。

1．2 掃描線點云二維化

由于各項誤差的存在，每條掃描線上的點云不可能都嚴格位于各自的光刀平面內(nèi)，而是以微小的距離分布在光刀平面的兩側。因此將掃描線點云二維化至其對應的光刀平面，首先須根據(jù)掃描線點云擬合計算出對應的光刀平面方程式。本文采用特征值法求取平面方程式，具體解求過程不再詳述。擬合平面求出后將對應的三維點云投影上去，完成點云的投影。

經(jīng)過投影后點空間三維點雖已全部位于平面上，但其坐標仍為（Ind，X，Y，Z）（其中Ind為索引值）的三維形式，須將這些點轉化為（Ind，X，Y）的二維形式，圖1所示為某擬合平面α1內(nèi)的投影點集（P0，P1，…，Pn）在三維直角坐標系中；圖2所示為所要得到的二維坐標。其轉換過程為：①以P1點為原點，P1Pn連線的方向矢量為X 軸，以過點P1并垂直于X軸成右手系的向量作為Y軸。②計算其他點Pi到P1點的距離d，以及向量與之間的夾角γ。③根據(jù)d和γ，將二維極坐標向二維直角坐標轉換，求取Pi點的直角坐標（X，Y）。

圖1 投影點的三維表達

圖2 投影點的二維表達

2 RANSAC算法的改進

2．1 RANSAC算法原理及其不足

RANSAC算法是通過不斷地選擇數(shù)據(jù)集中的一組隨機子集來估計待定模型。選取的點集假設為局內(nèi)點即符合模型的數(shù)據(jù)點，不符合模型的點稱為局外點。每次用選定的隨機子集去估計一個待估模型，然后用該模型去測試數(shù)據(jù)集中其他的點，符合該模型的點歸為局內(nèi)點，當局內(nèi)點數(shù)量達到設定要求時就認為該模型合理，并且將局內(nèi)點歸納進來重新估算模型。如果局內(nèi)點數(shù)量不夠，則認為該模型估算的不正確，此時舍棄原模型，重新在數(shù)據(jù)集中隨機抽取一個子集來估算模型。每次估算的模型要么因為局內(nèi)點數(shù)量充足而重新生長，要么由于局內(nèi)點數(shù)量不足而遭到舍棄［7］。最終以局內(nèi)點和模型的錯誤率來評價模型估算的精度。

雖然傳統(tǒng)RANSAC算法能從含有大量局外點的數(shù)據(jù)集中估算出高精度的模型參數(shù)，但其迭代次數(shù)沒有上限。如果設置了迭代上限，可能會導致抽樣不充分從而計算出錯誤的模型，如果不控制迭代次數(shù)，便會造成算法效率低下，難以收斂。RANSAC算法的另一個不足是它只能在特定的數(shù)據(jù)集中估計出一個模型，對于數(shù)據(jù)集中存在兩個或者兩個以上的模型，RANSAC不能識別。RANSAC算法輸入?yún)?shù)見表1。

表1 RANSAC算法輸入?yún)?shù)

設n個點全部為局內(nèi)點的概率為P，點集的總點數(shù)為N，所有局外點數(shù)為Nt，則隨機選取一個點為局外點的概率為W ，且W ＝Nt／N。n個點全部為局內(nèi)點的概率又可以表示為（1－W）n，1－（1－W）n表示n個點中至少有一個為局外點的概率，則（1－（1－W）n）k表示永遠都取不到n個點全部都為局內(nèi)點的概率，它應該和1－P相等，即1－P＝（1－（1－W）n）k，對兩邊取對數(shù)即可得出迭代時取略大于k的值即可。

由式（1）可以看出，在n和P固定的情況下，局外點率W 越大，迭代次數(shù)k也就越大，算法效率越低下。因此為了減少迭代次數(shù)，提高算法效率，就必須降低局外點所占的比例并且根據(jù)每次數(shù)據(jù)的調(diào)整對k值進行自適應調(diào)整。

2．2 局外點的預剔除

本文提取的圓弧點云為球面圓弧點云，為掃描光刀平面在球面上截取的圓，其直徑必然小于或等于球直徑（球面被光刀面所截的圓截面中，通過球直徑的截面最大），因此那些直徑大于球直徑的數(shù)據(jù)點即可認為局外點。利用這一特性本文以相鄰的3個點為一組遍歷整條掃描線，計算每組數(shù)據(jù)對應圓的直徑，將直徑大于設定閾值的數(shù)據(jù)剔除，從而達到降低外點率的目的。圖3為局外點剔除示意圖。

圖3 局外點剔除示意圖

2．3 k值的自適應調(diào)整

隨著迭代次數(shù)的增加，內(nèi)點被不斷地增加到估算模型的點集中來，即在迭代過程中內(nèi)點率不斷增加，相應的外點率在不斷減小，則根據(jù)式（1）迭代次數(shù)k值也在隨之減小。本文算法在開始計算時將k值設置為一個較大的值，然后在每次迭代時根據(jù)外點率重新計算k的值使其趨于一個合理的值完成迭代。為了驗證k值自適應調(diào)整的效果，事先針對迭代次數(shù)k值做了一組測試。將k的初始值設為14 000，開始計算后每隔10 s記錄一次k值，從圖4可以看出k值在前40 s中數(shù)值下降顯著，最終在第90 s處自適應停止，穩(wěn)定到55 s左右，表明本文的自適應處理能夠取到良好的效果。

圖4 k值自適應變化過程

2．4 多模型識別的改進

上文提到RANSAC算法的另一大不足就是只能對待估點集中的一個模型進行識別，對包含兩個及其以上的模型就無法適用。為解決這一問題，本文采用分次識別的方法，即將第一次識別出的模型所對應的點集剔除出二維點集后再進行下一個模型的識別，按照這種流程直到滿足某種條件為止。

綜合以上3點改進，本文改進的RANSAC算法提取圓弧點的算法步驟如下：

1）選定一組已經(jīng)二維化后的掃描線點集｛P1，P2，…，Pn｝，將相鄰的3個｛Pi，Pi＋1，Pi＋2｜i∈ ［1，n－2］｝計算構成圓的半徑值r，按順序無重復地遍歷點集。

2）將半徑值r∈ ［R1，R2］對應的點保留，將超過r閾值范圍的對應點集剔除，構成新的點集｛Q1，Q2，…，Qm｝。

3）將迭代次數(shù)k設置為一個足夠大的數(shù)值，隨機抽取一個包含3個點的樣本，計算其模型參數(shù)Modelk，即圓心坐標及半徑 （xo，yo，r）k。

4）再次檢驗樣本點計算的r值是否符合r∈［R1，R2］，若是，則進入下一步，否則退出本次循環(huán)，轉回到3）。

5）遍歷點集｛Q1，Q2，…，Qm｝，判斷每加入一個點后圓擬合余差σ0是否符合閾值來找出所有符合本模型的點，并判斷內(nèi)點數(shù)是否達到設定的閾值Nu m，若達到則記錄本模型參數(shù)Modelk，σ0和對應的內(nèi)點集Inliersk，并根據(jù)式（1）計算新的外點率W和對應的新的迭代次數(shù)k，其中N取點集｛Q1，Q2，…，Qm｝的個數(shù)。

6）重復迭代過程3）～5），以內(nèi)點數(shù)更多的模型Modelk＋1作為更好的模型替換上一個模型Modelk，最終得到一個置信概率下的模型并保存相應內(nèi)點點集。

7）將6）中得到的模型對應的內(nèi)點從點集｛Q1，Q2，…，Qm｝中剔除，重復3）～6）完成下一模型選取。

3 實驗分析

實驗選取3個排列在一起大小不等的3個球體，采用Tri mble GX200型掃描儀進行掃描，經(jīng)過去噪等簡單處理后得到16 230個數(shù)據(jù)點，134個切片。圖5所示為掃描點云。

分別用RANSAC算法和本文改進的RANSAC算法提取其中的圓弧點。對RANSAC算法中迭代次數(shù)k分別取4個不同的值進行測試，由于3個掃描球體的半徑最大為200 mm，最小為41 mm，考慮到一定的容差，將預剔除閾值設置為10～500 mm，超過此范圍的點作為外點剔除掉。經(jīng)過多次實驗，兩種算法中模型擬合余差σ0取0．8 mm，最小內(nèi)點數(shù)Nu m取8。最終本實驗共提取圓弧總數(shù)319條，以41號切片數(shù)據(jù)為例，包含數(shù)據(jù)點109個，實際圓弧數(shù)為3條。本文改進的RANSAC算法所提取的圓弧如圖6所示，兩種算法效果對比見表2。

圖5 掃描點云

圖6 本文算法提取的41號圓弧點云

表2 41號掃描線的計算結果對比

從表2和圖6可以看出，傳統(tǒng)的RANSAC算法當?shù)螖?shù)k分別取較小值500，2 000，8 000時，算法最終的擬合結果為失敗、錯誤和遺漏。這就充分證明了對于傳統(tǒng)RANSAC算法，迭代次數(shù)如果設置得太小就無法估算出模型。當k值增加到較大值12 000時，傳統(tǒng)算法僅能夠識別出1條圓弧并且耗時較大。這充分顯示了傳統(tǒng)RANSAC算法計算效率低下且僅能估計單一模型的缺點。本文改進的RANSAC算法不僅將3條圓弧點云有效提取，而且每條圓弧提取的k值最終都以一個較小的值固定下來，算法耗時為最少。

4 結束語

本文利用了掃描線式點云數(shù)據(jù)的特點，先以掃描線為單位將三維點云進行二維化處理，降低了數(shù)據(jù)處理的復雜度。在分析傳統(tǒng)RANSAC的基礎上，針對球面圓弧點云數(shù)據(jù)的特點，提出了改進的RANSAC算法的流程，對局外點進行的預剔除，從總體上降低了迭代次數(shù)。對迭代次數(shù)進行的自適應調(diào)整使迭代次數(shù)能夠根據(jù)數(shù)據(jù)的變化及時調(diào)整到合理的較小值。分次識別法則實現(xiàn)了多個圓弧模型的提取。實驗證明，本文改進的RANSAC算法能夠有效克服傳統(tǒng)RANSAC算法的不足，為復雜場景下多模型特征點云的提取提供了一種思路。但本文處理的點云數(shù)據(jù)僅為掃描線式，所提取的模型也僅僅是圓弧模型，對于其他格式的點云數(shù)據(jù)和其他性質(zhì)模型的提取還有待進一步研究。

［1］ WEINKAUF T，GNT HER D．Separatrix persistence：Extraction of salient edges on surfaces using topological met hods［M］．Co mputer Graphics，2009．

［2］ 潘國榮，秦世偉，蔡潤彬，等．三維激光掃描擬合平面自動提取算法［J］．同濟大學學報：自然科學版，2009，37（9）：1250－1255．

［3］ 趙偉玲．三維點云的數(shù)據(jù)預處理和圓提取算法研究［D］．哈爾濱：哈爾濱工程大學，2008．

［4］ FISCHLER M A，BOLLES R C．Random sample consensus：a paradig m for model fitting wit h applications to i mage analysis and automated cartography［J］．Grap hics and Image Processing，1981，24（6）：381－395．

［5］ 郭杰，劉建永，張有亮，等．基于掃描線自適應角度限差法的地面點云濾波［J］．計算機應用，2011，31（8）：2243－2245．

［6］ 潘國榮，谷川，王穗輝，等．三維激光掃描擬合直線自動提取算法研究［J］．大地測量與地球動力學，2009，29（1）：57－63．

［7］ 蔡潤彬．地面激光掃描數(shù)據(jù)后處理若干關鍵技術研究［D］．上海：同濟大學，2008．