趙夫群，戴 翀，耿國華*

(1. 西安財經大學信息學院 西安 710100；2. 西北大學信息科學與技術學院 西安 710127)

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

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

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

1 融合特征計算

1.1 曲率特征

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

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

k-D tree 鄰域點查詢算法的步驟如下：

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

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

3)對于左、右子空間，分別重復步驟1)和步驟2)，以相同的方式遞歸地進行分割，直到分割的子空間內點的個數滿足條件為止，由此構建好k-D tree。

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

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

通過上述步驟即可查詢出點云 D上任意一點di的k近鄰點。假設x軸和y軸是點云 D上點 di及其k近鄰點擬合切平面上的兩個正交向量， z軸是點云D的法矢，那么x、 y和z軸就構成了笛卡爾坐標系?？梢远x點 di的切平面S(x,y)為：

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

1.2 法向夾角

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

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

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

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

1.3 特征融合

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

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

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

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

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

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

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

式中， s 表示迭代次數，初始設置為s=0。

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

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

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

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

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

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

3 實驗結果與分析

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

圖1 部分碎片

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

圖2 檢索參考模型

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

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

圖3 碎片檢索結果

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

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

表1 4 種檢索算法的準確率%

4 結 束 語

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