摘要
建立地理信息系统(GIS)的一个重要环节是地理数据的获取,工作量占整个系统开发的80%以上,也是影响GIS发展的瓶颈。地图要素智能识别是地理数据获取的核心问题,是图像处理、模式识别和人工智能等多种学科的综合应用,同时也是计算机视觉领域的重要课题。其直接面向企业需求,具有很高的理论意义和应用价值,多年来的理论研究及实践为此课题的深入研究奠定了良好的基础,但也存在着许多亟待解决的问题,识别理论和方法有待突破。
地形图是点、线、面符号的有机集合,是矢量线划图;而扫描地形图图像是点阵像素的自然集合。为了将点阵像素聚合为地图要素符号,本文从知识出发,进行分层处理和自组织的推理,力求加强表达单元整体性、提高表达的层次性、关注各种关联信息以及根据启发信息选择和组织识别数据。本文扩充了图段的约束条件,使其满足颜色、宽度和拓扑一致性要求,使图段成为具有单意义的图像表达单元。根据象素之间的关联,先对点阵图像进行游程编码,构建带有属性信息的扫描串,然后基于扫描串宽度、颜色和拓扑一致性形成图段,得到图像的图段表达,同时提取图段之间连接关系,构建图段连通体。根据图段连通体的属性提取点、线、面连通体,并对线进行矢量化,得到线符号及其之间的连接关系,构建线符号之间的邻接关系。根据线符号之间的关联性,搜索属于同一地图要素的所有线符号,提取之间的关系,重建地图要素。
根据人脑识别地形图时对目标信息的组织方式,本文提出了地形图目标的三级模型——地图要素模型、符号模型和影像模型,符号模型将现实模型和影像模型联系起来,该模型基于矢量栅格一体化数据表达形式,是面向地物的,具有矢量数据的特点;同时,通过地物的标识号可以找到该地物途径的所有像元,从而又具有栅格的全部特性。基于符号模型进行地物的识别和提取,可以充分利用地物所有像元的局部特征,同时又可利用地物的拓扑关系等整体特征。识别过程中提取的信息分成图段、符号和地图要素三个层次,同一层次数据之间相互关联,不同层次数据之间也相互关联,这样既注重横向的关联又重视纵向的关联。在识别中,先获得像素局部特征再生成图段连通体的整体结构,然后又用整体结构去指导和修正局部特征;高层信息从低层数据获得,反过来又去指导低层数据,采用自下而上与自上而下推理相结合的方式完成整个识别。
为了充分利用地形图的颜色信息,在分析前人分色处理方法的基础上,面向像元层次提出了增加颜色分类数的思想,从而有效地解决了过渡色分色模糊的难题;面向扫描串层次将颜色组合情况归纳为16种,巧妙地用各颜色代码之和来表示,从而使得扫描串带有了颜色信息,为图段颜色信息的提取提供了基础。本文采用游程编码技术实现了像元矩阵→扫描串→图段的转换。图段是满足颜色、宽度和拓扑一致性的邻接扫描串,其能够直接表达线段和交点。利用图段的颜色信息和邻接关系构建单版图段连通体,从而实现了地形图图像的自动分色,由于同时考虑了颜色属性与空间关系,其在处理效率和抑制噪声等方面更为优越。
在单版连通体图基础上,对图段连通体进行分析。从地图符号的形状、尺寸和拓扑关系入手,归纳总结出特征尺寸、高宽比、黑白比、节点密度等适于表达的特征,并基于特征的区别有效地将线符号从点、面符号中分离出来。对提取得到的线符号,依据节点图段采用分段矢量化的处理方法,然后根据节点图段的邻接关系进行同源直线检测,从而得到属于同一地图要素的所有矢量线段,形成完整的矢量信息。同时针对不同的地图要素自适应地调整检测条件,更好的提取虚线型道路、河流和等高线的矢量数据。
基于上述识别方法和算法,设计开发了一个地形图智能识别原型系统。软件以VC++为平台,采用面向对象的设计方法,并利用通用数据库管理数据。
Geographic Information Acquisition (GIA) which accounts for 80% of the whole work is important for Geographical Information System (GIS) development, and still a bottleneck of the development for the GIS. Automatic interpretation and acquisition of topographic map is the core of GIA because it involves many subjects such as image processing, pattern recognition and artificial intelligence, etc. At the same time, it is one of key issues in the field of computer vision.The research on recognition is important in both theory and practical application. Previous theories and applications have provided a solid foundation for further research, but there are still some urgent and thorny problems. New approaches of recognition have to be proposed.
The topographic map, which can be regarded as vector line graph, is a set of point, line and surface symbols, while the scanned map is composed of pixels. To extract symbols from pixels, recognition process should be self-organizationally implemented by different levels. The approach developed by this dissertation aims to capture more global features. The constraints of the segment are extended to meet the color, width, and topological consistency, so that the segment is the expression unit of a single meaning for image. Firstly, according to the relationship between pixels, images are run-length encoded and the scan strings with the attribute are built. Secondly, based on the color, width and topological consistency of scan strings, the segments expressing image are obtained. At the same time, connecting relationships among the segments are extracted for building the segment connected components. Thirdly, according to the properties of the components, the line symbols are extracted from point and surface symbols. The adjacency relationships between the vector line symbols are constructed to search for all line symbols belonging to the same map element, and thus we can rebuild the map elements.
According to the organization of topographic map information in the human brain, this dissertation proposes a three-tier model of topographic map target:the map element model, symbolic model and image model. The symbolic model relates the realistic model and the image model. At the same time, it also has the raster data characteristic therefore we might find ways to all pixels of surface features by its identification number. Recognizing and extracting surface features through the symbolic model, we can use not only the partial characteristic of all pixels, but also the overall characteristics such as topological relationship. Data in the same level and in the different levels are associated with each other, so the associations are paid great attention horizontally and vertically. High-level information originates from low-level data and in turn instructs low-level data, therefore, the recognition is completed through bottom-up and top-down reasoning combination.
To take full advantage of the color information of topographic map, the dissertation puts forward the idea to increase the number of color categories in pixel level, which effectively solved the difficult problem of fuzzy transition-color separation. In scan string level color combinations are classified into 16 sorts and are skillfully indicated with the sum of the various color code, which enables scan string to have the color information and provides the foundation for obtaining segments'color. In this paper, run-length coding technology is used to realize the conversion from pixel matrix to scan string and then to segment which makes up of the adjacent scan strings meeting the color, width, and topological consistency. The segment can directly express line and intersection. Single version of a connected graph is built using the color information and the adjacent relationship of segment, thus achieving automatic color separation of topographic map image. The method has a high processing efficiency and reduces much noise since taking into the color attribute and spatial relationship.
By analyzing the shape, size and topology of the connected component, the dissertation has summarized characters for expression, such as the size, aspect ratio, black and white ratio and node density, and has effectively separated line symbol from point symbol and surface symbol based on these characteristic. The sub-vector method is adopted to deal with line symbols, at the same time, homologous lines are detected according to the adjacency relationship of node segments. Through the process, all vector lines to the same map element are obtained and the complete vector information is established. In order to better extract the vector data of dashed roads, rivers and contour lines, test conditions can be adaptively adjusted according to different map elements.
The above mentioned recognition methods have been realized in the already-developed prototype system of recognizing the topographic map. In which, the software shall be designed according to the objects and data be managed by common database.
引文
[1]尹贡白,王家耀等.地图概论[M].北京:测绘出版社,1990.
[2]郭玲.彩色地图线状要素的识别与获取[D].周献中,黄志同教授指导,南京理工大学,2003.
[3]Samet H. and Soffer A. MARCO:Map retrieval by Content. IEEE Pattern Analysis and Machine Intelligence,1996,18(8):783-798.
[4]Ogier J.M, Mullot R. Semantic Coherency:the Basis of an Image Interpretation Device-application to the Cadastral Map Interpretation. IEEE Transactions on Systems, Man and Cybernetics,2000,30(2B):322-338.
[5]Pavlids T. A review of algorithms for shape analysis[J]. Computer Graphics and Image Processing,1978,7:243-258.
[6]Hilditch C J. Comparison of thinning algorithms on a parallel processor [J]. Image and Vision computing,1983,1(3):115-132.
[7]Naccache N J, SPTA R. Shinghal A Proposed Algorithm for Thinning Binary Patterns. IEEE Transactions on Systems, Man, and Cybernetics,1984,14(3):409-418.
[8]Chin R T,WanHK, StoverD L, IversonR D. A one-pass thinning algorithm and its parallel implementation.ComputerVision Graphics Image Processing,1987,40:30-40.
[9]Zhang T Y, Suen C Y.A fast parallel algorithm for thinning digital patterns[J]. Communications of ACM,1984,27(3):236-239.
[10]Lam L, Suen C Y. An Evaluation of Parallel Thinning Algorithms for Character Recognition. IEEE Transactions on Pattern Analysis and Machine Intelligence,1995, 17(9):914-919.
[11]李侠民,徐美瑞.两个快速的完全的并行细化算法[J].计算机研究与发展,1996,33(7):521-527.
[12]王辉连,武芳.利用数学形态学提取骨架线的改进算法[J].测绘科学,2006,31(1):29-33.
[13]C.-C.Han and K.-C.Fan. Skeleton Generation of Engineering Drawings via Contour Matching. Pattern Recognition,1994,27(2):261-275.
[14]颜学阶,常明,朱林.基于线性轮廓匹配的工程图识别算法研究.华中理工大学学报,1997年3月,25(3):34-37.
[15]谭建荣,彭群生.基于图形约束的工程图扫描图像直线整体识别方法[J].计算机学报,1994,17(8):561-569.
[16]李伟青,谭建荣,彭群生.基于图段结构的整休识别方法的研究[J].计算机学报,1998,21(8):753-758.
[17]王金鹤.基于条形域结构的扫描图样识别理论与方法研究[D].大连,大连理工大学,1999,6.
[18]李宾.基于认知模型的工程图层次矢量化算法研究[D].浙江,浙江大学,1998,6.
[19]张习文.基于单义域邻接图的扫描工程图样自组织智能识别理论与技术研究[D].大连,大连理工大学,2000,6.
[20]李岩影,过静珺.大比例尺地形图扫描图像的整体矢量化方法研究[J].测绘通报,2000,8:20-22.
[21]刘彤宇,顾树生等.基于模糊分类的地图整体识别方法[J].计算机科学,2002,29(3):103-105.
[22]Yang C K, Tsai W H. Reduction of color space dimensionality by moment-serving thresholding and its application for edge detection in color images [J]. Pattern Recognition Letters.1996,17(5):481 -490.
[23]Bernd Lauterbach, Walter Anheier. Segmentation of scanned maps in uniform colors Paces。MVA 94 IAPR Workshop on Machine Vision Applications, Kawasaki,1994, 12:322-325.
[24]Serguei Levachkine et al. Semantic Analysis and Recognition of Raster-Scanned Color Cartographic Images.2002.
[25]Khotanzad A, Bouarfa A. Image Segmentation By a Parallel, Non-parametric Histogram Based Clustering Algorithm[J]. Pattern Recognition,1990,23(9):961-973
[26]冯玉才,宋恩民.彩色地图图像的聚色算法研究[J].软件学报,1996,7(8):466-470.)
[27]Kurugollu F, Sankur B, et al. Color image segmentation using histogram multi-thresholding and fusion [J]. Image and Vision Computing,2001,19(13):915-928.
[28]刘健庄,谢维信.高效的彩色图像塔形模糊聚类分割方法[J].西安电子科技大学学报,1993,20(1):40-46.
[29]Lim YW, Lee SU. On the color image segmentation algorithm based on the thresholding and the fuzzy c-means techniques [J]. Pattern Recognition,1990,23(9):935-952.
[30]林开颜,徐立鸿,吴军辉.快速模糊C均值聚类彩色图像分割方法[J].中国图象图形学报,2004,9(2):159-163.
[31]Chen T Q, Lu Y. Color image segmentation-An innovative approach[J]. Pattern Recognition,2002,35(2):395-405.
[32]Abdelhafid Bessaid et al. Image analysis and Pattern recognition as tools in Map interpretation[J]. Technieal Acoustics,2003,15:254-258.
[33]陈洪亮,沈琳琳.基于Kohonen神经网络的地图自动输入技术[J].小型微型计算机系统,2001,22(12):69-72.
[34]林宗坚,刘少创.自组织特征映射神经网络及其在彩色地图自动分层中的应用[J].武汉测绘科技大学学报,1994,19(2):108-112.
[35]吕建平,王玉辉.彩色地图自动识别方法的研究[J].西安电子科技大学学报,1993,20(3):109-114.
[36]黄培之.实现彩色地图扫描数据自动分层的途径与方法[J].测绘学报,1998,27(4):318-325.
[37]Fleteher L A. A Robust Algorithm for Text String Separation from mixed text/graphics Images [J]. IEEE Trans, Pattern and Machine Intelligence,1988,10(6):910-918.
[38]Chen W. Combined Symbol Matching Facsimile Data Compression System. Proc. IEEE,1980,68:786-796.
[39]Wall F M. Block Segmentation and Text Extraction in Mixed Text/Image Document. CVGIP,1982,20(4):375-390.
[40]Blay H. Segmentation and Preprocessing of electrical Schematics Using Picture Graphs. CVGIP,1984,28(3):271-288.
[41]黄文骞.地图模式识别原理与方法[M].北京:测绘出版社,2000.
[42]Yamada H. Directional Mathematical Morphological and Reformalized Hough Transformation for the Analysis of Topographic Maps [J].IEEE Transactions on PAMI, 1993,15(4):380-387.
[43]Illert A. Automatic Recognition of Texts and symbols in Scanned Maps. Proceedings EUROCARTO SEVEN. En scheme. The Netherlands, ITC Publish,1988(8).
[44]Illert A. Automatic Digitization of Large Scale Maps. Technical Papers ACSM ASPRS Annual Convention,1991(6).
[45]林宗坚,卢健.基于计算机视觉的专题图读取系统[J].武汉测绘科技大学学报,1992,17(2):8-17.
[46]邹荣金.工程图中线状图形的自动分类与识别算法[J].计算机辅助设计与图形学报,1999,36(1):62-67.
[47]骆剑承,周成虎.彩色扫描地图等高线的自动识别[J].地球信息科学,1999,1(2):57-62.
[48]郝向阳.地图信息识别与提取技术[M].北京:测绘出版社,2001.
[49]Yaguchi A, et al. Automatic recognition of road information on medium scale topographical maps.16th ISPRS Congress, Comm. Ⅲ, Kyoto:1988:350-359.
[50]Suzuki S, Kosugi M, T Hoshino. Automatic line drawing recognition of large-scale maps. Optical Engineering,1987,26(7,):642-649.
[51]陈晓勇,李德仁.CCD扫描等高线的自动栅格—矢量转换方法[J].测绘学报,1991,20(1):22-26.
[52]Ebi N, et al. Automatic data acquisition from topographic maps using a knowledge-based image analysis system,17th ISPRS Congress, Comm. Ⅳ, B4, Washingtpn, 1990:655-663.
[53]刘学.基于知识的地图自动识别理论[博士论文].张祖勋,张剑清教授指导,武汉测绘科技大学,1995.
[54]王润生.图像理解[M].北京:国防工业出版社,1994.
[55]田德森.现代地图学理论.北京:测绘出版社,1991.
[56]傅仲良.地图扫描影像自动识别技术.北京:测绘出版社,2003.
[57]周辉.扫描工程图纸识别输入处理与联机手绘图形输入技术的研究(博士学位论文).欧宗瑛教授指导,大连理工大学,1998.
[58]李岩影,过静珺.大比例尺地形图扫描图像的整体矢量化方法研究[J].测绘通报,2000,(8):20-22.
[59]李伟青,谭建荣等.基于图段结构的整体识别方法的研究[J].计算机学报,1998,21(8):753-758.
[60]江早,刘晋军等.一种可交互删改的二值图像快速连通体标识方法[J].东北大学学报(自然科学版),1998,19(3):251-254.
[61]张树生.一种基于线的标号传播二值图像连通体快速检测方法[J].计算机研究与发展,1994,31(10):51-54.
[62]李聪,梁昌勇.十字链表存储技术在协同过滤中的应用[J].情报杂志,2008,3:84-86.
[63]Fletcher L A. A Robust Algorithm for Text String Separation from Mined Text/Graphics. IEEE PAMI,1988,10(6):910-918.
[64]Chen W. Combined Symbol Matching Facsimile Data Compression System. Proc. IEEE,1980,68:786-796.
[65]Wall F M. Block Segmentation and Text Extraction in MixedText/Image Document. CVGIP.1982,20(4):375-390.
[66]Blay H. Segmentation and Preprocessing of Electrical Schematics Using Picture Graphs. CVGIP,1984,28(3):271-288.
[67]Illert A. Extract of Texts and Symbols from Non-structured Vector Data. Proc. Of the 13th Int. Cart. Conf. Morelia (Vol. N). Mexico:Mich,1987,367-374.
[68]林宗坚,傅仲良.地形图线状目标与点状符号的自动分离[J].武汉测绘科技大学学 报.1994,19(4):328-331.
[69]叶建栲,任留成等.基于知识的点状符号自动识别[J].解放军测绘学院学报.1999,16(3):203-206.
[70]杜清运,白亭颖.基于地图符号语言学特征的线状要素自动识别[J].武汉测绘科技大学学报.1999,24:1-7.
[71]Sven Loncarie. A Survey of Shape Analysis Techniques. Patten recognition.1998, (8):983-1001.
[72]郑华利.彩色地形图的自动识别与矢量化研究[D].周献中教授指导,南京理工大学.2004,6.
[73]Pal N R, Pal S K. Entropy thresholding. Signal Processing,1989,16:97-108.
[74]Pun T.A new method for grey-level Picture thresholding using the entropy of histogram. Signal Processing,1980,2:223-237.
[75]候志强,韩崇昭等.一种基于视觉模型的边缘检测阈值选择策略[J].光电工程.2004,31(2):59-62.
[76]辛动军.彩色地形图要素的自动识别与获取研究[D].周献中教授指导,南京理工大学.2007,6.
[77]薛峰,王润生.组合利用统计和结构信息的道路提取算法[J].光学学报.2001,21(4):504-508.
[78]刘静等.地图中道路自动识别的方法[J].上海交通大学学报.1996,30(12):161-166.
[79]Chang Ahn, Kyu Sik Kim, Sang Burm Rhee. A Road Extraction Method from Topographical Map Images [J].IEEE pacific RIM conference on communications, computers and signal Proceedings,1997,2:839-842.
[80]He Yinghua, Wang Hong, Zhang Bo. Color-based road detection in urban traffic scenes. Intelligent Transportation Systems, IEEE Transactions,2004,5(4):309-318.
[81]J. Amini, et.al. Automatic road-side extraction from large scale image maps. International Journal of Applied Earth Observation and Geoinformation,2002,4:95-107.
[82]张荣,王勇,杨榕.TM图像中道路目标识别方法的研究[J].遥感学报,2005,9(2):220-224.
[83]李燕,邵作叶,余旭初.基于感知编组的道路网自动提取研究[J].遥感信息,2005,1:11-14.
[84]林塞P.H,诺曼D.A.人的信息加工心理学概论.科学出版社,1987.
[85]Heilo Hecht, Hethert bader. Perceiving topological structure of 2-D patterns. Acta psychological,1998(9):255-292.
[86]MaPk w Pettet, Suzannep mekee. Constraints on long range interaetions mediating contour detection vision researeh.1998,38(6):865-879.
[87]王润生.图像理解[M].长沙:国防科技大学出版社,1995.
[88]章毓晋.图像分割[M].北京:科技出版社,2001.
[89]李燕,余旭初.基于启发式图搜索的遥感影像道路半自动提取[J].测绘学院学报,2002,19(4):268-271.
[90]D. B. Dhar, B. Chanda. Extraction and recognition of geographical features from Paper maps. International Journal of Document Analysis and Recognition,2005,10(9):123-131.
[91]陆玮琳,潘云鹤.基于非交点跟踪的地图矢量化算法[J].计算机学报,1994,17,增刊:122-124.
[92]吕建平.线形交叉模式识别算法的探讨[J].微电子学与计算机,2005,29(9):40-42.
[93]刘慧娟,周源华.地图中河流的自动识别方法[J].自动化学报,1993,19(4):509-511.
[94]吕建平,秦岩.地图中河流自动识别方法的探讨[J].西安电子科技大学学报,1996,23(1):54-58.
[95]Kweon I, Kanade T. Extracting topographic terrain features from elevation maps [J].CVGIP:Image Understanding,1994,59(2):171-182.
[96]Cronin T. Automated reasoning with contour maps [J].Computers & Geosciences, 1995,21 (5):609-618.
[97]Cronin T. Classifying hills and valleys in digitized terrain [J].Photogrammetric Engineering & Remote Sensing,2000,66(9):1129-1137.
[98]张登荣,刘绍华,毛天露,等.等值线自动建立拓扑关系算法与快速填充应用[J].中国图象图形学报,2001,6A(3):264-269.
[99]Chen J, Qiao C, Zhao R. A voronoi interior adjacency-based approach for generating a contour tree[J].Computers and Geosciences,2004,30:355- 367.
[100]乔朝飞,赵仁亮等.基于Voronoi内邻近的等高线树生成法[J].武汉大学学报:信息科学版,2005,30(9):801-804.
[101]孟亮,方金云.基于扫描线的等高线树生成法[J].计算机工程与应用,2007,43(27):26-28.