基于柵格的點云數據的邊界探測方法

何 麗，李 嘉，鄭德華

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

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

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

1 點云網格化及其轉換

1.1 三維點云的特征

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

圖1 三維激光掃描儀的內部坐標系

激光掃描所獲得的是由離散矢量點構成的點云（Points Cloud）數據。總體上來講，點云數據可以分為散亂點云和規則點云兩大類。散亂點云沒有明顯的幾何分布特征，掃描點之間沒有明確的空間鄰域和拓撲關系，無規則的分布于目標對象空間（見圖2）。

圖2 不同類型的數據點云

規則點云是按照一定的規則進行采集和存儲的點云數據。規則點云一般有兩種類型：

1）網格化點云。點云數據呈矩形分布，所有點都與參數域中一個均勻網格相對應。多為點云數據經過網格化插值得到。

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

地面激光掃描儀以掃描線的形式進行數據采集和存儲，一般通過掃描線分組和線內數據點排序的方法來建立掃描線點云的鄰域關系和拓撲結構。

1.2 三維點云的柵格化

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

1.2.1 確定X，Y軸上的值

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

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

1.2.2 掃描線分組

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

圖3 坐標轉換后水平角值及其局部放大圖

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

1.2.3 點云數據分行

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

圖4 坐標轉換后豎直角值

其中，［］表示取整。

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

1.3 深度圖像的生成

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

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

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

結合上面討論的三維點云數據的柵格化，實現x，y方向的均勻規格采樣，因此可快速實現深度圖像的轉換。

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

三維激光掃描過程中受到儀器誤差、環境誤差等影響，現場實測的三維數據在很多區域會出現數據缺失，如圖5所示，進而導致映射的深度圖像中對應像素數據的缺失。因此，需要對圖像進行處理后再進行邊界的提取。

圖5 點云柵格示意圖

2 圖像邊界探測算法

2.1 深度圖像處理

2.1.1 圖像插值

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

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

2.1.2 深度圖像濾波

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

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

2.2 深度圖像邊緣檢測

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

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

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

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

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

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

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

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

3 點云邊界探測及顯示

將圖像的邊界探測結果轉換到三維空間中，即檢測出點云數據中對應邊界的掃描點。

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

4 實驗結果

通過VC6.0調用OpenGL三維函數庫，實現基于掃描線的地面激光掃描數據邊界提取的程序開發，并進行了大量的實驗，應用Jiang［7］等提出的評估方法進行評估，驗證本文算法有較優的性能。

4.1 算法性能評估

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

4.2 實驗結果分析

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

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

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

圖10 邊界點云（EM圖）

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

表1 兩種算法實驗結果比較

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

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

圖13 原始點云顯示

圖14 邊界探測結果

5 結 論

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

1）邊界提取方法簡單，用戶可以自動調節Canny算子的高低閾值，得到最完整的邊界數據。

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

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

4）可應用在基于邊界特征的點云數據的多視拼接與配準、點云數據的角點檢測、點云數據的分割、點云的重構建模等后續處理工作。

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

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

［3］李江雄.反求工程中復雜曲面邊界線的自動提取技術［J］.機械設計與制造工程，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］孫曉蘭，趙慧潔.基于網格采樣的深度圖像表面 特征提取算法［J］.中國圖像圖形學報，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.