基于改進(jìn)隨機(jī)抽樣一致的點云分割算法

趙夫群， 馬 玉， 戴 翀

(1.西安財經(jīng)大學(xué)信息學(xué)院， 西安 710100； 2.西北大學(xué)信息科學(xué)與技術(shù)學(xué)院， 西安 710127)

點云是三維圖形數(shù)據(jù)的常見存在形式之一，它能夠立體高效地存儲三維物體的詳細(xì)屬性信息。點云分割是將三維空間中點云通過一系列算法，將散亂的點云數(shù)據(jù)劃分為更加連貫的子集的過程。分割后的點云數(shù)據(jù)按照點云屬性被劃分為同一組別，從而方便進(jìn)行下一步的數(shù)據(jù)處理。對三維點云模型的合理分割是后續(xù)數(shù)據(jù)分析的基礎(chǔ)，便于后續(xù)的特征提取、目標(biāo)識別、三維重建和虛擬現(xiàn)實等操作的處理。目前，點云分割已經(jīng)在逆向工程、文物虛擬復(fù)原、醫(yī)學(xué)研究等領(lǐng)域得到了廣泛的應(yīng)用[1-4]。

對于點云分割的研究，國內(nèi)外學(xué)者提出了很多的相關(guān)算法。代璐等[5]提出一種點云分割神經(jīng)網(wǎng)絡(luò)NEPN(non-equivalent point network)，可以有效解決點云分割中的非等效性，提高分割精度； 張坤等[6]利用點云形狀相關(guān)的特征參數(shù)實現(xiàn)了基于形狀分割的點云分割方法，該方法提高了點云分割的精度和速度，并且具有較強(qiáng)的穩(wěn)健性；李仁忠等[7]針對點云分割準(zhǔn)確度低的問題，提出一種基于骨架點和外部特征點的點云分割算法，可以實現(xiàn)點云表面小范圍內(nèi)凸面體的有效分割，提高分割精度；傅歡等[8]提出基于八叉樹和局部凸性的分割算法方，有效減少了分割的曲面數(shù)量同時提升了曲面質(zhì)量；周炳南等[9]基于點云庫，通過對比歐式距離點云分割算法、區(qū)域生長點云分割算法以及SegmenterLight分割算法的優(yōu)缺點，對算法的優(yōu)化提出相應(yīng)的改進(jìn)策略；Charles等[10]采用深度學(xué)習(xí)算法實現(xiàn)了三維點云的有效分類和分割，可以有效提高分割的精度；Schnabel等[11]使用隨機(jī)抽樣一致算法(RANSAC)實現(xiàn)點云分割，對于異常點云和噪聲點云具有較高的魯棒性，但必須提前指定合適的誤差閾值和迭代次數(shù)；Biosca等[12]提出一種基于模糊聚類的點云分割算法，該算法準(zhǔn)確性較高，但耗時較長；Wu等[13]提出一種基于標(biāo)簽傳播的交互式形狀分割方法，可以實現(xiàn)點云模型的快速精確分割，但對噪聲數(shù)據(jù)不敏感；Bertolotto等[14]提出一種基于改進(jìn)區(qū)域生長算法的點云的快速分割算法，可以實現(xiàn)基于語義的特征標(biāo)準(zhǔn)的精度和高適應(yīng)度分割。

對于點云分割算法的改進(jìn)，一直以來都是一個復(fù)雜的問題，雖然已有算法已經(jīng)在一定程度上提高了分割精度和分割效率，但是仍然存在一些問題。例如，算法容易受到噪聲點和異常點的影響；算法大多依賴點的法向量、曲率和顏色等信息，容易造成分割過少或分割過度的問題，從而無法獲取完整的分割模型和光滑分割邊界。針對如上問題，現(xiàn)采用一種改進(jìn)的RANSAC算法，通過改進(jìn)原始點云的選取方式、優(yōu)化分割面片的合并等方式，提高點云分割質(zhì)量和分割精度，實現(xiàn)點云精準(zhǔn)分割。

1 RANSAC點云分割算法

1.1 RANSAC算法原理

點云分割目的是將原始點云中不同的物體提取成獨立的單元，后續(xù)可以針對不同的物體特征進(jìn)行有效的處理。在點云數(shù)據(jù)獲取之前，需要對被采集的物體所處場景中有一定的先驗信息。例如：地面、墻面以及屋頂大多都是大平面，長方體往往是某種盒子。對于類似于房間這樣的復(fù)雜場景中的物體，大部分物體的形狀可以劃分到簡單的幾何形狀，這樣可以為點云分割帶來很大的便利性。對于常見的幾何形狀可以通過數(shù)學(xué)方式進(jìn)行表示，使用部分參數(shù)來表示復(fù)雜物體的特征，RANSAC算法可以從點云數(shù)據(jù)中將具有幾何特征物體分割出來。

RANSAC算法最早由Fischler等[15]在1987年共同提出，起初是作為數(shù)據(jù)處理的算法，該算法的主要作用是在源數(shù)據(jù)包含眾多噪聲的情況下提取出源數(shù)據(jù)中符合某些特征的數(shù)據(jù)。該算法可以在一定的概率區(qū)間保證最終結(jié)果的合理性，提升迭代次數(shù)可以提高概率，保證在某個置信區(qū)間內(nèi)最小抽樣數(shù)N與一個良好概率P滿足如下關(guān)系：

P=1-(1-εk)N

(1)

式(1)中：ε為局內(nèi)點和總體數(shù)據(jù)集的比值；k為模型參數(shù)的最小值；P一般取值為0.9～0.99。

對式(1)變形，可得

(2)

RANSAC算法可以將指定的數(shù)據(jù)集作為輸入，總體數(shù)據(jù)中包括局內(nèi)點、局外點和可以用于解釋數(shù)據(jù)集的參數(shù)模型，參數(shù)模型中包含部分可靠參數(shù)。RANSAC算法通過迭代的方式每次隨機(jī)選擇一部分?jǐn)?shù)據(jù)集作為參數(shù)模型的參數(shù)，被選取的子數(shù)據(jù)集為局內(nèi)點，通過下面5個步驟完成模型驗證：①有被選取的局內(nèi)點適用于該參數(shù)模型，即可以通過該局內(nèi)點計算出參數(shù)模型中其他的未知參數(shù)；②將其他數(shù)據(jù)擬合到步驟①中得出的模型中，若其中某些點適用于該模型，則認(rèn)為這些符合條件的點也為局內(nèi)點；③如果有大量的子數(shù)據(jù)集被認(rèn)定成為局內(nèi)點，則說明此參數(shù)模型合理；④將所有局內(nèi)點作為輸入重新擬合參數(shù)模型，因為參數(shù)模型只被初始選取的局內(nèi)點擬合過；⑤最終通過估計獲取的局內(nèi)點的數(shù)量和參數(shù)模型的誤差來改進(jìn)模型。

現(xiàn)將通過改進(jìn)RANSAC算法的初始點的選取方式，并利用半徑空間密度信息和連通性對分割平面進(jìn)行優(yōu)化，使原算法對平面分割的準(zhǔn)確性和對邊緣位置的分割效果得到提高。

1.2 RANSAC算法缺點

RANSAC算法用于室內(nèi)平面場景下的點云分割時存在如下缺點。

(1)算法效率。根據(jù)RANSAC算法的原理當(dāng)處理數(shù)據(jù)集比較大的室內(nèi)平面場景時，若對場景中的點云數(shù)據(jù)進(jìn)行簡單的提取，那么在某次具體的搜索中，隨著最小抽樣數(shù)N的增加，導(dǎo)致合理概率P降低，算法的耗時增加。

(2)點云錯分。使用RANSAC算法只能提取出點云空間中的平面，這與真實場景下的平面有很大不同，點云空間中的平面不會體現(xiàn)出平面邊界，在多平面的場景中可能會出現(xiàn)點云錯分割現(xiàn)象。

(3)分割尺度。RANSAC算法在計算過程中用一個固定不變的閾值δ，那么會導(dǎo)致這樣的問題：若采用相對較大的閾值δ，當(dāng)小于此值的分割平面會達(dá)不到閾值無法提取出來；若采用相對較大閾值δ時，當(dāng)大于此值的分割平面在迭代過程中會因為多次達(dá)到閾值條件，導(dǎo)致平面多次分割，造成完整的平面破損。

2 改進(jìn)的RANSAC點云分割算法

改進(jìn)的RANSAC算法基于RANSAC算法，改進(jìn)了原始種子點的選取方式，在判斷準(zhǔn)則中加入了對面片標(biāo)準(zhǔn)差的限制，可以有效減少偽平面的出現(xiàn)，并利用半徑密度信息對分割后的面片進(jìn)行優(yōu)化，增強(qiáng)了分割的精準(zhǔn)性和邊緣準(zhǔn)確度。

2.1 Kd樹與半徑空間密度

Kd(K-dimensional)樹主要用于分割k維數(shù)據(jù)空間的數(shù)據(jù)結(jié)構(gòu)，主要應(yīng)用場景是搜索k維空間的多維數(shù)據(jù)。與傳統(tǒng)二叉搜索樹不同的地方在于Kd樹的每個節(jié)點表示的是k維空間的點，而且Kd樹的每一層都可以進(jìn)行決策分析。Kd樹也繼承了二叉搜索樹的優(yōu)點可以精確快速的查找某點，可以實現(xiàn)在某個半徑空間鄰域點的高效查找，在三維空間當(dāng)中，半徑空間密度是指以該點為中心、R為半徑的空間球體所包含點云數(shù)據(jù)的個數(shù)。

2.2 改進(jìn)初始點選取

在點云數(shù)據(jù)中，兩個點云的距離(空間距離)越靠近，那么這兩個點云屬于同一個物體的概率也就越大。因此，將使用改進(jìn)選取初始點的方式，在同樣的采集次數(shù)下提高了對平面分割的可信度。

對復(fù)雜場景中大平面進(jìn)行點云分割是，不同的平面對應(yīng)不相同的平面方程，對于三維空間的方程可以通過3個不共線的點來進(jìn)行標(biāo)識，所以式(1)、式(2)中的k=3。傳統(tǒng)的RANSAC算法選取初始點的方式是從原始數(shù)據(jù)集當(dāng)中隨機(jī)選取3個點作為基準(zhǔn)點來獲取平面方程參數(shù)的初始值，然后通過獲取到的初始值來尋找其他局內(nèi)點，這樣得到的模型大多都不會滿足判斷準(zhǔn)則，因此在進(jìn)行同樣次數(shù)的采樣下滿足平面模型的數(shù)據(jù)集也被減少了，最優(yōu)模型的概率也會隨之降低。

采取的方式是隨機(jī)在數(shù)據(jù)集中選取一個點，通過Kd樹建立索引，然后查找以該點R半徑以內(nèi)的點，將查找到的所有點采用最小二乘法來擬合，根據(jù)擬合的結(jié)果來確定平面參數(shù)的初始值。針對最小二乘法的結(jié)果需要設(shè)置閾值進(jìn)行限制，設(shè)閾值為δ0，若擬合結(jié)果大于δ0，說明以該點R半徑范圍內(nèi)的點云分布不規(guī)律，差異較大，在同一平面的概率較小，拋棄該值，并以同樣的方式來選取直至初始值的確定。通過這種改進(jìn)后的方式可以在數(shù)據(jù)處理的開始剔除異常信息過大的點，減少異常點的影響，提供了數(shù)據(jù)處理效率，在相同采集次數(shù)下提高了獲得模型的概率。

2.3 判斷準(zhǔn)則的設(shè)計

設(shè)定的判斷條件為局內(nèi)點的數(shù)據(jù)量和擬合平面的標(biāo)準(zhǔn)差。通常情況下，處于同一平面的點滿足以下條件：

ax+by+cz=d

(3)

式(3)中：(x,y,z)為平面點的空間坐標(biāo)；(a,b,c)為平面法向量并且滿足a2+b2+c2=1；d為坐標(biāo)原點到平面的距離。

距離d采用P(x,y,z)到平面PL(a,b,c,d)的歐氏距離計算，計算式為

d(P,PL)=|ax+by+cz-d|

(4)

式(4)中：P(x,y,z)為(x,y,z)確定的平面；PL(a,b,c,d)為(a,b,c)確定的平面。

選取的局內(nèi)點在平面內(nèi)，那么理論上到分割平面的距離應(yīng)該為零，但是因為在點云空間中點云數(shù)據(jù)存在誤差導(dǎo)致平面不會是絕對的平面而是由多個點在一定范圍內(nèi)組成的擬合平面，需要給定一定的閾值δ0作為判斷選取的點是否在平面內(nèi)，閾值δ0過小會導(dǎo)致平面過度分割，造成平面破損，過大則會增加平面腐蝕作用，無法將平面分割出來。

在實際場景當(dāng)中需要盡可能地包含其中的平面，所以針對場景中平面內(nèi)細(xì)節(jié)信息較多的通常采用嚴(yán)格的閾值，對于普通的平面可將閾值的范圍設(shè)置的寬泛一些。

若選取的點到平面的距離小于δ0，則認(rèn)為平面該點為平面模型的局內(nèi)點。計算點云數(shù)據(jù)中局內(nèi)點的數(shù)量，若大于閾值Pmin，則說明平面分割完成。判斷一個平面是否分割的完成的條件為點云數(shù)據(jù)中局內(nèi)點的數(shù)量和平面的標(biāo)準(zhǔn)差，所以一個完整的分割平面需要平面使用標(biāo)準(zhǔn)差進(jìn)行約束。

2.4 面片合并

按照以上準(zhǔn)則點云分割之后，可能會存在這樣的情況：在點云空間中一些面片可能有多個層次但是總體可視為同一個平面，所以需要將這部分面片進(jìn)行合并和優(yōu)化。面片合并的條件為：空間中近似面片的法向量夾角θ一般比較小，可以通過θ值來確定是否進(jìn)行面片的合并。θ的計算式為

θ=arccos-1(n1·n2)

(5)

式(5)中：n1、n2分別為兩個面片的法向量。

僅使用θ來判斷合并可能會使得具有相似法向量但距離相差較大的面片合并(類似于平行平面)，且分割后的面片由多個面片組成。對此問題，本文研究使用的算法如下。

(1)首先在分割后的面片建立Kd樹索引，從中選取初始點P0。

(2)判斷面片R半徑的密度信息。若R大于閾值Rnum，將在R中的點添加到集合T={P1,P2,…,Pk}當(dāng)中，否則將P0從索引中刪除，并重新選擇P0進(jìn)行以上判斷。

(3)以集合T中的點執(zhí)行步驟(2)，并將得到的點加入集合T中，并進(jìn)行統(tǒng)計。若總數(shù)小于閾值(最小面片的點數(shù))，則認(rèn)為該點為噪聲點，從點云集中剔除。

(4)重復(fù)執(zhí)行以上步驟，直至將面片中所有點判斷完為止。

2.5 算法流程

本文改進(jìn)RANSAC算法對場景大平面點云分割時需要進(jìn)行反復(fù)迭代，每次迭代會將已經(jīng)分割過的點從原始數(shù)據(jù)集剔除，直至模型點數(shù)小于給定閾值Nmin，具體流程如下。

(1)根據(jù)式(2)計算循環(huán)次數(shù)N。

(2)計算待擬合面片標(biāo)準(zhǔn)差，若標(biāo)準(zhǔn)差大于閾值δ0，則需要重新確定面片的平面參數(shù)，否則進(jìn)行下一步。

(3)統(tǒng)計局內(nèi)點數(shù)量，若大于點數(shù)閾值，則計算面片標(biāo)準(zhǔn)差，否則返回上一步。

(4)重復(fù)步驟(2)、步驟(3)N次，根據(jù)設(shè)定的判斷準(zhǔn)則獲得最佳面片。

(5)重復(fù)步驟(1)～步驟(4)，直至模型點數(shù)小于給定閾值Nmin。

(6)根據(jù)優(yōu)化策略對多層次面片進(jìn)行合并和優(yōu)化，獲得最后分割平面。

3 實驗結(jié)果與分析

實驗在Windows 10環(huán)境下，采用點云庫(PCL)框架和C++語言作為開發(fā)工具，利用Microsoft Visual studio 2015運行得到。利用提出的該改進(jìn)RANSAC算法，將兩個原始點云模型進(jìn)行分割，分割結(jié)果如圖1和圖2所示。

在分割中，設(shè)定平面的判斷閾值δ0=0.09 m，半徑密度閾值Rnum=8。利用式(2)設(shè)定循環(huán)次數(shù)N的取值，0.9≤P≤0.99。對于改進(jìn)RANSAC算法，其主要影響因素為循環(huán)次數(shù)N和非分割平面模型的數(shù)量值Nmin，二者的關(guān)系與完整的分割面積有關(guān)，所以當(dāng)確定好完整的分割平面即可實現(xiàn)面片分割。

從圖1和圖2的分割結(jié)果可見，改進(jìn)的RANSAC算法能夠?qū)⑾嚓P(guān)性較低的邊緣點剔除，保留較為完整的大平面，實現(xiàn)良好的點云分割效果。為了驗證該改進(jìn)的RANSAC算法的分割性能，對圖1(a)和圖2(a)的兩個點云模型分別采用RANSAC算法和自適應(yīng)分割算法[16]進(jìn)行分割，分割結(jié)果如表1所示。

圖1 改進(jìn)RANSAC算法對點云模型1的分割結(jié)果

圖2 改進(jìn)的RANSAC算法對點云模型2的分割結(jié)果

從表1可以看出，對于同一原始點云，改進(jìn)的RANSAC算法對于分割后平面的邊緣更加精準(zhǔn)，同時還可以在保留完整的面片的同時剔除了不相關(guān)的部分點云，具有良好的點云分割結(jié)果。這是由于RANSAC算法只能在一定的概率區(qū)間內(nèi)保證分割結(jié)果的合理性，對室內(nèi)平面場景的分割效率較低，容易出現(xiàn)點云錯分的現(xiàn)象；自適應(yīng)分割算法根據(jù)提取的特征自動選擇種子點，并采用改進(jìn)的區(qū)域生長算法對種子點進(jìn)行分割，該算法可以解決與區(qū)域增長算法相關(guān)的不一致或過度分割等問題，不需要用戶干預(yù)，具有較好的魯棒性，但是該算法對噪聲不夠敏感；而本文提出的改進(jìn)RANSAC算法利用半徑空間密度重新定義初始點的選取方式，通過多次迭代來剔除無特征點，在實現(xiàn)點云分割的同時可以有效去除噪聲點，因此改進(jìn)RANSAC算法的點云特征提取數(shù)據(jù)量較大，面片分割的準(zhǔn)確性較高。

表1 分割算法對比結(jié)果

4 結(jié)論

點云分割是三維重建的關(guān)鍵技術(shù)之一，從三維視圖中分割點云可以方便地進(jìn)行逆向工程處理。主要針對三維點云數(shù)據(jù)分割算法進(jìn)行研究，基于RANSAC算法在點云分割中存在的問題，通過改進(jìn)初始點數(shù)據(jù)的選取方式和判斷準(zhǔn)則，使RANSAC算法對點云數(shù)據(jù)分割的準(zhǔn)確度提高。并通過將改進(jìn)RANSAC算法與RANSAC算法和自適應(yīng)分割算法進(jìn)行實驗對比，證明改進(jìn)RANSAC算法的良好分割效果。在今后的研究中，要進(jìn)一步對閾值設(shè)置進(jìn)行優(yōu)化，實現(xiàn)基于點云密度信息的自適應(yīng)閾值選取，減少人工計算量，進(jìn)一步提高算法的效率和應(yīng)用范圍。