图形相似的基本原理_方法及其在结构模式识别中的应用.pdf

《图形相似的基本原理_方法及其在结构模式识别中的应用.pdf》由会员分享，可在线阅读，更多相关《图形相似的基本原理_方法及其在结构模式识别中的应用.pdf（9页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第25卷第9期2002年9月计算机学报CH I N ESE J1COM PU TERSVol.25 No.9Sept.2002图形相似的基本原理、方法及其在结构模式识别中的应用谭建荣岳小莉陆国栋(浙江大学CAD&CG国家重点实验室杭州310027)收稿日期:2001208214;修改稿收到日期:2002201210.本课题得到国家自然科学基金(69878038)、国家“八六三”高技术研究发展计划C I M S主题(8632511298422006)以及浙江省自然科学基金(696045)资助.谭建荣,男,1954年生,教授,博士生导师,主要从事产品信息建模、CAD、工程信息可视化等方面的研究.E

2、2mail:.岳小莉,女,1971年生,博士研究生,主要从事工程图样计算机理解、人工智能与模式识别等方面的研究.陆国栋,男,1963年生,博士,教授,主要研究领域为智能CAD、三维重建、工程图样计算机理解等.摘要将相似的有关思想和方法引入到图形识别和理解中,系统地讨论了图形相似的基本原理和方法.首先分析了图形的相似性特征、相似性的内涵以及相似性的性质,同时给出了图形相似度的计算方法;其次,借助图的方式对图形的各相似性特征进行描述,并提出了统一的图形特征编码方式,以此实现图形由“形”到“数”的转换;而且,提出了一种具有层次性的、以图形特征编码为基础、以相似度为依据的图形相似性判别算法;最后,将该

3、方法应用于基于二维的结构模式识别中,以一个实际零件中的非相交基元体的识别为例说明了该方法的具体应用.实验结果表明,与传统的识别方法相比较,该方法在模式的识别范围、模式的搜索以及模式的匹配速度等几个方面取得了较大进展,并且这种基于多个相似性特征的图形识别方法具有更大的灵活性和可靠性.关键词图形相似,相似性特征,相似度,图形编码,结构模式识别中图法分类号:TP391Basic Principle,M ethod of Graphic Si m ilarityand Its Application to Structure Pattern Recogn itionTAN Jian2RongYU E

4、Xiao2L iLU Guo2Dong(S tate K ey L aboratory of CAD&CG,Zhejiang U niversity,H angzhou310027)AbstractIn this paper,the sim ilarity idea and some corresponding method are introduced into2D graphic recognition and understanding,and the basic principle and approaches of 2D graphicsim ilarity are systemat

5、ically provided.The prem ise of this paper is established on the follow ingfacts,that sim ilarity among different graphic existed in many aspects,such as,topology struc2ture sim ilarity,geometry shape sim ilarity,express function sim ilarity,and so forth.A s to thesame sim ilarity features,the sim i

6、larity can be further separated out from each other according totheir different sim ilarity degrees.In this paper,the basic principle and methods of graphic sim i2larity are discussed as follow s.Firstly,the sim ilarity of 2D graphic is analyzed,including sim ilar2ity features,sim ilarity connotatio

7、n and sim ilarity property,then the computation method of sim i2larity degree is put forward.Secondly,the graphic features are described by means of graph,while the graphic coding mode is proposed at the same time,w ith which the graphic can bechanged into digital.In the follow ing,taken graphic cod

8、e as the source and sim ilarity degree asthe basis,a hierarchy discrim ination algorithm of graphic sim ilarity is brought forward.A t theend,more details are provided to illustrate the structure pattern recognition using this approach.The experimental results show that some improvements are obtaine

9、d by using this method,suchas the pattern recognition scope,the speed of pattern searching and matching,etc.Furthermore,the new algorithm has stronger flexibility and stability compared w ith those traditional ones.Keywordsgraphics sim ilarity,sim ilarity feature,sim ilarity degree,graphic coding,st

10、ructurepattern recognition1引言图形相似是画法几何与计算机图形处理中的一个基本问题,许多与图形识别处理相关的研究都涉及到图形相似,如工程图形识别理解、特征识别、模式识别、分形、甚至制造领域中的成组技术等等,因此对它的研究具有非常重要的实际意义和广泛的应用价值.鉴于不同领域的研究对象所具有的不同特性,加之研究角度及方法也有所差异,本文将研究范围限定在二维图形相似性识别的基本原理和方法上.从人对图的认知过程来看,人们往往是将识别的图形信息与头脑中已有的模式不断地进行比较、验证,是一个由粗到精、由主体到细节、由模糊到清晰的过程;同时,由于图形之间所具有的诸多可比较性和相似性

11、,这一过程又具有某种程度上的不确定性和非严格性.从相似的观点来看,图形间的相似性覆盖了与图形有关的拓扑结构、几何形状以及图形的表达功能等多个方面;并且在同一相似性特征中,又有不同的相似程度之分,即图形的相似存在于不同层次、不同方面.虽然文献1对相似问题做了较为系统、深入的研究,然而,从拓扑结构、几何形状和表达功能等多个方面研究图形的相似性,并运用图形相似原理解决图形识别问题,却是一个新的研究课题.本文通过对图形相似性特征的分析,提出了图形相似的基本原理和方法,利用各相似性特征所具有的内在逐层递进式关系来实现对图形的识别,并将这一方法应用于基于二维的结构模式识别2中.由于利用了图形间的相似性特征

12、,新的方法在图形的特征描述、模式的可识别范围、模式识别的效率以及可靠性等几个主要环节上对以往的识别方法36进行了较大的改进.2图形相似的基本原理图形相似是指图形之间在拓扑结构、几何形状以及表达功能上的相似程度.在图形识别和理解中,图形的相似性是识别和理解相似图形的基础,图形的相似性特征是判断其相似性的依据,相似度是用来度量其相似程度的当量尺度.而基本几何元素、相关的符号元素以及它们之间的关系则是图形及其相似性特征的基础,下面集中介绍这些基本概念.2.1图形的属性和特征图形是指由基本几何元素及其相互关系所构成的一个集合体,本文识别和处理的图形是封闭的二维单连通域,线、圆弧等基本几何元素及其相互关

13、系是其主要构成要素,例如,几何构成元素的数量、类型以及各几何元素的连接顺序、连接方式等会直接影响到图形的真实形状;另外,在实际工程图纸中,往往有相关的尺寸对其进行约束,用以确定它的实际大小或表明它所表达的空间形体类型.以下列出图形的主要特征及其属性,并以数字的形式对不同的属性进行标识.这些图形特征将成为判别图形相似的基础.(1)图形的几何构成元素的数量;(2)几何构成元素类型;属性值为:0表示直线段;1表示圆弧;2表示圆;3表示样条曲线.(3)几何构成元素的邻接状态;即按照顺(逆)时针方向,与当前几何元素相邻的下一个几何元素的类型.(4)邻接几何构成元素的连接方式;属性值为:0表示垂直连接;1

14、表示锐连接(夹角 90);2表示钝连接A(90夹角 180);4表示相切连接;5表示相割连接;6表示其它连接方式(如零件上的某些工艺结构:圆角、倒角等).如图1所示,按照逆时针方向,a与b为垂直连接,b与c为钝连接A,c与d为锐连接,d与e为钝连接B,e与f为相割连接,f与a为相切连接.(5)几何构成元素的尺寸约束状况;属性值为:0表示无尺寸约束;1表示线性尺寸;2表示直径类尺寸;3表示半径类尺寸;4表示球径类尺寸;5表示螺纹类尺寸.069计算机学报2002年(6)图形的对称性;以该图形中是否存在对称中心线为依据,它的属性值为:0表示不对称;1表示对称.2.2图形的相似性分析第2.1节中所列出

15、的图形的主要特征,不难看出,它们分别对应于图形的拓扑结构、几何约束以及尺寸约束,同时它们也是识别图形相似的重要特征.因此本文着重从这几个方面来分析图形的相似性.2.2.1图形相似性的定义定义1.拓扑结构相似.如果两个图形的几何构成元素的类型及其连接顺序为一一对应,则称二者拓扑结构相似.定义2.几何形状相似.如果两个图形拓扑结构相似,并且其几何构成元素的邻接方式(垂直、相切连接等)也是一一对应的,则称二者几何形状相似.定义3.尺寸约束相似.如果两个图形拓扑结构相似,并且其上的尺寸约束(包括尺寸数量和类型)为一一对应,则称二者尺寸约束相似.显然,以拓扑结构相似为前提,当两个图形满足几何约束条件或尺

16、寸约束条件时,二者具有几何形状相似或尺寸约束相似;进一步地,当二者满足尺寸约束条件或几何约束条件时,它们具有严格意义上的相似,即这样的两个图形不仅“形”相似,而且“表达功能”相似,即它们对应于同一类型的三维形体(例如同样的矩形既可以是某一长方体的面投影,又可以是某一圆柱体的侧视投影,只有尺寸约束情况相同时,它们才对应于同一类型的形体.这种情况在工程图样中较为常见).这也是我们在图纸识别中所需要做到的.此外,从图1中可以看出,对于两个具有严格相似性的图形的匹配过程可以有两个途径(图中以箭头标识),即在拓扑结构相似的情况下,可以选择几何约束和尺寸约束中的一种进行下一步的判断,具体选用情况根据图形的

17、类型而有所区别.从另一个角度而言,对图形的匹配过程是一个由粗到精、逐层递进的过程,只有具备前一种相似性,才可能具备后面的相似性.三者之间的关系可以通过图2来表示.2.2.2图形相似性的性质图形相似性的性质是针对图形之间在各相似性特征上所表现出的相似性而言.图3所示为一组相似图形,图形的几何构成元素的数量均为8,其中图3(a)是原形.广义地看,图3中的几个图形都在某种程度上与图3(a)具有相似性,但它们的相似性特征又不尽相同,表现出多样性.根据定义,表1列出了图3(b)图3(h)在不同的图形特征上所具有的相似性.表1图形的相似性图形特征拓扑约束相似性几何约束相似性(b)完全部分(c)完全完全(d

18、)完全部分(e)完全部分(f)完全部分(g)完全部分(h)部分部分对应于图形的各相似性特征(如拓扑结构相似、几何形状相似或尺寸约束相似等),通过对图形各特征属性(如图形的几何构成元素数量、几何构成元素的类型、元素连接顺序和邻接方式等等)的比较、判断,可以确定图形间所具有的相似性的性质.结合上述图形相似性特征的定义,给出如下相关定义.定义4.确定性相似.如果两个图形完全符合定义1、定义2或定义3的条件,则称二者为确定性相似,分别为确定性拓扑结构相似、确定性几何形状1699期谭建荣等:图形相似的基本原理、方法及其在结构模式识别中的应用相似以及确定性尺寸约束相似.定义5.模糊性相似.如果两个图形的几

19、何构成元素的数量相同,但只是部分满足定义1、定义2或定义3的条件,则称它们为模糊性相似.分别为模糊性拓扑结构相似、模糊性几何形状相似以及模糊性尺寸约束相似.实际中,图形之间的相似性往往表现为模糊性相似.由于模糊性只是一个定性的概念,它表示图形之间具有一定的相似性,但又不完全相似,若要更为清楚地认识图形之间的相似程度,则必须借助于相似度.2.3图形的相似度有关相似度的研究,在文献1中有较为系统的论述,但对图形的相似性涉及不多.作者将图形相似限定在几何学中相似图形的定义范畴内,即当图形的有关特征(如夹角、边等)可进行线性变换时,图形才具有相似性.例如,对于几个大小不等的等边三角形,文献中的方法是根

20、据它们的大小比例关系来区分出它们之间的不同相似程度.这种方法适用于对简单多边形的精确相似性分析,但在图形的识别和理解中并不完全适用,这是因为图形识别和理解的目的在于识别出图形所属的形状范畴,如对于三角形,不管其大小或具体形状(等边、等腰、直角)如何,从其形状范畴而言,它们都是三角形.因此,在对图形相似度的分析中,充分考虑到图形相似中的模糊性,扩大了以往对图形相似性的理解范畴.对应于图形相似性的几个特征,本文给出图形在拓扑结构、几何形状以及尺寸约束上的相似度的计算方法.参考第2.1节中所列出的图形的主要特征,其中几何构成元素类型(C1)和几何元素的邻接状态(C2)与图形的拓扑结构相关;除此之外,

21、几何元素的连接方式(C3)和图形的对称性(C4)与图形的几何形状有关,而几何构成元素的尺寸约束状况(C5)则与图形的尺寸约束相关.这些特征是计算各相似度的相似要素,并且认为这些相似要素对图形各相似性判断的影响是同等重要的.此外,由于图形是由基本几何元素(如线、圆、圆弧等)构成的,因此,在对图形各相似要素进行分析时,这些几何元素将被当作是各相似要素的相似元素.假定图形A与图形B的相似要素个数为M,各相似要素的相似元素个数为N,则图形相似度的计算方法如下QAB=Mi=1Nj=1ijqij?(MN)(1)式(1)中,QAB是图形A和图形B的相似度,qij代表各相似要素的相似元素,ij为各相似元素的相

22、似系数(确定方法见后).由于不同相似特征的相似要素不同,其中拓扑结构相似度的相似要素为2个(C1,C2);几何形状相似度的相似要素为4个(C1,C2,C3,C4),尺寸约束相似度的相似要素为5个(C1,C2,C3,C4,C5),其中对称性与图形的整体结构有关,识别方法与其它的相似要素有所区别,计算时需单独计作一项.因此根据式(1),它们的相似度分别为拓扑结构相似度(QT(AB)QT(AB)=2i=1Nj=1ijqij?(2N)(2)几何形状相似度(QG(AB)QG(AB)=3i=1Nj=1ijqij+sqs(3N+1)(3)尺寸约束相似度(QD(AB)QG(AB)=4i=1Nj=1ijqij+

23、sqs(4N+1)(4)式(3)和式(4)中的qs代表图形对称性的相似元素(即图形中是否存在对称中心线),s为其相似系数.从上述相似度的计算方法可以看出,相似度计算的一个关键在于如何确定各相似元素的相似系数,因为它直接关系到图形相似性判断的准确性.在第2.1节中,对应于各图形特征,给出了其属性值,当两个图形进行相似性比较时,如果相应的相似元素的属性值相同,则其相似系数为1;如果不同,则根据该特征属性在相关的相似性判断中所起的影响程度做如下约定:(1)几何元素类型.当属性值在(0,1,2,3)中变动时,其相似系数为0.25;(2)几何元素的连接方式.当属性值在(0,6)中变动时,其相似系数为0.

24、75;当属性值在(0,6)与(1,2,5)中变动时,其相似系数为0.5;当属性值在(0,1,2,6)与(3,4)中变动时,其相似系数为0;(3)几何元素的尺寸约束状况.当属性值在(2,3)中变动时,其相似系数为0.75;当属性值在(2,3)、(1,4,5)以及(0)中变动时,其相似系数为0;(4)图形的对称性:当属性值在(0,1)中变动时,其相似系数为0.相似度Q=1时,表示两图形在某一特征上完全相似,即两图形为确定性相似;Q=0,表示两图形269计算机学报2002年在某一特征上相异;0Q 1,则表示两图形为模糊性相似.以图4中的图形为例(图4(a)为原形),这些图形具有相同的拓扑结构,根据式

25、(3),它们与图4(a)的几何形状相似度分别计算如下:QG(ab)=(1+1+1)+(1+1+1)+(1+1+1)+(1+1+1)+1)?(34+1)=1,QG(ac)=(1+1+0.5)+(1+1+0.5)+(1+1+1)+(1+1+1)+1)?(34+1)0.92,QG(ad)=(1+1+0.5)+(1+1+0.5)+(1+1+0.5)+(1+1+0.5)+1)?(34+1)0.85,QG(ae)=(1+1+0)+(1+1+0.5)+(1+1+1)+(1+1+0.5)+1)?(34+1)0.85.可见,图4(b)与图4(a)确定性相似,图4(c),图4(d)和图4(e)与图4(a)模糊性相

26、似,其中图4(c)的相似程度较大.该方法同样适用于文献1中对图形的精确相似性分析,当相似要素为图形边、角的对应比例时,可得到相同的计算结果.3图形相似的识别方法从图论的观点来看,每个图形都是一个图,其中结点为图形的几何构成元素,连接弧表示元素的邻接关系,由于在实际绘图过程中没有固定的绘制顺序,因此这样的图是无向图.这些图形是计算机识别理解的对象和基础,其描述方式直接影响着计算机识别的方法、效率以及识别的可靠性和有效性.在前文分析图形相似性特征的基础上,这部分首先以图的方式对图形的特征进行描述;接着以编码的形式对图进行数字化转换,以便于计算机的处理;最后,给出了基于编码的图形相似识别方法.3.1

27、图形的相似性特征描述图形的主要相似性特征包括拓扑结构、几何形状以及尺寸约束状况,它们都有各自相似要素以及相似元素,借助于图的方式可以对图形及其特征进行描述.图5所示为四边形及其特征描述方式.图5中,1表示线段a;2表示线段b;3表示线段c;4表示线段d.A12表示线段1,2之间的连接方式;A23表示线段2,3之间的连接方式;A34表示线段3,4之间的连接方式;A41表示线段4,1之间的连接方式.D1,D2,D3,D4分别为线段1,2,3,4上的尺寸约束值;当几何元素上无尺寸约束时,相应的Di为空值(NULL).从图5中我们可以提取出图形的各相似性特征并以此进行图形间的相似性比较.例如,只要相应

28、的图的结点类型和结点邻接状态相同,则两图形为拓扑结构相似;进一步地,考虑连接弧上的赋值(即相邻元素的连接方式)可以比较图形在几何形状上的相似性.此外,根据定形的要求,每个图形都有与之相对应的尺寸标注方式,当图形绘制不够准确时,尺寸即成为唯一可靠、正确的参考标准;并且,当图形为三维形体在某一方向上的投影时,它又是区分具有相同投影而类型不同的形体的重要依据.因此利用尺寸信息可以对具有相似几何形状的图形进行表达功能上的相似性比较.3.2基于相似性特征的图形编码对图形进行编码,本质上是将几何上“形”的概念转化为便于计算机处理的“数”的形式.为了实现图形的相似性比较,编码应该包含与此相关的相似性特征信息

29、,图6给出了本文所制定的图形的特征编码方式.其中,V为视图码,用于标识该图形所处的视3699期谭建荣等:图形相似的基本原理、方法及其在结构模式识别中的应用图,在基于多视图的图形识别和理解中是必需的,它的属性值为:F表示主视图;T表示俯视图;S表示左视图;.N是代表图形的几何构成元素的数量,作为分类码以区分边数不同的图形,对两个图形进行相似性比较的前提是二者的边数相同.E1,E2,EN为图形的各几何构成元素的属性码,元素的排列顺序与它们在图形中的连接顺序一致,元素的属性包括以下三个方面的内容:类型、与下一个元素的连接方式以及其上的尺寸约束信息.从属性码中可以提取出与图形相似性特征相关的各相似要素

30、及其相似元素的信息,以此作为图形相似性判断的主要依据.此外,图形的对称性S被当作辅助码,可以对图形的相似程度进行进一步的判断,例如对于属性码相同的两个图形,二者同时具有(或不具有)对称性比之只有其中一个具有对称性具有更大的相似程度.图7所示为一些带尺寸标注的二维图形,按照以上的编码方法,它们的特征编码见表2.其中编码各属性值的取值见第2.1节中的定义.表2图形的特征编码图号VNE1E2E3E4S(a)-40000010010000(b)-40000010020001(c)-40311310301301(d)-40400410400400(e)-40220100120200(f)-4021011

31、0110200(g)-41330000110301(h)-12-41(i)-12-21(j)-2021241以图7(d)为例,其编码为V4 040 041 040 0400,从中可以知道它的边数为4;几何构成元素类型和连接顺序为:直线2直线2直线2直线;几何元素间的连接方式均为圆弧过渡连接;尺寸约束状况为:一条直线上存在线性尺寸约束;图形中无对称中心线.按照这种方式,我们可以对大部分的二维图形进行描述.3.3基于编码的图形相似识别方法根据图形的相似性特征,对图形相似性的比较可以分别从拓扑结构、几何形状以及尺寸约束三个方面进行;而对应于每一个相似性特征,图形的相似又有确定性相似和模糊性相似之分.

32、其中,前一种可以直接通过比较二者特征编码中的属性值是否一一对应来加以确认,而对后一种情况的识别则需要计算二者的相似度来进行判断.识别算法如下.Step1.从图中的某一几何元素出发,搜索得到一个以该几何元素为边界的单连通域,将之记为P;Step2.对P进行特征编码;Step3.从属性码中选取与拓扑结构相关的值,即边数N、几何构成元素类型Ei1以及各几何元素的邻接状况(即识别码中各几何元素的连接顺序),可以表示为:NEi1E(i+1)1E(i+2)1En1,由此得到P的拓扑结构特征码;Step4.将P与已有图形进行拓扑结构的相似性比较,即根据式(2)计算二者的拓扑结构相似度QT,如果QT=1,则二

33、者的拓扑结构为确定性相似,转下一步;否则,当0QT 1时,二者具有拓扑结构模糊相似;当QT=0时,二者拓扑结构完全不相似,转Step9;Step5.从属性码中选取与几何形状相关的值,即各相邻几何元素之间的连接方式Ei2,由此得到P的几何形状特征码;Step6.将P与具有确定性相似拓扑结构的图形做几何形状的相似性比较,即根据式(3)计算二者的几何约束相似度QG,如果QG=1,则二者具有几何形状确定相似,转下一步;否则,当0QG 1时,二者具有几何形状模糊相似;当QG=0时,二者几何形状完全不相似,转Step9;Step7.从属性码中选取与尺寸约束相关的值,即各相邻几何元素的受约束情况Ei3,由此

34、得到P的尺寸约束特征码;Step8.将P与具有确定性相似几何形状的图形做尺寸约束的相似性比较,即根据式(4)计算二者的尺寸约束相似度QD,如果QD=1,则二者的尺寸约束情况确定性相似;否则,当0QD 1时,二者具有尺寸约束模糊相似;当QD=0时,二者尺寸约束情况完全不相似,转下一步;Step9.结束.从算法中可以看出,由于提供了多个可供比较的相似性特征并增加了相似度的定义,使得图形的匹配和识别过程突破了以往简单的判别方式,即“要么是,要么非”,从而具有了更大的灵活性和可操作性,同时又扩大了图形的可识别范围.例如,在图形的模式匹配中,当两个图形不完全相同时(即模糊性相似),如果应用传统的方法,对

35、它的识别会以失败告终,导致无法识别该图形;应用本文的方法,则可以最大限度地将它与已有的图形进行相似性的比较469计算机学报2002年和判断,当满足相似度的要求时,将它归入某一类图形中以完成对它的识别.此外,由于各相似性特征所固有的逐层递进式的内在逻辑关系(参照图1),因此图形的相似性判别是在逐层筛选、由粗到精的过程中进行的,从而避免了大量的冗余操作.在实际应用中,可以根据具体的要求对图形进行不同相似性特征的比较.4图形相似方法在结构模式识别中的应用结构模式识别是图形理解和特征识别中的一项关键技术,在二维环境下进行结构模式识别是要通过搜索、识别不同视图中的相关环来假定并验证某个三维子体结构的存在

36、,从而实现该结构模式的识别.识别过程主要包括以下几个环节:模式库建立、二维环搜索及其特征编码以及模式识别.结合第3.3节中有关图形相似的识别方法和主要步骤,基于二维的结构模式识别的流程如图8所示.图8中的预处理过程是指通过尺寸类型的识别,找到受定形尺寸约束的几何元素.这是因为在实际工程应用中,所处理的对象通常是二维工程图纸,其中包含完整的尺寸信息.传统的图形搜索方法通常是对各视图中可能存在的各种封闭环进行搜索,并进行相应的组合,这种方法的不足在于:搜索过程中缺乏知识的引导,存在着大量冗余操作;同时,随着形体复杂度的增大,会造成环组合搜索的爆炸,且常常会产生假解.因此,图形搜索的关键在于如何缩小

37、搜索空间以及如何提高搜索的可靠性和有效性.针对这一问题,我们将尺寸约束信息引入图形搜索过程中,根据定形尺寸对图形的约束功能将之作为搜索过程中的引导信息.从定形尺寸所约束的几何元素出发,可以快速而有效地搜索到相关的封闭环.对定形尺寸的识别,可以通过将视图中易于识别的定位尺寸和总体尺寸区分出来进行初步的确认,有关尺寸类型的识别规则见附录.我们以一个实际零件中的非相交基元体的识别为例来说明图形相似方法在结构模式识别中的具体应用.图9所示为轴承座及其三视图,这里以轴承座的底板为识别对象进行说明.(1)模式库建立.附图1中列出了零件中常见子体结构及其在三视图中的投影(尺寸略),根据第3.2节的编码方式分

38、别对它们进行编码,即每个子体结构对应三组编码,以此建立相应的模式库.(2)识别预处理.根据尺寸类型的识别规则,图中打圈的尺寸是定位尺寸,其余的为定形尺寸.(3)二维环搜索及其特征编码.从主视图中的尺寸15出发,可以搜索得到一个由实线构成的封闭环,它的特征编码为(a):F 8 001 000 000 000 000001 001 000 1;根据投影关系,它在左视图中的对应封闭环为受尺寸63约束的矩形,其特征编码为(b):S 4 000 000 001 000 0;同理,它在俯视图中的投影为受尺寸116约束的封闭环,其特征编码为(c):T 4001 040 040 000 1.假定(a),(b)

39、,(c)三组编码对应5699期谭建荣等:图形相似的基本原理、方法及其在结构模式识别中的应用一个子体结构,将它与模式库中的模式进行比较.(4)模式识别.根据第3.3节中的算法将它们与模式库中的模式进行相似性比较,其中(a),(b)与已有模式为确定性相似,(c)为模糊性相似(由相似度计算得到它与矩形相似,其区分特征为相邻元素的连接方式圆角过渡).最后,根据它们在视图中的分布情况(综合考虑视图码)可以将它们所表达的结构与附图1中的(i)进行匹配,识别成功,即该组图形所表达的三维形体与附图1(i)相似.另外,在具体的识别过程中需要注意的一个问题是:这类基元体中往往带有一些从属体特征(如孔),对它们的识

40、别同样可以应用图形相似性判别算法,即从直径类尺寸出发,搜索得到它在各视图中的投影域(二维图形),对其进行编码后将之与已有模式进行相似性比较、识别.识别出的完整投影信息被记录下来以避免在后续识别过程中造成对相关环搜索的干扰.有关三视图中与基元体识别相关的内容在文献7已有详细论述,这里不再赘述.5结论基于对自然界中普遍存在的事物间的相似性这一认识,首次将相似性的概念引入到图形的识别过程中,系统地研究了图形相似的基本原理和方法,并将之应用于结构模式识别中.与传统的结构模式识别方法相比较,该方法在以下几个方面取得了较大的进展:(1)在模式的识别范围上,由于将图形的相似性分为确定性相似和模糊性相似,可以

41、对具有模糊性相似的图形进行识别,从而拓宽了图形及其所表达模式的识别范围;(2)在模式的建立方法上,以编码的方式将图形由“形”转变为便于计算机处理的“数”,进而建立相应的模式库,通过从中提取相关的特征属性值可以加快图形相似性比较的速度;(3)尺寸约束信息被用于引导图形的搜索,避免了以往图形搜索过程中大量盲目、冗余的工作,提高了搜索的有效性;(4)基于多个相似性特征的图形识别过程,增加了图形之间的可比较性,使得整个识别过程更具灵活性和可靠性.进一步的研究将集中于以下几个方面:(1)目前的识别对象主要限于具有均匀厚度的形体,今后将增加对具有非均匀厚度形体之间相似性特征的描述,逐步实现对更为复杂形体的

42、识别;(2)模糊性是图形相似的一个重要性质,也是其中的一个难点,将继续对这一性质做更为深入的研究;(3)将图形相似的理论和方法应用到相关领域的研究中,例如参数化设计方法,因为参数化设计方法中的约束问题与本文所论及的二维图形的拓扑结构相似特征和尺寸约束相似特征是一致的.参考文献1ZhouM ei2L i.Sim ilar Engineering.Beijing:Engineering Indus2try Press,1998(in Chinese)(周美立.相似工程学.北京:机械工业出版社,1998)2A ldefeld B.On automatic recognition of 3D stru

43、cture from 2Drepresentations.Computer2A ided Design,1983,15(2):59-643GongM ao2Kai,Gao Guo2An,ShiM iao.A survey of construc2tion methods of 32D objects from three2view draw ings.Journalof Computer Research and Development,1992,24(8):47-52(inChinese)(公茂凯,高国安,石淼.由三视图构造三维实体方法的综述.计算机研究与发展,1992,24(8):47-5

44、2)4W ang Dong2Quan.A survey:A lgorithm s for reconstructing 3Dsolids from 2D orthographic projections.Computer Applicationsand Software,1995,(1):55-59(in Chinese)(王东泉.由二维正投影重建三维实体算法的评述.计算机应用与软件,1995,(1):55-59)5Lee2W en Tyan,Venkat D.Automatic identification of non2in2tersecting machining features fr

45、om 2D CAD input.Computer2A ided Design,1998,30(5):357-3666Case K,Gao J.Feature technology:An overview.InternationalJournal for Computer Integrated M anufacturing,1993,6(12):2-127Yue Xiao2L iet al.Research on 3D reconstruction based on mul2ti2level pattern matching.Pattern Recognition and A rtificial

46、 In2669计算机学报2002年telligence,2000,13(3):205-209(in Chinese)(岳小莉 等.基于多层次模式匹配的三维重建技术研究.模式识别与人工智能,2000,13(3):205-209)附录1.规则1.当尺寸的一端或两段引出线与中心线相连时,该尺寸为定位尺寸;规则2.当尺寸的一端或两端的箭头落在中心线或中心圆或圆弧上时,该尺寸为定位尺寸;规则3.当某一线性尺寸值等于由三视图包围盒所确定的总宽、总高或总长时,该尺寸为侯选总体尺寸;规则4.当尺寸为侯选总体尺寸时,若存在以该尺寸所约束几何元素的部分为界的子环(线型相同),则该尺寸为总体尺寸;规则5.当尺寸为侯

47、选主体尺寸时,如果该尺寸的一条尺寸界线同时也是其它尺寸的尺寸界线并且在这些尺寸中至少有一个尺寸不满足规则1和规则2时,该尺寸为总体尺寸.TAN Jian-Rong,male,bornin1954,professor at Zhejiang U niversity.H ismain research topics are product in2formation modeling,Computeraideddesign and engineering information visu2alization,etc.YUE Xiao-L i,female,born in 1971,Ph.D.cand

48、idateat Zhejiang U niversity.Her current research interests in2clude engineering draw ing understanding,artificial intelli2gent and pattern recognition.LU Guo-Dong,male,born in 1963,professor at Zhe2jiang U niversity.H is research interests include intelligentcomputer aided design,3D reconstruction and engineeringdraw ing understanding.7699期谭建荣等:图形相似的基本原理、方法及其在结构模式识别中的应用