基于特征融合的文物碎片模型檢索

趙夫群，戴 翀，耿國華*

(1. 西安財(cái)經(jīng)大學(xué)信息學(xué)院 西安 710100；2. 西北大學(xué)信息科學(xué)與技術(shù)學(xué)院 西安 710127)

隨著三維激光掃描技術(shù)的出現(xiàn)，物體的三維模型展現(xiàn)和處理技術(shù)也得到了快速發(fā)展。這是由于三維模型具有較強(qiáng)的特征展現(xiàn)力，并且可以彌補(bǔ)其他多媒體資源在信息存儲(chǔ)、共享和展示等方面的不足。模型檢索是三維模型處理技術(shù)的一個(gè)重要研究內(nèi)容，是指從大量三維模型中檢索出與某一特定模型相似的所有模型的過程。目前，三維模型檢索已經(jīng)在數(shù)字圖像處理、文物虛擬復(fù)原以及計(jì)算機(jī)輔助設(shè)計(jì)等領(lǐng)域[1-4]得到了較為廣泛的應(yīng)用。

根據(jù)提取對(duì)象的差異，通常可以將三維模型檢索方法分為兩種類型，即基于文本的檢索方法和基于內(nèi)容的檢索方法。基于文本的檢索方法需要人為地給三維模型添加相應(yīng)的關(guān)鍵字，具有較強(qiáng)的主觀性；而基于內(nèi)容的檢索方法則是通過提取三維模型的顯著幾何特征進(jìn)行檢索，可以有效減少人工干預(yù)，是目前使用較多的模型檢索方法。近年來，國內(nèi)外學(xué)者提出了很多基于內(nèi)容的三維模型檢索算法。文獻(xiàn)[5]提出一種基于聯(lián)合形狀分布的三維模型檢索算法，通過主面分析和群融合提高了模型檢索的精度；文獻(xiàn)[6]提出一種多模態(tài)視圖的三維模型檢索算法，通過構(gòu)造多模態(tài)特征空間中圖的超邊實(shí)現(xiàn)模型檢索；文獻(xiàn)[7]提出一種基于多模態(tài)圖學(xué)習(xí)的三維模型檢索算法，通過度量模型的多個(gè)視圖間的相似性實(shí)現(xiàn)檢索；文獻(xiàn)[8]提出一種基于非監(jiān)督特征學(xué)習(xí)的三維模型檢索算法，有效提高了模型檢索的效率；文獻(xiàn)[9]提出一種基于梯度描述子優(yōu)化的支持三維物體檢索的有效方法，該方法以稀疏編碼為基礎(chǔ)，通過實(shí)驗(yàn)驗(yàn)證了該方法的有效性。這些三維模型檢索算法均具有較高的檢索效率，但仍然存在局部特征有效性低、模型整體信息表達(dá)差以及檢索效率低等缺點(diǎn)，因此不適合用于復(fù)雜陶質(zhì)文物類碎片模型的檢索。

兵馬俑是一種較為復(fù)雜的文物模型，在出土挖掘過程中破損嚴(yán)重，碎片數(shù)量較多，并且存在碎片缺失、形狀各異以及特征模糊等問題。在計(jì)算機(jī)輔助兵馬俑虛擬復(fù)原時(shí)，直接將大量碎片進(jìn)行拼接復(fù)原是一項(xiàng)NP 難題，因此有必要設(shè)計(jì)高效的碎片智能檢索方法，將碎片按照一定規(guī)則劃分為若干子集，降低碎片匹配時(shí)的窮舉規(guī)模，為匹配拼接工作提供指導(dǎo)約束，提高虛擬修復(fù)效率。針對(duì)兵馬俑碎片的三維模型復(fù)雜引起的檢索困難問題，提出一種基于特征融合的碎片點(diǎn)云數(shù)據(jù)模型的快速檢索算法。該算法通過融合碎片點(diǎn)云的曲率和法向夾角特征，并通過迭代對(duì)融合特征進(jìn)行匹配來實(shí)現(xiàn)模型檢索。算法不僅可以準(zhǔn)確地描述碎片的表面幾何特征，而且可以避免算法陷入局部極值，從而提高碎片檢索的精度和速度。

1 融合特征計(jì)算

1.1 曲率特征

曲率可以有效反映點(diǎn)云表面的凹凸程度，越是特征明顯的點(diǎn)云區(qū)域，其曲率也就越大，而特征不夠明顯的區(qū)域，其曲率也就越小。這里利用k-D tree(k-Dimension tree)算法[10]構(gòu)造點(diǎn)云上點(diǎn)及其鄰域點(diǎn)的切平面來計(jì)算曲率。

對(duì)于點(diǎn)云模型D={di}，i=1,2,···,ND， ND表示點(diǎn)云 D中所包含的點(diǎn)數(shù)，首先采用k-D tree 算法計(jì)算點(diǎn) di的k近鄰點(diǎn)。該算法需要查找在點(diǎn) di周圍的固定半徑為r內(nèi)的k個(gè)近鄰點(diǎn)，通過判斷兩點(diǎn)之間的歐氏距離即可實(shí)現(xiàn)，具有較高的處理效率。這里，k 不是一個(gè)固定的整數(shù)值，需要在實(shí)驗(yàn)中設(shè)置k的上限，而r是一個(gè)固定半徑，也需要在實(shí)驗(yàn)中給出。

k-D tree 鄰域點(diǎn)查詢算法的步驟如下：

1)確定點(diǎn)云 D的劃分維度和劃分點(diǎn)。通常從方差最大的維度開始劃分，可確保良好的切分效果和平衡性。根據(jù)該維度上的點(diǎn)的數(shù)值進(jìn)行排序，并取中值點(diǎn)作為點(diǎn)云的劃分點(diǎn)。

2)確定點(diǎn)云 D的左、右子空間。分割超平面過劃分點(diǎn)可以將點(diǎn)云 D劃分為兩部分，數(shù)值小于中值點(diǎn)的劃為左子空間，剩下的一部分為右子空間。

3)對(duì)于左、右子空間，分別重復(fù)步驟1)和步驟2)，以相同的方式遞歸地進(jìn)行分割，直到分割的子空間內(nèi)點(diǎn)的個(gè)數(shù)滿足條件為止，由此構(gòu)建好k-D tree。

4)從k-D tree 的根結(jié)點(diǎn)開始，按照查詢點(diǎn)與各個(gè)結(jié)點(diǎn)的比較結(jié)果向下訪問k-D tree，直至達(dá)到葉子結(jié)點(diǎn)。計(jì)算查詢點(diǎn)與葉子結(jié)點(diǎn)上保存的數(shù)據(jù)之間的距離，若距離小于r，則記錄該點(diǎn)的索引和距離。

5)回溯搜索路徑，并判斷搜索路徑上結(jié)點(diǎn)的其他子節(jié)點(diǎn)空間中是否有與查詢點(diǎn)距離小于r的點(diǎn)。若有，則跳到該子節(jié)點(diǎn)空間中去搜索，執(zhí)行步驟4)中相同的查找過程；否則，繼續(xù)回溯過程直到搜索路徑為空。

通過上述步驟即可查詢出點(diǎn)云 D上任意一點(diǎn)di的k近鄰點(diǎn)。假設(shè)x軸和y軸是點(diǎn)云 D上點(diǎn) di及其k近鄰點(diǎn)擬合切平面上的兩個(gè)正交向量， z軸是點(diǎn)云D的法矢，那么x、 y和z軸就構(gòu)成了笛卡爾坐標(biāo)系。可以定義點(diǎn) di的切平面S(x,y)為：

在式(1)中，存在一組數(shù)值a、 b、 c、 d、 e使其成立，采用線性方程組可表示為：

1.2 法向夾角

法向夾角是指數(shù)據(jù)點(diǎn)法線方向與其鄰近點(diǎn)法線方向的夾角，可用于描述點(diǎn)云表面的彎曲程度[11]。對(duì)于點(diǎn)云 D上 任意一點(diǎn) di，通過查詢 di的k近鄰點(diǎn)可計(jì)算其協(xié)方差矩陣 Ci為：

計(jì)算協(xié)方差矩陣 Ci的特征值，假設(shè)其特征值為λ1≤λ2≤λ3，那么點(diǎn) di的法線就是協(xié)方差矩陣 Ci的最小特征值對(duì)應(yīng)的特征向量的方向。假設(shè)特征值λ1≤λ2≤λ3對(duì)應(yīng)的特征向量為分別為e1,e2,e3，那么特征值 λ1就表示點(diǎn)云表面沿法線方向的變化量，點(diǎn)di的法線方向就是ni=e1。

定義點(diǎn) di的法線夾角參數(shù)ωa(di)為：

法線夾角參數(shù)ωa(di)反映了點(diǎn) di的所有k近鄰點(diǎn)對(duì)點(diǎn)云表面彎曲程度的影響。ωa(di)越大，點(diǎn) di及其k近鄰點(diǎn)的表面彎曲程度就越大，點(diǎn) di的鄰域成為特征區(qū)域的可能性就越大；反之，ωa(di)越小，點(diǎn) di的k近鄰點(diǎn)的表面就越光滑，點(diǎn) di的鄰域成為特征 區(qū)域的可能性就越小。

1.3 特征融合

基于以上對(duì)曲率和法向夾角參數(shù)的計(jì)算，定義點(diǎn) di的融合特征參數(shù)ω(di)為：

式中， α和β表示曲率系數(shù)，均為正數(shù)。

由式(9)可見，主曲率Ri1、Ri2、法線夾角ωa(di)與融合特征參數(shù)ω(di)均成正比。 Ri1、 Ri2和ωa(di)越大，點(diǎn) di成為特征點(diǎn)的幾率就越高；反之， Ri1、Ri2和ωa(di)越小，點(diǎn) di成為特征點(diǎn)的幾率就越低。

2 基于融合特征匹配的檢索

基于以上計(jì)算的融合特征參數(shù)ω(di)，通過將大量三維模型與一個(gè)已知模型進(jìn)行融合特征匹配即可實(shí)現(xiàn)模型檢索。假設(shè)已知點(diǎn)云模型為M={mj|mj∈R3,i=1,2,···,NM}，某一個(gè)待檢索的目標(biāo)點(diǎn)云模型為D={di|di∈R3,i=1,2,···,ND}，采用融合特征匹配算法將 M 與 D進(jìn)行匹配檢索的具體步驟描述如下：

指紋是指尖表面上交替分布的脊線和谷線圖案。指紋圖像有著許多不同于其它圖像的特點(diǎn)，其紋理性和方向性比較強(qiáng)，而指紋圖像的方向場代表了指紋的這種固有性質(zhì)。通過原始指紋圖像的紋理信息，求出每一個(gè)像素點(diǎn)的切線方向，就可以描繪出整幅指紋圖像的方向場圖，而方向場圖又為后續(xù)指紋圖像的濾波、特征提取奠定了基礎(chǔ)，故該方向場估算十分重要[12-13]。

1)對(duì)于參考點(diǎn)云 M和目標(biāo)點(diǎn)云 D，利用k-D tree 算法查詢其上任意一點(diǎn)di∈D和 mj∈M的k近鄰點(diǎn)，并利用式(3)～式(9)計(jì)算點(diǎn)的主曲率、法向夾角和融合特征參數(shù)；

式中， s 表示迭代次數(shù)，初始設(shè)置為s=0。

3)判斷式(11)和式(12)，若成立，那么點(diǎn) di即為點(diǎn) mj的匹配點(diǎn)：

式中， Ri1和 Ri2表示鄰域點(diǎn)的兩個(gè)主曲率； ωα表示鄰域點(diǎn)的法向夾角；τcurvature和τnormal分別表示曲率和法向夾角的閾值。

4)令s=s+1，利用式(13)計(jì)算旋轉(zhuǎn)矩陣 Rs、平移矢量 ts和Ds=RsD+ts。

6)重復(fù)步驟4)到步驟5)，直到匹配誤差RMSs小于預(yù)設(shè)閾值ε或達(dá)到最大迭代次數(shù)stepmax為止；

7)判斷，若RMSs小于給定閾值ε，那么目標(biāo)點(diǎn)云 D就可以和參考點(diǎn)云 M正確匹配，點(diǎn)云 D就是檢索到的點(diǎn)云 M的相似模型。否則，點(diǎn)云 D就不是點(diǎn)云 M的相似模型，由此實(shí)現(xiàn)了模型檢索。

在該檢索算法中，尋找兩個(gè)三維模型的匹配點(diǎn)時(shí)，不僅僅利用式(10)計(jì)算相應(yīng)點(diǎn)的距離來實(shí)現(xiàn)，而且加入了約束條件式(11)和式(12)，通過融合曲率和法線夾角特征來進(jìn)一步刻畫模型上點(diǎn)的鄰域曲面的彎曲程度，可以更加精確地描述模型特征，降低相關(guān)點(diǎn)的誤匹配率，從而避免陷入局部極值，提高模型檢索的精度。

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

實(shí)驗(yàn)采用西北大學(xué)可視化技術(shù)研究所提供的兵馬俑碎片驗(yàn)證所提檢索算法。以50 個(gè)已經(jīng)拼合的兵俑為模板，共包含1 036 個(gè)碎片。由于碎片數(shù)量較大，這里僅展示部分碎片，如圖1 所示，碎片均采用三維點(diǎn)云數(shù)據(jù)模型表示。按照俑的身體部位，將碎片按照5 種類別進(jìn)行檢索，即頭部碎片(C1類)、軀干碎片(C2 類)、裙擺碎片(C3 類)、上肢碎片(C4 類)和下肢碎片(C5 類)。

圖1 部分碎片

采用所提檢索算法，以圖2 所示的頭部碎片、軀干碎片、裙擺碎片、上肢碎片和下肢碎片為檢索的參考模型，首先計(jì)算碎片點(diǎn)云模型的曲率和法向夾角，并將其加權(quán)融合，然后通過對(duì)融合特征的匹配來實(shí)現(xiàn)碎片檢索。所提算法的碎片檢索結(jié)果如圖3 所示。

圖2 檢索參考模型

通過對(duì)大量兵馬俑碎片的點(diǎn)云數(shù)據(jù)模型進(jìn)行檢索分析，結(jié)果發(fā)現(xiàn)曲率系數(shù) α 和 β對(duì)特征參數(shù)的計(jì)算結(jié)果有較大影響。同時(shí)由于鄰域點(diǎn)的數(shù)量跟點(diǎn)云密度及其分布的均勻性有很大關(guān)系，因此當(dāng)點(diǎn)云數(shù)據(jù)模型的密度較大時(shí)， α 和 β的取值較小，當(dāng)點(diǎn)云數(shù)據(jù)模型的密度較小時(shí)， α和 β的取值較大。

通過實(shí)驗(yàn)驗(yàn)證，通常建議 α和 β的取值范圍均在10～30 之間。本實(shí)驗(yàn)中， α和 β的取值均為20。

圖3 碎片檢索結(jié)果

為了驗(yàn)證所提檢索算法的精度，對(duì)1 036 個(gè)兵馬俑碎片再分別采用文獻(xiàn)[12]算法、文獻(xiàn)[13]算法，以及本文算法中無主曲率和融合特征參數(shù)約束的算法進(jìn)行檢索，檢索結(jié)果的準(zhǔn)確率如表1 所示。從表1 的檢索結(jié)果可見，所提檢索算法的準(zhǔn)確率最高，檢索效果最佳。

這是由于文獻(xiàn)[12]算法是一種基于多層深度網(wǎng)絡(luò)的三維模型檢索算法，通過構(gòu)建局部信息和全局信息的特征學(xué)習(xí)模型實(shí)現(xiàn)模型檢索。雖然該算法在一定程度上提高了檢索效率，但是采用的特征表示方法對(duì)兵馬俑碎片模型的整體信息表達(dá)相對(duì)較差，因此檢索的準(zhǔn)確率依舊不夠高。文獻(xiàn)[13]算法是一種基于模糊C 均值和卷積神經(jīng)網(wǎng)絡(luò)的模型檢索算法，該方法將直覺模糊集引入到模型特征中以實(shí)現(xiàn)碎片特征分離，并根據(jù)分離特征實(shí)現(xiàn)模型檢索。但是該算法需要人為設(shè)置檢索參數(shù)，檢索時(shí)間復(fù)雜度較高，對(duì)交叉特征的檢索效果較差，從而影響了檢索的準(zhǔn)確率。無約束算法是在所提算法中去除了主曲率和融合特征參數(shù)約束，通過直接計(jì)算模型特征點(diǎn)的距離實(shí)現(xiàn)相似特征的匹配，從而進(jìn)行模型檢索，因此準(zhǔn)確率不高。而所提算法融合了兵馬俑碎片的兩個(gè)主曲率和法向夾角特征，并通過迭代地對(duì)融合特征進(jìn)行匹配來實(shí)現(xiàn)模型檢索，不僅可以準(zhǔn)確地描述碎片的幾何特征，而且可以避免算法陷入局部極值，從而提高檢索精度和速度。由此可見，本文的基于融合特征的三維模型檢索算法是一種有效的高精度兵馬俑碎片檢索方法。

表1 4 種檢索算法的準(zhǔn)確率%

4 結(jié) 束 語

在基于特征的三維模型檢索方法中，選擇合適的特征并對(duì)其進(jìn)行表示和融合是模型檢索要解決的關(guān)鍵問題。提出的三維模型檢索算法融合了曲率和法向夾角特征，并通過對(duì)融合特征的相似性匹配實(shí)現(xiàn)了三維模型的精確檢索。通過將該算法應(yīng)用到兵馬俑碎片檢索中，可以實(shí)現(xiàn)碎片分類，降低后期碎片匹配的窮舉規(guī)模，為碎片拼接提供指導(dǎo)和約束，提高兵馬俑虛擬修復(fù)技術(shù)在文物數(shù)字化保護(hù)中的應(yīng)用能力。但是，本文算法采用的是加權(quán)求和的特征融合方式，通用性不夠高，因此后期研究中要考慮將視覺顯著性應(yīng)用到模型特征提取中，將多模態(tài)應(yīng)用于特征融合中，進(jìn)一步提高模型檢索的精度。