向量相似度可復原三維點云壓縮算法*

張旭康，牛保寧，張錦文

太原理工大學 信息與計算機學院，太原 030000

1 引言

三維激光掃描技術又被稱為實景復制技術，激光掃描系統可以快速、自動、實時地獲取目標物體表面的高精度三維點云數據。該技術被廣泛應用于文物古跡保護、建筑、規劃、醫學、土木工程、工廠改造、室內設計等領域[1-5]。三維激光掃描儀掃描物體產生的數據量十分龐大，含有大量冗余數據。后期的數據處理、傳輸和使用要耗費大量的時間和空間資源。因此，在保留重要模型特征的前提下，壓縮點云數據，減少點云數據量，成為目前點云數據處理的主要任務之一。

當前的點云壓縮算法主要有三類[6]：概率壓縮、網格壓縮、曲率壓縮。概率壓縮算法隨機地剔除模型中一部分點，每個點的剔除概率相同，只需進行一次點云遍歷，實現簡單，運行速度快，時間和空間復雜度低。但此類算法沒有考慮模型特征點區域，無法保證模型特征的完整性和精度。網格壓縮算法，使用六面體或者四面體等形狀的網格，將模型分為多個部分分別壓縮。該類算法為了保證模型壓縮精度，需要增加網格的個數，導致算法時間和空間復雜度高，網格數據也會占用大量的內存空間。曲率壓縮算法，根據模型表面的曲率大小和變化幅度來提取三維模型的細節特征，特征保留效果較好，但是在模型表面平緩、變化幅度小的部位，不能很好地控制點的留存度。由于三維模型的表面特征復雜，被去除的點可能跨越多個復雜曲面或多層曲面，造成被壓縮的點集合雜亂、無規律，難以組織用于復原，因此這些點云壓縮算法沒有對應的點云復原算法。

針對點云壓縮算法存在的以上問題，本文提出一種易于實現、能夠保留模型重要特征的向量相似點云壓縮算法，以及與該壓縮算法對應的點云復原算法CVS（compression based on vector similarity）。CVS 能夠較好地保留模型的細節特征，復原精度高，時間復雜度為O(n2)。

本文的創新如下：

（1）提出一種新的向量相似度度量——L3A 相似度。對于兩個從原點出發的向量，L（length）是它們長度差值的絕對值，3A（angle）是它們與三個坐標軸夾角余弦的差的絕對值。L3A 用來判斷點云的稠密程度。

（2）CVS 壓縮算法根據L3A 相似度，生成覆蓋整個模型的參考向量采樣空間集合，對每個采樣空間按照其曲面曲率，確定剔除數據點的概率，以保留模型的細節特征。

（3）CVS 復原算法利用壓縮算法在壓縮時生成的曲率信息，對壓縮后點云進行增厚增稠處理，可有效復原點云模型細節。

2 相關工作

基于曲率的點云壓縮算法主要通過度量曲面的變化程度來判斷模型的特征區域，盡可能地保留特征點。Han 等人[7]利用邊緣點和非邊緣點法向量的不同，保留模型邊緣點，維持點云的細節特征。符晨曦等人[8]提出法向量夾角法和曲率采樣法協同的壓縮算法，減少平坦區域內的點，保留高曲率區域內的點，來保證細節特征不丟失。陳朋等人[9]提出點到平面距離的點云數據壓縮方法，該方法計算每個模型點到其最近三個點組成平面的距離，通過距離的大小來判斷模型表面的復雜程度?；谇实乃惴ㄌ崛√卣鼽c的效果較好，但是不能控制平坦區域的壓縮程度，容易出現過壓縮現象，而且這些壓縮算法均沒有對應的點云復原方法。

基于網格的點云壓縮主要通過創建多個體積相同的網格將模型分為多塊，進行分塊壓縮，同時結合曲率、聚類等算法來提高特征保留度。付忠敏等人[10]提出基于主成分分析與柵格劃分的壓縮算法，用柵格劃分模型，用主成分分析算法保留模型特征區域不被壓縮。但是此算法容易在模型平緩部位產生過度壓縮現象。姚頑強等人[11]提出基于改進八叉樹的三維點云壓縮算法，能夠有效地去除離群點，較完整地保留關鍵信息。陳龍等人[12]使用八叉樹創建聚類中心，然后使用K-means 聚類算法確認特征區域，并計算區域中點的曲率法向量與鄰域點法向量夾角的平均值等多個參數來提高特征點的保留效果。葉珉呂等人[13]使用KDtree 構建鄰域，創建拓撲，計算模型曲率壓縮點云。這些基于網格的算法在構建網格時需要消耗較多的時間和空間，尤其是使用較復雜的算法如聚類算法、主成分分析算法提取特征區域時，隨著模型數據量的增加，壓縮時間顯著增加。

3 CVS 壓縮算法

CVS 壓縮算法的核心是L3A 相似度。

3.1 L3A 相似度

如圖1 所示，V1、V2是兩個從原點出發的向量，標號①、⑤分別代表向量V1、V2的長度，記作L(V1)、L(V2)。標號②、③、④分別代表向量V1與坐標軸X、Y、Z的夾角的余弦，記作A(V1,X)、A(V1,Y)、A(V1,Z)。標號⑥、⑦、⑧分別代表向量V2與坐標軸X、Y、Z的夾角的余弦值，記作A(V2,X)、A(V2,Y)、A(V2,Z)。

Fig.1 Definition of L3A similarity圖1 L3A 相似度定義

四元組(Δlength,ΔangleX,ΔangleY,ΔangleZ)表示向量V1和V2的相似程度，被稱作L3A 相似度。判別V1和V2相似與否的函數定義如下：

ΔL是V1和V2長度差的絕對值上限，ΔAX、ΔAY、ΔAZ分別是V1和V2與坐標軸X、Y、Z的夾角余弦的差的絕對值上限。如果四元組中四個值均分別小于或等于四個閾值，函數值為1，表示向量V1與V2相似。否則，輸出0，表示兩個向量不相似。

圖2 是將點云中每個點與原點連接形成向量后的示意圖。區域①和②點云較密，向量之間的長度和夾角都相近。區域③點云較疏，向量之間的長度相差較大，夾角相近。區域④點云較疏，向量之間長度相近，夾角相差較大。在三維模型的一個稠密點云區域中，會存在大量的位置相近的點，這些點分成多個相鄰的子區域并映射到向量空間，每個子區域會呈現出上圖標號①、②區域周圍向量的特點，即向量之間的L3A 相似度四元組中的四個值的變化范圍均很小。而稀疏點云區域中的點映射到向量空間，每個子區域的向量之間的L3A 相似度四元組中的四個值的變化范圍均很大。

Fig.2 Vector graph formed by coordinates of multiple clusters of point clouds connected to origin圖2 多團點云坐標與原點連接形成的向量圖

3.2 參考向量采樣空間生成

函數f()有6 個參數，4 個閾值可以分別被看作是一個向量的長度值與X、Y、Z坐標軸角度余弦的最大變化范圍。給定向量V1和4 個閾值，所有與V1相似的向量V2構成了一個相似向量空間。向量V1被稱為參考向量，閾值確定時，向量V1生成的相似向量空間被稱為采樣空間。

CVS 選取多個參考向量，并設定閾值，使得這些參考向量生成的采樣空間集合能夠覆蓋整個點云。在每個采樣空間中根據曲率大小使用概率算法保留或者剔除其中包含的點。圖3 是使用小車模型生成若干個參考向量的示意圖。參考向量選取可以通過算法自動生成，其數量因模型而異，詳細算法在第3.6節介紹。

Fig.3 Reference vectors generated in car model圖3 在小車模型中生成若干個參考向量

采樣區域的大小與參考向量對應的四個閾值的大小成正比。當參考向量對應的四個閾值確定時，長度越大的參考向量生成的采樣空間越大，這樣會導致模型邊界區域的采樣空間壓縮掉過量的點。因此需要建立閾值ΔAX、ΔAY、ΔAZ與向量長度L(V)的約束關系。使得參考向量長度變化時，形成的參考向量區域大小基本保持不變。

3.3 參考向量采樣空間形狀與閾值的關系

參考向量生成的采樣空間形狀取決于閾值。通常三個角度閾值取相同的值，用ΔA表示。ΔA影響采樣區域坐標軸方向擴展的廣度。ΔL影響采樣區域向量方向拉伸的深度。ΔL、ΔA越大，采樣空間體積越大；反之越小。ΔL增大ΔA減小，采樣空間變長；ΔL減小ΔA增大，采樣空間變扁。

圖4（a）的閾值參數為ΔL=13，ΔA=1（大距離、大角度），整個空間的點都和向量相似，點云壓縮變成了全局壓縮。圖4（b）的閾值參數為ΔL=0.1，ΔA=1（小距離、大角度），采樣區域形成“洋蔥”，即分層壓縮的形式。圖4（c）的閾值參數為ΔL=0.11，ΔAY=0.08，ΔAX=ΔAZ=0.5，壓縮空間呈帶狀。圖4（d）的閾值參數為ΔL=0.1，ΔA=0.05（大距離小角度），采樣區域呈棒狀。

Fig.4 Relation between shape of reference vector sampling space and threshold value圖4 參考向量采樣空間形狀與閾值的關系

3.4 曲面信息的計算

本文使用最小二乘曲面擬合方法計算采樣區域包含曲面的曲面方程[14]。使用式（9）計算采樣區域曲面曲率值[15]。

三維模型點云表面劃分為多個區域，每個區域的點云構成一個簡單的曲面等值面，這些曲面等值面用一個簡單的隱式二次方程近似表示。如下式：

用最小二乘擬合曲面法，用至少7 個曲面等值面中的點云坐標，求解線性方程組，得出曲面方程的6個系數，最終得到曲面等值面的二次隱式方程的近似表示。

曲面曲率反映曲面的彎曲程度?？赏ㄟ^計算曲面曲率來判斷三維點云模型中曲面變化波動較大的區域，即特征區域。特征區域壓縮時可采用較低的壓縮率，或者不壓縮，以保留模型的細節特征。使用下面的曲率計算式（7）、式（8）、式（9）和二次隱式曲面方程的6 個系數，可以計算該曲面的平均曲率Km、高斯曲率Kg、極大曲率Kmax。

計算曲面系數需要生成并求解六元一次非齊次方程組，該方程組各系數的計算需要累加曲面等值面的點云坐標求出。CVS 算法利用方程組系數計算需要累加的特點，每讀入一個點可動態實時完成采樣區域中已生成但不完整的等值面曲面方程與曲面曲率計算，并根據計算的曲面曲率的大小，設定曲率閾值動態實時調整各采樣區域中點云壓縮程度。如計算出的曲面曲率大于某個閾值，則降低點云壓縮程度。當所有點云被讀完，每個采樣區域中的等值面曲面即生成完畢。記錄最終生成的曲面方程以及坐標范圍參數，形成點云復原信息文檔，用來復原點云。

CVS 使用最小二乘法計算曲面方程。曲面方程的計算從采樣空間集齊6 個坐標開始。根據文獻[14]中的二次曲面擬合方法可知，6 個以上的曲面坐標可導出曲面方程系數為未知數的六元一次方程組，使用高斯消元解方程組即可得出曲面方程。曲面曲率極大值曲率可根據式（7）、式（8）、式（9）直接由曲面方程系數計算得出。

CVS 采用最小二乘法擬合二次曲面得出曲面方程，然后直接用曲面方程的6 個參數計算出曲面曲率極大值。因此曲率的計算準確度取決于擬合曲面的擬合效果。如果在采樣區域內擬合的二次曲面能緊緊貼合到采樣區域中散點組成的曲面，說明擬合效果較好，計算的曲率值較準確。而擬合效果取決于參考向量參數閾值的選取。調小參數閾值，可以降低參考向量采樣區域中包含曲面的復雜程度，以提高該采樣區域的曲面擬合效果。

3.5 CVS 參數閾值的設定與調整

由3.2 節可知，合理地選擇參考向量采樣空間使用的閾值可使稀疏區域選取的向量生成的采樣空間所含點的密度較低，甚至不含點；稠密區域選取的向量生成的采樣空間中，所含點的密度較高；使得在相同壓縮概率下，稠密區域被剔除點的數目大于稀疏區域的剔除點的數目。在采樣區域中可設置多級曲率閾值，以使曲率越高的曲面被剔除的點越少，甚至不剔除。

參數閾值的選取和三維模型本身的性質有關。目前參數的選取通過實驗來設置。ΔA按照實驗經驗值其初始值一般設為0.03。這個閾值下生成的采樣區域基本不會跨越模型多個曲面。ΔL初始值與模型點坐標值的數量級有關，其初始值設為模型中所有的坐標值中最低數量級的低一個數量級乘一。如三維模型中每一個坐標點的坐標值的數量級是10-1，則將ΔL設置為0.01。調低ΔA、ΔL可使得采樣區域更小更精細，曲面采樣越不容易跨越復雜曲面，從而保留更多復雜特征，但會增加采樣區域個數，降低算法效率。反之，調高ΔA、ΔL會使得采樣區域大而少，在提升算法效率的同時也會讓特征保留效果變差?？梢愿鶕Ｐ偷男螤钐攸c適當調整采樣區域使其變長或者變扁來調整壓縮效果。根據CVS 中曲面信息計算方法計算各個采樣區域的曲率并計算均值來選取曲率閾值初始值。ΔA與向量長度的反比關系可以采用反比例函數，如ΔA=factor/L(V)，其factor值由模型離原點最近點與原點連接生成向量的長度乘ΔA的初始值得到。

3.6 CVS 壓縮算法

CVS 壓縮算法如算法1 所示。CVS 壓縮需要循環從文件中讀入PS 中的三維坐標點，并將這些點轉換為向量SP，查看這些向量是否屬于已有的參考向量S的采樣空間S.Samplespace。如果不屬于任何采樣空間，則將此向量歸入采樣空間數組REF，并生成采樣空間，否則將向量歸入其所屬采樣空間S.Samplespace。此方法可使得模型所有的坐標點要么被轉化為參考向量，要么就歸入其所屬的參考向量采樣空間中，實現自動選取一組參考向量并生成采樣空間集合以覆蓋整個模型區域的功能。在采樣空間S.Samplespace 內計算當前采樣點云生成的曲面等值面的曲面方程和曲率極大值，并統計各種復原信息S.Info。函數Adramrange 根據曲面曲率閾值調整隨機數接受閾值R，并使用Proramvalue 函數產生隨機數r。如果曲率的極大值超出了設定的曲率閾值的設定范圍，說明該曲面曲率較大，屬于復雜曲面，則降低該曲面的點壓縮概率。需要保留的點會被寫入壓縮點云文件CPS。所有點讀入并處理后，將每個采樣空間的統計信息Ref.Rec.Info 輸出到文件中形成復原信息文件Reci，最后將所有的參考向量Ref.Rec輸出到壓縮點云文件中，并在文件中做出標示。

算法1 CVS 壓縮算法

由算法1 可知，壓縮算法中存在雙重循環。第一重循環用來遍歷三維模型中的坐標。第二重循環用來為每個坐標查找其所屬的采樣空間。最壞情況下，每個坐標點都無法找到其所屬的采樣空間，即所有的坐標都被轉換為參考向量。則讀入n個坐標需要查找n2次采樣空間，時間復雜度為O(n2)。曲面方程計算的高斯消元時間復雜度是O(n3)，CVS 中n為定值6，因此CVS 中高斯消元的時間復雜度為O(1)。CVS 每讀入m個模型點，其所屬的采樣空間就會計算一次曲面方程，可知CVS 中曲面方程計算的時間復雜度為，即O(n)。由式（7）、式（8）、式（9）可看出，曲率計算可直接由曲面方程系數計算得出，其在CVS 中的時間復雜度為O(n)。因此CVS 壓縮算法的復雜度是O(n2)。方程擬合和曲率的計算不影響CVS 壓縮算法整體的時間復雜度。

4 CVS 點云復原算法

CVS 點云復原需要使用CVS 點云壓縮階段產生的復原信息數據。

4.1 CVS 點云復原算法原理

點云復原算法是點云壓縮算法的逆過程。點云壓縮算法剔除冗余點并存儲曲面信息，點云復原算法利用曲面信息，生成符合曲面方程的坐標點添加到被簡化的模型中。為了讓點云復原算法達到最佳效果，要求點云壓縮時每個采樣區域不能跨越多個曲面，這可以通過調整點云壓縮參數閾值，使得采樣區域的曲面等值面光滑、規則。

點云復原信息在點云壓縮階段產生，包括點云壓縮的4 個參數閾值、每個采樣區域的壓縮點云個數、擬合的曲面方程的6 個系數、曲面上點X坐標的最小最大值、曲面上點Y坐標的最小最大值、曲面上點Z坐標的最小最大值、采樣區域兩兩向量之間長度差值絕對值最大值。點云復原以參考向量作為參照，完成點云復原。被標示出的參考向量連同復原信息中保存的各個參數閾值在點云壓縮的時候記錄和統計，點云壓縮完成后，記錄為文件并保存。

4.2 三維坐標點的產生和添加

C是一個點云添加器，S是某采樣區域添加點云集合，有：

P是一個立方體點云產生器，設立方體點云集合為L，則有：

其中，XS、YS、ZS是X、Y、Z軸數值范圍的下限，XE、YE、ZE是X、Y、Z軸數值范圍的上限，SX、SY、SZ是X、Y、Z從下限增長到上限的步長。Select是一個點篩選器，Method是篩選方法。式（6）是計算曲面Z坐標的計算式。V(x,y,z)是三維坐標的轉換器，該轉換器將三維坐標轉換為過原點的向量。設xi∈[XS,XE]，yi∈[YS,YE]，zi∈[ZS,ZE]，P會產生所有符合上述條件的(xi,yi,zi)∈L。且有：

使用一個點產生器P產生一個以曲面上點的X坐標變化范圍數值為長，Y坐標變化范圍為寬，Z坐標變化范圍為高的一個實心立方體點云。該立方體點云可以完全包含被采樣曲面中的所有點。Method通過復原信息中的曲面方程系數可以組建方程，并根據產生器中每個點的xi和yi，計算出對應的曲面Z坐標值zi，進而得曲面向量的長度。然后使用Select將曲面上計算出的向量長度和產生點對應的向量長度相減取絕對值，這個絕對值和向量長度變化區間max進行比較，1 表示留下，0 表示剔除。通過調整變化值的大小，可以實現添加點云層的厚薄控制。通過調整點產生器P中SX、SY、SZ步長大小，控制產生點云的疏密程度。

4.3 CVS 復原算法

CVS 復原算法由算法2 所示，函數Getvector 從壓縮文件CPS 中讀入參考向量或者普通向量P，如果P是參考向量則算法需要通過函數Getreinfo 從復原信息Reci 中讀入與該參考向量相關的所有參數閾值P.Info，生成采樣空間，否則將點輸出到復原點云文件Rec。然后點云產生器Pointsgen 根據復原信息P.Info產生點云集合，根據采樣空間中的曲面信息選取產生器中的點形成集合p，并輸出到復原點云文件Rec中。所有的向量處理完后模型復原結束。

算法2 CVS 復原算法邏輯

5 實驗分析

本章通過一組實驗驗證本文所提出的算法的壓縮效果、壓縮速度和復原效果。

實驗環境：本文算法通過C 語言編程實現，實現平臺為Intel?CoreTMi5-4670 CPU @3.4 GHz 處理器，4 GB 內存，1 TB 硬盤。使用軟件Meshlab 建模。

實驗模型數據：為了驗證算法的有效性，本文使用斯坦福兔子模型、維納斯模型、人頭骨模型、龍模型、佛模型進行實驗。兔子、維納斯、人頭骨模型數據量小，特征區域多且易辨別，容易顯示算法壓縮和復原效果。龍模型和佛模型數據量大，且表面復雜，可用于研究算法對于大數據量模型的壓縮效率和效果。表1 是模型自身參數。

Table 1 Model information used in experiment表1 實驗模型信息

5.1 實驗設計

5.1.1 點云壓縮實驗

壓縮實驗數據和參數：點云壓縮運行時間與模型文件數據量、壓縮參數的設置有關。模型壓縮時使用參數ΔA和向量長度關系ΔA=factor/L(V)。表2是五個模型在本文壓縮算法中使用的參數表。ΔC代表曲率閾值，CP表示采樣區域計算出的曲率值達到曲率閾值時的點保留概率，NCP表示采樣區域計算出的曲率值未達到曲率閾值時點保留概率。

Table 2 Parameter table of five models used in CVS compresion in this paper表2 五個模型在本文壓縮算法中使用的參數表

對比算法如下：

（1）PCL（point cloud library）開源點云庫[16]中基于八叉樹的區域重心點云降采樣算法，簡稱PCL，該算法是常用的點云壓縮算法，壓縮時間短，效率高。

（2）K-means 點云壓縮算法[12]，簡稱K-means，該算法使用基于K-means 聚類的方法判斷特征區域，模型特征保留效果較好。

（3）本文的CVS 壓縮算法。

壓縮效果實驗：分別用CVS、PCL 降采樣、Kmeans 算法壓縮斯坦福兔子模型、維納斯模型、頭骨模型、龍模型和佛模型的點云圖，通過觀察點云圖中的點云密度分布和建模后模型的表面積變化來比較壓縮效果。

壓縮速度實驗：分別用CVS、PCL 降采樣、Kmeans 算法壓縮斯坦福兔子模型、維納斯模型、頭骨模型的點云圖，比較壓縮時間。

5.1.2 點云壓縮復原實驗

點云壓縮復原實驗數據和參數：點云復原需要一定的條件才能夠達到最佳效果，即采樣區域未跨越多個曲面，且采樣區域中的曲面不難擬合。因此算法中L3A 相似度中的四個閾值取值越大，越不利于點云的復原。因此壓縮復原算法中三個模型的壓縮率較低。在CVS 點云壓縮和復原實驗中，兔子、維納斯、頭骨模型的還原效果最為明顯。Bunny和Skull模型壓縮使用的角度閾值與向量長度關系是ΔA=factor/L(V)。Venus 壓縮使用的關系是ΔA=factor/L(V)2。表3 列出了三個模型在CVS 壓縮復原算法中使用的參數表。

Table 3 Parameter table of three models used in CVS compression and restoration表3 三個模型在CVS 壓縮復原算法中使用的參數表

點云壓縮復原效果實驗：先使用CVS 壓縮算法壓縮斯坦福兔子模型、維納斯模型、頭骨模型。然后使用CVS 復原算法復原三個模型。通過觀察壓縮復原前后模型的點云密度分布以及根據建模后模型的表面積變化情況來比較點云復原效果。

5.2 算法效果分析

5.2.1 點云壓縮實驗結果分析

（1）CVS、K-means、PCL 壓縮效果分析

圖5 是斯坦福兔子模型、維納斯模型、頭骨模型的點云原圖。圖6 的（a）、（b）、（c）三列是兔子、維納斯、頭骨三個模型分別經CVS 壓縮算法、PCL 降采樣算法、K-means 算法壓縮后的點云圖。圖7、圖8 各自的（a）、（b）、（c）、（d）圖分別是龍模型和佛模型的點云原圖、經CVS 壓縮算法、PCL 降采樣算法、K-means 算法壓縮后的點云圖。表4 列出了各模型分別在三類壓縮算法中壓縮后的點數和壓縮率。

Fig.5 Point cloud of Bunny,Venus and Skull圖5 兔子、維納斯、頭骨模型點云原圖

Fig.6 Point cloud of CVS,PCL and K-means compression algorithm experimental results圖6 CVS、PCL、K-means壓縮算法實驗結果點云圖

Fig.7 Point cloud of Dragon model compression experiment result圖7 龍模型壓縮實驗結果點云圖

Fig.8 Point cloud of Buddha model compression experiment result圖8 佛模型壓縮實驗結果點云圖

表4 列出了各模型在三類算法中的壓縮率，說明算法對比是在兩者壓縮率相近的前提下進行。從圖6 的斯坦福兔子模型點云分布可看出，CVS 和Kmeans 壓縮產生的模型，在模型細節區域保留了較多的點，對應模型的細節顯示更加明顯。而PCL 降采樣算法產生的大密度點云區域相對較少。從圖6 的維納斯模型點云分布圖可以看出，CVS 和K-means 算法的大密度點區域集中在人物的面部，使得人物面部的細節更加明顯。而PCL 降采樣算法在人物面部的眉毛、嘴唇部位的點云密度較低，導致對應模型中的相應部位的建模不是很清晰。從人頭骨點云分布圖中可看出，CVS 和K-means 算法在人頭骨模型的牙齒、額頭圖案、頭上文字處等特征細節處保留了較多的點，所建模型相應細節顯示效果增強。從圖7 和圖8 的復雜龍模型和佛模型的壓縮效果來看，CVS 和Kmeans 在特征區域均保留了較多的點，而平緩區域點較少，但是不會使得平緩區域的點云過度稀疏。

Table 4 Compression ratio of each model in three types of algorithms表4 各模型在三類算法中的壓縮率

表5 列出了三類壓縮算法的表面積變化情況。PCL 壓縮的模型表面積變化均比其余算法的變化大，說明本文壓縮算法與K-means 算法對于模型的整體改變小于PCL 算法。且CVS 算法與K-means 的壓縮效果相當。

Table 5 Change of surface area of each model in three types of algorithms表5 各模型在三類壓縮算法中表面積變化

（2）CVS、K-means、PCL 壓縮速度分析

表6 是各模型分別在三個壓縮算法下的壓縮用時?？梢钥闯?，在相同壓縮率下，PCL 降采樣處理時間最短，K-means 最長，CVS 介于兩者之間。PCL 降采樣對于點云的處理較為簡單，它只將每個網格中的點云用這些點云的重心替代，故處理時間短，但是特征保留效果差。K-means 算法包含了聚類算法以及多重特征點判斷方法，雖然特征保留效果好，但是隨著點云數據量和模型復雜度的增加，特征提取聚類中心個數以及聚類的樣本數目也增加，使得算法的時間復雜度顯著增加，不適合用于大數據量的點云數據的處理。CVS 壓縮算法在小數據量和大數據量的處理中均使用了較少的時間，而且還保證了與K-means算法相近的特征保留效果。

Table 6 Compression time of each model in three types of algorithms表6 各模型在三類壓縮算法中壓縮用時

5.2.2 點云壓縮復原實驗結果分析

圖9、圖10 分別是三個模型在CVS 壓縮復原算法下的實驗結果建模圖和點云圖，第一行是斯坦福兔子模型，第二行是維納斯模型，第三行是頭骨模型。

Fig.9 Model of CVS compression and restoration algorithm圖9 CVS 壓縮復原算法模型圖

Fig.10 Point cloud of CVS compression and restoration algorithm圖10 CVS 壓縮復原算法點云圖

表7 提供了本實驗中模型的壓縮程度以及模型復原時添加的點的數目。圖10 的斯坦福兔子點云分布說明，點云復原后，復原模型的點云分布基本與原模型相當，模型細節有了大幅度的恢復，尤其是兔子耳朵部分與原模型相差無幾。從圖10 的維納斯點云分布圖可以看出，復原模型成功填補了壓縮模型中密度小的點云區域，如嘴部，使得相應部位的細節更加明顯細膩。圖10 的人頭骨圖點云分布圖表明復原算法成功復原增加了模型細節部分以及大量平坦部分區域的點的密度。從圖11 人頭骨建模圖可看出，人頭骨額頭的圖案有了明顯恢復。表8 的數據表明了復原后的模型表面積變化率變小，說明復原算法對模型表面積的恢復起到了一定的作用。

Table 7 Point numbers of three models in CVS compression and restoration表7 三個模型在CVS 算法中的壓縮復原點數

Fig.11 Enlarged detail of CVS compressed and restored skull model圖11 CVS 壓縮和復原頭骨模型的細節放大圖

Table 8 Model change in surface area in CVS compression and restoration表8 模型在CVS 壓縮復原算法中表面積變化

由以上實驗結果可以得出，CVS 算法通過調整閾值，可以生成覆蓋整個模型點云的采樣空間，使得點云稀疏的區域中，參考向量包含的點云較少，甚至不包含點云，而點云稠密的區域的參考向量包含較多的點云，然后根據點云疏密程度進行點云壓縮。而且CVS 在采樣空間中，根據曲率大小決定剔除的點云比率，實現模型平緩稠密區域的點云精簡，稀疏區域的點云保留，復雜稠密部位的點云低壓縮率，盡可能保留模型的細節特征。CVS 壓縮是在原模型的基礎上減少點云個數，不會從整體上修改模型點云的坐標，不會較大程度改變模型的整體形態。在CVS點云復原階段，可根據復原信息生成貼合模型外表的點云，恢復并增強模型的細節特征。

6 結束語

本文提出了一種新的向量間相似度L3A，并提出了使用該向量相似度實現點云模型壓縮復原的CVS算法。該算法能夠通過調節參數使得點云的壓縮和復原達到一個較好的效果。CVS 能夠很好地保留模型細節特征，有效地去除冗余點，且能使得點云密度較為稀疏的區域不會被過度壓縮而產生孔洞。通過三個模型的實驗結果和與PCL 點云庫使用的降采樣算法和K-means 點云壓縮算法進行對比分析，表明本文壓縮算法不但可以保留模型特征信息，還能盡量減少模型的表面積變化，壓縮時間短，適合處理大數據量的點云模型。CVS 點云復原也能有效恢復大量模型細節，使得點云模型更精細。