一种基于形状分布的工程图形整体相似性检索方法

王 鹏 ，姜寿山

(西北工业大学 机电学院，西安 710072)

0 引言

近几十年来，随着计算机技术的迅速发展，现代CAD系统提供强大的工具创建和编辑工程图，如AutoCAD、UG、CATIA。虽然在工程图应用领域重用过去的工程图已经成为一种惯例，但是在当前CAD系统中并没有提供相应的自动检索机制。据资料估计，在产品开发中约有80%的设计为变形设计和自适应设计，其中约有40%是重用过去的部件设计，40%对已有部件稍作修改，而全新的设计仅占20%[1]。由此可知，已有的工程图资料是企业进行新产品设计和开发的重要依据和基础，准确地检索出工程图信息对于进行新产品的设计具有重要的意义。

图形形状的相似性比较是模式识别与图形检索领域的主要研究内容，目前有多种图形形状的相似性比较算法。常用的轮廓描述子是傅里叶描述子(Fourier descriptor, FD)[2]，傅里叶描述子具有选择和比例不变性的特点，用于描述工程图形的外轮廓。Legendre[3]描述子是正交描述子，具有比例不变性的优点，但是其不具有图形旋转不变性。形状分布算法是由Osada[4,5]等率先提出，主要用于三维模型的形状特征提取，可以很好的描述三维形状的几何特征，而二维形状可以看作是三维形状在二维空间中的投影，那么通过改进三维形状分布方法，可以设计出一种二维形状分布算法，其必然能够很好地描述二维形状的几何特征。基于上述思想，本文提出了一种基于形状分布的工程图形整体相似性检索方法。

1 基于形状分布的工程图整体相似性检索方法总体思路

工程图形整体相似性检索与2D图形形状识别相对应。本文定义工程图形整体相似性检索为：给定一个工程图A和一个工程图库L={Bi|0≤i≤n}，如何计算工程图A与Bi之间的相似性，即D(A,Bi)，并且找到最相似的k个工程图。在检索过程中，寻找一个合适的图形形状描述符是工程图整体相似性检索效果的关键。本文从统计学角度提出通过从工程图图形上采集采样点的形状分布算法，其总体思路如图 1所示。

图1 工程图整体相似性检索算法整体思路

2 形状分布算法主要步骤

2.1 选择形状分布函数

选择形状函数的目的是提取二维图形的形状信号，理想的形状函数所提取的形状信号具有变换不变性，即相同的工程图图形对旋转、平移和缩放等变换具有相同的形状信号。本文选用D[4,5]2形状分布函数，其分布曲线是一些规范化的形状，如图2所示。通常，不同的图形对应的分布是不一样的，且连续改变的工程图图形对D2分布的影响是连续的。

2.2 计算统计数据

在设计好形状函数之后计算统计数据。一般来讲，给定一个图形，随机计算图形上任意两点的距离的复杂度非常大，根据统计理论，可以通过随机采样来解决。而要实施随机采样，就必须解决三个关键问题：一是如何对图形进行表示才能设计出合理的随机采样方法；二是如何设计合理的随机采样方法；三是随机采样多少个数据点才能充分反映图形的形状特征，而且计算量在可接受的范围内。下面给出上述三个问题的解决方法。

1）工程图形的离散化表示

一个工程图形由一些基本的几何元素组成，如线段、圆弧、圆、样条曲线等。为了更好更有效的对工程图形进行数据点采样，本文将工程图形离散化为由一系列线段组成的集合。对于圆弧、圆、样条曲线由一系列线段去近似。这样一个工程图形可以表示为：

S= {((xi, yi),(xi+1,yi+1))|0≤i≤n-1}

其中n为S中线段的个数，(xi, yi)与(xi+1,yi+1)分别为线段的起点与终点。

2）数据点的随机采样方法

合理的随机采样方法不仅能够反映图形的总体形状特征，还要充分体现图形局部的细节特征。为此，本文设计了一种基于查表算法的数据点采样方法，该方法基于图形的离散化表示，其详细步骤如下：

1）计算二维工程图形S中所有线段的总长度。每相加一个线段，就将该长度存入表T中，其大小为n，其中图形线段的个数为n-1，则表T可以表示为一个线性数组，如式(1)所示。

其中L表示两个点之间的欧氏距离。

2）随机产生一个实数r(0≤r≤tn-1)；然后采用著名的二分法查找法找到值r在表T中的位置，该位置记为((xm,ym),(xm+1,ym+1))。

3）随机产生一个实数l(0≤l≤1)，根据式(2)，可以获得一个采样数据点(xk,yk)，并且将其存入数据点采样向量A。

4）重复执行2）与3）2N次获得N个无偏数据采样点对。

从统计学理论角度来讲，采样点的数量越多，就越能反映三视图的形状特征。但是采样点越多，则计算量越大，需要的计算时间就越长，效率越低。因此，二者是矛盾的，必须寻找一个平衡点，即采样点的数目既能充分反映图形的形状特征，又能将计算量控制在可接受的范围内。

为了获取该平衡点，选取不同数目的采样点进行实验，实验结果如图3所示，其中横坐标代表采样点的数目，纵坐标代表采样过程所需时间或不同数目的采样点描述图形形状的准确度。从图3可以看出，当采样点数目为103个时，即N=103效果比较好，即此时不仅能够充分反映图形的准确度，而且采样过程所需时间又在可接受的范围内。

图3 采样过程效率与准确度实验测试结果

2.3 构造形状分布曲线

本文采用统计理论对随机信号进行参数化，并且对随机点对之间的距离值进行统计，生成一个形状直方图。对于不同大小的工程图形，其距离值跨度很大，因此需要对形状分布直方图的尺度进行归一化。本文以D2距离的平均值的1/50作为区间长度，统计落在第i个区间的点对距离数量为Ni，以i的值作为横轴，纵轴可以表示为100×Ni/499500，由此构建形状直方图，如图4（a）所示，通过对形状直方图的拟合形成形状分布曲线图，如图4（b）所示。随机信号参数化的结果即把工程图形的形状信号参数化成为一个形状分布直方图(离散的)或形状分布曲线图(连续的)。

2.4 相似性度量

通过计算工程图形上任意两点之间的距离并进行统计，工程图形的形状特征被映射成为一个形状分布曲线，这样，工程图形之间的相似性比较就可以转化为形状分布曲线之间的距离度量。距离越大，工程图形之间的差别就越大，反义亦然。两个分布之间的距离包括Minkowski距离、x2统计距离、二次距离等，本文采用EMD距离。

EMD距离是一种有效且正在被越来越广泛使用的集合间或向量间距离计算方式[6]。它能只通过一次线性规划计算出两个具有不等(或相等)权值分布的不同(或相同)大小的集合或向量的距离。该算法产生于物理学，线性规划中的运输问题可作为其具体求解算法。

形象的解释EMD距离算法就是：空间S中分布着M堆土Pi，i=1,…,M，每堆土的质量为wpi，同时分布有N个土坑Qi，i=1,…,N，每个坑可以装土的质量为wqi。把所有土填到这些坑内，做的功表示为：

其中d(Pi,Qj)表示第i堆土到第j个坑的距离，称其为基本距离或单位代价。fij表示从第i堆土到第j个坑的土的质量。d(Pi,Qj)fij表示把第i堆土中质量为fij的土运到第j个坑所做的功。式(3)满足如下约束：

约束1说明，每次搬运的质量大于零时才做功。约束2说明，从第i堆土运到各个坑的土的质量总和，一定不会大于该堆土的质量。约束3说明从各堆土运到第j个坑的土的质量总和，一定不会大于该坑所能容纳的土的质量。

从上述定义，不难把工程图形的相似性度量问题转化为EMD距离计算问题。当测量两个工程图形的距离时，把其中一个工程图形的形状分布分量映射成土堆，另一个工程图形的形状分布分量映射成土坑，则两个工程图形之间的距离，就是把所有的土填入坑内，在选择最佳路径的情况下，做功的最小值。因此，两个工程图形形状分布的EMD距离定义为：

式(4)的分母是归一化因子。分子同线性规划中运输问题的目标函数完全一致，约束条件也可以转换为运输问题的约束条件的标准形式，因此可以很方便地应用运输问题的标准算法求解。

3 实例验证与讨论

为了验证本文所提出的基于形状分布的工程图形整体相似性检索方法的有效性，我们构建了一个工程图库，该工程图库包括轴类、盘类、箱体类等各类零件模型共300个，工程图形的数据格式统一采用DXF标准格式，以Microsoft Visual Studio 2008为集成开发环境验证本文算法。基于该模型库，我们进行了如下两个方面的实验。

实验1：形状分布算法实例分析。给定一个图形，从工程图库中检索出与其最相似的5个图形，其结果如表 1所示。从表 1可以看出，本文方法能够实现工程图形的整体相似性检索，能够检索出所有与检索图形整体相似的图形(共4个)，与人的相似性感知结论相同。优于文献[2][7]中的方法。

图5 工程图形整体相似性检索算法检索性能曲线比较

4 结束语

本文提出了一种基于形状分布的工程图形整体相似性检索方法，并将其应用到工程图模型的相似性评价中。该方法首先对工程图形进行无偏采样，将一个工程图形表达为一个形状分布曲线，将工程图形的整体相似性匹配问题转化为两个工程图模型的形状分布曲线比较问题，然后采用EMD距离计算出两个图形间的相似性。实验结果显示，本文算法能够实现工程图形的整体相似性检索，并且形状分布算法检索性能优于文献[2][7]所提出的方法。

表1 基于形状分布的工程图形整体相似性检索算法实例

实验2： 工程图整体相似性检索算法检索性能比较.为了验证本文算法的检索性能，将本文方法与文献[2][7]方法进行比较，其中“D2”代表本文的D2形状分布算法，“Fourier”代表文献[2]中提出的基于傅里叶描述子的工程图整体相似性检索算法，“Hough transform”代表文献[7]中提出的方法。图5绘制了三种方法的查全率—查准率曲线(PR曲线)，从图5可以看出，本文提出的基于形状分布的工程图形整体相似性检索方法的检索性能

在下一阶段研究中，我们将对工程图模型构建索引描述子，依据索引描述子对模型进行分类，在此基础上进一步改进本文算法，提高检索效率；将本文算法与工程语义相结合，不但利用工程图的空间关系和几何信息，而且利用工程图所包含的语义信息，使其更有利于设计人员设计新产品。

[1] 王玉,刑渊,阮雪榆.机械产品设计重用策略研究[J].机械工程学报,2002,38(5):145～148.

[2] Tabbone S,Wending L,Tombre K.Matching of graphical symbols in line-drawing images using angular signature information [J].Int J Doc Anal Recog,2003,6(2):115-125.

[3] Yun G E,Shu H Z,Luo L M.A new way of linear registration using the legendre orthogonal moment and application in 2-value image data [J].Acta Electronica Sinica,2001,29(1):54-56.

[4] Osada R,Funkhouser T,Chazelle B, Dobkin D.Shape distribution[J].ACM Trans Graph,2002,21(4):807-832.

[5] Osada R,Funkhouser T,Chazelle B,er al.Matching 3d Models with Shape Distributions[C]//International Conference on Shape Modeling and Applications.Geneba:IEEE Computer Society Press,2001:154-166.

[6] Y.Rubner,C.Tomasi,L.J.Guibas,The earth mover's distance as a metric for image retrieval[J].International Journal of Computer Vision,2000,40(2):99-121.

[7] Franti P,Mednonogov A,Kykri V,et al.Conten-based matching of line-drawing images using the hough transform [J].Int J Doc Anal Recog,2000,3(3):117-124.