張旭康，牛保寧，張錦文

太原理工大學(xué) 信息與計算機(jī)學(xué)院，太原 030000

1 引言

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

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

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

本文的創(chuàng)新如下：

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

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

（3）CVS 復(fù)原算法利用壓縮算法在壓縮時生成的曲率信息，對壓縮后點(diǎn)云進(jìn)行增厚增稠處理，可有效復(fù)原點(diǎn)云模型細(xì)節(jié)。

2 相關(guān)工作

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

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

3 CVS 壓縮算法

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

3.1 L3A 相似度

如圖1 所示，V1、V2是兩個從原點(diǎn)出發(fā)的向量，標(biāo)號①、⑤分別代表向量V1、V2的長度，記作L(V1)、L(V2)。標(biāo)號②、③、④分別代表向量V1與坐標(biāo)軸X、Y、Z的夾角的余弦，記作A(V1,X)、A(V1,Y)、A(V1,Z)。標(biāo)號⑥、⑦、⑧分別代表向量V2與坐標(biāo)軸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相似與否的函數(shù)定義如下：

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

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

Fig.2 Vector graph formed by coordinates of multiple clusters of point clouds connected to origin圖2 多團(tuán)點(diǎn)云坐標(biāo)與原點(diǎn)連接形成的向量圖

3.2 參考向量采樣空間生成

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

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

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

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

3.3 參考向量采樣空間形狀與閾值的關(guān)系

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

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

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

3.4 曲面信息的計算

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

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

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

曲面曲率反映曲面的彎曲程度。可通過計算曲面曲率來判斷三維點(diǎn)云模型中曲面變化波動較大的區(qū)域，即特征區(qū)域。特征區(qū)域壓縮時可采用較低的壓縮率，或者不壓縮，以保留模型的細(xì)節(jié)特征。使用下面的曲率計算式（7）、式（8）、式（9）和二次隱式曲面方程的6 個系數(shù)，可以計算該曲面的平均曲率Km、高斯曲率Kg、極大曲率Kmax。

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

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

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

3.5 CVS 參數(shù)閾值的設(shè)定與調(diào)整

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

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

3.6 CVS 壓縮算法

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

算法1 CVS 壓縮算法

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

4 CVS 點(diǎn)云復(fù)原算法

CVS 點(diǎn)云復(fù)原需要使用CVS 點(diǎn)云壓縮階段產(chǎn)生的復(fù)原信息數(shù)據(jù)。

4.1 CVS 點(diǎn)云復(fù)原算法原理

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

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

4.2 三維坐標(biāo)點(diǎn)的產(chǎn)生和添加

C是一個點(diǎn)云添加器，S是某采樣區(qū)域添加點(diǎn)云集合，有：

P是一個立方體點(diǎn)云產(chǎn)生器，設(shè)立方體點(diǎn)云集合為L，則有：

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

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

4.3 CVS 復(fù)原算法

CVS 復(fù)原算法由算法2 所示，函數(shù)Getvector 從壓縮文件CPS 中讀入?yún)⒖枷蛄炕蛘咂胀ㄏ蛄縋，如果P是參考向量則算法需要通過函數(shù)Getreinfo 從復(fù)原信息Reci 中讀入與該參考向量相關(guān)的所有參數(shù)閾值P.Info，生成采樣空間，否則將點(diǎn)輸出到復(fù)原點(diǎn)云文件Rec。然后點(diǎn)云產(chǎn)生器Pointsgen 根據(jù)復(fù)原信息P.Info產(chǎn)生點(diǎn)云集合，根據(jù)采樣空間中的曲面信息選取產(chǎn)生器中的點(diǎn)形成集合p，并輸出到復(fù)原點(diǎn)云文件Rec中。所有的向量處理完后模型復(fù)原結(jié)束。

算法2 CVS 復(fù)原算法邏輯

5 實(shí)驗(yàn)分析

本章通過一組實(shí)驗(yàn)驗(yàn)證本文所提出的算法的壓縮效果、壓縮速度和復(fù)原效果。

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

實(shí)驗(yàn)?zāi)Ｐ蛿?shù)據(jù)：為了驗(yàn)證算法的有效性，本文使用斯坦福兔子模型、維納斯模型、人頭骨模型、龍模型、佛模型進(jìn)行實(shí)驗(yàn)。兔子、維納斯、人頭骨模型數(shù)據(jù)量小，特征區(qū)域多且易辨別，容易顯示算法壓縮和復(fù)原效果。龍模型和佛模型數(shù)據(jù)量大，且表面復(fù)雜，可用于研究算法對于大數(shù)據(jù)量模型的壓縮效率和效果。表1 是模型自身參數(shù)。

Table 1 Model information used in experiment表1 實(shí)驗(yàn)?zāi)Ｐ托畔?/p>

5.1 實(shí)驗(yàn)設(shè)計

5.1.1 點(diǎn)云壓縮實(shí)驗(yàn)

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

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

對比算法如下：

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

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

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

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

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

5.1.2 點(diǎn)云壓縮復(fù)原實(shí)驗(yàn)

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

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

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

5.2 算法效果分析

5.2.1 點(diǎn)云壓縮實(shí)驗(yàn)結(jié)果分析

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

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

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

Fig.6 Point cloud of CVS,PCL and K-means compression algorithm experimental results圖6 CVS、PCL、K-means壓縮算法實(shí)驗(yàn)結(jié)果點(diǎn)云圖

Fig.7 Point cloud of Dragon model compression experiment result圖7 龍模型壓縮實(shí)驗(yàn)結(jié)果點(diǎn)云圖

Fig.8 Point cloud of Buddha model compression experiment result圖8 佛模型壓縮實(shí)驗(yàn)結(jié)果點(diǎn)云圖

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

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

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

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

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

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

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

5.2.2 點(diǎn)云壓縮復(fù)原實(shí)驗(yàn)結(jié)果分析

圖9、圖10 分別是三個模型在CVS 壓縮復(fù)原算法下的實(shí)驗(yàn)結(jié)果建模圖和點(diǎn)云圖，第一行是斯坦福兔子模型，第二行是維納斯模型，第三行是頭骨模型。

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

Fig.10 Point cloud of CVS compression and restoration algorithm圖10 CVS 壓縮復(fù)原算法點(diǎn)云圖

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

Table 7 Point numbers of three models in CVS compression and restoration表7 三個模型在CVS 算法中的壓縮復(fù)原點(diǎn)數(shù)

Fig.11 Enlarged detail of CVS compressed and restored skull model圖11 CVS 壓縮和復(fù)原頭骨模型的細(xì)節(jié)放大圖

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

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

6 結(jié)束語

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