基于改進隨機抽樣一致的點云分割算法

趙夫群， 馬 玉， 戴 翀

(1.西安財經大學信息學院， 西安 710100； 2.西北大學信息科學與技術學院， 西安 710127)

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

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

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

1 RANSAC點云分割算法

1.1 RANSAC算法原理

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

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

P=1-(1-εk)N

(1)

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

對式(1)變形，可得

(2)

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

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

1.2 RANSAC算法缺點

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

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

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

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

2 改進的RANSAC點云分割算法

改進的RANSAC算法基于RANSAC算法，改進了原始種子點的選取方式，在判斷準則中加入了對面片標準差的限制，可以有效減少偽平面的出現，并利用半徑密度信息對分割后的面片進行優化，增強了分割的精準性和邊緣準確度。

2.1 Kd樹與半徑空間密度

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

2.2 改進初始點選取

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

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

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

2.3 判斷準則的設計

設定的判斷條件為局內點的數據量和擬合平面的標準差。通常情況下，處于同一平面的點滿足以下條件：

ax+by+cz=d

(3)

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

距離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)確定的平面。

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

在實際場景當中需要盡可能地包含其中的平面，所以針對場景中平面內細節信息較多的通常采用嚴格的閾值，對于普通的平面可將閾值的范圍設置的寬泛一些。

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

2.4 面片合并

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

θ=arccos-1(n1·n2)

(5)

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

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

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

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

(3)以集合T中的點執行步驟(2)，并將得到的點加入集合T中，并進行統計。若總數小于閾值(最小面片的點數)，則認為該點為噪聲點，從點云集中剔除。

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

2.5 算法流程

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

(1)根據式(2)計算循環次數N。

(2)計算待擬合面片標準差，若標準差大于閾值δ0，則需要重新確定面片的平面參數，否則進行下一步。

(3)統計局內點數量，若大于點數閾值，則計算面片標準差，否則返回上一步。

(4)重復步驟(2)、步驟(3)N次，根據設定的判斷準則獲得最佳面片。

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

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

3 實驗結果與分析

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

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

從圖1和圖2的分割結果可見，改進的RANSAC算法能夠將相關性較低的邊緣點剔除，保留較為完整的大平面，實現良好的點云分割效果。為了驗證該改進的RANSAC算法的分割性能，對圖1(a)和圖2(a)的兩個點云模型分別采用RANSAC算法和自適應分割算法[16]進行分割，分割結果如表1所示。

圖1 改進RANSAC算法對點云模型1的分割結果

圖2 改進的RANSAC算法對點云模型2的分割結果

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

表1 分割算法對比結果

4 結論

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