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

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

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

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

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

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

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

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

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

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

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

1　點(diǎn)云壓縮算法簡介

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

圖1　算法流程圖

2　點(diǎn)云有損壓縮算法

2.1浮點(diǎn)數(shù)簡介

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

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

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

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

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

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

2.2FtoI規(guī)則

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

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

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

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

FtoI規(guī)則：

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

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

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

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

圖5　Bunny點(diǎn)云模型

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

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

圖6　點(diǎn)距誤差比示意圖

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

2.3點(diǎn)云模型切分

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

圖7　八叉樹簡圖

以下是八叉樹切分算法：

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

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

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

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

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

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

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

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

2.4最小生成樹生成與壓縮

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

本文Prim算法流程如下：

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

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

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

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

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

圖9　最小生成樹示意圖

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

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

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

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

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

3　實(shí)驗(yàn)結(jié)果與分析

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

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

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

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

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

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

表2　不同點(diǎn)云模型的點(diǎn)距誤差比

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

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

4　結(jié)論與展望

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

浮點(diǎn)數(shù)表示的精度很高，但在工程實(shí)踐中有時(shí)候不需要很高的精度。本文的點(diǎn)云快速有損壓縮算法可以實(shí)現(xiàn)不同精度的壓縮，在點(diǎn)距誤差比很小時(shí)，可以適當(dāng)降低精度，從而達(dá)到更高的壓縮率。在今后研究中可以結(jié)合點(diǎn)云精簡技術(shù)，根據(jù)需求對整個(gè)模型的點(diǎn)云數(shù)量進(jìn)行處理，盡量減少壓縮時(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] 王鵬杰, 潘志庚, 劉勇奎. 基于點(diǎn)的三維模型壓縮技術(shù)研究進(jìn)展[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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] 何辰. 基于形狀分析的三維點(diǎn)云模型壓縮[D]. 濟(jì)南:山東大學(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] 王鵬杰, 潘志庚, 徐明亮, 等. 基于局部最小生成樹的點(diǎn)模型快速無損壓縮算法[J]. 計(jì)算機(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ī)模點(diǎn)云選擇及精簡[J]. 圖學(xué)學(xué)報(bào), 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é)基金項(xiàng)目(61405034, 51175081, 51475092)；教育部博士點(diǎn)基金項(xiàng)目(20130092110027)

律帥(1989–)，男，山東濟(jì)寧人，碩士研究生。主要研究方向?yàn)槿S數(shù)據(jù)壓縮。E-mail：lssoutheast@163.com

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