基于徑向基函數(shù)的點云島嶼孔洞自動修復(fù)①

張立國 王 靜 金 梅 康 樂

(燕山大學(xué)河北省測試計量技術(shù)與儀器重點實驗室 秦皇島 066004)

?

基于徑向基函數(shù)的點云島嶼孔洞自動修復(fù)①

張立國②王 靜③金 梅 康 樂

(燕山大學(xué)河北省測試計量技術(shù)與儀器重點實驗室 秦皇島 066004)

研究了利用點云獲得的模型的孔洞修復(fù)，針對目前主要通過人工修復(fù)帶有島嶼面片的孔洞耗時較長的問題，提出了一種基于徑向基函數(shù)(RBF)自動修復(fù)島嶼孔洞的方法。該方法首先利用最小權(quán)重三角化法修復(fù)模型主體上的孔洞，其次計算模型主體上孔洞與島嶼面片的相關(guān)性，利用模型主體上孔洞和與其相關(guān)島嶼面片周圍點來計算徑向基函數(shù)，最后將粗修復(fù)后細(xì)分的點調(diào)整到徑向基函數(shù)描述的曲面上。實驗表明，與其他方法相比，該方法能快速、準(zhǔn)確地修復(fù)缺陷模型。

點云， 孔洞， 島嶼面片， 徑向基函數(shù)(RBF)， 最小權(quán)重三角化

0 引 言

隨著計算機立體視覺的發(fā)展，點云(用儀器測得的產(chǎn)品外觀表面的點數(shù)據(jù)集合)的處理技術(shù)在逆向工程、醫(yī)學(xué)圖像處理、文物模型保存中得以廣泛應(yīng)用。在現(xiàn)有的技術(shù)條件下，利用三維掃描儀或者計算機軟件得到的點云大多都伴隨著孔洞。由于物體表面的凹陷、數(shù)據(jù)獲取時的角度、數(shù)據(jù)的丟失等原因，得到物體的模型還帶有島嶼面片。要保證模型的完整性，點云孔洞修復(fù)是必不可少的一個環(huán)節(jié)。在模型使用之前，需要進行一系列的操作將孔洞修復(fù)。為此，本文提出了一種基于徑向基函數(shù)(radial basis function, RBF)的點云島嶼孔洞自動修復(fù)方法。

1 相關(guān)工作

根據(jù)模型表示方式的不同，使用的孔洞修復(fù)方法分為基于體積元素的孔洞修復(fù)和基于三角網(wǎng)格的孔洞修復(fù)。

基于體積元素表示的孔洞修復(fù)方法，需要用具有簡單、一致等特性的體積元素來表示模型。Davis等人使用體積離散的方法實現(xiàn)孔洞修復(fù)，這種方法能夠修復(fù)帶有島嶼面片的模型，但是會改變原有模型的拓?fù)鋄1]。Curless等人將空間雕刻和等值面提取引入孔洞修復(fù)[2]，Podolak等人利用最小切割算法確定空間中的各部分在模型的內(nèi)部或外部，實現(xiàn)孔洞的修復(fù)[3]。這兩種方法能夠修復(fù)復(fù)雜的模型，但是比較費時。

基于三角網(wǎng)格的孔洞修復(fù)方法需要將模型用具有存儲、渲染效率高的三角網(wǎng)格表示。與直接將孔洞周圍點連接實現(xiàn)孔洞修復(fù)不同，隱函數(shù)孔洞修復(fù)方法能夠修復(fù)復(fù)雜的孔洞。Kazhdan等人利用泊松方程重構(gòu)出沒有孔洞的模型[4]。Zhao等人提出利用波前推進法完成孔洞的粗修復(fù)，然后利用泊松方程將粗修復(fù)的點調(diào)整到曲面[5]。Centin等人利用泊松方程對孔洞進行逐層修復(fù)，每修復(fù)一層孔洞便更新一次泊松方程，直到孔洞修復(fù)完成[6]?；诓此煞匠痰姆椒ㄐ枰獪?zhǔn)確地計算模型中所包含點的法線，并且只能應(yīng)用在封閉的模型。Xie等人利用差分進化算法獲得缺陷處的拓?fù)浜托螤?，然后?yōu)化獲得的三角形，這個方法對參數(shù)依賴較大[7]。Carr等人利用徑向基函數(shù)(RBF)實現(xiàn)曲面重構(gòu)，并且可以得到一個光滑模型[8]。本研究在Carr提出的方法的基礎(chǔ)上實現(xiàn)了孔洞自動修復(fù)。

理想的孔洞修復(fù)方法能夠充分利用已有的信息，在給定的時間內(nèi)給出滿足要求的模型。本研究基于徑向基函數(shù)進行孔洞修復(fù)的主要思想是：點云是曲面上的采樣點，通過這些點來計算整個曲面方程，然后通過等值面提取，實現(xiàn)模型的存儲和可視化。本研究中，對于相互連接的總數(shù)小于40個三角形的面，便當(dāng)作島嶼面片來處理，提出了島嶼面片與模型主體上孔洞的相關(guān)性檢測方法。如果相關(guān)，則將模型主體上孔洞周圍的點與島嶼面片上的點添加到一個點集中，利用集合中的點來計算徑向基函數(shù)，將這個模型主體上的孔洞粗修復(fù)并且細(xì)分，新得到的三角形上的點調(diào)整到徑向基函數(shù)表示的曲面上，實現(xiàn)孔洞的自動修復(fù)。

2 徑向基函數(shù)的孔洞修復(fù)算法

基于徑向基函數(shù)方法的主要過程包括：孔洞檢測、孔洞粗修復(fù)、將粗修復(fù)的點調(diào)整到由徑向基函數(shù)所描述的曲面上。

2.1 孔洞檢測

進行孔洞修復(fù)，首先需要檢測孔洞。模型是由圖元組成的，通過圖元特征分析實現(xiàn)孔洞的檢測。在三角網(wǎng)格模型中，一個三角形在孔洞邊界上，它至少有一條邊沒有被其它三角形共用，檢查模型中所有的三角形，提取出全部沒有被共用的邊。那些可以首尾相接的邊,就組成了一個邊界孔洞。

對于孔洞，還有內(nèi)孔洞和外孔洞的區(qū)分。通過邊界點擬合一個平面，得到這個平面的方程。將所有的邊界點和與它相鄰的點投影到這個平面上，遍歷領(lǐng)域點是順時針還是逆時針來判定它是內(nèi)孔洞還是外孔洞[9]。集合S={pi=(xi, yi, zi)|i=1,2,…,k}構(gòu)成的孔洞邊界，利用最小二乘法估計得到這個邊界的擬合平面，即解下面的方程：

AG=0

(1)

ax+by+cz+d=0

(2)

將邊界上的點p1p2…pk和與邊界相鄰的點投影到這個擬合平面上，利用這些投影點來判斷這個邊界是內(nèi)邊界還是外邊界。具體判斷內(nèi)外孔洞的過程如下：假設(shè)p1p2…pk是散亂的點云的孔洞邊界，應(yīng)用最小二乘法計算該孔洞的擬合平面N，這個平面為該邊界的特征平面[10]。將p1p2…pk及其領(lǐng)域點投影到特征平面上，以特征面法矢方向為z軸正方向，規(guī)定沿投影邊界遍歷時領(lǐng)域點在它(邊界)的右側(cè)，以z軸正方向為觀察方向，如果投影邊界線的遍歷方向是逆時針，則此邊界線為內(nèi)邊界；反之邊界線為外邊界[10]。

2.2 孔洞粗修復(fù)和細(xì)分

普通的隱函數(shù)孔洞修復(fù)方法都是將粗修復(fù)的點進行調(diào)整，得到最終的模型。最終修復(fù)新增加點的個數(shù)與粗修復(fù)點的個數(shù)相等，并且新增加的點是通過粗修復(fù)點沿著某個方向移動得到的。新增點的相關(guān)點通過兩個步驟得到：第一步是利用三角化算法將這個外孔洞修復(fù)；第二步是將這些新得到的三角形細(xì)分。

三角化孔洞修復(fù)的算法比較多，選擇最小權(quán)重原則的三角化算法來修復(fù)孔洞。首先，計算出相鄰邊界邊之間的權(quán)重，具有最小權(quán)重的兩邊組成一個三角形；更新孔洞邊界和權(quán)重，再次將最小權(quán)重的兩個邊連接成三角形，直到孔洞被完全修復(fù)。

曲面細(xì)分能細(xì)化現(xiàn)有的模型而不改變現(xiàn)有模型的特性[11]，這里采用的曲面細(xì)分是將具有較長邊的三角形裂變成幾個三角形。這種細(xì)分方法速度非?？?，而且不改變原來的曲面形狀。細(xì)分的具體做法是首先計算孔洞周圍三角形邊長的平均值作為閾值，然后檢測孔洞內(nèi)新增三角形的三邊長，如果某邊長超過閾值，則將該邊從中點處分裂，曲面細(xì)分示意圖如下圖1示。圖1中，邊長bc大于這個閾值，需要將三角形abc分裂成三角形abd和三角形acd。

圖1 三角形細(xì)分

這一步后，就可以得到粗孔洞修復(fù)的點和面，將這些點調(diào)整到計算出來的曲面上，不改變點之間的連接關(guān)系，得到最后修復(fù)的模型。

2.3 求取徑向基函數(shù)

2.3.1 利用徑向基函數(shù)求曲面方程

隱函數(shù)重構(gòu)就是由點云來計算出曲面方程f，徑向基函數(shù)重構(gòu)就是隱函數(shù)重構(gòu)中的一種，利用孔洞周圍的點估計曲面函數(shù)，實現(xiàn)孔洞的修復(fù)。對于表面M′上的點di(i=1,…,n)，如果有一個函數(shù)f滿足

f(di)=0 (i=1,…,n)

(3)

這個方程有一個平凡解，為了消除這種解，必須添加附加約束條件，為曲面加入附加約束點。我們選取一些不在平面上的點來添加約束條件。這樣方程就轉(zhuǎn)變?yōu)?/p>

(4)

基于徑向基函數(shù)的隱式曲面可以表示為[4]

(5)

(6)

通過這些條件建立起一個線性方程組，通過高斯消元法求出方程中的各個系數(shù)。

2.3.2 插值約束點和附加約束點

為了能夠準(zhǔn)確地估計出曲面方程，輸入的插值約束點數(shù)量要足夠。這里輸入的插值約束點包括孔洞周圍的點，使用k領(lǐng)域搜索的方法來添加。查找孔洞周圍的點主要過程如下：

步驟1： 讀入提取得到的孔洞邊界點，將其加入到插值約束點的集合Q中。

步驟2： 以任意孔洞點為起點，查找其k鄰域,刪除與Q中元素重復(fù)的點, 剩余的點添加到點集Q中。

步驟3： 重復(fù)步驟2，直到遍歷完所有的孔洞點，得到所需的插值約束點的集合。

上面提到過，為了避免方程的平凡解，需要添加一些附加約束點。這些附加約束點是與這個曲面相關(guān)的一些點，選擇距離插值約束點0.5單位長度、法向量方向的點作為附加約束點，增加的附加約束點的數(shù)量與插值約束點的數(shù)量相同。雖然我們?nèi)〉命c是距離插值約束點0.5單位長度的一個點，但是這個點的函數(shù)值可以是1或者其它值，因為它們都是相等的，不會影響方程的解。

2.3.3 計算隱式曲面方程

通過插值約束點、附加約束點和正交條件，可以建立一個線性方程組。通過高斯消元法，求得方程中的參數(shù)，得到最終的曲面方程為

(7)

2.4 調(diào)整點到曲面上

這里沒有保留原本模型中的島嶼面片，只利用它們計算曲面方程。我們利用這些島嶼面片來計算曲面方程，然后把這些島嶼面片刪除掉。將一個距離曲面不遠(yuǎn)的點調(diào)整到平面上，是這個過程的最后一步。將孔洞修復(fù)新增點的相關(guān)點調(diào)整到平面上，使用Tasso Karkanis的梯度下降法[12]。這種方法能很快地逼近曲面，因為沿著負(fù)梯度方向的逼近最快，具體方程如下：

R1=R0-γ×▽F

(8)

3 修復(fù)島嶼孔洞的方法

本文方法與普通的徑向基函數(shù)孔洞修復(fù)方法不同的是，需要利用島嶼面片上的點來計算徑向基函數(shù)。 主要步驟如下：

步驟1： 檢測出模型中的島嶼面片。相互連接小于40個三角形的面，將它們從模型的主體上刪除。得到島嶼面片的個數(shù)n。

步驟2： 檢測模型主體上的孔洞，并且將它們粗修復(fù)和細(xì)分。得到模型主體上孔洞的個數(shù)m后，將每個孔洞邊界點和孔洞周圍點添加到對應(yīng)的集合Si(i=1,2,…,m)中。

步驟3： 模型主體上的孔洞與島嶼面片相關(guān)性檢測。對于模型主體上的孔洞，與每個島嶼面片進行相關(guān)性檢測。如果島嶼面片與孔洞相關(guān)，將這個島嶼面片上的點添加到主體孔洞所對應(yīng)的Si中。

步驟4： 利用點集合Si，計算出得到徑向基函數(shù)Fi(i=1,2,…,m)，將每個粗修復(fù)的三角形中的點，調(diào)整到它對應(yīng)的Fi上，不改變它們之間的連接關(guān)系。

假設(shè)一個由點t1t2t3…tn組成的面，計算它的擬合平面的形心O，即

(9)

判斷島嶼面片與模型主體上孔洞的相關(guān)性。通過下面兩個條件進行判斷：(1)設(shè)定一個閾值dmax，并且島嶼面片的形心O距離模型主體上孔洞的擬合平面的距離小于dmax；(2)O在這個內(nèi)孔洞擬合平面的投影點O′在邊界投影的內(nèi)部。滿足這兩個條件，這個島嶼面片和模型主體上孔洞是相關(guān)的。

如圖2所示，有兩個由三個三角形構(gòu)成的島嶼面片，它們的頂點分別包括defgh和ijklm。nopqrstuv是模型主體上一個孔洞在它擬合平面上的投影。defgh、ijklm的形心a、b到平面nopqrstuv的距離w1、w2都小于給定的dmax，并且它們的形心a、b在平面上的投影點a′、b′都在nopqrstuv的內(nèi)部，defgh和ijklm與nopqrstuv是相關(guān)的。將這兩個島嶼孔洞上的頂點加入到與這個模型主體孔洞相聯(lián)系的點集Si中。

圖2 具有島嶼面片的缺陷模型

判斷a′、b′都在nopqrstuv的內(nèi)部，可以通過內(nèi)外邊界的判定方法來完成。如圖2所示，要判斷a′在邊界投影nopqrstuv的內(nèi)部，可以假設(shè)a′是與邊界投影nopqrstuv相連的點，由a′判定由點nopqrstuv組成的邊界是內(nèi)邊界還是外邊界。如果判定nopqrstuv為外邊界，這個點就在邊界投影的內(nèi)部。反之則在邊界投影的外部。

通過點的集合Si(i=1,2,…,m)，計算m個徑向基函數(shù)，并且將粗修復(fù)三角形的頂點調(diào)整到對應(yīng)的曲面上，最后將所有的島嶼孔洞刪除，實現(xiàn)孔洞的修復(fù)。如圖2所示，利用上述方法可以知道它們是相關(guān)聯(lián)的孔洞，利用d、e、f、g、h、i、j、k、l、m這些頂點與模型主體上孔洞周圍的點來計算徑向基函數(shù)。

4 實驗及分析

本實驗使用的計算機硬件配置是AMD羿龍X4和8G內(nèi)存，軟件配置是OpenGL和VC++。圖3中所利用的模型，是一個石頭的模型。

圖3中的(a)、(b)是模型中的缺陷和孔洞檢測的結(jié)果。(c)為利用最小權(quán)重三角化的方法將內(nèi)孔洞填充后的效果，這種孔洞修復(fù)方法速度雖然很快，但是修復(fù)的模型不夠光滑。(d)中是利用一般的徑向基函數(shù)孔洞修復(fù)技術(shù)修復(fù)這個孔洞的效果，修復(fù)的模型較為光滑，誤差較最小權(quán)重三角化小。由于沒有利用島嶼面片中頂點坐標(biāo)來計算徑向基函數(shù)， 與本文中提出的方法相比較，誤差較大。由于梯度下降法本身的一些缺陷，可能最終修復(fù)的模型的三角形大小不一，具有局限性。

圖3 石頭的缺陷模型和修復(fù)結(jié)果

圖3中的(e)、(f)是利用島嶼孔洞修復(fù)方法，軟件運行中的截圖和最終結(jié)果的截圖。由于石頭的最大半徑是0.5m，所以我們設(shè)置相關(guān)孔洞中檢測的參數(shù)dmax為0.5m。逼近時γ取0.1，R1與R0的差值取0.01。圖3中(e)為相關(guān)點調(diào)整之后，但是沒有刪除島嶼面片的結(jié)果，新添加的紅色面與島嶼面片有相交的部分，修復(fù)后的形狀與實際更加接近；圖3中(f)是刪除島嶼面片后，最終修復(fù)后的模型。

在Z軸方向上取一個截面，獲得二維的曲線。如圖4為Z為0.3時的曲線圖。利用島嶼孔洞修復(fù)

圖4 Z=0.3時各方法的曲線

后的曲線與真實的曲線最為接近，修復(fù)后的模型光滑并且準(zhǔn)確。

從結(jié)果可以看出，本文的方法是有效的，修復(fù)以后的模型更加接近實際形狀，并且平滑地與模型主體相接。表1給出了在這個實驗中新增的點和面的信息。

表1 實驗中的數(shù)據(jù)

本文方法還應(yīng)用到實際項目中，下面介紹重構(gòu)燕大電氣工程學(xué)院石頭的項目。 圖5中的3張照片是從25張石頭照片中選出來的。利用Structure from Motion，可以獲得照片的位置信息和稀疏的點云，如圖6中的左邊照片所示。圖6中右邊照片是經(jīng)過加密以后獲得點云[13]。

圖5 重構(gòu)石頭所用的照片

圖6 圖片的位置信息與石頭的點云

本文的目的是獲得石頭的模型，如圖7中左邊圖片所示。圖7中右邊圖片是實際中帶有島嶼面片的孔洞，島嶼面片由于沒有與模型主體相連接，拓?fù)浣Y(jié)構(gòu)也不一致。對圖7中的孔洞依次經(jīng)過孔洞檢測、孔洞粗修復(fù)、新增加點的位置調(diào)整和刪除島嶼面

片后得到最終的結(jié)果，圖8中四張照片與這個過程相對應(yīng)。

圖7 刪除無效區(qū)域的模型與帶有島嶼面片的孔洞

圖8 修復(fù)石頭孔洞過程中的效果圖

5 結(jié) 論

本文提出的相關(guān)孔洞的檢測方法，設(shè)置合理的參數(shù)后，能夠檢測到相關(guān)的孔洞；將島嶼面片上的點應(yīng)用到徑向基函數(shù)的計算中，增加了修復(fù)中所用點的數(shù)量，能夠更好地用徑向基函數(shù)來表示孔洞處的曲面，修復(fù)的曲面誤差小。檢測模型主體上孔洞與島嶼面片的相關(guān)性，基于投影和距離，具有局限性。綜上所述，該方法對缺陷模型修復(fù)，新增加的面能與原始的面平滑過渡。添加島嶼面片上的頂點用于孔洞修復(fù)中徑向基函數(shù)的計算，增加了孔洞修復(fù)中曲面的復(fù)雜度，有利于提高修復(fù)后模型的精度?？梢詰?yīng)用到實際模型的孔洞修復(fù)中，并且修復(fù)的模型較為光滑、準(zhǔn)確。

[1] Davis J, Marschner S R, Garr M, et al. Filling holes in complex surfaces using volumetric diffusion. In: Proceedings of the IEEE International Symposium on 3D Data Processing Visualization & Transmission, Padova, Italy, 2002. 428-441

[2] Curless B, Levoy M. A volumetric method for building complex models from range images. In: Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques, New York, USA, 1996. 303-312

[3] Podolak J, Rusinkiewicz S. Atomic volumes for mesh completion. In: Proceedings of the Symposium on Geometry Processing, Vienna, Austria, 2005. 33-41

[4] Kazhdan M, Bolitho M, Hoppe H. Poisson surface reconstruction. In: Proceedings of the 4th Eurographics Symposium on Geometry Processing, Cagliari, Italy, 2006. 7-7

[5] Zhao W, Gao S, Lin H. A robust hole-filling algorithm for triangular mesh.VisualComputer, 2007, 23(12):22

[6] Centin M, Pezzotti N, Signoroni A. Poisson-driven seamless completion of triangular meshes.ComputerAidedGeometricDesign, 2015, 35: 42-55

[7] Xie W C, Zou X F. A triangulation-based hole patching method using differential evolution.Computer-AidedDesign, 2013, 45(12):1651-1664

[8] Carr J C, Beatson R K, Cherrie J B, et al. Reconstruction and representation of 3D objects with radial basis functions. In: Proceedings of the 28th Annual Conference on Computer Graphics and Interactive Techniques, New York, USA, 2001. 67-76

[9] 晏海平,吳祿慎,陳華偉. 基于徑向基函數(shù)的散亂點云孔洞修復(fù)算法. 計算機工程與設(shè)計, 2014,35(4)：1253-1257

[10] 顧園園. 散亂點云孔洞修補技術(shù)的研究與實現(xiàn):[碩士學(xué)位論文]. 蘇州大學(xué)計算機科學(xué)與技術(shù)學(xué)院, 2008. 33-36

[11] Deng C, Wang G. Interpolating triangular meshes by Loop subdivision scheme.ScieceChinaInformationSciences, 2010, 53(9):1765-1773

[12] Karkanis T, James Stewart A. Curvature-dependent triangulation of implicit surfaces.IEEEComputerGraphicsandApplications, 2001, 21(2):60-69

[13] Xiao J, Owens A, Torralba A. SUN3D: A database of big spaces reconstructed using SfM and object labels. In: Proceedings of the 2013 IEEE International Conference on Computer Vision, Sydney, Australia, 2013. 1625-1632

Automatic repair of point cloud holes with isolated surfaces based on radial basis function

Zhang Liguo, Wang Jing, Jin Mei, Kang Le

(Measurement Technology and Instrumentation Key lab of Hebei Province, Yanshan University, Qinhuangdao 066004)

The hole patching for the triangular meshes obtained by using point clouds under existing conditions was studied, and aiming at the serious time consumption problem of the manual repair method in common use at present, a method for automatic repair of the holes with isolated surfaces based on radial basis function (RBF) was proposed. This method uses the minimum weight triangulation method to fill the holes on the main body of the mesh; then calculates the correlation of the holes on the main body of the mesh and the isolated surfaces, and calculates the RBF by using the holes on the main body of the mesh and their related isolated surfaces’ around points; and finally, adjusts the vertexes obtained by subdivision to the curved surface expressed by RBF. The experimental results show that the proposed method can achieve fast, accurate repair of the meshes with holes compared to other approaches.

point cloud, hole, isolated surface, radial basis function (RBF), minimum weight triangulation

10.3772/j.issn.1002-0470.2016.02.007

①河北省自然科學(xué)基金(F2015203392)和秦皇島市科技計劃(201502A043)資助項目。

2015-10-29)

②男，1978年生，博士，副教授；研究方向：慣性導(dǎo)航，三維立體重構(gòu)及智能信號處理；E-mail: zlgtime@163.com

③通訊作者，E-mail: 307536367@qq.com