一種改進(jìn)的點(diǎn)云數(shù)據(jù)組合精簡算法

尹星翔　唐平　黃永慧　鐘靈

摘要：在逆向工程中，點(diǎn)云數(shù)據(jù)的精簡是一個重要的步驟，精簡的質(zhì)量直接關(guān)系到后續(xù)曲面重構(gòu)的效率。文章針對廣州灰塑曲率較大，凹凸面較多的特點(diǎn)，提出了一種基于曲率和均勻精簡的點(diǎn)云數(shù)據(jù)精簡方法：利用包圍盒法對散亂的點(diǎn)云數(shù)據(jù)進(jìn)行拓?fù)湟?guī)則排序，建立點(diǎn)的K-鄰域集，計算點(diǎn)云在某點(diǎn)處的曲率，在曲率較大處保留更多的特征點(diǎn)，但是曲率較小處會刪除較多的點(diǎn)云數(shù)據(jù)。文章在此基礎(chǔ)上再利用均勻網(wǎng)格的方法對初始精簡后的點(diǎn)云進(jìn)行重采樣處理，使得曲率較小處的特征點(diǎn)也能保留下來。

關(guān)鍵詞：逆向工程；灰塑；曲率；均勻精簡；點(diǎn)云數(shù)據(jù)；K-鄰域

隨著三維數(shù)據(jù)采集設(shè)備的日益發(fā)展和計算機(jī)技術(shù)的不斷成熟，文物保護(hù)工作者可以方便而精準(zhǔn)地獲取文物的三維物體表面數(shù)據(jù)點(diǎn)云信息。廣州灰塑作為非物質(zhì)文化遺產(chǎn)的一部分，更應(yīng)好好保護(hù)。在與廣州灰塑文化研究院合作的項目（廣州市花都區(qū)科技計劃項目）中發(fā)現(xiàn)灰塑點(diǎn)云數(shù)據(jù)的采集有如下的特點(diǎn)：灰塑作品種類繁多、體積較大，采集到的點(diǎn)云數(shù)據(jù)極為龐大，單個作品的點(diǎn)云數(shù)量級達(dá)到百萬以上。在三角剖分中，由于過密點(diǎn)云結(jié)構(gòu)的三角面片模型過于龐大，傳輸、顯示或處理都將消耗大量的時間和計算機(jī)資源；在曲面重構(gòu)時，過密的點(diǎn)云不但計算量大，而且可能影響其光順性及存儲。因此，如何在保持測量對象信息的情況下對測量點(diǎn)進(jìn)行最大程度地精簡，對于準(zhǔn)確、快速地點(diǎn)云預(yù)處理或其他的后續(xù)工作非常重要。

國內(nèi)外對點(diǎn)云精簡的研究，已經(jīng)有了很多研究成果。劉濤提出了一種基于包圍盒法的散亂點(diǎn)云數(shù)據(jù)的曲率精簡，該方法雖然對特征點(diǎn)保留得很好，但是對曲率較小的平滑區(qū)域剔除的點(diǎn)云數(shù)據(jù)太多，不利于模型后續(xù)的三維重建。程效軍等提出了基于自適應(yīng)八叉樹的點(diǎn)云數(shù)據(jù)壓縮方法，該方法能較好地保留點(diǎn)云數(shù)據(jù)的細(xì)節(jié)和輪廓特征，但是構(gòu)建八叉樹的過程較復(fù)雜，且一些經(jīng)驗閾值（如包圍盒的大?。┑脑O(shè)定也尚待改進(jìn)。

經(jīng)過對各種精簡算法的比較，結(jié)合灰塑的種類繁多的特點(diǎn)，即有的凹凸不平（平均曲率值較大），有的較光順（平均曲率較?。?，文章提出了一種基于曲率和均勻精簡的點(diǎn)云數(shù)據(jù)精簡方法，核心思想是基于包圍盒來建立K-鄰域，求出整個點(diǎn)云數(shù)據(jù)的平均曲率，根據(jù)曲率精簡原則選取特征點(diǎn)云，然后針對曲率較小處空白較多的問題采用均勻精簡方法。首先，基于曲率的精簡算法對處理曲率變化較大的點(diǎn)云數(shù)據(jù)優(yōu)勢明顯，其次，均勻精簡算法能保留曲率較小處的特征點(diǎn)，避免空白區(qū)域的產(chǎn)生，且算法原理簡單。

1 改進(jìn)的點(diǎn)云數(shù)據(jù)組合精簡算法

算法的基本思想：

（1）將原始點(diǎn)云利用包圍盒法進(jìn)行剖分，確立每個K-鄰域的中心點(diǎn)，并對所有中心點(diǎn)的K-鄰域完成搜索。計算鄰域內(nèi)的曲率并依照曲率精簡原則對點(diǎn)云進(jìn)行精簡，曲率較大處保留較多點(diǎn)云，曲率較小處點(diǎn)云精簡多一些。

（2）對基于曲率精簡中被剔除的點(diǎn)進(jìn)行重采樣，將點(diǎn)云數(shù)據(jù)劃分到柵格中，每個柵格中保留距離柵格中心距離最近的點(diǎn)，然后將保留下來的點(diǎn)加入第一步保留的點(diǎn)中，最終得到精簡后的點(diǎn)云。

1.1 基于包圍盒法建立K-鄰域

論文中原始點(diǎn)云數(shù)據(jù)分布沒有規(guī)律性，缺少明顯的幾何拓?fù)潢P(guān)系。因此，需要建立點(diǎn)云的拓?fù)潢P(guān)系來提高精簡點(diǎn)云的效率，這里采用包圍盒法來對點(diǎn)云進(jìn)行剖分并建立K-鄰域。包圍盒法建立K-鄰域的方法參照文獻(xiàn)，文章在此不作詳述。

點(diǎn)云數(shù)據(jù)在X，Y，Z方向上的最值X_min，X_max，Y_min，Y_max，Z_min，Z_max，設(shè)n為選取點(diǎn)云的總個數(shù)，其值根據(jù)點(diǎn)云的分布情況和密集程度選取，一般為24～32時可以達(dá)到精度要求，文章中由于點(diǎn)云數(shù)據(jù)較密集，n取32，則自適應(yīng)的包圍盒大小為：（1）

包圍盒個數(shù)：設(shè)X在軸方向上，包圍盒個數(shù)為Nx，則

N_x=ceil[（X_max-X_min）/S₀]

同理，沿著X軸和y軸方向的包圍盒個數(shù)為分別為

N_y=ceil[（Y_max-Y_min）/S₀]

N_z=ceil[（Z_max-Z_min）/S₀]

所以總的包圍盒個數(shù)為N_max=N_xN_yN_z

通過上述步驟取的32個點(diǎn)利用最小二乘法來擬合二次曲面，二次曲面方程如（2）式所示。（2）

1.2 基于曲率的點(diǎn)云數(shù)據(jù)精簡

1.2.1 曲率的計算

由（2）式建立的擬合方程，根據(jù)最小二乘原理求出擬合方程的系數(shù)，即要使下式取得最小值：（3）

（3）式中x_k，y_k，z_k鄰域內(nèi)數(shù)據(jù)點(diǎn)的坐標(biāo)值，將式（3）分別對系數(shù)求導(dǎo)，并使其等于0：（4）

根據(jù)（4）式求出擬合方程系數(shù)c_i，j-i。

求出系數(shù)之后，文章求出數(shù)據(jù)點(diǎn)的平均曲率，二次曲面函數(shù)的一階和二階微商表示如下：（5）則曲面的平均曲率可由曲面函數(shù)的微商表示為（6）

重復(fù)以上步驟，求出所有選取點(diǎn)在該鄰域內(nèi)的平均曲率P_i，然后計算出整個點(diǎn)云數(shù)據(jù)所有點(diǎn)的曲率平均值：（7）

1.2.2 曲率精簡準(zhǔn)則

由微分幾何可知，平均曲率是曲面彎曲程度的測量標(biāo)準(zhǔn)，因此可以用平均曲率來作為點(diǎn)云數(shù)據(jù)的精簡準(zhǔn)則。若該點(diǎn)的平均曲率P_i≤p，則說明該點(diǎn)在它的K-鄰域內(nèi)屬于分布較平坦的點(diǎn)，刪除該點(diǎn)；反之，則說明該點(diǎn)在它的K-鄰域內(nèi)屬于分布較尖銳的點(diǎn)，保留該點(diǎn)。重復(fù)該步驟，直到所有點(diǎn)的曲率比較完成這個過程。

1.3 均勻精簡

在1.2節(jié)基于曲率的點(diǎn)云精簡過程中，點(diǎn)云中位于較平坦區(qū)域的大部分?jǐn)?shù)據(jù)點(diǎn)會因為曲率較小而被精簡掉，這樣會導(dǎo)致點(diǎn)云數(shù)據(jù)平坦區(qū)域留有一片空白，丟失很多模型的幾何特征，如圖1所示。

這些空白區(qū)域會影響后續(xù)建模的質(zhì)量，導(dǎo)致模型不夠完整，特征點(diǎn)丟失較多。為了在基于曲率精簡的基礎(chǔ)上盡可能多地保留特征點(diǎn)，本文提出了一種基于曲率和均勻精簡的混合精簡算法，有效地解決了這個問題。

均勻精簡法的思想流程是把所有點(diǎn)云數(shù)據(jù)都封閉在一個大的長方體之中，然后根據(jù)精簡百分比將這個長方體劃分為m×n×l（m，n，l的值見下文）個邊長相等的小立方體，在每個小立方體中取離立方體中心點(diǎn)最近的點(diǎn)云數(shù)據(jù)作為特征點(diǎn)，如圖2所示。

這種方法單獨(dú)使用會存在一定的缺陷：在模型曲率較大處會損失很多幾何特征點(diǎn)。但是與基于曲率的初始精簡相結(jié)合，就能彌補(bǔ)平坦區(qū)域空白的產(chǎn)生，相互克服各自的缺點(diǎn)。

均勻精簡具體算法流程如下：

（1）將在初始精簡中被刪除的點(diǎn)讀入，求出這些點(diǎn)數(shù)據(jù)在X，Y，Z方向上的最值X_min，X_max，Y_min，Y_max，Z_min，Z_max。

（2）按照精簡百分比需要確定小立方體包圍盒邊長s，將大長方體在X，Y， Z方向上分別分割成m，n，l個小立方體，其中

m=（int）[（x_max-x_min）/s+1]

n=（int）[（y_max-y_min）/s+1] （8）

l=（int）[（z_max-z_min）/s+1]

（3）將點(diǎn)云中所有點(diǎn)按其三維坐標(biāo)劃分到不同的小立方體中，點(diǎn)P₀（x₀，y₀，z₀）所在的立方體空間位置索引為x_Index，y_Index，Z_Index，則

x_Index=（int）[（x₀-x_min）/s]

y_Index=（int）[（y₀-y_min）/s] （9）

z_Index=（int）[（z₀-z_min）/s]

（4）對每一個小立方體，求出其內(nèi)部所有點(diǎn)到其中心的空間距離并進(jìn)行排序，取距離中心最近的點(diǎn)并保留，其余的點(diǎn)將被作為精簡點(diǎn)。其中索引位置（x_Index，y_Index，z_Index），的立方體方格的中心位置（z，y，z）的計算公式為：

x=x_min+（0.5+x_Index）×s

y=y_min+（0.5+y_Index）×s

z=z_min+（0.5+z_Index）×s （10）

1.4 本文算法的點(diǎn)云精簡流程

綜上所述，點(diǎn)云數(shù)據(jù)總體的精簡步驟的流程圖如圖3所示。

2 實(shí)驗結(jié)果

2.1 實(shí)驗環(huán)境

如圖4所示為廣州市花都區(qū)灰塑文化研究院提供的灰塑作品一木棉花開（以下簡稱盤子）來進(jìn)行三維掃描，獲得實(shí)驗的數(shù)據(jù)來源。

2.2 實(shí)驗結(jié)果

在精簡的比例約為93%的前提下，用3種不同的精簡方法，對比所得實(shí)驗結(jié)果，驗證文章中方法的有效性。

試驗環(huán)境：Windows7 64位操作系統(tǒng)，CPU為酷睿i5-3210M 2.5GHz雙核，內(nèi)存為4GB，顯卡為GT645M，仿真環(huán)境Matlab2010b。

如圖5所示為盤子經(jīng)過三維掃描儀掃描得到原始點(diǎn)云數(shù)據(jù)，點(diǎn)云總數(shù)為428532；圖6是僅采用基于曲率算法精簡的結(jié)果；圖7是僅采用均勻精簡算法精簡的結(jié)果，其中立方體柵格邊長取s=30.0μm；圖8是文章中的組合算法精簡的結(jié)果。

表1所示為3種算法的結(jié)果對比。

從精簡結(jié)果可以看出，相比于曲率精簡，文章中的算法在平坦處保留了較多的點(diǎn)，避免了空白區(qū)域的產(chǎn)生，而且算法運(yùn)行速度也更快了；相比于均勻精簡，文章中的算法保留了更多的特征點(diǎn)。將兩種算法組合起來，既能夠保留點(diǎn)云數(shù)據(jù)的特征區(qū)域，又有效地降低了時間復(fù)雜度，整體精簡效果比較好。

3 結(jié)語

對于海量散亂點(diǎn)云數(shù)據(jù)的處理工作，點(diǎn)云數(shù)據(jù)的精簡是一個重要的環(huán)節(jié)。在與廣州灰塑文化研究院合作的項目中，文章分析了現(xiàn)有的散亂點(diǎn)云數(shù)據(jù)精簡算法，在此基礎(chǔ)上針對灰塑文化作品的曲率較大、凹凸面較多的特點(diǎn)，提出了一種基于曲率和均勻精簡的點(diǎn)云數(shù)據(jù)精簡方法。曲率精簡法在保留特征點(diǎn)方面有優(yōu)勢，但是在平坦區(qū)域會產(chǎn)生空白區(qū)域；均勻精簡法在保留特征點(diǎn)處存在很大缺陷。文章針對這兩種算法的優(yōu)點(diǎn)和缺點(diǎn)，進(jìn)行了算法整合，原理簡單明了，雖然相應(yīng)的處理速度變慢了，但是獲得的精簡效果是非常好的。