陳思琦，劉 麗，陳秀秀，張 龍，王天時(shí)

山東師范大學(xué) 信息科學(xué)與工程學(xué)院，濟(jì)南 250014

1 引言

隨著信息技術(shù)的不斷發(fā)展和人們生活水平的提高，人們對(duì)色彩、視覺享受的要求越來越高，單一的圖像、文本、音頻等已經(jīng)遠(yuǎn)不能滿足人們的需求。因此，三維模型應(yīng)運(yùn)而生，憑借其豐富的形狀信息和逼真的視覺效果，廣泛應(yīng)用于三維游戲、虛擬現(xiàn)實(shí)環(huán)境、計(jì)算機(jī)輔助設(shè)計(jì)、考古學(xué)[1-6]等多個(gè)領(lǐng)域。

在眾多三維模型中，至少有10%～20%的三維模型存在殘缺或信息不完整，其中包括年代久遠(yuǎn)的出土文物的自然破損、外力造成的人為缺損和掃描時(shí)因遮擋或其他原因造成的三維模型信息不完整等。信息缺失的三維模型無法表達(dá)完整的模型信息，對(duì)殘缺三維模型特征的提取也會(huì)受到殘缺區(qū)域的影響。因此，在三維模型檢索時(shí)，殘缺區(qū)域較大的殘缺三維模型也難以得到理想的檢索結(jié)果。

在眾多三維模型檢索方法中，主要有兩大類方法：基于視圖的方法和基于投影的方法[7]。Ansary等[8]提出自適應(yīng)視圖聚類算法（Adaptive Views Clustering，AVC），利用兩個(gè)單位正二十面體得到三維模型的320張投影，選取代表性圖像，引入一種概率統(tǒng)計(jì)方法來計(jì)算兩個(gè)三維模型的相似距離；Papadakis等[9]提出全景視圖三維模型檢索算法，將三維模型分別進(jìn)行復(fù)數(shù)主成分分析（Complex Principal Component Analysis，CPCA）、法向主成分分析（Normal Principal Component Analysis，NPCA）后，放入圓柱體內(nèi)沿三個(gè)坐標(biāo)軸進(jìn)行放射投影，得到灰度圖后，分別提取Fourier 特征和離散小波變換（Discrete Wavelet Transformation，DWT）特征，并以此來計(jì)算兩個(gè)三維模型的相似距離。此類方法通過投影獲得三維模型的二維信息，但是沒有充分學(xué)習(xí)視圖間關(guān)系，檢索精確度有待進(jìn)一步提高。Gao等[10]提出一種與相機(jī)位置無關(guān)的三維模型檢索算法，將視圖集聚類后，引入高斯模型來進(jìn)行模型間匹配。此類方法通過學(xué)習(xí)視圖間關(guān)系，提高了檢索精確度，但是其特征描述符表達(dá)能力不足，限制了精確度的進(jìn)一步提升。Gao 等[11]將詞袋模型引入三維模型檢索，提高了檢索效率；Zhao等[12]利用多特征融合的方式，對(duì)三維模型進(jìn)行檢索；Nie等[13]將稀疏編碼引入三維模型檢索，取得了較好的檢索精確度。此類方法直接以三維模型的多視圖作為算法輸入，復(fù)雜性相對(duì)較低，檢索結(jié)果優(yōu)異，但是沒有充分考慮視圖間關(guān)聯(lián)。

雖然三維模型檢索方法較多，各自有其優(yōu)點(diǎn)，但這些方法都難以有效實(shí)現(xiàn)對(duì)殘缺模型的檢索。因此，本文以殘缺三維模型為研究對(duì)象，通過填充殘缺三維模型建立其與對(duì)應(yīng)的完整三維模型之間的形狀關(guān)聯(lián)，從而實(shí)現(xiàn)殘缺三維模型的有效檢索。

2 基于孔洞填充的殘缺三維模型檢索

若想將殘缺三維模型填充成為完整三維模型，首先要確定殘缺三維模型的孔洞邊界，使用填充算法進(jìn)行填充，但在填充時(shí)需要注意的是，填充后孔洞區(qū)域應(yīng)與模型其他區(qū)域平滑自然地銜接；填充完成后，對(duì)于填充三維模型的每一點(diǎn)，取與該點(diǎn)距離最近的n個(gè)點(diǎn)構(gòu)建矩陣，通過求解矩陣獲得該點(diǎn)的曲率值，作為填充三維模型的特征；最后，對(duì)填充三維模型使用聚類算法進(jìn)行聚類，并計(jì)算填充三維模型與不同三維模型之間的曲率差值，從而獲得兩個(gè)三維模型的相似距離。

2.1 高精度的孔洞填充

孔洞填充屬于無中生有的過程，填充數(shù)據(jù)與原數(shù)據(jù)之間存在一定誤差，因此，需要不斷優(yōu)化填充后的數(shù)據(jù)，以達(dá)到填充數(shù)據(jù)與原數(shù)據(jù)誤差盡可能小的目的。

三角網(wǎng)格模型由一系列三角面片組成，通常情況下，每條邊連接兩個(gè)三角面片。假設(shè)三角網(wǎng)格模型的曲面為M，對(duì)M上所有的邊進(jìn)行檢測，若M上某條邊只連接了一個(gè)三角面片，則這條邊即為孔洞區(qū)域的邊界邊。所有只連接一個(gè)三角面片的邊最后連接包圍的區(qū)域即為孔洞區(qū)域，這些邊即為孔洞區(qū)域的邊界。

確定邊界后，采用最小角度法對(duì)網(wǎng)格進(jìn)行初始化填充，首先計(jì)算邊界邊長度的平均值ˉ；再計(jì)算每條邊界邊與其相鄰邊的夾角大小，并找出具有最小夾角的邊界點(diǎn)，計(jì)算它的兩個(gè)相鄰邊界點(diǎn)的距離d，若d ＜2×，則增加一個(gè)三角形，反之則增加兩個(gè)三角形；最后，更新邊界點(diǎn)的信息，判斷孔洞是否填充完成。

使用最小角度法填充的網(wǎng)格效果并不是很好，最小二乘網(wǎng)格法可以提供視覺上的平滑性，使填充后的模型更加自然。

其中，di為頂點(diǎn)vi的1 環(huán)鄰域頂點(diǎn)數(shù)。當(dāng)式（1）成立時(shí)，頂點(diǎn)vi則位于其1環(huán)鄰域的中心處。

由于vi位于三維空間中，該方法可以用矩陣表示，如下所示：

其中，x、y和z為包含n個(gè)頂點(diǎn)n×1 維向量，L為n×n的Laplace矩陣，其具體形式為：

在式（3）中，矩陣L的秩為n-k,n為網(wǎng)格頂點(diǎn)數(shù)目，k為網(wǎng)格連通區(qū)域的個(gè)數(shù)。為使方程有解，需加入個(gè)控制頂點(diǎn)坐標(biāo)vs作為方程的邊界條件，本文將孔洞區(qū)域的邊界頂點(diǎn)作為控制頂點(diǎn)，則線性方程的表達(dá)形式轉(zhuǎn)換為：

其中，

當(dāng)矩陣A滿秩時(shí)，使下式最小化即可求得x：

在式（8）中，等式右邊第一部分是使得每個(gè)頂點(diǎn)位于其1環(huán)鄰域頂點(diǎn)的中心，第二部分是為了使控制頂點(diǎn)的位置滿足要求。

當(dāng)矩陣A滿秩時(shí)，該方程的唯一解為ATb，因此，當(dāng)ATAx=ATb時(shí) ‖Ax-b‖最小，對(duì)系數(shù)矩陣進(jìn)行因式分解，可以得到ATA=RTR。其中R為上三角矩陣，則通過求解三角線性方程RTX=ATb和Rx=X即可求得x，同理可求得y和z。

徑向基函數(shù)（Radial Basis Function，RBF）網(wǎng)絡(luò)能夠解決空間散亂數(shù)據(jù)點(diǎn)的平滑插值問題，使填充模型更加接近于原始模型。其輸入由構(gòu)成，隱層單元由輸入x和已知坐標(biāo)點(diǎn)坐標(biāo)計(jì)算得到的基函數(shù)構(gòu)成，輸出層由一個(gè)或多個(gè)線性單元組成，表示為多個(gè)基函數(shù)的線性組合：

其中，λi表示RBF的組合系數(shù)，通過已知的坐標(biāo)點(diǎn)坐標(biāo)求得最優(yōu)解。

為得到三維網(wǎng)格模型，采用牛頓迭代法將網(wǎng)格頂點(diǎn)映射到隱式曲面上。若取，則式（10）變?yōu)椋?/p>

算法具體過程如下所示。

算法1 高精度的孔洞填充

步驟1 確定孔洞邊界，若三維網(wǎng)格模型的邊只連接一個(gè)三角面片，則該邊為孔洞邊界邊。

步驟2 采用最小角度法填充網(wǎng)格模型。計(jì)算邊界邊長度的平均值ˉ，若具有最小夾角的邊界點(diǎn)的兩條邊界邊的距離d ＜2×，則增加一個(gè)三角形，反之則增加兩個(gè)三角形。

步驟3 采用最小二乘網(wǎng)格法優(yōu)化已生成的頂點(diǎn)位置。

步驟4 采用RBF 網(wǎng)絡(luò)和牛頓迭代法優(yōu)化模型，獲得填充后的三維網(wǎng)格模型。

2.2 填充三維模型檢索

2.2.1 填充三維模型曲率計(jì)算

在提取三維點(diǎn)云模型的幾何信息時(shí)，主要通過直接計(jì)算法和最小二乘擬合算法獲取點(diǎn)云的局部n次曲面。點(diǎn)云的局部曲面有兩種表示方法：一是基于法向距離的局部曲面表示；二是基于歐氏距離的局部曲面表示?；诳锥刺畛涞臍埲比S模型檢索方法利用點(diǎn)云模型的坐標(biāo)信息，采用基于歐氏距離的局部曲面表示法獲取點(diǎn)云模型的曲率。曲率是描述三維模型形狀的重要屬性[14]，準(zhǔn)確的坐標(biāo)信息提高了對(duì)模型描述的精確度，進(jìn)而提高了三維模型檢索時(shí)的準(zhǔn)確率[15]。

2.2.2 填充三維模型聚類

基于孔洞填充的殘缺三維模型檢索算法將三維模型看作由幾個(gè)點(diǎn)集組合而成的整體，每個(gè)點(diǎn)集內(nèi)的點(diǎn)都具有較高的相似度，點(diǎn)集間相似度較低。因此，在三維模型檢索時(shí)，可以采用類間匹配的方法，計(jì)算兩個(gè)三維模型的類間曲率距離，從而使具有最高相似度的兩個(gè)類相互匹配。對(duì)于填充三維模型M1和其他不同的三維模型M2,M1和M2應(yīng)該具有相同的聚類數(shù)目，才能保證M1和M2中的類可以一一匹配。

經(jīng)典聚類算法中，K-means聚類算法以其簡單快速的優(yōu)勢得到廣泛應(yīng)用，但由于K-means聚類算法對(duì)初始聚類中心的選擇是隨機(jī)的，當(dāng)兩個(gè)聚類中心相聚比較近時(shí)，最終的聚類結(jié)果可能不太理想。因此，本文使用K-means++聚類算法，在K-means 聚類算法的基礎(chǔ)上，首先隨機(jī)選擇一個(gè)點(diǎn)作為初始聚類中心；然后計(jì)算其他點(diǎn)到該聚類中心的歐氏距離，并計(jì)算其他各點(diǎn)適合作為聚類中心的概率，選擇具有最大概率的點(diǎn)作為第二個(gè)聚類中心；重復(fù)此過程，直到選出K個(gè)聚類中心為止；最后，以聚類中心對(duì)每個(gè)數(shù)據(jù)點(diǎn)的影響為標(biāo)準(zhǔn)對(duì)三維模型進(jìn)行聚類。K-means++聚類算法選取的初始聚類中心進(jìn)行了優(yōu)化，使初始聚類中心不是完全隨機(jī)選取，而是選擇距離已有聚類中心較遠(yuǎn)的點(diǎn)作為下一個(gè)聚類中心。該算法的時(shí)間復(fù)雜度為O( )n，其中n是樣本數(shù)量，算法執(zhí)行效率比較高。

具體聚類過程如下：

然后，計(jì)算每個(gè)點(diǎn)成為下個(gè)聚類中心的概率，計(jì)算公式如下：

重復(fù)這一過程，直到選出K個(gè)初始聚類中心為止。

在一次聚類完成后，需要重新計(jì)算聚類中心的坐標(biāo)，計(jì)算公式如下：

最后，計(jì)算新聚類中心對(duì)其他各點(diǎn)的影響值，并重新進(jìn)行聚類，重復(fù)這一過程，直到聚類結(jié)果不發(fā)生改變?yōu)橹?。聚類過程結(jié)束后，最終結(jié)果即為具有相同聚類數(shù)目的三維模型M1和M2。

2.2.3 填充三維模型匹配

聚類過程結(jié)束后，三維模型M1和M2分別由相同聚類數(shù)目的類簇組成，類簇內(nèi)的點(diǎn)具有較高的相似度，類簇間的點(diǎn)具有較低的相似度，因此M1的類簇和M2的類簇也存在相似度高低的問題。由此，計(jì)算三維模型M1和M2的相似度可以轉(zhuǎn)化為計(jì)算M1的類簇和M2的類簇的相似度，并對(duì)M2中的每一類設(shè)置標(biāo)記位，若M2中的某一類k2與M1中的某一類k1相似度最高，則將的標(biāo)記位設(shè)置為1，不再參與M1中其他類的相似度計(jì)算，從而提高了計(jì)算效率。

在三維點(diǎn)云模型中，類簇即為點(diǎn)的集合，計(jì)算類簇之間的相似度，即計(jì)算兩個(gè)點(diǎn)集之間的相似度。計(jì)算點(diǎn)集間距離最常用的方法是計(jì)算兩點(diǎn)集間的Hausdorff距離。假設(shè)空間中有兩點(diǎn)集，則A和B之間的Hausdorff距離為：

該方法的主要思想是對(duì)任意的類k1∈M1，分別計(jì)算k1與M2中標(biāo)記位不為1的類之間的距離，稱該距離為類間曲率距離，記為，在M2所有標(biāo)記位不為1的類中，選擇與k1具有最小的類作為k1匹配類，將匹配類的標(biāo)記位設(shè)置為1，在進(jìn)行M1中其他類匹配時(shí)，標(biāo)記位為1 的類不再參與匹配計(jì)算；所有類均匹配完成后，將所有的相加，結(jié)果記為C_DIS，C_DIS即為M1與M2的相似度。該方法的具體計(jì)算過程如下。

M1中第k1類的類間曲率距離為：

對(duì)任意的類k1∈M1，應(yīng)計(jì)算k1與M2中所有標(biāo)記位不為1的類，從中選擇具有最小的類與k1匹配，并將匹配類k2的標(biāo)記位設(shè)置為1。

然后，計(jì)算C_DIS。三維模型M1和M2中的類一一對(duì)應(yīng)后，此時(shí)每個(gè)均為最小值，M1和M2的類間相似度最高，因此將K個(gè)相加，M1和M2的相似度也為最高，計(jì)算公式如式（14）所示。

3 實(shí)驗(yàn)及結(jié)論

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

實(shí)驗(yàn)使用 Matlab R2016a、Visual Studio 2017 和OpenGL編程環(huán)境實(shí)現(xiàn)計(jì)算曲率特征、模型分類、模型匹配和顯示模型，實(shí)驗(yàn)平臺(tái)為Intel i7-6700 3.40 GHz CPU、8 GB 內(nèi)存的IBM PC 機(jī)。實(shí)驗(yàn)使用斯坦福大學(xué)三維模型數(shù)據(jù)庫，以填充后的三維模型Bunny為三維檢索模型M1,三維檢索模型M2為grey rabbit、hare、smile Bunny、cat、bird、bicycle、Armadillo 和 buddha。圖1 展示了完整三維網(wǎng)格模型、殘缺三維網(wǎng)格模型及填充三維網(wǎng)格模型，圖2展示了三維檢索模型M2的點(diǎn)云模型。

圖1 三維模型的網(wǎng)格模型圖

圖2 三維檢索模型M2 的點(diǎn)云模型圖

由圖1可以看出，填充后的三維模型雖然也是完整三維模型，但是其拓?fù)浣Y(jié)構(gòu)與完整三維模型相比已經(jīng)發(fā)生改變。因此，填充三維模型有形狀關(guān)聯(lián)的作用，可以作為殘缺三維模型與其對(duì)應(yīng)的完整三維模型的過渡模型。

為探究拓?fù)浣Y(jié)構(gòu)的改變是否會(huì)對(duì)三維模型聚類結(jié)果造成影響，將填充三維模型和對(duì)應(yīng)的完整三維模型分別進(jìn)行聚類，聚類數(shù)目K分別取10、9、8、7、6。聚類結(jié)果如圖3所示。

圖3 填充三維模型與完整三維模型在不同K 值下的聚類結(jié)果

由圖3 可以看出，在相同K值下，填充三維模型與其對(duì)應(yīng)的完整三維模型的聚類結(jié)果不完全相同，主要的差異體現(xiàn)在孔洞及其周圍區(qū)域，填充三維模型與其對(duì)應(yīng)的完整三維模型的聚類結(jié)果差別最為明顯，而遠(yuǎn)離孔洞區(qū)域的部分，如耳朵、臉部等區(qū)域，填充三維模型與其對(duì)應(yīng)的完整三維模型的聚類結(jié)果差別不大。由此可以看出，拓?fù)浣Y(jié)構(gòu)的改變會(huì)導(dǎo)致聚類結(jié)果發(fā)生變化。

拓?fù)浣Y(jié)構(gòu)的改變導(dǎo)致聚類結(jié)果發(fā)生了改變，是否會(huì)進(jìn)一步對(duì)檢索結(jié)果有較大影響，以及不同的聚類數(shù)目K對(duì)填充三維模型的檢索結(jié)果是否也存在影響。為探究以上兩個(gè)問題，表1和表2分別列出了在取不同的K值時(shí)，完整三維模型和填充三維模型進(jìn)行檢索時(shí)的C_DIS結(jié)果。

表1 完整三維模型的C_DIS結(jié)果

表2 填充三維模型的C_DIS結(jié)果

由表1 的實(shí)驗(yàn)結(jié)果可知，當(dāng)K固定時(shí)，在三維檢索模型M2中，按照與完整三維模型的相似度由高到低的順序，依次為hare、grey rabbit、smile Bunny、cat、Armadillo、buddha、bird 和 bicycle。由表 2 的實(shí)驗(yàn)結(jié)果可知，當(dāng)K固定時(shí)，在三維檢索模型M2中，按照與填充三維模型M1的相似度由高到低的順序，檢索結(jié)果與完整三維模型的檢索結(jié)果相同。當(dāng)K取不同值時(shí)，表1和表2的檢索結(jié)果不變，并按照與M1為同類生物、與M1為不同類生物的順序排列，在與M1為不同類生物中，又按照生物、非生物的順序排列。

根據(jù)表1 和表2 的實(shí)驗(yàn)結(jié)果，可以畫出以聚類數(shù)目K為X軸，以 C_DIS 為Y軸的折線圖，如圖4所示。

由圖4可知，從總體來看，在K取不同值時(shí)，無論是填充三維模型還是其對(duì)應(yīng)的完整三維模型，C_DIS 結(jié)果基本保持穩(wěn)定，受K值變化的影響不大。因此，即使在不知道事先應(yīng)將模型聚為幾類的情況下，也能得到較為準(zhǔn)確的檢索結(jié)果。從檢索結(jié)果來看，雖然不同K值下檢索結(jié)果稍有差異，但與Bunny屬于同類生物的grey rabbit、hare 和 smile Bunny 的相似度要高于與 Bunny 屬于不同類生物的三維模型，檢索結(jié)果基本穩(wěn)定，準(zhǔn)確率比較高。

為了更直觀地描述填充三維模型與其對(duì)應(yīng)的完整三維模型檢索結(jié)果的對(duì)比關(guān)系，圖5繪制了填充三維模型和其對(duì)應(yīng)的完整三維模型與每一個(gè)三維檢索模型檢索時(shí)的K-C_DIS折線圖。

圖4 K-C_DIS折線圖

由圖5可知，三維檢索模型與填充三維模型的檢索結(jié)果與其對(duì)應(yīng)的完整三維模型檢索結(jié)果的差異均保持在一定范圍內(nèi)，由此可知，在一定誤差范圍內(nèi)，殘缺三維模型可以通過填充成為完整三維模型進(jìn)行檢索，其檢索結(jié)果可以作為對(duì)應(yīng)的完整三維模型檢索結(jié)果使用。

3.2 性能分析

實(shí)驗(yàn)過程可以分為孔洞檢測、孔洞填充、模型聚類和模型匹配四部分。以殘缺三維模型Bunny為例，孔洞檢測和孔洞填充所用的時(shí)間如表3所示。

表3 孔洞檢測和孔洞填充所用時(shí)間

在模型聚類階段，取不同K值時(shí)聚類所用時(shí)間如表4所示。

表4 取不同K 值時(shí)聚類所用時(shí)間

在不同K值下，模型匹配所用時(shí)間如表5所示。

在完整的三維模型檢索過程中，孔洞檢測和孔洞填充所需時(shí)間占完整實(shí)驗(yàn)所需時(shí)間的比例如表6所示。

圖5 填充三維模型和其對(duì)應(yīng)的完整三維模型K-C_DIS對(duì)比圖

表5 不同K 值下模型匹配所用時(shí)間 s

表6 孔洞檢測和孔洞填充所需時(shí)間占比 %

由表5 和表6 的數(shù)據(jù)可知，當(dāng)檢索模型的數(shù)據(jù)集大小與被檢索模型的數(shù)據(jù)集大小相差不大時(shí)，孔洞檢測和孔洞填充所需時(shí)間占完整實(shí)驗(yàn)運(yùn)行時(shí)間的比例集中在50%左右，最高可達(dá)到70%以上，所占比例較高；當(dāng)檢索模型的數(shù)據(jù)集大小遠(yuǎn)大于被檢索模型的數(shù)據(jù)集大小時(shí)，孔洞檢測和孔洞填充所需時(shí)間占完整實(shí)驗(yàn)運(yùn)行時(shí)間的比例集中在20%左右。雖然孔洞檢測和孔洞填充所用時(shí)間占完整實(shí)驗(yàn)所用時(shí)間的比例大幅下降，但模型匹配過程所用時(shí)間卻大幅增長，因此，孔洞檢測和孔洞填充所占比例相對(duì)而言呈現(xiàn)下降趨勢。

4 結(jié)束語

基于孔洞填充的殘缺三維模型檢索方法以殘缺三維模型為研究對(duì)象，通過填充殘缺三維模型建立與其對(duì)應(yīng)的完整三維模型的形狀關(guān)聯(lián)，從而實(shí)現(xiàn)對(duì)殘缺三維模型的檢索。從檢索結(jié)果來看，填充三維模型檢索結(jié)果與其對(duì)應(yīng)的完整三維模型檢索結(jié)果差異較小，在一定誤差范圍內(nèi)，填充三維模型的檢索結(jié)果可以作為與其對(duì)應(yīng)的完整三維模型的檢索結(jié)果使用。因此，本文算法既適用于殘缺三維模型，也適用于完整三維模型，檢索方法具有魯棒性。此外，通過填充，使殘缺三維模型在外觀上盡可能接近對(duì)應(yīng)的完整三維模型。因此，填充三維模型和對(duì)應(yīng)的完整三維模型曲面彎曲程度基本保持一致，曲率能夠較好地描述填充三維模型的特征。最后，根據(jù)聚類中心對(duì)每個(gè)數(shù)據(jù)點(diǎn)的影響進(jìn)行聚類，采用類間匹配的方法計(jì)算模型相似度，避免了重復(fù)計(jì)算每個(gè)點(diǎn)與其他數(shù)據(jù)點(diǎn)的距離，提高了計(jì)算效率。