基于分層投影的特征點(diǎn)點(diǎn)云數(shù)據(jù)壓縮算法研究

田豐瑞　胡　榮

(1.中鐵工程設(shè)計(jì)咨詢集團(tuán)有限公司，北京　100055；2.華中科技大學(xué)文華學(xué)院，湖北武漢　430074)

三維激光掃描技術(shù)在數(shù)字三維建模方面已得到越來(lái)越多的應(yīng)用。一般三維激光掃描得到的數(shù)據(jù)都會(huì)有數(shù)十萬(wàn)到上百萬(wàn)個(gè)點(diǎn)，為海量數(shù)據(jù)。如果直接將原始的點(diǎn)云數(shù)據(jù)用于數(shù)字建模，不僅要求處理速度和計(jì)算能力較高的計(jì)算機(jī)，而且會(huì)影響后續(xù)數(shù)據(jù)處理的工作效率。同時(shí)，構(gòu)造的三維模型常包含很多冗余信息。為了提高數(shù)據(jù)后處理的工作效率并得到合適分辨率的數(shù)字模型，需要在保證數(shù)據(jù)幾何信息不大量丟失的前提下對(duì)原始點(diǎn)云數(shù)據(jù)進(jìn)行重采樣，即點(diǎn)云數(shù)據(jù)壓縮。

為了避免因存儲(chǔ)信息點(diǎn)之間的連通性而帶來(lái)的存儲(chǔ)消耗和信息冗余，以散亂點(diǎn)云數(shù)據(jù)為處理對(duì)象，N Dyn，M S Floater，A Iske[1]等人在2000年提出了一種雙變量適應(yīng)性壓縮方法，該算法可以獲得與原始點(diǎn)云所表達(dá)的物體表面相接近的效果；鄭德華[2][3]在2005年提出了直接縮減法；吳杭彬，劉春[4]在2006年提出格網(wǎng)數(shù)據(jù)壓縮法；黃承亮，吳侃，向娟[5]在2009年提出了區(qū)域重心數(shù)據(jù)壓縮法等。這些傳統(tǒng)的散亂點(diǎn)云壓縮算法都是基于數(shù)理統(tǒng)計(jì)的思想對(duì)數(shù)據(jù)進(jìn)行均勻采樣，壓縮過(guò)程很少顧及信息點(diǎn)之間的幾何關(guān)聯(lián)，并且隨著壓縮程度的增大，會(huì)造成數(shù)據(jù)壓縮結(jié)果的邊界及曲面特征信息嚴(yán)重丟失，進(jìn)而影響模型構(gòu)建的后續(xù)操作。在對(duì)常用的點(diǎn)云數(shù)據(jù)壓縮算法進(jìn)行研究的基礎(chǔ)上，提出并實(shí)現(xiàn)了一種基于分層投影的特征點(diǎn)壓縮算法，該算法可有效地解決這些問(wèn)題并提高數(shù)據(jù)壓縮率。

1　常用的點(diǎn)云數(shù)據(jù)壓縮方法

本文將對(duì)常用的點(diǎn)云壓縮算法進(jìn)行概述，并采用MATLAB平臺(tái)實(shí)現(xiàn)，結(jié)合現(xiàn)有的三維激光掃描數(shù)據(jù)進(jìn)行實(shí)例分析。實(shí)驗(yàn)數(shù)據(jù)屬于散亂點(diǎn)云數(shù)據(jù)，共包含242 526個(gè)信息點(diǎn)。

1.1　直接縮減法

(1)基于均勻采樣的壓縮算法

根據(jù)用戶設(shè)定的壓縮率(λ)對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行壓縮，即每λ個(gè)信息點(diǎn)僅保留1個(gè)點(diǎn)。壓縮效果見(jiàn)圖1(b)和圖1(c)，與原始數(shù)據(jù)相比(見(jiàn)圖1(a))，壓縮率越低，邊緣特征數(shù)據(jù)丟失更為嚴(yán)重。

(2)基于k鄰域的壓縮算法

針對(duì)點(diǎn)云數(shù)據(jù)，計(jì)算每個(gè)點(diǎn)與其他點(diǎn)的空間距離并比較大小，將與其距離最近的k個(gè)點(diǎn)建立聯(lián)系，稱(chēng)為k鄰域。k鄰域建立以后，以此為基礎(chǔ)進(jìn)行數(shù)據(jù)壓縮。壓縮時(shí)既可以按距離進(jìn)行簡(jiǎn)化，即在每個(gè)點(diǎn)的k鄰域內(nèi)去除所有距離小于給定閾值的點(diǎn)；也可以按點(diǎn)數(shù)進(jìn)行簡(jiǎn)化，即遍歷所有點(diǎn)的鄰域信息，然后刪除點(diǎn)云中距離最近的兩個(gè)點(diǎn)中的一個(gè)，直到達(dá)到要求為止。實(shí)例分析中k=20按距離50 mm和100 mm的壓縮效果見(jiàn)圖2(a)和圖2(b)。

圖1　均勻采樣的壓縮

圖2　k鄰域的壓縮

直接縮減法數(shù)據(jù)統(tǒng)計(jì)見(jiàn)表1，其中，“-”表示數(shù)據(jù)無(wú)法獲取。均勻壓縮算法的理論壓縮率為λ′=1/λ。

圖3　格網(wǎng)壓縮效果

表1　直接縮減法數(shù)據(jù)統(tǒng)計(jì)

與基于均勻采樣的壓縮法相比較，基于k鄰域的壓縮算法更能體現(xiàn)空間實(shí)體的表面特征。

1.2　格網(wǎng)數(shù)據(jù)壓縮法

該算法采用中值濾波的方式對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行壓縮[6]。處理原理是：將點(diǎn)云數(shù)據(jù)投影到已進(jìn)行均勻格網(wǎng)劃分的平面上，然后計(jì)算每個(gè)信息點(diǎn)到該平面的幾何距離，最后以格網(wǎng)為單位，按中值濾波的要求篩選出幾何距離位于中間值的信息點(diǎn)，將其余點(diǎn)刪除，實(shí)現(xiàn)數(shù)據(jù)壓縮。

投影面內(nèi)格網(wǎng)均按照300×300進(jìn)行劃分，數(shù)據(jù)壓縮效果見(jiàn)圖3(a)、圖3(b)和圖3(c)。

實(shí)驗(yàn)數(shù)據(jù)是按垂直于Y軸方向進(jìn)行的，從壓縮效果圖分析與比較，可以看出，在Y方向投影壓縮效果最好，因?yàn)樾畔Ⅻc(diǎn)在該方向的重疊較少。格網(wǎng)壓縮數(shù)據(jù)統(tǒng)計(jì)見(jiàn)表2。

表2　格網(wǎng)壓縮數(shù)據(jù)統(tǒng)計(jì)

其中，格網(wǎng)壓縮的理論壓縮率為網(wǎng)格數(shù)與原始點(diǎn)云信息點(diǎn)數(shù)的比值。

1.3　區(qū)域重心數(shù)據(jù)壓縮法

區(qū)域重心壓縮法又稱(chēng)為均勻柵格壓縮法[7][8]，其實(shí)質(zhì)也是均勻采樣壓縮算法的一種。基本原理是：首先根據(jù)點(diǎn)云數(shù)據(jù)的6個(gè)最值(Xmax,Xmin,Ymax,Ymin,Zmax,Zmin)建立最大外包立方體，然后根據(jù)用戶指定對(duì)立方體細(xì)分柵格，最后對(duì)落入柵格內(nèi)的信息點(diǎn)進(jìn)行重心距離采樣，將與柵格重心幾何距離最近的信息點(diǎn)保留下來(lái)，刪除其余點(diǎn)。

圖4　區(qū)域重心壓縮效果

本次實(shí)例分析取了三種方式細(xì)分柵格，壓縮效果見(jiàn)圖4，數(shù)據(jù)統(tǒng)計(jì)見(jiàn)表3。

表3　區(qū)域重心數(shù)據(jù)壓縮統(tǒng)計(jì)

與直接縮減法和格網(wǎng)數(shù)據(jù)壓縮法相比，區(qū)域重心數(shù)據(jù)壓縮法的壓縮效果最能保留原點(diǎn)云數(shù)據(jù)的整體特征。但由于三維激光掃描數(shù)據(jù)為面采樣數(shù)據(jù)，在進(jìn)行柵格細(xì)分時(shí)，會(huì)產(chǎn)生很多空白柵格(即不包含信息點(diǎn)的柵格)，因此其實(shí)際壓縮率也最難控制。

2　基于分層投影的特征點(diǎn)壓縮法

經(jīng)過(guò)上文的實(shí)例分析與比較，直接縮減法易丟失特征點(diǎn)，格網(wǎng)數(shù)據(jù)壓縮法實(shí)際壓縮率低，區(qū)域重心數(shù)據(jù)壓縮法能獲得較好的壓縮效果，但是實(shí)際壓縮率難以控制。對(duì)此，本文提出一種基于分層投影的特征點(diǎn)壓縮算法，該算法首先通過(guò)分層投影的方法將散亂點(diǎn)云數(shù)據(jù)分別沿X、Y、Z三個(gè)方向擬合成掃描線點(diǎn)云，然后以曲率為篩選標(biāo)準(zhǔn)對(duì)信息點(diǎn)進(jìn)行特征提取。采用單一方向投影壓縮會(huì)導(dǎo)致信息點(diǎn)在投影方向發(fā)生位置重疊而出現(xiàn)數(shù)據(jù)空洞，為了克服這一缺陷，利用數(shù)據(jù)融合的方法將三個(gè)坐標(biāo)軸方向上的階段性結(jié)果統(tǒng)一為壓縮成果。

2.1　算法流程與實(shí)現(xiàn)

本文提出的基于分層投影的特征點(diǎn)壓縮算法主要可分為四個(gè)階段，其具體實(shí)現(xiàn)流程如下。

(1)點(diǎn)云分層投影

將點(diǎn)云數(shù)據(jù)讀入一個(gè)n×3矩陣并查找信息點(diǎn)中的坐標(biāo)最值，(Xmax,Xmin,Ymax,Ymin,Zmax,Zmin)以坐標(biāo)最值為基礎(chǔ)進(jìn)行分層投影，投影流程見(jiàn)圖5。

圖5　點(diǎn)云分層投影流程

(2)掃描線擬合

搜索位于同一投影面上信息點(diǎn)的平面坐標(biāo)最值，以Z方向投影為例，比較Lx=Xmax-Xmin與Ly=Ymax-Ymin的大小，確定較大值的坐標(biāo)軸方向?yàn)閽呙枨斑M(jìn)方向，選用Sortrows函數(shù)對(duì)信息點(diǎn)進(jìn)行排序。

(3)特征點(diǎn)提取

點(diǎn)云數(shù)據(jù)信息點(diǎn)處的曲率大小表征了該掃描對(duì)象對(duì)應(yīng)部位的曲面構(gòu)造情況，可以通過(guò)信息點(diǎn)的曲率關(guān)系進(jìn)行點(diǎn)云數(shù)據(jù)的特征點(diǎn)提取，包括大曲率點(diǎn)及輪廓點(diǎn)。為避免曲率求解過(guò)程中的矩陣求逆操作，本文采用圓擬合的方式進(jìn)行信息點(diǎn)的曲率計(jì)算。

(4)數(shù)據(jù)融合

將分別沿X、Y、Z方向提取出的特征點(diǎn)進(jìn)行融合。數(shù)據(jù)融合時(shí)，首先將三個(gè)坐標(biāo)軸方向上的階段性結(jié)果合并起來(lái)，然后選用unique函數(shù)將數(shù)據(jù)中重復(fù)的信息點(diǎn)剔除，生成最終輸出結(jié)果。算法的理論壓縮率為

式中T為分割投影面層數(shù)，N為原始點(diǎn)云數(shù)據(jù)量，a為曲率壓縮比，即每a個(gè)點(diǎn)選取一個(gè)曲率最大點(diǎn)。

2.2　實(shí)例結(jié)果分析與比較

對(duì)點(diǎn)云數(shù)據(jù)沿坐標(biāo)軸進(jìn)行分層投影分割，分割效果見(jiàn)圖6。

以1 000層投影面分割為例，掃描目標(biāo)的輪廓特征，掃描效果見(jiàn)圖7。

圖6　分層投影分割效果

圖7　提取目標(biāo)輪廓特征的效果

以擬合掃描線為單位，計(jì)算信息點(diǎn)的曲率，并結(jié)合用戶指定的曲率壓縮比a(取a=10)，篩選曲面特征點(diǎn)。

將得到的輪廓特征數(shù)據(jù)與曲面特征數(shù)據(jù)再次進(jìn)行融合，構(gòu)成點(diǎn)云數(shù)據(jù)的壓縮結(jié)果，效果見(jiàn)圖8。

壓縮過(guò)程的數(shù)據(jù)統(tǒng)計(jì)如表4所示。

表4　壓縮結(jié)果數(shù)據(jù)統(tǒng)計(jì)

從數(shù)據(jù)壓縮效果圖及數(shù)據(jù)壓縮統(tǒng)計(jì)表可以看出，基于分層投影的特征點(diǎn)壓縮法能較好地解決直接縮減法邊緣數(shù)據(jù)丟失的問(wèn)題，同時(shí)，與能較好保留邊緣特征的區(qū)域重心數(shù)據(jù)壓縮法(數(shù)據(jù)壓縮率為17.57%)相比，數(shù)據(jù)壓縮效果更好，為后續(xù)的數(shù)據(jù)配準(zhǔn)工作節(jié)約時(shí)間。

3　結(jié)論

三維激光掃描技術(shù)以其快速獲取大量數(shù)據(jù)等優(yōu)勢(shì)給三維建模工作帶來(lái)極大的便利，如何對(duì)點(diǎn)云數(shù)據(jù)進(jìn)行適當(dāng)?shù)膲嚎s，則是國(guó)內(nèi)外研究的重點(diǎn)之一。本文針對(duì)混亂點(diǎn)云數(shù)據(jù)，分析對(duì)比了各類(lèi)方法的壓縮效率和效果，并在此基礎(chǔ)上提出及實(shí)現(xiàn)了一種基于分層投影的特征點(diǎn)壓縮算法。試驗(yàn)證明，該算法充分考慮到空間實(shí)體的幾何特征，使得壓縮結(jié)果具有較強(qiáng)的針對(duì)性，可有效地保留點(diǎn)云數(shù)據(jù)的輪廓及曲面信息，在后續(xù)的點(diǎn)云數(shù)據(jù)配準(zhǔn)工作中，以這些特征點(diǎn)為基礎(chǔ)搜索鄰近點(diǎn)對(duì)，可大大提高數(shù)字建模的時(shí)間效率。

圖8　點(diǎn)云數(shù)據(jù)壓縮效果

[1]N Dyn， M S Floater， A Iske. Adaptive Thinning for Bivariate Scattered Data[J]. Journal of Computational and Applied Mathematics， 2000，33：43-58

[2]鄭德華. 三維激光掃描數(shù)據(jù)處理的理論與方法[D].上海:同濟(jì)大學(xué)，2005

[3]鄭德華. 點(diǎn)云數(shù)據(jù)直接縮減方法及縮減效果研究[J].測(cè)繪工程，2006，15(4):27-30

[4]吳杭彬，劉春.三維激光掃描點(diǎn)云數(shù)據(jù)的空間壓縮[J].遙感信息，2006，2：22-24

[5]黃承亮，吳侃，向娟.三維激光掃描點(diǎn)云數(shù)據(jù)壓縮方法[J].測(cè)繪科學(xué)，2009，34(2):142-144

[6]R R Martin， I A Stroud， A D Marshall. Data reduction for reverse engineering[R]. Deliverable Document Copernicus project， Computer and Automation Institute of Hungarian Academy of Science， January 1996．

[7]朱冒冒，馮祖軍，郭建華，等.三維柵格法在數(shù)據(jù)點(diǎn)云精簡(jiǎn)中的應(yīng)用[J]. 上海大學(xué)學(xué)報(bào)，2005，11(3):242-246

[8]張麗艷，周儒榮，蔡煒斌，等.海量測(cè)量數(shù)據(jù)簡(jiǎn)化技術(shù)研究[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2001，13(11):1019-1023