（计算机系统结构专业论文）光栅图像矢量化技术研究.pdf

摘要 摘要 工程图扫描输入及自动矢量化是c a d 等领域中的关键技术之一。采用模式识别技 术，将二值点阵图像信息通过预处理、矢量化处理等环节转换为矢量信息存储是本文研 竞的主萼目的。 本文对现有几种矢量化算法进行了分析和比较。在此基础上，研究形成j 种- 陕速、 育效的方法基于关键点的矢量化算法。该算法在处理拐角、交叉区域时，逆_ j 了矫 正处理流程，通过调整步长以产生正确的矢量；在处理圆和圆弧时，用圆心、半径、圆 弧的起点和终点表示，大大减少了图元占用的存储空间，使得对图形的进一j 处理更容 易，效果更好，同时也解决了圆弧断裂的问题；在提取关键点的过程中，保l 旷丁整个图 像中尽可能少的关键点数量。大量的实验表明，运用本文提出的矢量化算法能日# 取得较 t j 的矢量图形效果。 关键词：矢量化关键点跟踪过程游码 垒! ! ! 型 a b s t r a c t a u t o m a t i cv e c t o r i z a t i o no ft h e e n g i n e e r i n gd r a w i n gi s o n eo ft h ek e yt e c h n o l o g i e si n c a df i e l dt h ep u r p o s eo ft h i s p a p e ri s t ot r a n s f o r mb l a c k - w h i t er a s t e r i m a g ei n t ov e c t o r s t o i a g ea f t e rp r e p r o c e s s i n ga n dv e c t o r i z i n gs t e p s a n i m p r o v e dv e c t o r i z a t i o na l g o r i t h m i s p r e s e n t e d a f t e r t h e o r e t i c a l l ya n a l y z i n g a n d c o m p a r i n gd i f f e r e n tv e c t o r i z a t i o nm e t h o d st h ep r o m i n e n tf e a t u r e so ft h i sa l g o li t h ma r ea s t o l l o u 7 s c o r r e c t l yd e a l i n gw i t hc r o s sa n dc o f n e rb ya d o p t i n gj u n c t i o nr e c o v e r yp lo c e s sw h i c h a d j u s t st h el e n g t ho f t r a c k i n gs t e pa c c o r d i n gt ot h ed e m a n d ；c o m p r e s s i n gt h ea n l o h n o fd a t a ， e d i t h _ gi m a g ea n dd r a w i n gn e wg r a p hm o r ee a s i l yb ye x t r a c t i n gc o o r d i n a t e so ft h ec e n t e c 】- a d i u ss t r u tp o i n ta n de n d p o i n to f c i r c l e 、a v o i d i n gt h eg a po f c i r c u l a ra r c ：e n s l l l 。i n gt h el ：】- i t i c a l p o i n t si nt h ei m a g ea sl e s sa sp o s s i b l et h er e s u l t ss h o wt h i sv e c t o r i z a t i o na l g o t t h mc a nm a k e g o o d v e c t o ri m a g e s k e ) w o i d ： v e e t o r i z a t i o nc r i t i c a lp o i n t t r a c k i n gp r o c e d u r e 1 u n 第一章绪论 第一章绪论 1 1目的和意义 随着时代的发展，各企业、科研设计、档案管理等单位部保留有原先手工作 图时代所积存的大量图纸。随着图纸的逐渐积累，所占的空间越来越大，再加上 长期存放容易引起变质，因而大大降低了图纸的再利用价值，止给图梢竹疆人员 带来了繁重的工作量。 | 从而将这些图纸信息输入电脑并处理成电脑c a d 软件可以自由处理的f 片息具 有很重要的意义。- - n 可以节约大量的储存空间，二则使得对图形的进。步处理。 | 如编辑修改、绘制新图更容易。在更高层次的优化特征识别和图形列啄u ：q f j 域， 矢量化是其预处理中的关键技术，矢量化技术先进的理论研究会- 大大推聊i 辛预域 的发展。因此现阶段研究工程图纸的扫描输入与矢量化处理成为图像群；i 关注 的一个焦点问题。 i 目前利用图像扫描方式输入( 例如用c c d 器件制成的扫描仪来输入围形) 然后再进行点阵图像的矢量化形成高效自动化的图形输入方法正在发展。 方法的研究课题之一就是如何进行点阵图像的矢量化。 图形在计算机中的表示，通常有两种方式：一种是以光栅点阵的形式一 g r a p h i c s ) ；另一种是用矢量的形式( v e c t o rg r a p h i c s ) 。 光栅点阵图像是对象素( p i x e l ) 进行存取，故耍占据很大的存储空问， 也不易进行各种变换处理如对图像进行缩放、旋转、修改等。而对于* 量 只需对描述图形的参数进行存取，例如直线仅需存储其端点坐标，刺于叫0 存储圆心坐标、半径、起点和终点，因而便于进行各种图形变换。 对于用矢量表示的图形而言如果需要转化成光栅点阵的形式， 这种 a s t e r 同时 l 形， 仅需 由给出的图 形参数描述，利用计算机图形学的基本方法，可以很方便的进行转化。但 程，即是耍从图形的光栅点阵形式转化成其参数的描述也就是采用矢量来 形式，却相当困难了。 本文的目的，就在于对这一逆过程进行探索，分析比较现有的几种矢 法，提出一种更实用、更高效的矢量化算法，将点阵图像转化成矢量图形- 1 2 国内外发展状况 逆过 示的 化算 将纸介质图纸经过一系列软硬件处理而转换成由c a d 系统可直接处理的电子 了一一一；l itt。-。-，l 光栅图像矢量化技术研究 图纸，这一领域的工作国内外开展的都比较晚，其中一个原因是因为图形识别软 件研制难度大，要求高，存在着许多困难，如圆弧及各种工程曲线的识别，字符 的分离和识别，尺寸数字的识别。 进入八十年代以来，国外一些公司和大学投入了相当多的人力、物力和资力 致力于图形信息的输入及识别的研究和开发。近年来，由于光纤传感、激光扫描 等新技术在计算机图形学领域中的应用，使图形的快速输入成为可能。九十年 初期，g r a p h i k o n 公司开始了矢量化软件方面的研究与开发。s o r s o f l 公司从l u u t j 年也重点加强了矢量化技术的研究并开发了相对实用性的产品。值得注意的是现 有的矢量化j = j = 件有两种矢量化方式。一种是交互式矢量化。这种方式相当于矗；jj 描后的光栅文件上进行数字化板的工作。但它与数字化板对比来说精度大大提高 对直缝、吲比较多，规则元素多的图纸有非常好的效果速度也快于数字化扳， 另一p 方式就是全自动矢量化，就是由软件完成全部矢量化工作。它的特点就址 速度冉，矢量化过程不需要人工干预。但在某些交叉点多而复杂的图纸，软俐 7 l 动跟踪州r i 能会出现错误走向。这两种矢量化方式各有优劣。德国著名矢量化软 件js o f t e l e c ，其产品v ph y b r i d c a d 软件( 简称v p 系列软件) 自从1 9 9 0 年目单一的光栅矢量化软件演化到更复杂、功能更强大的矢量化软件包v pm a x p r oi 一级扳b o 中提供了两种矢量化方式。挪威、英国等国家血推出了各e ln ：0 ： 量化软件，捌 吱r a s t e r e x 公司生产的r x a u t o l m a g e 系列软件提供了光栅编辑、 光棚矢量混台编辑同时也具有交互式矢量化和全自动矢量化两种方式。 国内从八十年代后期开始图像矢量化软件的研究和开发并且取得了一定的 进展， 二如北京东力泰坦科技有限公司在国际著名的加拿大阿波罗科技集团t 】+ r a g i s 软件基础上，开发了资讯系统平台t i t a n s c a n i n 。麦普公司生产的m p r v s 智 能矢量化系统针对地理图件矢量化过程中的问题发展了最久未用淘汰技术。采 用空间相关最久未用淘汰策略调度四叉树线性编码的栅格分块数据，发展了线条 跟踪提取技术。并利用控制点d e l a u n a y 三角剖分并借助仿射变换校准变形区域的 方法，确保了结果矢量数和走步。 在社会各界的努力下光栅图像矢量化的研究工作不断完善，矢量化方法也 髓之不断的改进。到目前为止。已经研究开发出了适合众多特定领域的矢量化较 件，例如专门为地图矢量化而设计的软件以及专门为工程图矢量化而设计的软件 等。但值得注意的是，现有矢量化软件在对图形进行后处理时对中文字的识别能 力基本没有，但识别英文和数字的能力尚可。 就目前状况来看，矢量化软件的水平不是很高，主耍表现在抗噪声性、处理 速度和各种曲线、字符的识别还不很理想，还不能发挥极大的效益，离实用化还 存在一定距离。 第一章绪论 1 3 本文的研究内容 采用模式识别技术，最终将二值点阵图像信息通过预处理、矢量化处理等环 节转换为矢量信息存储是本文研究的主要目标。 本文主要做了以下几个方面的工作： 1 对已有的各种矢量化算法研究比较后，从中选出了一种比较好的算法，在 此基础上，研究形成了基于关键点的矢量化算法。该算法在性能上白j 较大的改 进，尤其是对圆弧、拐角以及交叉区域的处理。 2 提出了对圆及圆弧的识别算法。经过矢量化处理后，所得到的迓jl 是卜一些 折线和线段，各种曲线段都是由这些折线构成。本文提出的算法能够提日出回及 团弧的圆心坐标、半径、起点和终点，进一步压缩了数据量，更便川期h ：的睁档 和编辑，避免了出现圆弧断裂的现象。 ： 对于图像中拐角、交叉区域等的处理，本文运用校正处理流程和j 量l e 后 的优化调整相结合的方法，从而改善了矢量化算法的性能。i 4 本文研究形成的关键点提取方法保证了整个图像中尽可能，扣的关键巨数 奄，相对于s k l a n s k y 和g o n z a l e z 的多边形逼近法( 保证局部非关键点的最大数量) 来说更有效，实现起来也更为简便。j 本文各章节的内容安排如下： 1 第二章对现存的矢量化算法进行了分析与比较，在此基础上进行l 干时 改进之后形成了一种新的矢量化算法。 ! 结合我们具体的研究与实现，在第三章中对基于关键点的矢量化鲋法 铰为详尽的论述。总结实际的开发经验，阐明了该算法的具体工作漉捏，j 沦述了开发过程中的重点和难点问题。 ： 在第四章中，对该算法的具体实现工作进行了较为详尽的描述，并对 关键点的矢量化算法作了综合性能评价。本文最后提出了该算法中存在的一 足以及几个有待完善的方面。 的 ， j 细 于 不 4 光栅图像矢量化技术研究 第二章光栅图像矢量化算法分析 一光栅图像与矢量图形 2 1 矢量化概述 峻j 眸扫描与矢量化进程，先要简要介绍一下光栅图像与矢量图形。当_ l j ji 描。蚶j 推吲纸时，光栅文件也就产生了。光栅数据的内容被表示成黑点和白点( ? 值模一l ) 或彩色点组成的一个矩阵。单个的点被排在图纸的x 、y 方向上，被此 之蚓波白任何逻辑上的联系。这些点以镶嵌的形式显示在计算机屏幕上简单地 说光削悔就是一个点阵的概念。当光栅图像放大或缩小时，图像信息会发生失 真特凯 i 放大时图像目标的边界会发生阶梯效应。对黑白或灰度光棚图像口j 进 行如卜让理：i 点处理；2 区处理；3 帧处理：4 几何处理。其中区处理是二舱 图像世理t 如线细化) 的基础，而几何处理则是进行图像坐标纠正处理的基础， 矢量数据j i 几何元素的说明方式，比如直线，圆，弧等。矢量数据与光栅数据_ 1 1 以达到显小效果相通，但它4 f 的数据结构完全不同。矢量图形是各种矢量数据的 集旮花( 1 a d 系统里矢量数据被广泛使用，它们可以在屏幕上以图元为单位进j j ： 移动，拷一或删除等操作。矢量图元可以分成线类图元( 曲线，椭圆，矩形等) 、 文字娄图j i ( 外文自符，点阵汉字，矢量汉字) 和图符类图元( 各种行业符号， 如电阳符号等) 。对于线类为主的图纸用矢量图形表示耍比光栅图像节古存贮“r j 问，侄于i 改图纸。因此工程图纸的扫描与矢量化处理的目的就是将那些线类的 图纸由光柑格式转换成矢量格式，从而可以在c a d 软件里进一步处理。工程图纸 进入c a d 软件处理的过程可以分为“下几个步骤： 扫描 原始图纸 修正 原始光栅文件 矢量化 正式光栅文件 后处理 原始矢量图形 输出 正式矢量图形 转入c a d 处理 第二章光栅图像矢量化算法分析 二图像的预处理 1 图纸的扫描 耍进行图像矢量化过程，首先需要将图纸数据输入计算机，图纸数据输入计 算机时一般有两种方法：1 数字化板输入，2 扫描仪输入。一般来说敬譬化叛适 用于时间要求不紧，图纸信息不太复杂的场合。用数字化板输入图纸相j j 于用一 只数字笔将原有图纸在计算机里再描一遍，它直接就将光栅模式的图纸扪触跃量 格式。而且用数字化板可以在输入时人工将不同信息分层，很直观l 一二h t 反 输入对处理复杂图纸时明显力不从心对不规则曲线如等高线就得尔j i j “i 犊拟 的方式。而且耗时多是该方法的最大缺点。采用该方法是半自动的讹冲 法 是用扫描仪输入。这是目前比较先进的图纸处理方式，它速度快，精j l ：、i 由于扫描仪中c c d ( 电荷耦合) 器件本身具有许多优点，如 描j 塑。i 两、集 喊度高、易于处理，因而受到了广泛的应用。并且可以保证图纸的糈雎。二乳， 噪声也小。但其缺点是输入时对原始图纸有固定幅面的要求，不能1 f 尝：| j 啦i 一 张较大的工程图纸可以分成几块进行输入，再通过软件控制将几；：输八曲h 酐再 重新拼接成一幅完整的图纸，然后可进行任意分块和显示。在文献| 2 l 年0 8 拈睦了 分块处理方面的技术。对于分块处理的考虑是基于在数据量很大的前提h 为了 提高运算速度。 ； 如果我们采用扫描仪输入原始图纸。需耍对扫描仪的两个最重蛭n ：j t j 敌”卜一 分辨率私消蓝功能作一介绍。 分辨率：所有的工程扫描仪都使用模拟记录设备即c c d 。一个( ( d 。i 份快能 自# 输出依赖于图像反射光强的电平信号，输出的保真度有光学的或物删的分辩率。 物理分辨率依赖于扫描仪焦点允许每英寸有多少c c d ，因此如果1 、】程归描 仪育5 0 0 0 个c c d ，可扫描3 6 英寸( 9 1 5 毫米) 的宽度，那么它的光学分辩障就 是5 0 0 0 3 6 = 1 3 9 d p i 。通过插值，将象素点一分为二，可以得到2 7 8 d p i 的搦值防辨 率。但光学分辨率决定了扫描仪的最小识别宽度。比如1 3 9 d p i 光学分辨率的| 扫描 仪最4 、只能识别到9 1 5 5 0 0 0 = - 01 8 3 毫米的线，小于此宽度的线就是提高插侧分辨 率也不能识别。一般应选择光学分辨率大于3 0 0 d p i 的扫描仪，j 消蓝功能：由于实际操作中蓝图的使用比例很高，如果扫描仪没仃j 肖蓝啪能， 就会将蓝底识别成灰度值造成图纸模糊，数据量急剧增大。一般现在h ：j ：i 程扫 描仪都采用选阀值的技术来消蓝，选阀值也就是定一个阀值作为控制，将列于该 阀值的象素标为可见，将小于该阀值的象索为不可见。理论上说一张白包图纸上 绘制的黑线图纸的阀值可设为0 。而在蓝图上就可以设的高一点，将背景的嗣色消 去。可以看出，选阀值就相当于确定图纸的对比度。由于蓝图的复杂性，删一张 蓝图的深浅不均匀等，很多扫描仪就采取了进一步的阔值处理技术。例如v 1 i ) a r 【 i i 厂一) | | 1 ij 。 lli 6 光橱图像矢量化技术研究 的t r u s c a n 8 0 0 首先通过预扫描确定某灰度阀值，然后在正式扫描中可以将图纸 细分为0 2 + o0 l 英寸的小矩形网块自动修正阀值：而c o n t e x 扫描仪则内置丁 d s p ，采用二维自适应阀值处理，可以快速的在线消蓝。此外还应该注意扫描速度， 随配的软件的适用平台即随带的控制软件是否在扫描控制中就带有简单的光栅处 理功能，如消斑，补洞等。 芷衡量专业用扫描仪时还有一个很重要的技术指标动态范围( 也n i f 密度 范围) ，动态范围指的是原稿最暗点密度值( d m a x ) 与原稿最亮点密度值( d m i n ) 之问的差值，它不是取决于扫描仪某一光学部件的性能，而主耍是由扫描仪整个 光学；象乐统的技术指标所决定的。 2 l j 蚺j 与的消除 图纸辅八到计算机后，由于输入转换器件( 光敏器件、a d 变换器件) 以， 图纸水1 ji 最量等因素的影响，不可避免的在输入后的图像中会出现些孤、r ： 点、“i 【j 、慢尖峰毛刺等噪声，为了保证矢量化处理的精度。必须先对图像q ， 噪声避m i 滤。在图像处理中，噪声的消除有许多方法。通常采用图21 所句j 的 3 + 3 霄门逆行半0 9 0 平口消除。 i t t i j 描仪输入后，得到的图像己被转化成二值图像。这里假设象素值为“l ”， 表4 - 1 割；一j ：象素值为0 ，表示背景点。 斟像中每一象索点的处理都要考虑其邻接8 个点的象素值图2l 中p ”的喙 素值m 由1 、。式给出： 只：厣p ( o ) - i 1 副8 互1 l p ，其它情况 i p 。 p 3p 2 i p ，p op 1 l p 。 p 7 p 8 图2 l 噪声消除窗口 用这护力法可以较好的消除空穴及麻点噪声，起到了线条边缘平滑的效果， 庄之献中，采用的是模板匹配的方法，首先定义了毛刺模板和空洞模板，0 j ： 掖点阵格式扛描图像上每一象素p ，只要p 与模板及其旋转9 0 度，l 8 0 度t2 7 0 度所形成的模板相匹配，则判定该象素为毛刺或空洞，若为毛刺，p 由l 变为o ： 若为空洞，p 由0 变为l 。 j图文分离 在一定的尺寸范围内，文字符号和一些较小的图形元素都是孤立图元，在 第二章光栅图像矢量化算法分析 7 初步提取工作完成后，还须采取一些必耍步骤将它们有效的区分开。在工程图 中，字符和图形是两种类型的矢量数据。如果未经区分的直接进入文字符号矢 量化和图形元素矢量化过程，就会导致两类元素和两类处理过程的严重互相干 扰从而影响处理效果。图像中的字符主要分为孤立字符和粘连字符两类。实 际上，困扰着传统矢量化处理的字符与图形元素间的相互干扰主强是 j 三图夜粘 连引起的。因为粘连字符往往会被误认为是图形的一部分而被拒识，| 1 _ | j 被粘连 的图形元素在矢量化时也会产生歧异。文献p 】对粘连字符的图文分离自m 尽的描 述，其粘连字符分割方法的核心是寻找并获得粘连处，然后将粘j 生处旧点置白， 从而使粘连字符和被粘连元素分开。清华大学所研究的e d v p s 彖缱分听f _ j | 到， 粘连处不是一个夹在字符和被粘连元素之间的、有确定的构成点和r 嘲吼边爵的 区域，它只是一个假想的区域，因而从理论上讲是无法直接根据吐i 10 的形态 找到的。该系统对大量的字符与图形粘链的情况进行了分析，总站j 粘茬形 态的苦干规则，在分割中，利用这些规则对各种粘连情况进行处j 峄 - 三矢量化处理的总流程 原始图纸经过扫描后生成原始光栅图像，此时的光栅图像还小能“接妊行 矢量化，因为考虑到原图的质量和扫描的误差，还应该对原始的光栅h 像姓行 处理。一个好的矢量化软件应该带有较强的光栅图像修正能力，h ；中k 较巨要 的育以下几个：1 消除斑点可以方便的消去图像上大d 、在指定驾：袭沁训j , j 的 斑点。这个在蓝图质量较差的时候很重要，能大大减小数据量。! 。纬j ：纠正， 应该提供方便的橡皮版功能来修正图纸坐标的偏差，达到满意的精使j 哙制 或删除光栅象素。经过光栅修正处理后的图像就可以进行矢量化j | 扫描并经修正处理后的光栅可以以j p g ，t i f f 等格式存储住k i i 化欧件 中有一种是光栅矢量混合编辑处理软件，它并不矢量化光栅但司l l 混台匣示 输出光栅矢量混合图形。比较适合于只需要将光栅图像作为底图的场i 7 瞎样 只需提供光栅处理功能就可以比较好的满足要求。| 任何一个光栅一矢量转换过程，也就是所说的矢量化过程都是柞$ 比栅 圈并用矢量元素替换的过程。理论上说如果原始光栅文件包占清晰、单值象 素，那么转换过程就能产生在c a d 软件中编辑的1 0 0 的矢量文件但实际上 由于原图纸的质量问题，那么在扫描中就可能提供错误的光棚结构，返时候优 秀的矢量化软件就能产生接近原图的矢量表示。i 光栅数据的原始矢量化产生了个高精度复制原图的基于矢量的拓扑陷构 ( 使用多义线) ，但是没能生成真i g n i ：) , 由c a d 处理的矢量元素= 闭f f j 叫几何 元素直线、圆、文本或箭头都被构造成多义线，看起来就象手工绦制十样a l 啊- 一 l li 8 光栅图像矢量化技术研究 矢量化后处理就是运用误差原则和比较解释技术来从多义线中提取直线圆和 圆弧t 它建立不同的线宽，线型，校正角度并识别文本、箭头、符号和剖面线 等。并姆识别出的元素放在不同的层上，而这个过程则应该是参数化可以控制 的。经过矢量化和后处理的矢量图形就可以以d x f 或i g e s 等格式输出保存。 这两种格式的矢量文件被大多数c a d 软件支持，因此就可以很方便的输入c a d 软件中进一步处理了。 22 经典矢量化方法的回顾与比较 日前，矢量化方法大致可分为两类，即基于细化的方法和基于非细化的力法 在瑶于细化的算法中，主要有边界追踪法1 6 4 】、距离交换法 9 - 1 0 和适当骨架化” 等经典细化算法。在基于非细化的方法中，主要有基于轮廓线的方法1 1 2 - 12 1 l ， f h 播艇式的方法1 1 4 - 1 5 1 ，基于游码的方法1 1 6 - 1 7 1 以及正交方向转换方法1 18 i 等 媳墼的光栅图像矢量化方法的基本流程如下： ( 1 ) 采样中心轴点。这是信息简化的核心过程，获得能表征中心轴的 ( 2 ) 线形踩踪。跟踪中心轴点，从而产生每个矢量的点链。 ( 3 ) 线段逼近。除去点链中的非关键点，对剩下的关键点进行链接 22l 薹于细化的矢量化算法 细化是一种简化图象的方法，在图象处理和模式识别中得到了广泛研究所 谓细化就是将线条的宽度减少到只有一个象素，仅剩下能表征其特征的骨架 纸化处理的基本原则是：( 1 ) 细化要取原图象的中心线，即细化过程是对称 的。t2 ) 细化不改变原图象的连通性。( 3 ) 细化要保持原图象的基本特征，比如 细化处理后的线条不能变短，拐角不能断开或出现多余分支等。 国内外学者己提出了许多细化算法，主要可以分为三类：边界追踪法，距离 交搀蠹和适当骨架化方法。 1边焊追踪法 边界追踪细化算法运用不断收缩线体轮廓( 即去除线体的外层象素) 的思 想，就象一个波前从线体外层向内层传播，直到只剩下骨架。其核心过程就是在 图象上移动一个窗口，并运用一套规则来标识窗口的中心。每完成一次扫描，就 删除捧所有的标识点。重复进行扫描，直到没有多余的点可被删除。例如，n a c c a c h e 和s h i n g h a l l 6 l 运用一个3 * 3 的窗1 ：3 如图2 2 采用如下标识规则，对其中心点进 行标识，如果下面的规则都能够被满足，那么p 就标识为删除。 ( 1 ) p 的4 邻域( 即p o ，p 2 ，p 4 ，p 6 ) 中必须至少有一个象素是白的，也就 第二章光栅图像矢量化算法分析 是说p 是一个边界点。 ( 2 ) p 的8 邻域( 即p i ，i = 0 7 ) 中必须至少有两个象素是黑的，也就娌说p 不是一个结束点。 ( 3 ) 对于p ，在其8 邻域的黑色象素中，必须至少有一个没做过标识、 ( 4 ) p 一定不是一个断点。 ( 5 ) ( 6 ) 如果p 2 作了标识，在设置p ：为白的情况下 如果p 一作了标识在设置凡为白的情况下 p 3p 2p i p dp p n p p 6 p 7 一定不能使p 是一个断点。 一定不能使p 赶竹断点。 j 图2 23 * 3 的矩阵窗口 】 由于重复细化的作用，使得边界重复细化方法在形状类似y 耵t 的奁 _ 迁处容易产生变形。为了克服这一缺点，研究人员进一步提出j ，渊罄：i ， 臣爱：细 化的技术，该项技术主要包括调整标识规则以及改变窗口的尺寸等惭j 如， d i e e n i 8 1 运用的是一个3 * 7 的窗口，而o c , o r m a n r 7 1 把重复细化方法推，1 。到：d 罨k * k 尺寸的窗口。虽然这些修改已经在速度和精确度方面获得了改进，f l | j t 【1 ，l 上的效 果并不是很明显。i 2 距离交换法| 在规津性的细化算法中，给出了更形式化的骨架的定义i 。p f a l l ：z 祁r o s ea f e l d i ” 定义了点阵图的距离转换，即通过该象素与一个白的象素之间的最小m 离 替该 象素。这一转换通过顺序的估算函数值计算得到，首先估算图形光栅拦捎扣的函 数，然后估算反方向扫描中的函数a 在得到了距离函数之后，运用局翻：最9 i 操作 找到骨架。该方法最主要的不足是骨架的不连续性，尤其是在交叉点处拣而它 的速度相对于边界追踪细化算法来说要快一些。 3 适当骨架化法 d a v i e s 和p l u m m e r 定义了适当骨架化1 矢量化方法。这种- 5 法通过把 r 。s e n 凫l d 的算法和边界追踪细化算法所得到的骨架点进行台并，得到2 ( 、象素 宽的骨架，然后再细化为一个象索宽的骨架。该矢量化方法能够保证很高6 精确 度，并能保证骨架的连续性但所需的计算量也很大。 以上对基于细化的算法中比较典型的几种方法进行了简单描述和分n 基于细化的矢量化算法有以下几个特点：能够保持线段的连续性，后续的 取矢量的过程比较简单，进一步的图形识别也比较容易；但有很高的时间 丢失线宽信息，在交叉区域处容易产生变形以及错误的分支。此类算法主 总之， 踪获 杂度， 应用 光掘图像矢量化技术研究 于图像尺寸小且线宽信息不重要的o c r 领域。在处理技术图纸以及地图学应用中， 当原图包含直线、圆以及基于这些基本元素并且没有填充物体的光栅图像时，使 用这种算法往往能产生很好的效果。 222 基于非细化的矢量化算法 相对于基于细化的矢量化算法，基于非细化的矢量化算法不必先对光栅图像中 的线体细化提取中心骨架线，而是直接追踪光栅图像中的线体边界从而加以矢抖 化hi t 和：基于非细化的矢量化方法中主耍有四种：基于轮廓线的方法，基丁州 恪梅- ：】i j 汪，基于游码的方法以及正交方向转换方法。以下分别介绍这四利r 量化弹，扎 】基卜轮廓线的方法 l q 矗：u 降低缅化计算量为目的，在取样中心轴点之前尽量减少数据量。 - 蛭 思想j i 苜先找到线体的形状，即线体的边或轮廓；然后计算相互平行边上川、j 点日ij j 一量取样和跟踪中心轴点的操作是同时进行的，这不同于基于细化的算法， 在细化算i j ：中，所有中心轴点取样之后再进行线段跟踪的操作。该方法主璎自勺操 作就足：尘的识别和多边形化，比细化算法的速度要快很多。边的识别在计算机州 觉鞭j ：t 已经是一个很成熟的操作。另外，线宽的值电很容易得到线宽在更高j ，： 的圈缘点解领域中是一个很重要的参数。 沱晒图像进行了边识别和多边形化操作之后两条近似平行边的中心轴点定 义为从边到另一边垂直投影的中点【1 2 | ，如图2 3 ( a ) ( b ) 所示。从某一形态良好的 边开始线性搜索找到距离该边最近的边作为此目标体的另一边，再从一边到- 一边，t 几条垂线。通过跟踪边和交叉点的判定很容易找到一系列边。 _ j 、， 、 一j 、， 、 、 r a )相互平行边的中点( b ) 近似平行边的中点 图2 3定义中心轴点 这类算法所面临的主要困难是如何解决交叉区域的问题。主要存在两种情况， 一种是在交叉区域处交叉点形成的角度很小，如图24 ( a ) ，所形成的合并区域很畜 易丢失。另一种是十字交叉区域的情况，如图24 ( b ) ，如果只是简单的将交叉线进 第二章光栅图像矢量化算法分析 行合并，得出的矢量图形必定存在缺陷。算法强壮并且能够正确处理线形和交叉 点的情况对于光栅图像矢量化相当重要。 、 图2 4交叉区域 t ：+：十一 图2 5 网格规则模式 有又长又直的线段存在的区域，网格边界的每一边基本上都相交图象中的一 条线 l ， i一 光橱图像矢量化技术研究 段，据此，形成了五个规则模式，如图2 ，( a ) 全白，( b ) 白黑白，( c ) 黑白， ( d ) 白黑，( e ) 全黑。通过这五个规则模式的任意合并，再加上斜线的情况，l i n e ta l 定义并标识了5 1 个己知特征模式。对于每一个网格，如果它的分布是一个己 知特征模式则用相应的特征模式标识代替。对于未知的情况，则用问号进行标 记，问号区域需要在控制图分析期间用一个更为复杂详尽的过程进行处理。该过 程扫描区域中的每一个象素，并将每一个黑色象素标识为一个特征点。 为了能对问号区域进行更为简单可行的处理，v a x i v e r e 和t o m b r e f l 刮应用动态 网格盯l i ne ta l 的方法进行了改进并把基于网格模式的方法运用到了机械工程剖 的分_ i 和识别当中。他把标识问号的网格进一步分裂为几个更小并且己知的特 ：i 】： 模式川等，其形状可以是任意的。另外，为了减少网格的总体数目，把有同样编 码的邻近网格合并成了一个网格。矢量化过程的结果就是一个数据结构它用可： 同娄型h 连接段( 细线段，粗线段，黑团的轮廓) 和这些连接段间的交叉点来表 达一1 、【訇蒙 赴基f 同格模式的方法中由于只考虑网格边框上的图象信息，而忽略了刚格 昨爿：晌7 j 恳，使得研究问题得到了相当地简化。但是网格尺寸很难控制，往往会 因为i j 格大小的选择而引发一系列问题。如果网格尺寸太小，则容易错误连接问 隙很小的断开线以及错误合并很接近的平行线等。如果网格尺寸太大，就会使甜 叫格内的情况太复杂而难以分析。所以，该类方法适用于所含线段直并且少的 e 图中， 3基j 二游码的方法 m o n a g a n 和r o o s l i ”1 对游码图作了形式化的定义，即把游码图定义为光栅图像 在线段识5 j | | 以前的一种半矢量表示法。游码表示法充分表达了线图的结构，并且 可以更有效的进行线段抽取，信息保存，实现起来也更为容易。 几种对光栅图像的游码图的表示法如图2 6 ，每个游码都有一个方向，是黑色 象素在此方向上的最大序列，可以是水平方向也可以是垂直方向。因此游码可 作如f 的定义： r = fd ，c d l ，b a ，e a ，b a e a 上式中，d 指的是游码的方向，可用0 代表水平方向1 代表垂直方向；c a 指j e 交坐标，即游码在正交于游码方向上的坐标，也就是说，d 为水平方向时，那么 c a 指的是行数，d 为垂直方向时，那么c d 指的是列数：b d 指的是在游码方向上 的游码起始象素的坐标；e d 指的是在游码方向上的游码终止象素的坐标。如图2 0 ， r 。是垂直游码，r 2 是水平游码。另外，游码也可以通过两个端点表达在这种情 况下，游码的方向可以通过两个端点的坐标推断。如果它们的x 坐标相等，则为 垂直方向，如果它们的y 坐标相等，则为水平方向。 第二章光撕图像矢量化算法分析 接触点端区域 边区域连接区域r 图26 光栅图像的游码图表示方法 如果游码组a 和游码组b 有相同的方向，它们的正交坐标差是1 并且它们 的最大起始坐标和最小终止坐标的差小于或等于1 ，则说它们是相邻的。曲果a 和b 是相邻的并且a 的正交坐标小于b 的正交坐标，则a 称作b 的前驱ib 称 作a 的后继。如果一个游码只有一个前驱和一个后继则称该游码是规则的，否 是共轭的。基于上面的两个定义，产生了短游码的概念，对于垂直游码来说，如 果它是规则的并且长度不长于它的所有共轭游码，则称该垂直游码为短游杩。对 于水平游码来说，如果它是规则的并且长度短于它的所有共轭游码则称梭水平 一个边区域由相邻短游码在相同方向上的最大序列构成。个端区域f i 包括 一个游码且该游码在某侧没有相邻游码。连接区域指的是象素相邻的垂直游 m o n a g a n 和r o o s l i 还引进了接触点的概念，如图2 6 所示，因为两个接触并且相邻 的游码，属于边区域中的部分，所以它的定义与边区域的定义相矛盾。如果抛 r g = ； 上式中，v 是连接区域或端区域的节点集合，e 是连接节点的边区域中的边集合。 根据b o a t t o 1 7 1 所作的定义，构造图像的游码图的步骤如下第一步构造水平 游码图和垂直游码图，各自只能包括水平游码和垂直游码。第二步用相邻的规则 短游码构造边区域，最后，将图像中所保留的被编码为垂直游码和子游码的区域 游码图形成后，开始进行基于游码图的线段抽取操作。每一节点的形状鄙通过 游码分离过程进行优化，此过程尽量减小节点区域并增大连接边的长度。特边区 域中短游码的中点作为图像的骨架点，最后对这些骨架点进行多边形化以产生最 l _ 砸一；1l 一 光橱图像矢量化技术研究 在半矢量游码图表达方式的基础上进行的线段抽取操作有很高的效率，但构建 游码图这一预操作需要花费访问图像中所有黑色象素至少一次的时间。这种方法 的缺点还包括由于交叉区域的不准确定位产生了不准确的交叉点，这是因为游码 方向改变或是边上的噪音点所造成的。因此这种方法不适用于曲线段的矢量化。 4 正交方向转换方法 正交方向转换方法【1 8 | 是由d c d 所发展的矢量化方法组中的第一种，正交- h 向 转换的基本思想是：跟踪一个象索宽的光柱路线，每当碰到黑色区域的边界时跟 踪路线作正交转换，并纪录正交方向上游码的中点，此处游码指的是光柱所经过 的黑色区域。如图2 7 ( a ) 。首先需要给定游码长度的最大阀值，如果游码长于这个 阀值- 则在最大阀值处停止，进行正交方向上路线的跟踪，并纪录正交方向上游 码的中点。游码长于最大阀值的情况一般会在在沿近似于水平区域或垂直区域进 行跟踪的情况下发生。图27 ( b ) 显示了水平方向的跟踪情况。 ( a ) 图2 7 正交方向转换矢量化算法的规则说明 正交方向转换方法的详细过程如下，水平扫描线从左向右扫描图像，扫描线 每次向下移动n ( 比如n = 1 0 ) 个象素的距离。当遇到黑色象素时，表明进入了黑 色区域，开始正交方向转换过程。直到遇到白色象素( 也就是说光柱遇到了黑色 区域的边界) 或游码的长度值超过了预先确定的阀值时暂停扫描。如果遇到的是 黑色区域的边界，则记录下游码的中点，扫描轨迹在黑色区域内取正交方向后再 继续进行正交方向转换的流程。如图2 7 ( a ) 。如果是游码的长度值超过了预先确定 的阀值，则暂停扫描，从停止点处正交方向上发射两条新的光柱，这两条光柱的 方向相反。当两条新光柱遇到黑色区域的边界时从黑色区域的一边到另一边将 两条共线的扫描游码定义成一个新的游码组合游码。把组合游码的中点记录 第二章光据图像矢量化算法分析 下，并作为与组合游码正交方向上新光柱的源点，从这个新发射的光柱继续进行 正交方向转换的流程，如图2 7 ( b ) 。如上所述依次进行，每当正交方向转换流程遇 到线段的边界时，通过从停止点发射一条与当前扫描线方向正交的光柱开始另一 个正交方向转换的流程。在跟踪的过程中，记录并依次连接这些中点，作为图像 的中心轴点。再通过多边形化进一步处理中心轴点，以保证正交力向转换方法的 输出结果。同时记录下识别过的黑色区域以防止同样区域被再一次识别的情 兄发 生。 整个水平扫描的过程结束后，再进行垂直扫描。在垂直扫描的过柑a h 匿直 扫描线从上到下进行扫描，每次移动n 个象素的距离。垂直扫描k _ j - 1 f i 。绿日 后| 1 台 并两个扫描过程中记录的线段并删除覆盖的线条区域。 因为是对图像的稀疏取样，所以正交方向转换方法效率很高研汕i e ，j 的像素 敬量与图像的宽度和高度之和呈直线关系。然而，该方法对图像中的f 蜞；1 - 限敏感。 并且，这种算法只产生线条，因此，曲线图象的矢量化结果可能会花j 南_ i 处产生 重叠的缝条或错误的间隙。因此，这种方法不适合曲线图像的矢量化 为了使矢量化算法更加完善，l i u 和d o r i 1 9 1 在正交方向转损方i j ：f f , jj i l f ：l ，卜j ，研 宄形成了稀疏象素矢量化算法。稀疏象素矢量化算法在以下儿1 方曲x , j 】r 砭向 转换方法进行了改进： 1 对于每个黑色区域，通过一个特定的流程找到个可靠的开j ! i ! f 幽再| 从这 个开始点开始进行整个的跟踪流程。j 2 这个跟踪流程用于处理正交方向转换方法的三种情况，即水乎的，蚓直的 和倾斜的，只需要一遍扫描过程，避免了两个扫描过程的台并操仁所l 以， 稀疏象素矢量化方法的执行速度会更快。i 3 在线段跟踪的过程中，每当遇到交叉区域，在连接处夏运用枝j j ! = 处理流程。 经过评估，稀疏象素矢量化算法就时间效率和形状保存来说有很好的性l 能。 它可以用于任意种类的线图和技术文档的初步矢量化。但是稀疏象素矢量化j 算法 有两个主要的缺点，一个是连接处的校正能力虽然该算法可以解决奄义困域的 问题，但得到良好处理的只是部分的连接问题。另一个是圆弧的矢量结果删由折 线段组合而成的，并且在以圆心为原点，斜率绝对值等于1 的四个特定位到上容 易产生断裂的现象。i l j 2 3基于关键点的矢量化算法的形成 j 本文所研究形成的基于关键点的矢量化算法是在稀疏象素矢量化算7 j i 上进行了改进。该算法的主要特点如下： 1 只需对图像中包含图形部分的区域进行扫描，并且对于圆及圆弧的 酣基础 铡量化 fi 1 6 光栅图像矢量化技术研究 处理不再是采用直线逼近，而是采用圆心、半径、起点和终点组成的表达武表示， 从而大大减少了图像元素的存储空间，同时也解决了圆弧断裂的问题。 2 该算法对拐角以及交叉区域等的处理采用了校正处理流程和优化调整相结 合的力法，解决了拐角、交叉区域变形的问题，对于少数部分不能得到准确跟踪 的多分支7 芷叉区域，采用人机交互的方法进行修正。 3 本之的关键点提取方法保证了整幅图像中尽可能少的关键点数量，相对于 s k l a n s k y 和o o n z a l e z 的多边形逼近法( 保证局部非关键点的最大数量) 来说更有 效，j 0 吧起来也更为简便。 【毫勺；j 的基本过程如下： i ) 玳掘d o vd o r i 提供的方法，找到一个稳定的中一t z , 轴的起始点以及跟踪方 忆i 夏起始点要不受图像噪声和图像不精确性的影响。 ：j 选j 兰跟踪步长，沿其跟踪方向进行跟踪，只耍下列三个连续条件被满赴， 刑继续进行跟踪，并记录中心轴点和宽度游码信息。 t ，) 宽度一致：在跟踪过程中，由宽度游码所表达的线宽之间的差值璎小 1 。某一个阀值。 b ) k 度力向一致：在跟踪过程中象索长度方向应与其前面中心轴 ：j 长度力向相同。 c ) 正的跟踪步长：跟踪步的长度耍大于0 。 ) 如裂上述前两个条件中一个或两个同时被违背了，则开始进行连接处的校 e 处理。 4 ) j - 夷示中心轴的这些点链中，运用本文研究的关键点的提取方法选出能反 映j 取图的关键点，去掉那些不重要的冗余点。这样既能正确反映图像的j i l 担，叉能减少内存的占用。 5 ) 圆及圆弧的矢量化：对每组点链进行判断，看每组点链是否与其它组的 点链构成圆或圆弧，若能够成圆，则求出圆心及半径；若能构成圆弧，求 出国心、半径、起点和终点。 b ) 调整优化。 u 上是基于关键点的矢量化算法的基本工作流程为了能够简洁的描述该算 法中的细苄和关键点，以下给出该算法中术语的定义。 i ) 黑色象素整幅图像中图形部分的前景象素。 2 ) 黑色蒙素区域整幅图像中图形部分的前景区域。 3 ) 线条宽度非零的直线段。 4 ) 扫描线从左到右通过图像的水平线，一个象素的宽度，用于找到黑色 区域中的第一个黑色象素。扫描线间垂直方向间隔为n 个象素，n 夏小于 预期的最小线宽。 第二章光栅图像矢量化算法分析 5 ) 象素访问方向上、下、左、右四个方向之一，即从当前象素开始访问 下一相邻象素的跟踪方向。 6 ) 定向游码在象索访问方向上，从遇到的第一个黑色象素到停止氯素问 连续水平或连续垂直黑色象素的序列。 7 ) 定向游码符号当定向游码的象素访问方向为左或上时，定向游码符号