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

陳思琦，劉 麗，陳秀秀，張 龍，王天時

山東師范大學 信息科學與工程學院，濟南 250014

1 引言

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

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

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

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

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

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

2.1 高精度的孔洞填充

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

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

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

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

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

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

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

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

其中，

當矩陣A滿秩時，使下式最小化即可求得x：

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

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

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

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

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

算法具體過程如下所示。

算法1 高精度的孔洞填充

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

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

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

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

2.2 填充三維模型檢索

2.2.1 填充三維模型曲率計算

在提取三維點云模型的幾何信息時，主要通過直接計算法和最小二乘擬合算法獲取點云的局部n次曲面。點云的局部曲面有兩種表示方法：一是基于法向距離的局部曲面表示；二是基于歐氏距離的局部曲面表示。基于孔洞填充的殘缺三維模型檢索方法利用點云模型的坐標信息，采用基于歐氏距離的局部曲面表示法獲取點云模型的曲率。曲率是描述三維模型形狀的重要屬性[14]，準確的坐標信息提高了對模型描述的精確度，進而提高了三維模型檢索時的準確率[15]。

2.2.2 填充三維模型聚類

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

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

具體聚類過程如下：

然后，計算每個點成為下個聚類中心的概率，計算公式如下：

重復這一過程，直到選出K個初始聚類中心為止。

在一次聚類完成后，需要重新計算聚類中心的坐標，計算公式如下：

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

2.2.3 填充三維模型匹配

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

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

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

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

對任意的類k1∈M1，應計算k1與M2中所有標記位不為1的類，從中選擇具有最小的類與k1匹配，并將匹配類k2的標記位設置為1。

然后，計算C_DIS。三維模型M1和M2中的類一一對應后，此時每個均為最小值，M1和M2的類間相似度最高，因此將K個相加，M1和M2的相似度也為最高，計算公式如式（14）所示。

3 實驗及結(jié)論

3.1 實驗結(jié)果

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

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

圖2 三維檢索模型M2 的點云模型圖

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

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

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

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

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

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

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

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

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

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

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

圖4 K-C_DIS折線圖

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

3.2 性能分析

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

表3 孔洞檢測和孔洞填充所用時間

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

表4 取不同K 值時聚類所用時間

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

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

圖5 填充三維模型和其對應的完整三維模型K-C_DIS對比圖

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

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

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

4 結(jié)束語

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