基于柵格的點云數(shù)據(jù)的邊界探測方法

何 麗，李 嘉，鄭德華

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

邊界是三維建模的重要幾何特征信息。邊界提取技術(shù)在醫(yī)學(xué)圖像、工業(yè)斷層掃描圖像等二維圖像處理領(lǐng)域中應(yīng)用廣泛。在逆向工程中，點云數(shù)據(jù)的三維空間分布的不均勻性，難以建立嚴格的數(shù)學(xué)模型，使得點云數(shù)據(jù)的邊界提取成為一項較復(fù)雜的工作。近年來對于點云數(shù)據(jù)邊界的自動提取，國內(nèi)外學(xué)者已有一些研究［1－3］。

為了簡化算子結(jié)構(gòu)，提高對大量復(fù)雜點云數(shù)據(jù)的處理速度，本文提出一種基于掃描線的點云數(shù)據(jù)邊界探測算法，該算法的主要思想是利用點云數(shù)據(jù)的特征將三維點云數(shù)據(jù)轉(zhuǎn)換為深度圖像，對深度圖像提取邊緣信息，最后將其轉(zhuǎn)換到三維空間中。

1 點云網(wǎng)格化及其轉(zhuǎn)換

1.1 三維點云的特征

地面三維激光掃描儀原始觀測值主要有：通過TOF（Time of Flight）脈沖測距法獲得的儀器到掃描儀的距離值S；精密時鐘控制編碼器同步測量每個激光束的水平方向角度值α和豎直方向角度值θ；反射強度I。前兩類數(shù)據(jù)用來計算掃描點的三維坐標值；反射強度用來給反射點匹配顏色。一般使用儀器內(nèi)部坐標系統(tǒng)，如圖1所示，三維掃描點P的坐標（Xp，Yp，Zp）的計算公式為

圖1 三維激光掃描儀的內(nèi)部坐標系

激光掃描所獲得的是由離散矢量點構(gòu)成的點云（Points Cloud）數(shù)據(jù)?？傮w上來講，點云數(shù)據(jù)可以分為散亂點云和規(guī)則點云兩大類。散亂點云沒有明顯的幾何分布特征，掃描點之間沒有明確的空間鄰域和拓撲關(guān)系，無規(guī)則的分布于目標對象空間（見圖2）。

圖2 不同類型的數(shù)據(jù)點云

規(guī)則點云是按照一定的規(guī)則進行采集和存儲的點云數(shù)據(jù)。規(guī)則點云一般有兩種類型：

1）網(wǎng)格化點云。點云數(shù)據(jù)呈矩形分布，所有點都與參數(shù)域中一個均勻網(wǎng)格相對應(yīng)。多為點云數(shù)據(jù)經(jīng)過網(wǎng)格化插值得到。

2）掃描線點云。點云以掃描光刀面的形式進行儲存，點云由一系列掃描線組成，在同一光刀面內(nèi)的掃描點是共面的。

地面激光掃描儀以掃描線的形式進行數(shù)據(jù)采集和存儲，一般通過掃描線分組和線內(nèi)數(shù)據(jù)點排序的方法來建立掃描線點云的鄰域關(guān)系和拓撲結(jié)構(gòu)。

1.2 三維點云的柵格化

柵格化的目的是把三維點云映射為圖像的二維矩陣表示形式，即將掃描點映射到XY平面。

1.2.1 確定X，Y軸上的值

目前，三維激光掃描文件一般無法直接讀取距離及角度，利用式（1）中坐標與角度的關(guān)系，把坐標（Xp，Yp，Zp）依次轉(zhuǎn)化為（α，θ，S）格式，如式（2）所示，得到一個二維點集，記為S：｛Pi（αi，θi）｜1≤i≤n｝，其中n為掃描點的總個數(shù)。

式中：α，θ為XY投影面橫軸、豎軸上的值。α取值范圍（0，2π），θ取值范圍（－π/2，π/2）。計算XY平面內(nèi)“點云”數(shù)據(jù)最小包圍盒，得到α，θ最大最小值。

1.2.2 掃描線分組

遍歷X軸方向的水平角值，其散點圖如圖3所示，由圖中可見每一組的水平角為固定值，且水平角呈線性分布。因此，可通過相鄰兩個掃描點的水平角差值的變化確定掃描線的分組：當(dāng)?shù)趇＋1個點與第i個點的水平角差值突然增大，且大于某一正數(shù)時，第i＋1個掃描點為下一組掃描線的第1個掃描點。N等于掃描線的總數(shù)。

圖3 坐標轉(zhuǎn)換后水平角值及其局部放大圖

因掃描時存在誤差，每組掃描線間隔不完全相等?？赏ㄟ^計算每組掃描線的水平角均值αavg來計算相鄰兩組掃描線之間的水平角差值，求其平均值即得掃描線平均間距Δα。

1.2.3 點云數(shù)據(jù)分行

遍歷Y軸方向的豎直角值，其散點圖如圖4所示，由圖中可見每組掃描線上的豎直角呈相同的線性分布。由此可計算每個掃描點在柵格中對應(yīng)的位置。首先搜索每組掃描線的掃描點個數(shù)，取其最大值M為柵格的行數(shù)，則豎直角平均間距約為Δθ＝。在點云中選取西南角點（αmin，θmin）作為基準點，然后計算掃描點與基準點的相對位置。根據(jù)式（3）可計算出每個掃描點在柵格中的位置。

圖4 坐標轉(zhuǎn)換后豎直角值

其中，［］表示取整。

點云柵格化后生成M行N列的二維矩陣，建立矩陣與點云對應(yīng)的索引矩陣。

1.3 深度圖像的生成

深度圖像實質(zhì)就是帶有距離信息的視覺圖像。與傳統(tǒng)的視覺圖像相比，深度圖像中的每個像素存放的不是灰度信息或者顏色信息，而是三維模型表面到成像面的距離信息，因此，深度圖像既包含三維模型空間信息，又具有視覺圖像的特點。

1988年，Besl提出了深度圖像表達形式［5］

式中：d（i，j）表示深度信息，即掃描點到圖像像面距離S；（i，j）表示像素點行列坐標。深度圖像d（i，j）可看成二維矩陣，即有0≤i≤M－1，0≤j≤N－1；矩陣元素成為圖像像素，M×N表示圖像的大小，即行數(shù)和列數(shù)。

結(jié)合上面討論的三維點云數(shù)據(jù)的柵格化，實現(xiàn)x，y方向的均勻規(guī)格采樣，因此可快速實現(xiàn)深度圖像的轉(zhuǎn)換。

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

三維激光掃描過程中受到儀器誤差、環(huán)境誤差等影響，現(xiàn)場實測的三維數(shù)據(jù)在很多區(qū)域會出現(xiàn)數(shù)據(jù)缺失，如圖5所示，進而導(dǎo)致映射的深度圖像中對應(yīng)像素數(shù)據(jù)的缺失。因此，需要對圖像進行處理后再進行邊界的提取。

圖5 點云柵格示意圖

2 圖像邊界探測算法

2.1 深度圖像處理

2.1.1 圖像插值

傳統(tǒng)插值方法平滑效果較好，但會造成邊緣和細節(jié)特征的模糊；基于區(qū)域的插值方法，可以保持圖像的邊緣特征，故使用基于區(qū)域的插值技術(shù)來恢復(fù)出缺失的像素。

此方法大致過程是：首先通過區(qū)域分割技術(shù)，將圖像分為不同的區(qū)域，然后確定插值點所屬的區(qū)域，在一般區(qū)域用鄰域加權(quán)線性方法進行插值，對邊緣區(qū)域則采用有針對性的插值方法。

2.1.2 深度圖像濾波

三維數(shù)據(jù)映射為深度圖像后，引入圖像噪聲。主要有脈沖型噪聲、高斯噪聲、椒鹽噪聲，如果直接對含有噪聲的圖像進行分割，會損失很多圖像細節(jié)，或出現(xiàn)偽邊緣，檢測效果差。

本文采用中值濾波器，它是一種非線性濾波，可以有效地去除噪聲，特別是對脈沖型噪聲、椒鹽噪聲，而且可以較好地保護圖像邊緣。

2.2 深度圖像邊緣檢測

邊緣是圖像中表面或者方向不連續(xù)的點。有多種算法可以檢測深度圖像邊緣，如Roberts、Sobel、Prewitt、Kirsch和Laplacian等算子。但它們對噪聲比較敏感，處理實際圖像的效果并不理想。

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

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

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

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

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

4）雙閾值算法檢測和邊緣連接。利用Canny算子檢測圖像邊緣的關(guān)鍵是選取適當(dāng)?shù)拈撝狄约唉?，合理的高低閾值設(shè)定能檢測出更多真實邊緣，去除盡可能多的偽邊緣。若高閾值設(shè)定過小會檢測出的邊緣中混有大量噪聲，設(shè)定過大又會漏檢真實邊緣，對于低閾值，若設(shè)定過大會造成灰度值突變較小的邊緣被漏檢；另外，合理的σ大小也很重要，σ越大，使圖像平滑程度越大，將導(dǎo)致圖像細節(jié)消失，灰度突變也會遠離原來邊緣的位置，同時使高斯濾波器長度變長，加大計算量，反之，σ越小，則又會因為圖像平滑不夠使檢測的邊緣中混有許多噪聲。

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

3 點云邊界探測及顯示

將圖像的邊界探測結(jié)果轉(zhuǎn)換到三維空間中，即檢測出點云數(shù)據(jù)中對應(yīng)邊界的掃描點。

因為點云數(shù)據(jù)與深度圖像之間存在一對一的映射關(guān)系，由Canny算子檢測得到的邊界圖像其像元位置沒有發(fā)生改變，故可通過邊界圖像上邊界線的像元的位置找到對應(yīng)索引矩陣中的位置，從而得到邊界點的坐標。即得圖像邊界位置的掃描點的空間位置信息。

4 實驗結(jié)果

通過VC6.0調(diào)用OpenGL三維函數(shù)庫，實現(xiàn)基于掃描線的地面激光掃描數(shù)據(jù)邊界提取的程序開發(fā)，并進行了大量的實驗，應(yīng)用Jiang［7］等提出的評估方法進行評估，驗證本文算法有較優(yōu)的性能。

4.1 算法性能評估

應(yīng)用軟件對點云原始數(shù)據(jù)進行人工邊界提取，得到的結(jié)果稱為GT（ground truth），用算法自動邊界提取的結(jié)果稱為EM（machine－generated edge map）。當(dāng)提取的邊界點同屬于GT和EM中時，則被認為是正確檢測［8］。

4.2 實驗結(jié)果分析

點云數(shù)據(jù)是由Trimble GXTM三維激光掃描儀采集，圖6是在RealWorks軟件中顯示的原始點云，點云個數(shù)為688 716；對原始數(shù)據(jù)進行坐標變換并柵格化后得到深度圖像，如圖7所示，圖像大小為1200×675像素，圖中灰度值的大小代表掃描點到圖像像面的距離S，灰度值為0的區(qū)域代表背景區(qū)域。由于這幅點云是在室外進行掃描，受到外界條件影響較大，故生成的圖像空缺點較多。

對深度圖像進行插值平滑處理后的圖像如圖8所示，其空點明顯減少，圖中右邊橋梁上的大空洞是由掃描過程中遮擋物造成的，故無法平滑。

調(diào)節(jié)Canny算子閾值，當(dāng)高低閾值分別為10、30時，邊緣提取的結(jié)果如圖9所示，此時橋梁邊緣線連接程度較好，邊界表示完整，邊緣線較細。通過邊界圖像上邊界線的像元的位置找到對應(yīng)索引矩陣中的位置，從而得到邊界點的坐標，將邊界線轉(zhuǎn)換到三維空間中，其邊界點云（EM圖）如圖10所示，檢測到的邊界點總數(shù)為18 264。

圖10 邊界點云（EM圖）

圖11是在軟件中對原始點云進行人工提取邊界得到的GT圖。采用文獻［2］中直接提取算法得到的結(jié)果如圖12所示，可以看出，提取出的邊界點不連續(xù)，甚至發(fā)生跳變，邊緣錯位。表1所示為本文算法與直接提取法的結(jié)果比較。

表1 兩種算法實驗結(jié)果比較

基于柵格化的掃描線法的正確檢測率較高，可以較好地平衡邊緣定位精度和抗噪聲性能的矛盾，其性能優(yōu)于其他算法。這對后續(xù)的處理工作非常有利。但是結(jié)果與相應(yīng)的GT圖像還有一定的差距。

為了對算法的適應(yīng)性進行實驗，選取了一幅復(fù)雜的點云數(shù)據(jù)進行處理，其原始的數(shù)據(jù)點云如圖13所示，共有746 252個點，包含曲面物體、平面物體等。圖14是其邊界探測的結(jié)果，可見該算法對于任意形狀的物體都適用，具有很強的適應(yīng)性和應(yīng)用性。

圖13 原始點云顯示

圖14 邊界探測結(jié)果

5 結(jié) 論

本文分析三維點云和深度圖像的數(shù)據(jù)結(jié)構(gòu)特征，提出一種基于柵格化的掃描線點云數(shù)據(jù)邊界提取方法。采用該方法能對大量的復(fù)雜點云數(shù)據(jù)進行直接、有效的提取，其具有以下特點：

1）邊界提取方法簡單，用戶可以自動調(diào)節(jié)Canny算子的高低閾值，得到最完整的邊界數(shù)據(jù)。

2）特別適合于曲面特征多的點云數(shù)據(jù)，對其他特征的數(shù)據(jù)也同樣適用。

3）運行速度較快，對點云數(shù)據(jù)的邊界提取質(zhì)量高，可以滿足點云數(shù)據(jù)后續(xù)處理的要求。

4）可應(yīng)用在基于邊界特征的點云數(shù)據(jù)的多視拼接與配準、點云數(shù)據(jù)的角點檢測、點云數(shù)據(jù)的分割、點云的重構(gòu)建模等后續(xù)處理工作。

［1］Alrashdan A，Motavalli S，F(xiàn)allahi B.Automatic Segmentation of digitized data for reverse engineerng applications［J］.IEEE Transaction on Design and Manufacturing，2000，32（4）：59－69.

［2］柯映林，范樹遷.基于點云的邊界特征直接提取技術(shù)［J］.機械工程學(xué)報，2004，40（6）：116－120.

［3］李江雄.反求工程中復(fù)雜曲面邊界線的自動提取技術(shù)［J］.機械設(shè)計與制造工程，2000，9（2）：26－28.

［4］鄭德華，沈云中，劉春.三維激光掃描儀及其測量誤差影響因素分析［J］.測繪工程，2005，14（2）：32－34.

［5］Besl P J，Jain R C.Jain.Segmentation through variable－order surface fitting［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1988，10（2）：167－192.

［6］孫曉蘭，趙慧潔.基于網(wǎng)格采樣的深度圖像表面 特征提取算法［J］.中國圖像圖形學(xué)報，2007，12（6）：1091－1097.

［7］Jiang X Y，Bunke H.Edge detection in range images based on scan line approximation［J］.Computer Vision and Image Understanding，1999，73（2）：183－199.

［8］Hoover A，Jean－Baptiste G，Jiang X Y，et al.An experimental comparison of range image segmentation algorithms［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1996，18（7）：673－689.