基于模擬退火算法的模型檢索

高雪瑤 譚濤 張春祥

摘?要：為了從模型庫中檢索到最相似的CAD（Computer-Aided?Design）模型，采用模擬退火算法檢索相似模型。利用源模型面與目標模型面之間的邊數差異，來構造兩個模型之間的面相似度矩陣。利用模擬退火算法對面相似度矩陣進行搜索，得到兩個模型之間的最優面匹配序列。以最優面匹配序列為基礎，來計算源模型與目標模型之間的相似性。實驗結果表明：該方法能夠準確地度量兩個模型之間的差異。

關鍵詞：模擬退火算法;邊數;面相似度;面匹配序列

DOI：10.15938/j.jhust.2020.03.023

中圖分類號：?TP391.7

文獻標志碼：?A

文章編號：?1007-2683（2020）03-0151-06

Abstract：In?order?to?retrieve?the?most?similar?CAD（Computer?Aided?Design）?model?from?model?library，?simulated?annealing?algorithm?is?used?to?retrieve?similar?models.?The?difference?of?edge?number?between?source?model?face?and?target?model?face?is?used?to?construct?face?similarity?matrix?of?two?models.?Simulated?annealing?algorithm?is?used?to?search?face?similarity?matrix?in?order?to?find?an?optimal?matching?sequence?of?faces?between?two?models.?Based?on?this?optimal?matching?sequence?of?faces，?the?similarity?between?source?model?and?target?one?is?calculated.?Experimental?results?show?that?this?method?can?measure?the?difference?of?two?models?accurately.

Keywords：simulated?annealing?algorithm;?edge?number;?face?similarity;?matching?sequence?of?faces

0?引?言

隨著CAD技術的快速發展，已經積累了大量的CAD設計模型。如果能充分地利用現有的CAD模型庫，必將大大地提高設計效率，節約設計成本。目前，國內外學者越來越關注三維CAD模型檢索這一課題。

有效特征描述符[1-2]的提取是保證檢索準確性的前提，多特征結合[3]的特征提取方式可更好評價模型之間的差異。白靜[4]以三維CAD模型的邊界表示為輸入，利用非精確的樹匹配算法和自適應權重分配方案來評價兩個模型之間的相似性，提出基于擴展特征樹的三維CAD模型相似性評價。很多研究者直接將三維模型轉換成二維圖形[5-8]，來提取模型的邊、面信息并描述模型的特征[9]。王衛兵等[10]以隨機采樣一致性算法和優化加速魯棒特征為基礎提出了一種適應性強的優化匹配算法，以解決圖像匹配過程中匹配時間長和匹配正確率低的問題。劉露等[11]使用優化的視覺顯著模型對圖像進行快速識別，初始化前景區與背景區的高斯混合模型，分割顯著圖，提出了一種基于視覺顯著模型的圖像分割算法。三維模型圖片的質量對模型檢索準確性有很大影響。陳莉等[12]構建相關領域的本體，對已有實例進行分析，找出模型本體間具有的相關屬性。對此，張猛等[13]將連續曲面上的形狀直徑函數推廣到離散點集，將錐體內部空間離散化，采用OBB樹批量處理點云數據。同時，給出了點云的形狀直徑計算方法。黃瑞等[14]以特征實例關聯工藝為參考，建立了基于中軸轉換的特征相似性評價模型。同時，給出了一種基于子圖同構的相似局部結構提取算法。Chen等[15]以樣本模型作為對齊目標，將所有三維模型依次排列，提出了一種基于樣本對齊的模型檢索方法。Tao等[16]將數據模型的面鄰接圖分割為凸、凹和平面區域，利用區域圖來表示。利用最優過程進行遞歸組合，以形成關于目標函數的最佳區域子圖。同時，引入區域屬性代碼來表示CAD模型的面區域。Wang等[17]利用一種優化算法來比較三維模型面。同時，對比中立點的形狀特征來計算兩個三維模型之間的相似性。

利用模型幾何特征[18-19]，全面考慮全局特征與局部特征，張勇等[20]提取了必要的拓撲屬性。本項目利用模型面的邊數差異，來構建源模型與目標模型之間的面相似度矩陣。以面相似度矩陣為基礎，使用模擬退火算法來搜索源模型與目標模型之間的最優面匹配序列。以此為基礎，來計算源模型和目標模型之間的相似性。

1?模型相似性計算

三維CAD模型是由多個面組成的。面的形狀差異造成了模型之間的千差萬別。為了計算兩個模型之間的相似性，需要度量這兩個模型面之間的形狀差異。面是由邊圍成的。兩個邊數不同的面，其形狀一定是不一樣的。本文利用邊數差異來度量兩個面之間的形狀相似度。如果兩個模型面的組成邊數差異越小，那么這兩個面的形狀就越相似。如果兩個模型面之間的組成邊數差異越大，那么這兩個面之間的形狀差異就越大。綜合兩個模型面之間的相似度來度量這兩個模型之間的差異。本文以源模型U和目標模型V來說明模型之間相似性的計算過程。

源模型U如圖1所示，包括5個面u1、u2、u3、u4、u5。其中，u1、u2為模型U的兩個底面，u3、u4、u5為模型U的3個側面。由圖1可以看出：面u1與面u3、u4、u53個面鄰接，即面u1的邊數為3。面u3與面u1、u2、u4、u5四個面相鄰，因此，面u3的邊數為4。同理，可以得出面u2有3條邊，面u4、u5有4條邊。目標模型V與源模型U相同，如圖2所示。

此處，使用ui來表示源模型U的面序號，利用vj來表示目標模型V的面序號。源模型U和目標模型V之間的面相似度計算方法如式（1）所示。

其中：N（f）表示模型面f的組成邊數;max（x，y）表示取x與y之間的最大值;S（ui，vj）表示源模型面ui與目標模型面vj之間的面相似度值。

根據式（1）來計算源模型U與目標模型V各面之間的相似度數值。如果面ui和面vj所含的邊數差別越小，那么這兩個面之間的相似度就會越高，S（ui，vj）的值就越大。相反，如果面ui和面vj所含邊數差別越大，那么這兩個面之間的相似度就會越低，S（ui，vj）的值也就越小。以面相似度值為基礎，來構造源模型U與目標模型V之間的面相似度矩陣SUV，如下所示。

使用m表示源模型U的面數，n表示目標模型V的面數。其中，使用源模型U的面序號u1、…、um來表示面相似度矩陣SUV的行標，利用目標模型V的面序號v1、…、vn來表示面相似度矩陣SUV的列標。為了便于對面相似度矩陣SUV進行搜索，始終保持SUV的行數要小于等于列數。如果m大于n，則將源模型U與目標模型V互換。圖1和圖2兩個模型的面相似度矩陣如下所示。

在源模型U中，源模型面u1的邊數為3，目標模型面v1的邊數也為3。由式（1）可知：面相似度矩陣SUV的第u1行第v1列的值為1。源模型面u3的邊數為4，目標模型面v2的邊數為3。由式（1）可知：面相似度矩陣SUV的第u1行第v6列的值為0.75。依次可以得出面相似度矩陣SUV其它元素的數值。

2?基于模擬退火算法的面匹配

使用模擬退火算法來搜索源模型U與目標模型V之間的面相似度矩陣SUV，來獲取二者之間的最優面匹配序列。根據所獲得的序列，從面相似度矩陣SUV中提取所對應的面相似度數值。通過累積面相似度數值，得到源模型U和目標模型V之間的整體相似性。

此處，面匹配序列被視為解向量。設所搜索到的解向量為X=（（1，?j（1）），?（2，?j（2）），…，?（m，?j（m）））。其中，j（i）表示與源模型面ui所匹配的目標模型面編號（i=1，?2，?…，?m）。在搜索面相似度矩陣SUV的過程中，根據模擬退火算法的特性，逐漸降溫并計算每次降溫后的解向量X的適應度值。使用式（2）來計算X的當前適應度數值F（X）。

在溫度T時，執行Markov過程，其方法如下所示。采用隨機移位方法產生新解，對解向量中的每一個元素（i，?j（i））使用rand函數產生一個[0，?1]之間的隨機數r。利用式（3）決定j（i）的移動，設步長為1。

式中：jlT（i）表示在溫度T時，第l次迭代所搜索到的源模型面ui所匹配的目標模型面序號。經過變換之后，產生新解jl+1T（i）。當r<1/3時，源模型面ui所匹配的目標模型面序號減1。當r>2/3時，源模型面ui所匹配的目標模型面序號加1。當r為其它數值時，源模型面ui所匹配的目標模型面序號保持不變。產生新解的次數為Markov鏈的長度L。

使用Metropolis準則來判斷是否接受新解Xnew，還是保留原始解Xold。Xold為上一次所搜索到的面匹配序列，Xnew為當前搜索到的面匹配序列，即：

將搜索到的面匹配序列Xold和Xnew代入式（2）計算出對應的相似度數值F（Xold）和F（Xnew）使用Metropolis準則進行判斷。Metropolis準則如式（4）所示：

模擬退火過程采用式（5）來完成。其中，Q為退火參數。

基于模擬退火算法的面匹配過程如下所示：

1）根據式（1），構造源模型U和目標模型V之間的面相似度矩陣SUV。

2）設定初始溫度T0=100，最大迭代次數Maxk=100，當前溫度迭代次數l，以及Markov鏈長度L=20，降溫參數Q=0.95，隨機產生初始解X0，Xold=X0，溫控參數k=0。

3）采用式（3）在Xold附近搜索得到新解Xnew。

4）分別計算Xold和Xnew的適應度函數值F（Xold）和F（Xnew）。若F（Xold）

5）若F（Xold）≥F（Xnew），則計算△F=?F（Xold）-F（Xnew）。若exp（-△F/Tk）>ε，ε為（0，1）之間的隨機數，則Xold=Xnew，否則保留原解Xold。

6）在當前溫度Tk下，重復執行3）～5）L次。

7）降溫Tk+1=QTk。

8）k是否大于Maxk，若滿足則輸出最優解，否則重復執行3）～7）。

在源模型和目標模型的面相似度矩陣中，利用模擬退火算法來搜索這兩個模型之間的最優面匹配序列。所得到的最優面匹配序列為（（1，?j（1）），?（2，?j（2）），…，?（m，?j（m）））。根據面匹配對（i，?j（i）），從面相似度矩陣SUV中取出對應的面相似度數值S（i，?j（i））。其中，i=1，?2，…，?m。通過累積面相似度數值S（1，?j（1）），?S（2，?j（2）），…，?S（m，?j（m））來計算兩個模型之間的整體相似性。其計算過程如式（6）所示：

其中：min表示m與n中的最小值;（i，?j（i））表示最優面匹配序列中的第i個面匹配對。

3?實?驗

本文使用Matlab編寫算法，實現對面相似度矩陣SUV的搜索。在實驗中，目標模型為一個五棱錐，如圖3所示。一共有6個面，面v1與面v2、v5、v6相鄰接，面v2與面v1、v3、v6相鄰接，面v3與面v2、v4、v6相鄰接，面v4與面v3、v5、v6相鄰接，面v5與面v1、v4、v6相鄰接，面v6與面v1、v2、v3、v4、v5相鄰接。由此可知：面v1、v2、v3、v4、v5的邊數都為3，面v6的邊數為5。

選取如圖4所示的6個CAD模型為源模型。源模型A為五棱錐，源模型B為四棱錐，源模型C為三棱柱，源模型D為在三棱柱側面開了一個長方體的通槽，源模型E為在長方體上部開了一個長方體的通槽，源模型F為在圓柱底座上疊加一個圓柱。

源模型A共有6個面。面u1、u2、u3、u4、u5都為三角形，邊數都為3。面u6為五邊形，邊數為5。以源模型A為例，使用式（1）來計算源模型A與目標模型之間的面相似度，并構造這兩個模型之間的面相似度矩陣，如下所示。

在源模型A中，面u1與面u2、u5、u6相鄰接。在目標模型中，面v1與面v2、v5、v6相鄰接。由式（1）可知：面相似度矩陣的第u1行第v1列的值為1。在源模型A中，面u1與面v2、v5、v6相鄰接。在目標模型中，面v6與面v1、v2、v3、v4、v5相鄰接。由式（1）可知：面相似度矩陣的第u1行第v6列的值為0.6。

以源模型A與目標模型的面相似度矩陣為基礎，使用模擬退火算法來搜索二者之間的最優面匹配序列。得到的一組最優面匹配序列為（1，2）、（2，1）、（3，4）、（4，5）、（5，3）、（6，6）。以該序列為基礎，使用式（6）來計算這兩個模型之間的相似性，其數值為1。

為了驗證所提出方法的有效性，共進行了兩組對比實驗。在實驗中，利用式（1）來構造源模型與目標模型的面相似度矩陣。然后，分別使用貪心算法和模擬退火算法來搜索面相似度矩陣來獲得這兩個模型之間的最優面匹配序列。以最優面匹配序列為基礎，從面相似度矩陣中提取源模型面與目標模型面之間的面相似度。同時，使用式（6）來分別計算這兩個模型之間的相似性，其結果如表1所示。

從形狀上看，源模型A與目標模型完全一致。由表1可知：貪心算法和模擬退火算法得到的模型相似性數值都為1。對于源模型B而言，貪心算法和模擬退火算法計算出的模型相似性數值也都相同。模型C和D是兩個關鍵模型。相對于模型D而言，模型C的形狀要更接近于目標模型。在使用模擬退火算法時，模型C的相似性數值要高于模型D的相似性數值。在使用貪心算法時，模型D的相似性數值要高于模型C的相似性數值。模擬退火算法能夠更準確地尋找源模型與目標模型之間的最優面匹配序列。由此可知：相對于貪心算法而言，本文所提出的方法能更有效地判別兩個模型之間的形狀差異。

4?結?語

利用面的邊數差異來計算模型面之間的形狀相似度。以面之間的形狀相似度為基礎，構建源模型與目標模型之間的面相似度矩陣。利用模擬退火算法搜索面相似度矩陣，以獲得源模型與目標模型之間的最優面匹配序列。根據最優面匹配序列，從面相似度矩陣中提取源模型面與目標模型面之間的相似度數值。通過累積模型面之間的相似度數值，來判別源模型與目標模型之間整體差異。實驗結果表明：所提出的方法在模型相似性計算方面是有效的。

參?考?文?獻：

[1]?劉志，?尹世超，?潘翔，?等.?基于特征線條的三維模型檢索方法[J].?計算機輔助設計與圖形學學報，?2016，?28（9）：?1512.

LIU?Zhi，?YIN?Shichao，?PAN?Xiang，?et?al.?3D?Model?Retrieval?Method?Based?on?Feature?Lines[J].?Journal?of?Computer-Aided?Design?and?Computer?Graphics，?2016，?28（9）：?1512.

[2]?孫長樂，?寧大勇，?熊偉，?等.?基于特征的工程領域CAD模型檢索技術[J].?計算機集成制造系統，?2014，?20（4）：?747.

SUN?Changle，?NING?Dayong，?XIONG?Wei，?et?al.?Featute-based?CAD?Model?Retrieval?Technique?in?Engineering?Field[J].?Computer?Integrated?Manufacturing?Systems，?2014，?20（4）：?747.

[3]?莊廷，?張旭堂，?侯珍秀.?多特征結合相似度優化的三維工程模型檢索算法[J].?哈爾濱工程大學學報，?2015，?36（5）：?720.

ZHUANG?Ting，?ZHANG?Xutang，?HOU?Zhenxiu，?et?al.?3D?Engineering?Model?Retrieval?Algorithm?Based?on?Multiple?Features?and?Similarity?Calculation?Optimization[J].?Journal?of?Harbin?Engineering?University，?2015，?36（5）：?720.

[4]?白靜.?基于擴展特征樹的三維CAD模型相似評價[J].?計算機集成制造系統，?2014，?20（2）：?267.

BAI?Jing.?3D?CAD?Model?Similarity?Assessment?Based?on?Extended?Feature?Tree[J].?Computer?Integrated?Manufacturing?Systems，?2014，?20（2）：?267.

[5]?劉玉杰，?宋陽，?李宗民，?等.?融合信息熵和?CNN?的基于手繪的三維模型檢索[J].?圖學學報，?2018，?39（4）：?735.

LIU?Yujie，?SONG?Yang，?Li?Zongmin，?et?al.?Sketch-Based?3D?Shape?Retrieval?with?Representative?View?and?Convolutional?Neural?Network[J].?Journal?of?Graphics，?2018，?39（4）：?735.

[6]?牟春倩，?唐雁，?胡金戈.?基于流形排序的三維模型檢索方法[J].?山東大學學報，?2017，?29（5）：?929.

MOU?Chunqian，?TANG?Yan，?HU?Jinge，?et?al.?A?New?3D?Model?Retrieval?Method?Based?on?Manifold?Ranking[J].?Journal?of?Shandong?University，?2017，?29（5）：?929.

[7]?XIAO?J，?FENG?Y?F，?JI?M?M，?et?al?Fast?View-based?3D?Model?Retrieval?via?Unsupervised?Multiple?Feature?Fusion?and?Online?Projection?Learning[J].?Signal?Processing，?2016，?120（3）：?702.

[8]?李海生，?董水龍，?趙天宇，?等.?利用深度圖像改進光場描述符的三維模型檢索算法[J].?北京郵電大學學報，?2016，?39（4）：?56.

LI?Haisheng，?DONG?Shuilong，?ZHAO?Tianyu，?et?al.?Improved?Light?Field?Descriptor?Using?Depth?Images?for?3D?Model?Retrieval[J].?Journal?of?Beijing?University?of?Posts?and?Telecommunications，?2016，?39（4）：?56.

[9]?LIU?A?A，?NIE?W?Z，?GAO?Y，?et?al.?Multimodal?Clique?Graph?Matching?for?View-based?3D?Model?Retrieval[J].?IEEE?Trans?Image?Process，?2016，?25（5）：?2103.

[10]王衛兵，?白小玲，?徐倩.?SURF和RANSAC的特征圖像匹配[J].?哈爾濱理工大學學報，?2018，?23（1）：?117.

WAND?Weibing，?BAI?Xiaoling，?XU?Qian.?Features?Image?Matching?of?SURF?and?RANSAC[J].?Journal?of?Harbin?University?of?Science?and?Technology，?2018，?23（1）：?117.

[11]劉露，?于曉婷，?丁博，?等.?一種基于視覺顯著模型的PET圖像快速分割算法[J].?哈爾濱理工大學學報，?2017，?22（4）：?40.

LIU?Lu，?YU?Xiaoting，?DING?Bo，?et?al.?A?Fast?Segmentation?Algorithm?of?PET?Images?Based?on?Visual?Saliency?Model[J].?Journal?of?Harbin?University?of?Science?and?Technology，?2017，?22（4）：?40.

[12]陳莉，?劉弘.?基于跨本體語義相關的三維模型檢索方法[J].?電子科技大學學報，?2017，?46（4）：?585.

CHEN?Li，?LU?Hong.?3D?Model?Retrieval?Method?Based?on?Semantic?Correlation?Between?Different?Ontology[J].?Journal?of?Harbin?University?of?Science?and?Technology，?2017，?46（4）：?585.

[13]張猛，?陳雙敏，?舒振宇，?等.?點云曲面上的形狀直徑函數[J].?計算機輔助設計與圖形學學報，?2017，?29（7）：?1203.

ZHANG?Meng，?CHEN?Shuangmin，?SHU?Zhenyu，?et?al.?The?Shape?Diameter?Function?on?Point?Clouds[J].?Journal?of?Computer-Aided?Design?and?Computer?Graphics，?2017，?29（7）：?1203.

[14]黃瑞，?蔣俊鋒，?張樹生.?關聯工藝引導的型腔類零件局部結構檢索方法[J].?計算機輔助設計與圖形學學報，?2018，?30（4）：?707.

HUANG?Rui，?JIANG?Junfeng，?ZHANG?Shusheng.?Associated?Machining?Process-Guided?Subpart?Retrieval?Approach?of?Parts?with?Pockets?for?Machining?Process?Reuse[J].?Journal?of?Computer-Aided?Design?and?Computer?Graphics，?2018，?30（4）：?707.

[15]CHEN?Z?Y，?LIN?W?C，?TSAI?C?F，?et?al.?3D?Model?Retrieval?by?Sample?Based?Alignment[J].?Journal?of?Visual?Communication?and?Image?Representation，?2016，?40（10）：?721.

[16]TAO?S?Q，?WANG?S?T，?CHEN?A?H.?3D?CAD?Solid?Model?Retrieval?Based?on?Region?Segmentation[J].?Multimedia?Tools?and?Applications，?2017，?76（1）：?103.

[17]WANG?J?H，?WANG?H?Y.?A?Study?of?3D?Model?Similarity?Based?on?Surface?Bipartite?Graph?Matching[J].?Engineering?Computations，?2017，?34（1）：?174.

[18]皇甫中民，?張樹生，?閆雒恒.?基于層次特征描述子的三維CAD模型檢索[J].?計算機集成制造系統，?2015，?21（12）：?3095.

HUANGFU?Zhongmin，?ZHANG?Shusheng，?YAN?Luoheng.?3D?CAD?Model?Retrieval?Based?on?Hierarchical?Feature?Descriptor[J].?Computer?Integrated?Manufacturing?Systems，?2015，?21（12）：?3095.

[19]周陽，?于勇，?顧黎，?等.?基于特征的MBD模型檢索方法研究[J].?組合機床與自動化加工技術，?2018，?10（10）：?198.

ZHOU?Yang，?YU?Yong，?GU?Li，?et?al.?Research?of?MBD?Model?Retrieval?Method?Based?on?Feature[J].?Mondular?Machine?Tool?&?Automatic?Manufacturing?Technique，?2018，?10（10）：?198.

[20]張勇，?耿國華.?基于拓撲關系和幾何特征的圖像匹配方法[J].?北京師范大學學報，?2018，?54（12）：?198.

ZHANG?Yong，?GENG?Guohua.?Image?Matching?Method?Based?on?Topological?Relation?and?Geometric?Feature[J].?Journal?of?Beijing?Normal?University，?2018，?54（2）：?198.

（編輯：溫澤宇）