一種利用矢量-角度法的模型點云壓縮算法

劉繼庚，王曉紅，王東東，鄧仕雄，閆星光

(1. 貴州大學礦業(yè)學院，貴州 貴陽 550025； 2. 貴州大學林學院，貴州 貴陽 550025)

三維激光掃描技術的快速發(fā)展使其在文物保護、數(shù)字城市、逆向工程等領域得以應用[1-6]，但其海量的數(shù)據(jù)包含大量的冗余信息，帶來數(shù)據(jù)處理和存儲的難題[7]。因此，在保證一定精度的前提下，對海量點云數(shù)據(jù)進行壓縮是必要的。目前點云壓縮算法主要有2種：直接基于點云的壓縮和基于網格的壓縮[8]。前者直接根據(jù)點云空間拓撲關系計算對應的離散幾何信息對點云進行精簡處理，但壓縮數(shù)據(jù)在細節(jié)特征上容易損失[9-10]。基于網格的壓縮需要構建三角網格，而這是一項耗時復雜的工作，效率低下[11-13]。本文基于切片技術[14-15]提出一種新的自適應點云壓縮算法。該算法基本思路為，先將點云進行分層形成點云切片，在此基礎上使用矢量-角度法逐層進行點云壓縮。

1 算法介紹

1.1 自適應切片點云生成

形成點云切片的基本步驟是建立點云的最小包圍盒，通過分割包圍盒得到小分割塊，在每個分割塊上建立切片點云。算法流程如圖1所示。

1.1.1 包圍盒的初步分割

最小包圍盒是在三維坐標系中將模型包含在內的最小立方體。假設點云集為p={p1,p2,…,pn}，pi為(xi,yi,zi)∈R3。最小包圍盒通常按照模型坐標的最大值和最小值確定，即為|xmax-xmin|、|ymax-ymin|、|zmax-zmin|，那么形成最小包圍盒B=[xmin,xmax]×[ymin,ymax]×[zmin,zmax]，分割方向可以自定義，一般沿坐標軸進行分割。若沿z軸分割包圍盒，將最小包圍盒B作均勻分割，得到n個平行的小長方體Bzi，i=0,1,2,…，n-1。由于初始分割沒有考慮點云密度變化的問題，接下來要對密度過大的分割塊進行迭代分割。

圖1 自適應切片算法流程

1.1.2 對包圍盒進行迭代分割

1.1.3 點云切片的建立

1.2 矢量-角度法

點云切片數(shù)據(jù)屬二維數(shù)據(jù)，這樣就簡化了下一步的壓縮運算。如果單獨使用角度閾值進行數(shù)據(jù)精簡，當2個點相距較遠時，即使夾角很小，最短距離也可能很大，這時不能單憑角度就將其刪除；當2個點相距較近時，最短距離很小也可能有較大的夾角，這時也不能由于最短距離小而將其刪除。因此，采用矢量-角度法能克服上述缺點，快速有效地精簡數(shù)據(jù)。矢量-角度法示意圖如圖2所示。

(1)

由向量的方向性可知，根據(jù)r值的不同，最短距離d可以計算為

(2)

圖2 矢量-角度法

當夾角大于或小于所設的夾角閾值，或最短距離小于所設閾值時說明形狀變換平緩，應當刪除該點。當某點滿足以下2個條件之一時，說明該點處形狀變換平緩，應當刪除該點：一是最短距離小于所設閾值；二是夾角小于或大于某個閾值(本文把該閾值稱為特征角度)。自定義的閾值參數(shù)可由不同的指標定義，由圖2可以看出，閾值的取值決定壓縮率和壓縮質量。當閾值過大時刪除的數(shù)增多，此時只有形狀變化劇烈的地方才能保留較多的點，很多細節(jié)和小特征將丟失；當閾值過小時，刪除的點數(shù)變少，得不到理想的壓縮效果。因此，選取適合的閾值在提高壓縮率的同時保證重要細節(jié)特征非常關鍵。

本文用點云數(shù)據(jù)分層后每層的最短距離均值分布選取閾值，角度閾值通過試驗予以給定。每層的最短距離均值由式(3)計算得到

(3)

2 算法實現(xiàn)及對比分析

本文試驗的硬件環(huán)境為Intel i3-2310處理器、6 GB內存，軟件環(huán)境為VS2015、PCL點云庫。試驗數(shù)據(jù)采用從Leica官網下載的Gate點云數(shù)據(jù)，原始點云總共包含320 557個點。

2.1 確定分層數(shù)目

初始分層數(shù)目對最終的分層結果，以及執(zhí)行時間和壓縮率有比較大的影響，由于閾值參數(shù)對分層結果沒有影響，本文隨機選取了一個角度閾值進行試驗。圖3為設定角度閾值為α>140°或α<40°時使用不同分層數(shù)對Gate點云模型壓縮的結果。

圖3 模型分層數(shù)與時間、壓縮率的關系

從圖3可以看出，算法的執(zhí)行時間隨著分層數(shù)目的增加而隨之增加，壓縮率隨著分層數(shù)的增加而逐漸減少。圖3(a)是分層數(shù)和執(zhí)行時間的關系，當分層數(shù)比較小，如30～90層時隨著分層數(shù)的變大執(zhí)行時間急速增大；大于100層后隨著分層數(shù)的增加執(zhí)行時間小幅增加；大于110層時執(zhí)行時間的增幅趨于穩(wěn)定。圖3(b)是分層數(shù)與壓縮率的關系圖，當分層數(shù)較小時，增加分層數(shù)會讓壓縮率銳減；大于100層后，隨著分層數(shù)的增加壓縮率小幅度降低，大于110層時，壓縮率的變化逐漸趨于穩(wěn)定。綜合二者考慮，當分層數(shù)為100時算法有較高的效率又能保證壓縮率，是試驗的最適合層數(shù)。最終的分層結果如圖4所示。

圖4 最終分層結果

2.2 確定最短距離和角度閾值

對試驗數(shù)據(jù)設定分層數(shù)為100，選取相同的角度閾值不同最短距離平均閾值進行壓縮，其結果如圖5所示。從圖5可以看出壓縮率隨閾值遞增呈顯著上升趨勢。大壓縮率是算法追求的效果之一，但是在壓縮率大的同時，被刪除點數(shù)增多，壓縮對象的細節(jié)與特征可能會有丟失，因此最短距離閾值的選取十分重要。圖6為原始數(shù)據(jù)點云分層為100時每層的最短距離平均值分布情況，可以看出每層的最短距離均值最小值為0.06 mm、最大值為0.23 mm。

圖5 平均閾值與壓縮率的關系

圖6 每層最短距離均值分布

分別設最短距離閾值為0.05 mm(小于最短距離均值最小值)和0.2 mm(在最短距離均值最小值與最大值之間)，對點云數(shù)據(jù)進行壓縮，其壓縮結果如圖7所示。其中，圖7(a)是原始點云數(shù)據(jù)，圖7(b)是閾值為0.05 mm時的壓縮結果，壓縮率為65.41%。圖7(b)中點云模型的輪廓特征，裝飾紋理、雕刻紋理處仍然可以很好地表現(xiàn)出來，壓縮效果和壓縮率較為理想。圖7(c)是閾值為0.2 mm時的壓縮效果，壓縮率為76.05%。從圖7(c)可以明顯看出壓縮后的輪廓線已近變形，部分部位點云丟失嚴重。因此，為了保證壓縮質量，切片點云的最短距離均值選取是重要的參考量，為了很好地保留點云特征和細節(jié)，應該選取小于該值的數(shù)作為閾值。

圖7 原始點云與不同閾值壓縮點云對比

角度對點云壓縮質量有重要影響，為了得出合適的角度閾值，本文采取以下試驗方式：對試驗數(shù)據(jù)設定分層數(shù)為100，取不同的角度閾值進行壓縮，通過分析角度和時間(壓縮率)之間的關系確定適合的閾值，結果如圖8所示。從圖8(a)可以看出壓縮率隨著特征角度的增大逐漸降低，特征角度α>140°或α<40°時(對應圖8橫坐標3)，隨著特征角度的變化壓縮率變化趨勢逐漸放緩。圖8(a)橫坐標值為0°時，只把最短距離作為閾值進行點云壓縮，可以看出相比有角度閾值時壓縮率急劇下降，并且從圖8(b)可以看出只有最短距離閾值的壓縮時間和角度-最短距離閾值相差不多。試驗結果表明α>150°或α<30°(對應圖中橫坐標4)為最適合的角度閾值。

注：圖中橫坐標1—7分別代表特征角度α>120°或α<60°、α>130°或α<50°、α>140°或α<40°、α>150°或α<30°、α>160°或α<20°、α>170°或α<10°、α=180°。圖8 角度與壓縮率、時間的關系

2.3 壓縮結果比較和評價

點云精簡評價多采用目視的方式，也可用體積變化率進行壓縮效果評價，本文采用這兩種方式對壓縮結果進行評價。為了驗證本文算法的優(yōu)越性，在壓縮率基本相同的情況下，將隨機采樣法、曲率法、文獻[14]算法、文獻[15]算法與本算法進行比較，各算法壓縮結果見表1，點云壓縮效果和建模效果如圖9、圖10所示。

表1 Gate模型不同壓縮方法對比結果

通過表1、圖9和圖10可知，本文算法在既沒有大的形狀變化也沒有小特征的平坦處保留較少點，在形狀變化劇烈及細節(jié)特征很多處，保留了大量的點。通過和原始點云圖9(a)對比不難發(fā)現(xiàn)本文算法能保證在較高壓縮率的情況下自適應地刪除點，即根據(jù)點云模型的特征在平坦處刪除大量的點，在特征處保留大量的點，這樣不但保證了點云壓縮的效率而且很好地保留了點云模型的特征，并且花費時間相對較少。對壓縮后的點云進行建模時，本文算法基本沒有出現(xiàn)孔洞，而且在柱體花紋、門洞彎曲處、大門左右雕刻處等特征部位保留了更多的細節(jié)，建模結果與原始點云基本沒有區(qū)別。其他4種方法在不同部位過度壓縮產生了孔洞，而且細節(jié)特征有著不同程度的丟失。

圖9 原始點云與壓縮點云對比

圖10 原始點云與壓縮點云建模對比

3 結 語

針對點云數(shù)據(jù)量大，冗余數(shù)據(jù)多，影響點云數(shù)據(jù)后續(xù)處理的問題，本文結合包圍盒理論，提出了基于自適應切片點云的矢量-角度法實現(xiàn)對點云的壓縮。該壓縮算法的分層數(shù)與算法執(zhí)行時間和壓縮效率相關，角度和最短距離閾值的取值大小決定特征細節(jié)點的保留與否。本文通過試驗確定了點云壓縮的最短距離和角度參數(shù)的最佳取值，利用該算法對Gate點云數(shù)據(jù)進行壓縮，并對壓縮結果進行分析，結果表明，該算法在快速壓縮的同時具有較高的壓縮率，并且能夠很好地保留原模型的細節(jié)特征信息。