在CAD领域中，80%的设计是对原有方案的重用和修改。为了从规模庞大的模型库中获取所需要的模型，许多研究者使用了基于三维视图的模型检索方法^[1]，如樊亚春等^[2]、范菁等^[3]采用局部视图信息对模型进行组合描述。刘志等^[4]获取了三维模型较优视点集，并从各个视点混合轮廓线视图中抽取边缘响应特征。利用自然图像与特征线的边缘相似性来检索三维模型。但是视图的投影方向和数目会对模型特征的精度产生影响，而且此方法对于拓扑结构复杂的三维模型，效果不稳定。利用模型本体的结构信息^[5]结合三维模型面的几何属性^[6]，是行之有效的方法。徐静等^[7]根据外部边闭合规范、待定边转换规范和表面区域合并规范，将三维零件模型分割为若干个区域。对分割区域进行编码，利用区域结构编码来检索零件。此外，多属性融合的特征描述子^[8-9]能更好地描述模型之间的差异。王新颖^[10]从多个不同的方向上利用张量来抽取特征，给出了一种加权多线性主成分分析方法，并将其应用于三维模型的特征提取过程之中。Furuya等^[11]将部分整体关系嵌入网络算法应用于三维模型检索过程中，能够有效地检测部分整体包含关系，并将其融入特征空间之中。Wang等^[12]比较三维模型面，对比中立点的形状特征来计算2个三维模型之间的相似性。Tao^[13]利用顶点之间的兼容性矩阵和边缘兼容性矩阵表示模型，采用归一化方法来构造最优顶点映射矩阵，使用分级分配算法来检索CAD模型。Li等^[14]使用多个分类器来预测给定的三维模型，使用不精确推理理论来融合所有的预测结果，提高了高维空间的搜索效率。Chen等^[15]以样本模型作为对齐目标，将所有三维模型依次排列，提出了一种基于样本对齐的模型检索方法。

本文提取模型的几何拓扑属性^[16]，综合考虑几何信息在模型相似性计算中的作用^[17]。利用边数差异来计算面的形状相似性，进而构建2个模型之间的面相似度矩阵。以模型面的邻接关系和面的形状相似性为基础来度量2个模型面的结构相似性。综合面的形状相似性和结构相似性来建立2个模型的整体相似度矩阵。融合遗传算法和模拟退火算法来搜索最优面匹配序列，并计算这2个模型之间的相似性。

1 模型之间的相似性计算

模型是由多个面组成的。模型面的形状差异，造成了模型之间的千差万别。为了计算2个模型之间的相似性，需要度量这2个模型面之间的形状差异。面是由边构成的，2个边数不同的面，其形状一定有差别。本文利用边数差异来度量2个面之间的形状相似性。使用面相似性来度量2个模型的形状差异。如果2个模型面的组成边数差异越小，那么这2个面的形状就越相似。如果2个模型面之间的组成边数差异越大，那么这2个面之间的形状差异就越大。本文以源模型U和目标模型V为例来说明模型之间的形状相似性计算过程。

带有槽的三棱柱如图 1所示。图 2也是一个带有槽的三棱柱，只是面的编号有所不同。

此处，使用u_s表示源模型U的面；v_t表示目标模型V的面。源模型面u_s和目标模型面v_t之间的面相似性计算过程为：

$ {S_f}({u_s},{v_t}) = 1 - \frac{{|N({u_s}) - N({v_t})|}}{{{\rm{max}}(N({u_s}),N({v_t}))}} $

(1)

式中：N(f)表示面f的组成边数；max(x, y)表示x与y之间的最大值。

如果面u_s和v_t所含边数差别越小，那么u_s与v_t之间的相似性就越高，S_f(u_s, v_t)的值就越大；相反，如果面u_s和v_t所含边数差别越大，那么u_s与v_t之间的相似性就越低，S_f(u_s, v_t)的值也就越小。利用式(1)计算源模型与目标模型各个面之间的形状相似性，并构造面相似度矩阵。此处，使用m表示源模型面数，利用n表示目标模型面数。搜索面相似度矩阵，能够获得源模型与目标模型之间的最优面匹配序列。为了便于求解，假设m≤n，即面相似度矩阵的行数要小于等于列数。如果m>n，则将源模型与目标模型互换来进行求解。

源模型与目标模型之间的相似性，不仅取决于各个组成面之间的形状相似程度，而且还取决于各个组成面之间的结构相似程度。在计算源模型面u_s与目标模型面v_t之间的结构相似性时，需要考虑u_s的邻接面和v_t的邻接面之间形状相似程度，还需要考虑u_s及其邻接面与v_t及其邻接面之间邻接顺序对应情况。在模型中，使用邻接矩阵来表示组成面之间的邻接关系：

$ {\mathit{\boldsymbol{w}}_{ab}} = \left\{ {\begin{array}{*{20}{l}} {1,}&{a{\rm{ 与 }}b{\rm{ 相邻 }}}\\ {0,}&{a{\rm{ 与 }}b{\rm{ 不相邻 }}} \end{array}} \right. $

(2)

式中：a和b分别表示模型的2个面。在源模型中，使用如下规则来表示面与面之间的邻接顺序关系:当i≤s时，表示源模型面u_i和u_s之间的顺序为正序。当i>s时，表示源模型面u_i和u_s之间的顺序为反序。当j≤t时，表示目标模型面v_j和v_t之间的顺序为正序。当j>t时，表示目标模型面v_j和v_t之间的顺序为反序。此处，令w=w_uius+w_vjvi。源模型面u_i及u_s与目标模型面v_j及v_t之间的邻接顺序对应值W(i, s, j, t)的计算过程为：

$ W(i,s,j,t) = \left\{ {\begin{array}{*{20}{l}} {0.5,}&{w = 1,{\rm{ 且 }}(i < s,j < t{\rm{ 或 }}i > s,j > t)}\\ {0.25,}&{w = 2,{\rm{ 且 }}(i > s,j < t{\rm{ 或 }}i < s,j > t)}\\ {1,}&{w = 2,{\rm{ 且 }}(i < s,j < t{\rm{ 或 }}i > s,j > t)}\\ {0,}&{{\rm{其他}}} \end{array}} \right. $

(3)

源模型面u_i与目标模型面v_j之间的结构相似性计算过程如下：

$ {\rm{Si}}{{\rm{m}}_{st}}({u_i},{v_j}) = \sum\limits_{i = 1}^n {\sum\limits_{j = 1}^m {{S_f}} } ({u_s},{v_t}) \cdot W(i,s,j,t)/(mn) $

(4)

在计算u_i与v_j的结构相似性时，不仅考虑了u_i的所有邻接面与v_j的所有邻接面之间的形状对应程度，而且考虑了u_i及其邻接面与v_j及其邻接面的邻接顺序对应关系。因此，式(4)能够度量源模型面与目标模型面之间的结构相似性。

为了准确地计算源模型面u_i与目标模型面v_j之间的相似性，需要考虑二者之间的形状和结构相似程度。源模型面u_i与目标模型面v_j之间的相似性S(u_i, v_j)的计算过程为：

$ S({u_i},{v_j}) = {S_f}({u_i},{v_j}) \cdot {S_{st}}({u_i},{v_j}) $

(5)

利用式(5)计算源模型与目标模型各个面之间的相似性，并构造源模型与目标模型之间的整体相似度矩阵S。

2 基于遗传退火算法的面匹配

遗传算法对离散空间具有较强的全局搜索能力，模拟退火算法具有较好的局部搜索能力。为了提高面匹配的准确性，文本融合这2种算法，提出了基于遗传退火算法的面匹配方法。

1) 染色体编码。

使用二元序对(i, j(i))表示源模型面u_i与目标模型面v_j(i)相匹配。对于每个源模型面而言，都可以获得一个二元序对。按照源模型面序号递增的顺序，利用所有的二元序对来构造染色体X=((1, j(1)), (2, j(2)), …, (m, j(m)))。对于源模型面u_i，有多种面匹配方案。因此，可以获得多条不同的染色体。此处，选取s条染色体X_t=((1, j_t(1)), (2, j_t(2)), …, (m, j_t(m))) (t=1, 2, …, s)。设定染色体的数量s为20。源模型与目标模型的面匹配过程将转化为求最优染色体编码的问题。染色体X的适应度值F(X)的计算过程为：

$ F(\mathit{\boldsymbol{X}}) = \sum\limits_{i = 1}^m S (i,j(i)) $

(6)

2) 选择操作。

在选择最优面匹配序列时，采用轮盘赌比例选择操作，实现方式如下：

利用式(6)分别计算出F(X₁)、F(X₂)、…、F(X_s)的适应度值。染色体X_t的选择概率为:

$ P({\mathit{\boldsymbol{X}}_t}) = F({\mathit{\boldsymbol{X}}_t})/\sum\limits_{i = 1} {F({\mathit{\boldsymbol{X}}_i})} ,\;\:t = 1,2, \cdots ,s $

(7)

产生一个[0, 1]的随机数r。若$\sum\limits_{i = 0}^{i - 1} {P\left( {{\mathit{\boldsymbol{X}}_i}} \right)} \le r\langle \sum\limits_{i = 0}^t {P\left( {{\mathit{\boldsymbol{X}}_i}} \right)} $，则选择染色体X_t遗传到下一代。其中P(X₀)=0。

3) 交叉操作。

采用顺序交叉方法，对面匹配序列进行交叉，实现方法如下：

在相邻2个染色体之间，随机选取一段用于产生待交叉序列(待交叉序列的长度为序列长度的1/3~2/3，并采用四舍五入方法进行取整)，以概率P_c产生交叉。交叉操作是使种群多样化的主要因素。

对于面序对(i, j(i))，定义操作c(i, j(i))=j(i)，即取面序对的第2分量。对于染色体X=((1, j(1)), (2, j(2)), …, (m, j(m)))，定义操作C(X)=(c(1, j(1)), c(2, j(2)), …, c(m, j(m)))。C(X)为从源模型与目标模型的面匹配序列中依次抽取每个面序对的第二分量所形成的向量。对于父代染色体X_p=((1, j_p(1)), (2, j_p(2)), …, (m, j_p(m)))和X_q=((1, j_q(1), (2, j_q(2)), …, (m, j_q(m)))，可以获得C(X_p)和C(X_q)。构造子代染色体X_sp=((1, j_sp(1)), (2, j_sp(2)), …, (m, j_sp(m)))和X_sq=((1, j_sq(1)), (2, j_sq(2)), …, (m, j_sq(m)))。

所取出的交叉分量为X′_sp=((round(m/3), j_sp(round(m/3))), …, (round(2m/3), j_sp(round(2m/3))))和X′_sq=((round(m/3), j_sq(round(m/3))), …, (round(2m/3), j_sq(round(2m/3))))。互换X′_sp与X′_sq所对应面序对的第2分量。C(X′_sp)=(c(round(m/3), j_sp(round(m/3))), …, c(round(2m/3), j_sp(round(2m/3))))和C(X′_sq)=(c(round(m/3), j_sq(round(m/3))), …, c(round(2 m/3), j_sq(round(2 m/3))))。setdiff(A, B)= A-B为序列差操作。I_sp=setdiff(C(X_p), C(X′_sq))，I_sq=setdiff(C(X_q), C(X′_sp))。将I_sp中的元素依次插入X_sp的第1~round(m/3)-1和第round(2m/3)+1~m的面序对的第2分量。将I_sq中的元素依次插入X′_sq的第1~round(m/3)-1和第round(2m/3)+1~m的面序对的第2分量。从而获得子代染色体X_sp和X_sq。

4) 变异操作。

为了避免陷入局部最优，同时保证解空间的多样性，采用逆转变异方法对面匹配序列进行处理。随机选择染色体X_i=((1, j_i(1)), (2, j_i(2)), …, (b, j_i(b)), …, (d, j_i(d)), …, (m, j_i(m)))。随机选取2个交换位置点b和d，取出位置点b和d的面序对(b, j_i(b))和(d, j_i(d))。将(b, j_i(b))和(d, j_i(d))的第二分量进行互换。变异后的面匹配序列为X_vi=((1, j_i(1)), (2, j_i(2)), …, (b, j_i(d)), …, (d, j_i(b)), …, (m, j_i(m)))。变异操作是保证种群多样性的辅助手段。为了避免损失优良的个体，变异概率P_d设定为0.01。

5) 模拟退火操作。

通常，模拟退火算法在当前解的邻域范围内更新解。本文采用如下方法来产生新解：

在染色体X_i中，对基因j_i(k)使用rand函数产生一个[0, 1]之间的随机数r。利用下式决定基因j_i(k)的移动方向，设定步长为1：

$ j_i^{t + 1}(k) = \left\{ {\begin{array}{*{20}{l}} {j_i^t(k) + 1,}&{r > \frac{2}{3}}\\ {j_i^t(k),}&{{\rm{其他}}}\\ {j_i^t(k) - 1,}&{r < \frac{1}{3}} \end{array}} \right. $

(8)

式中：j_i^t(k)为位置k上的基因在第t次迭代时的数值。经过变换之后，产生的新解为j_i^t+1(k)。若r>2/3，则j_i^t(k)的值加1。若r < 1/3，则j_i^t(k)的值减1。若r为其他值时，则j_i^t(k)的值保持不变。当前最优解序列为C(X_i)=(j_i(1), …, j_i(2), …, j_i(b), …, j_i(d), …, j_i(m))。经过模拟退火操作之后，产生新解C(X_z)=(j_z(1), …, j_z(2), …, j_z(m))。产生新解的次数为Markov链的长度L，设置L的数值为20。在每次产生新解时，使用Metropolis准则来判断是否接受新解X_new，还是保留原始解X_old。X_old为上一次所搜索到的面匹配序列，X_new为当前搜索到的面匹配序列，即：

$ \left\{ {\begin{array}{*{20}{l}} {{\mathit{\boldsymbol{X}}_{{\rm{old}}}} = ((1,{j_{{\rm{old}}}}(1)),(2,{j_{{\rm{old}}}}(2)), \cdots ,(m,{j_{{\rm{old}}}}(m)))}\\ {{\mathit{\boldsymbol{X}}_{{\rm{new}}}} = ((1,{j_{{\rm{new}}}}(1)),(2,{j_{{\rm{new}}}}(2)), \cdots ,(m,{j_{{\rm{new}}}}(m)))} \end{array}} \right. $

将搜索到的面匹配序列X_old和X_new代入式(6)计算出对应的相似度数值F(X_old)和F(X_new)，使用Metropolis准则进行判断。

Metropolis接受准则为:

$ \begin{array}{l} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} {\kern 1pt} P = \\ \left\{ {\begin{array}{*{20}{l}} {1,}&{F({\mathit{\boldsymbol{X}}_{{\rm{ old }}}}) < F({\mathit{\boldsymbol{X}}_{{\rm{ new }}}})}\\ {{\rm{exp}}\left( { - \frac{{F({X_{{\rm{ old }}}}) - F({X_{{\rm{ new }}}})}}{T}} \right),}&{F({\mathit{\boldsymbol{X}}_{{\rm{ old }}}}) \ge F({\mathit{\boldsymbol{X}}_{{\rm{ new }}}})} \end{array}} \right. \end{array} $

(9)

式中：F(X_old)为上一次得到的面匹配序列的适应度值；F(X_new)为新的面匹配序列的适应度值。退火过程采用下式来完成：

$ {T_k} = Q{T_{K - 1}} $

(10)

式中：Q为退火参数，设定Q的值为0.95。

在产生新解的过程中，基因的移动是随机的，而且是相互独立的。因此，在所产生的新解中，会出现0元素、越界元素和重复元素。为了解决这一问题，进行了如下处理：

I₁=setdiff(randperm(n), I);

    i=1;

    for k=1: m

      if(I(k)==0||I(k)>n)

        I(k)=I₁(i);

        i=i+1;

      end

    end

[B, N]=unique(I);

R=setdiff(1: numel(I), N);

I₂=setdiff(randperm(n), unique(I));

for r=1: length(R)

      for p=1: m

        if(I(R(r))==I(p))

        I(p)=I₂(r);

        break;

      end

    end

end

此处，集合I=C(X)，即I为面匹配序列的第二分量的集合。randperm函数返回1~n的一个随机序列；setdiff(A, B)为序列差操作，返回集合A与B的差集；[B, N]=unique(I)为去重函数，B为I中不重复元素组成的集合，N为B中元素在I中的位置序号的集合；numel(I)为I中元素的个数；length(R)为集合R的长度。

基于遗传退火算法的面匹配：

1) 根据式(5)计算源模型U的第i个面和目标模型V的第j个面之间的相似性，并构造整体相似度矩阵S。

2) 初始化温度T=100，降温参数Q=0.95、种群规模s=20、交叉概率p_c=0.7、变异概率p_d=0.01，Markov链的长度L=20和最大迭代次数Maxk=100，置迭代次数的初始值i=1。

3) 产生初始种群G=(X₁, X₂, …, X₂₀)，染色体X_t=((1, j_t(1)), (2, j_t(2)), …, (m, j_t(m))) (t=1, 2, …, 20)。利用式(6)计算染色体X_t的适应度值F(X_t)，并进行选择操作。

4) 对种群G中的染色体随机配对并执行交叉操作，得到交叉后的种群G_c。

5) 对交叉后的种群G_c中的染色体执行变异操作，得到变异后的种群G_m。

6) 对种群G_m中的染色体执行模拟退火操作，采用Metropolis准则判断更新解序列，产生种群G_g=(X₁^*, X₂^*, …, X₂₀^*)，G=G_g。

7) 判断是否满足条件i≤Maxk，若满足，则输出最优面匹配序列，否则重复执行步骤4)~6)。

在源模型U和目标模型V的整体相似度矩阵S中，利用上述算法来搜索二者之间的最优面匹配序列，得到的解向量(j(1), j(2), …, j(m))。所对应的最优面匹配序列为((1, j(1)), (2, j(2)), …, (m, j(m)))。以最优面匹配序列为基础，从整体相似度矩阵S中取出源模型面与目标模型面的相似性。通过累积面的相似性来计算源模型U与目标模型V之间的相似性，其计算过程为：

$ {S_{{\rm{ Model }}}}(U,V) = \sum\limits_{i = 1}^m S (i,j(i))/n $

(11)

式中：m表示源模型U的面数；n为目标模型V的面数；(i, j(i))为利用上述算法所获得的最优面匹配序列中的第i个序对。

3 实验和结果

本文使用Matlab编写基于遗传退火的面匹配算法，对整体相似度矩阵S进行搜索。在实验中，目标模型为一个六棱锥，如图 3所示。同时选取了15个CAD模型作为源模型，如图 4所示。

使用贪心算法对面相似度矩阵进行搜索，以获得最优面匹配序列。利用蝙蝠算法^[18]、模拟退火算法和本文所提出的方法分别对整体相似度矩阵进行搜索，以获得最优面匹配序列。以最优面匹配序列为基础，使用式(11)计算源模型与目标模型之间的相似性。在4组实验中，源模型与目标模型之间的相似性如表 1所示。

对源模型按照相似性由大到小的顺序进行排序。对贪心算法，源模型排序的结果为A、L、N、D、J、K、G、B、E、H、C、F、I、M、O。对蝙蝠算法，源模型排序的结果为A、B、C、D、E、G、J、K、L、H、N、I、F、M、O。对模拟退火算法，源模型排序的结果为A、B、C、D、E、G、L、H、K、F、J、I、M、N、O。对本文所提出的方法，源模型排序的结果为A、B、C、D、E、G、K、J、L、H、I、F、M、N、O。从形状上看，源模型A与目标模型相同。贪心算法、蝙蝠算法、模拟退火算法和本文所提出方法都把模型A排在了第1位。

从形状上看，源模型B和C与目标模型的相似度很高。蝙蝠算法、模拟退火算法和本文所提出方法都把源模型B、C排在第2位和第3位，而贪心算法却把与目标模型非常不相似的L、N 2个模型排在第2位和第3位。

从形状上看，源模型D和G与目标模型的相似程度明显不如B、C 2个模型。蝙蝠算法、模拟退火算法和本文所提出方法都把模型D和G排在模型B、C之后，而贪心算法把模型D和G排在模型B、C之前。由此可以看出：在计算2个模型的相似性时，蝙蝠算法、模拟退火算法和本文所提出方法的性能要好于贪心算法。其原因是：在计算模型相似性时，蝙蝠算法、模拟退火算法和本文所提出方法不仅考虑了形状信息，而且考虑了结构信息。贪心算法仅仅考虑了形状信息。

对H、J、K、L4个模型而言，K最接近目标模型，J与目标模型较为相似，H、L与目标模型的差异较大。贪心算法把L排在了J、K之前，K排在了J之后。蝙蝠算法把K排在了J之后。模拟退火算法将H、L排在了J、K之前。本文所提出方法将K、J排在了H、L之前，将K排在J之前。相对于模拟退火算法而言，所提出方法使13.33%的模型的排序效果有所改善。相对于模型N而言，I、M更接近于目标模型。蝙蝠算法将模型N排在I、M之前，模拟退火算法和本文所提出方法都把模型N排在I、M之后。由此可以看出：在计算2个模型的相似性时，本文所提出方法的性能要优于蝙蝠算法和模拟退火算法。其原因是：本文所提出的方法既兼顾了遗传算法的全局搜索能力，又兼顾了模拟退火算法的局部搜索能力。与模拟退火算法和蝙蝠算法相比，本文所提出方法能够更好地计算2个模型之间的相似度。

4 结论

1) 本文利用面之间的边数差异构造2个模型之间的面相似度矩阵。以此为基础，结合面的邻接关系来计算源模型面与目标模型面的结构相似性。结合面的形状相似性和结构相似性构造整体相似度矩阵。

2) 利用遗传退火算法来搜索整体相似度矩阵，以获得源模型与目标模型之间的最优面匹配序列。以最优面匹配序列为基础，通过累积源模型面与目标模型面之间的相似性度量2个模型之间的差异。

3) 在计算模型相似性时，本文所提出的方法要优于蝙蝠算法、模拟退火算法和贪心算法，能够更准确地计算2个模型之间的相似性。