基于持久同調(diào)的三維模型檢索方法

況立群，李 麗，幸嘉誠，諶鐘毓，韓 燮

(1.中北大學(xué) 大數(shù)據(jù)學(xué)院，山西 太原 030051；2.南昌大學(xué) 軟件學(xué)院，江西 南昌 330047；3.華東交通大學(xué) 軟件學(xué)院，江西 南昌 330013)

0 引 言

面對數(shù)量眾多、種類繁雜的三維模型，如何及時有效地獲取到用戶所需模型，成為三維建模領(lǐng)域的研究熱點[1]。根據(jù)特征描述子的不同提取方式，三維模型檢索方法可分成統(tǒng)計特征獲取、投影視圖計算和拓?fù)浣Y(jié)構(gòu)描述3類。基于統(tǒng)計特征的檢索方法研究每個個體特征組成的總體分布情況，在描述模型內(nèi)部結(jié)構(gòu)方面有所欠缺，使得檢索效率不高[2]。基于投影視圖的檢索方法將三維模型投影為多個二維視圖[3]，在降維時會丟失三維模型的部分信息[4]。以上兩類檢索方法主要是對模型的幾何結(jié)構(gòu)進(jìn)行分類，忽略了模型的本質(zhì)拓?fù)涮卣鳎谕負(fù)浣Y(jié)構(gòu)的檢索方法則通過描述三維模型的骨架結(jié)構(gòu)來獲取模型的拓?fù)涮卣鱗5]，但難以應(yīng)用于無明顯骨架結(jié)構(gòu)的三維模型檢索。

近年來，國際上興起了基于持久同調(diào)理論的拓?fù)鋽?shù)據(jù)分析方法，適用于研究任意形狀物體的拓?fù)涮卣鳎褟V泛應(yīng)用于大數(shù)據(jù)[6]、腦影像特征分析[7]等領(lǐng)域，然而在三維模型檢索中的應(yīng)用不多，且國內(nèi)鮮有相關(guān)研究報道。因此，本文提出一種基于持久同調(diào)的三維模型檢索方法。該方法關(guān)注三維模型在多尺度下的拓?fù)浣Y(jié)構(gòu)，從本質(zhì)上獲取三維模型內(nèi)部的拓?fù)涮卣鳎煽坍嬕恍o明顯骨架結(jié)構(gòu)的三維模型的拓?fù)涮卣鳎哂行D(zhuǎn)平移和尺度不變性。

1 相關(guān)工作

1.1 持久同調(diào)

持久同調(diào)(persistent homology)是拓?fù)鋽?shù)據(jù)分析中的一個重要研究方向，關(guān)注的是三維模型結(jié)構(gòu)中點與點之間的拓?fù)洳蛔兞浚糜谘芯慷鄠€尺度下的定性特征[8]。本文運(yùn)用持久同調(diào)理論提取三維模型的特征描述子，其中的重要一步是為三維模型構(gòu)建復(fù)形過濾流(filtered complex)，其主要過程為：在三維模型中，每個點被一個直徑為d的球體所包圍，該球的直徑d從0開始逐步增大，當(dāng)三維模型中任意兩點的間距小于該時刻的直徑d時，便將這兩點連在一起。在該過程中使用單純復(fù)形(simplicial complex)去填充整個變化的結(jié)構(gòu)，最后形成一系列嵌套的單純復(fù)形，如圖1所示。

圖1 復(fù)形過濾流構(gòu)建

在構(gòu)建復(fù)形過濾流過程中獲取到三維模型在多尺度范圍上的拓?fù)浣Y(jié)構(gòu)，一些拓?fù)浣Y(jié)構(gòu)短暫出現(xiàn)之后被填充，被認(rèn)為是噪音和擾動；另外一些拓?fù)浣Y(jié)構(gòu)長時間持續(xù)存在，被認(rèn)為是穩(wěn)定的拓?fù)涮卣鳎@些穩(wěn)定的拓?fù)涮卣髅枋隽巳S模型內(nèi)部本質(zhì)的特征，將其作為特征描述子來表征三維模型，這便是持久同調(diào)的全過程[9]。

常構(gòu)建的復(fù)形過濾流有Cech復(fù)形、Alpha復(fù)形、Witness復(fù)形、Vietoris-Rips復(fù)形。本文中構(gòu)建的是Vietoris-Rips復(fù)形，即在高維空間中有一點集P，在過濾尺度λ下生成變化的P的子集σ，且子集中任意兩點之間距離都小于λ[10]，Vietoris-Rips復(fù)形的形式化如式(1)所示，其構(gòu)建過程如圖2所示[11]

VλP=du,v≤λ,?u≠v∈σ

(1)

圖2 Vietoris-Rips構(gòu)建過程

1.2 特征描述子

為了通過比較三維模型間的差異來實現(xiàn)檢索，需要為三維模型生成一個特征描述子。在持久同調(diào)過程中，產(chǎn)生了一些持續(xù)時間長的穩(wěn)定拓?fù)涮卣鳎ǔＳ秘惖贁?shù)(Betti number)的變化來量化這些特征[12]。

令K為一個原始的單純復(fù)形，可在某一時刻添加其子單純復(fù)形，構(gòu)建變化的復(fù)形過濾流，建立單純復(fù)形間的嵌套關(guān)系

K0?K1?K2…?Kn=K

(2)

因為Ki-1?Ki，在單純復(fù)形之間引入同態(tài)f:Hp(Ki-1)→Hp(Ki)，使嵌套的復(fù)形序列與同態(tài)連接的同調(diào)群序列一一對應(yīng)，其中每個維度對應(yīng)一個不同的p，則同調(diào)群秩的序列如下[8]

Hp(K0)→Hp(K1)→Hp(K2)…→Hp(Kn)=Hp(K)

(3)

同調(diào)群Hp(K)的秩叫作單純復(fù)形K的p維貝蒂數(shù)，它是代數(shù)拓?fù)渲卸x在同調(diào)群上的拓?fù)洳蛔兞浚?維貝蒂數(shù)表示連通分支的個數(shù)，1維貝蒂數(shù)表示一維下孔洞的個數(shù)，可用條形碼[11]和持久性[13]來表示貝蒂數(shù)的變化，如圖3和圖4所示。在條形碼圖中直線的起始點表示孔洞的產(chǎn)生時間，直線的終止點表示孔洞的消失時間；持久性圖中橫坐標(biāo)表示孔洞的產(chǎn)生時間，縱坐標(biāo)表示孔洞的消失時間。條形碼圖與持久性圖可以相互轉(zhuǎn)換，本文采用持久性圖來表征三維模型特征，作為三維模型的特征描述子。

圖3 條形碼

圖4 持久性

1.3 Wasserstein距離

由于持久性圖是二維散點的集合，難以在一維空間直接度量持久性圖之間的相似性。最傳統(tǒng)的度量方法當(dāng)屬瓶頸距離法，近年來有研究表明Wasserstein距離[14]具有更好的度量性能。Wasserstein距離最早被用來比較兩個直方圖的差異，之后被用來刻畫兩個分布之間的距離，可以通俗理解為將一堆物體移動到另一個位置的最小成本，它的定義為

(4)

其中，X和Y分別為滿足μ和ν概率分布的d維空間集合，p表示Lp范數(shù)，inf表示下界，本文方法中p值取1。

2 基于持久同調(diào)的三維模型檢索方法

本文提出一種基于持久同調(diào)的三維模型檢索方法，整個檢索框架如圖5所示。首先，采用Ripser軟件包來構(gòu)建Vietoris-Rips復(fù)形，計算得到三維模型的拓?fù)涮卣?1維貝蒂數(shù))，并將其表示在持久性圖中，形成特征描述子；然后利用分段Wasserstein距離計算兩個持久性圖之間的相似性；最后，檢索相應(yīng)模型，通過獲取到的評價參數(shù)來評價檢索效率。

圖5 總體檢索框架

2.1 數(shù)據(jù)預(yù)處理

本文采用Vietoris-Rips復(fù)形構(gòu)建三維點云模型的拓?fù)浣Y(jié)構(gòu)，該結(jié)構(gòu)比傳統(tǒng)的三角網(wǎng)格化模型的結(jié)構(gòu)復(fù)雜得多，嵌套復(fù)形的信息量異常龐大，難以對其直接拓?fù)浠桀A(yù)先對三維模型數(shù)據(jù)集進(jìn)行簡化。本文利用meshlab中的插件meshlabserver進(jìn)行批處理降采樣，通過減少面的個數(shù)來減少點的個數(shù)，同時在降采樣前設(shè)置“保留拓?fù)涮卣鳌钡葏?shù)。這樣不僅保留了三維模型內(nèi)部的拓?fù)涮卣鳎譁p少了模型的稠密度，縮短了計算時間。實驗中考慮到時間和設(shè)備的限制，將模型降為800個面，400多個點。

2.2 提取特征描述子

構(gòu)建Vietoris-Rips復(fù)形的軟件包有Javaplex、PHAT、GUDHI、DIPHA、Ripser等，其中Ripser是用于計算Vietoris-Rips持久性條形碼的精簡C++代碼，與其它軟件包相比，Ripser的運(yùn)行速度超出40倍，內(nèi)存效率超過15倍，且沒有外部依賴，可以大大提高計算的時間和效率[11]。因此，本文選用Ripser軟件包來構(gòu)建復(fù)形結(jié)構(gòu)，編程環(huán)境為Python語言的Pycharm。

在讀取簡化后三維模型點的信息后，調(diào)用Ripser庫中的ripser函數(shù)為每個三維模型構(gòu)建Vietoris-Rips復(fù)形，獲取到復(fù)形過濾流下的一維貝蒂數(shù)，它比零維貝蒂數(shù)能更好地表征三維模型內(nèi)部本質(zhì)的拓?fù)涮卣鳌D6為對三維模型數(shù)據(jù)集中的一個杯子模型構(gòu)建Vietoris-Rips復(fù)形后，得到零維和一維下的貝蒂數(shù)，將其表示在條形碼圖(左圖)和持久性圖(右圖)中，形成特征描述子。

圖6 杯子的特征描述子圖

2.3 相似性度量

Wasserstein距離在數(shù)值上只能計算一維高斯分布的情況，而本文計算的是二維持久性圖間的相似性，故此提出一種分段的Wasserstein距離來度量持久性圖之間的相似性。分段的Wasserstein距離是對Wasserstein距離的一個改進(jìn)，其基本原理為：讓通過原點的多條線去劃分持久性圖的平面，將二維的點投影到每條線的方向上，從而將二維點集投影為一維點集，然后再計算兩個一維點集間的Wasserstein距離，最后將各個方向上Wasserstein距離累加求和再平均，即為最終距離。本方法將提取到的拓?fù)涮卣饕渣c的形式記錄在持久性圖中，在第一象限內(nèi)的多個方向上進(jìn)行多次迭代，得到分段Wasserstein距離。計算過程分為對角線投影、Wasserstein距離計算、迭代求平均這3個步驟。

(1)投影到對角線

假設(shè)有兩個持久性圖dg1和dg2，其中dg1為m個點構(gòu)成的特征集合，dg2為n個點構(gòu)成的特征集合，將dg1的點投影到y(tǒng)=x這條對角線上，并將投影后的點加入到dg2中。同理，將dg2的點投影到y(tǒng)=x這條對角線上，將投影后的點加入到dg1中。投影到對角線保證了兩個持久性圖在進(jìn)行相似性度量時特征向量個數(shù)一致，并且仍保留各自的特征分布，原始的持久性圖表示如下

(5)

投影到對角線后得到

(6)

(2)計算Wasserstein距離

計算Wasserstein距離的示意圖如圖7所示。從原點射出的某條直線與X正半軸成θ角，且滿足sinθ2+cosθ2=1，由式(7)依次計算dg1中每個點和這個方向的點積

(cosθ,sinθ)·(xi,yi)=xicosθ+yisinθ=Xi,i=1…(m+n)

(7)

圖7 計算Wasserstein距離

將結(jié)果計入V1數(shù)組并排序，同理計算dg2中每個點與該方向的點積，將結(jié)果計入V2數(shù)組并排序

(8)

(3)迭代求平均

將第一象限平均分成M個方向，即迭代次數(shù)為M。為了加快計算過程，可以設(shè)置較小的迭代次數(shù)，實驗結(jié)果表明迭代次數(shù)較少時也能得到較好的檢索效果。從0開始以s=π/2/M的角度遞增，在每個方向上計算出一維數(shù)據(jù)的Wasserstein距離，之后累加求和再平均得到分段Wasserstein距離(式(9))。以此作為兩個持久性圖之間的差異值，該值越小表示兩個持久性圖的分布越近似，說明兩個三維模型越相似。迭代的目的是使兩個持久性圖在多個方向上計算差異，通過迭代求平均使實驗結(jié)果更準(zhǔn)確，更具有穩(wěn)定性

(9)

3 實驗結(jié)果及分析

3.1 實驗環(huán)境及數(shù)據(jù)

本研究實驗硬件環(huán)境為Intel(R)Xeon(R)CPU E5-1603 v3 @ 2.80 GHz 2.80 GHz，內(nèi)存為16 GB，軟件環(huán)境為64位的windows 10、matlab2013b、PyCharm Community Edition 2018.3.2。實驗數(shù)據(jù)集來源于2011年的三維模型檢索競賽(SHREC TRACK 2011)的標(biāo)準(zhǔn)數(shù)據(jù)庫[15]，本數(shù)據(jù)集包括600個三維模型，共分為30個類，每類20個三維模型。

3.2 評價標(biāo)準(zhǔn)

為了衡量檢索效果的好壞，本文使用檢索領(lǐng)域常用的評價參數(shù)NN(nearest neighbor)、F-T(first tire)、S-T(second tire)、E(e-measure)、DCG(discounted cumulative gain)來進(jìn)行評估。假設(shè)目標(biāo)類模型個數(shù)為C，K為需檢索出的模型個數(shù)，則NN表示當(dāng)K=1時正確檢索到的目標(biāo)模型的比例；F-T表示當(dāng)K=C-1時正確檢索到的目標(biāo)模型的比例；S-T表示當(dāng)K=2*C-1時正確檢索到的目標(biāo)模型的比例；DCG表示根據(jù)檢索結(jié)果的排列順序來評價檢索優(yōu)劣；E為查全率和查準(zhǔn)率的綜合評價參數(shù)。為了更好地表征三維模型檢索的效果，通常還采用P-R圖表示數(shù)據(jù)集整體的查全率和召回率。

3.3 實驗結(jié)果

本文實驗結(jié)果分為兩部分，第一部分是本文方法的檢索結(jié)果，第二部分是本方法與其它方法的實驗數(shù)據(jù)對比。

(1)采用本文方法對“螞蟻”、“鉗子”三維模型進(jìn)行檢索，這兩類三維模型在本數(shù)據(jù)集中各有20個，所以本實驗檢索出與目標(biāo)模型最相近的前20個三維模型，以評價檢索的準(zhǔn)確性，檢索結(jié)果如圖8所示。由圖8可以看出，除個別三維模型外，其余模型與目標(biāo)模型同屬一類，由此得出，本文方法可以有效地檢索出目標(biāo)模型，準(zhǔn)確率較高。

圖8 檢索結(jié)果

(2)本文實驗與Osada等的形狀概率分布方法(shape distribution，D2)、Sun等的熱核特征方法(heat kernel signature，HKS)[16]、Sipiran等的角點檢測方法(Harris 3D geodesic map，Harris3DGeoMap)[17]和焦世超等的多特征融合流行排序方法(multi-features fused manifold ran-king，M-F FMR)[18]進(jìn)行了對比。D2方法首先計算所有點之間的距離，然后將所有距離值作為特殊分布表示在直方圖中。HKS方法對模型上每個點的熱量變化曲線離散化，之后獲取全部點的特征，進(jìn)而得到整個模型的熱核特征。Harris3DGeoMap方法采用3D Harris算法選取原始模型小部分的顯著興趣點，用特征分布直方圖表示興趣點間測地線距離的差異。Harris3DGeoMap16和Harris3DGeoMap32分別表示直方圖區(qū)間數(shù)目為16和32條件下的Harris3DGeoMap實驗。M-F FMR方法采用融合特征對二維視圖提取特征，然后利用深度學(xué)習(xí)對草圖進(jìn)行語義標(biāo)注，再使用流行排序算法實現(xiàn)二維草圖到三維模型的檢索。

這幾種方法都是在SHREC TRACK 2011的三維數(shù)據(jù)集上進(jìn)行實驗，實驗結(jié)果具有可比性。對NN、F-T、S-T、E、DCG參數(shù)進(jìn)行實驗對比，結(jié)果見表1，這些值越接近于1表明檢索效果越好，從表中看出本文的全部參數(shù)優(yōu)于所有對比方法。同時繪制P-R曲線圖進(jìn)行對比，結(jié)果如圖9所示，該圖走向越趨向于右上方說明檢索效果越好，從圖中可以看出本文方法的曲線均高于其它方法。

表1 6種檢索方法的評價參數(shù)

圖9 6種檢索方法的P-R曲線

綜上，實驗結(jié)果表明，本文提出的基于持久同調(diào)的三維模型檢索方法具有較高的準(zhǔn)確率，在檢索結(jié)果(圖8)中可以看到準(zhǔn)確檢索到了待查詢的模型；此外，本文方法的評價參數(shù)和P-R曲線圖均優(yōu)于其它方法。

4 結(jié)束語

本文將持久同調(diào)理論應(yīng)用于三維模型檢索，提出了一種基于持久同調(diào)的三維模型檢索方法，能夠在不降維的情況下提取出三維模型的全局特征描述子，該描述子具有旋轉(zhuǎn)、平移和尺度不變性，在數(shù)據(jù)擾動的情況下具有很好的穩(wěn)定性，可全面有效地表征任意拓?fù)浣Y(jié)構(gòu)的三維模型的特征。另外提出了區(qū)分性更好的分段Wasserstein距離，對持久性圖之間進(jìn)行了更為準(zhǔn)確的相似性度量，進(jìn)一步提高了三維模型檢索的查準(zhǔn)率和查全率。本文研究結(jié)果對今后三維模型檢索提供了一種新的研究思路和設(shè)計方法。鑒于時間與空間上的計算資源限制，本文未能將三維模型的全部點計算在內(nèi)，而是進(jìn)行了降采樣處理，客觀上降低了檢索效率。在今后的研究中將利用并行計算資源來完善實驗環(huán)節(jié)，提高檢索準(zhǔn)確率。