基于主成分分析與柵格劃分的點云壓縮算法研究?

付忠敏 張 星 孫志剛

（華中科技大學自動化學院 武漢 430074）

基于主成分分析與柵格劃分的點云壓縮算法研究?

付忠敏 張 星 孫志剛

（華中科技大學自動化學院 武漢 430074）

三維激光掃描儀可在短時間內(nèi)通過非接觸測量獲得大量高度密集的點云數(shù)據(jù)，針對大量數(shù)據(jù)導致的資源占用多和數(shù)據(jù)處理速度慢的問題，提出了一種基于主成分分析和空間柵格劃分的點云壓縮算法；該算法通過對鄰域點集作主成分分析建立點的局部特征描述子，對點云空間進行柵格劃分，在柵格內(nèi)依據(jù)點的局部特征描述子確立特征點，剔除非特征點；實驗結(jié)果表明，該算法能在保持原有模型局部細節(jié)特征的同時較大程度地壓縮點云數(shù)據(jù)。

點云壓縮；主成分分析；柵格劃分；局部特征；特征點

1 引言

三維激光掃描技術由于其非接觸性、高精度、實時性強等優(yōu)點正越來越廣泛的應用于空間場景信息的獲取中，但是，它在短時間內(nèi)通過掃描獲取到的大量包含物體表面細節(jié)特征的點云數(shù)據(jù)也給后續(xù)的數(shù)據(jù)存儲、處理、顯示和輸出帶來不便［1］。動輒十幾萬甚至上百萬的點云數(shù)據(jù)不僅會占用大量系統(tǒng)資源，而且還會影響特征點識別與表面重建等后續(xù)工作［2］。因此，在保持原始點云必要細節(jié)特征的前提下，對點云數(shù)據(jù)進行壓縮簡化顯得非常必要。

文獻［4］闡述了將點云空間劃分為均勻大小的小包圍盒，取其中心點來代替整個包圍盒中點的壓縮方法，簡單高效。但沒有考慮局部特征，容易造成細節(jié)丟失。文獻［5］提出了均勻網(wǎng)格法，將點云數(shù)據(jù)投影到平面上已經(jīng)建立好的均勻網(wǎng)格中，取中值點來代替所有點。這種方法同樣會造成細節(jié)的丟失，僅適用于點分布均勻且表面特征變化不大的點云數(shù)據(jù)。文獻［6］針對傳統(tǒng)方法在壓縮點云數(shù)據(jù)時經(jīng)常丟失過多特征點的不足，提出了基于K近鄰和法向精度的點云精簡算法，該算法能在不丟失細節(jié)特征的同時精簡點云，但運算量大，并且不適用于表面特征變化不大的普通點云數(shù)據(jù)。

本文提出了基于主成分分析與柵格劃分的點云壓縮算法，算法首先對輸入的點云數(shù)據(jù)建立鄰域索引，通過主成分分析計算點的局部特征描述子，再將點云空間劃分為均勻柵格，對柵格內(nèi)的點進行壓縮時，以點的局部特征描述子建立判斷準則，提取特征點，舍棄非特征點。

2 點云壓縮算法設計

2.1 主成分分析的原理

主成分分析（Principal Component Analysis，PCA）也稱主元分析，是一種數(shù)據(jù)分析技術，其最重要的應用是對原有的復雜數(shù)據(jù)降維［7］，揭示隱藏在復雜數(shù)據(jù)背后的簡單結(jié)構(gòu)。它的優(yōu)點是簡單，而且無參數(shù)限制，可以方便的應用于各個場合。這種數(shù)據(jù)分析方法能夠找到原始數(shù)據(jù)中最主要的成分和結(jié)構(gòu)，去除噪聲和冗余。從線性代數(shù)的角度來看，主成分分析其實就是尋找另外一組正交基來重新描述數(shù)據(jù)，使得在新的一組基下，數(shù)據(jù)在各個觀測方向上的變化趨勢能夠更明顯的呈現(xiàn)，數(shù)據(jù)沿著哪個觀測方向沿的運動最劇烈即方差最大，這個觀測方向就是最重要的“主元”。

三維激光掃描儀采集到的點一般分布在物體的表面，每個點需要用三個維度值來描述。物體表面越平滑，掃描點的分布越趨向于二維平面，采用主成分分析后，點沿表面法矢方向的變化越??；物體表面形態(tài)越復雜，變化越劇烈，點在三個維度方向上的變化越均勻即點越趨向于在三維空間中均勻分布。若樣本點都分布在物體形態(tài)大小變化明顯的位置，則樣本數(shù)據(jù)沿空間三個維度方向的變化劇烈程度相當，即方差差別很小。

點云只涉及三維空間，有三個觀測方向，為了對點云作主成分分析，先要計算得到鄰域點集的協(xié)方差矩陣 C3×3。樣本點集 P=(p1，p2，…，pk)T，其中 pi=(xi， yi， zi)T，則

協(xié)方差矩陣包含了所有觀測變量之間的相關性度量，這些相關性度量反映了數(shù)據(jù)的噪音和冗余的程度。PCA指出樣本的協(xié)方差矩陣的特征值對應各主成分的方差大小，特征向量就是樣本分布變化最劇烈的那些方向。

2.2 點云局部特征描述

原始點云數(shù)據(jù)是往往是散亂的，數(shù)據(jù)點之間的拓撲結(jié)構(gòu)是未知的［8］。對一個點的主成分分析是基于其鄰域進行的，目前，最常用的點云數(shù)據(jù)拓撲結(jié)構(gòu)分別是k鄰域以及r鄰域，如圖1所示。三維點云數(shù)據(jù)集 P={pi∈R3，i=1，2，…，n} ，點 pi的 k鄰域為點云數(shù)據(jù)集P中距離 pi最近的k個點的集合，r鄰域為點云數(shù)據(jù)集P中與 pi的距離小于r的所有點的集合。使用八叉樹和k-d樹這樣特殊的數(shù)據(jù)結(jié)構(gòu)對點云作劃分，可以加快鄰域搜索速度［9］。

圖1 k鄰域與r鄰域

為了建立點云局部特征描述量綱，取一個點的鄰域點集作主成分分析，距離目標點更近的點顯然對其局部特征有更大的影響，因此算法中使用加權協(xié)方差矩陣。對于任意點 p=(x，y，z)T，其鄰域點集為 P=(p1，p2，…，pk)T，定義點 p 的加權協(xié)方差矩陣如下：

式（3）中di表示鄰域點集P中點 pi到目標點的距離，dˉ表示點集P中所有點到目標點距離的均值。矩陣C3×3的三個特征向量構(gòu)成了線性變換后三維空間中新的坐標基，其對應的特征值從小到大依次是 λ0，λ1，λ2。定義目標點的局部特征描述子LFD（Local Feature Descriptor）：

C3×3是實對待矩陣，所以三個特征值都為正實數(shù)，則 LFD∈。以LFD為一個點的局部特征描述量綱，LFD值越小，表示該點所在的局部區(qū)域在三維空間的一個觀測方向上變化很小，即區(qū)域越趨向于二維平面；LFD越大，表示該點所屬局部區(qū)域形態(tài)特征變化越明顯，一般是物體的邊緣部分或者表面出現(xiàn)凹凸變化處或者多個物體的交匯處。

綜合以上闡述，對點云作主成分分析建立其局部特征描述量綱的步驟如下：

1）對目標點搜索其鄰域點集，k為鄰域內(nèi)點的個數(shù)，計算所有鄰域點到目標點的距離及其均值；

2）根據(jù)式（2）、（3）、（4）得到3×3加權協(xié)方差矩陣；

3）求解加權協(xié)方差矩陣的特征值，根據(jù)式（5）計算目標點的LFD。

2.3 柵格劃分

在進行點云壓縮時，為了最大程度的保存原始點云中的局部特征，壓縮處理并不是針對點云整體，而是針對小的空間柵格［11］。先將點云空間劃分為小的柵格，對柵格內(nèi)的點作壓縮處理后，再將其合并為一個總體，因此柵格劃分是點云數(shù)據(jù)壓縮的重要一環(huán)。一種較好的空間柵格劃分方法是將點云所在空間劃分為許多體積相等的立體柵格，設立體柵格的長寬高依次為L、W、H。首先求出原始點云各點坐標中沿xyz三個方向的最小最大坐標值：xmin、xmax、ymin、ymax、zmin、zmax，為了讓這些小的立體柵格的形狀與整體點云空間包圍盒的形狀一致，需要確定三個方向上合理的劃分間隔值，使原始點云模型沿空間三個坐標方向上劃分的網(wǎng)格數(shù)目相等，L、W、H需滿足式（6）。

式（7）中floor表示向下取整，點云模型所在空間根據(jù)式（7）被劃分為div_x*div_y*div_z個小的柵格。假設點云中某一點的坐標是(x，y，z)，計算其所在空間柵格的三維索引值(Ix、Iy、Iz)

為了方便柵格的快速查找，可將空間柵格線性排列［10］，如圖2 所示。根據(jù) Ix，Iy，Iz計算出柵格索引值：

根據(jù)式（9）計算所有點的柵格索引值，點云中柵格索引值相同的點都處于同一個柵格中。這種柵格劃分方法形式簡單有效，而且計算復雜度低。

圖2 空間柵格一維線性排列

2.4 點的提取和算法流程

點云壓縮的目的是希望能在降低點的數(shù)目的同時仍然能夠保留大部分的物體表面特征信息［12］。用更少的點的去展示物體表面特征信息意味著保留下的點必須比舍棄的點更有“代表性”。本文定義保留下來的點為特征點，判定一個點是否是特征點需要用到前面提出的點的局部特征描述子——LFD這個量綱。LFD越大的點，其局部特征越明顯，比其他點更具“代表性”。因此，在進行數(shù)據(jù)壓縮時，希望在點云LFD較大的區(qū)域也就是物體表面形態(tài)起伏比較大的地方保留較多的點，以更好地表達被掃描物體在該處的細節(jié)信息，而在點云LFD較小的區(qū)域也就是相對較平坦的地方保留較少的點，這樣就可以在對點云數(shù)據(jù)進行壓縮的同時最大限度地保留物體的表面特征信息。

在對柵格內(nèi)的點進行壓縮時，需要建立一個判斷標準確定哪些點是需要保留的特征點。假設點云所有點LFD的均值是avg_LFD，柵格內(nèi)的點個數(shù)為n，柵格內(nèi)所有點LFD的均值grid_avg_LFD。本文取grid_avg_LFD作為整個柵格所表示的區(qū)域局部特征是否明顯的度量，以avg_LFD作為閾值，若grid_avg_LFD≥avg_LFD，則認為整個柵格內(nèi)的點都是特征點，全部保留；反之，計算一個壓縮率CR，將柵格內(nèi)的n個點按LFD大小遞減排列，僅將前n*CR個點視為特征點予以保留。

由上述判斷標準可知，柵格壓縮率CR由點的LFD確定，二者之間存在函數(shù)關系CR=ψ(LFD)，該函數(shù)必須單調(diào)遞增，在LFD增大時，CR也增大，并且隨著LFD的增大，CR增大的趨勢要逐漸放緩。即ψ(LFD)的導函數(shù)要單調(diào)遞減。一個可以使用的壓縮率公式如下：

綜合以上，點云壓縮算法的流程如圖3所示。

結(jié)合以上流程圖，下面給出使用主成分分析與柵格劃分的方法進行點云壓縮的程序步驟：

1）讀入原始點云，建立k-d樹或八叉樹空間索引以加快點的鄰域查找；

2）遍歷點云中的所有點，選取點的一種鄰域計算加權協(xié)方差矩陣，計算LFD的值并計算全局LFD均值；

3）將點云空間劃分為N個均勻柵格，計算點的柵格索引值確定其所屬的柵格；

4）遍歷所有柵格，計算柵格內(nèi)點的LFD均值，結(jié)合壓縮率公式計算柵格壓縮率，確定柵格內(nèi)需要保留的特征點數(shù)目；

5）將所有保留下來的特征點添加到新點云中即為壓縮后點云。

圖3 點云壓縮算法流程圖

3 算法實例與實驗分析

本文實驗的軟件環(huán)境為：Windows7 64位操作系統(tǒng)，Visual Studio2013集成開發(fā)環(huán)境。點云文件的輸入輸出使用了PCL庫，矩陣運算采用Eiggen庫中的API，點的鄰域使用K鄰域，并且K=30。

實驗結(jié)果如圖4所示，圖（a）是原始的sofa點云，有82368個點，圖（b）是壓縮后的sofa點云，可以明顯看出原始點云中沙發(fā)的邊界輪廓、玩具娃娃、毛毯這些細節(jié)特征在壓縮后點云中保存完好，而較平坦的地方保留的點較少。圖（c）是原始的table點云，有156892個點，圖（d）是壓縮后的table點云，可以明顯看出壓縮后點云中桌面邊緣輪廓、杯子等局部特征明顯的地方保留了較多的點，而平坦的桌面上保留了很少的點。

實驗中，分別計算并記錄原始點云與壓縮后點云中所有點的LFD數(shù)據(jù)并繪制直方圖，圖5是原始點云與壓縮后點云LFD的分布直方圖對比。圖（a）是原始sofa點云的LFD分布直方圖，圖（b）是壓縮后sofa點云的LFD分布直方圖。圖（c）是原始table點云的LFD分布直方圖，圖（d）是壓縮后table點云的LFD分布直方圖。各直方圖中的直線指示全局LFD均值的位置。

圖4 原始點云與壓縮后點云對比

由圖5中（a）與（b）兩圖的對比可知，壓縮前LFD值小于全局均值的點占比極大，直方圖兩端相差很大。壓縮后左側(cè)LFD較小的點明顯減少，這表示壓縮過程舍棄了sofa點云中大量分布在坐墊與墊上的局部特征單一的點。壓縮后LFD均值線右移，即LFD均值變大。（c）與（d）兩圖的對比結(jié)果亦表明，壓縮后直方圖變得更加平緩，原始點云中LFD值偏小的點大幅減少，LFD值大的點被保留，這表示壓縮過程舍棄了table點云中大量分布在平坦桌面上的點。壓縮前后的數(shù)據(jù)分析結(jié)果表明，本文提出的點云壓縮原則通過算法得到了實現(xiàn)，局部特征明顯的點被保留，局部特征單一的點被舍棄。

圖5 原始點云與壓縮后點云LFD的分布直方圖對比

對兩幅點云壓縮前后的各項統(tǒng)計數(shù)據(jù)的記錄如表1。

表1 點云壓縮前后各項統(tǒng)計數(shù)據(jù)對比

4 結(jié)語

本文針對傳統(tǒng)點云壓縮算法在壓縮數(shù)據(jù)的同時不能較好地保留細節(jié)特征的問題，提出了基于主成分分析和柵格劃分的點云壓縮算法。首先對原始點云作主成分分析建立點的局部特征描述，再將點云空間劃分為立體柵格，計算柵格壓縮率，保留特征點，最后將數(shù)據(jù)壓縮后的柵格合并為一個整體得到壓縮后點云。實驗結(jié)果表明，本文提出的算法既能較大程度壓縮點云數(shù)據(jù)，又不會丟失掃描物體的表面輪廓特征，算法簡潔、效率高，適用于有較多形態(tài)變化的三維點云數(shù)據(jù)。

［1］邢正全，鄧喀中，薛繼群.基于柵格劃分和法向量估計的點云數(shù)據(jù)壓縮［J］.測繪通報，2012（7）：50-51.XING Zhengquan，DENG Kazhong，XUE Jiqun.Point Cloud Data Compression Based on Grid Division and Nor?mal Vector Estimation［J］.Bulletin of Surveying and Map?ping，2012（7）：50-51.

［2］解則曉，徐尚.三維點云數(shù)據(jù)拼接中ICP及其改進算法綜述［J］.中國海洋大學學報，2010，40（1）：99-100.XIE Zexiao，XUE Shang.A Survey on the ICP Algorithm and Its Variants in Registration of 3D Point Clouds［J］.Journal of Ocean University of China，2010，40（1）：99-100.

［3］張會霞，朱文博.三維激光掃描數(shù)據(jù)處理理論及應用［M］.北京：電子工業(yè)出版社，2012：27-31.ZHANG Huixia，ZHU Wenbo.Theory and Application of 3D Laser Scanning Data Processing［M］.Beijing：Publish?ing House of Electronics Industry，2012：27-31.

［4］K.H.Lee，H.Woo and T.Suk.Data Reduction Methods for Reverse Engineering［J］.Int J Adv Manuf Technol），2001，17：735-743

［5］Sun W，Bradley C，Zhang YF，Loh HT.Cloud data model?ing employing a unified，non-redundant triangular mesh［J］.Comput-Aided Design，2001，33（1）：83-93.

［6］Masuda T，Yokoya N.A robust method for registration and segmentation of multiple range images［C］//Quebec City，Canada：Proceeding of the 3rd International Conference on 3D Digital Imaging and Modeling，2001：254-261.

［7］張鵬.基于主成分分析的綜合評價研究［D］.南京：南京理工大學，2004：5-7.ZHANG Peng.Research on Comprehensive Evaluation Based on Principal Component Analysis［D］.Nanjing：Nanjing University of Science and Technology，2004：5-7.

［8］張順嵐，莫建文，鄒路路.基于K近鄰和法向精度的點云精簡算法［J］.武漢理工大學學報，2014，38（3）：572-575.ZHANG Shunlan，MO Jianwen，ZHOU Lulu.Point Cloud Simplification Algorithm Based on K Neighbor and Normal Accuracy［J］.Journal of Wuhan University of Technology，2014，38（3）：572-575.

［9］王振，孫志剛.散亂點云噪聲分析與降噪方法研究［J］.計算機與數(shù)字工程，2015，43（9）：1668-1672.WANG Zhen，SUN Zhigang.Denoising Methods Research on Scattered Point Cloud Based on Noise Analysis［J］.Computerand DigitalEnineering，2015，43 （9） ：1668-1672.

［10］徐翰.基于空間網(wǎng)格劃分的點云質(zhì)量檢測算法［J］.東華理工大學學報（自然科學版），2015，38（1）：88-90.XU Han.A Point Cloud Quality Detection Algorithm Based on Spatial Meshing［J］.Jounal of East China Insti?tute of Technology（Natural Science），2015，38（1）：88-90.

［11］周波，陳銀剛，顧澤元.基于八叉樹網(wǎng)格的點云數(shù)據(jù)精簡方法研究［J］.現(xiàn)代制程工程，2008（3）：64-67.ZHOU Bo，CHEN Yingang，GU Zeyuan.Research of Point Cloud Data Reduction Based on Octree Grid［J］.Modern Manufacturing Engineering，2008（3）：64-67.

［12］劉濤，徐錚，沙成梅，等.基于包圍盒法的散亂點云數(shù)據(jù)的曲率精簡［J］.科學技術與工程，2009，9（12）：3333-3335.LIU Tao，XU Zheng，SHA Chengmei，et al.Curvature Es?timation of Scattered Point Cloud Data Based on Bound?ing Box Method［J］.Science Technology and Engineer?ing，2009，9（12）：3333-3335.

Research on the Algorithm of Point Cloud Compression Based on Principal Component Analysis and Grid Divison

FU Zhongmin ZHANG XingSUN Zhigang
（School of Automation，Huazhong University of Science and Technology，Wuhan 430074）

Three dimensional laser scanner can obtain a large number of highly dense point cloud data through non-contact measurement in a short time.Aiming at the issue that the large amount of data leads to the high resource consumption and the slow data processing speed，a point cloud compression algorithem based on principal component analysis and space grid division is intro?duced.In this algorithm，local feature descriptor of point are established via principal component analysis of the neighborhood points and the point cloud space is divided into grids，the feature points defined by the local feature descriptor in the grid are retained while non-feature points are eliminated.Experimental results show that the algorithm can compress the point cloud data while pre?serving the local details of the original model.

point cloud compression，principal component analysis，grid division，local feature，feature point

Class Number TP391

TP391

10.3969/j.issn.1672-9722.2017.12.004

2017年6月4日，

2017年7月27日

付忠敏，男，碩士研究生，研究方向：三維數(shù)據(jù)處理，機器視覺與圖像處理。張星，男，碩士研究生，研究方向：三維場景重建，計算機視覺。孫志剛，男，碩士生導師，研究方向：計算機實時控制、網(wǎng)絡化控制、機器視覺與圖像處理。