基于模拟退火算法的模型检索

高雪瑶 谭涛 张春祥

摘 要：为了从模型库中检索到最相似的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.

（編辑：温泽宇）