一種改進的點云數據組合精簡算法

尹星翔　唐平　黃永慧　鐘靈

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

關鍵詞：逆向工程；灰塑；曲率；均勻精簡；點云數據；K-鄰域

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

國內外對點云精簡的研究，已經有了很多研究成果。劉濤提出了一種基于包圍盒法的散亂點云數據的曲率精簡，該方法雖然對特征點保留得很好，但是對曲率較小的平滑區域剔除的點云數據太多，不利于模型后續的三維重建。程效軍等提出了基于自適應八叉樹的點云數據壓縮方法，該方法能較好地保留點云數據的細節和輪廓特征，但是構建八叉樹的過程較復雜，且一些經驗閾值（如包圍盒的大小）的設定也尚待改進。

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

1 改進的點云數據組合精簡算法

算法的基本思想：

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

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

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

論文中原始點云數據分布沒有規律性，缺少明顯的幾何拓撲關系。因此，需要建立點云的拓撲關系來提高精簡點云的效率，這里采用包圍盒法來對點云進行剖分并建立K-鄰域。包圍盒法建立K-鄰域的方法參照文獻，文章在此不作詳述。

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

包圍盒個數：設X在軸方向上，包圍盒個數為Nx，則

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

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

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

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

所以總的包圍盒個數為N_max=N_xN_yN_z

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

1.2 基于曲率的點云數據精簡

1.2.1 曲率的計算

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

（3）式中x_k，y_k，z_k鄰域內數據點的坐標值，將式（3）分別對系數求導，并使其等于0：（4）

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

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

重復以上步驟，求出所有選取點在該鄰域內的平均曲率P_i，然后計算出整個點云數據所有點的曲率平均值：（7）

1.2.2 曲率精簡準則

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

1.3 均勻精簡

在1.2節基于曲率的點云精簡過程中，點云中位于較平坦區域的大部分數據點會因為曲率較小而被精簡掉，這樣會導致點云數據平坦區域留有一片空白，丟失很多模型的幾何特征，如圖1所示。

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

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

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

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

（1）將在初始精簡中被刪除的點讀入，求出這些點數據在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）將點云中所有點按其三維坐標劃分到不同的小立方體中，點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）對每一個小立方體，求出其內部所有點到其中心的空間距離并進行排序，取距離中心最近的點并保留，其余的點將被作為精簡點。其中索引位置（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 本文算法的點云精簡流程

綜上所述，點云數據總體的精簡步驟的流程圖如圖3所示。

2 實驗結果

2.1 實驗環境

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

2.2 實驗結果

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

試驗環境：Windows7 64位操作系統，CPU為酷睿i5-3210M 2.5GHz雙核，內存為4GB，顯卡為GT645M，仿真環境Matlab2010b。

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

表1所示為3種算法的結果對比。

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

3 結語

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