張大鵬，鄭德華，夏佳毅

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

基于特征線的點(diǎn)云數(shù)據(jù)分割算法

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

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

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

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

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

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

1 深度圖像的生成

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

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

式中， Smin和Smax分別表示點(diǎn)云數(shù)據(jù)到掃描儀中心的距離的最小值與最大值。

為了方便后續(xù)點(diǎn)云數(shù)據(jù)處理，需要?jiǎng)?chuàng)建另外一個(gè)圖像數(shù)組，其像素為Pi=（xi，yi，zi），其中（xi，yi，zi）表示該點(diǎn)在三維直角坐標(biāo)系下的坐標(biāo)。這種形式的深度圖像無(wú)法以灰度圖像的形式直接顯示出來(lái)，但由于掃描點(diǎn)的位置可以根據(jù)深度圖像中的像元位置（即掃描點(diǎn)在柵格中的行列號(hào)）來(lái)確定，使得這種掃描點(diǎn)云拓?fù)浣Y(jié)構(gòu)的建立方式提高了后續(xù)數(shù)據(jù)處理的效率。

2 深度圖像的邊界探測(cè)

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

本文采用Canny算子對(duì)深度圖像進(jìn)行特征提取。Canny算子滿足3個(gè)判斷準(zhǔn)則：信噪比準(zhǔn)則，定位精度準(zhǔn)則，單邊緣響應(yīng)準(zhǔn)則。Canny算法是高斯函數(shù)的一階導(dǎo)數(shù)，是對(duì)信噪比與定位精度乘積的最優(yōu)化逼近算子[7]。其分為4步，分別是圖像平滑、邊緣檢測(cè)、閾值分割及邊緣定位，具體如下：

1）采用高斯濾波器，對(duì)圖像f（x，y）進(jìn)行平滑濾波，高斯函數(shù)公式為：

2）用一階偏導(dǎo)數(shù)的有限差分計(jì)算平滑后的圖像梯度?g（x，y）和方向θ（x，y）：

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

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

本文采用開放式的閾值設(shè)置方法，用戶可以自己調(diào)節(jié)高低閾值及σ的大小，以得到最滿意的邊界數(shù)據(jù)。

3 生成初始特征線

根據(jù)得到的特征點(diǎn)及其在柵格中的索引，利用點(diǎn)之間的距離關(guān)系將相近的點(diǎn)連接起來(lái)。

具體步驟如下：

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

2）在S0的近鄰中計(jì)算特征點(diǎn)集與S0的距離d，搜索距離最近的2個(gè)點(diǎn)P、Q。若其距離d

3）在S0的近鄰中搜索距離最近的點(diǎn)Pi，若其距離d

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

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

4 提取平面點(diǎn)

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

提取平面點(diǎn)的具體步驟如下：

1）將特征線按點(diǎn)云數(shù)目排序，從特征點(diǎn)數(shù)目最多的特征線開始計(jì)算。

2）在特征線上的點(diǎn)云中任選3點(diǎn)（P1，P2，P3），構(gòu)造一個(gè)平面L，利用特征值法計(jì)算a、b、c的初始值。

3）根據(jù)計(jì)算出的a、b、c值，按照公式計(jì)算出該掃描線上其余點(diǎn)至平面L的距離di。統(tǒng)計(jì)di小于閾值2σ的點(diǎn)的個(gè)數(shù)，作為L(zhǎng)的分?jǐn)?shù)SL。

4）重復(fù)第2）、3）步Cn3/2次，選擇出分?jǐn)?shù)最高的平面L'，重新計(jì)算最佳的a、b、c值。

5）以平面L'為最佳擬合平面，運(yùn)用式（6）計(jì)算特征線內(nèi)的點(diǎn)的高度差h，設(shè)置閾值ε，判斷h是否小于閾值ε，高度差小的即可認(rèn)為是平面。

6）將平面點(diǎn)標(biāo)記為已訪問，計(jì)算下一條特征線，直到所有的點(diǎn)訪問完畢。

其中，閾值2σ為距離di的標(biāo)準(zhǔn)偏差，其計(jì)算公式為：

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

對(duì)RealWorks軟件中提供的某培訓(xùn)數(shù)據(jù)進(jìn)行處理，如圖1所示，共有145 329個(gè)點(diǎn)。將其轉(zhuǎn)換成深度圖像，如圖2所示，像素大小為512 416。

圖1 原始點(diǎn)云數(shù)據(jù)

圖2 深度圖像

因?yàn)榇藪呙鑼?duì)象為平面，其特征邊緣都為跳躍型，所以直接對(duì)深度圖像采用邊緣檢測(cè)算子進(jìn)行特征提取就能取得較好的結(jié)果，如圖3所示。轉(zhuǎn)換為點(diǎn)云如圖4所示，共檢測(cè)到2 854個(gè)特征點(diǎn)。將特征點(diǎn)連成特征線，共有特征線33條，其中閉合特征線7條，如圖5所示。對(duì)其進(jìn)行平面點(diǎn)的提取，結(jié)果如圖6所示。利用提取出來(lái)的平面點(diǎn)進(jìn)行平面擬合，其標(biāo)準(zhǔn)差為78.52 mm。若直接采用原始點(diǎn)云數(shù)據(jù)進(jìn)行平面擬合，其標(biāo)準(zhǔn)差為120.33 mm。可見，對(duì)于平面點(diǎn)云數(shù)據(jù)，本文算法可有效快速地提取出點(diǎn)云數(shù)據(jù)的特征點(diǎn)，并提取出平面。

P237.3

B

1672-4623（2015）03-0120-02

10.3969/j.issn.1672-4623.2015.03.042

2014-03-17。