面状要素的多层次骨架线提取

摘要/Abstract

摘要： 多边形的骨架线是对其形态的准确描述，多尺度的骨架线表达在图形分析如多边形的形态恢复和多边形的模式识别等方面具有重要作用。利用双缓冲区变换、障碍距离变换和Voronoi图技术，本文提出一种新的多边形多层次骨架线提取方法，并且，利用复杂湖泊多边形、简单多边形、含岛洞多边形、噪声边缘多边形等不同形状的多边形测试和比较了该方法提取的骨架线的连通性、拓扑一致性和对图形旋转的灵敏性等。实验结果表明，本文方法在上述特性上优于现有算法。

关键词: 障碍距离变换, 缓冲区变换, 多层次骨架, Voronoi图

Abstract: Polygon skeleton is generally recognized as a good shape descriptor. The multiscale representation of polygon skeletons makes it convenient for image analyzing, such as polygon shape recovering, pattern recognition etc. This paper presented a new method to extract multiscale skeletons basing on double buffering transforming, obstacle distance transforming and Voronoi diagram. We tested our method by extracting various skeletons from polygons in different shapes and compared the skeletons qualities from the following indexes, connectivity, topological consistency, and graphics rotating sensitivity. These experimental polygons include complex lake polygon, simple polygon, polygons with holes and noisy polygons. Result shows that according to the above criteria, our method outperforms existing methods to a certain extent.

Key words: Obstacle distance transform, double buffering transform, Multiscale Skeleton, Voronoi Digram

中图分类号:

P208

刘小凤吴艳兰胡海. 面状要素的多层次骨架线提取[J]. , 2013, 42(4): 0-0.

参考文献

[1] Wu Hehai. Map Generalization Theory and Techniques[M]. Beijing :Publishing House of Surveying and mapping，2004.(毋河海.地图综合理论基础与技术方法研究[M].北京: 测绘出版社，2004.)
[2] Du Shihong，Du Taosheng. A New Raster_based Algorithm for Extracting Main Skeleton Line of Polygon[J]. Journal of Wuhan Technical University of Surveying and Mapping，2000，25(5):432-436.(杜世宏,杜道生. 基于栅格数据提取主骨架线的新算法[J].武汉测绘科技大学学报，2000，25(5): 432-436.)
[3] DU Ruiying，LIU Jingnian. A Research on Automatic Placement of Geo-Name in Area Feature [J]. Acta Geodaetica et Cartographica Sinica，1999，28(4):365-368.(杜瑞颖，刘镜年. 面状地物名称注记的自动配置研究[J].测绘学报，1999，28(4): 365-368.)
[4] ATTALI D L，J O. Weighted Skeletons and Fixed Share Decomposition [J]. Computational Geometry，2001，2-3(19): 175-189.
[5] SHAMIR A. A Shahan. Skeleton Based Solid Representation with Topology Preservation[J]. Graphical models，2006， 68(3): 307-321.
[6] XU Limin，XUE An.Terrain Reconstruction from Contours by Skeleton Extraction Using Delaunay Triangulation and Voronoi Diagram[J]. Acta Scientiarum Naturalium Universitatis Pekinensis,2009,45(4):43-48.(许丽敏，薛安.基于Delaunay三角网与Voronoi图联合提取等高线骨架的地形重建算法研究[J].北京大学学报(自然科学版),2009,45(4):43-48.)
[7] OGNIEWICZ R L, O KUBLER. Hierarchic Voronoi Skeletons [J].Pattern recognition, 1995, 28(3): 343-359.
[8] CHANG YongHan, SONG-HwaKwon, CHOI-HyeongIn. Media Axis Transform of a Planar Domain with Infinite Curvature Boundary Points[J].Computer Aided Geometric Design,2012,52(4).
[9] Ai Tinghua，Guo Renzhong.A Constrained Delaunay Partitioning of Areal 0bjects to Support Map Generalization[J]. Journal of Wuhan Technical University of Surveying and Mapping，2000，25（1）：35-41.（艾廷华，郭仁忠. 支持地图综合的面状目标约束Delaunay三角网剖分. 武汉测绘科技大学学报，2000，25(1): 35-41.
[10] FRANK Y S，CHRISTOPHER C P. A Skeletonization Algorithln by Maximal Tracking on Euelidean Distance Transform[J]. Pattern recognition，1995，28(3): 331-341.
[11] GE Y. On the Generation of Skeletons from Discrete Euclidean Distance Maps[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence，1996， 11(18): 1055-1066.
[12] GUO Bangmei，WANG Tao. Research on Algorithm of Polygon Skeleton Line Extracting[J].Bulletin of Surveying and mapping，2010，17(12): 17-19+53.（郭邦梅，王涛.面状要素骨架线提取算法的研究.测绘通报，2010，17(12): 17-19+53.）
[13] LI Xiaojun，JIANG Fanglong，JIANG Zhifeng. Research of an Algorithm for Extracting Central Skeleton Line of TrueType Fonts[J].Journal of mechanical manufacturing，2010，48(1):19-21.(李小军，方江龙，蒋知峰.TrueType字体中心骨架线提取算法研究[J].机械制造，2010，48(1): 19-21.)
[14] CHEN Huirong，ZHENG Yidong，GUAN Haibo. Improvement of Douglas-Peucker Algorithm Based on Skeleton Line[J].Hydrographic Surveying and Charting，2011，31(5): 18-20.(陈惠荣，郑义东，关海波.基于骨架线的Douglas-Peucker算法改进[J].海洋测绘，2011，31(5): 18-20.)
[15] LIU Xiufang，YANG Yongping，LUO Ji. Research on Chart Contour Automatic Cartographic Generalization Based on Arc Info[J].Hydrographic Surveying and Charting，2010，30(5):46-48.(刘秀芳，杨永平，罗吉.基于内侧缓冲区算法的多边形骨架线提取模型[J].海洋测绘，2010，30(5):46-48.)
[16] LIU Jing. Design and Implementation of Skeletonization in GIS Cartography[J].Journal of South—Central University for Nationalities(Nat．Sci．Edition)，2007，26(4):78-80.(刘晶.GIS制图中骨架提取算法的设计与实现[J].中南民族大学学报(自然科学版)，2007，26(4):78-80.)
[17] David T，G.C. Terrain Reconstruction from Contours by Skeleton Construction [J]. GeoInformatica，2000，4(4): 349-373
[18] MASAYUKI H，ALEXANDER G B，TOSIYASU L K. A Skeleton-based Approach for Detection of Perceptually Salient Features on Polygonal Surfaces[J]. Computer Graphics，2002，21(4):689-700.
[19] DOMINIQUE A，JEAN-DANIEL B，HERBERT E. Stability and Computation of Medial Axes：A State-of-the-Art Report[C]. in Mathematics and visualization. Berlin Heidelberg: Springer Verlag ，2008.
[20] ZHU Weisong. A Study of Distance Transform Based Fiber Skeleton Determination Algorithm[D].Dong Huan University，2008.(朱维松.基于距离变换的纤维骨架提取算法研究[D]. 东华大学，2008.)
[21] EFTEKHARIAN A A，HOREA T I. Distance Functions and Skeletal Representations of Rigid and Non-rigid Planar Shapes[J]. Computer-Aided Design，2009，41(12): 865-876.
[22] GAO Wei, ZHANG Jianbo. The Algorithm And Its Application Of Best Route Analysis Based On Raster Data Mode [J].Journal of Heilongjiang Institute of Technology,2006,18(1):22-24.(高伟，张剑波.基于栅格数据模型的最优路径分析算法及实现[J].黑龙江工程学院学报，2004，18(1):22-24.)
[23] WANG Weilu. Research on Parallel Algorithm of Cost Distance for Complex Geometric Features in Obstacle Space[D].NanJing University,2011.(汪维录.障碍空间下复杂几何对象成本距离并行算法研究[D].南京大学，2011.)
[24] HU Peng, YOU Lian,HU Hai. Introduction to Map Algebra[M].Beijing: Publishing House of Surveying and mapping，2008.(胡鹏，游链，胡海.《地图代数概论》[M]. 北京: 测绘出版社，2008)
[25] VASILIS M, ANDRONIKI X,BYRON N,VASILIS V. The Use of Epsilon-Convex Area for Attributing Bends Along a Cartographic Line[C].in 12th International Cartographic Conference, Spain,2005.
[26] WANG Zhonghui，YAN Haowen. Design and Implementation of an Algorithm for Extracting the Main Skeleton Lines of Polygon[J].Geography and Geo-information Science,2011,27(1): 42-44+48.(王中辉，闫浩文.多边形主骨架线提取算法的设计与实现[J]. 地理与地理信息科学，2011，27(1): 42-44+48.)
[27] ANDRES S M，JOCHEN L. Skeleton Pruning by Contour Approximation and the Integer Media Axis Transform [I]. Computers & Graphics,2012(4).
[28] IVANOV D, KUZMIN E, BURTSEV S. An Efficient Integer-based Skeletonization Algorithm [J]. Computers and Graphics, 2000, 1(24): 41-51.
[29] WANG Tao,WU Heihai. Extraction of Hierarchical Skeleton of Areal Object Based on Multivariate Analysis[J].Geomatics and Information Science of Wuhan University,2004,29(6):533-536.( 王涛，毋河海.顾及多因素的面状目标多层次骨架线提取[J].武汉大学学报:信息科学版，2004，29(6):533-536.