基于特征線的點云數據分割算法

張大鵬，鄭德華，夏佳毅

（1.河海大學 地球科學與工程學院，江蘇 南京 210098）

基于特征線的點云數據分割算法

張大鵬1，鄭德華1，夏佳毅1

（1.河海大學 地球科學與工程學院，江蘇 南京 210098）

為了提高點云數據分割的效率和精確度，基于深度圖像和CANNY算子，研究了一種新的按照特征線的點云數據分割算法。結果表明，這種基于特征線的數據分割算法能夠顯著提高數據分割的精度。

特征線；分割；深度圖像；CANNY算子

數據分割是點云數據處理中的一個重要環節，數據分割的好壞直接影響到曲面重構的質量[1]。國內外學者在點云分割方面已經作了大量研究。Jiang等[2]通過將掃描線分段擬合形成一組直線段來實現點云數據的平面分割，但效率較低；Besl和Jain提出區域生長方法識別數據中的同類區域[3]，僅局限于一個特定的模式；向日華和王潤生提出的基于高斯混合模型的分割算法[4]，對于大量散亂點云的效果并不理想；Yokoya和Levine實現了一種基于邊緣和基于區域生長的混合分割方式[5]，需要進行批量三角化，計算量大，難以精確識別特征點或特征線；丁益洪等人提出的基于隨機Hough變換的分割算法[6]，僅考慮了單個點計算隸屬度函數。

本文提出一種新的基于特征線的分割點云數據的方法。首先將三維點云數據轉換為深度圖像，利用CANNY算子來提取深度圖像的邊緣信息，然后將其轉換到三維空間中。根據特征線上的點擬合出最佳平面，并計算特征線內點的鄰域高度差，判斷該點是否屬于該平面，最后完成點云分割。

1 深度圖像的生成

深度圖像實際是帶有距離信息的圖像，它既包含空間三維信息，又具有視覺圖像的特點。Besl在1988年提出了深度圖像的表達形式：d（i，j）= f（xi,j，yi,j） (1)式中，d（i，j）表示深度信息，即掃描點到圖像像面的距離S；（i，j）表示像素點的行列坐標。深度圖像d （i， j）可看成二維矩陣，即有0≤i≤M-1，0≤j≤N-1；矩陣元素為圖像像素，M×N表示圖像的大小，即行數和列數。

二維矩陣與圖像的像素點是一對一的映射關系。因此，可根據掃描點在柵格中的位置（行列號）定位其在圖像中的像元的位置。根據掃描點到圖像像面的距離S 確定該點對應像元的灰度值，即Z方向代表深度，如式（2）所示，距離和灰度值成正比關系：

式中， Smin和Smax分別表示點云數據到掃描儀中心的距離的最小值與最大值。

為了方便后續點云數據處理，需要創建另外一個圖像數組，其像素為Pi=（xi，yi，zi），其中（xi，yi，zi）表示該點在三維直角坐標系下的坐標。這種形式的深度圖像無法以灰度圖像的形式直接顯示出來，但由于掃描點的位置可以根據深度圖像中的像元位置（即掃描點在柵格中的行列號）來確定，使得這種掃描點云拓撲結構的建立方式提高了后續數據處理的效率。

2 深度圖像的邊界探測

之前有很多的算法可以探測圖像的邊緣信息，如Kirsch、Prewitt、Laplacian等，但它們的魯棒性較差，對噪聲較敏感，無法高效率地提高圖像的實際邊緣。

本文采用Canny算子對深度圖像進行特征提取。Canny算子滿足3個判斷準則：信噪比準則，定位精度準則，單邊緣響應準則。Canny算法是高斯函數的一階導數，是對信噪比與定位精度乘積的最優化逼近算子[7]。其分為4步，分別是圖像平滑、邊緣檢測、閾值分割及邊緣定位，具體如下：

1）采用高斯濾波器，對圖像f（x，y）進行平滑濾波，高斯函數公式為：

2）用一階偏導數的有限差分計算平滑后的圖像梯度?g（x，y）和方向θ（x，y）：

Fx（x，y）、Fy（x，y）由G（x，y）在x 方向和y方向的偏微分分別與圖像卷積得到。

3）對梯度進行“非極大值抑制”， 為了細化幅值圖像中的屋脊帶，保留局部梯度極大值及在該點處梯度突變最大的像素點。

本文采用開放式的閾值設置方法，用戶可以自己調節高低閾值及σ的大小，以得到最滿意的邊界數據。

3 生成初始特征線

根據得到的特征點及其在柵格中的索引，利用點之間的距離關系將相近的點連接起來。

具體步驟如下：

1）確定起始點。本文以索引順序搜索，從特征點中第一個點S0開始，根據點云數據的分辨率定義距離閾值dmax。不同的三維點云數據的掃描間隔是不同的，根據不同的掃描間隔來定義距離閾值dmax(本文中實驗所用點云的掃描間隔為10 mm，距離閾值dmax設置為15 mm)。

2）在S0的近鄰中計算特征點集與S0的距離d，搜索距離最近的2個點P、Q。若其距離d

3）在S0的近鄰中搜索距離最近的點Pi，若其距離d

4）在特征點集未訪問的點中，取一點Pi賦值給S0，重復第2）、3）步，直到所有的點處理完畢。

若該終點的鄰點中包含起始點S0，則該特征線封閉；若不包含起始點S0，則特征線不封閉。

4 提取平面點

每個三維點的特征向量表示它鄰域的最主要特征。特征向量由3個屬性組成其中hi是點i相對于其鄰點的高度差，是點i的單位法向量，di是切平面到原點的距離。高度差hi是由點到其鄰點的最佳擬合平面的距離。點與其鄰點的高度hi通常用來測量曲面局部變化。hi值表示曲面的變化：值較小表示點位于曲面上，而值較大表明曲面波動較大。則此點的高度差h為：式中， （a，b,，c）表示平面的單位法向量， a2+ b2+c2= 1；d表示坐標原點到該平面的距離。根據hi的大小能判斷不同的曲面類型。對于均勻的點密度和均勻程度的噪音的平面點云數據，若hi約等于0說明點在曲面區域內。然而，如果是曲面點云數據，點到最佳擬合平面的距離將大于0。利用高度差來識別點是否屬于平面是很好的方法。

提取平面點的具體步驟如下：

1）將特征線按點云數目排序，從特征點數目最多的特征線開始計算。

2）在特征線上的點云中任選3點（P1，P2，P3），構造一個平面L，利用特征值法計算a、b、c的初始值。

3）根據計算出的a、b、c值，按照公式計算出該掃描線上其余點至平面L的距離di。統計di小于閾值2σ的點的個數，作為L的分數SL。

4）重復第2）、3）步Cn3/2次，選擇出分數最高的平面L'，重新計算最佳的a、b、c值。

5）以平面L'為最佳擬合平面，運用式（6）計算特征線內的點的高度差h，設置閾值ε，判斷h是否小于閾值ε，高度差小的即可認為是平面。

6）將平面點標記為已訪問，計算下一條特征線，直到所有的點訪問完畢。

其中，閾值2σ為距離di的標準偏差，其計算公式為：

5 實驗分析

對RealWorks軟件中提供的某培訓數據進行處理，如圖1所示，共有145 329個點。將其轉換成深度圖像，如圖2所示，像素大小為512 416。

圖1 原始點云數據

圖2 深度圖像

因為此掃描對象為平面，其特征邊緣都為跳躍型，所以直接對深度圖像采用邊緣檢測算子進行特征提取就能取得較好的結果，如圖3所示。轉換為點云如圖4所示，共檢測到2 854個特征點。將特征點連成特征線，共有特征線33條，其中閉合特征線7條，如圖5所示。對其進行平面點的提取，結果如圖6所示。利用提取出來的平面點進行平面擬合，其標準差為78.52 mm。若直接采用原始點云數據進行平面擬合，其標準差為120.33 mm。可見，對于平面點云數據，本文算法可有效快速地提取出點云數據的特征點，并提取出平面。

P237.3

B

1672-4623（2015）03-0120-02

10.3969/j.issn.1672-4623.2015.03.042

2014-03-17。