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

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

0 引 言

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

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

1 點(diǎn)云數(shù)據(jù)精簡(jiǎn)算法評(píng)價(jià)體系

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

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

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

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

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

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

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

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

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

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

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

3.1 最小距離法

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

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

3.2 平均距離法

在每一條掃描線上，依次計(jì)算點(diǎn)與點(diǎn)之間的距離，平均距離為

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

3.3 角度偏差法

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

3.4 弦高偏差法

圖3 平均距離法精簡(jiǎn)的掃描線結(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ǎn)的掃描線結(jié)果Fig.5 Result of Scan Line Simplified by Angular Deviation Method

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

4 CMS掃描線特征點(diǎn)的新提取方法

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

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

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

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

圖7顯示了角度偏差法和改進(jìn)的角度偏差法精簡(jiǎn)后的掃描線對(duì)比。顯然，改進(jìn)的角度偏差法精簡(jiǎn)后的數(shù)據(jù)不但保持了截面線的細(xì)節(jié)特征，還彌補(bǔ)了部分區(qū)域間距過(guò)大的問(wèn)題，其各項(xiàng)指標(biāo)見(jiàn)表1。

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

圖7 角度偏差法與改進(jìn)的角度偏差法精簡(jiǎn)的掃描線對(duì)比Fig.7 Comparison of Scan Lines Simplified by Angular Deviation Method and Improved Angular Deviation Method

表1 角度偏差法與改進(jìn)的角度偏差法精簡(jiǎn)后的掃描線指標(biāo)對(duì)比Tab.1 Comparison of Indicators of Scan Lines Simplified by Angular Deviation Method and Improved Angular Deviation Method

5 結(jié) 語(yǔ)

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

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

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

References：

［1］ 來(lái)興平.路基下大采空區(qū)動(dòng)力災(zāi)害監(jiān)測(cè)預(yù)報(bào)［J］.長(zhǎng)安大學(xué)學(xué)報(bào)：自然科學(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］ 計(jì) 宏，余學(xué)義，高志興，等.彬長(zhǎng)生產(chǎn)服務(wù)區(qū)下采空區(qū)穩(wěn)定性評(píng)價(jià)研究［J］.西安科技大學(xué)學(xué)報(bào)，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ū)厚黃土層采動(dòng)變形數(shù)值模擬研究［J］.西安科技大學(xué)學(xué)報(bào)，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ù)精簡(jiǎn)技術(shù)的研究［J］.西安電子科技大學(xué)學(xué)報(bào)：自然科學(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］ 吳杭彬，劉 春.三維激光掃描點(diǎn)云數(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］ 徐 尚.三維點(diǎn)云數(shù)據(jù)拼接與精簡(jiǎn)技術(shù)的研究［D］.青島：中國(guó)海洋大學(xué)，2009.XU Shang.Study on Data Registration and Reduction for 3DPoint Clouds［D］.Qingdao：Ocean University of China，2009.

［13］ 溫銀放.數(shù)據(jù)點(diǎn)云預(yù)處理及特征角點(diǎn)檢測(cè)算法研究［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］ 夏永華，方源敏，孫宏生，等.三維激光探測(cè)技術(shù)在采空區(qū)測(cè)量中的應(yīng)用與實(shí)踐［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ū)點(diǎn)云數(shù)據(jù)的小波平滑方法［J］.湖南科技大學(xué)學(xué)報(bào)：自然科學(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］ 趙 柳，馬 禮，楊銀剛，等.逆向工程中散亂點(diǎn)云數(shù)據(jù)精簡(jiǎn)研究［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é)報(bào)，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.