Polygon contour similarity and complexity measurement and application in simplification

doi:10.11947/j.AGCS.2019.20180124

Abstract

Abstract: On a comprehensive study concerning polygon contour similarity and complexity, in which the inner chord length, outer chord length, and average arc-to-chord length corresponding to multi-scale entities are extracted to construct chord-feature matrices. A multi-scale polygon contour similarity measurement model is developed. According to the frequency and amplitude of the edges, a complexity measurement model is constructed considering the ratio of the notch, relative increment of the perimeter of the convex shell, and relative increment of the area of the minimum envelope. After verifying the validity and effectiveness of the two models, the similarity variation rules for entities of different complexity at different scales are analyzed, and a general automation simplification flow based on similarity constraints is obtained. Results of the experiments show that the proposed method can set reasonable threshold parameters for the simplification algorithm, and improve the level of automation.

CLC Number:

P208

CHENG Mianmian, SUN Qun, XU Li, CHEN Huanxin. Polygon contour similarity and complexity measurement and application in simplification[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(4): 489-501.

References

[1] 武芳, 巩现勇, 杜佳威. 地图制图综合回顾与前望[J]. 测绘学报, 2017, 46(10):1645-1664. DOI:10.11947/j.AGCS.2017.20170287. WU Fang, GONG Xianyong, DU Jiawei. Overview of the research progress in automated map generalization[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10):1645-1664. DOI:10.11947/j.AGCS.2017.20170287.
[2] 杜佳威, 武芳, 李靖涵, 等. 采用多元弯曲组划分的线要素化简方法[J]. 计算机辅助设计与图形学学报, 2017, 29(12):2189-2196. DU Jiawei, WU Fang, LI Jinghan, et al. Line simplification method based on multi-bends groups division[J]. Journal of Computer-Aided Design & Computer Graphics, 2017, 29(12):2189-2196.
[3] 安晓亚, 孙群, 肖强, 等. 一种形状多级描述方法及在多尺度空间数据几何相似性度量中的应用[J]. 测绘学报, 2011, 40(4):495-501. AN Xiaoya, SUN Qun, XIAO Qiang, et al. A shape multilevel description method and application in measuring geometry similarity of multi-scale spatial data[J]. Acta Geodaetica et Cartographica Sinica, 2011, 40(4):495-501.
[4] 刘鹏程, 罗静, 艾廷华, 等. 基于线要素综合的形状相似性评价模型[J]. 武汉大学学报(信息科学版), 2012, 37(1):114-117. LIU Pengcheng, LUO Jing, AI Tinghua, et al. Evaluation model for similarity based on curve generalization[J]. Geomatics and Information Science of Wuhan University, 2012, 37(1):114-117.
[5] 马京振, 孙群, 肖强, 等. 利用多级弦长拱高复函数进行面实体综合相似性度量研究[J]. 中国图象图形学报, 2017, 22(4):551-562. MA Jingzhen, SUN Qun, XIAO Qiang, et al. Measurement of the comprehensive similarity of area entities using a multilevel arc-height complex function[J]. Journal of Image and Graphics, 2017, 22(4):551-562.
[6] 陈占龙, 覃梦娇, 吴亮, 等. 利用多级弦长弯曲度复函数构建复杂面实体综合形状相似度量模型[J]. 测绘学报, 2016, 45(2):224-232. DOI:10.11947/j.AGCS.2016.20140633. CHEN Zhanlong, QIN Mengjiao, WU Liang, et al. Establishment of the comprehensive shape similarity model for complex polygon entity by using bending mutilevel chord complex function[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(2):224-232. DOI:10.11947/j.AGCS.2016.20140633.
[7] YAN Haowen. Quantitative relations between spatial similarity degree and map scale change of individual linear objects in multi-scale map spaces[J]. Geocarto International, 2015, 30(4):472-482.
[8] YAN Haowen, LI J. Spatial similarity relations in multi-scale map spaces[M]. Geneva:Springer, 2015.
[9] YAN Haowen. Theory of spatial similarity relations and its applications in automated map generalization[D]. Waterloo, Ontario, Canada:University of Waterloo, 2014.
[10] 王斌, 陈良宵, 叶梦婕. 弦特征矩阵:一种有效的用于植物叶片图像分类和检索的形状描述子[J]. 计算机学报, 2017, 40(11):2559-2574. WANG Bin, CHEN Liangxiao, YE Mengjie. Chord-features matrices:an effective shape descriptor for plant leaf classification and retrieval[J]. Chinese Journal of Computers, 2017, 40(11):2559-2574.
[11] ZHANG Dengsheng, LU Guojun. Study and evaluation of different Fourier methods for image retrieval[J]. Image and Vision Computing, 2005, 23(1):33-49.
[12] 郝燕玲, 唐文静, 赵玉新, 等. 基于空间相似性的面实体匹配算法研究[J]. 测绘学报, 2008, 37(4):501-506. DOI:10.3321/j.issn:1001-1595.2008.04.017. HAO Yanling, TANG Wenjing, ZHAO Yuxin, et al. Areal feature matching algorithm based on spatial similarity[J]. Acta Geodaetica et Cartographica Sinica, 2008, 37(4):501-506. DOI:10.3321/j.issn:1001-1595.2008.04.017.
[13] 余英林. 数字图象处理与模式识别[M]. 广州:华南理工大学出版社, 1990. YU Yinglin. Digital image processing and pattern recognition[M]. Guangzhou:South China University of Technology, 1990.
[14] 何爱玲, 王力加, 郭晶鑫, 等. 二维图形复杂度计算与叶片轮廓复杂性分析[J]. 数学计算, 2014, 3(3):89-95. HE Ailing, WANG Lijia, GUO Jingxin, et al. Complexity computation of two-dimensional graphics and complexity analysis of leaf contour[J]. Mathematical Computation, 2014, 3(3):89-95.
[15] TOUSSAINT G. Efficient triangulation of simple polygons[J]. The Visual Computer, 1991, 7(5-6):280-295.
[16] CHAZELLE B, INCERPI J. Triangulation and shape-complexity[J]. ACM Transactions on Graphics, 1984, 3(2):135-152.
[17] PAGE D L, KOSCHAN A F, SUKUMAR S R, et al. Shape analysis algorithm based on information theory[C]//Proceedings of 2003 International Conference on Image Processing. Barcelona, Spain:IEEE, 2003:I-229-32.
[18] FALOUTSOS C, KAMEL I. Beyond uniformity and independence:analysis of R-trees using the concept of fractal dimension[C]//Proceedings of the 13th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. Minneapolis, Minnesota:ACM, 1994:4-13.
[19] PEITGEN H O, JVRGENS H, SAUPE D. Chaos and fractals:new frontiers of science[M]. New York, NY:Springer, 2004:241-255.
[20] BRINKHOFF T, KRIEGEL H P, SCHNEIDER R, et al. Measuring the complexity of polygonal objects[C]//Proceedings of the ACM-GIS. Baltimore, MD:DBLP, 1995:109.
[21] DOUGLAS D H, PEUCKER T K. Algorithms for the reduction of the number of points required to represent a digitized line or its caricature[J]. Cartographica:The International Journal for Geographic Information and Geovisualization, 1973, 10(2):112-122.
[22] WANG Zeshen, MVLLER J C. Line generalization based on analysis of shape characteristics[J]. Cartography and Geographic Information Systems, 1998, 25(1):3-15.
[23] 何海威. 顾及层次结构和空间冲突的道路网选取与化简方法研究[D]. 郑州:信息工程大学, 2015. HE Haiwei. Research on road selection and simplification method considering hierarchical structure and spatial conflicts[D]. Zhengzhou:Information Engineering University, 2015.
[24] 郭立帅, 沈婕, 朱伟. 线要素化简算法的时间复杂度分析[J]. 测绘科学技术学报, 2012, 29(3):226-230. GUO Lishuai, SHEN Jie, ZHU Wei. Time complexity analysis of line simplification algorithms[J]. Journal of Geomatics Science and Technology, 2012, 29(3):226-230.
[25] 李成名, 殷勇, 吴伟, 等. Stroke特征约束的树状河系层次关系构建及简化方法[J]. 测绘学报, 2018, 47(4):537-546. DOI:10.11947/j.AGCS.2018.20170141. LI Chengming, YIN Yong, WU Wei, et al. Method of tree-like river networks hierarchical relation establishing and generalization considering stroke properties[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(4):537-546. DOI:10.11947/j.AGCS.2018.20170141.
[26] 孙群. 多源矢量空间数据融合处理技术研究进展[J]. 测绘学报, 2017, 46(10):1627-1636. DOI:10.11947/j.AGCS.2017.20170387. SUN Qun. Research on the progress of multi-sources geospatial vector data fusion[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10):1627-1636. DOI:10.11947/j.AGCS.2017.20170387.
[27] 艾廷华, 帅赟, 李精忠. 基于形状相似性识别的空间查询[J]. 测绘学报, 2009, 38(4):356-362. DOI:10.3321/j.issn:1001-1595.2009.04.012. AI Tinghua, SHUAI Yun, LI Jingzhong. A spatial query based on shape similarity cognition[J]. Acta Geodaetica et Cartographica Sinica, 2009, 38(4):356-362. DOI:10.3321/j.issn:1001-1595.2009.04.012.