方源敏，夏永華，陳 杰，宋煒煒，楊永明，左小清

（昆明理工大學(xué)國土資源工程學(xué)院，云南昆明 650093）

0 引 言

地下采礦的采空區(qū)是一次整體爆破后形成的，是形狀極不規(guī)則的復(fù)雜空間實體，出于安全考慮，人員不準許進入其內(nèi)進行測量［1－3］?？諈^(qū)探測系統(tǒng)（CMS）可解決采空區(qū)的自動化測量，所獲取的采空區(qū)三維激光點云數(shù)據(jù)雖然很精細，但是數(shù)據(jù)量大。如果設(shè)置成水平和垂直掃描間隔均為1°，掃描一個空區(qū)得到的三維坐標數(shù)據(jù)點接近50 000個，數(shù)據(jù)量超過2MB，一個中等礦山的采空區(qū)可能超過100個，僅空區(qū)數(shù)據(jù)量就會超過200MB。整個礦區(qū)三維地理信息系統(tǒng)的建立還需要很多其他空間數(shù)據(jù)，諸如礦體、井巷等，巨大的數(shù)據(jù)量將使存儲、運算和傳輸效率低下，生成三維曲面模型的速度較慢，并且過于密集的點云會影響重構(gòu)曲面的光順性。因此，在采空區(qū)點云數(shù)據(jù)預(yù)處理中，必須在保證被測物體幾何特征的前提下，根據(jù)物體的特征點對點云數(shù)據(jù)進行精簡，提高曲面模型重構(gòu)的效率。

很多學(xué)者對數(shù)據(jù)精簡的研究已有一系列成果。Schroeder等提出了基于頂點刪除的網(wǎng)格刪減方法［4］；Turk給出了基于重新劃分的模型簡化方法［5］；Eck等將小波技術(shù)用于模型簡化［6］；Filip等應(yīng)用包圍盒法來簡化點云［7］；Lee等通過點云法矢量估算，運用八叉樹數(shù)據(jù)結(jié)構(gòu)，實現(xiàn)點云數(shù)據(jù)的空間精簡［8］；劉德平等研究了自適應(yīng)最小距離精簡算法［9］；吳杭彬等總結(jié)激光掃描數(shù)據(jù)的特點，并基于其線掃描的特點，提出以掃描線斜率變化為準則實施數(shù)據(jù)壓縮［10］；Yu等提出了一種自適應(yīng)的三維點云數(shù)據(jù)精簡算法［11］。這些方法只對某一種數(shù)據(jù)形式精簡效果好，并且有些方法實現(xiàn)難度較大；因此，筆者提出了一種適合于采空區(qū)點云數(shù)據(jù)的精簡算法——改進的角度偏差法。

1 點云數(shù)據(jù)精簡算法評價體系

一個最佳的精簡算法應(yīng)該是利用最少的離散點就能達到全面表示空間復(fù)雜實體原有信息，并在此基礎(chǔ)上追求更快的建模速度。點云數(shù)據(jù)精簡算法的效果可以從以下3方面來衡量［11－13］。

（1）精度，即用精簡后的點云數(shù)據(jù)構(gòu)建的三維模型與原始三維模型之間的誤差要小。數(shù)據(jù)精簡后，不但要保證誤差值在允許范圍內(nèi)，還要盡可能地保留原始點云特征。具體指標有長度、表面積、截面面積、體積、飽滿度等。

（2）簡度，即在保證精度的基礎(chǔ)上盡量精簡點云數(shù)據(jù)。需要指出的是，有時數(shù)據(jù)點數(shù)過少會給后續(xù)建模（例如三角網(wǎng)格化）帶來困難，因此應(yīng)根據(jù)實際需要選擇合適的精簡率。

（3）速度，即精簡過程的時間耗費要盡可能少。即使?jié)M足精度和簡度，但如果耗費時間太多，也難以在實際應(yīng)用中推廣。

實際上，要同時實現(xiàn)以上3個目標是不可能的，很多算法往往只能在一個或兩個方面有優(yōu)勢。數(shù)據(jù)精簡的最佳效果是使精簡后的點云數(shù)據(jù)量較少、能保持細節(jié)特征且速度較快［14］。數(shù)據(jù)點在精簡后的疏密應(yīng)該隨著曲面曲率的變化而變化，即曲率變化越大，數(shù)據(jù)點越多；曲率變化越小，數(shù)據(jù)點就越少。因此，在數(shù)據(jù)精簡過程中，必須在保證被掃描實體幾何特征的前提下，根據(jù)物體曲面的曲率變化對點云數(shù)據(jù)進行非均勻精簡，以提高曲面重構(gòu)的效率和精度。

2 CMS掃測采空區(qū)點云數(shù)據(jù)的方式

為了對點云數(shù)據(jù)進行精簡，許多學(xué)者提出了很多點云數(shù)據(jù)精簡算法。雖然點云數(shù)據(jù)精簡算法很多，但是對于不同類型的點云數(shù)據(jù)需要采取不同的精簡算法，才能達到理想效果［15－16］。

CMS是沿著事先設(shè)置好水平和豎直間隔角度形成線狀掃描的系統(tǒng)［17］（圖1）。根據(jù)CMS掃描獲得的觀測數(shù)據(jù)，筆者分析其本身的特點，并考慮掃描結(jié)構(gòu)特征的影響，對數(shù)據(jù)進行精簡處理，并用采空區(qū)掃描數(shù)據(jù)實例加以說明。在引入CMS之前，在安全條件允許的條件下，采用全站儀按一定間隔測量常規(guī)采空區(qū)斷面，然后根據(jù)斷面數(shù)據(jù)進行后續(xù)建模。假設(shè)密集的點云數(shù)據(jù)構(gòu)成的點云包裹體是一個“真實”的采空區(qū)，在“真實”的采空區(qū)進行采樣，可以采用某一條水平掃描線來進行分析，減少數(shù)據(jù)量的同時，還可將新的點集擬合成輪廓曲線，最后根據(jù)這些輪廓信息以及方向矢量信息重建曲面。

圖1 空區(qū)探測系統(tǒng)掃測原理Fig.1 Scanning Principle of CMS

3 CMS掃描線特征點常規(guī)提取方法

CMS掃描線點云數(shù)據(jù)特征點的提取可以采用最小距離法、平均距離法、角度偏差法、弦高偏差法等［18－19］。以一條水平掃描線為例，分析這些方法對采空區(qū)掃描線點云數(shù)據(jù)進行精簡處理的優(yōu)缺點。

3.1 最小距離法

以掃描線為單位，事先設(shè)定一個最小距離dmin，然后沿掃描線方向，順序比較相鄰兩點之間的距離d。若d＜dmin，則兩點中的一個點將被刪除，依次判斷所有的掃描點。其中，最小距離應(yīng)根據(jù)具體數(shù)據(jù)精簡處理的精度要求來確定。這里取dmin＝0.5m，結(jié)果見圖2。當(dāng)采用最小距離法進行數(shù)據(jù)精簡時，為了保證精度，只能采用較小的最小距離，這樣數(shù)據(jù)的精簡效率會明顯減弱；為了保證效率，選用較大的最小距離，則不能更好地保持細節(jié)特征。

圖2 最小距離法精簡的掃描線結(jié)果Fig.2 Result of Scan Line Simplified by Minimum Distance Method

3.2 平均距離法

在每一條掃描線上，依次計算點與點之間的距離，平均距離為

式中：d－為平均距離；di為點Pi與相鄰點的距離；n為數(shù)據(jù)點個數(shù)。若di≤d－，則對應(yīng)點Pi將被刪除，反之則保留，精簡結(jié)果見圖3。這種方法原理很簡單，但是無法保證掃描線的細節(jié)特征，不適合數(shù)據(jù)密集以及精度要求高的情況。

3.3 角度偏差法

引入角度αi來判斷點Pi是否應(yīng)該保留，事先設(shè)定一個角度閾值α（圖4），如果αi≥α，則點Pi保留，否則刪除，結(jié)果見圖5。角度偏差法能夠保持掃描線的細節(jié)特征，但在局部區(qū)域會出現(xiàn)點間距較大的情況。

3.4 弦高偏差法

圖3 平均距離法精簡的掃描線結(jié)果Fig.3 Result of Scan Line Simplified by Average Distance Method

圖4 角度偏差法與弦高偏差法原理Fig.4 Principles of Angular Deviation Method and Chord Height Deviation Method

圖5 角度偏差法精簡的掃描線結(jié)果Fig.5 Result of Scan Line Simplified by Angular Deviation Method

對于n個數(shù)據(jù)點，通過計算每一個輸入點和基線距離來判斷某一測點是否應(yīng)該刪去（圖4），精簡結(jié)果見圖6。弦高偏差法能夠保持掃描線的細節(jié)特征，但在較平緩區(qū)域會出現(xiàn)點間距過大的現(xiàn)象。

4 CMS掃描線特征點的新提取方法

在對比最小距離法、平均距離法、角度偏差法、弦高偏差法等采空區(qū)點云數(shù)據(jù)精簡方法的基礎(chǔ)上，筆者提出了保留采空區(qū)幾何特征更為有效的點云數(shù)據(jù)精簡方法——改進的角度偏差法。

圖6 弦高偏差法精簡的掃描線結(jié)果Fig.6 Result of Scan Line Simplified by Chord Height Deviation Method

在圖4中，Pi－1、Pi、Pi＋1為相鄰3個點。αi為線段Li－1，i、Li，i＋1的夾角，a、b、c分別為點Pi與點Pi－1、點Pi與點Pi＋1以及點Pi－1與點Pi＋1的距離。它們存在如下關(guān)系

首先將一條掃描線（截面線）上的點云數(shù)據(jù)按順序放到一個數(shù)組A中，根據(jù)式（2）順序取3點Pi－1、Pi、Pi＋1，可求得點Pi的偏角。遍歷這條截面線上所有點，即可求出該截面線上所有點的偏角，進而求出平均偏角值。將偏角值大于平均值的數(shù)據(jù)點提取出來，記錄它在數(shù)組A中的編號，然后放到數(shù)組B中。這時，數(shù)組B中的數(shù)據(jù)點可能不是均勻分布的。改進的方法是：計算數(shù)組B相鄰點的間距，將其與事先設(shè)定的閾值比較，如果間距大于閾值，以數(shù)組B中的這兩點為端點，向數(shù)組B中插入兩端點中點附近的數(shù)據(jù)點，所插入的數(shù)據(jù)點從數(shù)組A中提取，插入完畢后將數(shù)據(jù)存入數(shù)組C中，重復(fù)以上步驟，直到數(shù)組B中每兩點之間的距離都小于閾值為止，這時，數(shù)組C中的點數(shù)據(jù)基本是均勻分布的。

圖7顯示了角度偏差法和改進的角度偏差法精簡后的掃描線對比。顯然，改進的角度偏差法精簡后的數(shù)據(jù)不但保持了截面線的細節(jié)特征，還彌補了部分區(qū)域間距過大的問題，其各項指標見表1。

筆者提出的點云數(shù)據(jù)精簡算法——改進的角度偏差法，原理簡單，運算速度快，容易編程實現(xiàn)，雖然精簡率相對于角度偏差法有所降低，但其他各項指標均優(yōu)于角度偏差法。對每一條掃描線，利用上述算法進行處理，即完成了整個采空區(qū)的數(shù)據(jù)精簡。

圖7 角度偏差法與改進的角度偏差法精簡的掃描線對比Fig.7 Comparison of Scan Lines Simplified by Angular Deviation Method and Improved Angular Deviation Method

表1 角度偏差法與改進的角度偏差法精簡后的掃描線指標對比Tab.1 Comparison of Indicators of Scan Lines Simplified by Angular Deviation Method and Improved Angular Deviation Method

5 結(jié) 語

（1）CMS獲取的采空區(qū)三維激光點云數(shù)據(jù)雖然很精細，但是數(shù)據(jù)量大，在運算和存儲上都不方便，特別是在構(gòu)建礦山三維地理信息系統(tǒng)時，大量采空區(qū)掃描數(shù)據(jù)會影響系統(tǒng)的運行速度。因此，有必要對采空區(qū)三維激光掃描點云數(shù)據(jù)進行有效精簡。

（2）從CMS采集數(shù)據(jù)的特點入手，在分析了已有數(shù)據(jù)精簡算法的基礎(chǔ)上，提出了改進的角度偏差法，并運用該方法對采空區(qū)點云數(shù)據(jù)進行精簡。

（3）改進的角度偏差法雖然耗時稍長，但精簡效果理想，不但保持了掃描線上的細節(jié)，而且使精簡后的點云數(shù)據(jù)較為均勻，為后續(xù)三維建模及應(yīng)用打下良好基礎(chǔ)。

References：

［1］ 來興平.路基下大采空區(qū)動力災(zāi)害監(jiān)測預(yù)報［J］.長安大學(xué)學(xué)報：自然科學(xué)版，2003，23（5）：28－31.LAI Xing－ping.Dynamical and Unstable Monitoring Signal of Large Scale Subsiding Area Under Roadbed［J］.Journal of Chang'an University：Natural Science Edition，2003，23（5）：28－31.

［2］ 計 宏，余學(xué)義，高志興，等.彬長生產(chǎn)服務(wù)區(qū)下采空區(qū)穩(wěn)定性評價研究［J］.西安科技大學(xué)學(xué)報，2011，31（5）：544－548.JI Hong，YU Xue－yi，GAO Zhi－xing，et al.Assessment on Stability of Mine Goaf in Binchang Production Service Area［J］.Journal of Xi'an University of Science and Technology，2011，31（5）：544－548.

［3］ 湯伏全，原 濤，汪桂生.渭北礦區(qū)厚黃土層采動變形數(shù)值模擬研究［J］.西安科技大學(xué)學(xué)報，2011，31（1）：53－58.TANG Fu－quan，YUAN Tao，WANG Gui－sheng.Mining Deformation Numerical Simulation of Thick Loess Layer in Weibei Mining Area［J］.Journal of Xi'an University of Science and Technology，2011，31（1）：53－58.

［4］ SCHROEDER W J，ZARGE J A，LORENSEN W E.Decimation of Triangle Meshes［J］.Computer Graphics，1992，26（2）：65－70.

［5］ TURK G.Re－tiling Polygonal Surfaces［J］.Computer Graphics，1992，26（2）：55－64.

［6］ ECK M，DEROSE T，DUCHAMP T，et al.Multiresolution Analysis of Arbitrary Meshes［J］.Computer Graphics，1995，29（2）：173－182.

［7］ FILIP D，MAGEDSON R，MARKOT R.Surface Algorithms Using Bounds on Derivatives［J］.Computer Aided Geometric Design，1986，3（4）：295－311.

［8］ LEE K H，WOO H，SUK T.Point Data Reduction Using 3DGrids［J］.The International Journal of Advanced Manufacturing Technology，2001，18（3）：201－210.

［9］ 劉德平，陳建軍.逆向工程中數(shù)據(jù)精簡技術(shù)的研究［J］.西安電子科技大學(xué)學(xué)報：自然科學(xué)版，2008，35（2）：334－339.LIU De－ping，CHEN Jian－jun.Point Data Reduction Technique in Reverse Engineering［J］.Journal of Xidian University：Natural Science Edition，2008，35（2）：334－339.

［10］ 吳杭彬，劉 春.三維激光掃描點云數(shù)據(jù)的空間壓縮［J］.遙感信息，2006（2）：22－24.WU Hang－bin，LIU Chun.Spatial Compression of Point Cloud Data from Three Dimension Laser Scanning［J］.Remote Sensing Information，2006（2）：22－24.

［11］ YU Z W，WONG H S.ASM：an Adaptive Simplifica－tion Method for 3DPoint－based Models［J］.Computeraided Design，2010，42（7）：598－612.

［12］ 徐 尚.三維點云數(shù)據(jù)拼接與精簡技術(shù)的研究［D］.青島：中國海洋大學(xué)，2009.XU Shang.Study on Data Registration and Reduction for 3DPoint Clouds［D］.Qingdao：Ocean University of China，2009.

［13］ 溫銀放.數(shù)據(jù)點云預(yù)處理及特征角點檢測算法研究［D］.哈爾濱：哈爾濱工程大學(xué)，2007.WEN Yin－fang.Research on the Algorithms of Point Cloud Pre－processing and Feature Corner Detection［D］.Harbin：Harbin Engineering University，2007.

［14］ WAND M，BERNER A，BOKELOH M，et al.Processing and Interactive Editing of Huge Point Clouds from 3DScanners［J］.Computers and Graphics，2008，32（2）：204－220.

［15］ 夏永華，方源敏，孫宏生，等.三維激光探測技術(shù)在采空區(qū)測量中的應(yīng)用與實踐［J］.金屬礦山，2009（2）：112－113.XIA Yong－h(huán)ua，F(xiàn)ANG Yuan－min，SUN Hong－sheng，et al.Application Practice of 3DLaser Monitoring Technology in Finished Stope Survey［J］.Metal Mine，2009（2）：112－113.

［16］ 夏永華，方源敏，陳 杰，等.采空區(qū)點云數(shù)據(jù)的小波平滑方法［J］.湖南科技大學(xué)學(xué)報：自然科學(xué)版，2012，27（1）：84－87.XIA Yong－h(huán)ua，F(xiàn)ANG Yuan－min，CHEN Jie，et al.A Wavelet Smoothing Algorithm for Cloudy Data of Goaf［J］.Journal of Hunan University of Science and Technology：Natural Science Edition，2012，27（1）：84－87.

［17］ 趙 柳，馬 禮，楊銀剛，等.逆向工程中散亂點云數(shù)據(jù)精簡研究［J］.光電技術(shù)應(yīng)用，2010，25（1）：60－63.ZHAO Liu，MA Li，YANG Yin－gang，et al.Scattered Cloud Data Reduction Technique in Reverse Engineering［J］.Electro－optic Technology Application，2010，25（1）：60－63.

［18］ HUANG M C，TAI C C.The Pre－processing of Data Points for Curve Fitting in Reverse Engineering［J］.The International Journal of Advanced Manufacturing Technology，2000，16（9）：635－642.

［19］ 惠文華，郭新成.3D－GIS中空間曲線繪制方法研究［J］.地球科學(xué)與環(huán)境學(xué)報，2005，27（2）：63－65.HUI Wen－h(huán)ua，GUO Xin－cheng.Method of Drawing Spatial Curves in 3D－GIS［J］.Journal of Earth Sciences and Environment，2005，27（2）：63－65.