基于分層投影的特征點點云數據壓縮算法研究

田豐瑞　胡　榮

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

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

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

1　常用的點云數據壓縮方法

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

1.1　直接縮減法

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

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

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

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

圖1　均勻采樣的壓縮

圖2　k鄰域的壓縮

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

圖3　格網壓縮效果

表1　直接縮減法數據統計

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

1.2　格網數據壓縮法

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

投影面內格網均按照300×300進行劃分，數據壓縮效果見圖3(a)、圖3(b)和圖3(c)。

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

表2　格網壓縮數據統計

其中，格網壓縮的理論壓縮率為網格數與原始點云信息點數的比值。

1.3　區域重心數據壓縮法

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

圖4　區域重心壓縮效果

本次實例分析取了三種方式細分柵格，壓縮效果見圖4，數據統計見表3。

表3　區域重心數據壓縮統計

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

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

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

2.1　算法流程與實現

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

(1)點云分層投影

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

圖5　點云分層投影流程

(2)掃描線擬合

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

(3)特征點提取

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

(4)數據融合

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

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

2.2　實例結果分析與比較

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

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

圖6　分層投影分割效果

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

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

將得到的輪廓特征數據與曲面特征數據再次進行融合，構成點云數據的壓縮結果，效果見圖8。

壓縮過程的數據統計如表4所示。

表4　壓縮結果數據統計

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

3　結論

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

圖8　點云數據壓縮效果

[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]鄭德華. 三維激光掃描數據處理的理論與方法[D].上海:同濟大學，2005

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

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

[5]黃承亮，吳侃，向娟.三維激光掃描點云數據壓縮方法[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]朱冒冒，馮祖軍，郭建華，等.三維柵格法在數據點云精簡中的應用[J]. 上海大學學報，2005，11(3):242-246

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