基于Ｓｕｒｆｅｌ點云數據的壓縮算法

（1.浙江大學 CAD CG國家重點實驗室， 杭州 310058；2.大連民族學院 計算機科學與工程學院， 遼寧大連 116600；3.吉林大學 計算機科學與技術學院， 長春 130025）



摘要：針對點云數據局部集中的特點，使用差值預測對點云數據進行預測處理；在預測的同時，根據IEEE-754浮點數標準，簡化浮點數的尾數，使用3.5 Byte來表示一個浮點數，以提高壓縮效果；然后對預測數據中連續重復的字節使用該字節加該字節重復的次數的方式存儲；最后對經過以上處理的數據使用一階自適應算術編碼進行壓縮。最終得到的程序在壓縮比和內存占用兩個方面遠優于WinRAR、WinZip壓縮軟件。

關鍵詞：點云；基于預測的壓縮；算術編碼; Surfel

中圖分類號：TP391文獻標志碼：A

文章編號：1001-3695(2008)11-3471-03



Compression algorithm of point clouds based on Surfel



WANG Peng-jie1，2， SONG Hai-yu2，3， SHENG Sen2



(1.State Key Laboratory of CAD C G，Zhejiang University，Hangzhou 310058， China;2.College of Computer Science Engineering， Dalian Nationalities University， DalianLiaoning 116600， China;3.College of Computer Science Techology， Jilin University， Changchun 130025， China)



Abstract: According to the fact that the Surfel was locally intensive， a predictor was used to predict next Surfel by getting the difference between this Surfel and prior one. At the same time， according to the IEEE-754 floating standards， the mantissa part of a float was reduced from 23 bit to 19 bit. After this， the repeated byte was replaced by this byte and it was repeated times. At the last， the 1 context-based adaptive arithmetic coding was used to further compress the data sets. The result shows that the compression ratio and memory using of the algorithm is greatly better than WinRAR and WinZip.

Key words：point clouds; compression based on prediction; arithmetic coding; Surfel

隨著三維掃描技術的迅速發展，產生出了大量頂點數達百萬數量級的高精度三維模型。如果用多邊形網格表示這些高精度模型，需要的多邊形將達到了幾百萬。一方面，維護和存儲這么龐大的多邊形網格的拓撲信息將占據非常大的CPU時間及內存；另一方面，當多邊形網格數量超過屏幕像素數時，一個多邊形網格在屏幕上投影比一個屏幕像素還小。這時采用沒有拓撲信息的點來代替多邊形網格作為模型數據的基本單元有更明顯的優勢。所以，基于點的圖形學應運而生并成為近年來的研究熱點^[1~3]。

基于點的圖形學中兩個最基本問題的是基于點的繪制和壓縮。基于點的實時繪制系統中比較出色的有QSplat^[4]和PointShop3D^[5]系統以及Botsch等人^[6]的基于八叉樹的點云繪制系統；國內較有影響力的是浙江大學的Peng等人^[7]提出的基于點的繪制系統。QSplat巧妙地利用點模型的靈活性，建立了一種新奇的層次包圍球的結構，采用層次遍歷的方法進行繪制，極大地提高了繪制速度。但是這種算法只著眼于繪制的速度，忽略了繪制的質量。點繪制中另一部分重要的工作著眼于提高繪制的質量。Pfister等人^[8~10]提出用點面元（Surfel）來代表一個采樣點。Surfel是位于點切面上的一個圓盤，各點的Surfel相互重疊而形成緊密的物體表面，通過可見性預處理和圖像重建而得到光滑圖像。PointShop3D即是該類型的繪制系統。本文中使用的SLS文件即是由大量Surfel組成的圖形文件，它可由PointShop3D系統繪制。

目前基于網格的壓縮技術^[11~13]已比較成熟，但是基于點的模型數據的壓縮尚屬于新的領域，雖然已經有很多的算法^[14~21]，但這些算法均針對某一特定的繪制算法，沒有廣泛的適應性。而隨著基于點的繪制技術的發展及Surfel類繪制算法的成熟，研究開發針對Surfel類點云數據壓縮的算法已經非常必要。本文針對存儲Surfel的點云數據文件設計一個無損壓縮算法，得到較高的壓縮率。

1SLS文件格式

點模型用從幾何體表面密集采樣得到的離散點云來隱式地表示幾何體的表面，從本質上講點模型是一種面表示模型。與傳統的三角網格模型相比，點模型最顯著的特點就是它不包含任何拓撲信息，如點與點之間的連接關系及點的鄰域信息等。點模型的基本幾何單元就是點(point)。每一個點所包含的基本的信息有：位置(x， y， z)；法向(nx，ny，nz)。僅僅用以上的孤立點集不能構成一個封閉的表面，因此基于點的繪制的基本任務就是由點集重建出視覺等價的光滑曲面。目前最流行的做法是用Surfel(surface element)來表示一個點。每一個Surfel包含的信息有：位置(x， y， z)；法向(nx，ny，nz)；半徑r；顏色（材質）等其他信息。這實際上將每個點局部考慮為一個圓盤。圓盤的半徑r與曲面在該點處的曲率有關。理想情況下，模型曲率大的地方應采樣比較密集，半徑較小；而曲率小的地方應采樣比較稀疏，半徑較大。半徑r應該足夠大使得所有的Surfel相互重疊而構成一個閉合表面。

SLS文件是包含大量Surfel數據的點集。其標準文件格式為：第一行存放其Surfel個數，從第二行開始每行存儲一個Surfel的數據。每個Surfel的數據順序為坐標值(x， y， z)、顏色值(r， g， b)、法向量（nx，ny，nz）、點的半徑radius。SLS的文件結構如下：

〈number-of-surfels〉

〈x〉〈y〉〈z〉〈r〉〈g〉〈b〉〈nx〉〈ny〉〈nz〉〈radius〉

〈x〉〈y〉〈z〉〈r〉〈g〉〈b〉〈nx〉〈ny〉〈nz〉〈radius〉





2壓縮編碼算法

21浮點數簡化

目前大多數高級語言均按照IEEE-754標準來規定浮點數的存儲格式，IEEE-754規定，單精度浮點數用4 Byte存儲，雙精度浮點數用8 Byte存儲。單精度的浮點數如下所示：



符號位31指數30…23尾數22…0

單精度的浮點數分為三個部分，即符號位（1位）、指數（8位）和尾數（23位）。

32位浮點數來說已經具有很高的數據精度，其精度可以表示最微小粒子的半徑，也可以表示遙遠的宇宙外空間到地球的距離。而在工程應用中，無須這么高的精度。觀察在SLS的模型數據，點云數據的尾數均為5~6位，以后的17~18位幾乎可以忽略。如果將其浮點數多余的尾數位消去，則可以節省大量空間，對繪制幾乎沒有影響。筆者將尾數的23位中去掉其最后4位，使用19位來表示尾數，即每個浮點數平均使用35 Byte來存儲和表示。例如對于浮點數f = -0123 45，編寫程序轉換為二進制轉換處理，再轉換為十進制后f仍為-0123 45，如下：

簡化處理前：f =-0.123 45

二進制位為101111011111110011010011010111011

簡化處理后10111101111111001101001101010000

此時轉換為十進制仍為 f=-012345

隨機抽取了SLF文件中的浮點數，均發現這樣的規律。所以，浮點數簡化是可行的。

對內存的操作最小是按字節進行的，所以無法直接用35 Byte來存儲一個浮點數。而一個Surfel中包含10個浮點數，平均每個浮點數需要用35 Byte來存儲，共需要35個字節。采用一個cFloat[35]數組中來存儲這35個字節，先存儲每個浮點數的前3個字節，這樣共需要30個字節，剩余的5個字節用來存儲每個浮點數的剩余的4 bit，如下所示：

第一個浮點數的前3個字節第二個浮點數的前3個字節…剩余的浮點數部分

22預測處理

經浮點數簡化后，每行數據寫出文件后也為35個字節，在內存中，筆者用一個Surfel對象來存儲。激光掃描產生的三維點云數據是大量密集的點，其數據特點是相鄰的點比較接近，若將其相鄰的點依此做差，得到的差值集中分布在一個較狹窄的范圍內，應具有更好的局部聚集性，而算術編碼對這樣的數據具有很高的壓縮率。所以要對經浮點數簡化后的數據進行差值預測。具體過程為存儲第一個Surfel的數據，然后存儲第二個Surfel數據與前一個的差值；接著存儲第三個Surfel與第二個的差值，依此類推，如下所示：

Surfel[i+1](x2，y2，z2…)-Surfel[i](x1，y1，z1…)=Correction[i](Δx，Δy，Δz…)

文本將預測差值稱為預測校正值(correction)。解碼時遵循相反的過程即可。

圖1是對部分SLS文件的Surfel原始點云數據及預測后的預測校正值分布情況統計。以下分布圖中橫坐標表示數據值，縱坐標表示該值的個數。可以看出，原始數據分布較為散亂，如圖1所示，而預測后的數據則集中分布在較小的一個區間內，如圖2所示。圖2的數據具有很強的局部聚集行，算術編碼對圖2中的數據具有很高的壓縮率。

23重復數據壓縮

在對點云數據的預測處理后，有大量比較接近的數據，而預測后得到的校正值出現大量的重復字符如0、60等。在出現同一字符時，對其進行替換，只保留該字符和從這個字符開始連續出現該字符的個數，這樣可以顯著提高壓縮效果。但必須保證待壓縮的重復字符至少重復出現兩次以上，否則反而有可能使待壓縮的文件增大。統計預測后文件中各字符連續出現兩次以上的情況，如圖3所示。



圖3預測數據中字符出現規律

在編碼過程中，若讀取到的字符為0，則不進行編碼，繼續讀下一個字符，如果不為0，則以一個特殊符號代替0進行編碼，否則繼續讀，直到出現不為0的字符，把字符0以及統計得到的0個數分別進行編碼。如此處理，最終得到的程序壓縮效果更高。解碼過程與此過程類似，若解碼出的字符為代替0的特殊符號，則直接輸出0，若為0則繼續解碼下一個字符，得到其連續出現的次數，然后循環輸出0。

24一階上下文自適應算術編碼

不同于靜態模型，自適應的算術編碼無須存儲和傳輸靜態模型概率數據，它能在壓縮編碼的過程中自動統計和更新字符的概率。由于概率值隨著編碼的進行而調整，得到的概率分布值有利于數據的高效壓縮。筆者選用自適應模型的算術編碼。高階的算術編碼具有很高的壓縮率，但是，其時間代價也比較大。本文選擇了一階算術編碼以在時間與壓縮率之間取一個平衡。

經過21節的浮點數簡化，22節的預測處理及23節的重復數據壓縮處理后。筆者對得到的數據運用一階的自適應算術編碼進行壓縮。

3結果與比較

由于對浮點數的簡化處理后，浮點數再經過運算時，精度會有輕微變化。但不影響繪制的效果。例如模型male的壓縮前繪制效果如圖4(a）所示，壓縮后的效果如(b）所示。

圖4壓縮前后繪制

在操作系統為Windows XP，CPU為22 GHz Pentium 4，256 MB內存的微機上進行了實驗。將本文算法 (SurfelCompr)與別的壓縮工具（WinZip 111、WinRAR 351）進行了比較。表1是壓縮率比較，比較的值有壓縮比（壓縮后大小 / 壓縮前大小）。在表的最后兩列給出了SurfelCompr優于WinZip和WinRAR的百分比。SurfelCompr在壓縮率上平均要優于WinZip 361%，優于WinRAR 287%。表2為壓縮時間使用表。SurfelCompr在壓縮時間上比WinZip要長，基本與WinRAR相當。表3為內存峰值情況表，內存使用最多的是WinRAR，最少的是SurfelCompr。

4結束語

隨著基于點的圖形學的快速發展，存儲點云的數據文件需要好的壓縮算法以利于其傳輸和存儲。本文設計了一個針對Surfel點云數據的無損壓縮算法。從取得的結果看，得到了比傳統壓縮軟件更高的壓縮率，并且在內存使用上遠遠低于傳統壓縮軟件。但本文的算法在壓縮時間上沒有太大的優勢，須進一步提高，這可作為以后的工作，作進一步的研究。

致謝感謝ETH Zurich 的Computer Graphics Lab提供的Pointshop3D軟件及balljoint、face、gnome、male和santa模型。

參考文獻：

［1］

ALEXA M， DACHSBACHER C， GROSS M，et al. Point-based computer graphics [R]. Granada: University of Granada， 2003.

[2]田海山，何援軍，蔡鴻明.基于點的計算機圖形學綜述[J]. 系統仿真學報，2006， 18(S1): 42-45.

[3]王曉云.點模型及其繪制技術研究[J]. 計算機應用研究，2005， 22(7): 158-160.

[4]RUSINKIEWICZ S， LEVOY M. QSplat: a multiresolution point rendering system for large meshes[C]//Proc of ACM SIGGRAPH.New Orleans:[s.n.]，2000:343-352.

[5]ZWICKER M， PAULY M， KNOLL O，et al.Pointshop3D:an interactive system for point-based surface editing[C]//Proc of ACM SIGGRAPH. San Antonio:[s.n.]，2002:322-329.

[6]BOTSCH M， WIRATANAYA A， KOBBELT L. Efficient high quality rendering of point sampled geometry [C]//Proc of the 13th Eurographics Workshop on Rendering.[S.l.]:Aire-la-Ville，2002:53-64.

[7]PENG Q S， HUA W， YANG X. A new approach of point-based rendering[C]//Proc of Computer Graphics Conference.Hong Kong:[s.n.]，2001:275-282.

[8] PFISTER H， ZWICKER M，BAAR J van，et al.Surfels: Surface elements as rendering primitives[C]//Proc of ACM SIGGRAPH. New Orleans:[s.n.]，2000:335-342.

[9] ZWICKER M， PFISTER H，BAAR J van，et al. Surface splatting [C]//Proc of ACM SIGGRAPH. Los Angeles:[s.n.]，2001:371-378.

[10]REN L， PFISTER H， ZWICKER M. Object space EWA surface splatting : a hardware accelerated approach to high quality point rendering [J].Computer Graphics Forum，2002，21(3):461-470.

[11] ALLIEZ P，GOTSMAN C.Recent advances in compression of 3D Me-shes[R].Cambridge:Springer，2005.

[12] 郭力真，吳恩華.多邊形模型簡化算法綜述[J].計算機應用研究，2005，22(8):20-23，42.

[13]方同祝，田錚，胡正國，等.多分辨率網格的數據壓縮[J].系統仿真學報，2005，17(3): 653-655.

[14]OCHOTTA T， SAUPE D. Compression of point-based 3D models by shape-adaptive wavelet coding of multi-height fields [C]//Proc of Eurographics Symposium on Point-based Graphics.Zürich:[s.n.]，2004:103-112.

[15]WASCHBUSCH M， GROSS M， EBERHARD F， et al. Progressive compression of point-sampled models [C]//Proc of Eurographics Symposium on Point-based Graphics.Zürich:[s.n.]，2004：95-102.

[16]權毓舒， 何明一. 基于三維點云數據的線性八叉樹編碼壓縮算法[J]. 計算機應用研究，2005， 22(8):70-71，129.

[17]HUANG Y， PENG J， KUO C-C J， et al. Octree-based progressive geometry coding of point clouds [C]//Proc of Eurographics Symposium on Point-based Graphics. Boston:[s.n.]，2006:103-110.

[18]SCHNABEL R， KLEIN R. Octree-based point-cloud compression [C]// Proc of Eurographics Symposium on Point-based Graphics.Boston:[s.n.]，2006:111-120.

[19]GUMHOLD S， KARNI Z， ISENBURG M， et al. Predictive point-cloud compression [C]//Proc ofInternational Conference on Compu-ter Graphics and Interactive Techniques.New York:ACM，2005.

[20]MERRY B， MARAIS P， GAIN J. Compression of dense and regular point clouds [J]. Computer Graphics Forum， 2006， 25 (4):709-716.[21]CHEN D， CHIANG Y-J， MEMON N. Lossless compression of point-based 3D models [M].Macao:Pacific Graphics， 2005:124-126.