基于最大相似類別和位置熵的三維模型融合檢索方法

陳俊英， 孟月波， 王羨慧， 劉四妹（. 西安建筑科技大學(xué)信息與控制工程學(xué)院，陜西 西安 70055；

2. 新疆大學(xué)信息科學(xué)與工程學(xué)院，新疆 烏魯木齊 830046；

3. 中國(guó)聯(lián)通網(wǎng)絡(luò)通信公司西安分公司，陜西 西安710043）

基于最大相似類別和位置熵的三維模型融合檢索方法

陳俊英1， 孟月波1， 王羨慧2， 劉四妹3（1. 西安建筑科技大學(xué)信息與控制工程學(xué)院，陜西 西安 710055；

2. 新疆大學(xué)信息科學(xué)與工程學(xué)院，新疆 烏魯木齊 830046；

3. 中國(guó)聯(lián)通網(wǎng)絡(luò)通信公司西安分公司，陜西 西安710043）

為了有效利用各特征集對(duì)三維模型內(nèi)容的描述信息，對(duì)各種特征集上分別檢索的結(jié)果進(jìn)行綜合分析，統(tǒng)計(jì)各類模型的分布概率得到查詢模型的最大相似類別，然后在各個(gè)檢索結(jié)果中統(tǒng)計(jì)該類別模型的位置熵，基于最大相似類別模型數(shù)目和位置熵計(jì)算融合權(quán)值。在普林斯頓標(biāo)準(zhǔn)3D模型集上進(jìn)行實(shí)驗(yàn)，并和其他幾種動(dòng)態(tài)融合方法和靜態(tài)方法進(jìn)行比較，結(jié)果說明所提出的方法在有弱特征集存在的情況下是有效的。

3D模型檢索；多特征；動(dòng)態(tài)融合

隨著3D模型的普及應(yīng)用，從現(xiàn)有模型資源中進(jìn)行檢索是勢(shì)在必行的事情，基于內(nèi)容的 3D模型檢索已得到產(chǎn)業(yè)界與學(xué)術(shù)界越來(lái)越多的重視。在基于內(nèi)容的3D模型檢索過程中，首先需要尋找合適的特征描述算法。迄今為止，已有幾十種特征描述算法被相繼提出，但沒有一種通用的特征描述方法能針對(duì)任意的模型都能取得最佳的檢索效果。并且文獻(xiàn)[1]的研究結(jié)果表明：特征提取方法在描述能力方面存在極限，這一極限不能通過提高形狀特征的細(xì)致程度加以突破。

為提高檢索性能，研究人員一方面在繼續(xù)尋找高效的特征提取方法，如矩描述[2]方法等；另一方面在現(xiàn)有的特征提取方法基礎(chǔ)上借助于機(jī)器學(xué)習(xí)領(lǐng)域的方法進(jìn)行進(jìn)一步處理，包括特征選擇、多種特征融合、對(duì)特征進(jìn)行分類和聚類分析等，尋找有效的多特征融合方法是目前研究的熱點(diǎn)問題之一[3]。文獻(xiàn)[4]應(yīng)用靜態(tài)權(quán)值的方法進(jìn)行融合，這種方法需先給定權(quán)值等級(jí)（如0,1,2,3）。在檢索時(shí)，針對(duì)任何查詢模型都使用同一參數(shù)組合。文獻(xiàn)[5]中分別計(jì)算各個(gè)特征集上的熵不純度(entropy impurity)，然后基于熵不純度計(jì)算融合權(quán)值。文獻(xiàn)[6]中分別統(tǒng)計(jì)各個(gè)特征集上檢索列表的前 k（k是設(shè)定的參數(shù)）項(xiàng)同類模型最多的數(shù)目，得到各個(gè)特征集對(duì)應(yīng)的純度(purity)，然后利用純度計(jì)算融合權(quán)值。Leng等人[7]提出基于先驗(yàn)知識(shí)的檢索方法，對(duì)一個(gè)特定的特征集，先統(tǒng)計(jì)檢索列表前k項(xiàng)中同類模型最多的類別，然后計(jì)算該類別模型在列表中的累加增益，通過累加增益得到該特征集的融合權(quán)值。這3個(gè)算法中熵雜度、純度和先驗(yàn)知識(shí)的獲得主要依賴于各個(gè)檢索列表中排序前幾位的模型類別和各類別模型的數(shù)目，沒有利用各個(gè)特征集上的綜合檢索結(jié)果指導(dǎo)權(quán)值計(jì)算，這對(duì)在單特征集上檢索性能都較好的情況下是有效的，如果融合中存在弱特征集，排序前幾位的模型類別和同類模型數(shù)目可能給出誤導(dǎo)信息，導(dǎo)致計(jì)算出的融合權(quán)值不適合，從而導(dǎo)致檢索性能變差。

針對(duì)融合中有弱特征集存在的問題，提出基于最大相似類別和位置熵的多特征動(dòng)態(tài)融合檢索方法，該方法從各特征集的綜合檢索結(jié)果出發(fā)，避免了從各個(gè)特征集自身出發(fā)計(jì)算相應(yīng)參數(shù)的片面性。下面首先介紹多特征動(dòng)態(tài)融合的檢索方法，然后通過實(shí)驗(yàn)驗(yàn)證了該方法的有效性。

1 多特征動(dòng)態(tài)融合算法

對(duì)一個(gè)查詢模型，先把各個(gè)特征集上檢索列表的前k項(xiàng)綜合考慮，統(tǒng)計(jì)同類模型數(shù)，將具有最多模型數(shù)目的類別作為查詢模型的最大相似類別，然后在各個(gè)檢索列表中統(tǒng)計(jì)該類別模型的數(shù)目和位置熵，兩者的乘積作為融合權(quán)值。最后基于融合權(quán)值計(jì)算模型之間的相似度，從而實(shí)現(xiàn)3D模型的檢索。

1.1 判斷查詢模型的最大相似類別

用Σ表示3D模型集合，其中已分類模型用C表示，未分類模型用U每個(gè)類的模型集合用表示，則有

應(yīng)用l種特征提取方法，3D模型庫(kù)轉(zhuǎn)化為相對(duì)應(yīng)的 l個(gè)特征空間上的特征集，表示為。給定一個(gè)查詢模型、一個(gè)常數(shù)k，在第j個(gè)特征集 Fj上計(jì)算C內(nèi)模型與查詢模型之間的相似度，生成一個(gè)相似度由大到小的結(jié)果排序列表，記為，記為中前k個(gè)模型組成的集合。

綜合各個(gè)特征集上檢索列表的前k項(xiàng)，得到模型集合 Rqk， Rqk計(jì)算式如下：

Rqk 中第 i類模型集合記為 Sqki，計(jì)算式如下：

模型 q的最大相似類別定義為 Rqk中模型數(shù)最多的類別，判定用公式如下：

1.2 計(jì)算最大相似類別模型的位置熵

在確定查詢模型q的類別 Class( q, k)后，統(tǒng)計(jì)各個(gè)特征集對(duì)應(yīng)的檢索列表前 k項(xiàng)中類別為Class( q, k)的模型在列表中的位置，第j個(gè)特征集對(duì)應(yīng)的檢索列表前k項(xiàng)中類別為 Class( q, k)的模型序號(hào)表示為。表示對(duì)應(yīng)于序號(hào)的模型，表示這一模型的類別。則在第j個(gè)特征集上最大相似類別模型的位置熵可以表示為下式：

其中：

1.3 計(jì)算融合權(quán)值

統(tǒng)計(jì)各個(gè)特征集對(duì)應(yīng)的檢索列表前k項(xiàng)中類別為 Class( q, k)的模型的個(gè)數(shù)，將第j個(gè)特征檢索列表中類別為 Class( q, k)的模型的個(gè)數(shù)表示為。針對(duì)查詢模型q，常數(shù)k，第j個(gè)特征集上的融合權(quán)值記為，考慮到 Class( q, k)模型數(shù)越大對(duì)應(yīng)的權(quán)值應(yīng)該越大，而位置熵越小對(duì)應(yīng)的權(quán)值應(yīng)該越大，計(jì)算式如下：

模型個(gè)數(shù)減1是為了除去檢索結(jié)果中與檢索模型相同的那個(gè)模型。如遇到(nj-1)都為0時(shí)，假定各特征集對(duì)融合所起的作用一樣，各融合權(quán)值都設(shè)為1。

1.4 計(jì)算模型之間的相似度令 dj表示應(yīng)用特征集時(shí)的距離函數(shù)，表示應(yīng)用時(shí)查詢模型q和模型庫(kù)中模型的最大距離，則融合后查詢模型q和模型庫(kù)中的模型o之間的相似性距離定義式如下：

2 特征提取算法

實(shí)驗(yàn)中用體素化球面調(diào)和函數(shù)方法、基于形狀分布的方法[8]和基于二維視圖的方法提取三維模型的特征。下面簡(jiǎn)單介紹一下這3種特征提取方法的實(shí)現(xiàn)。

基于體素化球面調(diào)和函數(shù)（voxelization Spherical harmonics，簡(jiǎn)稱為 VSH）的特征提取方法首先計(jì)算出以三維模型重心為球心的最小包圍球，假設(shè)半徑為，按照該球半徑的1 N為單位，將這個(gè)模型投射到2 N× 2 N× 2N個(gè)網(wǎng)格中，該網(wǎng)格重心放置和三維模型的重心重合。每個(gè)格子的數(shù)值非0即1，如果任何一個(gè)格子內(nèi)部存在著三維模型表面上的點(diǎn)，那么該格子的數(shù)值設(shè)為 1，反之，該格子的數(shù)值設(shè)為 0。之后將網(wǎng)格限制在一系列半徑為的球殼上，每個(gè)球殼對(duì)應(yīng)一個(gè)二值化的球坐標(biāo)方程。將每個(gè)方程展開形成球面調(diào)和函數(shù)的和，組合系數(shù)就形成一組具有旋轉(zhuǎn)不變性質(zhì)的特征向量。

基于形狀分布（Shape Distribution，簡(jiǎn)稱SD）的特征提取算法，其基本思想是統(tǒng)計(jì)模型表面上點(diǎn)分布的統(tǒng)計(jì)特征。多次隨機(jī)采樣三維模型表面上的點(diǎn)對(duì)，計(jì)算兩點(diǎn)間的距離，而后根據(jù)距離等分成多個(gè)區(qū)間，統(tǒng)計(jì)位于各個(gè)距離區(qū)間的兩點(diǎn)間距離的個(gè)數(shù)，得到統(tǒng)計(jì)直方圖，經(jīng)過歸一化等變換得到特征描述向量。

基于二維視圖（簡(jiǎn)稱 SIL）的特征提取方法[9]通過 CPCA方法計(jì)算三維模型的正交坐標(biāo)系；沿著3個(gè)正交坐標(biāo)軸方向得到三維模型的3個(gè)二維投影視圖；對(duì)二維投影圖像采用傅里葉變換方法提取特征，然后組合3個(gè)特征向量形成三維模型的特征描述。

3 實(shí)驗(yàn)與分析

3.1 實(shí)驗(yàn)數(shù)據(jù)

實(shí)驗(yàn)采用研究人員使用最為廣泛的普林斯頓形狀基準(zhǔn)數(shù)據(jù)庫(kù)PSB[9]。該數(shù)據(jù)庫(kù)共包含1814個(gè)模型，分訓(xùn)練集TR和測(cè)試集TS，各包括907個(gè)模型，訓(xùn)練集用來(lái)計(jì)算融合權(quán)值。在實(shí)驗(yàn)中，使用VSH方法提取的256維特征集、SD方法提取的64維特征集和SIL方法提取的300維特征集。

3.2 性能評(píng)價(jià)準(zhǔn)則

實(shí)驗(yàn)結(jié)果用查準(zhǔn)率-查全率曲線、平均查準(zhǔn)率、前 50%查全率上的平均查準(zhǔn)率、BEP、R-Precision、和最近鄰檢索精度來(lái)評(píng)價(jià)檢索性能[10]。其中查準(zhǔn)率-查全率曲線比較全面地描述了檢索性能，是較重要的一種性能評(píng)價(jià)標(biāo)準(zhǔn)。其他每種指標(biāo)各有側(cè)重點(diǎn)，一種指標(biāo)評(píng)價(jià)算法某一方面的優(yōu)劣，如最近鄰檢索精度表示當(dāng)返回檢索結(jié)果數(shù)為1時(shí)的正確率；R-Precision表示返回模型數(shù)為（ ni表示與查詢模型相關(guān)的模型數(shù)）時(shí)的查準(zhǔn)率；BEP表示返回模型數(shù)為時(shí)的查全率；平均查準(zhǔn)率是各種返回模型數(shù)上的查準(zhǔn)率的平均值，計(jì)算時(shí)取查全率為0.1，0.2，…，1時(shí)的查準(zhǔn)率的平均值；前50%查全率上的平均查準(zhǔn)率表示前 50%中各個(gè)返回模型數(shù)上的查準(zhǔn)率的平均值，即取查全率為0.1，0.2，…0.5時(shí)的查準(zhǔn)率的平均值。因?yàn)槟壳斑€沒有一種通用的評(píng)價(jià)指標(biāo)能完全表明檢索性能的好壞，本文使用多種指標(biāo)是為了全面地評(píng)價(jià)檢索性能。

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

3.3.1 k參數(shù)的取值

首先對(duì)不同k值對(duì)檢索性能的影響進(jìn)行了實(shí)驗(yàn)，圖1給出了不同k值對(duì)應(yīng)的平均查準(zhǔn)率。如圖1所示，k從1取到5過程中，平均查準(zhǔn)率逐漸遞增，k=5時(shí)取得了最好的平均查準(zhǔn)率，隨后k值在[6-15]之間平均查準(zhǔn)率變化不大，這說明了該算法對(duì)k參數(shù)變化具有較強(qiáng)的魯棒性。在后續(xù)的實(shí)驗(yàn)中選取k=5。

圖1 不同k值下的平均查準(zhǔn)率

3.3.2 融合實(shí)驗(yàn)

為了和其他融合方法進(jìn)行比較，我們還實(shí)現(xiàn)了基于純度的方法[6]、基于熵不純度的方法[5]、基于先驗(yàn)知識(shí)的方法[7]和靜態(tài)權(quán)值方法[4]?；陟o態(tài)權(quán)值的方法中，設(shè)定權(quán)值等級(jí)為0，1，2，3等4個(gè)等級(jí)，在訓(xùn)練集上找到最優(yōu)的權(quán)值參數(shù)組合為(3,1,0)，給出的性能是在這一參數(shù)組合下PSB中所有模型的平均檢索性能。圖2給出了各種融合方法在 SIL[300]+VSH[256]+SD[64]組合上的檢索結(jié)果和各單特征集對(duì)應(yīng)的檢索結(jié)果。圖注中按順序給出的值分別為：前 50%平均查準(zhǔn)率，平均查準(zhǔn)率，BEP，R-Precision指標(biāo)和最近鄰檢索精度。

如圖2所示，SD特征集檢索性能較差，為弱特征集，VSH特征集比SD特征集檢索性能好一些。融合方法的查準(zhǔn)率-查全率曲線和5個(gè)性能評(píng)價(jià)指標(biāo)都遠(yuǎn)遠(yuǎn)好于SD特征集和VSH特征集上的相應(yīng)指標(biāo)值，所以本文方法避免了在檢索過程中選擇最差特征集進(jìn)行檢索導(dǎo)致的風(fēng)險(xiǎn)問題。

圖2 各種融合方法在SIL[300]+VSH[256]+SD[64]組合上的檢索結(jié)果和各單特征集對(duì)應(yīng)的檢索結(jié)果

本文方法在查全率小于 0.6時(shí)的查準(zhǔn)率-查全率曲線在SIL方法的曲線上方，僅在查全率大于0.6時(shí)，SIL方法的查準(zhǔn)率-查全率曲線略位于上方。和最好單特征集相比，本文提出的方法將前 50%的平均查準(zhǔn)率提高 6.7%，平均查準(zhǔn)率提高3.3%，BEP提高0.7%，R-Precision指標(biāo)值提高4.6%，最近鄰檢索精度提高9.5%?？紤]到用戶重點(diǎn)關(guān)注的是位于檢索列表前面的模型，也就是說在查全率大到一定程度后的查準(zhǔn)率對(duì)用戶來(lái)說已經(jīng)沒有太大意義了。綜合起來(lái)考慮，本文方法優(yōu)于SIL方法。

基于純度、基于熵不純度和基于先驗(yàn)知識(shí)的3種方法僅在最近鄰檢索精度上略優(yōu)于最好特征集SIL，在其他4個(gè)指標(biāo)上都差一些。這是因?yàn)檫@幾種方法都是基于單個(gè)特征集檢索結(jié)果計(jì)算相應(yīng)的融合權(quán)值，而在多特征集中SD特征集檢索性能較差，單依靠特征集本身可能會(huì)使得計(jì)算出來(lái)的融合權(quán)值給出錯(cuò)誤的信息，從而導(dǎo)致檢索性能下降。本文方法的查準(zhǔn)率-查全率曲線位于基于純度的、基于熵不純度的和基于先驗(yàn)知識(shí)3種方法對(duì)應(yīng)的查準(zhǔn)率-查全率曲線上方，并且在題注中給出的5種性能評(píng)價(jià)指標(biāo)上也略優(yōu)一些。說明本文方法在有弱特征集存在的情況下優(yōu)于其他3種動(dòng)態(tài)融合方法。

基于靜態(tài)權(quán)值的方法的查準(zhǔn)率-查全率曲線在查全率大于0.6以后的查準(zhǔn)率-查全率曲線在本文方法的曲線上方，但在查全率小于0.6時(shí)，本文方法的查準(zhǔn)率-查全率曲線位于上方。從5個(gè)性能評(píng)價(jià)指標(biāo)上看本文方法好于基于靜態(tài)權(quán)值的方法。

靜態(tài)權(quán)值方法在前 4個(gè)性能指標(biāo)上優(yōu)于其他3種動(dòng)態(tài)融合方法，在最近鄰檢索精度這個(gè)指標(biāo)上比基于純度方法和基于先驗(yàn)知識(shí)的方法略差一些。靜態(tài)權(quán)值方法之所以取得和動(dòng)態(tài)融合檢索相似甚至更好的檢索性能，是因?yàn)榛陟o態(tài)權(quán)值的方法通過對(duì)弱特征集SD的權(quán)值賦值0，較弱的特征集 VSH的權(quán)值賦值 1，最好的特征集SIL的權(quán)值賦值3，既保持了SIL特征集在檢索過程中的主導(dǎo)地位，又利用VSH特征集對(duì)其進(jìn)行了補(bǔ)充，從而取得了在5個(gè)性能指標(biāo)上比最好單特征集SIL都要好的結(jié)果。

本文提出的多特征融合檢索方法從各個(gè)特征集上檢索結(jié)果的綜合情況考慮查詢模型的最大相似類別，避免了僅從單個(gè)特征集考慮造成的片面性。如果某一種特征集針對(duì)查詢模型q的檢索性能太差的話，則在計(jì)算權(quán)值時(shí)可能因?yàn)榱斜砬発項(xiàng)中不含與q同類的模型，從而使得計(jì)算的權(quán)值為0，即回避掉弱特征集。如果某一種特征集針對(duì)查詢模型q的檢索列表前k項(xiàng)中包含與q同類的模型的數(shù)目較少或位置較靠后，都會(huì)使計(jì)算的權(quán)值較小，從而只起到對(duì)其他特征集的補(bǔ)充作用。某一種特征集針對(duì)查詢模型q的檢索列表前k項(xiàng)中包含與q同類的模型的數(shù)目越多、位置越靠前，對(duì)應(yīng)的權(quán)值越大，對(duì)融合結(jié)果起的作用越大。本文方法就是通過這種針對(duì)查詢模型動(dòng)態(tài)計(jì)算融合權(quán)值的方法，取得了較好的檢索效果。

4 結(jié) 論

本文提出的多特征動(dòng)態(tài)融合檢索算法能夠針對(duì)查詢模型自動(dòng)計(jì)算融合權(quán)值，計(jì)算時(shí)利用最優(yōu)單特征集對(duì)模型類別判斷的主導(dǎo)作用，避免了單獨(dú)依靠特征集自身進(jìn)行模型類別判斷的片面性。實(shí)驗(yàn)結(jié)果表明在有弱特征集存在的情況下，本文算法避免了檢索過程中選擇最差特征集進(jìn)行檢索導(dǎo)致的風(fēng)險(xiǎn)問題，并在一定程度上有效提高了檢索效果。

[1] 呂天陽(yáng). 三維模型檢索中基于聚類與基于語(yǔ)義方法的研究[D]. 長(zhǎng)春: 吉林大學(xué), 2007.

[2] 劉玉杰, 李宗民, 李 華. 三維 U系統(tǒng)矩與三維模型檢索[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2006, 18(8): 1111-1116.

[3] Shih J L, Chen H Y. A 3D model trtrieval approach using the interior and exterior 3D shape information [J]. Multimedia tools and Application, 2009, 43(1): 45-62.

[4] Akbar S, Josef Kung , Wagner R. Multi-feature integration on 3D model similarity retrieval [C]//2006 1st International Conference on Digital Information Management. Bangalore, 2006: 151-156.

[5] Bustos B, Keim D, Saupe D, et al. Using entropy impurity for improved 3D object similarity search [C]// IEEE International Conference on Multimedia and Expo (ICME'04), 2004: 1303-1306.

[6] Bustos B, Keim D, Saupe D, et al. Automatic selection and combination of descriptors for effective 3D similarity search [C]//Proceedings of the IEEE Sixth International Symposium on Multimedia Software Engineering (ISMSE'04), 2004: 514-521.

[7] Leng Biao, Zheng Qin. Automatic combination of feature descriptors for Effective 3D shape retrieval[C]//ProceedingsinComputerVision/Compu-te r Graphics Collaboration Techniques. Rocquencourt, France, 2007.

[8] Robert Osada, Tom Funkhouser, Bernard Chazelle, et al. Matching 3D models with shape distributions [C]// International Conference on Shape Modeling and Applications, 2001.

[9] Philip Shilane, Patrick Min, Michael Kazhdan, et al. The princeton shape benchmark [C]//Shape Modeling International. Genova, Italy, 2004.

[10] Vranic D V. 3D model retrieval [D]. University of Leipzig. Germany, 2004.

3D Model Retrieval Based on Maximum Similar Category and Location Entropy

Chen Junying1, Meng Yuebo1, Wang Xianhui2, Liu Simei3
( 1. School of Information and Control Engineering, Xi'an University of Architecture and Technology, Xi'an shaanxi 710055, China; 2. School of Information Science and Engineering, Xinjiang University, Urumqi Xinjiang 830046, China; 3. China Unicom Xi'an Branch, Xi'an shaanxi 710043, China )

For using descriptive information of individual feature of 3D models effectively, the maximum similar category of the query model is determined by comprehensively analyzing the distribution of models in retrieved results based on various features. Then the location entropy of the same class models of individual feature is calculated respectively. Finally, combination weights are computed dynamically based on the number of models of the maximum similar category and location entropy. Compared with other dynamic and static combination methods on Princeton 3D benchmark models, the results show the proposed method is effective in the case of weak features included.

3D model retrieval; multi-features; dynamic combination

TP 391.3

A

2095-302X (2013)05-0051-05

2012-10-18；定稿日期：2012-12-14

陜西省自然科學(xué)基礎(chǔ)研究計(jì)劃資助項(xiàng)目（2012JQ8039）陜西省教育廳科研計(jì)劃資助項(xiàng)目（11JK1036）西安建筑科技大學(xué)青年基金資助項(xiàng)目（DA05037）

陳俊英（1980-），女，內(nèi)蒙古豐鎮(zhèn)人，講師，博士，主要研究方向?yàn)槟Ｊ阶R(shí)別、三維模型檢索等。E-mail：vcjy@163.com