基于自適應(yīng)鄰域的非均勻點云數(shù)據(jù)封裝方法

郭 敏, 張文麗, 呂源治, 李貞蘭

(1.長春工業(yè)大學(xué) 計算機科學(xué)與工程學(xué)院, 吉林 長春 130102;2.中國科學(xué)院長春光學(xué)精密機械與物理研究所, 吉林 長春 130033;3.吉林大學(xué)白求恩第一醫(yī)院, 吉林 長春 130012)

0 引 言

隨著三維激光掃描技術(shù)的日益成熟,極大地推動了三維重建技術(shù)在文物保護、虛擬現(xiàn)實和逆向工程等領(lǐng)域的發(fā)展[1-3]。近年來,點云網(wǎng)格化作為三維重建技術(shù)的重要處理步驟,被眾多研究人員關(guān)注。

目前,常用的點云網(wǎng)格化方法主要有3類:基于隱式曲面的方法、基于投影的方法和基于區(qū)域生長的方法[4-7]。其中,基于區(qū)域生長算法由于思路簡單、時間復(fù)雜度低的優(yōu)點被廣泛應(yīng)用。區(qū)域生長算法從種子三角形[8]開始,根據(jù)一定的約束準(zhǔn)則獲取最優(yōu)點[9],實現(xiàn)網(wǎng)格生長。許多學(xué)者針對如何選取網(wǎng)格生長范圍進行了研究,Bernardinit F等[10]提出BPA方法,通過人為定義滾球半徑獲取網(wǎng)格生長范圍,在點云稀疏區(qū)域會出現(xiàn)孔洞。邱春麗等[9]提出基于動態(tài)球搜索鄰域的算法,能夠構(gòu)建平滑曲面,但是在孔洞周圍會生成錯誤三角形。付永健等[11]提出根據(jù)內(nèi)在屬性因子和擴展邊關(guān)系自適應(yīng)確定網(wǎng)格生長范圍的方法,對于含有孔洞的點云,網(wǎng)格曲面質(zhì)量會降低。實際應(yīng)用中,在掃描形狀較為復(fù)雜的模型時,由于存在視線死角或模型表面粘貼標(biāo)識點,導(dǎo)致獲得的點云數(shù)據(jù)存在孔洞,且點云分布不絕對均勻[12]。張麗艷等[13]、李松等[14]基于最小角度法修補孔洞,其過程主要分為識別邊界、計算孔洞邊界夾角和修補孔洞三個步驟。傳統(tǒng)的區(qū)域生長方法在處理密度非均勻點云時,難以控制網(wǎng)格生長范圍,易出現(xiàn)孔洞和網(wǎng)格錯亂現(xiàn)象,降低重建精度。

針對上述問題,提出一種基于自適應(yīng)鄰域的非均勻點云數(shù)據(jù)封裝方法,該算法通過點云密度自適應(yīng)選擇合適的空間搜索球半徑,控制網(wǎng)格生長范圍,優(yōu)化了最優(yōu)擴展點的選取,從而減少網(wǎng)格孔洞數(shù)量,避免了網(wǎng)格錯亂現(xiàn)象。

1 基于自適應(yīng)鄰域的點云網(wǎng)格化算法

基于自適應(yīng)鄰域的非均勻點云數(shù)據(jù)封裝算法整體流程如圖1所示。

圖1 算法整體流程

首先構(gòu)建種子三角形;其次提取一條邊界邊,并自適應(yīng)搜索邊界邊頂點的鄰域;然后將鄰域投影到二維平面,計算出投影坐標(biāo);再根據(jù)約束準(zhǔn)則找出最優(yōu)擴展點,與邊界邊形成新的三角形,重復(fù)之前的步驟,直到邊界邊列表為空;最后修補網(wǎng)格曲面中的孔洞。

網(wǎng)格質(zhì)量的評價指標(biāo)通常為三角形的正則度,即三角形接近正三角形的程度。文中通過三角形內(nèi)角的余弦和進行計算,

g=2*(cosα+cosβ+cosλ-1),

(1)

式中:α,β,λ----三角形的內(nèi)角;

g----三角形正則度,0

1.1 構(gòu)建種子三角形

為了避免種子三角形穿過網(wǎng)格內(nèi)部,首先在網(wǎng)格模型的平坦區(qū)域選擇一點Q1作為種子點,然后找出距離Q1最近的點Q2,再找出與Q1、Q2距離和最小的點Q3,則Q1、Q2、Q3就是種子三角形的三個頂點。Q1作為種子點要求所有鄰域點的法向量與Q1法向量的夾角均小于90°。

1.2 基于點云密度的自適應(yīng)鄰域選擇

采樣后的三維點云數(shù)據(jù)如圖2所示。

圖2 三維點云(機器貓胡須部分)

從圖2可以看出,在細節(jié)特征豐富的地方點云分布相對密集,其它地方的點云分布相對稀疏。

由于點云密度不均勻,當(dāng)網(wǎng)格生長范圍限定不適當(dāng)時,容易出現(xiàn)孔洞,而且會影響后續(xù)的最優(yōu)點選擇,導(dǎo)致網(wǎng)格出現(xiàn)交疊。因此,文中根據(jù)點云密度設(shè)置自適應(yīng)的搜索球,以優(yōu)化網(wǎng)格生長范圍。

通過計算點云中各點的距離平均值來估算點云密度,點云的平均距離密度一般為

(2)

式中:d----點云中某一點與距離這點最近點的距離;

N----點云中數(shù)量。

平均距離E越大,表示點云分布越稀疏,平均距離E越小,點云分布越密集。

設(shè)PC為點云集合,Pi(Pi∈PC|i=1,2,…,N)為目標(biāo)點,作球心為Pi,半徑為r的空間搜索球。根據(jù)點云平均距離密度E確定空間搜索球的初始半徑為

R1=S*E,

(3)

式中:S----倍數(shù)。

由目標(biāo)點Pi的初始空間搜索球可以確定Pi的鄰域點Qj(j=1,2,…,M),定義Pi的鄰域平均距離為

(4)

文中算法的r值僅與S相關(guān),參數(shù)只有S一個,自動化程度較高。由于S的大小影響r的大小,如果S過小,此時模型重建不完整;如果S過大,此時程序運行時間增大。文中為了確定合適的參數(shù)S,對點云進行多次曲面重建實驗,最終根據(jù)三角形的正則度、數(shù)量以及網(wǎng)格孔洞數(shù)量選取曲面質(zhì)量最優(yōu)時的S值為3.5。

1.3 投影到平面

將邊界邊頂點P1、P2的鄰域Qj(j=1,2,…,M)投影到平面時,可分為兩個步驟:

1)將鄰域點投影到切平面。計算P1、P2的中點P(Px,Py,Pz)的法向量n1=(nx,ny,nz),由P點的坐標(biāo)和法向量可以確定切平面方程為

nx*(x-Px)+ny*(y-Py)+nz*(z-Pz)=0,

(5)

(6)

式中:θ----局部平面法向量n1和xoy面法向量n2的夾角;

k----向量n1和n2的叉積。

I是3×3的單位矩陣,若

則

(7)

1.4 選取最優(yōu)擴展點

選取最優(yōu)擴展點就是在擴展邊頂點的鄰域中,利用約束準(zhǔn)則選取一個最優(yōu)的鄰域點,與擴展邊形成新的三角網(wǎng)格。

1.4.1 平面約束準(zhǔn)則

三角形空外接圓準(zhǔn)則、三角形內(nèi)角約束準(zhǔn)則和小三角形準(zhǔn)則。

1.4.2 空間二面角準(zhǔn)則

空間二面角示意圖如圖3所示。

圖3 空間二面角示意圖

△ABC是已生成三角形,AB是生長邊,D是擴展點,計算△ABC和△ABD的夾角,即計算它們法向量nABC和nABD的夾角,夾角越接近180°,相鄰三角形的過渡越平穩(wěn)。此外,二面角過小時,三角形之間可能會形成交疊,因此需要設(shè)置一個最小閾值βmin,文中閾值βmin設(shè)置為π/3。

1.5 修補孔洞

由于重建曲面存在部分孔洞,為了獲得完整的模型,需要對孔洞區(qū)域進行修補。

基于最小角度法修補孔洞,該方法主要包括識別邊界、計算孔洞邊界夾角和修補孔洞三個步驟。如圖4所示。

圖4 孔洞修補示意圖

(8)

當(dāng)f≥0時,孔洞多邊形是逆時針方向,否則是順時針方向,進而求出夾角大小。在計算孔洞邊界夾角后,通過孔洞邊界長度、邊界點的距離和孔洞邊界夾角計算新增點Enew,并去除邊長和內(nèi)角不滿足閾值的三角形。

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

1)為驗證文中算法,以機器貓石膏像點云為實驗數(shù)據(jù),該點云由中國科學(xué)院長春光學(xué)精密機械與物理研究所自主研發(fā)的SVision751B型三維激光掃描儀掃描得到。

2)為驗證文中算法的有效性,將其與傳統(tǒng)區(qū)域生長網(wǎng)格化算法的結(jié)果進行對比分析。

兩種方法的對比結(jié)果如圖5所示。

(a) 傳統(tǒng)區(qū)域生長網(wǎng)格化算法

圖5(a)是傳統(tǒng)區(qū)域生長網(wǎng)格化算法結(jié)果,存在局部區(qū)域網(wǎng)格錯亂現(xiàn)象,圖5(b)是文中算法結(jié)果,在圖(a)的相同位置,沒有網(wǎng)格錯亂現(xiàn)象,且三角形形態(tài)良好,能夠準(zhǔn)確地表達眼睛、鼻子等細節(jié)特征信息。

文中采用正則度對網(wǎng)格質(zhì)量進行評價,兩種結(jié)果的正則度直方圖反映了正則度大小與三角形個數(shù)的關(guān)系,如圖6所示。

(a) 傳統(tǒng)區(qū)域生長網(wǎng)格化算法

通過比較圖6中的兩幅圖可知,兩種方法的正則度大小及所占三角形數(shù)量基本相同,大多數(shù)正則度在0.8～1.0,極少數(shù)小于0.5,狹長三角形數(shù)量不多。網(wǎng)格化結(jié)果數(shù)據(jù)見表1。

表1 網(wǎng)格化結(jié)果數(shù)據(jù)

由表1可知,與傳統(tǒng)區(qū)域生長網(wǎng)格化算法相比,文中算法更大程度地利用了點云數(shù)據(jù),同時三角形個數(shù)增加0.213 5%,相應(yīng)的孔洞數(shù)量減少20.114 9%。

綜上,文中算法略優(yōu)于傳統(tǒng)區(qū)域生長網(wǎng)格化算法。

孔洞修補效果如圖7所示。

(a) 孔洞修補前

圖7(a)是孔洞修補前的網(wǎng)格曲面,含有若干由于模型表面粘貼標(biāo)識點而形成的孔洞,圖(b)是孔洞修補后結(jié)果,網(wǎng)格孔洞基本修補完成。

孔洞修補結(jié)果數(shù)據(jù)見表2。

表2 孔洞修補結(jié)果數(shù)據(jù)

結(jié)合表2可知,修補過程中三角形數(shù)目增加3.551 3%,網(wǎng)格頂點個數(shù)增加2.599 3%,且修補前點云平均密度為1.442 6,修補后孔洞區(qū)域網(wǎng)格頂點平均密度為1.478 3,網(wǎng)格密度接近周圍網(wǎng)格。修補孔洞產(chǎn)生的三角形的正則度分布情況如圖8所示。

圖8 孔洞修補網(wǎng)格正則度直方圖

由圖8可知,正則度在0.8～1.0的占比49.839 5%,0.5～1.0的占比86.416 7%,狹長三角形較少。

3 結(jié) 語

針對密度非均勻點云重建時難以控制網(wǎng)格生長范圍問題,文中對基于自適應(yīng)鄰域的非均勻點云數(shù)據(jù)封裝方法進行了研究,在保證正則度和三角形數(shù)量的前提下,減少了狹長三角形和網(wǎng)格孔洞的數(shù)量,有效解決了局部網(wǎng)格錯亂問題。實驗結(jié)果表明,文中算法可以有效、準(zhǔn)確地構(gòu)建出質(zhì)量較好的三角網(wǎng)格模型,具有一定的實用性。