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

田豐瑞　胡　榮

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

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

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

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

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

1.1　直接縮減法

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

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

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

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

圖1　均勻采樣的壓縮

圖2　k鄰域的壓縮

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

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

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

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

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

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

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

實驗數(shù)據(jù)是按垂直于Y軸方向進行的，從壓縮效果圖分析與比較，可以看出，在Y方向投影壓縮效果最好，因為信息點在該方向的重疊較少。格網(wǎng)壓縮數(shù)據(jù)統(tǒng)計見表2。

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

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

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

區(qū)域重心壓縮法又稱為均勻柵格壓縮法[7][8]，其實質(zhì)也是均勻采樣壓縮算法的一種?；驹硎牵菏紫雀鶕?jù)點云數(shù)據(jù)的6個最值(Xmax,Xmin,Ymax,Ymin,Zmax,Zmin)建立最大外包立方體，然后根據(jù)用戶指定對立方體細分柵格，最后對落入柵格內(nèi)的信息點進行重心距離采樣，將與柵格重心幾何距離最近的信息點保留下來，刪除其余點。

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

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

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

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

2　基于分層投影的特征點壓縮法

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

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

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

(1)點云分層投影

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

圖5　點云分層投影流程

(2)掃描線擬合

搜索位于同一投影面上信息點的平面坐標最值，以Z方向投影為例，比較Lx=Xmax-Xmin與Ly=Ymax-Ymin的大小，確定較大值的坐標軸方向為掃描前進方向，選用Sortrows函數(shù)對信息點進行排序。

(3)特征點提取

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

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

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

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

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

對點云數(shù)據(jù)沿坐標軸進行分層投影分割，分割效果見圖6。

以1 000層投影面分割為例，掃描目標的輪廓特征，掃描效果見圖7。

圖6　分層投影分割效果

圖7　提取目標輪廓特征的效果

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

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

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

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

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

3　結(jié)論

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

圖8　點云數(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].上海:同濟大學，2005

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

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

[5]黃承亮，吳侃，向娟.三維激光掃描點云數(shù)據(jù)壓縮方法[J].測繪科學，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ù)點云精簡中的應(yīng)用[J]. 上海大學學報，2005，11(3):242-246

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