图形相似的基本原理_方法及其在结构模式识别中的应用.pdf
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_1.gif)
![资源得分’ title=](/images/score_05.gif)
《图形相似的基本原理_方法及其在结构模式识别中的应用.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)为原形),这些图形具有相同的拓扑结构,根据式
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 图形 相似 基本原理 方法 及其 结构 模式识别 中的 应用
![提示](https://www.deliwenku.com/images/bang_tan.gif)
限制150内