多特征結合相似度優化的三維工程模型檢索算法

莊廷，張旭堂，侯珍秀

（哈爾濱工業大學機電工程學院，黑龍江哈爾濱150001）

多特征結合相似度優化的三維工程模型檢索算法

莊廷，張旭堂，侯珍秀

（哈爾濱工業大學機電工程學院，黑龍江哈爾濱150001）

為提高三維模型的檢索準確度，針對工程三角網格模型提出了一種基于隨機點間距離和法向夾角余弦聯合分布及二進制粒子群優化的檢索算法。在模型表面構造若干隨機點并計算各點之間的距離和法向夾角余弦，然后以距離和余弦為坐標軸建立距離－余弦二維網格，統計各網格中的隨機點數量，得到三維模型的距離?余弦聯合形狀分布矩陣，用分布矩陣之間的L2距離表示模型之間的相似度。為了體現形狀分布矩陣中各元素對模型相似度影響的差異性，采用一種基于二進制粒子群優化的方法對相似度計算過程進行了改進。實驗結果表明，本算法可有效提高工程三角網格模型檢索的準確性。

三維模型檢索；基于內容的檢索；多特征聯合；距離?余弦分布；相似度計算；二進制PSO優化

隨著三維模型在機械行業的廣泛使用，如何有效地重用三維模型逐漸引起了學術界和工業界的重視，作為模型重用首要環節的模型檢索問題更是成為研究熱點［1?3］，這也是本文的研究目的所在。三維模型檢索研究中，基于模型內容的檢索技術由于其良好的檢索性能受到了廣泛關注?；趦热莸臋z索算法分為3個步驟，首先對模型進行歸一化處理，消除模型外形大小和位姿對模型檢索造成的影響；然后自動計算并提取三維模型的特征，如形狀、空間關系等，建立三維模型的多維信息索引；最后以多維特征空間中特征向量之間的距離表示模型之間的相似度［4］。文獻［5］提出的基于形狀分布的三維模型檢索算法（D2）是基于內容的三維模型檢索領域的開創性算法。該算法首先在模型表面構造隨機點，然后計算任意2個隨機點之間的歐式距離，根據距離的分布情況構造距離分布直方圖。使用兩個直方圖之間的距離表示模型之間的相似度。D2算法無需歸一化處理，實現簡單、計算快捷。但由于僅使用隨機點之間的距離作為形狀特征，所以對模型的分辨能力有限，對復雜模型的檢索效果不佳。為了彌補D2算法的不足，有學者對其進行了改進［6?9］。這些改進算法通過改善D2的特征提取環節不同程度地提高了D2的檢索能力，但都忽視了對相似度計算環節的改善。為此，本文從以下兩方面入手提出了一種新的檢索算法：1）使用隨機點距離－弦聯合分布，通過多特征聯合增強算法檢索能力；2）以檢索結果最優為目標，采用二進制粒子群算法對距離?余弦聯合分布矩陣各行進行篩選，用選中的行進行相似度計算。

1 算法說明

1.1 基于距離－向夾角余弦分布的模型

1.1.1 距離與法向夾角余弦的計算

本文采用文獻［5］的隨機點構造方法，隨機點的法向與其對應的三角面片法向一致。圖1中的P1和P2表示2個隨機點，n1和n2為2個隨機點對應的法向，d表示P1和P2之間的歐式距離，α為n1和n2的夾角。

圖1 隨機點之間的距離與法向夾角示意圖Fig.1 The distance and included angle of two random points

1.1.2 距離?余弦二維分布矩陣

設隨機點間距離的最大值為dmax，平均值為davg。以距離作為橫軸，余弦作為縱軸，將（0，1）、（dmax，1）、（dmax，－1）和（0，－1）4個點確定的矩形區域劃分成一個m×n網格，用bij（i＝1，2，..，m；j＝1，2，..，n）表示單元網格。對距離進行平均值歸一化，將［0，davg］和［davg，dmax］分別等分為n／2個單元；余弦的值域為［－1，1］，等分為m個單元。如果隨機點之間的距離屬于橫軸單元j，夾角余弦屬于縱軸單元i，網格bij中的數字加1。當所有隨機點對統計完畢后，使用網格中的數字組成一個m×n矩陣，稱該矩陣為模型的距離?余弦分布矩陣（下文將其簡稱為DC分布）。表1為2個模型的D2分布和DC分布的比較，這2個模型外形迥異，但D2分布較為相似，DC分布則明顯不同。由此可見DC分布對模型的分辨能力強于D2。

表1 距離－余弦聯合形狀分布示例Table 1 Examples of distance?cosine distribution

1.2 基于二進制粒子群優化的相似度計算過程

1.2.1 相似度計算公式改進

得到模型的DC分布矩陣后，模型相似度計算問題轉化為分布矩陣之間的距離計算問題。本文使用DC矩陣之間的L2距離來表示模型之間的相似度。令A、B分別代表模型ma和mb的DC分布矩陣，aij和bij表示A、B的元素，模型ma和mb之間的相似度計算公式如下

為了消除分布矩陣中噪音數據對相似度計算帶來的影響，對式（1）進行了修改，加入系數向量X。X＝｛x1x2..xn｝′，其中xi等于1或0。式（2）為改進后的相似度計算公式。當xi＝0時，分布矩陣的第i行將不參與相似度計算。當X不全為1時，與式（1）相比，式（2）的計算結果將發生變化，即ma和mb的相似度發生變化。

如果使用ma表示檢索模型，mb表示模型庫中的模型。使用式（1）計算模型庫中所有模型與ma的相似度，按照與ma的相似度從小到大的順序對模型庫中的所有模型進行排序，排序結果稱為相似度排名（或者檢索結果）。當前通用的檢索算法性能評價指標均以相似度排名為依據對檢索算法的性能做出定量評價，相似度排名的評價越高說明檢索算法性能越強，反之則越差。由式（2）知，對同一個檢索模型，采用不同的X可產生不同的相似度排名，使用算法性能評價指標對這些排名進行分析，結果必然有優有劣。由此可知，X的變化可以影響到算法的檢索性能。對X的變化加以控制，保證其變化始終朝著相似度排名更優（算法性能評價更優）的方向進行，這就是本文相似度計算環節的優化思路。

1.2.2 二進制粒子群優化

粒子群優化算法（particle swarm optimization，PSO）是由Kennedy等提出的一種非線性優化算法［10］。PSO求解優化問題時首先隨機生成若干個粒子，每個粒子對應搜索空間中的一個解。粒子本身有2個屬性：位置和速度，還有一個由被優化函數決定的適應度，適應度描述了粒子對優化問題的優劣程度。粒子的初始狀態隨機確定后，算法進入迭代求解過程。在每一次迭代中，粒子通過跟蹤2個“極值”來更新自己的速度和位置信息：一個是該粒子當前的歷史最優解，稱為個體極值點（用gbest表示），另一個是整個種群的當前最優解，稱為全局極值點（用gbest表示）。每次迭代結束后，粒子根據適應度的大小更新自己的個體極值點gbest，并在所有的gbest中選出最優解作為種群的全局極值點gbest。迭代終止條件為預先確定的最大迭代次數或者為對優化結果的精度要求。為了解決組合優化問題，Kennedy等在PSO的基礎上提出了二進制離散版本的PSO算法［11］，其優化思想與PSO一致。二進制PSO算法在第k次迭代時，粒子Pm按照

更新自己的速度和位置信息。式中：vmn和xmn分別為粒子Pm在第k次迭代中第n維的速度和位置；pbestmn表示粒子Pm在第k次迭代后得到的個體極值點在第n維的位置，gbestn表示在第k次迭代后得到的全局極值點第n維的位置；w為慣性權值；c1和c2為學習因子；rand1、rand2以及是屬于（0，1）的隨機數；

1.2.3 粒子適應度函數

理論上講，所有相似度排名的評價指標均可作為粒子適應度函數。但是，由于在實際使用中只能將檢索結果中排在前幾位的模型返回給用戶（如前10個模型），所以在排名靠前的檢索結果中相關模型越多，排名越靠前，算法的實用性越強。為此，本文選用相似度排名評價指標First?Tier（下文用FT表示）［12］作為二進制PSO的適應度函數。FT指標的計算公式如下：

式中：C為檢索模型所在類的模型總數；R表示前C－1個檢索結果中相關模型的數量。根據式（5）可知，FT指標的計算需要用到檢索模型的類別信息，而在實際檢索過程中，用戶提交的檢索模型其類信息未知。為此，本文采用文獻［13］提出的預測相似類的概念。用M表示三維模型庫，M＝｛mi｜i＝1，2，…n｝，用Q表示檢索模型。使用式（3）計算mi與Q的相似度，稱Q的最相似模型所在的模型類為Q的預測相似類。

相似度計算過程優化以DC分布矩陣為輸入，通過多次迭代輸出使得FT指標最大的系數向量為X。優化過程朝著FT指標增長的方向進行，FT指標越高檢索結果越好。

1.3 算法整體流程

首先使用式（1）進行一次相似度計算，確定模型的預測相似類；然后，使用二進制PSO優化相似度計算過程，輸出使得FT取得最大值的系數向量X以及對應的檢索結果。檢索流程如下：

1）用戶提交檢索模型Q；

2）使用式（1）計算Q與模型庫中所有模型的相似度，確定Q的預測相似類，生成檢索結果；

3）對相似度計算過程進行二進制PSO優化，確定最優系數向量X以及優化后的檢索結果Re?trivel_Result；

4）返回Retrivel_Result的前K個模型。

2 算法時間復雜度分析

本節從DC分布矩陣構造、模型檢索和二進制PSO優化3個方面來分析整個算法的時間復雜度。

1）構造DC分布矩陣的時間復雜度

分布矩陣的構造由兩步完成：首先構造隨機點；然后計算隨機點之間的距離和法向夾角余弦，并進行統計。假設隨機點數量為n，那么構造DC分布矩陣的時間復雜度為O（n2）

2）模型相似度計算的時間復雜度

假設分布矩陣的規模為n×m，三維模型庫中的模型數量為k。模型相似度的時間復雜度為O（n×m×k）。

3）二進制PSO優化的時間復雜度

假設粒子數量為p，迭代次數為t，那么二進制PSO優化環節的時間復雜度為O（n×m×k×p×t）。

3 算法驗證

以VS2010為集成開發環境，結合MATLAB（R2011b）實現了本文提出的檢索算法。使用普渡大學建立的工程模型標準庫（engineering shape benchmark，ESB）［14］對算法進行了驗證。實驗采用PC機，CUP為E5400，主頻2.7 GHz，2 G內存。形狀描述階段生成1 024個隨機點，形狀分布矩陣規模為50×50；二進制PSO優化過程參數設置如下：學習因子w為1，粒子數量為50，迭代20次。檢索試驗過程中檢索模型已從模型庫中剔除。

本節共進行了兩類檢索實驗。第一類：使用式（1）計算模型對應的DC分布之間的距離，意在驗證本文提出的多特征聯合的檢索能力（下文用DC表示）；第二類：在DC分布的基礎上，加入二進制PSO優化，使用式（2）計算模型相似度，意在驗證優化環節的效果（下文用DC+PSO表示）。兩類檢索實驗的結果均與D2算法進行了對比，其中部分檢索實驗的結果如表2所示。表2顯示了部分檢索實驗的前9個相似模型的分布情況。3個檢索模型分別取自ESB庫的薄壁類、棱柱類和回轉類。

在薄壁類模型的檢索實驗中，D2檢索到3個相關模型，排名為①、③和④；DC檢索到5個相關模型，排名為①、②、③、④和⑤；而DC+PSO檢索到的相關模型為①、②、③、④、⑤、⑥和⑨。無論是從相關模型的數量還是排名來比較，DC+PSO的檢索結果在3種算法中最優，DC次之，D2最差。在棱柱類模型的檢索實驗中，D2檢索到的相關模型排在第①、②、⑧和⑨，DC為①、②、③、④和⑥，DC+PSO為①、②、③、④、⑤、⑦和⑧，同樣是DC+PSO最優，DC次之，D2排在第3位。在回轉類模型試驗中，D2檢索到的相關模型為①、②、③、⑤、⑥、⑧和⑨，DC為相關模型，但DC+PSO相關模型排名更高。

表2 距離－余弦聯合形狀分布示例Table 2 Examples of distance?cosine distribution

表3為D2、DC和DC+PSO關于薄壁類、棱柱類、回轉類以及ESB全庫的平均查準率對比。從表3的數據可以看到，DC+PSO檢索性能明顯優于D2和DC；DC在薄壁類和棱柱類上的檢索性能優于D2，在回轉類上略遜于D2。圖2為DC、DC+PSO與幾種典型檢索算法（D2［5］、光場描述子［15］、特征臨界點［16］以及測地連接圖［17］等）在ESB全庫上的平均查全率－查準率（Recall?Precision）曲線對比。從查全?查準曲線對比上來看，DC+PSO的檢索性能略優于光場算法，明顯優于其他幾種算法。

表3 D2、DC和DC+PSO 3種算法的平均查準率對比Table 3 Average precision of D2，DC and DC+PSO

本文采用FT（first?tier）、ST（second?tire）、NN（nearest neighbor）以及DCG（discounted cumulative gain）等4類指標［12］對3種算法（D2、DC和DC+ PSO）的檢索性能進行了評價，并統計了其在分布矩陣構造與模型檢索階段的時間消耗，具體內容如表4所示。表4中的數據顯示：DC算法的檢索性能全面優于D2，FT、ST和NN指標增幅明顯，說明多特征聯合有效提高了算法的檢索能力。與DC相比，DC+PSO的檢索性能進一步提高，FT指標增長到50%，優化效果明顯。但由于增加了優化環節，所以時間消耗有所增加。

圖2 球面沖擊波作用于剛性平板Fig.2 The spherical shock wave acting on a rigid plate

表4 算法性能的定量比較Table 4 Performance metrics comparison

4 結論

針對D2算法的不足，提出了基于隨機點距離－法向夾角余弦分布和二進制PSO優化的三維工程網格模型檢索算法。該算法通過統計隨機點之間的距離與法向夾角余弦構造距離?余弦二維聯合分布矩陣，以此矩陣對模型進行描述；在相似度計算環節，為了消除噪音數據對檢索帶來的影響，以檢索結果最優為目標，采用二進制粒子群優化對分布矩陣的行向量進行篩選，將相似度計算限制在保留下來的行向量之間。實驗結果表明本文算法可有效提高三維工程網格模型的檢索效率。

在本文中，預測相似類是二進制粒子群優化適應度函數的計算依據。簡言之，錯誤的預測相似類將導致優化過程失去意義，優化后檢索結果的優劣性不可知。所以提高預測相似類的準確度是后續研究的重點。

［1］YER N，JAYANTI K，LOU K Y，et al.Three dimensional shape searching：state?of?the?art review and future trends［J］.Computer?Aided Design，2005，37（5）：509?530.

［2］TANGELDER J W H，VELTKAMP R C.A survey of con?tent based 3D shape retrieval methods［J］.Multimedia Tools and Applications，2008，39（3）：441?471.

［3］JAYANTI S，KALYANARAMAN Y，RAMANI K.Shape?based clustering for 3D CAD objects：a comparative study of effectiveness［J］.Computer?Aided Design，2009，41（12）：999?1007.

［4］楊育濱，林暉，朱慶.基于內容的三維模型檢索綜述［J］.計算機學報，2004，27（10）：1297?1310.

YANG Yubin，LIN Hui，ZHU Qing.Content?based 3D model retrieval：a survey［J］.Chinese Journal of Comput?ers，2004，27（10）：1297?1310.

［5］OSADA R，FUNKHOUSER T，CHAZELLE B，et al.Shape distributions［J］.ACM Transactions on Graphics，2002，21（4）：807?832.

［6］IP C Y，LAPADAT D，SIEGER L，et al.Using shape distri?butions to compare solid models［C］／／Proceedings of the 7th ACM Symposium on Solid Modeling and Applications.New York，USA：ACM，2002：17?23.

［7］王洪申，張樹生，張開興，等.基于法向分類的三維模型形狀分布檢索算法［J］.計算機集成制造系統，2009，15（6）：1187?1193.

WANG Hongshen，ZHANG shusheng，ZHANG Kaixing，et al.Shape distributions retrieval algorithm of 3D CAD models based on normal direction［J］.Computer Integrated Manufac?turing System，2009，15（6）：1187?1193.

［8］DARAS P，AXENOPOULOS A，LITOS G.Investigating the effects of multiple factors towards more accurate 3?D object retrieval［J］.IEEE Transaction on Multimedia，2012，14（2）：374?388.

［9］王洪申，張樹生，白曉亮，等.三維CAD曲面模型距離?曲率形狀分布檢索算法［J］.計算機輔助設計與圖形學學報，2010，22（5）：762?770.

WANG Hongshen，ZHANG Shusheng，BAI Xiaoliang，et al.3D CAD surface model retrieval algorithm based on distance and curvature distributions［J］.Journal of Computer?Aided Design＆Computer Graphics，2010，22（5）：762?770.

［10］KENNEDY J，EBERBART R C.Particle swarm optimiza?tion［C］／／Proceedings of IEEE International Conference on Neural Networks.（s.l.）：IEEE Press，1995：1942?1948.

［11］KENNEDY J，EBERBART R C.A discrete binary version of the particle swarm algorithm［C］／／Proceedings of the 1997 IEEE International conference on Systems，Man，and Cybernetics.（s.l.）：IEEE Press，1997：4104?4108.

［12］SHILANE P，MIN P，KAZHDAN M，et al.The Princeton shape benchmark［C］／／Proceedings of Shape Modeling International SMI 2004.Genove，Italy，2004：167?178.

［13］LI B，JOHAN H.3D model retrieval using hybrid features and class information［J］.Multimedia Tools and Applica?tions，2013，62（3）：821?846.

［14］JAYANTI S，KALYANARAMAN Y，IYER N，et al.De?veloping an engineering shape benchmark for CAD models［J］.Computer?Aided Design，2006，38（9）：939?953.

［15］CHEN D Y，OUHYOUNG M.On visual similarity based 3D model retrieval［J］.Computer Graphics Forum，2003，22（3）：223?232.

［16］侯鑫，張旭堂，金天國，等.基于網格臨界點的三維工程模型檢索算法［J］.計算機集成制造系統，2009，15（1）：72?81.

HOU Xin，ZHANG Xutang，JIN Tianguo，et al.3D engi?neering models retrieval algorithm based on mesh salient critical［J］.Computer Integrated Manufacturing System，2009，22（3）：223?232.

［17］張旭堂，陳曉峰，蔣立軍，等.基于局部特征提取的棱柱類零件三維模型檢索［J］.計算機集成制造系統，2012，18（3）：458?465.

ZHANG Xutang，CHEN Xiaofeng，JIANG Lijun，et al.Prismatic parts 3D model retrieval based on local shape factures extraction［J］.Computer Integrated Manufacturing System，2012，18（3）：458?465.

3D engineering model retrieval algorithm based on multiple features and similarity calculation optimization

ZHUANG Ting，ZHANG Xutang，HOU Zhenxiu
（School of Mechanical Engineering，Harbin Institute of Technology，Harbin 150001，China）

This paper proposes a retrieval algorithm based on the binary particle swarm optimization（PSO）and the joint distribution including the distance between every two random points and the normal included angle cosine in or?der to improve the retrieval accuracy of 3D engineering triangular mesh model.Firstly，numerous sample points on the surface of the model are randomly chosen.Next，the distances and the cosine values of the normal angles among the sample points are calculated.Finally，a two?dimensional grid with the distance and the cosine value as the coordinate axes is established.The joint distance?cosine shape distribution matrix of the 3D model is constructed through the sta?tistic data of sample points acquired in each mesh，using the distance L2between distribution matrixes to represent similarity between models.In order to demonstrate the different influence of shape distribution elements on the simi?larity in 3D models efficiently，binary PSO is employed to ameliorate the similarity computing process.Experimental results showed that the approach could improve the retrieval accuracy of engineering mesh models effectively.

3D model retrieval；content?based retrieval；multi?feature；distance?cosine distribution；similarity cal?culation；binary PSO

10.3969／j.issn.1006?7043.201312089

http：／／www.cnki.net／kcms／detail／23.1390.U.20150414.1613.010.html

TP391

A

1006?7043（2015）05?0720?05

2013?12?26.網絡出版時間：2015?04?14.

國家自然科學基金資助項目（51001121）.

莊廷（1982?），男，博士研究生；

侯珍秀（1958?），女，教授，博士生導師.

莊廷，E?mail：zt_hit＠126.com.