面轮廓线相似性和复杂性度量及在化简中的应用

doi:10.11947/j.AGCS.2019.20180124

测绘学报 ›› 2019, Vol. 48 ›› Issue (4): 489-501.doi: 10.11947/j.AGCS.2019.20180124

面轮廓线相似性和复杂性度量及在化简中的应用

程绵绵¹, 孙群¹, 徐立¹, 陈换新²

1. 信息工程大学地理空间信息学院, 河南郑州 450001;
2. 96911部队, 北京 100011

收稿日期:2018-03-20 修回日期:2018-08-02 出版日期:2019-04-20 发布日期:2019-05-15
通讯作者: 孙群 E-mail:sunqun@371.net
作者简介:程绵绵(1990-),男,博士生,研究方向为多源数据融合及制图综合。E-mail:chmmian@163.com
基金资助:
国家自然科学基金（41571399；41071297）

Polygon contour similarity and complexity measurement and application in simplification

CHENG Mianmian¹, SUN Qun¹, XU Li¹, CHEN Huanxin²

1. Institute of Geospatial Information, Information Engineering University, Zhengzhou 450001, China;
2. Troops 96911, Beijing 100011, China

Received:2018-03-20 Revised:2018-08-02 Online:2019-04-20 Published:2019-05-15
Supported by:
The National Natural Science Foundation of China(Nos. 41571399; 41071297)

摘要/Abstract

摘要： 本文对同名实体相似性和复杂性进行综合研究，通过抽取多个尺度下的内弦长、外弦长及弧到弦的平均投影长度构造弦特征矩阵，建立了多尺度面轮廓线相似性度量模型。依据边的振动频率及幅度，从凹口比例、凸壳周长相对增量及最小外包圆面积相对增量3个方面建立复杂性度量模型。在验证两类模型正确性和有效性的基础上，分析了不同复杂度目标在不同尺度下相似性变化规律，据此给出基于相似性约束的自动化简的一般流程。试验表明，本文方法可为化简算法设置合理阈值参数，增加化简算法的自动化程度。

关键词: 相似性度量, 弦特征, 形状描述, 复杂性, 制图综合, 化简

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.

中图分类号:

P208

程绵绵, 孙群, 徐立, 陈换新. 面轮廓线相似性和复杂性度量及在化简中的应用[J]. 测绘学报, 2019, 48(4): 489-501.

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.

参考文献

[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.

面轮廓线相似性和复杂性度量及在化简中的应用

Polygon contour similarity and complexity measurement and application in simplification

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价

[1]	杜佳威, 武芳, 朱丽, 刘呈熠, 王安东. 图形、图像融合利用的集成学习智能化简方法及其在岛屿岸线化简中的应用[J]. 测绘学报, 2022, 51(3): 373-387.
[2]	晏雄锋, 袁拓, 杨敏, 孔博, 刘鹏程. 建筑物形状特征分析表达与自适应化简方法[J]. 测绘学报, 2022, 51(2): 269-278.
[3]	行瑞星, 武芳, 巩现勇, 杜佳威, 刘呈熠. 建筑群组合直线模式识别的模板匹配方法[J]. 测绘学报, 2021, 50(6): 800-811.
[4]	龚希, 谢忠, 周林, 何占军. 空间方向相似性二元组模型度量方法[J]. 测绘学报, 2021, 50(12): 1705-1716.
[5]	尹烁, 闫小明, 晏雄锋. 基于特征边重构的建筑物化简方法[J]. 测绘学报, 2020, 49(6): 703-710.
[6]	刘呈熠, 武芳, 巩现勇, 行瑞星, 罗登瀚. 规则池塘群的复杂直线模式识别[J]. 测绘学报, 2020, 49(2): 256-266.
[7]	郭文月, 刘海砚, 孙群, 余岸竹, 丁梓越. 顾及几何特征相似性的多源等高线匹配方法[J]. 测绘学报, 2019, 48(5): 643-653.
[8]	张立华, 唐露露, 贾帅东, 戴泽源. 多条海岸线协同化简的层次化三角网分区法[J]. 测绘学报, 2019, 48(4): 520-531.
[9]	杜佳威, 武芳, 李靖涵, 行瑞星, 巩现勇. 一种河口湾海岸线渐进化简方法[J]. 测绘学报, 2018, 47(4): 547-556.
[10]	何海威, 钱海忠, 谢丽敏, 段佩祥. 立交桥识别的CNN卷积神经网络法[J]. 测绘学报, 2018, 47(3): 385-395.
[11]	李成名, 郭沛沛, 殷勇, 武鹏达, 顾腾. 一种顾及空间关系约束的线化简算法[J]. 测绘学报, 2017, 46(4): 498-506.
[12]	杨敏, 陈媛媛, 金澄, 程前. 保持移动速度特征的轨迹线化简方法[J]. 测绘学报, 2017, 46(12): 2016-2023.
[13]	武芳, 巩现勇, 杜佳威. 地图制图综合回顾与前望[J]. 测绘学报, 2017, 46(10): 1645-1664.
[14]	郭沛沛, 李成名, 殷勇. 建筑物合并的Delaunay三角网分类过滤法[J]. 测绘学报, 2016, 45(8): 1001-1007.
[15]	晏雄锋, 艾廷华, 杨敏. 居民地要素化简的形状识别与模板匹配方法[J]. 测绘学报, 2016, 45(7): 874-882.