基于區(qū)域增長方法的點云分割

介 維,張京軍,,高瑞貞

1.河北工程大學 信息與電氣工程學院,河北 邯鄲 056038

2.河北工程大學 機械與裝備工程學院,河北 邯鄲 056038

當前，已經有很多對二維圖像分割與識別方面的研究，圖像在采集過程中因受到環(huán)境因素的影響，從而影響圖片質量，導致分割效果不理想。隨著信息技術的發(fā)展，三維點云模型已逐漸成為國內外的研究熱點[1,2]，并且在眾多領域都有著廣闊的應用前景，如多目視覺下的自主移動機器人、醫(yī)療行業(yè)、視頻游戲產業(yè)、建筑業(yè)等。其數據的采集也越來越方便，精度也越來越高。分割作為點云數據處理的主要步驟，為后續(xù)的特征提取提供了重要的信息，也是實現物體識別的必要環(huán)節(jié)。

目前常用的點云分割方法有：區(qū)域增長[3]、特征聚類[4]和模型擬合[5]。其中區(qū)域增長方法因其精確的分割效果而被廣泛使用[6]。1976 年，區(qū)域增長是由Zucker 最先提出，最早被用在二維圖像處理方面，其優(yōu)點是計算量簡單且高效，不足之處是算法簡單易于實現，曲率分布不均勻，且對噪聲比較敏感，容易造成過分割或者欠分割等問題[7]。近年來，國內外一些學者對區(qū)域增長該算法進行了改進，將其運用在三維點云分割中，把點云的法向量、幾何特征以及曲率作為判斷標準來對點云數據進行處理。肖曉明、馬智等[8]針對道路區(qū)域的分割問題，提出基于聚類分析的自適應區(qū)域增長準則算法，該算法可以消除車道線對其分割的干擾，但適用范圍具有局限性；Klasing K,et al.[9]用點云距離算法實現對象的分割，但是在物體單一情況下分割效果良好，若物體情況復雜則不能得到理想的分割效果；Angelina S,et al.[10]使用閾值和遺傳算法對現有的區(qū)域增長算法進行改進，分割效率提高，但邊界保持性比較差；Chen J,et al.[11]運用分解協(xié)差矩陣的方法，但該方法一般用于提取規(guī)則建筑物的平面，且成本比較高；李娜等[12]利用Ransac 算法通過對點云r 半徑密度的計算最終提取建筑物的表面特征，該方法不能實現點云的快速處理，容易形成誤差累積。

目前對于場景的點云分割研究方法仍然存在技術性問題，雖然最先進的方法在基準性能方面逐步提高，但它們變得也越來越復雜，例如通過合并分類器鏈，這需要對大型手動注釋數據集進行培訓。作為替代方案，提出了將3D 點云分割作為對象部分，該算法首先將場景數據進行過分割形成依附物體目標邊界的超體素，再進行區(qū)域增長算法，進行種子體素的篩選，最后形成精確的分割區(qū)域。該算法改善了分割，可以直接實現而且不需要訓練數據，同時產生較好的分割結果。

1 點云分割

將點云按照顏色、空間位置進行有意義的分割，將其分割成多個小塊，分割之后顯示較亂，在對物體進行分割時，其優(yōu)點是不需要用深度學習方法訓練點云分割的框架，可以直接進行分割，且分割效果不錯。點云數據通常以X、Y、Z 的三維坐標形式表示，主要是指用于表示對象外部形狀的三維坐標系的一系列矢量。大多數的點云數據一般由3D 掃描設備生成，比如飛行時間相機、立體相機、激光掃描、雷達掃描等等，這些設備以自動化方式測量對象表面上的大量點的信息，然后用數據文件輸出點云數據。或者用雙目相機拍攝兩幅圖像，根據立體視覺的三維測距原理獲得深度信息，進而獲取視差圖[13]，對場景進行三維重建[14]，然后經過格式轉換形成點云數據再對其進行分割。

在本文中，算法包括兩個部分，第一部分是基于超體聚類的過分割，第二部分是在其基礎上用點云區(qū)域增長算法進行分割。在二維圖像中，其概念即像素，體素即為三維概念。超體是一種集合，集合的元素是體，其本質就是一個個的小方塊。在對點云進行過分割時，即把場景點云化成很多小塊，將顏色、紋理相似的部分分割到一起，以方便后續(xù)的識別工作。

2 過程與分析

2.1 過分割算法流程與體素化

點云數據的過分割是將初始的點云數據聚類得到固定大小的點云簇，用作后續(xù)區(qū)域增長的輸入數據，以降低計算復雜度，消除噪聲和雜波，提高分割的精度。其基本的過分割處理的過程：

圖1 過分割算法的基本流程Fig.1 Basic flow of the over-segmentation algorithm

三維信息采集的原始數據中包含很多冗余信息，有著散亂稀疏、密度不均勻且數據海量的特點。若直接對其進行處理會受到信息的干擾，導致分割邊界不明確、分割區(qū)域表面粗糙，為了避免這種情況的發(fā)生，應對采集的點云數據進行體素化處理。目前，三維激光掃描系統(tǒng)快速發(fā)展，由于研究的需要，往往需要把不具有空間長度信息的點數據轉為具有三維空間信息的立方體，如何使用軟件進行快速、有效的點云體素化轉化便顯得格外重要。雖然使用MATLAB 等軟件可以進行編程完成點云體素化轉化的過程，但其過程往往比較繁瑣，給點云數據快速體素化處理造成一定的困難。算法中首先對采集到的點云數據做體素化處理得到體素云后，然后利用網格化來篩選種子體素，為后續(xù)的聚類算法初始化，結合體素數據的特征屬性，對體素聚類形成光滑并粘附在物體邊界上的超體素。

超體聚類是一種特殊的區(qū)域增長算法，區(qū)別于無限制的生長，其過程與結晶類似。結晶的過程實際上是不斷吸納類似的粒子。為了確保通過聚類體素云獲得的超體素不跨越空間斷開的邊界，考慮兩個體素之間的26 鄰接關系來構建體素云數據的鄰接圖，用Voxel Cloud Connectivity Segmentation(VCCS)方法[15]把3D 點云數據過分割成超體素晶塊，用來創(chuàng)造物體表面的鄰接圖。首先，超體聚類需要布置有規(guī)律的區(qū)域生長晶核，晶核均勻分布在空間中，當全部晶核同時開始生長并填滿整個空間時，就會使物體具有晶體結構。類似的概念是不精確的，我們可以用如下公式表示：

式（1）為類似的公式，公式中顏色上的差異用DC來表示，法線的差異用Dn來表示，距離上的差異用DS來表示。W*表示一系列的權重，結晶的形狀用其控制。結晶的順序在層次上是同時生長的，但計算機在計算時有先后之分，通過遍歷體素空間的26 鄰域關系可以構建相應的鄰接關系圖，依據逐層向外遍歷的原則可以得到鄰接關系圖的優(yōu)先遍歷順序，下圖中的箭頭表示體素數據的遍歷順序：

圖2 體素的鄰接關系及遍歷順序Fig.2 Voxel adjacencies and traversal order

2.2 幾何特征及種子體素的篩選

體素化過程完成后，用網格化操作來對種子體素進行篩選，實現聚類算法的初始化操作（圖3）。

Rpatch是進行網格化處理時的分辨率，Rsearch是種子體素的鄰域半徑，初始種子體素一般選擇網格內最接近中心的體素，選擇后要進行過濾去噪處理，對體素空間下孤立的種子點進行刪除，然后對物體表面上的種子體素進行保留。圖中與虛線圓相交的區(qū)域表示物體表面與搜索范圍內相交區(qū)域體素數目小于固定閾值的種子體素。圖中的背景虛線網格表示體素化處理，需要注意的是Rpatch>>Rsearch。在右側虛線圓種子體素的搜索范圍內，與物體表面相交的體素數據只有兩個，小于預先設置的閾值，所以上圖右方虛線圓內的種子體素為空間內的孤立種子點，應對其進行刪除。

在對種子體素進行選擇過濾過程后，需要結合體素數據的幾何特征、空間距離、邊緣屬性來衡量體素之間的相似性。中心點P的幾何特征FPFH計算方式如下：

上式（2）中的SPFH表示簡化的特征直方圖，wk代表權值，權值可以近似用查詢點離鄰近點的空間距離來表示，也可以用另一種度量來表示。已知點云P中有n個點，k表示在計算每個點的特征向量時考慮的鄰域數量，如圖4 表示的是以點P為中心的k鄰域影響范圍：

圖3 網格化和體素化過程中不同距離和參數示意圖Fig.3 Schematic diagram of different distances and parameters during meshing and voxelization

圖4 以點P 為中心的k 鄰域影響范圍圖Fig.4 k neighborhood influence range map centered on point P

從上述圖中可以看出，對于一個已知查詢點，首先利用中心點和它的鄰域點之間來估計它的SPFH值，如圖中與Pq的連線所示，顯然這樣比PFH的標準計算少了與鄰域點之間的互聯(lián)。在三維體素數據中，一般邊緣信息對應著三維物體中曲面彎曲程度較大的區(qū)域，物體表面的彎曲程度可以用曲率來表示，一般在物理意義上，曲率也可以用殘差值來表示，通過用曲率來表示三維體素數據的邊界屬性，來確保得到的超體素可以依附于物體的邊緣，使其具有精確的分割邊界。

在對體素數據進行過分割處理時采取的是流約束聚類算法，最后得到依附于物體目標邊界且光滑的超體素，該聚類算法的過程總結為：從最接近聚類中心的體素開始，逐層向外搜索相鄰的體素，并計算從這些體素到超體素中心的距離。如果距離是最小的，則標記該體素，然后搜索下一個超級體素，這樣所有超級體素同時考慮從中心向外的每個級別迭代地向外進行，直到到達每個超體素的搜索量的邊緣。

2.3 區(qū)域增長算法流程

通過對傳統(tǒng)區(qū)域增長算法的改進，增加算法過程中的過分割步驟，此步驟避免了直接對點云數據的分割，加強了分割算法中噪聲和異常值的魯棒性，并且可以確保得到精確的邊界信息。在此算法中，輸入的數據為過分割步驟得到的超體素，同時考慮了空間連通性、表面光滑性[16]以及表面幾何特征方面的幾個約束條件，通過對超體素的光滑性和幾何特征綜合衡量后進行區(qū)域增長。為了確保分割區(qū)域的光滑性，采用了法線的夾角，法線用超體素質心點的法線來表示，通過描述體素數據的表面幾何特征，可以處理結構形狀復雜的點云數據來保證分割算法的穩(wěn)定性（圖5）。

圖5 區(qū)域增長算法流程Fig.5 Regional growth algorithm flow

2.4 相似性距離計算

在對每次聚類過程的搜索范圍進行限制后，使得該算法在接近相鄰超體素的聚類中心時停止搜索。在聚類過程中，需要利用最大距離為的數據對空間距離DS進行歸一化處理。這兩種屬性的相對重要性會隨著種子分辨率Rpatch進行變化。體素與鄰接體素之間的距離定義為D，三維空間內體素的歐式距離值為DS，用DC來表示體素之間的曲率變化值，體素點特征直方圖的交叉核用DHIK來表示，λS、λC、λHIK分別對應空間距離和幾何特征的影響因子，體素鄰域范圍內的最大曲率值用Cmax來表示，鄰接體素相似距離的計算公式如下所示：

在上述超體素區(qū)域增長算法的流程中，可以先通過計算平面擬合[17]所有的超體素得到對應的殘差值，用殘差值的近似曲率來判斷初始的種子超體素，選擇殘差值最小的超體素作為初始種子，同時在篩選其余種子超體素時要設定確定的閾值；然后對每一個超體素提取衡量表面幾何特征和光滑程度的特征向量，在測量相鄰超體素間的相似性時可以采用歸一化距離值來處理，最后得到符合語義信息的分割區(qū)域。

2.5 空間連通性

本文的算法可以在法線相近且物體不同的邊緣處斷開，來確保分割結果不會出現跨越遮擋或者未被遮擋的邊界信息，保證空間的連通性。可舉例說明約束條件的場景，將兩個大小不同的盒子放置于同一平面上，可知表面的法線方向相同，在全局范圍內屬于表面光滑區(qū)域，在局部范圍內出現隱藏的邊界信息，該分割算法在兩盒子的邊界處將其分割開，但是，如果分割算法只對光滑性約束進行考慮而忽略空間連通性約束，最終將無法實現兩個盒子的精確分割。針對上述的操作過程，在完成過分割和區(qū)域增長算法的流程后，將超體素數據作為輸入數據，最后分割出平滑、精確的區(qū)域。

3 分割結果與數據比較

本文中使用了PCL 中的一些算法及可視化庫，實驗配置環(huán)境為Windows7、64 位的操作系統(tǒng)及VS2015+PCL1.8.0。分割原圖與結果圖如下所示：

圖6 場景圖與實驗分割結果Fig.6 Scene diagram and experimental segmentation results

Rabbani T,et al.[18]等人總結過，在局部范圍內，高曲率區(qū)域可以用模型擬合偏差產生的殘差值來確定，無法用殘差值來精確衡量曲率的大小和方向。k均值聚類算法的重點在于選取初始種子，但點云密度會影響最終的分割結果，Ransac 算法是將點進行分組，一般情況下用于建筑物的提取，使用凹凸性方法[19]只局限于將場景中的大型物體分割出來，本文中的算法與之相比，效果更好，更精確。通過表1 對比幾個算法的運行時間。

表1 各算法運行時間對比Table 1 Comparison of running time of each algorithm

4 結論

本文中的區(qū)域增長算法結合了空間連通性，同時在衡量超體素之間的相似性時，考慮了表面的幾何特征，在篩選種子超體素時運用超體素數據平面擬合的殘差值，使得算法可以在表面光滑但空間不連通的區(qū)域或者邊界處斷開，避免出現過分割或欠分割的問題。在過分割的基礎上，用基于超體素的區(qū)域增長算法，將超體素數據作為輸入數據，使改進后的算法在運行時間上減少，并且分割出平滑、精確的區(qū)域，提高了算法的魯棒性。