徐 工，程效軍

（同濟(jì)大學(xué) 測(cè)繪與地理信息學(xué)院，上海200092）

三維激光掃描系統(tǒng)的采樣精度高（一般可以達(dá)到cm甚至mm級(jí)精度）［1］，尤其是隨車載／機(jī)載掃描系統(tǒng)的不斷成熟和完善，能夠快速、準(zhǔn)確地獲取目標(biāo)表面高密度點(diǎn)位信息，在獲取數(shù)據(jù)的精度和速度方面有很大的優(yōu)勢(shì)，越來越廣泛地應(yīng)用于文物建筑的保護(hù)與修復(fù)、機(jī)械制造、數(shù)字城市建設(shè)海洋測(cè)深和環(huán)境監(jiān)測(cè)等領(lǐng)域［1－2］.三維激光掃描獲取的數(shù)據(jù)非常巨大，往往達(dá)到幾十萬甚至數(shù)百萬的量級(jí)，龐大點(diǎn)云數(shù)據(jù)的存儲(chǔ)、顯示和傳輸占用了大量的時(shí)間和空間資源，而且大大降低了后續(xù)分析和處理的效率.因此，在保證一定精度的前提下，對(duì)海量點(diǎn)云數(shù)據(jù)進(jìn)行壓縮是點(diǎn)云后處理的必然選擇［1－5］.

目前散亂點(diǎn)云數(shù)據(jù)壓縮方法主要有兩種：基于網(wǎng)格的壓縮（mesh－based simplification）方法和基于點(diǎn)的 壓 縮（points－based simplification）［5－8］方 法.前者要先建立點(diǎn)云數(shù)據(jù)的三角網(wǎng)格，然后將相同頂點(diǎn)的三角面片的最大法矢夾角［9］、壓縮后點(diǎn)數(shù)和最大邊界誤差［10］、頂點(diǎn)合并的誤差代價(jià)［11］等與相應(yīng)的自定義閾值相比較，進(jìn)行取舍，對(duì)網(wǎng)格進(jìn)行簡(jiǎn)化.基于網(wǎng)格的壓縮方法壓縮效果比較好，但是構(gòu)建網(wǎng)格，尤其是構(gòu)建海量數(shù)據(jù)網(wǎng)格是一項(xiàng)復(fù)雜耗時(shí)的工作，效率低，而且沒有固定的閾值選取準(zhǔn)則，壓縮效果具有一定的隨意性.基于點(diǎn)的壓縮方法是根據(jù)點(diǎn)云的空間拓?fù)潢P(guān)系計(jì)算對(duì)應(yīng)的離散幾何信息，如平均點(diǎn)距值［12］、包圍盒點(diǎn)數(shù)［13］、均勻網(wǎng)格中心［14］、曲率［15］、非均勻網(wǎng)格特征點(diǎn)［4，12］等，根據(jù)信息量對(duì)點(diǎn)云進(jìn)行精簡(jiǎn)處理.基于點(diǎn)的壓縮方法直接簡(jiǎn)化點(diǎn)云，效率較高，但是壓縮數(shù)據(jù)在細(xì)節(jié)和特征上的損失難以避免甚至難以控制［5］.

小波變換在時(shí)間（空間）域和頻率域具有良好的局部化特性，通過小波函數(shù)的伸縮和平移，小波變換可以反映信號(hào)任意點(diǎn)處的細(xì)節(jié)信息，被譽(yù)為“數(shù)學(xué)顯微鏡”［16］.本文借助快速成型理論中的切片技術(shù)，將小波變換引入點(diǎn)云數(shù)據(jù)壓縮中，提出一種基于小波技術(shù)的自適應(yīng)壓縮算法.通過與傳統(tǒng)壓縮方法的對(duì)比，說明該算法在實(shí)現(xiàn)快速壓縮的同時(shí)能夠兼顧點(diǎn)云的細(xì)節(jié)和特征信息，而且無需設(shè)置閾值或其他的參數(shù)，有助于實(shí)現(xiàn)壓縮的自動(dòng)化.

1 小波及小波變換理論

小波變換能夠通過伸縮和平移小波函數(shù)，以不同的分辨率自適應(yīng)地逼近信號(hào).低分辨率下的小波變換可以描述信號(hào)更多的細(xì)節(jié)信息，而高分辨率下的小波變換能夠反映出較大結(jié)構(gòu)的輪廓.目前，小波變換已經(jīng)廣泛地應(yīng)用于二維及高維圖像和視頻上，也有學(xué)者正在研究將小波變換應(yīng)用于散亂點(diǎn)云處理方面［17］.

任一函數(shù)φ（t）∈L2（R），若其Fourier 變換滿足

則φ（t）稱為基本小波函數(shù)或小波母函數(shù).其中，t為時(shí)間，ω為角頻率，式（1）稱為小波函數(shù)的可容許性條件.對(duì)小波母函數(shù)φ（t）進(jìn)行平移和伸縮可得到小波基函數(shù)集

式中：a稱為尺度伸縮因子，b稱為時(shí)間平移因子.函數(shù)f∈L2（R）的連續(xù)小波變換（CWT）

從式（3）中可以看出，小波變換為“恒Q濾波”，具有自適應(yīng)性.尺度因子a決定了時(shí)（空）域和頻域窗的大小，平移因子b決定了觀測(cè)窗位置［16，18］.小波函數(shù)φa，b（t）中的尺度因子和平移因子決定了小波變換可以獲取信號(hào)任意點(diǎn)處的細(xì)節(jié)信息，因而，小波系數(shù)的起伏與突變，能夠自適應(yīng)地識(shí)別信號(hào)的特征部位.鑒于小波系數(shù)的這種特征，本文將小波變換應(yīng)用到點(diǎn)云數(shù)據(jù)壓縮，以實(shí)現(xiàn)保留特征的點(diǎn)云自適應(yīng)壓縮.

2 點(diǎn)云特征的自適應(yīng)識(shí)別

原始點(diǎn)云數(shù)據(jù)的特征保留是衡量點(diǎn)云數(shù)據(jù)壓縮算法優(yōu)劣的一個(gè)重要參數(shù).以往的算法或是根據(jù)點(diǎn)的K近鄰域［5］建立拓?fù)潢P(guān)系，計(jì)算點(diǎn)法矢、曲率與閾值的關(guān)系，判斷特征點(diǎn)；或是構(gòu)建網(wǎng)格，根據(jù)三角面片最大夾角與閾值的關(guān)系決定點(diǎn)的取舍［9］等.這些算法都依賴于閾值的選取，但是目前并不存在一個(gè)固定的閾值選取準(zhǔn)則，因而特征點(diǎn)的提取結(jié)果具有一定的隨意性.

小波系數(shù)能夠反映相鄰點(diǎn)的細(xì)節(jié)信息.若數(shù)據(jù)變化不大，即各個(gè)數(shù)據(jù)點(diǎn)相似，相應(yīng)地由式（3）計(jì)算的小波系數(shù)也相似；當(dāng)數(shù)據(jù)出現(xiàn)起伏變化時(shí)，對(duì)應(yīng)的小波系數(shù)會(huì)發(fā)生改變，從而出現(xiàn)小波系數(shù)峰值，這說明小波峰值能夠很好地反映點(diǎn)云數(shù)據(jù)的起伏變化.

假設(shè)有兩組數(shù)據(jù)，一組變化平緩，近似是一條直線，另一組有起伏變化，如圖1所示.從圖1中可以看出，平緩數(shù)據(jù)的小波系數(shù)也是平緩的，沒有峰值出現(xiàn)；起伏變化較大的一組數(shù)據(jù)，在發(fā)生變化的點(diǎn)處都出現(xiàn)了小波系數(shù)峰值.從仿真實(shí)例中可以明顯看出小波系數(shù)的峰值可以自適應(yīng)地探測(cè)數(shù)據(jù)的特征點(diǎn).

圖1 兩組數(shù)據(jù)及其對(duì)應(yīng)的小波系數(shù)Fig.1 Two sets of data and corresponding wavelet coefficients

3 算法概述

小波變換是一個(gè)一維的變換，為將小波變換引入到三維空間點(diǎn)云數(shù)據(jù)壓縮中，需要對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行降維處理，首先借助切片技術(shù)將三維空間點(diǎn)云降維為二維平面點(diǎn)集，并按順（逆）時(shí)針順序?qū)ζ矫纥c(diǎn)集進(jìn)行排序，然后對(duì)排序后的切片點(diǎn)云進(jìn)行小波變換，獲取小波系數(shù)峰值，并根據(jù)小波系數(shù)峰值自適應(yīng)地選取需要保留的點(diǎn).算法的流程如圖2所示.

圖2 算法流程圖Fig.2 Algorithm flow chart

3.1 生成切片點(diǎn)云

三維激光掃描儀能夠獲取物體表面高密度的點(diǎn)云數(shù)據(jù)，沿物體的結(jié)構(gòu)特征方向?qū)c(diǎn)云數(shù)據(jù)進(jìn)行切片，將落在切片上的數(shù)據(jù)投影到參考平面上，生成切片點(diǎn)云.經(jīng)過切片處理后，三維空間散亂點(diǎn)云轉(zhuǎn)化為能夠反映物體輪廓形狀的平面點(diǎn)集.

假 設(shè) 三 維 空 間 點(diǎn) 集p＝｛Pi＝（xi，yi，其 中Px＝｛x1，x2，…，xn｝，Py＝｛y1，y2，…，yn｝，Pz＝｛z1，z2，…，zn｝，分別表示X，Y，Z坐標(biāo)，n表示點(diǎn)的數(shù)目.假設(shè)沿掃描坐標(biāo)系的Z軸分割，分隔厚度為d，則第j層上的點(diǎn)即為Pz中滿足條件zmin＋（j－1）d≤z＜zmin＋jd的點(diǎn).從點(diǎn)集p中提取該層的點(diǎn)，并投影到相應(yīng)的參考平面上，形成輪廓形狀的切片點(diǎn)云.同樣的方法，也可以得到沿X或Y軸分割的切片點(diǎn)云.以由地面激光掃描儀獲取的華佗雕塑半身像的散亂點(diǎn)云數(shù)據(jù)為例，共69 189個(gè)點(diǎn)，沿Z軸做切片，得到的切片點(diǎn)云和其中某一單層切片如圖3所示.

3.2 保留特征的點(diǎn)云自適應(yīng)壓縮

空間散亂分布的三維點(diǎn)云經(jīng)過切片處理后，轉(zhuǎn)化為以切片形式存在的二維平面點(diǎn)集.小波系數(shù)反映的是相鄰若干數(shù)據(jù)的細(xì)節(jié)信息，從而需要對(duì)每個(gè)切片點(diǎn)云按照輪廓形狀，以順時(shí)針或逆時(shí)針的順序進(jìn)行排序，對(duì)排序后的數(shù)據(jù)進(jìn)行小波變換，根據(jù)小波系數(shù)峰值選取需要保留的點(diǎn).對(duì)圖3c的切片保留特征的壓縮結(jié)果如圖4所示，切片點(diǎn)云采用的是順時(shí)針排序.對(duì)所有的切片都進(jìn)行相同的處理，可得到該點(diǎn)云數(shù)據(jù)的壓縮結(jié)果.

圖4 單層切片點(diǎn)云和保留點(diǎn)云示意圖Fig.4 Single slicing and point cloud retention

4 算例分析

點(diǎn)云數(shù)據(jù)壓縮算法基本原則是在保證失真較小的情況下，最大限度地壓縮點(diǎn)云數(shù)量，并在此基礎(chǔ)上要求算法穩(wěn)健、執(zhí)行效率高、適應(yīng)性強(qiáng).一般而言，壓縮率越高，保留的數(shù)據(jù)量越少，細(xì)節(jié)特征損失相對(duì)越多.下面通過實(shí)驗(yàn)討論了切片分割厚度對(duì)算法的影響，以期獲得最佳的切片分割厚度，并與傳統(tǒng)壓縮方法進(jìn)行比較，說明本文算法在壓縮率相同的情況下，能夠保留更多的細(xì)節(jié)信息，失真較小.

4.1 分割厚度的選取

對(duì)原始點(diǎn)云做切片處理時(shí)，若切片的分割厚度d過大，投影時(shí)容易造成細(xì)節(jié)特征覆蓋，損失數(shù)據(jù)特征信息；若分割厚度d過小，投影平面上的輪廓線容易出現(xiàn)空缺，在進(jìn)行特征提取時(shí)，會(huì)將空缺的端點(diǎn)作為特征點(diǎn)保留，降低壓縮率.因此切片厚度的選擇和點(diǎn)云數(shù)據(jù)的采樣間隔密切相關(guān).綜合考慮細(xì)節(jié)覆蓋和輪廓線空缺問題，設(shè)計(jì)了多組實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明切片厚度按以下的方式選取時(shí)，可以較好地避免上述問題.

（1）若切片厚度小于2倍的采樣間隔時(shí)，將落在該切片上的點(diǎn)全部投影到參考平面上.

（2）若切片厚度大于等于2倍采樣間隔時(shí)，只取一半切片厚度的點(diǎn)投影到參考平面上，由于切片相對(duì)較薄，因而可以自由地選取一半切片厚度的點(diǎn)，可以是切片的上（或下）半部分，也可以是切片中間部分，對(duì)壓縮效果影響不大.

圖3所示的華佗半身像，采樣間隔為0.3cm.表1是分隔厚度分別取為0.3，0.5，0.6，0.8，1.0，1.2，1.5cm 時(shí)，對(duì)應(yīng)的壓縮率和壓縮時(shí)間統(tǒng)計(jì)，其中壓縮時(shí)間是在Matlab平臺(tái)上的運(yùn)行時(shí)間.

表1 不同分割厚度對(duì)應(yīng)的壓縮率和壓縮時(shí)間Tab.1 Reduction ratio and time in different split thickness

由表1可以看出，當(dāng)分割厚度小于2倍的采樣間隔時(shí)，壓縮率隨著分割厚度的增加而提高；當(dāng)分割厚度大于等于2倍的采樣間隔時(shí)，壓縮率較高，其中分割厚度為0.8cm 時(shí)，壓縮率出現(xiàn)的微小差異（量級(jí)為10－3）是由點(diǎn)云數(shù)據(jù)的散亂程度引起的，綜合來說壓縮率變化幅度較小，表明該算法對(duì)分割厚度的依賴相對(duì)較弱.

圖5是針對(duì)上述實(shí)驗(yàn)對(duì)象，采用本文算法取不同分割厚度時(shí)對(duì)應(yīng)的點(diǎn)云壓縮效果.

通過圖5 可以看出，當(dāng)分割厚度取0.3，0.5，0.6，0.8，1.0cm 時(shí)，壓縮效果均較好，較大程度地保留了特征信息，但是分割厚度為0.3，0.5cm 時(shí)，壓縮率偏低，壓縮時(shí)間較長(zhǎng)，因此，分割厚度為0.6，0.8，1.0cm 時(shí)，壓縮效果較為理想.

圖6是利用圖5中的壓縮點(diǎn)云數(shù)據(jù)建立的網(wǎng)格模型.

由圖6 可以看出，分割厚度小于等于1.0cm時(shí)，網(wǎng)格模型的細(xì)節(jié)和特征信息保留較好，當(dāng)分割厚度大于1.2cm 時(shí)，眼睛、方巾的褶皺等部位的細(xì)節(jié)和特征信息損失嚴(yán)重.

通過表1、圖5和6壓縮效果分析可以得出，采用本文算法的壓縮率較高，細(xì)節(jié)特征保留好，失真小，壓縮時(shí)間快.綜合壓縮率和網(wǎng)格模型效果，建議分割厚度取為2～3倍的點(diǎn)云采樣間隔.

4.2 與傳統(tǒng)方法的比較

為了進(jìn)一步說明本文算法，分別采用曲率估算法、均勻網(wǎng)格法、隨機(jī)采樣法對(duì)華佗半身像進(jìn)行壓縮.在壓縮率均為86%時(shí)，三種方法點(diǎn)云壓縮效果和網(wǎng)格模型分別如圖7和8所示.

從圖5～8可以看出，在壓縮率均為86%時(shí)，從點(diǎn)云壓縮效果和壓縮后網(wǎng)格模型上都反映出本文算法在特征保留上具有明顯的優(yōu)勢(shì)，在眼睛、鼻子、上嘴唇、方巾的褶皺等特征部位保留了更多的細(xì)節(jié)信息，壓縮效果更為理想.

5 結(jié)語

本文借助快速成型理論中的切片技術(shù)，將小波變換引入點(diǎn)云數(shù)據(jù)壓縮，提出基于小波技術(shù)的散亂點(diǎn)云自適應(yīng)壓縮算法.該算法實(shí)現(xiàn)簡(jiǎn)便、計(jì)算效率高，同時(shí)又最大限度地保留了細(xì)節(jié)和特征信息.通過實(shí)驗(yàn)表明切片的分割厚度選為采樣間隔的2～3倍時(shí)，可以實(shí)現(xiàn)快速高質(zhì)量的散亂點(diǎn)云壓縮，與曲率估算法、均勻網(wǎng)格法、隨機(jī)采樣法的壓縮效果進(jìn)行對(duì)比，表明本文算法在特征保留上具有明顯的優(yōu)勢(shì)，壓縮效果更為理想，且無需設(shè)置閾值或其他參數(shù)，可以自適應(yīng)地選取需要保留的細(xì)節(jié)和特征點(diǎn)，有助于實(shí)現(xiàn)壓縮的自動(dòng)化.

［1］ 吳航彬，劉春.三維激光掃描點(diǎn)云數(shù)據(jù)的空間壓縮［J］.遙感信息，2006（2）：22.WU Hangbin，LIU Chun.Spatial compression of point cloud data from three dimension laser scanning［J］.Remote Sensing Information，2006（2）：22.

［2］ Schnabel R W，Moser S，Klein R.Fast vector quantization for efficient rendering of compressed point－clouds［J］.Computers ＆Graphics，2008，32：246.

［3］ 程效軍，李偉英，張小虎.基于自適應(yīng)八叉樹的點(diǎn)云數(shù)據(jù)壓縮方法研究［J］.河南科學(xué)，2010，28（10）：1300.CHENG Xiaojun，LI Weiying，ZHANG Xiaohu.Adaptive Octree－based data compression method for points cloud data［J］.Henan Science，2010，28（10）：1300.

［4］ 王秀英，劉錫國(guó).逆向設(shè)計(jì)中點(diǎn)云數(shù)據(jù)處理技術(shù)的研究進(jìn)展［J］.機(jī)械設(shè)計(jì)與制造，2009（9）：191.WANG Xiuying，LIU Xiguo.Development of research on point cloud data processing technology in reverse design［J］.Machinery Design ＆Manufacture，2009（9）：191.

［5］ 張鴻飛.基于散亂點(diǎn)云三維重建的關(guān)鍵技術(shù)研究［D］.上海：同濟(jì)大學(xué)，2011.ZHANG Hongfei.Study of 3D reconstruction key technology based on scattered point cloud ［D］.Shanghai： Tongji University，2011.

［6］ Luebke D P.A developer’s survey of polygonal simplification algorithms［J］.IEEE Computer Graphics ＆Applications，2001，21（3）：24.

［7］ Cignoni P，Montani C，Scopigno R.A comparison of mesh simplification algorithms［J］.Computers ＆Graphics，1998，22（1）：37.

［8］ Erikson C.Polygonal simplification：an overview.Department of computer science［R］.Chapel Hill：University of North Carolina，1996.

［9］ 劉春，吳杭彬.基于真三維TIN 的三維激光掃描數(shù)據(jù)壓縮方法［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2006，31（10）：908.LIU Chun，WU Hangbin.Compression method for three dimension laser scanning data based on 3D triangulated irregular network［J］.Geomatics and Information Science of Wuhan University，2006，31（10）：908.

［10］ Chen Y H，Ng C T，Wang Y Z.Data reduction in integrated reverse engineering and Rapid Prototyping［J］.International Journal of Computer Integrated Manufacturing，1999，2（12）：97.

［11］ 葉建輝，李德華.三維激光掃描數(shù)據(jù)的網(wǎng)格簡(jiǎn)化［J］.紅外與激光工程，2002，31（6）：522.YE Jianhui，LI Dehua.Mesh simplification of 3D laser scanned data［J］.Infrared and Laser Engineering，2002，31（6）：522.

［12］ Weir D J，Milrou M J，Bradley C.Reverse engineering physical models employing wrap－around B－spline surfaces and quadrics［J］.Journal of Engineering Manufacture，1996，210（B）：145.

［13］ Sun W，Bradley C，Zhang Y F.Cloud data modeling employing a unified non－redundant triangle mesh ［J］.Computer Aided Design，2001，33（2）：183.

［14］ Martin R，Stroud I，Marshal A.Data reduction for reverse engineering［R］.［S.l.］：Computer and Automation Institute of Hungarian Academy of Science，1996.

［15］ 賀美芳.基于散亂點(diǎn)云數(shù)據(jù)的曲面重建關(guān)鍵技術(shù)研究［D］.南京：南京航空航天大學(xué)機(jī)電學(xué)院，2006.HE Meifang. Research on key technologies of surfaces reconstruction based on scattered point cloud data［D］.Nanjing：Nanjing University of Aeronautics and Astronautics Mechanical and Electrical Institute，2006.

［16］ 崔錦泰.小波分析導(dǎo)論［M］.西安：西安交通大學(xué)出版社，1995.CUI Jintai.An introduction to wavelet analysis［M］.Xi’an：Xi’an Jiaotong University Press，1995.

［17］ Liu C，Pei W.Wavelet transform based 3D scattered data processing in binocular micro stereovision system［J］.Key Engineering Materials，2005，291／292：673.

［18］ 李建平.小波分析信息傳輸基礎(chǔ)［M］.北京：國(guó)防工業(yè)出版社，2004.LI Jianping.Wavelet analysis and information transmission［M］.Beijing：National Defence Industry Press，2004.