基于數(shù)據(jù)類型轉(zhuǎn)換的點云快速有損壓縮算法

律　帥， 達(dá)飛鵬， 黃　源

(東南大學(xué)自動化學(xué)院，江蘇 南京 210096)

基于數(shù)據(jù)類型轉(zhuǎn)換的點云快速有損壓縮算法

律帥， 達(dá)飛鵬， 黃源

(東南大學(xué)自動化學(xué)院，江蘇 南京 210096)

針對海量三維點云數(shù)據(jù)為計算機存儲和傳輸增加沉重負(fù)擔(dān)的問題，提出一種基于數(shù)據(jù)類型轉(zhuǎn)換的點云快速有損壓縮算法。首先設(shè)計出一種數(shù)據(jù)類型轉(zhuǎn)化規(guī)則-FtoI規(guī)則，根據(jù) FtoI規(guī)則將浮點數(shù)類型點云轉(zhuǎn)換成整數(shù)類型點云，然后將整數(shù)類型點云切分成許多小單元面塊，每一單元點云生成最小生成樹，按廣度優(yōu)先的順序?qū)湫谓Y(jié)構(gòu)進行編碼。同時，按照樹形結(jié)構(gòu)對父子節(jié)點的差值進行編碼，把整型差值分成兩部分編碼，符號一部分，其絕對值一部分，其中絕對值部分采用算術(shù)編碼進行壓縮。實驗表明該文算法在保證整個三維點云模型的質(zhì)量情況下，具有不錯的壓縮速度和壓縮率。

三維點云；有損壓縮；浮點數(shù)；最小生成樹；算術(shù)編碼

點云數(shù)據(jù)是物體三維掃描后其三維坐標(biāo)的數(shù)據(jù)信息，還可能記錄了RGB、深度等信息。隨著三維掃描系統(tǒng)精度和速度的提升，掃描后點云數(shù)據(jù)量將達(dá)到幾百萬甚至更大的數(shù)量級，對其網(wǎng)格化的時間開銷增大，網(wǎng)格化模型的內(nèi)存開銷也隨之增大，管理操作網(wǎng)格拓?fù)湫畔⒋嬖谥T多問題，計算機在處理多邊形網(wǎng)格模型的復(fù)雜度急劇增加；此外，當(dāng)多邊形網(wǎng)格模型在屏幕中網(wǎng)格數(shù)量大于屏幕分辨率時，用點作為模型數(shù)據(jù)的基本單元比多邊形網(wǎng)格有更加明顯的效率優(yōu)勢。因此基于點的圖形學(xué)在1985年，由Levoy和Whitted[1]提出，并逐漸成為計算機圖形學(xué)的研究熱點[2-4]。目前，海量點云數(shù)據(jù)為計算機存儲和傳輸增加沉重的負(fù)擔(dān)，因此研究點云數(shù)據(jù)的壓縮具有重要的意義。

點模型壓縮通常由頂點數(shù)據(jù)壓縮和屬性數(shù)據(jù)壓縮[5]兩部分組成，本文壓縮算法主要針對點模型的頂點數(shù)據(jù)進行壓縮。點模型數(shù)據(jù)的壓縮根據(jù)接收數(shù)據(jù)的方式通常分為2種：漸進式壓縮和單分辨率壓縮，漸進壓縮是低精度的粗網(wǎng)格模型，是從邊傳送邊顯示精細(xì)細(xì)節(jié)信息，需要構(gòu)造多分辨率的層次結(jié)構(gòu)，導(dǎo)致數(shù)據(jù)冗余，從而影響數(shù)據(jù)壓縮效果，何辰[6]的基于形狀分析的三維點云模型壓縮方法是漸進壓縮方法中一個典型的代表。點模型的單分辨率壓縮只接受整個點模型數(shù)據(jù)后才進行壓縮編碼，相對于漸進壓縮有較高壓縮率，缺點是時間效率較低，如Gumhold等[7]的壓縮編碼算法。同時點模型數(shù)據(jù)的壓縮根據(jù)能否完整的還原點云數(shù)據(jù)分為無損壓縮和有損壓縮，其中無損壓縮如王鵬杰等[8]的基于局部最小生成樹的快速無損壓縮算法，算法有較高的時間效率。由于無損壓縮率較低，多數(shù)點云壓縮算法都是有損壓縮，點云模型去除一部分點云也可以很好地保留物體的三維信息[9-10]，同時點模型的位置坐標(biāo)信息都是用浮點數(shù)表示，浮點數(shù)表示的精度很大，在工程實踐中不需要很高的精度，可以降低浮點數(shù)精度，總體來說有損壓縮在壓縮率上要優(yōu)于無損壓縮。

點模型數(shù)據(jù)壓縮算法為了提高壓縮率，需要在預(yù)測之后和熵編碼算法進行有效的結(jié)合，如Chen 等[11]的算法由于沒有與熵編碼算法有效結(jié)合，得到的壓縮率相對較低，而Isenburg等[12]提出了一種浮點數(shù)熵編碼壓縮算法，可以有效地提高點云數(shù)據(jù)的壓縮率。

工程實踐中對壓縮實時性和壓縮率的要求越來越高，因此本文提出一種基于數(shù)據(jù)類型轉(zhuǎn)換的點云快速有損壓縮算法，該算法是一種單分辨率點模型壓縮算法，同時結(jié)合算術(shù)編碼，有效地提高壓縮率，實驗結(jié)果表明該算法在保證整個三維點云模型的質(zhì)量情況下，有著較高的壓縮速度和壓縮率，可以滿足在工程實踐中對實時性和高壓縮率的要求。

1　點云壓縮算法簡介

本文點云壓縮算法流程如圖1所示。首先本文提出一種數(shù)據(jù)類型轉(zhuǎn)換規(guī)則(float to integer, FtoI)，將浮點數(shù)轉(zhuǎn)換成對應(yīng)的整數(shù)，接著將整個模型分割成多個小塊模型單元，對于點云模型切分的大小決定了點云數(shù)據(jù)壓縮時間和壓縮率的大小，單元切分的過大，導(dǎo)致最小生成樹的時間開銷過大，時間效率低，最大預(yù)測誤差會增大，而單元切分的過小，會導(dǎo)致編碼不連續(xù)性，使算法壓縮率過低，下文實驗證明單元點云數(shù)70為最佳。點云模型切分后，對每一單元再采用最小生成樹算法，對點云數(shù)據(jù)進行預(yù)測，對于最小生成樹樹形結(jié)構(gòu)采用算術(shù)編碼進行編碼壓縮。對于整數(shù)類型的頂點數(shù)據(jù)，根據(jù)最小生成樹，把子父節(jié)點的差值拆成兩部分，符號位部分和絕對值部分，對絕對值部分進行算術(shù)編碼壓縮。

圖1　算法流程圖

2　點云有損壓縮算法

2.1浮點數(shù)簡介

現(xiàn)今計算機系統(tǒng)中普遍采用1985年IEEE協(xié)會發(fā)布的二進制浮點數(shù)算術(shù)標(biāo)準(zhǔn)(IEEE754)[13]，該標(biāo)準(zhǔn)定義了被廣泛使用的32位二進制浮點數(shù)(單精度) 和64位二進制浮點數(shù)(雙精度)的存儲格式。單精度浮點數(shù)在計算機中的存儲方式如圖2所示，一個單精度浮點數(shù)可分為3部分：符號位(1 Bit)、指數(shù)位(8 Bit)、尾數(shù)位(23 Bit)。

圖2　IEEE標(biāo)準(zhǔn)下浮點數(shù)存儲方式示意圖

任意二進制浮點數(shù)的數(shù)值由下式表示：

浮點數(shù)真實指數(shù)值e表示為：e=E-127。

圖3為浮點數(shù)之間的符號位、指數(shù)位和尾數(shù)位關(guān)系圖，橫坐標(biāo)為實數(shù)坐標(biāo)軸，縱坐標(biāo)為實數(shù)對應(yīng)的浮點數(shù)，如圖3所示，0.3、0.7和6.3、6.7的差值都是 0.4，但浮點數(shù)的尾數(shù)位差值分別為ox199999和ox0ccccc，表明在相同誤差下，不同的指數(shù)段，尾數(shù)位差值是不同的，指數(shù)位越大，尾數(shù)位差值越小。

圖3　浮點數(shù)符號位、指數(shù)位和尾數(shù)位關(guān)系圖

2.2FtoI規(guī)則

對于點云的三維坐標(biāo)信息，用浮點數(shù)表示，其指數(shù)位不盡相同，為了直觀顯示點云的指數(shù)位部分，圖4是Bunny點云數(shù)據(jù)模型指數(shù)位的直觀示意圖，紅綠根據(jù)x坐標(biāo)方向浮點數(shù)的指數(shù)位變化而變化。根據(jù)浮點數(shù)的特點，其指數(shù)位不同，因此其精度也不相同，指數(shù)位越小，表示數(shù)值的精度就越高。對于一個點云模型的數(shù)據(jù)顯示，各方向中指數(shù)位最大的坐標(biāo)數(shù)據(jù)精度最低。

圖4　點云模型指數(shù)位的示意圖

如果點云的測量精度小于點云數(shù)據(jù)表示的最低精度，那么對于指數(shù)位低的高精度數(shù)據(jù)即多余的二進制數(shù)相當(dāng)于估計值，沒有實際意義，可以忽略不計。相反如果點云的測量精度大于點云數(shù)據(jù)表示的最低精度，雖然指數(shù)位低的數(shù)據(jù)比指數(shù)位大的數(shù)據(jù)對模型表示更加準(zhǔn)確，但三維重建后[14]，模型與實際物體之間誤差在指數(shù)位高的區(qū)域較大，在指數(shù)位低的區(qū)域較小，對于整個模型的質(zhì)量來說由指數(shù)位高的區(qū)域決定。因此指數(shù)位較小的區(qū)域可以降低精度，使整個模型誤差達(dá)到相對的平衡。

基于以上分析，對于指數(shù)位小的點云數(shù)據(jù)無需保留太高的精度，統(tǒng)一將點云數(shù)據(jù)轉(zhuǎn)換成最大指數(shù)位的精度，設(shè)計出一種點云FtoI規(guī)則，將浮點數(shù)轉(zhuǎn)換成對應(yīng)的整數(shù)。

FtoI規(guī)則：

(1) 將點云x, y, z坐標(biāo)浮點型數(shù)據(jù)，拆成符號位、指數(shù)位、尾數(shù)位3部分，其中x, y, z各坐標(biāo)最大的指數(shù)位記為Exmax，Eymax，Ezmax。

(2) 各方向坐標(biāo)系的數(shù)據(jù)，根據(jù)其指數(shù)位和最大指數(shù)位的差值dif，將尾數(shù)位最左端補加一個1，即尾數(shù)位變成24位，再右移dif位，將尾數(shù)位轉(zhuǎn)換成整型。

(3) 整型數(shù)據(jù)符號位和對應(yīng)的浮點數(shù)符號位相同。

FtoI規(guī)則將浮點數(shù)類型點云數(shù)據(jù)統(tǒng)一精度，然后轉(zhuǎn)化成整數(shù)類型，浮點數(shù)和整數(shù)可以相互轉(zhuǎn)化。FtoI規(guī)則會損失部分精度，但不會影響整個點云模型的質(zhì)量，圖 5(a)為原始點云模型，圖 5(b)是經(jīng)FtoI規(guī)則轉(zhuǎn)換后的點云模型；圖5(c)是原點云模型和 FtoI規(guī)則轉(zhuǎn)換后的點云模型的合并模型，可以看出在中部有很少的綠色點云，表明原點云模型和規(guī)則轉(zhuǎn)換后的點云模型幾乎完全重合，只有中部存在少部分偏差，總體說明 FtoI規(guī)則不會影響整個點云模型的質(zhì)量。浮點數(shù)轉(zhuǎn)化整型有 2大優(yōu)勢：①整型數(shù)據(jù)運算相比浮點數(shù)效率高，提高時間效率；②轉(zhuǎn)化后的整型數(shù)據(jù)相比浮點數(shù)去除了指數(shù)位的信息，有利于后續(xù)的壓縮和保存，減少內(nèi)存開銷。

圖5　Bunny點云模型

為了定量分析有損壓縮后的模型與原模型的差別，本文提出點距誤差比的概念記為kdis，即某點與其對應(yīng)有損壓縮點之間的歐幾里得距離與該點與其最近點的歐幾里得距離的比值。點與其對應(yīng)有損壓縮點之間的歐幾里得距離記為diss，點與其最近點的歐幾里得距離記為disr，則：

在圖6中，a′點表示a點經(jīng)過有損壓縮后的點，b點表示離a點最近的點，a點的kdis為，當(dāng)三維模型重建時，線段 ab是原模型上的一條線段，而線段a′b是有損壓縮后模型上的一條線段，如果kdis比較小，說明ab和a′b越接近，有損壓縮后的模型與原模型越接近。

圖6　點距誤差比示意圖

把點云模型中點距誤差比最大的稱為最大點距誤差比，所有點距誤差比的平均值稱為平均點距誤差比，最大點距誤差比和平均點距誤差比越小，表明有損壓縮后的模型與原模型越接近。

2.3點云模型切分

為了方便后續(xù)處理，需要對點云模型進行切分，首先利用八叉樹算法進行粗切分，然后根據(jù)坐標(biāo)軸依次切分。八叉樹是一種三維數(shù)據(jù)結(jié)構(gòu)，如圖7所示，由Hunter[15]于1978年在其博士論文中首次提出，八叉樹的主要優(yōu)點在于可以非常方便地實現(xiàn)集合運算，有很強的空間分解能力，可以有效地處理大量的點云數(shù)據(jù)[16]，被廣泛用于點云數(shù)據(jù)壓縮中。

圖7　八叉樹簡圖

以下是八叉樹切分算法：

(1) 記錄點云在三維坐標(biāo)中，各方向最大和最小值 Xmax，Xmin，Ymax，Ymin，Zmax，Zmin。以為中心，邊長分別為最大值的最小立方體包圍盒進行八叉樹切分。

(2) 當(dāng)八叉樹父節(jié)點非空，且點云數(shù)量大于N，繼續(xù)切分，否則停止切分，并設(shè)最大遞歸深度為depth，防止無窮切割。

(3) 重復(fù)步驟(2)，直至切分完畢或達(dá)到最大遞歸深度。

因為八叉樹分割時無法保證每個葉節(jié)點內(nèi)的點云數(shù)量符合要求，會出現(xiàn)很多碎片立方體，只含有很少點云，所以要進行適當(dāng)?shù)暮喜⑻幚?，本文采用同一個父節(jié)點內(nèi)的點云x、y、z坐標(biāo)排序的方法解決這種問題，具體步驟如下：

首先假設(shè)m個點云作為一組，則取N=50 m，而最大遞歸深度根據(jù)文獻[17]分析，取 depth=20。對于一個點云模型八叉樹切分后，每個節(jié)點內(nèi)點云數(shù)量在50 m以下，對于點云數(shù)量m以下的節(jié)點合并到同一父節(jié)點相鄰節(jié)點內(nèi)，整個點云模型分成很多塊，記為Surfacei。

對于每個 Surfacei內(nèi)的點云再進行遞歸深度為2的八叉樹切分，找出所有非空子節(jié)點中離Surfacei最小包圍盒中心最近的子節(jié)點，從子節(jié)點任意取一個點記為o，并找出離o點最近的10個點，記為qi，利用這10個點對該單元點云擬合平面進行粗估計。求矩陣：

最小特征值的特征向量，記為v，v=(xv, yv, zv)做為擬合粗平圖的法向量，點o為擬合平面上一點，如圖8所示。對xv，yv，zv的絕對值進行升冪排列。假設(shè) Surfacei內(nèi)點云數(shù)量為num，法向量v的升冪排列為yv，xv，zv，取。首先全部 num個點云按照v中絕對值最小的方向分量yv升冪排列，沿y坐標(biāo)從小到大每L×m個點云一組，接著對每一組點云按照v中絕對值第二小的方向分量xv升冪排列，沿著x坐標(biāo)從小到大每m個點云一組，對于最后的一組點云數(shù)量可能小于m，如果小于合并到前一組，否則單獨一組，至此點云切分完畢。

圖8　點云粗?jǐn)M合平面

2.4最小生成樹生成與壓縮

在點云模型切分之后，首先需要對每個單元內(nèi)點云進行預(yù)測編碼，然后進行編碼壓縮處理。文獻[7]首次將最小生成樹應(yīng)用點云預(yù)測壓縮中，取得明顯壓縮效果。本文采用最小生成樹進行預(yù)測，具體以每個單元內(nèi)點云之間的曼哈頓距離作為權(quán)值，采用Prim算法[18]生成單元最小生成樹。

本文Prim算法流程如下：

設(shè)G=(V, E)，其最小生成樹S=(U, TE)。

(1) U，TE為空，從V中取出一點o加入U。

(2) 查找V和U中權(quán)值最小的兩點記為x和y，從V取出x加入U，邊(x, y)加入TE中。

(3) 重復(fù)步驟(2)直到V為空。

對于點云數(shù)據(jù)的預(yù)測壓縮需要最小生成樹的信息，在對點云數(shù)據(jù)解壓時，也需要用最小生成樹的信息對其進行解碼，因此，可單獨對最小生成樹編碼壓縮，記錄父節(jié)點的子節(jié)點個數(shù)。如圖9所示，1號節(jié)點有2個子節(jié)點2和3，2號節(jié)點有1個子節(jié)點 4，采用算術(shù)編碼[19]依次記錄父節(jié)點的子結(jié)點個數(shù)。2.5頂點數(shù)據(jù)壓縮

圖9　最小生成樹示意圖

點云頂點數(shù)據(jù)首先經(jīng) FtoI規(guī)則由浮點數(shù)類型轉(zhuǎn)換成整數(shù)類型，頂點數(shù)據(jù)壓縮是對于整型數(shù)據(jù)的壓縮，具體步驟分3步：

(1) 對于每個單元塊內(nèi)的點云根據(jù)其最小生成樹求對應(yīng)父子節(jié)點的差值，對整型的差值進行編碼壓縮，編碼順序為最小生成樹寬度優(yōu)先。樹形結(jié)構(gòu)如圖9所示，編碼順序：首先編碼1號節(jié)點的原值，其次2、3號節(jié)點與1號節(jié)點的差值。然后4號節(jié)點與2號節(jié)點的差值，5、6、7號與3號節(jié)點的差值。最后8號節(jié)點與5號節(jié)點的差值，9、10號節(jié)點與7號節(jié)點的差值。

(2) 由于三維點云數(shù)存在3個坐標(biāo)方向，對x、y、z 3個坐標(biāo)數(shù)據(jù)分別編碼壓縮。如果直接對 32位整數(shù)差值進行編碼壓縮，會影響壓縮效果，為了提高壓縮率，減少每一個差值所占用的Bit位，在每一個單元內(nèi)，求每個方向絕對值最大的差值Max，絕對值部分采用n位Bit存儲，其中n滿足以下條件：

而符號部分采用1位Bit存儲。把整型差值分成兩部分編碼，符號一部分，其絕對值一部分，整個差值所占Bit位為n+1。

(3) 為了達(dá)到更好地壓縮效果，對差值部分進行算術(shù)編碼壓縮。由于符號位部分的值0和1分布隨機，采用算術(shù)編碼沒有明顯的壓縮效果，而且增加了時間開銷，因此對符號部分直接存儲。而絕對值部分，其值小于Max，統(tǒng)一采用n位Bit記錄，其中一些值遠(yuǎn)小于Max，高位中0的出現(xiàn)概率大于1的出現(xiàn)概率，因此采用算術(shù)編碼壓縮會達(dá)到較好地壓縮效果。由于大多數(shù)計算機最多支持的 80位或差不多的浮點數(shù)，必須在每次完成有限個符號后重新開始，采用增量轉(zhuǎn)換方法來代替浮點數(shù)，形成一個較大的單數(shù)取代對應(yīng)的浮點數(shù)，這個單數(shù)的位數(shù)可以很大，從而解決了浮點數(shù)位數(shù)有限的不足。

3　實驗結(jié)果與分析

在CPU2.2 GHz，2 G內(nèi)存，W indows 7系統(tǒng)的電腦上實現(xiàn)本文算法，點云模型采用Stanford大學(xué)標(biāo)準(zhǔn)的點云模型。

對于點云模型切分的大小決定了點云數(shù)據(jù)壓縮時間和壓縮率的大小，單元切分的過大，導(dǎo)致最小生成樹的時間開銷過大，時間效率低下，而單元切分的過小，會導(dǎo)致編碼不連續(xù)性，使算法壓縮率過低。對于單元點數(shù)的選擇，通過對Bunny模型進行實驗分析，其含40 257個點云數(shù)據(jù)。實驗數(shù)據(jù)見表1，圖10是壓縮率和壓縮時間對應(yīng)趨勢的曲線圖，由圖 10可看出，隨著每單元點云數(shù)量增加，壓縮時間相應(yīng)增加，而壓縮率先提高再降低。綜合數(shù)據(jù)分析，為達(dá)到壓縮時間和壓縮率的最優(yōu)平衡，選點云數(shù)量為70的壓縮塊。壓縮時間以ms為單位，壓縮率以bpp(bits per point)為單位，即每個點數(shù)據(jù)所占二進制位數(shù)。

表2是3個標(biāo)準(zhǔn)點云模型的最大點距誤差比和平均點距誤差比，其中點距誤差比在10-4以下，表明有損壓縮后的點云模型與原始點云模型幾乎一致。

表3和圖11給出本文算法(簡稱New)和傳統(tǒng)7zip以及文獻[8]算法(簡稱Wang)壓縮率的比較，表明本文在壓縮率方面有良好的表現(xiàn)。同時本文算法在壓縮速度方面也有不俗的表現(xiàn)，平均壓縮速度約為200 k點/s，而7zip壓縮速度約為1.5 M/s，轉(zhuǎn)換成統(tǒng)一速度單位點/s，對于二進制文件格式點云，壓縮速度約為130 k點/s，對于文本文件格式點云，壓縮速度約為 45 k點/s，Wang算法壓縮率約為25 k點/s。同時本文解壓縮不需要壓縮時的前期處理，在時間上明顯小于壓縮時間，約為其八分之一，解壓縮平均速度為1 600 k點/s。

表1　不同點云數(shù)量對算法壓縮率和壓縮時間的影響

圖10　本文方法的壓縮率和壓縮時間隨點云數(shù)量變化曲線圖

表2　不同點云模型的點距誤差比

表3　3種算法壓縮率的對比

圖11　3種算法壓縮率的比較圖

4　結(jié)論與展望

本文提出了一種基于 FtoI規(guī)則的點云快速有損壓縮算法，該算法對部分點云的精度損失極其微小，不會影響整個三維點云模型的整體質(zhì)量。FtoI規(guī)則首先將浮點數(shù)統(tǒng)一精度，然后轉(zhuǎn)換成整數(shù)，可以有效地減少了計算復(fù)雜度和內(nèi)存開銷。實驗結(jié)果表明該算法有較好地壓縮速度和壓縮率。

浮點數(shù)表示的精度很高，但在工程實踐中有時候不需要很高的精度。本文的點云快速有損壓縮算法可以實現(xiàn)不同精度的壓縮，在點距誤差比很小時，可以適當(dāng)降低精度，從而達(dá)到更高的壓縮率。在今后研究中可以結(jié)合點云精簡技術(shù)，根據(jù)需求對整個模型的點云數(shù)量進行處理，盡量減少壓縮時間和內(nèi)存開銷。

[1] Levoy M, Whitted T. The use of points as a display primitive [R]. Chapel Hill: University of North Carolina, 1985.

[2] Kobbelt L, Botsch M. A survey of point-based techniques in computer graphics [J]. Computer & Graphics, 2004, 28(6): 801-814.

[3] Gross M, Pfister H. Point-based graphics [M]. San Francisco: Morgan Kaufman Publisher, 2007.

[4] 王鵬杰, 潘志庚, 劉勇奎. 基于點的三維模型壓縮技術(shù)研究進展[J]. 計算機輔助設(shè)計與圖形學(xué)學(xué)報, 2009, 21(10): 1359-1367.

[5] Zhang C, Florêncio D, Loop C. Point cloud attribute compression with graph transform [C]//Image Processing (ICIP), 2014 IEEE International Conference on. New York: IEEE Press, 2014: 2066-2070.

[6] 何辰. 基于形狀分析的三維點云模型壓縮[D]. 濟南:山東大學(xué), 2014.

[7] Gumhold S, Karni Z, Isenburg M, et al. Predictive point cloud compression [C]//Proceedings of SIGGRAPH Sketches. New York: ACM Press, 2005: 137.

[8] 王鵬杰, 潘志庚, 徐明亮, 等. 基于局部最小生成樹的點模型快速無損壓縮算法[J]. 計算機研究與發(fā)展, 2011, 48(7): 1263-1268.

[9] Morell V, Orts S, Cazorla M, et al. Geometric 3D point cloud compression [J]. Pattern Recognition Letters, 2014, 50: 55-62.

[10] 范然, 金小剛. 大規(guī)模點云選擇及精簡[J]. 圖學(xué)學(xué)報, 2013, 34(3): 12-19.

[11] Chen D, Chiang Y J, Memon N. Lossless compression of point-based 3D models [J]. Proceedings of Pacific Graphics, 2005: 124-126.

[12] Isenburg M, Lindstrom P, Snoeyink J. Lossless compression of floating-point geometry [J]. Journal of Computer-Aided Design, 2005, 37(8): 869-877.

[13] IEEE 754-1985, Standard for binary floating point arithmetic [S]. New York: The Institute of Electrical and Electronic Engineers Inc, 1985.

[14] Fabio R. From point cloud to surface: the modeling and visualization problem [J]. International Archives of Photogrammetry, Remote Sensing and Spatial Information Sciences, 2003, 34(5): W 10.

[15] Hunter G M. Efficient computation and data structures for graphics [D]. Princeton: Department of Electrical Engineering and Computer Science, Princeton University, 1978.

[16] Elserberg J, Borrmann D, Nuchter A. One billion points in the cloud-an octree for efficient processing of 3D laser scans [J]. ISPRS Journal of Photogrammetry and Remote Sensing, 2013, 76: 76-88.

[17] Schnabel R, Klein R. Octree-based point-cloud compression [C]//SPBG’06 Proceeding of the 3rd Eurographics. New York: IEEE Press, 2006: 111-120.

[18] Cormen H, Leiserson E. Introduction to algorithms [M]. 3rd ed. Cambridge: The M IT Press, 2009: 624-643.

[19] Witten I H, Neal R M, Cleary J G. Arithmetic coding for data compression [J]. Communications of the ACM, 1987, 30(6): 520-540.

A Fast and Lossy Com pression A lgorithm for Point-Cloud Models Based on Data Type Conversion

Lv Shuai,Da Feipeng,Huang Yuan

(School of Automation, Southeast University, Nanjing Jiangsu 210096, China)

In order to solve computer storage and transmission problem due to massive 3D point cloud, a fast and lossy compression algorithm for point-cloud models based on data type conversion is proposed. Firstly, a data type conversion rule-FtoI rule is designed. According to the FtoI rule, float-point type point cloud is converted to integer type point cloud, then the integer type point-based surface is split into many sized surface patches, the points of every patches construct a minimum spanning tree, which is encoded in breadth first order. Besides we encode the difference between father node and son node according to the minimum spanning tree, the difference is split into two parts, one is sign, another is absolute value, which is encoded by arithmetic coding. Experiments show that this compression algorithm has a nice compression speed and compression ratio without losing the quality of point-cloud model.

3D point cloud; lossy compression; float; the m inimum spanning tree; arithmetic coding

TP 391.41

10.11996/JG.j.2095-302X.2016020199

A

2095-302X(2016)02-0199-07

2015-09-24；定稿日期：2015-10-20

國家自然科學(xué)基金項目(61405034, 51175081, 51475092)；教育部博士點基金項目(20130092110027)

律帥(1989–)，男，山東濟寧人，碩士研究生。主要研究方向為三維數(shù)據(jù)壓縮。E-mail：lssoutheast@163.com

達(dá)飛鵬(1968–)，男，江蘇南通人，教授，博士，博士生導(dǎo)師。主要研究方向為三維精密測量研究與應(yīng)用。E-mail：dafp@seu.edu.cn