（控制理论与控制工程专业论文）电子地图中地理对象的智能识别研究(1).pdf

大连理t 大学硕士学位论文 摘要 地理信息的提取和识别是地理信息系统( g l s ) 、全球定位系统( g p s ) 发展的基 础和迫切需要。自动矢量化因其效率、精度、自动化程度和可靠性方面的显著优势，已 经成为获取地理信息的主要途径之一。 本文在研究和分析了目前具有代表性的扫描图像矢量化方法的基础上，针对地图扫 描图像中图形对象特点，发计了一种基于稀疏象素的方向无关的矢量化方法，并基于此 理论在p c 机上用v c + + 6 0 编程语言实现了一个自动矢量化实验系统a u t o v e c t o r 。 基于稀疏象素的方向无关的矢量化算法基本思想为：寻找稳定的初始点；判断跟踪 方向；提取关键点；获得直线的中轴线表示；擦除原直线栅格图像；进入线条网处理； 最后重构图形。该方法因为没有耗时的处理( 如细化、轮廓跟踪、行程编码等) ，因而 在速度上优于其他矢量化方法。由于不是访问所有象素，而是通过跳跃采样减少访问象 素点的次数，较之以象素为处理单元的算法减少了大量数据，抗干扰性明显增强。算法 中为了避免交叉区域的提前结束跟踪现象增加了交叉区域的处理过程，为从宏观上把握 整个图像的拓扑结构提供了便利。 图形的识别和提取是矢量化工作中的重点，本文采用最小角法则和惯性原理设计并 实现了多边形和折线的提取。此外，还成功运用了步进圆弧矢量化方法、方向距离统计 法、数学形态学噪声滤除技术以及对二值图像的一些基本操作。所实现的实验系统 a u t o v e 咖r 能够更快、更好地重建地图扫描图像的图形原貌，取得了较好的矢量化结 果。 目前的矢量化研究都是在工程图领域进行的，本文提出的算法是根据地理信息系统 的要求设计的，并实现了与g i s 软件m a p i n f o 的接口，在地理信息系统领域有一定的理 论意义和应用价值。 关键词：g i s ；稀疏象素；矢量化；二值图像；拓扑特征 电子地图中地理对象的智能识别研究 i n t e l l i g e n tr e c o g n i t i o na n d r e s e a r c ho n g e o g r a p h i c e l e m e n t s i nt h es c a n n e d m 印 a b s t r a c t t ke x l r a c f i o na n dr 湖鲥d o no ft h eg e o g 螂h yi n f o m t a t i o ni st h eb a s i so f g e o 鲫a p h i e i n f o m m f i o ns y s t e m ( g l s ) a n dg l o b a lp o s i t i o ns y s t e m ( g p s ) a u t o m a t e dv t o r i z a t i o nh a s t r a n s c e n d e n t a d v a n t a g e sa n d h a sb e c o m et h em a i nm e t h o dt oc a p t u r et h e d i g i t b li n f o r m a t i o n i nt h i sp a p e f am e t h o dt or e c o g n i z ef i g u r eo b j e c t si nt h es c a n n e dm a pi s p u tf o r w a r d w h i c hi sc a l l e da na l g o f i t h mb a s e do nt h es p a r s ep i x e lw i t h o u t d i r e c t i o n ，a f t e rd e e p l ys t u d y i n g a n da n a l y z m gt h er e p r e s e n t a t i v ev e c t o r i z a t i o ! a m e t h o d s u s i n gt h i sm e t h o da r ta u t o m a t e d v e c t o r i z a f l o ns y s t e m a u t o v e c t o ri sa l s oe s t a b l i s h e do i lt h ev i s u a lc h 6 oe n v i r o n m e n t t h e s t e p so f t h e i 砖wa l g o f i t h ma r ct 0f i n das t e a d yp o i n l j a d g e a c i n gd i r e c t i o n , p i c ku p t h ek e y p o i n t s ，g e tm e d i a la x i sl i n e ，e r l 强l l r et h eo r i g i n a lr a s t e rl i n ei n f o r m a t i o n , e n t e rt h el i n e s w e b p r o c e s s i n g ，a tl a s t r e c o n s t r u c tt h ef i g u r e s t h i sm e t h o dh a st h es u p e r i o r i t yo v e ro t h e r m e t h o d s ，b e c a u s ei th a sn ot i m e c o n s u m i n gp r o c e s s i n gs u c h t h i n n i n g ，c o n t o u ri x a c i n g ，w i r e s c o d i n g r a t h e rt h a nv i s i t i n ga l lt h ep o i n t st h r o u g ht h e w i r e sb l a c ka r e a , t h em e t h o dv i s i t sl e s s p o i n t s 谢t 1 1j u m p i n gs a m p l i n g i tr e d u c e sm o s to f d a t u mt os t o r a g ec o m p a r e d 诹血t h eo t h e r m e t h o d sb a s e d0 nt h ee v e r y p i x e l 日l ea n t i - j a m m i n gc a p a b i l i t yi si m p m v e do b v i o u s l y i no r d e r t oa v o i da d v a n c i n gt r a c i n ge n di nt h ei n t e r s e c t i o n ，a ni n t e r s e c t i o nd i s p o s a lp r o c c s s i n gi sa d d e d t o t h e a l g o r i t h m i t p r o v i d e s m o r e f a c i l i t y f o r t h e w h o l e m a p t o p o l o g y s t m e t u r o i no r d e rt or e e o g n i z ea n d c a p t u r | ef i g u r e s , m i n i m a l a n g l ep r i n c i p l ea n d i n e r t i ap r i n c i p l e8 r e a p p l i e di nt h i sp a p e rt or e a l i z ep o l y g o n sa n df o l dl i n e s p i c k i n gu p o 幽酊v i 船，t h ea u t h o r a p p l i e ss t e pa r cv e c t o f i z a t i o na l g o r i t h m ，d i r e c t i o ns t a t i s t i cd i s t a n c em o r p h o l o g y , n o i s e - r e m o v i n g a l g o r i t h ma n ds o m e b a s i co p e r a t i o nt o w a r d sb i n a r yi m a g e t h es y s t e mb u i l tc a nr e e s t a b l i s ht h e f i g u r e s o r i g i n a ls h a p e f a s t e ra n d b e t t e r , a n dg e t a l le x c e l l e n t r e s u l ta f t e rv e e t o r i z a t i o n a tp r e s e n tt h er e s e a r c ha b o u tv e c t o f i = f i o ni sm a i n l ya m o n gt h ee n g i n e e r i n gi m a g e 1 1 1 e m e t h o dd e s i g n e di nt h i sp a p e rr e a l i z e st h ei n t e r f a c ew i t hm a p l a f ow h i c hi sag i sg o t d _ r ea n d s a t i s f i e s t h e d e m a n d o f o l s i t h a s t h e o r y m e a n i n g a n d a p p t i c a f t o n v a l u e i n g s 。 k e yw o r d s ：g i s ：s p a r s ep i x e i ：v o e t o r i z a t i o mb i n a 略i m a g e ；t o p o l o 科 独创性说明 作者郑重声明：本硕士学位论文是我个人在导师指导下进行的研究 工作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 大连理工大学或其他单位的学位或证书所使用过的材料。与我一同工作 的同志对本研究所做的贡献均已在论文中做了明确的说明并表示了谢 意。 作者签名：扬圭左日期：2 嫂三生三旦呈旦 大连理工大学硕士学位论文 1 绪论 1 1 地图矢量化的过程及发展 地图矢量化是综合运用图像工程、图形工程、智能工程和地理学等多门学科的理论 方法，实现计算机理解地图图像的新领域。其过程也体现了这些方面的应用”l 。 1 1 1 栅格数据结构和矢量数据结构 地理信息系统必须在计算机上运行，目前输入计算机中的地图依存储形式的不同分 为两种，一种以栅格形式存储，_ 另一种以矢量形式存储。地理信息系统软件支持的主要 空刚数据结构有栅格数据结构和矢量数据结构两种形式。 ( 1 ) 栅格数据结构是以象素为单位描述图像，象素与所表达的真实空间实体没有直 接的对应关系。可以把一幅栅格图像考虑为一个矩阵，矩阵中的任一元素对应于图像中 的一个点，而相应的值对应于该点的灰度级，数字矩阵中的元素叫做象素。如果所有的 象素有且仅有两个献度级( 黑或白) ，则称其为二值图像，也即位图；否则称其为灰度 图像或彩色图像。地图经扫描仪扫描后，初步保存为栅格图像( 常见的格式有t 口f 、 b m p 、p c x 、j p e g 等) 。栅格数据表示的图像细腻逼真，便于描述边界复杂和模糊的 事物。 栅格图像在地理信息应用领域有着这样的缺陷：首先，栅格图像文件对图像每一象 素点( 不管是前景还是背景象素) 都要保存，所以其存储开销特别大。由于所占的存储 空间大，很难建立大幅面大比例尺地图。一张a 2 幅面的黑自图，按3 0 0 d p i 扫描后，图像 就将占4 兆多的存储空间，这样1 0 0 张图纸将占去4 0 0 多兆存储空间，如此大的文件计算 机很难操作。另外，不能对图像上的任一对象( 曲线、文字或符号) 进行属性修改、拷 贝、移动及删除等图形编辑操作，更不能进行拓扑求解，只能对某个矩形区域内的所有 象素同时进行图像编辑操作。此外，当图像进行放大或缩小显示时，图像信息会发生失 真。 陀) 矢量数据结构是以图形元素为单位描述，统一的单元是点、线和多边形。矢量 对象是以矢量的形式，即用方向和大小来综合表示目标的形式描述的对象。例如画面上 的一段直线，一个矩形，一个点，一个圆，一个填充的封闭区域等等。矢量图形 文件就是由这些矢量对象组合而成的描述性文件。 矢量数据结构是人们最熟悉的图形表达方式，对于线画地图来说，用矢量数据来记 录往往比栅格数据节省存储空| 、日j 。3 0 0 张a 2 幅面1 ：5 0 0 的地图，以矢量形式存储所占 电子地图中地理对象的智能识别研究 的存储空间也不过几十兆。以现在计算机的速度，操作几十兆的文件是非常容易的。另 外，由于各个地物在图形存储上是独立的，这使计算机操作和分析都更加容易，可以给 每一个独立的图形添加属性信息。并且矢量格式有很大的灵活性，图形的缩放旋转容 易，空间位置精度高。而这些特点正是地理信息系统所需要的。 1 1 2 地图矢量化的提出 矢量结构和栅格结构的相互转换，是地理信息系统的基本功能之一。而从栅格格式 到矢量格式的转换，特别是扫描图像的自动识别，仍是目前研究的重点 4 1 。 目前，把纸质地图转换成矢量地图主要有三种手段：一是人工屏幕数字化；二是使 用数字化仪数字化：三是利用计算机对地图扫描图像进行矢量化。 人工屏幕数字化方法是通过手工的方式，逐一提取地物的图形特征点，实现地物分 离。这一工作十分繁琐，效率低，丽且精确度很难保证。但该方法目前仍是制作矢量地 图的主要手段，因此当前在建设地理信息系统的工作中，矢量地图的制作占去了6 0 的 工作量。 使用数字化仪输入图纸时，需要设计人员在数字化仪上作图，作图过程中，把线段 的两个端点有意地突出，输入计算机后所生成的草图，其识别也是十分困难的。对己有 的图纸输入，数字化仪则根本无能为力。 以上这两种方法因其低效率，已使纸质地图矢量化成为“瓶颈”问题，极大地阻碍 了地理信息系统的应用和发展。计算机地图矢量化与以上两种方法不同，它实际上是一 种利用计算机把以栅格形式存储的地图转换成以矢量形式存储的地图的技术。在矢量化 过程中，计算机对地图扫描图像进行分析，提取地物图形的特征，进而使地物分离开 来，并存储各自的特征图形。 计算机地图矢量化以其高效率、高精度越来越受到关注，已成为科技人员的研究热 点。随着计算机辅助设计( c a d ) 、计算机图形学( c g ) 和计算机图像处理( c i p ) 等 学科的出现，图像矢量化的发展也越来越迅速。地理信息系统( g i s ) 、全球定位系统 ( g p s ) 、遥感技术( r s ) 的出现更为地图矢量化开辟了广阔的应用空间。未来的地图 自动矢龟化必将是建立地理信息系统的重要手段，应用全球定位系统和遥感技术的基 础。 2 大连理工大学硕士学位论文 1 1 3 地图矢量化的发展前景圈同 值得一提的是工程图矢量化比地图矢量化起步要早，在理论和实践方面的尝试比地 图矢量化要多。国外6 0 年代就有人进行这方面的研究，但当时限于计算机技术的发展 程度及普及率等因素，研究进展较缓慢。7 0 年代研究进入起步阶段，8 0 年代开始有实 用的系统问世。如挪威与德国m b b 合资的s y s s c a n 、美国的a n a t e c h 、m e t a g r a p h i c s 等 系统。国内也已有不少单位从事电路图和机械图的扫描处理识别研究。如清华大学、中 科院自动化研究所、中国科技大学等，并相继推出了矢量化系统。特别近几年来，随着 c a d 技术的发展和推广，一些公司也纷纷登场，使得国内在此领域的研究达到了高 潮。 地图矢量化在国外开始于7 0 年代，不久就有系统问世。如：美国工程兵测绘研究 所和美国地质测量局从7 0 年代中期就开始从事这方面的研究，并在栅格数据的处理与 矢量化方面取得了不少的成就。国内这方面的研究则是在近几年才刚刚开始。但由于地 图矢量化的市场潜力大，所以其发展较快，到目前为止国内已有多个软件系统问世，如 e p s c a n 2 0 0 0 、g e o l m a g e r 、d e o s c a n 等，但功能仍不完善。 从以上看来，地图矢量化与工程图矢量化在发展历史和所处领域有很多相同之处， 而且两者的研究对象和研究方法也类似。事实上地图矢量化的理论方法很多来自于工程 图矢量化，但两者又有区别，矢量化系统一般不能通用。 不论哪个学科、哪种技术、其发展越是与应用息息相关，应用前景越广阔，其发展 空间就越大，应用需求越迫切，其发展速度就越快。目前在国内地图矢量化的发展滞后 了很多，以至于在一些工程应用中，地图矢量化被忽视了，失去了发挥其高效、准确特 点的机会。因此面对我国地理信息系统g i s 的应用己全面铺开，应用领域迅速扩大的大 好形势，地图矢量化应抓住机会，快速发展。可以说地图矢量化技术成熟得越早，其市 场价值越大，服务社会的意义越大。 1 2 地图矢量化技术概况 近些年来，国内外有关学者在这一领域进行了广泛而深入的研究，而且随着各相关 学科的发展，各种新矢量化方法和新工具不断被引入到这项技术中，也已取得了一定的 成就【 0 1 。但目前矢量化的准确性和速度仍达不到预期的目标，仍有待于更深入的研 究。当前国内外对矢量化的研究多以工程图纸为主，市场上大部分自动矢量化软件也是 针对工程图设计的。地图扫描矢量化与之有着相同的本质，然而由于二者有着不同的特 点，甚至有些特点是截然不同的。所以对地图扫描矢量化研究可以借鉴一些工程图纸矢 3 。 电子地图中地理对象的智能识别研究 量化的技术，但针对地图特点进行专门研究是很有必要的。目前，在工程图纸矢量化的 多年研究和实践中，逐步形成了几种比较有效的矢量化算法，大致可以分为两类，即基 于细化的方法和基于非细化的方法。在基于非细化的方法中，主要有：基于轮廓线的方 法、基于邻接图的方法、基于网格的方法、基于图段合并的方法、h o u g h 变换法以及基 于稀疏象素跟踪的方法等。 ( 1 ) 基于细化的方法 细化卧”】是种简化图像的方法，对图像进行细化处理提取其骨架，在图像处理和模 式识别中得到了广泛的研究。所谓细化就是采用各种边界腐蚀操作逐层剥去图像的外边 界象素点，直到留下单象素宽的骨架点并将其转化成链码表示，然后通过折线拟台将链 码转化成低级矢量格式( 直线段或折线段) ，最后用基于矢量的图形识别方法在短线段 中识别出其中的图形对象。这类方法的缺点是丢失了线宽信息、在无交点处对噪音敏感 和在交点处造成畸变( 如图1 1 所示) 。虽然有些研究工作1 1 4 】试图在细化后立即修正交 点畸变来减少线段拟合与图形识别的难度，但由于工程图中相交情况变化太多和细化算 法的其他缺箔，上述研究收效并不明显。此外，反复遍历象素点和大量的短线段合并使 细化方法速度很慢。 ( a ) 细化前嘞细化后的骨架 图1 1 基于细化的方法 f i g , l la l g o r i t h mb a s e d o rt h i n n i n g r 2 】基于轮廓线的方法 轮廓特征也可表达图像的有用信息。这类利用图像轮廓进行识别处理的方法就是轮 廓匹配法l ”i 。基本步骤是：轮廓提取；轮廓匹配；轮廓对骨架化；骨架拼接， 矢量重建图形。 轮廓匹目b 方法通常是与细化算法结合在一起的。轮廓匹配方法是通过跟踪轮廓象素 和匹配轮廓矢量，得到图线的中间骨架矢量。这种方法虽然可以避免遍历全部象素点并 4 大连理t 大学硕士学位论文 能保持线宽信息，但由于在相交、粘连处无法找到轮廓时，必然会将一个完整的图形对 象分为多段，并且当线条位图退化时，轮廓之间常存在一对多的对应关系，给匹配带来 困难。 ( 3 ) 基于邻接图的方法 基于邻接图的方法f 1 6 1 1 7 1 1 “，它以连通图段为单元作图象处理。连通图段是由一串 上下相互连通的行程编码组成，包含了较大范围的图像信息；算法中直线、圆弧的识别 过程就是图段的分裂、合并和匹配的过程。基本步骤为：图像编码，用行程段表示图 形( 如图1 2 所示) ；提取节点域：由节点域确定矢量线段；由矢量线段依照拓 扑关系重建图形。基于邻接图的算法在处理象素时有一定的局限性。地图，特别是大比 例地形图具有与工程图完全不同的特点，它所包含的大量道路、房屋轮廓等较不规整的 曲线。利用基于邻接图的算法对其进行自动识别和矢量化并不合适。 在整体识别的前提下，有人提出了以矩形【1 9 1 1 2 0 或梯形【2 1 】为单元，将图纸图像转化 成以矩形块为节点、以块与块之间的几何邻接关系为边的条块图，然后对节点进行分类 识别。这些矩形块或梯形块是在扫描过程中按照一定的规则，由若干扫描串组合成的。 这种方法适用于规则线形，是针对工程图纸设计的。而g i s 道路中的地图的道、建筑物 轮廓并不是规则的图形，所以不适合采用这种方法。 图1 2 基于邻接图的方法 f i g 1 2a l g o r i t h mb a s e do na d j a c e n c yi m a g e ( 4 ) 基于图段合并方法 基于图段合并的方法【篮】是根据交点处行程段长度变化，将图线分割为图段，即由图 1 3 ( a ) 得到图1 3 ( b ) ，计算出各段的解析参数。然后对各短图线进行同向性检测，计算上。 与的夹角卢，若卢 s l o p e p l i n e n e x t - s l o p el w i d t h p l i n e n e x t - w i d t hi e n d p o i n t ，p l i n e n e x t - e n d p o i n t ) s e g s l o p e = i n e c u r - s l o p e + p l i n e n e x t - s l o p e ) 2 。0 9 ) 3 4 2 多边形、折线重构 所谓重构是指从弧段建立多边形或折线拓扑关系的过程。通俗的讲，就是找出多个 弧段中哪些能构成多边形或折线。 经过此前的各个处理过程后，包括直线图形的提取后，直线链列表中所存储的，实 际上只剩下多边形和折线的数据。本文采用最小角法则对多边形进行重构，采用惯性原 则对折线进行重构。 2 5 电子地图中地理对象的褶能识别研究 按最小角法则重构多边形的思路是：从一个种子直线段( 满足起始搜索条件的直线 段) 的一端开始，找出与之夹角最小的拓扑邻接直线段，并以此直线段作为新的起始搜 索直线段，从他的另一端出发重复以上过程继续搜索，直到回到第一个出发的种子直线 段的另一端或某个直线段没有拓扑邻接直线段的端点为止。如果回到种子直线段另一 端，则所搜索出的直线段构成一个多边形，否则留给下一步重构折线。 其中拓扑邻接直线段的夹角定义如下：两个拓扑邻接直线段在它们的公共端点处， 沿逆时针方向的夹角。范围在0 到2 x p i 之间。它可由两个拓扑邻接直线段与以公共端 原点的x 轴正向之间的逆时针方向夹角之差来求得。因而也就可以由两个直线段的斜 率来表征。比如线段a b 和a c 是拓扑邻接的，在公共端点a 处的央角b a c 就是 a r c t a n ( s l o p e a c ) 一a r c t m a ( s l o p e a b ) 。 按惯性原则重构折线的思路基本与重构多边形的思路相同，只是，种子直线段的一 端应为结束点。搜索下一个目标矢量段的条件是：目标矢量段和当前矢量线段在公共交 点处的夹角与当前矢量线段和前一个满足条件的矢量段之间的央角最相近。因为，折线 在一定程度上也是有延伸性的，此即惯性原则。 3 5 域值设置 典型的矢量化算法都需要设置些重要的域值或者参数。例如：基于运算法则的网 格矢量化算法的网格大小设置和o o z 算法的扫描线间隔。和其它的算法一样，设定这 些参数的大小对于算法的整体性能来说意义深远。 针对不同的图像，要想达到虽好的效果，域值的设置也有所不同。从理论和实际两 方面来考虑，参数的设置应该达到对大部分的图像而言效果最佳。 本文所述的矢量化算法和其它算法一样，在矢量化过程中也需要定义一些重要的参 数值，在这一节里着重讲一下算法中用到的三个参数的设置及这些参数在整个识别过程 中的作用，并用象素质量评估协议吲来对本文算法进行评价口4 确】。 3 5 1 矢量化算法质量指标 文献 3 3 】提出直线识别算法的评估协议，在此协议中用两个指标来衡量识别算法的 质量，分别是识别率d 。和误识别率f d ，公式如下： 卟掣 2 6 ( 3 1 0 ) 大连理工大学硕士学位论文 煳悔纠一掣 其中r 为图像中真正属于线条的象素集合，p d 表示重构出的矢量线条对应的象素集 合。识别率d ，代表算法的识别能力，d ，值越大表明矢量化算法越好：误识别率f p 表示 矢量化算法在识别上出现的错误，f d 值越小表明矢量化算法越好。结合识别率和误识别 率，定义象素重建指标p r i ( p i x e lr e v e r yi n d e x ) ，如下式所示： p r i = ( d p + 1 一f p ) 2 ( 3 - 1 2 ) p r i 表示整体识别性能，它综合考虑d 。和f p 两方面的因素，p r i 的值与性能成正比， 即p r i 越大表明矢量化算法越好。 3 5 2 三个域值的设置 在本文直线整体矢量化算法中可以看到有三个非常重要的参数，它们的设置可以影 响整个算法的质量，这三个参数分别是：扫描地图过程中扫描线间隔，矢量化跟踪过程 中定义的最大跟踪步长，在关键点提取过程中用到的最大多边形误差。 1 扫描线间隔 矢量化过程开始时，栅格图形被逐行扫描，相邻两条扫描线之间的距离即为扫描线 问隔，如图3 1 2 所示。当扫描线遇到黑象素点时则进入初始点搜索过程，由此可知， 如果扫描线的间隔逐渐增加，将会有越来越多的线被漏掉。 由公式( 3 1 0 ) 、( 3 1 1 ) 失u ，当扫描线间隔增加时，d 。下降。因为没有错误的线被检 测，f d 还不会受到什么直接的影响，从整体上来看，p r i 将会相应的下降。这个现象如 图3 1 2 所示。 ( a ) 扫描线间隔大，未识别直线( b ) 识别出直线 图3 1 2 扫描线间隔影响示意图 f 喀3 1 2s c h e m eo f s c a n n i n gl i n ei n t e r v a li m p a c t 从理沦上说，如果扫描线间隔设置为1 的话，那么就不会漏掉任何一条直线，p r i 也会达到最大。但是稀疏象素的“稀疏”有效性将会减小，算法速度将会大大减慢一所 一2 7 电子地图中地理对象的智能识别研究 以经过反复实验，定义扫描线间隔为小于直线线宽，取值为7 ，这样既保证了较少漏识 直线的数量，同时也保证了矢量化的速度。 2 最大跟踪步长 图3 1 3 最大跟踪步长影响示意图 f i g 3 1 3s c h e m eo fm a x i m a lt r a c k i n gs t e pi m p a c t 从图3 1 3 中可以看到最大跟踪步长可以影响某些特殊区域的识别质量。 图3 1 3 ( a ) 中线条区域里有一个空洞，图3 1 3 中有个凸起，根据最大线宽误差的 设置，两种情况都偏离了线宽致的条件，跟踪过程将会停止，进入线条网的处理。当 最大跟踪步长小于空洞和凸起的长度，这段直线区域将会被分成三段截然不同的线段。 相反，如果最大跟踪步长大于空洞和凸起的长度，这段直线区域将会识别为一条直线， 如图3 1 3 ( c ) 、( d ) 所示。 由公式( 3 1 0 ) 、( 3 1 1 ) 知，图3 1 3 ( c ) 中的d p 和图( a ) 中的d p 相同，面图( c ) 中的f p 比 图( a ) 中的f p 值要高，图( d ) 中的d ，要小于图( ”中的d ，圈( d ) 中的f p 与图( b ) 中的f p 值 相同。一般来讲，最大跟踪步长的改变对性能指标的影响不是很明显，所以可以取最大 跟踪步长默认值为2 0 。 3 最大多边形误差 当最大多边形误差值增加时，将会有更多的点被删除掉，假设该多边性正好为之所 求矢量线，然而有的点却被删除了，这时d 。变小，同时f ：增大，因此p 的值将随着 最大多边形误差值的增大而减小。当图像中存在很多圆弧段的时候，这个参数值的大小 将会明显影响整个地图识别的质量。为了能够正确地反映原始图像中的图形信息，这个 参数应该设置为0 5 1 o 之间数值。经过反复实验，最大多边形误差设置为0 7 ，这个 值可以获得最佳的识别结果及最快的识别速度。 2 8 大连理工大学硕士学位论文 图3 1 4 直线矢量化流程图 f i 晷3 1 4f l o w c h a r to f l i n ev e c t o r i z a t i o n 3 6 直线矢量化流程 图3 ，1 4 给出了整个直线矢量化的流程。基于稀疏象素的方向无关的直线对象的整 体矢量化是逐个线条网进行的： ( 1 ) 扫描地图二值图像寻找稳定的起始点： ( 2 ) 判断跟踪方向，跟踪确定直线的中轴点，提取关键点，确定直线线宽； ( 3 ) 擦除原直线栅格数据，减少图像数据量，降低复杂度，避免重复识别； ( 交叉区域的处理可以确定当前交叉区域内所有直线的数目及方向； 2 9 电子地翻中地理对象的智能识别研究 ( 5 ) 当前线条网的识别结束后，继续扫描图像，寻找下一个稳定的起始点，重复 第( 1 ) 步，直到扫描完整个图像； ( 6 ) 直线、多边形、折线的重构。 3 7 性能对比 直线矢量化方法的性能主要由以下几个方面来衡量：直线参数的识别精度、对各方 向直线的适应性和计算复杂度。表3 1 从理论上对本文所用的方法与现有方法的性能进 行了分析和对比。 表3 1 矢量化方法的性能对比 t a b l e3 1p e r f o r m a n c e c o m p a r i s o no f v e e t o r i z a t i a nm e t h o d s 从以上对比可以得出结论，基于稀疏象素的方向无关的直线对象矢量化方法比现有 的直线矢量化方法具有明显的优点。本文直线矢量化方法通过搜索初始点获得跟踪方向 和宽度特征，然后经定向跟踪次性识别整条直线，从根本上避免了分段识别后再合并 时所需的大量遍历与拼接操作，简化了矢量化过程。因为没有耗时的处理( 如细化、轮 廓跟踪、行程编码等) ，因而在速度上优于其他矢量化方法。又由于不是访问所有象 3 0 大连理工大学硕士学位论文 素，较之以象素为处理单元的算法减少了大量数据，矢量化速度明显提高。并通过擦除 仪仅对应于已识别直线的位图的方法使图像数据逐步简化，从而很好的解决了粘连、相 交的分离难题。因此，其直线矢量化的速度和精度比现有方法有较大程度的提高。 3 8 小结 本章给出整体矢量化的完整概念，提出了基于稀疏象素的方向无关的直线对象整体 矢量化方法。此方法较之以象素为处理单元的算法减少了大量数据，抗干扰性明显增 强，矢量化速度明显提高，充分利用了线条之间的相交关系实现线条网的整体矢量化， 并通过保留交点信息的擦除过程使图像数据逐步简化，从而很好的解决了粘连、相交的 分离难题。实验结果和理论分析均表明了基于稀疏象素的方向无关的直线对象整体矢量 化方法显著提高了直线识别的速度与精度。 3 1 i 旦子地图中地理对象的智能识别研究 4 圆弧的矢量化 圆弧是地图中的常见图形对象。本文基于象素跟踪方法，结合实际地图中圆弧的特 点，设计了步进圆弧矢量化方法。本章将具体介绍该方法的实现原理。 4 1 圆弧矢量化方法概述 现有线条矢量化方法大都具有处理圆弧的能力。现有圆弧矢量化方法可以分为三 类：基于型值点的方法【3 7 l 口剐、h 0 u 曲变换法1 3 7 】【3 8 】和象素跟踪方法1 2 7 1 1 3 9 1 4 0 。 基于型值点的方法通过不同的途径从图像中获得一个圆弧的型值点集合，从图像的 中心点集合中搜集可能属于同一个圆弧的中心点，然后由拟合公式计算出圆弧的参数。 该方法在型值点畸变时不够稳定，容易导致拟合圆弧偏离背景位图。并且，该方法依赖 大量迭代运算求解非线性方程组，因此速度较慢。 h o u e 扣变换法利用圆的j l 何对称性来检测圆。首先，对图像做水平和垂直扫描分别 统计每个点作为任意两个象索区域边界点的中点的次数；其次，对达至统计峰值的点做 直线h o u g h 变换得到图像的一组水平对称轴和垂直对称轴；然后，计算水平对称轴和垂 直对称轴的交点作为候选圆心：最后，对每个候选圆心收集关于该水平、垂直对称轴对 称的边界点，形成候选圆的子图像。该方法因为需要记录大量信息，并且采用h o u g h 变 换从而运算速度较慢，同时会将其它对称图形( 如矩形) 也检测出来，因此不适合地图 中复杂情况。 象素跟踪方法则利用了圆弧的几何特性来检测圆弧：圆弧上任意两点连线( 称为 弦) 的垂直平分线一定经过圆心。因此，如果可以在一个象素连通区中找到三段中垂线 共点的相邻段，则该连通区中可能存在圆弧。象素跟踪方法通常从图像中搜索满足此几 何特性的若干连通象素段作为跟踪圆弧的起点和计算初始圆弧参数。象素跟踪方法不需 要预先提取型值点，也不需要复杂的计算，因此速度较快。但是在实际应用过程中，象 素跟踪方法也有一些缺陷，比如直线链上的- , b 段直线段( 长度很小) 是很难确定出圆 弧的准确参数的，因此得出的矢量圆弧也是不准确的；再比如直线链的某段直线的长度 很大时，则说明该段直线不属于圆弧，那么接下来的圆弧矢量化及其跟踪过程将是徒劳 无功的。 本文基于象素跟踪方法，结合实际应用过程中遇到的问题，在原有的方法上进行了 改迸，有效地避免了上述象素跟踪方法在圆弧矢量化过程中的不足。圆弧的矢量化过程 可以简单的描述为：圆弧的分割；部分圆弧矢量化；圆弧跟踪：最后矢量化整个圆弧。 3 2 大连理工大学硕士学位论文 这个过程正体现了步进的原则，因此本文的圆弧矢量化定义为步进圆弧矢量化方法，其 中关于象素跟踪圆弧矢量化方法内容参考文献1 2 7 1 。 4 2 步进圆弧矢量化算法 由上一章的直线对象整体矢量化得知，各个圆弧段已经被近似为首尾相接的直线 链，完成了圆弧分割的过程。 为了构建圆弧，需要满足下列几条原则： 第一，直线链的各直线段弯曲方向一致，或者顺时针方向，或者逆时针方向； 第二，相邻直线段线宽近似相等； 第三，各直线段上的特征点须满足等式( 4 i ) 、( 4 2 ) ： 1 1 ， i r d p i l ；i = o 1 ，n ( 4 1 ) 卜d e i 卜詈；i - o 1 ，n ( 4 2 ) 其中r 为圆弧半径，w 为线宽，d p i 为从圆心到第i 条直线段特征点的距离，d e i 为从圆 心到第i 条直线段内侧边缘的距离。 第四，计算直线段两端点问的距离长度，如果直线段的长度小于一个给定的域值 ( 取值为5 0 个象素) ，可以继续进行圆弧的矢量化，如果大于给定的域值，则说明该 直线段不属于圆弧段，应该属于直线，则停止圆弧的矢量化过程。 第五，直线链上的直线段的长度如果很小，小于一个给定的域值( 取值为8 个象 素) ，结果是很难确定出圆弧的准确参数的，所以，此种情况下，该直线段扩展下一个 直线段，两条直线段合二为一，继续进行圆弧的矢量化。 出圆弧的几何特性知：圆弧上任意两点连线( 称为弦) 的垂直平分线一定经过圆 一1 1 , ，即多条弦的垂直平分线必交于一点。但是这种情况只在理想情况下发生，由于图像 质量原因，更由于经过了直线矢量化阶段，多条弦的垂直平分线不可能准确的交于一 点，多少会有一些误差，但是可以肯定的是垂直平分线的交点肯定落在个很小的矩形 范围内，称这个矩形区域为矩形包围盒r s b ( r e c t a n g l es u r r o u d i n gb o x ) ，下面就来介 绍确定矩形包围盒的方法。 如图4 1 所示，首先连接图中三条直线段的两个端点，取垂直平分线为p b 。，然后 取每条直线段的垂直平分线为p b 。，由p b 与p b 0 相交得到交点e ，如图4 1 所示。可 以得知所有的r 都落在p b 。直线上，在p b 0 上确定一个最小的范围r ，使在r 上包含所 3 3 电子地图中地理对蒙的智能识别研究 有的交点p ，r 即为所要确定的矩形区域的长，r s b 的宽可以取直线段的线宽，如图 4 1 所示确定灰色矩形包围盒r s b ，r s b 所包含的区域就是所要找的包含圆心的矩形包 副盒。 图4 1 直线链到圆弧的转化过程示意图p b o f i g , 4 1s c h e m eo fc o n v e r s i o nf r o mp o l y l i n et oa r c 在所有的b 点中选出一个平均值点p c ，定义p c 为临时圆心，计算从p c 到各个直线 段端点的距离，再取所有距离的平均值，这个平均的距离定义为临时半径r ，判断r 是 否满足等式( 4 1 ) 、( 4 2 ) ，如果条件满足则这条直线链可以转化为圆弧，如果其中任何一 个条件不满足的话，则当前的直线链不能拟合为矢量圆弧，当前圆弧矢量化过程停止。 4 3 圆弧跟踪 根据上节理论，如果判定该直线链为圆弧，则通过拟合公式可拟合出该圆弧。到此 为止已经识别出了- d , 段圆弧，下面就通过圆弧的跟踪来完成圆弧的扩展，最终识别出 整个圆弧。 每一段圆弧有两个扩展方向，分别从两个端点开始扩展，每一个方向的扩展都是通 过端点的反复向外延伸来完成的，跟踪完成一个弧段就要调整一次先前圆弧的参数。圆 弧的扩展先从扩展区域开始，扩展区域定义为一个正方形，正方形的边定义为两个线 3 4 大连理工大学硕士学位论文 宽。当前圆弧与带扩展圆弧( 或者为直线链) 满足下面三个条件时，就可以进行圆弧的 跟踪： ( 1 ) 线宽大小接近：待跟踪的两个弧段的线宽大小相等或者接近，线宽的差不得 大于一个给定的域值( 一般定义为两个象素宽) 。 ( 2 ) 共线性：带跟踪的两段直线段可能会形成一个夹角，这个夹角的角度应该小 于，r 3 。 ( 3 ) 连续性：当前弧段和待跟踪的弧段之间的间隙不得大于两倍的线宽，并且间 隙里面充满了黑象素点，黑象素点的数量要达到间隙的8 0 。 每跟踪完成一次扩展之后，就要动态的调整一次圆弧的参数，新参数的确定可以 参照图4 1 及文献 2 7 1 。 4 4 工作流程图 该步进圆弧矢量化算法在圆弧已完成分割的基础上，从一段属于圆弧的直线链出 发，跟踪出属于同一个圆的其他直线段，在跟踪过程中动态的调整参数，使最终求得 的圆或者圆弧与原有信息吻合。 整个图像的圆弧矢量化流程如图4 2 所示。 3 5 也子地图中地理对象的智能识别研究 图4 2 圆弧矢量化流程图 f i g 4 2f l o wc h a r to f a r c v e c t o r i 盟t i o n 4 5 小结 本章给出了步进圆弧矢量化方法，该方法利用了圆弧的几何特性来检测圆弧：圆弧 卜任意两点连线( 弦) 的垂直平分线一定经过圆心。通过从图像中搜索满足此几何特性 的若干连通直线段作为跟踪圆弧的起点和计算初始圆弧参数。由于不需要预先提取型值 点，也不需要复杂的计算，因此运算速度较快。 3 6 大连理工大学硕士学位论文 5 地图矢量化系统的功能与实现 前面几章对扫描地图矢量化技术的现状进行了分析研究，针对原有矢量化算法的不 足和人类读图识图的特点，提出了基于稀疏象素的方向无关的直线对象整体矢量化方 法，并对其原理和实现算法做了详细讨论。在前面几章的分析基础上，作者设计实现了 一个地图识别实验系统a u t o v e c t o r 。本章将介绍此实验系统的功能及使用。 5 1 地图矢量化应用程序a u t o v e c t o r 框架 5 1 1a u t o v e c t o r 程序功能 本文设计实现的实验系统是在w i n d o w s 2 0 0 0 平台下，采用v i s u a lc + 十6 0 编程实现 的”矧。 地图矢量化应用程序的作用是把地图以矢量的形式输入计算机。地图扫描后得到图 像( 本文以木b m p 位图文件为操作对象) ，矢量文件将以w i n d o w s 通用图形数据交换格 式存储，如图5 1 所示。程序可以实现多种栅格图像格式( b m p ，$ j p g ， t i f ) 的读取、 显示和存储；基本图形的绘制、选取、删除、存储；扫描地图的处理( 细化、去噪、膨 胀、腐蚀、开运算、闭运算) ；与g i s 软件m a p i n f o 的接口；地图扫描图像的自动矢量 化，能够较成功的提取出直线、折线、多边形和圆弧。 地絮b m 粕p 像h 姻短a u t o 性v e c t o 雕r 序h 煳紫m 煺i f 姘h 蚴系统 $ illi il 图像颓处理白动欠量化矢量编辑 曩ff 薰lj 曩ff 蓁fl 嘉j 霎li 耋f 誓i 曩ii 量ii 萎jl 季 图5 1 地图矢量化应用程序功能框图 f i g 5 1d i a g r a m o f f u n c t i o no f m a pr e c o g n i t i o np r o g r a m 3 7