權重自適應的多特征組合三維工程模型檢索算法

劉 研，張吉慶，張旭堂

（1.哈爾濱工業大學 理學院，黑龍江 哈爾濱150001；2.中國國際工程咨詢公司，北京100048；3.哈爾濱工業大學 機電學院，黑龍江 哈爾濱150001）

0 引 言

合理地重用三維模型有助于企業提高新產品開發速度，提升競爭力［1］，因此設計人員迫切需要一種有效的三維模型檢索方法，快速、準確地從模型庫中找到與檢索模型相似的三維模型。基于文本關鍵字的檢索方法被最先用來查找相似模型。這種方法通過在模型標注信息和用戶輸入的關鍵字之間進行匹配來實現檢索，這種方法存在以下幾方面缺陷：①有限的人力無法做到對所有模型進行標注；②不同的人對同一模型的標注可能是不同的，模型的標注信息隨著時間的推移可能發生變化；③關鍵字不準確時無法檢索到相似模型。隨著研究的深入，基于文本關鍵字的檢索方法被基于模型內容特征的檢索方法淘汰。基于內容的檢索方法核心思想是通過三維模型的內容特征來表征三維模型，將三維模型轉化為特征空間中的特征向量，通過計算特征向量之間的距離來判斷對應模型之間的相似度。基于內容的檢索利用模型自身攜帶的信息，檢索性能優于文本關鍵字方式，逐漸成為模型檢索問題的研究重點［2－7］。Osada等［8］提出了一種適合任意三維模型的形狀描述計算方法。該方法通過采樣確定某種形狀函數在模型上的分布情況，通過形狀分布對模型進行描述。Osada提出了5種形狀函數，如圖1所示，實驗顯示在5種形狀函數中，D2的檢索效果最好。

圖1 Osada提出的5種形狀函數［9］

蔣立軍等［9］提出一種基于網格模型面積分布的檢索算法。該算法通過對網格模型各頂點進行分析建立模型的面積分布序列。為了實現相似度計算對面積分布序列的歸一化操作和傅立葉變換，兩個模型之間的相似度等于兩個分布序列的L2距離。

侯鑫等［10］提出了一種與計算機輔助設計系統無關的基于網格特征臨界點的三維工程模型檢索算法。該算法根據Morse理論，采用網格頂點處的離散平均曲率作為光滑實值函數，計算網格特征臨界點，采用兩臨界點之間的測地線距離和頂點法矢夾角余弦值作為聯合形狀函數，按照極大值點和鞍點，分別計算同類臨界點間的聯合形狀函數得到形狀分布，從而將模型的比較映射為形狀分布矩陣的比較。通過在ESB庫上的驗證，算法明顯提高了基于圖形分布檢索算法的有效性。

基于內容的檢索算法在檢索性能上有較大提升，但是也存在一些問題：①單一特征對模型的描述能力有限。文獻 ［11］的實驗結果表明，不同的特征具有各自的優缺點，不存在適用于所有模型的特征。所以，使用單一特征很難在所有模型類別中取得滿意的檢索效果；② “語義鴻溝”問題［12］。人對模型相似性的判斷除了模型內容，還結合了模型視覺特征和語義信息，并以語義信息為重。基于特征的檢索算法完全依賴模型底層特征來計算模型的相似性，并未考慮到模型的語義信息，而模型的底層特征和語義之間不存在直接關系，所以模型內容的相似不代表語義的相似。為了解決“語義鴻溝”問題，有些研究人員將相關反饋技術應用到了三維模型檢索問題上［13］。在用戶的反饋信息的幫助下，檢索算法可以更加準確地捕捉到用戶的檢索意圖。

本文提出三維工程模型檢索算法針對上述兩方面缺陷做出了如下改進：①通過多個內容特征的組合增強算法的檢索能力；②根據用戶的反饋信息獲取用戶的檢索需求，通過粒子群算法優化動態選擇每個特征算子在相似性計算過程中的權重，使得檢索結果更加靠近用戶的檢索需求，在一定程度上縮小高層語義與模型底層特征信息之間的差距。

1 算法說明

1.1 相似度計算

用Q 表示檢索模型，用Oi表示模型庫中的任意一個模型。用F 來表示選用的特征算子集合，單個特征算子fi用表示，S（Ofii）表示在使用fi的情況下，Oi和Q 之間的相似度。其中wi表示特征算子fi對應的權重。用S（Oi）表示Oi和Q 之間的綜合相似距離，S（Oi）是由S（Ofii）線性組合得到的，S（Oi）的計算公式見式 （1）S（Oi）越小說明Oi和Q 越 相 似

1.2 特征算子權重動態更新

1.2.1 粒子群算優化法

粒子群優化算法 （particle swarm optimization，PSO）源于對鳥群捕食行為的研究，是近年來發展起來的一種進化算法［14］。PSO 求解優化問題時首先隨機生成若干個粒子（particle），每個粒子對應搜索空間中的一個解。每個粒子具備位置和速度兩個屬性，由適應度函數決定粒子對待優化問題的優劣程度。粒子的初始狀態隨機確定后，算法進入迭代求解過程。在迭代過程中，粒子利用兩個極值來更新自己，一個稱為pbest（當前粒子在進化過程中出現的最優位置），一個稱為gbest （整個種群在進化過程中出現的最優位置）。式 （2）、式 （3）為粒子的速度與位置更新公式。迭代終止條件為預先確定的最大迭代次數或者為對優化結果的精度要求。假設粒子在D 維空間搜索問題最優解，第i個粒子的位置信息可表示為：Xi＝（xi1，xi2，…，xiD），速度信息 可 表 示 為：Vi＝（Vi1，Vi2，…，ViD）。式 （2）和 式（3）為PSO 在第t＋1次迭代時的粒子速度和位置更新公式，式 （2）中的pbesti表示第i個粒子在第t 次迭代時的個體極值點，gbest表示粒子種群當前的全局極值點，w 為慣性權重，c1和c2為學習因子，r1和r2為0到1之間的隨機數。式 （4）為PSO 的適應度函數，適應度函數以粒子的位置信息為輸入，fitnessi表示第i 個粒子對待優化問題的優劣程度。每個粒子完成一次迭代后根據適應度大小更新自己的局部極值點 （pbest），粒子種群完成一次迭代后根據適應度大小更新全局極值點 （gbest）

1.2.2 權重優化過程

初次檢索結束后，將每個特征算子前K 個檢索結果返回給用戶供其標記，所以供用戶標記的模型總數為×K 個。用戶可將返回的模型標記為 “相關”、 “不相關”和“一般”3類。用R （relevant）來表示被用戶標記為 “相關”的模型集合，用R（Ofii）來表示特征算子fi的前K 個相似模型中屬于被標記為“相似”的模型；用IR （irrelevant）來表示被標記為“不相關”的模型集合，用IR（Ofii）表示不相關模型中被fi檢索到的模型；用M （middle）來表示被標記為“一般”的模型集合，用M（Ofii）表示 “一般”模型中被fi檢索到的模型。以上信息確認完畢后，使用粒子群算法優化fi的權重，權重優化過程中循序以下幾條規則：

R（Qfii）中的模型個數越多fi的權重越大；

IR（Qfii）中的模型個數越多fi的權重越小；

如果特征算子的相關模型個數一樣多，則考察其相關模型的排名之和，和越小fi的權重越大。

根據上述幾條原則構建粒子適應度計算公式，見式（5）。其中Fitness（pi）表示粒子第i個粒子的適應度，其值越大表明粒子狀態越優化

1.3 算法流程

權重更新完畢后，使用式 （1）重新計算模型Oi和Q之間的綜合相似度。算法將按照綜合相似度對模型庫中的模型進行排序，并返回前F ×K 個模型供用戶標注，用戶標記完畢后開始下一輪權重優化，照此循環直至用戶主動結束檢索過程。算法流程如下文所述，流程如圖2所示。

（1）初始化所有特征算子的權重；

（2）分別使用各個特征算子計算相似度R（Ofii）；

（4）用戶對模型進行相關性標注；

（5）PSO 更新所有特征描算子的權重；

（6）按照式 （1）計算綜合相似度S（Oi）；

（7）根據S（Oi）對數據庫中的所有模型排序，返回前×K 個模型供用戶標注；

（8）如果用戶對結果滿意，結束；否則返回第（4）步，開始下一輪反饋。

圖2 基于相關反饋的多特征融合算法流程

2 實驗討論

以Visual C＋＋6.0 為集成開發環境，結合Matlab R2011b實現了本文提出的算法。在實驗環節實現的算法聯合了上文中介紹的3種特征算子，分別是：D2［8］，臨界特征點［10］和測地線連接圖［15］。PSO 的參數選擇如下：粒子 規模50，慣性權重w＝1，學習因子c1＝c2＝1，迭代50次。使用普渡大學建立的工程標準模型庫ESB （engineering shape benchmark）對本文算法進行了驗證。ESB 庫中包含866個模型，被分為3個大類，45個小類［16］。表1為部分檢索實驗的前10個檢索結果，3個檢索模型分別來自ESB庫的3個大類，表格中圖片下方文字為模型名稱。

表1 部分檢索實驗結果

圖3為參與組合的3種檢索算法以及本文算法在ESB庫上的平均查全率－查準率曲線。由圖3可知，本文算法的PR 曲線優于參與的組合的3種檢索算法。

圖3 查全率－查準率曲線

3 結束語

針對三維模型檢索領域存在的 “語義鴻溝”和單特征檢索能力有限的問題，提出一種基于相關反饋和多特征組合的三維工程網格模型檢索算法。該算法以網格模型為對象，通過多特征聯合增強算法的檢索能力；在用戶相關反饋信息的指導下使用PSO 算法動態更新各特征算子在相似度計算過程中的權重，提高了檢索結果的語義相關性。實驗結果表明，本文提出的算法可有效提高檢索效率。

在未來的研究中可從以下幾方面對算法進行改進：①選取更優的特征算子參與組合以便提高組合算法的檢索能力；②改善粒子群算法適應度函數，更加合理的適應度函數有助于找到更能體現用戶檢索意圖的權重分配方案。

［1］ZHANG Kaixing，ZHANG Shusheng，WANG Hongshen，et al.Content－based 3Dmodel retrieval and its application to CAD／CAM［J］.Mechanical Science and Technology for Aerospace Engineering，2009，28 （7）：847－850（in Chinese）.［張開興，張樹生，王洪申，等.基于內容的3D 模型檢索及其在CAD／CAM 中的應用［J］.機械科學與技術，2009，28 （7）：847－850.］

［2］Takahiko F，Ryutarou O.Dense sampling and fast encoding for 3dmodel retrieval using bag－of－visual features［C］／／Proceeding of the ACM International Conference on Image and Video Retrieval，2009：192－199.

［3］Apostolos A，Georgios L，Petros D.3D model retrieval using accurate pose estimation and view－based similarity ［C］／／Proceeding of The 1st ACM International Conference Multimedia Retrieval，2011：17－20.

［4］Yi Y，Nie F P，Xu D，et al.A multimedia retrieval framework based on semi－supervised ranking and relevance feedback［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34 （4）：723－742.

［5］Li J B，Sun W H，Tang L L.3Dmodel classification based on nonparametric discriminate analysis with kernels ［J］.Neural Computing and Applications，2013，22 （3－4）：771－781.

［6］Tangelder J W H，Veltkamp R C.A survey of content based 3Dshape retrieval methods［J］.Multimed Tools Appl，2008，39 （3）：441－471.

［7］Jayanti S，Kalyanaraman Y，Ramani K.Shape－based clustering for 3DCAD objects：A comparative study of effectiveness［J］.Computer－Aided Design，2009，41 （12）：999－1007.

［8］WANG Hongshen，ZHANG Shusheng，BAI Xiaoliang，et al.3DCAD surface model retrieval algorithm based on distance and curvature distributions［J］.Journal of Computer－Aided Design＆Computer Graphics，2010，22 （5）：762－770 （in Chinese）.［王洪申，張樹生，白曉亮，等.三維CAD 曲面模型距離－曲率形狀分布檢索算法 ［J］.計算機輔助設計與圖形學學報，2012，22 （5）：762－770.］

［9］JIANG Lijun，ZHANG Xutang，ZHANG Guangyu.3Dmodel retrieval method based on area distributions［J］.Computer Engineering and Applications，2012，48 （12）：6－13（in Chinese）.［蔣立軍，張旭堂，張廣玉.基于面積分布算子的三維模型檢索算法［J］.計算機工程與應用，2012，48 （12）：6－13.］

［10］HOU Xin，ZHANG Xutang，JIN Tianguo，et al.3Dengineering models retrieval algorithm based on mesh salient critical［J］.Computer Integrated Manufacturing System，2009，15 （1）：72－81 （in Chinese）.［侯鑫，張旭堂，金天國，等.基于網格臨界點的三維工程模型檢索算法 ［J］.計算機集成制造系統，2009，15 （1）：72－81.］

［11］Leng B.A powerful relevance feedback mechanism for content－based 3D model retrieval ［J］.Multimed Tools Appl，2008，40 （1）：135－150.

［12］Havemann S，Fellner D.Seven research challenges of generalized 3Ddocuments［J］.IEEE Computer Graphics and Applications，2007，27 （3）：70－76.

［13］Yang Yi，Nie Feiping，Xu dong，et al.A multimedia retrieval framework based on semi－supervised ranking and relevance feedback ［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2012，34 （4）：723－742.

［14］Hu B K，Liu Y S，Gao S M.Parallel relevance feedback for 3D model retrieval based on fast weighted－center particle swarm optimization ［J］.Pattern Recognition，2010，43（8）：2950－2961.

［15］Zhang X T，Chen X F，Yang P Y，et al.Geodesic connected Graph representation of 3Dprismatic CAD models［C］／／Proceeding of International Conference on Digital Manufacturing and Automation，2010：776－779.

［16］Li B，Johan H.3D model retrieval using hybrid features and class information ［J］.Multimedia Tools and Applications，2013，62 （3）：1－26.