维普资讯

2 00 5生

工程图学学报JoURNAL oF ENGI NEERI NG GRAPH I CS

2 0 0 5NO . 4

第 4期

智能图元特征提取与图形匹配技术刘就女， 吴东庆2, 彭小敏， 李哲林f 1 .华南理工大学工业设计与图学研究所，广州 5 1 0 6 4 0;2 .仲凯农业技术学院，广州 5 1 0 2 2 5

3 .中国工商银行广州软件研发中心，广州 5 1 0 6 3 0 )

摘

要：实现作业的智能化批改是本课程多年来未能突破的技术难点，作者要解决

的正是这难点。其关键技术是图元特征提取与图形匹配，它为智能化批改的算法、设计与实 现做了理论上的准备。并找到了图形匹配的方法，研究了图形匹配技术，并且成功地利用图 形匹配技术，实现了规则图元和非规则图元 (曲线 )的智能批改。 关键词：计算机应用；智能化批改；算法设计；二次开发工具中图分类号：T P 3 9 1文献标识码：A文章编号：1 0 0 3 - 0 1 5 8 ( 2 0 0 5 ) 0 4— 0 1 4 6 - 0 5

工程制图作业的智能化批改是电子习题系统开发的难点，多年来，在一些高校开发的、各具特点的工程制图电子习题集系统中仍没有得到解决 J。 电子习题集系统的智能批改功能，只能实现规则图元 (直线、圆、圆弧等 )的批改，且要求完全匹配，对于短画、分段画等部分匹配的情况在批改时就不能处理。对于相贯线等非确定、非规则图元更不能做到智能化批改L 2 J。 作者研究的图元及特征提取与图形匹配技术是智能化作业批改系统开发过程中的关键技术，它为智能化批改的算法、设计与实现做了理论上的准备。这技术由两个过程体现：( 1 )图元及特征提取过程提取标准答案

和错误的图元。

1 图元及特征提取技术提取 Au t o C AD图形中的图元信息，实际上就是遍历 d wg图形数据库中所有图元并获得其信息。 数据库中实体 (图元 )通常属于一个块表记录。创建出来的新块 (如执行 B L OC K, H A T C H

或 D I ME NS I O N命令),被添加到块表记录中。对实体的遍历访问，是通过实体在数据库

中结构的从属关系进行。1 . 1图元的遍历遍历图元用到的浏览器主要是块表记录浏

和学生提交的作业的 d wg图形中的图元信息，分别存入各自的用于保存这些图元信息的数据库中。

览器 Ac Db B l o c k T a b l e R e c o r d l t e r a t o r。读取了模型

空间中所有实体，就是读取了数据库中所有实体，大概需要经过以下步骤：①获得 d wg文件的数据库对象指针；②通过数据库对象指针， 获得数据库的块表指针；③通过该块表指针， 获得数据库的模型空间的块表记录指针；④最后通过已获得的块表记录指针，得到块表记录浏

( 2 )图形匹配过程图元提取过后，已获

得的标准答案和提交的作业的所有图元信息，通过图形匹配技术，判断提交的作业中正确的图元

收稿日期：2 0 0 4— 0 1— 2 1 作者简介：刘就女 ( 1 9 4 7一 ) .女 .广东东莞人 .副教授 .主要研究领域为计算机图学、G I S。

维普资讯

第 4期

刘就女等：智能图元特征提取与图形匹配技术El s e

览器。代码实现如下：Ac D b D a t a b a s e * a c D b;//数据库对象指针

Af x Me s s e n g e r (”该实体不是直线！” );

a c D b￣ - a e w Ac D b Da t a b a s e ( t r u e, t r u e );//实例化数据库对象指针

至此，已经全面透析了 Au t o C AD图形的数据库结构，掌握了其中所有图元及其特征信息的提取技术，为图形匹配做了技术准备。

a c D b -> r e a d Dwg F i l e (” D:\ k D w g M. d wg", _ S H _ D E N Y NO, t r u e );//将D:\ k D wg M. d w g文件的读入到数据库a c D b中，Ac Db Bl o c k Ta bl e pBl o c kTa b l e;

2图形匹配技术智能批改的过程，即是提取标准答案和学生提交的作业中的所有图元及其特征信息后，通过图形匹配技术，找出提交作业相对标准答案之间

//通过数据库指针，获得块表指针a c Db -> g e t Bl o c k T a b l e ( p B l o

c k T a b l e, Ac Db:: k F o r Wr

i t e );Ac DbBl o c k Ta b l e Re c o r d p Bl o c k Ta bl e Re c o r d;

不相符的图元，这些不相符的图元就是学生在作业中的错误。 2 . 1基于位图的模板匹配法

//通过块表指针，获得块表记录指针

p B l o c k T a b l e -> g e t A t ( A C D B _ MO D E L _ S P A C E, p B 1o c k T a b l e R e c o r d, A c D b:: k F o r Wr i t e );Ac Db Bl o c k Ta bl e Re c o r d l t e r a t o r pBl k l t e r;

模板匹配已经广泛用于数字图像的模式识别领域。在机器识别事物的过程中，常需把不同

//通过块表记录，获得块表记录浏览器 p B l o c k T a b l e R e c o r d -> n e wl t e r a t o r ( p B l k l t e r );

传感器或同一传感器在不同时间、不同成像条件下对同一景物获取的两幅或多幅图像在空间上对照，或根据已知模式到另一幅图中寻找对应的

获得了块表记录浏览器，就可以通过该浏览器逐个遍历数据库中所有图元了。1 . 2图元信息提取

模式叫匹配 J。 在一幅图像中，能搜索出与已知模板有一样的尺寸和方向的目标，则匹配成功，这方法叫

所有 A u t o C AD实体都是类，均是 Ac D b E n t i t y 的派生类。它包含实体通用的函数，包括查询函数和编辑函数。如查询函数主要有：

模板匹配法。其基本原则就是通过相关的计算、比较，搜索到被找图的坐标位置。这个匹配过程及其中的术语可以通过图 1来显式说明：

Ac Db E n t i t y r:: b l o c k l d该函数获得实体拥有者的对象 I D( Ac d b O b j e c t i d类对象 ); Ac D b E n t i t y:: l a y e r该函数获得实体引用的用 Ac D b l a y e r t a b l e Re c o r d层表记录对象名表示字符串拷贝，即实体所在的图层名； 在工程制图习题中，用到的图元大都是直线、圆、圆弧等曲线，并分别设立一个类，这些类型的

线都可以被认为是由曲线变化而来，在查询和编辑方面存在很多共性，所以又为它们建立了一个基类 Ac Db C u r v e。 查询实体的类型时常用到函数 Ac Db E n t i t y:: i s A0:例如查看直线实体，代码如下：Ac Db En t i t y pE nt;

要搜索图 1 ( a )中有没有模板图中的三角形图l e o )的图像。寻找过程如下：

o△oo o口( a )

.( b )

图 1模板匹配示意图

设模板图像叠放在被搜索图上平移，模板覆盖下的那块搜索图叫做子图~,比较和‘ 的内容。若两者一致，则和，之差为零， 所以可以用下面这个测度来衡量和‘的相似程度

p B l k l t e r -> g e t E n t i t y ( p E n t, A c D b:: k F o r Wr i t e );

i f ( p E n t -> i s A 0== Ac D b L i n e:: d e s c 0 ) A f x Me s s e n g e r (”该实体是直线！” ):

维普资讯

工程

图一

学

学报

2 0 0 5牟

般点 C,以对象方式表示如下：I n t e r s e c Li n e T. s pe c i a l Po i n t A-￣ I n t e r s e c Li n e S. s pe c i a l Poi n t B I n t e r s e c Li n e T. s p e c i a l Poi n t B￣ I nt e r s e c Li n e S. s pe c i a l Poi nt B

D (=∑∑ ( , n ) - T ( m,, 2 )】 ( 1 )m=l n=l

其中

:模板图的长、宽Ⅳ:被搜索图的长、宽+1使得

显然如果存在满足 1< f,,< 2 . 2基于矢量图的图形匹配技术

I n t e r s e c Li n e T. c o mmo n Poi nt C≈ I n t e r s e c Li n e S. c o mmo nP oi nt C

D( i, = 0或者 D( i,≤,则匹配成功。

图元的属性匹配规则

不难发现，位图的模板匹配法的主题就是在给定位图中寻找与模板图相同或相似的图块的位置。下文将研究基于位图的模板匹配法的思想，应用于矢量图的图形匹配来解决工程制图习题的智能批

改问题2 . 2 . 1 匹酉己规贝 4

除此了图元的坐标位置、形状等各有独自的属性匹配规则之外，还有颜色、线型、线宽、属层等属性匹配规则，每一种图元都应具有这些属性。它的匹配规则表示如下：E n t i t y T . c o l o r - E n t i yS t . c o l o r E n t i yT t . 1 i n e yp t￣ E n t i yS t . 1 i n e t y p e

矢量图存储图元的类型、位置、坐标等信息， 而位图存储其中每一个像素的 R G B值，两者的匹配规则不同。A u t o C AD图形是矢量图形，可以通过图元特征提取技术读取各个图元的类型、 位置及其坐标等参数值。下面先找出各种类型的图元的匹配规则：

E n t i yT t . 1 i n e S c a l e==E n t i yS t . 1 i n e S c a l e E n t i y l t a y e r=::E n t i yS t . 1 a y e r

2 . 2 . 2 匹配过程

匹配的过程，即是从被搜索图中寻找与模板图中满足匹配规则的图元的过程。两组图元匹配的流程图见图 2。在匹配函数入口，先利用图元提取技术，分别将被搜索图中的图元和模板图中

图元的形状匹配规则

( 1 )直线直线的匹配规则是：起点、终点，以对象方

的图元分别读入数组和中，然后从中每个图元与中的图元逐个进行匹配，如果中有一个图元与它满足匹配规则，则它匹配成功，否则匹配不成功。

式表示如下：Li ne T. s t a r t Poi nt -=Li= ne S. s t a r t Po i nt Li n e T. e n d Poi nt==Li ne S. e nd l:} o i n t

T表示被标准搜索图中的图元对象； S表示

3结

论

模板图中的图元对象 (下同):( 2 )圆

作者研究对工程制图的习题的智能化批改的关键技术——图元特征提取与图形匹配技术做了深层次的研究，并应用在“工程制图网络习题集及智能批改系统”中，解决了最重要，也是最难的非规则图元，如相贯线和截交线的智能批改批改问题，学生作业可以远程提交、可以调出

圆的匹配规则是：圆心、半径，以对象方式表示如下：

Ci r c l e T . c e n t e r Ci r c l e S . c e n t e r Ci r c l e T. r a d i u s - -= Ci r c l e S . r a d i u s

( 3 )圆弧

圆弧的匹配规则是：圆心、半径、起始角、 终止角，以对象方式表示如下：Ar c T. c e n t e r=: Ar c S. c e nt e r Ar c T. r a d i u s￣ Ar c S. r a di us Ar c T. s t a r t An gl e￣ Ar c S. s t a r t An g l e Ar c T. e nd Ang e l￣ Ar c S. e n d An gl e

正确答案与学生作业比较结果、也可以演示作图过程的 f l a s h动画或三维模型、可以由计算机判

断作业的正误，并用不同的颜色和简单的文字提示错误 (图3 )p J。

当然，工程制图作业中还有其他部分的智能批改技术需要研究，也考虑到每个学生作业过程中用到的作图方法、作图技巧各有不同，还可以作更深入的探讨。

( 4 )相贯线

相贯线的匹配规则是：特殊点 A、特殊点 B、

维普资讯

第 4期

刘就女等：智能图元特征提取与图形匹配技术

1 4 9

图 2两组图元匹配流程图

5— 1 9 ( 1 )完成两实体的相贯线

5— 1 9 ( 1 )完成两实体的相贯线批改结果：一

…

一 黄色表示多画或错菩的线

青色表示少旨的线 固点表示错误的特殊点或一般点 (黄色)应为虚线， 不是粗实线正确的一般点和线

错菩的一般点和线

(青色 )蔫菩的相贯线

囵囵( a )调出学生作业的答案 ( b )调出正确答案，指出学生解题的错误图 3作业批改示例

维普资讯

1 5 0

工程

图

学

学报1 9 9 6, 2 8 ( 8 ): 6 1 7~ 6 3 0 .

2 0 0 5互

参考文献[ 1】 胡宜鸣，等 .工程制图智能电子习题集软件的研制——

侯

雄，孙凝生.用于故障字典的图形匹配算法研

究[ J] .航天控制， 1 9 9 8, ( 2 ): 5 4 - - 5 8 . 王雪飞。胡青泥 .基于分层加权的多边形图形匹配[ J] .工程图学学报， 2 0 0 2, 2 3 ( 2 ): 1 2 - 1 5 .

实时智能批改作业[ J

] .工程图学学报，2 0 0 2,

2 3 ( 2 ): 1 1 8 - 1 2 1、L e eI K。 Ki m M S, Ei b e rG、 P l a n e c u r v eo f s e t b a s e d

陈锦昌，刘就女，刘林 .计算机工程制图习题集[ M】 .广州：华南理工大学出版社， 1 9 9 9 . 5 0~ 5 1 .

o n c i r c l e a p p r o x i ma t i o n[ J】 ' C o mp u t e r A i d e d D e s i g n,

Gr a p h i c El e me n t s’ Ch a r a c t e r i s ic t Ex t r a c i t n g T e c h n i q u e a n d Gr a p h i c M a t c hi ng T e c hn i que f or I n t e l l i g e n c e Cor r e c t i o nLI U J i u— n t l , W U Do n g— q i n g , P E NG Xi a o— mi n , LI Z h e— l i n( 1 . I n s t i t u t e o fl n d u s t r yd e s i g n& Gr a p h i c s, S o u t h e n Ch r i n aUn i v e r s i t yo f T e c h n o l o g y, Gu a n g z h o u 5 1 0 6 4 0, Ch i na; 2 . Z h o n g k a i Un i v e si r y t o fAg r i c u l t u r e a n d T e c h n ol o g y, Gu a n g z h o u 5 1 0 2 2 5, Ch i n a; 3 . I n d u s t r i a l nd a Co mme r c i a l Ba n k o f Ch i n a S o t t wa r e De v e l o p me n t C e n t e r, Gu ng a z h o u

5 1 0 6 3 0, C h i n a )

Abs t r ac t: Ho me wo r k i nt e l l i ge n c e c o r r e c t i o n wa s a l o ng t i me o bs t a c l e f o r c o mp u t e r e ng i n e e in r g g r a p h i c s .Th e p a p e r pr e s e n t s t h e s ol ut i o n.I t s c it r i c a l po i n t i s ra g p hi c e l e me n t s’c h a r a c

t e is r t i c e x t r a c t i n g a n d ra g p h ma t c hi ng,whi c h i s a l s o s e r v e d f o r t h e de s i g n of i n t e l l i ge nc e c o re c t i o n a l go it r h m i n t h e o r y.I t in f ds

a n d s t u d i e s t h e ra g p h ma t c h i n g t e c h n i q u e .W i t h t h e h e l p o f i t,n o r ma l a n d a b n o m a r l ra g p h i c e l e me n t s’i nt e l l i g e n c e c o re c t i o n i s f e a s i bl e .

Ke y wo r d s: c o mp u t e r a p p l i c a t i o n; i n t e l l i g e n c e c o r e c t i o n; a l g o i r t m h d e s i n; g o b j e c t AR X