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

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

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

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

1 掃描線點(diǎn)云特點(diǎn)及其二維化

1．1 掃描線點(diǎn)云特點(diǎn)

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

1．2 掃描線點(diǎn)云二維化

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

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

圖1 投影點(diǎn)的三維表達(dá)

圖2 投影點(diǎn)的二維表達(dá)

2 RANSAC算法的改進(jìn)

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

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

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

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

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

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

2．2 局外點(diǎn)的預(yù)剔除

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

圖3 局外點(diǎn)剔除示意圖

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

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

圖4 k值自適應(yīng)變化過(guò)程

2．4 多模型識(shí)別的改進(jìn)

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

綜合以上3點(diǎn)改進(jìn)，本文改進(jìn)的RANSAC算法提取圓弧點(diǎn)的算法步驟如下：

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

2）將半徑值r∈ ［R1，R2］對(duì)應(yīng)的點(diǎn)保留，將超過(guò)r閾值范圍的對(duì)應(yīng)點(diǎn)集剔除，構(gòu)成新的點(diǎn)集｛Q1，Q2，…，Qm｝。

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

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

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

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

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

3 實(shí)驗(yàn)分析

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

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

圖5 掃描點(diǎn)云

圖6 本文算法提取的41號(hào)圓弧點(diǎn)云

表2 41號(hào)掃描線的計(jì)算結(jié)果對(duì)比

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

4 結(jié)束語(yǔ)

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

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

［2］ 潘國(guó)榮，秦世偉，蔡潤(rùn)彬，等．三維激光掃描擬合平面自動(dòng)提取算法［J］．同濟(jì)大學(xué)學(xué)報(bào)：自然科學(xué)版，2009，37（9）：1250－1255．

［3］ 趙偉玲．三維點(diǎn)云的數(shù)據(jù)預(yù)處理和圓提取算法研究［D］．哈爾濱：哈爾濱工程大學(xué)，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］ 郭杰，劉建永，張有亮，等．基于掃描線自適應(yīng)角度限差法的地面點(diǎn)云濾波［J］．計(jì)算機(jī)應(yīng)用，2011，31（8）：2243－2245．

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

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