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

尹星翔　唐平　黃永慧　鐘靈

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

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

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

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

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

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

算法的基本思想：

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

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

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

論文中原始點(diǎn)云數(shù)據(jù)分布沒有規(guī)律性，缺少明顯的幾何拓?fù)潢P(guān)系。因此，需要建立點(diǎn)云的拓?fù)潢P(guān)系來(lái)提高精簡(jiǎn)點(diǎn)云的效率，這里采用包圍盒法來(lái)對(duì)點(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)云的總個(gè)數(shù)，其值根據(jù)點(diǎn)云的分布情況和密集程度選取，一般為24～32時(shí)可以達(dá)到精度要求，文章中由于點(diǎn)云數(shù)據(jù)較密集，n取32，則自適應(yīng)的包圍盒大小為：（1）

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

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

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

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

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

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

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

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

1.2.1 曲率的計(jì)算

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

（3）式中x_k，y_k，z_k鄰域內(nèi)數(shù)據(jù)點(diǎn)的坐標(biāo)值，將式（3）分別對(duì)系數(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，然后計(jì)算出整個(gè)點(diǎn)云數(shù)據(jù)所有點(diǎn)的曲率平均值：（7）

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

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

1.3 均勻精簡(jiǎn)

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

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

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

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

均勻精簡(jiǎn)具體算法流程如下：

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

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

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

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)云精簡(jiǎn)流程

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

2 實(shí)驗(yàn)結(jié)果

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

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

2.2 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

3 結(jié)語(yǔ)

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