付忠敏 張 星 孫志剛

（華中科技大學(xué)自動(dòng)化學(xué)院 武漢 430074）

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

付忠敏 張 星 孫志剛

（華中科技大學(xué)自動(dòng)化學(xué)院 武漢 430074）

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

點(diǎn)云壓縮；主成分分析；柵格劃分；局部特征；特征點(diǎn)

1 引言

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

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

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

2 點(diǎn)云壓縮算法設(shè)計(jì)

2.1 主成分分析的原理

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

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

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

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

2.2 點(diǎn)云局部特征描述

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

圖1 k鄰域與r鄰域

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

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

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

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

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

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

3）求解加權(quán)協(xié)方差矩陣的特征值，根據(jù)式（5）計(jì)算目標(biāo)點(diǎn)的LFD。

2.3 柵格劃分

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

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

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

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

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

2.4 點(diǎn)的提取和算法流程

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

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

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

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

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

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

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

3）將點(diǎn)云空間劃分為N個(gè)均勻柵格，計(jì)算點(diǎn)的柵格索引值確定其所屬的柵格；

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

5）將所有保留下來(lái)的特征點(diǎn)添加到新點(diǎn)云中即為壓縮后點(diǎn)云。

圖3 點(diǎn)云壓縮算法流程圖

3 算法實(shí)例與實(shí)驗(yàn)分析

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

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

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

圖4 原始點(diǎn)云與壓縮后點(diǎn)云對(duì)比

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

圖5 原始點(diǎn)云與壓縮后點(diǎn)云LFD的分布直方圖對(duì)比

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

表1 點(diǎn)云壓縮前后各項(xiàng)統(tǒng)計(jì)數(shù)據(jù)對(duì)比

4 結(jié)語(yǔ)

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

［1］邢正全，鄧喀中，薛繼群.基于柵格劃分和法向量估計(jì)的點(diǎn)云數(shù)據(jù)壓縮［J］.測(cè)繪通報(bào)，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］解則曉，徐尚.三維點(diǎn)云數(shù)據(jù)拼接中ICP及其改進(jìn)算法綜述［J］.中國(guó)海洋大學(xué)學(xué)報(bào)，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］張會(huì)霞，朱文博.三維激光掃描數(shù)據(jù)處理理論及應(yīng)用［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］張鵬.基于主成分分析的綜合評(píng)價(jià)研究［D］.南京：南京理工大學(xué)，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近鄰和法向精度的點(diǎn)云精簡(jiǎn)算法［J］.武漢理工大學(xué)學(xué)報(bào)，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］王振，孫志剛.散亂點(diǎn)云噪聲分析與降噪方法研究［J］.計(jì)算機(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)格劃分的點(diǎn)云質(zhì)量檢測(cè)算法［J］.東華理工大學(xué)學(xué)報(bào)（自然科學(xué)版），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］周波，陳銀剛，顧澤元.基于八叉樹(shù)網(wǎng)格的點(diǎn)云數(shù)據(jù)精簡(jiǎn)方法研究［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］劉濤，徐錚，沙成梅，等.基于包圍盒法的散亂點(diǎn)云數(shù)據(jù)的曲率精簡(jiǎn)［J］.科學(xué)技術(shù)與工程，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ù)處理，機(jī)器視覺(jué)與圖像處理。張星，男，碩士研究生，研究方向：三維場(chǎng)景重建，計(jì)算機(jī)視覺(jué)。孫志剛，男，碩士生導(dǎo)師，研究方向：計(jì)算機(jī)實(shí)時(shí)控制、網(wǎng)絡(luò)化控制、機(jī)器視覺(jué)與圖像處理。