基于特征点的图形检索研究

唐 涛，高满屯，何 波

（西北工业大学机电学院，陕西 西安710072）

与文字相比，图形具有更形象，更直观的特性，不仅可以弥补文字对客观事务描述的不足，还可以辅助科研工程人员进行数据分析、工程实施：从对客观数据的直观显示，比如直方图，折线图等，到机械零件的设计加工，比如使用CAD软件完成的设计图纸，再到房屋、桥梁、航空器的建造，施工，图形正以前所未有的速度进入我们的工作与生活[1]。管理好、利用好海量的图形信息将极大地推动各项工作的进步。因此，对于图形检索的研究具有十分重要的工程应用价值。

当前，在图形检索领域，使用最广泛的是基于关键字的检索(Keywords-Based Retrieval)[2]，它需要在检索之前，通过人工将图形的主要信息概括为关键字，然后对图形进行标注。检索过程就是将用户输入的关键字与数据库中存储的关键字进行匹配的过程，不具有模糊查找性[3]。另外一种广泛使用的检索技术是基于图元之间拓扑关系的检索。即将图形分解为线段、圆弧等基本图元，然后将图元之间的关系定义为邻接、包含、相触等近十种拓扑关系，根据图元之间的拓扑关系完成检索[4]。虽然这种方法可以较好的实现图形的检索，具有一定的模糊性，但将图形分解成基本图元、然后分析图元之间关系的过程费时费力，不利于大规模图形的检索。本文提出一种基于特征点的图形检索方法，可以根据不同的任务需求，设定不同的模糊量，并且被检索到的图形具有平移不变性和旋转不变形。该方法主要以图形自身作为研究对象，从图形本身中确定一个基准点和基准向量，分析其他特征点与基准点和基准向量之间的关系，从而完成检索。

1 图形基准的确定

图形由基本的图元构成：点，线段，圆弧，圆等[5]。而线段可以由两个点唯一确定。圆弧可以由圆心和圆弧两端的点唯一确定，圆可以由圆心和圆上任意一点确定。任意折线可以用若干首位相接的线段进行近似。任意曲线可以通过若干规则的圆弧或者通过若干首位相接的线段进行近似。综上可以得出这样的结论：任何图形都可以通过有限的特征点进行描述。若图形与图形之间的特征点完全相同，则两个图形相似。

1.1 图形基准点的确定

将图形看成是若干特征点的集合，则这些特征点可以视为是围绕在图形型心附近的点。特征点与型心之间的关系，例如特征点的松散程度，与型心的紧密程度，可以被用以描述图形。因此将图形的型心定义为图形的基准点(Xc,Yc)。图形的型心可以通过公式(1)~(5)计算得到。

1.2 图形基准向量的确定

基准向量的确定是为了将图形中的特征点单独唯一的表征出来。从众多的特征点中确定出与型心距离最近的特征点。基准向量由型心与该特征点构成，方向指向特征点。如图1所示。特征点为A(X1,Y1)，B(X2,Y2)，C(X3,→Y3)，D(X4,Y4)。型心为Cd(Xc,Yc)。基准向量P由型心Cd(Xc,Yc)与最近的特征点B(X2,Y2)构成，由公式(6)计算得到。

2 特征点的规范化

为了进行图形检索，所有的图形必须经过规划化处理，即以统一格式的数据信息表征图形。特征点规范化后由角度值cosθ和距离值L组成。当两个图形规范化后的数据信息满足检索条件时，系统从数据库中把该图形输出。特征点的规范化以图形的基准向量作为基准。图形型心与每个特征点都可以构成一个向量，如图1所示，各个向量分别为其中，将向量定义为基准向量。将这些向量以与基准向量之间的夹角作为特征点规范化后的角度值cosθ，将向量的模作为距离值L，计算如公式(7)所示。

其中，表示基准向量，表示型心与各个特征点构成的向量。则基准向量与向量的角度值为cos∠ACdB，向量的模为，则特征点A对应于特征点B对应于特征点C对应于特征点D对应于

图1 型心与特征点的示意图

3 数据的处理

3.1 图形数组

从以上论述可知，图形中的每个特征点对应于一组数据：角度值和距离值。取角度值和距离值之积，不仅可以将两个数据合并为一个数据，减少后续检索过程中的计算量，而且还能扩大图形与图形之间相应特征点的差异程度。因此，本文将图形中特征点的一组数据简化为一个数据进行处理，计算如公式(8)所示。

其中，cosθ为特征点规范化后的角度值，为特征点规范化后的距离值。从以上的论述可知，Value可以唯一确定特征点在图形中的位置。因此，一个元素数目与特征点数目相等的数组就可以完整地描述一个图形。图形的检索则是寻找一个与已知数组相似的数组。本文把该数组定义为图形数组。图形数组的表示方式如式(9)所示。

3.2 图形数组的规范化

在进行检索的过程中，用户输入图形的特征点与数据库中图形的特征点的数目在大多数情况下并不相等。因此，在进行图形检索之前，要对图形数组进行规范化操作，即：在与用户输入图形进行比对之前，在相似图形的特征点中选取与输入图形特征点相同数目的特征点。由于之前的步骤已经将图形简化为一个图形数组，因此，选取特征点的操作就等同于在相似图形的图形数组中选取元素。这些元素需要满足以下两个约束条件：① 元素的数目与用户输入图形的图形数组中元素的数目相等；② 元素与在用户输入图形的图形数组中的元素最接近。在实际检索中，满足这两个约束条件的图形是：在相似图形中寻找与用户输入图形在形状上最接近的部分。规范化的过程如公式(10)~(12)所示。

其中m>=n

其中，函数min返回数组中最小元素的被减数。则规范化后的Vector2如公式(13)所示。

3.3 检索参数

在图形数组的数字特征可以很好的将图形数组的整体特性表示出来，即标准差Sn。标准差Sn描述的是图形数组元素的紧凑性。标准差可以通过式(14)求得。当差Sn在给定的模糊查找系数δ范围内时，向用户返回检索结果。

4 实验

4.1 选取相似点

在实际检索过程中，大多数情况是用户输入图形的特征点的数目与相似图形的特征点的数目不相一致。检索的第一步就是从相似图形中选取与用户输入图形最接近的特征点。

输入图形特征点的坐标是(0 2 2 4 4 20 20 4 4 2 2 0; 2 2 0 0 2 2 4 4 6 6 4 4);

相似图形特征点的坐标是(0 2 2 4 4 17 17 19 19 20 20 19 19 17 17 4 4 2 2 0; 2 2 0 0 2 2 1 1 2 2 4 4 5 5 4 4 6 6 4 4)。

图2 两个图形对比

从图2中两个图形的对比图可以看出，相似图形比用户输入图形多出了两个矩形区域。采用本文所提出的方法后，正确的从相似图形的特征点中选取了与输入图形特征点近似的点。

4.2 检索图形

用户输入图形特征点的坐标为(0 20 15 30 15 20 0; 5 5 0 7 14 9 9)。

近似图形1（图3(a)）的特征点为(0 20 15 28 28 15 20 0; 5 5 0 5 9 14 9 9)；

近似图形2(图3(b))的特征点为(0 30 15 50 15 30 0; 5 5 0 7 14 9 9)；

近似图形3(图3(c))的特征点为(0 4 4 20 15 30 15 20 4 4 0; 5 3 5 5 0 7 14 9 9 11 9)；

近似图形4(图3(d))的特征点为(0 20 45 30 45 20 0; 5 5 0 7 14 9 9)。

图3 相似图形与输入图形

用户输入图形与相似图形1, 2, 3, 4的标准差Sn的值分别是：0.0395，0.6780，0.0148，0.3696。因此，图3(c)与用户输入图形最为接近，与直观感受相同。

除此之外，在每个相似图形中，还标出了与用户输入图形最接近的点，并在形似图形的基础上形成与用户图形最接近的图形，方便用户对检索到的图形做后续处理。

4.3 旋转和平移特性

在检索过程中，相似图形的放置方式可能与用户输入图形不一致，如图4所示。

图4 对比图

图4(a)表示图形旋转后，依然可以进行有效检索。图4(b)表示图形经过平移后，依然可以进行有效检索。

4.4 一般多边形

为更加普遍的验证该方法，现对一般多边形[6]进行验证。表1公布了各个图形的Sn值，通过查阅此表，便可得出图形和图形之间的相似程度，从而判断出是否为相同图形。

表1 图形Sn值之间相似程度比较

从表1可以看出，即使是相近的图形，Sn值也相差较大，通过控制不同图形之间Sn值之差，可以方便地控制检索的近似度。

4.5 检索性能分析

本文在cpu corei3；内存6G，window7的环境下进行测试，测试对象为100张机械图纸，得到图5的查准查全图。其中纵坐标为查准率，横坐标为查全率。

图5 查准率、查全率全图

5 总 结

在众多基于图形的检索方法中，本方法的优势在于对图形的预处理较为简单，检索速度较快。但由于检索指标较为单一，对于复杂图形来说，检索的准确率会有所降低。

本文提出的图形检索方法，通过一个图形数组来描述图形，然后相似图形数组的数字特征来完成检索。在检索系统中，对于每个图形仅仅需要存储一个数组，大大节约了存储成本，提高了检索速度。另外，可以通过提高存储在数据库中的检索数据的精确度和降低模糊查找系数来避免检索数据重复的问题或实现精确检索的目的。经过试验，本方法的具有较高的可靠性和有效性。

[1]王林军.基于STEP零件属性图形的检索和对比研究[J].甘肃科学学报, 2007, 19(3): 96-99.

[2]沈兰荪, 张 菁, 李晓光.图像检索与压缩域处理技术的研究[M].北京: 人民邮电出版社, 2008: 12.

[3]余 淼.基于内容的线画图形检索研究进展[J].电脑知识与技术, 2008, 4(S2): 80-82.

[4]王 桦.基于分层和反馈技术的矢量图形检索研究[EB/OL].http://cdmd.cnki.com.cn/Article/CDMD-10335-2006033216.htm.2006.

[5]王炳忠.基于分层结构的矢量图元检索方法[J].浙江工业大学学报, 2008, 36(5): 499-508.

[6]梦祥辉.基于内角向量的二维图形几何相似性匹配方法[C]//2006年学术年会.西安: 西安电子科技大学, 2006.