基于壓縮感知的三維人體點(diǎn)云的壓縮及重建

劉　佳

(西安電子科技大學(xué) 電子工程學(xué)院，陜西 西安 710071)

?

基于壓縮感知的三維人體點(diǎn)云的壓縮及重建

劉佳

(西安電子科技大學(xué) 電子工程學(xué)院，陜西 西安 710071)

摘要經(jīng)過激光掃描得到的三維人體點(diǎn)云數(shù)據(jù)量龐大，給模型的存儲和傳輸帶來困難，影響了其在體域網(wǎng)中的應(yīng)用。針對這一問題，將壓縮感知理論應(yīng)用于人體點(diǎn)云模型的壓縮與重建中。在壓縮之前使用改進(jìn)的三維柵格法做點(diǎn)云精簡，針對人體點(diǎn)云的特點(diǎn)對數(shù)據(jù)進(jìn)行分塊稀疏變換，利用正交匹配追蹤算法重建原始模型。最終實驗重建誤差約為 ，證實了該算法的有效性和可行性。

關(guān)鍵詞壓縮感知；點(diǎn)云精簡；分塊稀疏；匹配追蹤

三維人體點(diǎn)云模型是通過激光掃描技術(shù)，對物理人體進(jìn)行全方位掃描獲取的。感興趣的三維數(shù)據(jù)包括人體的身高、外形特征、體貌形態(tài)等元素。將采集到的數(shù)據(jù)經(jīng)過三維建模軟件可視化渲染后，方便后期參數(shù)調(diào)整和圖像處理，這在體域網(wǎng)的實驗研究中具有重要意義。但隨著三維掃描設(shè)備的快速發(fā)展，掃描獲得的數(shù)據(jù)量越來越大，占用的空間也越來越多，給存儲和傳輸過程帶來較大困難[1]，本文將壓縮感知理論應(yīng)用在三維人體點(diǎn)云的壓縮重建中，可有效解決上述問題。

1壓縮感知理論

壓縮感知理論指出[2-3]：具備稀疏特性的信號可被一個與變換基不相關(guān)的觀測矩陣投影到低維空間中，然后通過求解一個欠定方程的優(yōu)化問題就能從這些少量的投影中高概率地恢復(fù)原始信號。傳統(tǒng)的信號獲取過程，如圖1所示，需要很高的采樣頻率，但采集到的大部分?jǐn)?shù)據(jù)點(diǎn)在壓縮的過程中被舍棄，這樣無疑產(chǎn)生了浪費(fèi)。壓縮感知理論和傳統(tǒng)的信息處理的最大區(qū)別在于其將采樣和壓縮過程同時進(jìn)行，這樣就能以遠(yuǎn)小于奈奎斯特采樣定理所要求的采樣頻率采集并且較準(zhǔn)確地重建初始信號。

壓縮感知主要研究的數(shù)學(xué)問題如下[4]：N維的信號x∈RN×1映射到某一正交基{ψi}( 代表一個N維列向量)，即

(1)

x=Ψθ

(2)

此處Ψ=[ψ1,ψ2,…,ψN]∈RN×N是正交基字典矩陣，θ=[θ1,θ2,…,θN]T。若θ中的非零系數(shù)的個數(shù)K≤N，則稱θ是K稀疏的。采用一個與變換基矩陣Ψ不相關(guān)的觀測矩陣Φ:M×N(M?N)對信號進(jìn)行采樣壓縮

y=Φx

(3)

這樣就得到了M個線性測量結(jié)果，這一低維的測量結(jié)果已包含了重構(gòu)原始信號的足夠信息。壓縮感知重構(gòu)問題的實質(zhì)是在已知測量信號y和觀測矩陣Φ的條件下，怎樣快速精確重構(gòu)初始信號。

圖1　傳統(tǒng)的信號處理過程

2三維人體點(diǎn)云的精簡和稀疏表示

經(jīng)過激光掃描生成的點(diǎn)云數(shù)據(jù)量龐大，這給后續(xù)數(shù)據(jù)采樣壓縮和恢復(fù)階段的模型重構(gòu)帶來了不小的問題。通過分析點(diǎn)云中數(shù)據(jù)的密度等信息，可知點(diǎn)云中相鄰點(diǎn)的間距只有毫米量級，這已經(jīng)遠(yuǎn)超過了刻畫人體細(xì)節(jié)所需要的密度，所以通過合適的算法來精簡點(diǎn)云是可接受的[5]。

當(dāng)前點(diǎn)云精簡的基本方法主要有三維柵格法、三角網(wǎng)格法和曲率表示法等[6]。三維柵格法適用于外表光滑，曲率變化不明顯的模型精簡。三角網(wǎng)格法的思想是通過減少三角網(wǎng)格的數(shù)目來簡化點(diǎn)云，但這種方法首先要對點(diǎn)云數(shù)據(jù)進(jìn)行三角網(wǎng)格化處理。曲率表示法能將點(diǎn)云模型的細(xì)節(jié)精準(zhǔn)地表示出來，缺點(diǎn)是計算時間復(fù)雜度較高。

本文采用的三維人體點(diǎn)云模型密度大，精確度高，且分布較為均勻，所以采用改進(jìn)的三維柵格法對人體點(diǎn)云進(jìn)行精簡，即通過將點(diǎn)云數(shù)據(jù)分成很多微小的空間三維立方體的集合，然后在每個小立方體內(nèi)用所有點(diǎn)的重心來近似表示其他鄰域點(diǎn)，這種方法比用柵格中心來逼近的方法更準(zhǔn)確，更不容易失真[7]。

點(diǎn)云數(shù)據(jù)具有分布于整個三維空間的性質(zhì)，這對稀疏化的要求很高，構(gòu)造字典矩陣要考慮點(diǎn)云的空間拓?fù)潢P(guān)系。通過分析點(diǎn)云中散亂點(diǎn)的分布，發(fā)現(xiàn)模型中任意兩個相鄰離散點(diǎn)的數(shù)值差別不大，具有較強(qiáng)的相似度，這說明點(diǎn)云的冗余度較高，可壓縮空間較大。如果重新對點(diǎn)云中的數(shù)據(jù)進(jìn)行組合排列，相關(guān)性就會變得更強(qiáng)。本文采用分塊稀疏的方法，具體過程如下[8]：

步驟1點(diǎn)云降維。由于同一個點(diǎn)的3個坐標(biāo)的相關(guān)性很小，而同一維度上的坐標(biāo)值相關(guān)性較強(qiáng)，所以首先進(jìn)行降維操作，將點(diǎn)云x方向，y方向和z方向的數(shù)據(jù)分開，分別組成x序列，y序列和z序列的數(shù)據(jù)集合；

步驟2點(diǎn)云分塊。將降維后的數(shù)據(jù)按照某一坐標(biāo)軸的大小進(jìn)行排序，抽取點(diǎn)云中相同坐標(biāo)分量的數(shù)據(jù)作為整體進(jìn)行后續(xù)處理，若這些數(shù)據(jù)過長，截短為 個作為一個塊單元進(jìn)行處理；

步驟3點(diǎn)云變換。選取Haar小波矩陣作為字典矩陣，對分塊后的點(diǎn)云數(shù)據(jù)做稀疏變換。

3點(diǎn)云數(shù)據(jù)的壓縮和重建

要對初始信號進(jìn)行精確重構(gòu)，觀測矩陣需要滿足約束等距條件。研究人員已證實一些常用的矩陣直接符合約束等距條件的要求，本文使用高斯隨機(jī)矩陣作為觀測矩陣，使用如下函數(shù)生成

Φ=rand(M,N)

(4)

其中，M代表采樣次數(shù)；M小于信號的維數(shù)，說明采樣次數(shù)比傳統(tǒng)采樣次數(shù)少。最終生成的信號已經(jīng)攜帶了原始信號足夠的信息，也就完成了點(diǎn)云數(shù)據(jù)的采樣壓縮。

重建過程采用正交匹配追蹤算法，初始化冗余向量r0=y，索引列表Λ0=φ，迭代次數(shù)t=1，算法步驟描述如下[9]

步驟1找到索引λ1，使得

(5)

步驟2 令Λt=Λt-1∪{λt}，計算{Φλ:λ∈Λt}張成空間的正交投影Pt；

步驟3計算新的近似a和冗余r:at=Pty,rt=y-at；

步驟4t=t+1，若t

(6)

正交匹配追蹤算法[10]繼承了匹配追蹤類算法[11]的原子選擇思想，有效減少了迭代次數(shù)，降低了時間復(fù)雜度。按照上述算法依次恢復(fù)數(shù)據(jù)塊中的每一維數(shù)據(jù)，最后使用逆排序恢復(fù)初始的人體點(diǎn)云。

4實驗與結(jié)果分析

4.1點(diǎn)云精簡效果仿真

實驗使用的三維人體點(diǎn)云由117 486個點(diǎn)構(gòu)成，從三維人體點(diǎn)云原圖和精簡后的圖像可知，此種精簡算法處理后的模型不會影響人的視覺感受，人體外形輪廓基本與原型一致，沒有造成特征丟失和模糊。

圖2　點(diǎn)云精簡效果對比

通過改變柵格的粒度來對比精簡效果，得到表1所示，可看出隨著柵格長度的增大，簡化程度逐漸變大，點(diǎn)云點(diǎn)數(shù)從117 486降低到17 933，保存點(diǎn)云數(shù)據(jù)的文件大小從3.5 MB降低到544 kB，當(dāng)然隨著簡化程度的逐步增大，程序執(zhí)行的時間也越來越長。從表中可知三維柵格精簡算法能夠有效地減少點(diǎn)云中的數(shù)據(jù)量，達(dá)到簡化模型的作用。

表1　不同柵格長度下點(diǎn)云精簡效果對比

4.2點(diǎn)云重建效果仿真

本實驗綜合評估各項因素，對精簡后的點(diǎn)云進(jìn)行壓縮，根據(jù)分塊稀疏變換后的稀疏度，將壓縮比設(shè)定為0.6，重建效果對比如圖3所示，可看出重建的三維人體點(diǎn)云模型基本輪廓與原始模型保持一致，并沒有出現(xiàn)外形上的變化和失真，也能較好地保留點(diǎn)云細(xì)節(jié)之處的形態(tài)。為了定量地對重建效果進(jìn)行評估，計算重建點(diǎn)與對應(yīng)的原始點(diǎn)的歐式距離，然后將距離累加求均值，評估重建效果的公式為

(7)

其中，Xi表示原始人體點(diǎn)云中的數(shù)據(jù)點(diǎn)；Ri表示重建的點(diǎn)云中相同位置處對應(yīng)的數(shù)據(jù)點(diǎn)；N代表點(diǎn)云的數(shù)目,經(jīng)過計算求得誤差接近2.17×10-5，結(jié)果令人滿意。但從圖3中也可看出，重建的三維人體模型在一些曲面交匯處出現(xiàn)粘連現(xiàn)象，這是由于精簡后的點(diǎn)云密度降低，點(diǎn)間距變大，造成在一些交界輪廓處構(gòu)建的三角形頂點(diǎn)不在同一曲面上?？赏ㄟ^精簡時降低柵格的大小和使用其他改進(jìn)的重建算法來改善這一問題，這也是進(jìn)一步的研究方向。

圖3　人體點(diǎn)云重建效果對比

5結(jié)束語

壓縮感知理論的提出給信號采集處理領(lǐng)域帶來了新的發(fā)展方向，本文將此理論應(yīng)用于三維人體點(diǎn)云模型的壓縮和重建中，可有效降低模型數(shù)據(jù)的傳輸復(fù)雜度，減小計算機(jī)存儲的壓力，這將大幅拓展三維人體點(diǎn)云模型在體域網(wǎng)中的應(yīng)用范圍。

參考文獻(xiàn)

[1]王鵬杰,潘志庚,劉勇奎.基于點(diǎn)的三維模型壓縮技術(shù)研究進(jìn)展[J].計算機(jī)輔助設(shè)計與圖形學(xué)學(xué)報,2009,21(10):1359-1367.

[2]Donoho D.Compressed sensing[J].IEEE Transactions on Information Theory,2006,52(4):4036-4048.

[3]Candès E,Romberg J,Tao T.Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information[J].IEEE Transactions on an Information Theory,2006,52(2):489-509.

[5]焦李成,楊淑媛,劉芳,等.壓縮感知回顧與展望[J].電子學(xué)報,2011,39(7):1651-1658.

[6]李鵬飛,侯毅星,景軍鋒.三維人體的點(diǎn)云獲取與點(diǎn)云重建[J].西安工程大學(xué)學(xué)報,2014,28(1):72-76.

[7]朱煜.散亂點(diǎn)云數(shù)據(jù)簡化及三角網(wǎng)格重構(gòu)的研究[D].西安:西北大學(xué),2012.

[8]朱德海.點(diǎn)云庫PCL學(xué)習(xí)教程[M].北京:北京航空航天大學(xué)出版社,2012.

[9]張習(xí)民,余小清,萬旺根,等.壓縮感知點(diǎn)云數(shù)據(jù)壓縮[J].應(yīng)用科學(xué)學(xué)報,2014,32(5):458-462.

[10]方紅,楊海蓉.貪婪算法與壓縮感知理論[J].自動化學(xué)報,2011,37(12):1413-1421.

[11]Tropp J,Gilbert A.Signal recovery from random measurements via orthogonal matching pursuit[J].IEEE Transactions on Information Theory,2007,53(12):4655-4666.

[12]Mallat S,Zhang Z.Matching pursuit with time-frequency dictionaries[J].IEEE Transactions on Signal Processing,1993,41(12):3397-3415.

Compression and Recovery of 3D Body Point Clouds Based on Compressed Sensing

LIUJia

(SchoolofElectronicEngineering,XidianUniversity,Xi’an710071,China)

AbstractWith higher precision of the laser 3D scanning, the growing point cloud model data lead to the difficulty of data storage and transmission, thus limiting its application in the body network. In order to solve this problem, the compressed sensing technique is applied to the compression and reconstruction of human body point clouds model to perform data simplification processing by the improved three-dimensional grid method before compression. In light of the characteristics of human point cloud data, the block sparse transformation and orthogonal matching pursuit algorithm is applied to reconstruct the original model. The final experimental error is only , which confirms the validity and feasibility of the algorithm.

Keywordscompressed sensing; data simplification; block sparse; matching pursuit

收稿日期:2015- 11- 16

作者簡介:劉佳(1990-)，男，碩士研究生。研究方向：物聯(lián)網(wǎng)技術(shù)與Web開發(fā)。

doi:10.16180/j.cnki.issn1007-7820.2016.07.021

中圖分類號TP317.4

文獻(xiàn)標(biāo)識碼A

文章編號1007-7820(2016)07-072-03