§4.1 构建闭环识别系统的探讨
第三章中笔者提出的道路识别系统均为开环系统，由算法处理的结果可以看出对于图像的提取是具有破坏性的，整体是不可逆转的，无法趋向收敛和稳定，因此以下我们做了对闭环系统的尝试，试图能够换个角度找到合理解决问题的办法。
下面将阐述理论上阐述闭环系统的基本思想，以及实际中出现的问题。
§4.1.1 闭环系统构建的基本思想
构建一个闭环系统，称为地图道路信息综合识别系统。把地图中不同类型的层次识别过程作为这个闭环系统中并联的子系统，通过对它们输出区域的比较，使闭环系统的综合输出的道路信息成为可观变量，对每个层次识别子过程进行反馈优化调节，再综合获得改善的道路网络识别率。图4-1是其示意图。
图4-1 地图道路信息综合识别系统原理方框图
1) 图4-1中，系统首先对需要处理的交通地图栅格图像进行模式识别前的常规处理，包括消噪、清除孤立点、清除文字图标、色调亮度反差调整等，使常规预处理后的栅格图像基本清晰地由两类（道路网络与非路区域）图层所覆盖。由于交通地图中道路网络与非路区域均具有与孤立点、文字、图标明显不同的特征，通常对孤立块、细线条段用其邻域或两侧的色彩取代即可获得有效的常规处理。常规处理后的栅格图像分别进入图象道路网络图层模式识别过程（含改善道路网络识别的图象预处理过程）与非路区域图层模式识别过程（含改善非路区域识别的图象预处理过程）。这样的设计思路，使得识别道路网络过程与识别非路区域过程均成为自动受控（通过阀值调整或其它策略）的模式识别过程。
2) 建立直接识别道路的“道路网络图层模式识别过程系统”（Road子系统）。研究和试验基于道路的色彩、线状、连通、网络等特征进行综合识别的多种道路网络层模式识别的特定算法。解析出道路识别率与误识别率受其特征评价函数阀值影响的统计模型。识别出的“道路” 记为R。但R可能只包含部分真实道路（计为R1），R也可能涵盖了部分不是路的区域（计为A2），故有R = R1∪A2。对选定的算法，找出合适的特征评价函数阀值初始值使R1较大而A2极小。
3) 建立排除道路的“非路区域图层模式识别过程系统”（Area子系统）。基于交通地图源的“非路即区域”特征，研究和试验基于区域的色彩、面状、孤立、闭合等特征进行综合识别的多种非路区域图层模式识别的特定算法。解析出非道路区域识别率与误识别率受其特征评价函数阀值影响的统计规律。识别出的“非路区域”记为A。但A可能只包含部分非路区域（计为A1），A也可能涵盖了部分真实道路（计为R2），故有A = A1∪R2。对选定的算法，找出合适的特征评价函数阀值初始值使A1较大而R2极小。
4) 构建“地图道路信息综合识别系统”如图4-1。通过两个并联子过程（即“道路网络图层模式识别过程系统”与“非路区域图层模式识别过程系统”）对输入的彩色栅格交通地图各自处理，分别获得道路网络图层输出R与非路区域图层输出A。我们希望两图层（R、A）既不重合（即其交R∩A=0）又能完全覆盖整图总区域M（即其并R∪A = M）。注意到R∩A > 0时则并联子过程至少有一个存在误判，而R∪A < M时则并联子过程至少有一个存在漏判，因此我们取R∩A与R∪A作为综合识别系统的输出误差量测函数，并在此基础上，对两个并联子过程同时进行反馈决策控制。设计的一组反馈控制策略，分别用以调整Road、Area两子过程系统中的特征评价函数中的阀值矢量，使得道路网络图层Road、非路区域图层Area的识别输出R与A能够向我们希望的方向发展。也就是说，地图道路信息综合识别系统的优化目标数学表达式可表示为：R∩A → 0 （误判率→ 0）与 R∪A → M（漏判率→ 0）。这组反馈控制策略选择得当，可望同时实现R1 → R → 全部道路，同时Area子系统输出A1 → A → 全部非路区域。
5) 以上构建的地图道路信息综合识别系统（含Road、Area两个受控过程子系统）优化目标（R∩A → 0与R∪A → M）的实现过程，采用的反馈控制策略（道路识别阀值调整策略与非路区域阀值调整策略）应使得两个子系统分别获得输出R1 → R 与 A1 → A （即A2 → 0，R2 → 0），并且R∪A → M，从而有R1∪A1 → M（也即R → 全部道路网络，A → 全部非路区域）。本项目的主要任务就是对该系统优化过程的有效性与收敛性给出理论证明，推导出加快收敛速度的最优反馈控制策略，并在实际应用中加以验证。
§4.1.2 闭环系统无法避免的问题
合理的图像评价的客观指标。在目前人多数数字图像系统中，输入光图像都是采用先冻结再扫描方式将多维图像变成一维电信号，再对其进行处理、存贮、传输等加工变换方法来进行的，最后还要再组成多维图像信号。在这些过程中电气系统和外界影响将使得图像元素的精确分析变得十分复杂。另一方面图像只是传输视觉信息的媒介，对图像信息的认识理解是由人的视觉系统所决定的。不同的图像元素，人的感觉(理解)程度是不同的，这就是人的噪声视觉特性课题。这方面虽早己进行研究，但终因人的视觉系统本身未搞清楚而尚不能解决。所以现在还不能规定出确切的图像元素识别的客观指标，而只能进行一些主观评价研究。
实际系统中，理想化的道路和区域都是人为界定的。对于一幅未处理的地图而言，计算机并不知道道路和区域子集各自包含那些元素，只有通过人眼的主观评价以确定函数来对其进行分类。用计算机语言描述这些函数形成的判据，从而界定图像中每个元素的归属，因此无法避免人工交互的出现。
在第三章中，我们用不同的方法对道路和区域进行提取，但是如何定义一个客观的评价函数来进行误差判别以及完成对AR∩的评估函数设计，这是目前尚未能考虑好的问题。在4.2节中我们只是对局部反馈策略进行了探讨，对一种道路提取算法作了尝试。
§4.2 城市地图道路提取的一种尝试算法
算法思路：将道路的提取过程转变成提取道路的中心线过程，把提取道路的中心线作为的反馈，根据某些判据来判断道路的合理性，并产生相应的策略来清除噪声、修补区域、修补道路，过程框图如下图4-2。
过程框图中输入的是经过归一化的图像，这样则保留了原来图像中基本的道路和区域信息，减少误识别的可能性。从过程框图中可以看到对于输入图像进行去除噪声、细化、反馈修补、循环几种操作。 修补图归一化图提取噪声位置信息二值化细化八方向去噪声相同位置转换成区域提取细化线位置根据细化线形成判据并修补NY是否有象素被转换是否有象素被转换NY
图4-2局部闭环流程图
该处理包括以下几个算法步骤：八邻域方向的去噪，细化，图像修正。
§4.2.1 八邻域方向的去噪算法
首先分析图源中的噪声特征：噪声块全部位于区域内，如图4-3中的“中”、“国”、“技”、“大”、“学”、“院”等字，其特征就是噪声块被区域完全包围（图中用红色线框标出）；噪声块全部位于道路内，这种情况是存在的，但是很少见，因为位于道路上的噪声块一般是文字噪声块；噪声块位于道路上同时延伸到区域上，如“科”、“太湖新村”、“市”、“三”、“医”、“松”、“路”等字，这种情况比较复杂，是地图中噪声块最常见的存在形式。
图4-3 噪声特征的不同表现形式
为了研究地图中噪声块的细节特征，此处选取城市地图中的一部分，并进行放大观察。如图4-4所示，可以清晰地看见每个像素点。
地图上的道路看起来是弯曲的，但是单个噪声块所在的道路段的边缘线基本上是平行的（如4-3所示）；同时，单个噪声块在道路上并没有把表示道路的像素完全覆盖，如图4-4中的“安”字，这是由以文字形式出现的噪声块的自身特征决定的。
在图4-4中包括了噪声块的3种不同的存在形式：箭头1所指的像素块完全位于道路内；箭头2所指的像素块完全位于区域内；图3中的“安”字便是噪声既存在于道路中也存在于区域中的典型情况。
图4-4放大后的地图及其八邻域标向
如图4-4所示，选择3个噪声像素块中的6个像素点（分别用1，2，3，4，5，6指示，而且可以看到此6点周围分别有8条射线射向8个方向）来研究它们的外延特征。
用人眼观察这6个噪声像素，分析这些像素应该被聚类到道路像素类，还是聚类到区域像素类？显然，像素1应该聚类到道路像素类；像素2应该聚类到区域像素类；像素3位于道路和区域的边界上，可以保持不变；像素4应该聚类到道路像素类；像素5应该聚类到区域像素类；像素6位于道路和区域的边界上，可以保持不变。
然后，以所考察噪声像素为中心，建立一个极坐标，对0o、45o、90o、135o、180o、225o、270o、315o这8个方向上的像素进行搜索，穿过其它的噪声像素，直到发现区域像素、道路像素或边界。统计8个方向上所发现的道路像素、区域像素或边界的个数，并分别记为r、a和o，我们将r、a和o分别称为噪声像素外延特征参数；参数r和a的大小关系，称为噪声像素的外延特征。
在上一章中已经用贴标签算法将整副地图的所有像素被分为3类：道路像素类R、区域像素类A和噪声像素类N，所以任何一个噪声像素的外延特征参数都是固定的，统计结果也是确定的。统计6个像素的特征参数，得到各自的外延特征，并与人为聚类结果相比较，如下表：
从上表中可以看出，人为聚类结果与噪声的外延特征相一致：
当噪声的外延特征为r>a时，人为聚类结果是将噪声N聚类到道路像素类R；
当噪声的外延特征为r<a时，人为聚类结果是将噪声N聚类到区域像素类A；
当噪声的外延特征为r=a时，人为聚类结果是噪声像素位于道路和区域的边界，暂不聚类。
上述判据即为无偏聚类准则。当噪声像素位于道路和区域的边界的时候，这些边界噪声像素的外延特征为r=a。根据“无偏”聚类准则，这些噪声像素将不进行聚类，仍然归为噪声像素类N，所以，仅仅利用“无偏”聚类准则不可能将所有噪声进行聚类，这是由“无偏”聚类准则自身决定的。所以必须引入“有偏”聚类准则才能将残留的边界噪声像素完全聚类到道路像素类或区域像素类。
“有偏”聚类准则分类函数：就是对于噪声像素八邻域方向进行探测，直到探测到区域象素或道路象素为止，到边界没遇到区域或道路则此方向不计，探测到道路的方向数记为r，探测到区域的方向数记为a，当r＋1>a 时说明此噪声象素周围被道路所包围，就把它转换成道路象素；否则不做变换。多次循环达到没有象素转化时为止，这样做就是采用“有偏”准则，把噪声去除偏向于道路，尽量地清除了道路上的噪声，结果也就造成了道路的过识别，下文中对于这部分过识别我们将做出解决的方法。
去噪算法实现流程图如下：
图4-5八邻域延伸去噪流程图
§4.2.2 细化
这里的细化算法源自图像形态学中的骨架化算法，本图中抽取的骨架即为道路的中心线。
线细化，就是不断去除曲线上不影响连通性的轮廓像素的过程，在这个过程中保留曲线的多重像素，直到目标曲线所有点都是多重像素为止，对细化的一般要求是：保证细化后曲线的连通性；细化结果是原曲线的中心线；细化处理速度快；保留细线端点。
根据各种不同的应用，国内外已经发表了许多细化算法，如内接圆法、经典算法、异步算法、快速并行算法及并行八边算法等，不同的算法在处理速度和效果上各有其特点。使用的算法是在Hilditch细化算法[25]的基础上改造而成，试验表明它有较好的细化效果和很快的处理速度。
如果目标像素P同时满足以下条件，那么P可以被标记为可删除点。
1) P0+P2+P4+P6<=3，保证P是轮廓像素。
2) Pi(i=0-7)中至少有两个目标像素，保证不是端点。
3) Nc=1，保证P不是多重像素。
算法中还要用到两个序列，一个用来描述某一像素点是否被标记为可删除点，另一个记录剩余的目标像素点。最后一个序列对提高算法的速度起着至关重要的作用，因为细化过程中，剩余的目标像素点越来越少，如果在这时候还是扫描整幅地图，必然要浪费许多的时间。
算法流程如下：
1) 扫描整幅地图，将属于道路的目标像素点记录在目标序列中。
2) 扫描剩余的目标像素点，检测其是否需要删除，如果需要，就标记为可删除点，否则，标记为不可删除点。
3) 把标记为可删除的目标像素点全部从目标序列中删去。
4) 重复Step2,Step3知道没有目标像素点可以删除为止。
宽度为2的道路
但这样有一个缺点就是宽度为2的线将全部被删除。如上图所示的两行像素点都满足可删除的条件。怎么办呢，我们已经知道，一个目标像素点是否可被删除，是由其八邻域中目标像素点的分布来决定的。但是，如果其八邻域中的某一目标像素点已经被标记为可删除点了，那么这个目标像素点其实就不能在当作目标像素点来对待，因为这个点注定是要删除的了。所以八邻域中的被标记为可删除点的目标像素点就不能在作为目标像素点进行判定了。这样这个问题就解决了。在上图中，第一行像素点被标记为可删除点后，在判定第二行像素点时，因为第一行已经不属于目标像素点，所以，第二行像素点就不会也被判定为可删除点了。
宽度为3的道路
但是这样会使细化的结果不是原曲线的中心线了，如4-4所示，第一行首先被标记为可删除点，接着第二行也被标记为可删除点，结果把第三行剩下了。下面我把目标像素点是否属于可删除点的三个判定条件再重申一下：
1) P0+P2+P4+P6<=3，保证P是轮廓像素。在这个条件中，八邻域中的目标像素点不管标没标记为可删除点，都按1处理。
2) Pi(i=0-7)中至少有两个目标像素，保证不是端点。在这个条件中，被标记为可删除点的目标像素点就要按0来处理。
3) Nc=1，保证P不是多重像素。在这个条件中，被标记为可删除点的目标像素点也要按0来处理。
细化使道路变短
接下来对去除噪声后的图像进行二值化后提取道路的中心线（也就是细化线），其中心线如图4-6中黑色细线所示：
图4-6 中心线位置示意图
§4.2.3 图像修正
修正过程：
1) 噪声特别是文字，它的笔画宽度明显地小于道路的宽度。在去噪图中，经过中心线象素的同一直线方向上区域象素的距离小于道路宽度（这里为6个象素）时，则在修补图中把此相同位置距离上的象素用一种图中没有的颜色象素（这里用蓝色）代替。
2) 垂直于道路中心线方向上的中心线到区域的距离为半个路宽。在去噪图中，把中心线象素相邻的象素方向看作中心线的方向即道路的方向。则此象素位置有两个方向（有可能在同一直线上）。那么此中心线象素在垂直与道路方向上到区域象素的位置小于半个道路宽度（这里为3）时，则在修补图中把此相同位置距离上的象素用一种图中没有的颜色象素（这里用蓝色）代替。
3) 按中心线象素整个图处理完毕。根据判据在修补图中的颜色转换把图4-6中的红色矩形框内区域放大示意如图4－7所示，
图4-7 中心线反馈修补示意图
4)在修补图中，把是蓝色同时相同位置在归一化图中不是白色（即道路）的象素转变成区域。这里是针对中心线象素进行处理，也就是对中心线根据上面的两个判据判断，对那些符合条件的中心线与相应的区域连接起来，在前面的去噪过程中产生了一些把文字的笔画或标志符号过渡地去除，经过细化也就成了中心线，这里就可以把这些符合条件的“道路”变成区域了。
经过上面的修正处理过程的多次循环，直到不再有满足条件的点产生。上面是一个循环对归一化图进行了两次修补，一次是去噪后把噪声转化为区域的修补；一次是根据中心线两个判据反馈把一些“道路”转换成区域的修补，这里区域按所给的规则在增长，所以也就不难解释去噪是用“有偏”准则，故意造成道路的过识别了。一个循环是对区域的两次修补，这样经过有限此的循环可以达到区域无增长的情况，这时完成了归一化图的修正，同时也就完成了道路的提取。
采用闭环反馈处理后最终修补图如图4-8所示：
图4-8 修补图
对修补图去噪处理得到的去噪图（如图4-9所示），对于图4-9进行细化得到图4-10。
从这几个处理结果图中看出采用闭环反馈的方法很好地实现了道路的提取，这个过程也是全自动化的过程，没有任何的人工干预。用这个程序处理光盘中的其他多个城市地图均得到了很好的效果，
结束语
本文主要研究城市交通GIS系统中的地图识别算法设计和实现技术，重点集中在对栅格地图中道路网络和区域块提取上，并通过编程实现一个实用性的城市地图的生成平台。
针对城市交通地图的特点，分析了国内外一些算法的研究情况，提出了一些适合于解决城市交通地图的处理算法，并不断改善了所给图源中的道路识别率。
主要研究工作如下：
1）基于聚类算法，将图像中的各色块分别聚类；利用图像特征点的性质进行模板匹配，完成图像的预处理算法部分。保证图像的连续性，弱化了复杂道路颜色和区域颜色；
2）通过贴标签算法将图像中的噪声点分类，去除区域中的主要文字噪声，提取出识别较好的区域块，建立了区域识别子系统；
3）对于经过预处理算法的图像，利用道路字符的性质做了有关道路识别子系统的尝试；
4）利用八邻域算法进行有偏无偏估计去除噪声，根据地图中的道路性质进行图像修正，得到较满意的图像，在这部分中实现了部分反馈。
以上工作是笔者在攻读学位期间完成的，只是一个阶段性的总结，就文章中研究的内容而言，仍有许多工作可以继续深入钻研，主要包括：
1) 针对地图中的离散区域块，其中面积比较小的部分设计合理算法，进行合并处理。
2) 虽然图像已经取得良好的效果，但是尚且没能提出较好的总体闭环评价函数。
以上想法是在作论文中考虑到的，但是由于时间限制，只是停留在想法阶段，没有去一一实现。
中国科学技术大学硕士学位论文 参考文献
参考文献
[1] 喻权刚、赵帮元、董戈英，GPS在水土保持生态建设中的应用研究，中国水土保持，2000，11期
[2] 许江，GIS技术及应用趋势，微电脑世界，2002，1期
[3] 仝培杰，“数字地球”的综述，地球信息科学，1998，Z1期
[4] 郝立，《城市地理信息系统及其应用》，电子工业出版社，2002
[5] Tomoharu NAGAO，Takeshi AGUI and Masayuki NAKAJIMA, An automatic road vector extraction method from maps，IEEE，1988
[6] NAKAJIMA，A graphical structure extracting method from an urban map using parallel vector tracer，IECE Trans. Vol.J67D,No. 12,1984
[7] Ding Bin，A system for automatic extraction of road network from maps, Proceedings of IEEE International Joint Symposia,1998
[8] A.Rosenfeld,and A.C.Kak, Digital Picture Processing, Academic Press,1982.
[9] Chang Ahn,Kyu Sik Kim,Sang Burm Rhee,A road extraction method from topographical map images, IEEE，1997
[10] O.Hori and A. Okazaki, High quality vectorization based on a generic object model,structured document image analysis, 1992,pp.325-339
[11] S.Suzuki and T. Yamada, MARIS: Map recongnition input system, Pattern Recongnition,Vol.23 ,No 8,1990,pp.919-933
[12] L. Boatto,V. Consorti,and M.D. Buono, An interpretaion system for land register maps, IEEE computer,1992,pp25-32
[13] D.A. Varley and M. Visvalingam, Road extraction and topographic data validation using area topology, the computer journal, vol 37, No.1,1994,pp 3-15
[14] Lloyd Alan Fletcher,Rangachar Kasturi, A robust algorithm for text string separation from mixed text/ graphics images, IEEE Trans On PAMI,1988, 10(6):910-917
[15] 夏波涌、刘政凯，中文地图文字图象理解的研究，中国图象图形学报,1998,3(12):979～981.
[16] 吕建平、赵树芗、王正光.一种基于预测跟踪技术的地图识别方
中国科学技术大学硕士学位论文 参考文献
法.1991,17(1):77～82.
[17] 刘重庆、金志伟、李介谷，城市地图图形矢量化方法的研究，上海交通大学学报,1994,28(5):63～68.
[18] 地质出版社地图编辑室编辑，中国公路交通图册，北京：地质出版社，2000.4
[19] 刘志清，“基于GIS技术的城市基本图数据库建设的几个问题”，北京测绘，1994年，第四期
[20] 王跃明，“点阵地图中道路的识别和提取”，学士论文，2000
[21] 沈清、汤霖，模式识别，国防科学技术大学出版社，1991
[22] 何斌、马天予、王运坚，Visual C++数字图像处理，人民邮电出版社，2002
[23] 史久根、张旺生、鲍远律，彩色地图图像中道路信息的识别和提取，微机发展，2000，10(1):64-66
[24] 崔屹，数学形态学方法及应用，北京：科学出版社，2000
[25] 林春蔚，徐学云等编著，c环境下地图图像矢量化及图形编辑技术与实例
程序实现涉及文献：
[26] 张旺生，黄晓刚，鲍远律，史久根：矢量电子地图的自动生成，微电子和计算机学报，1999：第16卷，第4期，30~32。
[27] 周长发，精通Visual C++图像编程，北京，电子工业出版社，2000。
[28] 叶家鸣，“彩色城市交通地图道路信息的识别和提取”，硕士论文，2003
[29] 向世明，Visual C++数字图像与图形处理，电子工业出版社，2002.3
参考以下网站：
[1] http://www.gis.com
[2] http://www.gpsworld.com
[3] http://www.chinainfo.gov.cn
[4] http://www.gischina.com
[5] http://www.mapinfo.com
[6] http://www.gps.org.cn/
[7] http://www.21cn-highway.com
附录: 硕士期间发表的学术论文
刘丽萍、鲍远律，“基于标签分类的道路提取算法”，计算机应用，p73－75， 24卷第二期，2004年2月
中国科学技术大学硕士学位论文 致谢
致谢
本文的工作是在鲍远律老师的精心指导下完成的。鲍老师严谨的治学态度，兢兢业业的敬业精神，雷厉风行的工作作风，广博的知识面，精深的，高尚正直的人格，使我受益非浅。在此，谨对鲍老师三年来在学习，工作和生活中给予我的关怀、指导和帮助致以衷心的感谢！刘振安老师在鲍老师出国期间，给予了我极大的关照和指导，在此对他表示衷心的感谢！他们甘当人梯、无私奉献、诲人不倦、亲切随和的人格魅力令我无限敬仰。
GPS实验室活跃的学术气氛，融洽的合作关系，良好的工作环境，使我始终以愉快的心情，浓厚的兴趣在这里学习，工作和生活。
感谢叶家明、王国江、阎庆、张中、季方、海涛，那些一起编写、调试程序和讨论问题的日子，是我难忘的记忆，也让我学习到了很多东西。在实验室工作、学习的工程中，你们给予我的关怀和帮助让我永远难忘，这份友情将陪伴我走过今后的每一天。感谢所有GPS实验室的成员，和我分享学习和生活中的苦与乐。
最后，感谢我的家人多年来对我的关怀、支持和鼓励，以及所有关心和帮助我的朋友们，谨把这篇论文献给他们，让他们能够分享我的喜悦。
刘丽萍
2004年5月8日
