地图自动识别系统中按颜色分层的算法及实现7期冯玉才等:地图自动识别糸统中按顧色分层的算法及实现437类样本的同一类;(6)重复步骤(5)直到不再有样本被分类时止平滑聚类法本质是颜色追踪,典型色和颜色差距界值的指定对总的分类时间有一定影响,其分类效果较好,但所需时间较枚举聚类法长.此方法对线状要素和面状要素均适用2方法的实现枚举聚类法和平滑聚类法是按颜色分层的有效算法,但在具体实现时,必须根据具体情况特殊处理,甚至多种方法并用,才能达到理想的效果(1)面状要素的典型色的确定面状要素例如背景植被、湖泊、海洋等,在地图上是一块块的,每块颜色是一样的,但在扫描输入的数据化地图中,同一面状要素的颜色不会是相同时,而是由几种相似的颜色混杂而成对面状要素的识别,可用平滑聚类方法,其典型色可用如下方法选定:在某一块状要素的中央选一样本点,以该样本点为中心圈一小圆形区域,使得该区域只含有该块状要素而不含其它地理要素,将该区域所有点都指定为典型样本,而这些样本点的颜色均为典型色(2)颜色差距界值的确定在运用枚举聚类法和平滑聚类法时,颜色差距界值的确定对分层的效果和效率有很大影响,对于不同的地理要素和不同的基准色,颜色差距界值应有所不同般情况下,块状要素的颜色差距界值不应太大,而对线状要素,颜色差距界值可定大点在印刷地图时,地图的颜色选取是为了让人眼便于区别,通常在同一幅地图中不会出现两种相似的颜色分别表示两类不同的地理要素,而人眼对不同的颜色敏感层度不尽相同,人眼对红色最敏感,其它依次为橙紫绿青蓝,利用这一特点将有利于确定颜色差距界值.一般,颜色差距界值的确定可依人眼对基准色的敏感层度而定,比如红色的波长范围较宽,对人眼的刺激要大于蓝色,因而红色的颜色差距界值可定大些,蓝色的颜色差距界值定小一些另外人眼对于相同颜色强度的不同属性的颜色敏感层度要比对同一颜色属性而不同强度的颜色的敏感层度要强,例如,在同一光照条件下,人眼可分辩出品红色和粉红色的不同而对某一颜色物品在不同光照条件下却被视为具有相同的颜色在数据化地图中,颜色的强度由象素的数值大小决定,而颜色的差异由象素中三色素数值的比例决定因此在人眼看上去是同一颜色的两个象素,一般是他们各自的三色素数值比例相近因此在平滑聚类中,颜色差距界值可定大一些,但应附加一个条件要求两者的三色素的比例相差不大,(3)平滑聚类法用于线状要素时的跨度平滑聚类法事实上是颜色追踪,其中要将未知类别的样本与其相邻样本求颜色差距,有时线状要素中夹杂了一个其它颜色的点,该点会使颜色追踪的过程到此中断.解决这一问题的办法是将聚类过程中的相邻改为邻近即可地图图象中两点若相邻,或者另有一点与它们两者都相邻,则称这两点是邻近的两个点若是相邻的,则称这两点的跨度为0,两个点若是邻近的,即这两者之间至多相隔一个点,则称这两者跨度为1.一般地,若两点之间至多相隔k个点,则称这两点之间跨度为k在平滑聚类中,将相邻改为跨度为k(k≥1)的,则可解决颜色追踪中断的问题,但跨度不宜定得太大,太大了有可能误判出很多的噪音点,跨度的确定可依线状要素的宽度和图面◎中国科学院软件研究所hp/ww.jos.org.cn438软件学报6卷复杂程度而定,般对宽度为1的线状要素的分层,可定路度为2,对宽度大于1的线状要素的分层,跨度可定为1(4)平滑聚类的扫描顺序在平滑聚类的过程中,要依次将所有未知类别的样本与其相邻的已分类的样本求颜色差距,而未知类别的样本很多,与每个未知类别的样本相邻的已分类的样本也不一定唯因此有必要明确扫描样本点的顺序对于未知类别的样本,还有可能要扫描多次对于未知类别的样本,可按如下的顺序扫描:从上到下逐行扫描,在每行中从左向右逐点扫描,全过程完成后,再从下至上逐行扫描,在每行中从右向左逐点扫描,如此上下往复扫描直至不再有样本被分类时止过程采用上下往复的次序扫描,比单纯从上至下扫描要快,因为从上至下的扫描适合于对向下方延伸的线状要素进行颜色追踪,而对向上方延伸的线状要素就很不适合,扫描一遍只能进展少数几个点,故有必要上下往复对于每个未知类别的样本,可以在其相邻(或邻近)的样本中按从上到下,从左至右的顺序依次搜寻已分类的样本,然后求两者之间的颜色差距(5)记录文件的创立按颜色分层事实上是将样本按其颜色分类,在具体实现时,是创造一个数据文件,将文件中每个数据与地图上每个点(即样本)一一对应起来,每个数据的值就记录了对应的样本所在的类例如欲将一个地图分为7层,则可令未知类别的样本对应的数据为0,令分在第类的样本对应的数据为2,分在第二类的样本对应的数据为4,为了提高平滑聚类法的处理速度,可将每遍扫描未知类别的样本改为搜寻与已分类样本相邻的未知类别的样本若一个已分类样本的相邻样本均已被搜寻过了,则称该已分类样本为老点,若一个已分类样本的相邻样本还没被搜寻过,则称该已分类样本为新点显然,若将平滑聚类法中扫描未知类别的样本改为搜寻与新点相邻的未知类别的样本,则速度会更进一步的提高为了利用新点的属性来提高平滑聚类的速度,有必要在记录文件中区别新点和老点通常,第i类的新点对应的数据值为2i,第类的老点对应的数据值为2+1,当与某个新点相邻的样本均被搜寻过后,该新点就变成了老点,其对应的数据值就加1,而新近被分类的样本就是新点(6)分层的顺序将彩色地图按颜色分层,可在一次聚类过程中同时分出各个颜色阶层,即对每个样本判定其应属于哪一颜色层就分到相应的类中;也可在一次聚类过程中只分出一个颜色层来,即对每个样本判定其是否属于某一特定的颜色层,若是则将其分类到相应类中,若不是则不改动它显然,若在一次聚类过程中能同时分出各个阶层,则可节省很多时间但实践证明,在一次聚类过程中很难同时分出各个阶层,这样分出的单色图不是噪音点多,就是缺损严重采用一次聚类过程只分出一个颜色层的方法,分层效果较好.该方法是先从原彩色地图中分出一幅单色地图,原彩色地图就少了一种颜色,再从少了一种颜色的原地图中分出一幅单色图原彩色地图就又少了一种颜色,如此继续直至原彩色地图中只剩一种颜色时止在一次聚类过程只分出一个颜色层的方法中,分层的顺序(即先分出哪个颜色层)对总◎中国科学院软件研究所hp/ww.jos.org.cn7期冯玉才等:地图自动识别余统中按颜色分层的算法及实现439的分层效果有很大影响这是因为若某样本已被分到了某一类,则该样本就不会作为噪音点出现在另一类中了效果较好的分层顺序是:先分面状要素的颜色层,再分线状要素的颜色层在面状要素中,先分背景色,再分海、湖、植被等颜色层,在线状要素中,先分出黑色、红色等与其它颜色反差大的颜色层再分出黄棕色等与其它颜色反差小的颜色层3结语地图的自动化识别是一项极为复杂的工作,而对彩色地图的按颜色自动分层是地图自动化识别的重要步骤,对它的研究既有理论意义,又有实用价值.本文探讨的有关对彩色地图按颜色自动分层的问题都是在实际研究工作中所遇到的问题,对这些问题的解决方法都已被编程实现了,在IBM486和 COMPAQ386等微型计算机上已调试通过,利用该算法对一幅以189dpi的分辨率扫描输入的1:50000的地图进行按颜色分层,分出5层,仅用了7分20秒时间就完成了对456×616象素点的地图图象的处理,效果理想参考文献1周源华,权淑媛,刘惠娟.地图的计算机识别.上海交通大学学报,1993,(6):26-322吕建平等.一种基于预测跟踪技术的地图识别方法.自动化学报.1991,(17):77-823蒋庆权译地图识别输入技术现代电子工程,1989,(1):69—754 Kasturi R, Alemang J. Information extraction from images of paper-based maps. IEEE Trans. on Software Engineering,May1988,14(5):671-6755 Heutte J, Ogier J M, Lecourtier Y et al. Two aspects of automatic map treatment: road and texture extractionsProc. 1lth IAPR Int. Conf. Pattern Recognition, Hague Netherlands, 1992,3: 109-112.6 Ablameyko S V, Bereishik V I, FrantskevichO V et al. Fast raster-to-vector conversion of large-size 2D linedrawings in a restricted computer. IAPR Workshop on Machine Vision Applications, Tokyo, Dec. 7-9, 199259-62.7 Ablameyko S V, Bereishik V I, Frantskevich O V et al. A system for automatic vectorization and interpretation ofgraphic images. Pattern Recognition and Image Analysis Systems, 1993, 3(1):39-528阮秋琦数字图象处理基础.北京:中国铁道出版社,1988AN ALGORITHM FOR LAYERING MAP IMAGE BY COLOURFeng Yucai Song Enmin Sun Xiaowei Liu Hong(Department of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan 430074)Abstract Layering map image by colour, which is one of important steps for automati-cal recognizing map image by computer, is researched in this paper. The algorithm for layering is proposed, and some problems about layering efficiency and effect are discussedSome methods to solve these problems are given. The algorithm has been implementedand it is idealKey words Map, colour, layering, collection, recognition.◎中国科学院软件研究所hp/ww.jos.org.cn