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

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

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

0 引 言

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

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

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

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

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

圖1 算法整體流程

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

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

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

(1)

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

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

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

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

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

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

圖2 三維點(diǎn)云(機(jī)器貓胡須部分)

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

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

通過(guò)計(jì)算點(diǎn)云中各點(diǎn)的距離平均值來(lái)估算點(diǎn)云密度,點(diǎn)云的平均距離密度一般為

(2)

式中:d----點(diǎn)云中某一點(diǎn)與距離這點(diǎn)最近點(diǎn)的距離;

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

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

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

R1=S*E,

(3)

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

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

(4)

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

1.3 投影到平面

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

1)將鄰域點(diǎn)投影到切平面。計(jì)算P1、P2的中點(diǎn)P(Px,Py,Pz)的法向量n1=(nx,ny,nz),由P點(diǎn)的坐標(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)擴(kuò)展點(diǎn)

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

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

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

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

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

圖3 空間二面角示意圖

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

1.5 修補(bǔ)孔洞

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

基于最小角度法修補(bǔ)孔洞,該方法主要包括識(shí)別邊界、計(jì)算孔洞邊界夾角和修補(bǔ)孔洞三個(gè)步驟。如圖4所示。

圖4 孔洞修補(bǔ)示意圖

(8)

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

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

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

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

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

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

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

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

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

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

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

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

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

孔洞修補(bǔ)效果如圖7所示。

(a) 孔洞修補(bǔ)前

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

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

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

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

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

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

3 結(jié) 語(yǔ)

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