A Head-Tail information break method oriented to multi-scale representation of polyline

doi:10.11947/j.AGCS.2020.20200004

Abstract

Abstract: It is proposed that a multi-scale representation model of geographic polyline based on Head-Tail break of amount of information. Firstly, a geographic polyline is transformed into a Fourier shape descriptors, and the amount of information in frequency domain is defined using Shannon’s information entropy theory. Secondly, Head-Tail breaks is introduced to determine the demarcation points of information content of the polyline, and a function is designed to estimate the Fourier truncating frequency corresponding to each demarcation point. Finally, the traditional radical model based on the frequency information amount of polyline is introduced to measure the key scales and to achieve hierarchical multi-scale representation of polylines. The experiments of contour and coastline demonstrate that the model proposed can effectively simplify geographic polylines according to the set scale, and the simplification results of different target scales exist good degree of differentiation and hierarchy. At the same time, under the same overlap ratio between the simplified result and the original geographic polyline, the model proposed is better than the traditional simplification algorithm.

Key words: multi-scale representation, Fourier transform, frequency domain, amount of information, Head-Tail break

CLC Number:

P208

LIU Pengcheng, XIAO Tianyuan, XIAO Jia, AI Tinghua. A Head-Tail information break method oriented to multi-scale representation of polyline[J]. Acta Geodaetica et Cartographica Sinica, 2020, 49(7): 921-933.

References

[1] 毋河海. 地图信息自动综合基本问题研究[J]. 武汉测绘科技大学学报, 200, 25(5):377-386. WU Hehai. Research on fundamental theory and technical approaches of automated map generalization[J]. Journal of Wuhan Technical University of Surveying and Mapping, 2000, 25(5):377-386.
[2] 王家耀. 空间数据自动综合研究进展及趋势分析[J]. 测绘科学技术学报, 2008, 25(1):1-7, 12. WANG Jiayao. The progress and trend of automatic generalization of spatial data[J]. Journal of Geomatics Science and Technology, 2008, 25(1):1-7, 12.
[3] 贾奋励. 电子地图多尺度表达的理论与方法的研究[D]. 郑州:信息工程大学, 2002. JIA Fenli. Research on the theories & methods of electronic map's multi-scale representation[D]. Zhengzhou:Information Engineering University, 2002.
[4] 贾奋励. 电子地图多尺度表达的研究与实践[D]. 郑州:信息工程大学, 2010. JIA Fenli. Research and practice of electric map multi-scale representation[D]. Zhengzhou:Information Engineering University, 2010.
[5] 艾廷华, 成建国. 对空间数据多尺度表达有关问题的思考[J]. 武汉大学学报(信息科学版), 2005, 30(5):377-382. AI Tinghua, CHENG Jianguo. Key issues of multi-scale representation of spatial data[J]. Geomatics and Information Science of Wuhan University, 2005, 30(5):377-382.
[6] 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.
[7] LI Zhilin, OPENSHAW S. Algorithms for automated line generalization based on a natural principle of objective generalization[J]. International Journal of Geographical Information Systems, 1992, 6(5):373-389.
[8] WANG Zeshen, MVLLER J C. Line generalization based on analysis of shape characteristics[J]. Cartography and Geographic Information Systems, 1998, 25(1):3-15.
[9] 刘鹏程, 罗静, 艾廷华, 等. 基于线要素综合的形状相似性评价模型[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.
[10] 刘鹏程, 艾廷华, 毕旭. 傅立叶级数支持下的等高线多尺度表达模型[J]. 武汉大学学报(信息科学版), 2013, 38(2):221-224. LIU Pengcheng, AI Tinghua, BI Xu. Multi-scale representation model for contour based on fourier series[J]. Geomatics and Information Science of Wuhan University, 2013, 38(2):221-224.
[11] 刘鹏程, 龚冲亚, 陶建斌, 等. 基于图形渐变技术的等高线连续尺度表达模型[J]. 地理科学, 2014, 34(3):332-337. LIU Pengcheng, GONG Chongya, TAO Jianbin, et al. The continual scale representation model for contour based on morphing technique[J]. Scientia Geographica Sinica, 2014, 34(3):332-337.
[12] 刘鹏程, 艾廷华, 杨敏. 基于傅里叶级数的等高线网络渐进式传输模型[J]. 测绘学报, 2012, 41(2):284-290. LIU Pengcheng, AI Tinghua, YANG Min. The internet progressive transmission model for contour based on Fourier series[J]. Acta Geodaetica et Cartographica Sinica, 2012, 41(2):284-290.
[13] LIU Pengcheng, LI Xingong, LIU Weibo, et al. Fourier-based multi-scale representation and progressive transmission of cartographic curves on the internet[J]. Cartography and Geographic Information Science, 2016, 43(5):454-468.
[14] 肖天元, 刘鹏程, 艾廷华, 等. 一种基于信息度量的傅里叶展开曲线分形描述方法[J]. 武汉大学学报(信息科学版), 2020, 45(1):119-125. XIAO Tianyuan, LIU Pengcheng, AI Tinghua, et al. A fractal description method of Fourier expansion curve based on information metrics[J]. Geomatics and Information Science of Wuhan University, 2020, 45(1):119-125.
[15] 李精忠, 方文江. 顾及邻域结构的线状要素Morphing方法[J]. 武汉大学学报(信息科学版), 2018, 43(8):1138-1143. LI Jingzhong, FANG Wenjiang. Morphing polylines by preserving local neighborhood structures[J]. Geomatics and Information Science of Wuhan University, 2018, 43(8):1138-1143.
[16] 李精忠, 张津铭. 一种基于傅里叶变换的光滑边界面状要素Morphing方法[J]. 武汉大学学报(信息科学版), 2017, 42(8):1104-1109. LI Jingzhong, ZHANG Jinming. A morphing method for smooth area features based on Fourier transform[J]. Geomatics and Information Science of Wuhan University, 2017, 42(8):1104-1109.
[17] 方文江, 李精忠. 一种基于形状上下文特征匹配的线状要素Morphing方法[J]. 武汉大学学报(信息科学版), 2017, 42(7):963-967. FANG Wenjiang, LI Jingzhong. A Morphing of linear feature based on shape context matching[J]. Geomatics and Information Science of Wuhan University, 2017, 42(7):963-967.
[18] 谢天, 李精忠, 陈凯. 顾及线状要素综合要求的Morphing算法[J]. 武汉大学学报(信息科学版), 2018, 43(5):792-797. XIE Tian, LI Jingzhong, CHEN Kai. Morphing algorithm for linear feature considering generalization requirements[J]. Geomatics and Information Science of Wuhan University, 2018, 43(5):792-797.
[19] 唐雅玲, 马晨燕, 宋佳, 等. 矢量Web网络地图应用研究[J]. 测绘与空间地理信息, 2018, 41(2):77-80, 83. TANG Yaling, MA Chenyan, SONG Jia, et al. Research on the application of vector web mapping[J]. Geomatics & Spatial Information Technology, 2018, 41(2):77-80, 83.
[20] SHANNON C E. A mathematical theory of communication[J]. The Bell System Technical Journal, 1948, 27(3):379-423.
[21] JIANG Bin. Head/Tail breaks for visualization of city structure and dynamics[J]. Cities, 2015, 43:69-77.
[22] JIANG Bin. Head/Tail breaks:a new classification scheme for data with a Heavy-Tailed distribution[J]. The Professional Geographer, 2013, 65(3):482-494.
[23] JIANG Bin, LIU Xintao, JIA Tao. Scaling of geographic space as a universal rule for map generalization[J]. Annals of the Association of American Geographers, 2013, 103(4):844-855.
[24] MA Ding, JIANG Bin. A smooth curve as a fractal under the third definition[J]. Cartographica:The International Journal for Geographic Information and Geovisualization, 2018, 53(3):203-210.
[25] JIANG Bin, BRANDT S A. A fractal perspective on scale in geography[J]. ISPRS International Journal of Geo-Information, 2016, 5(6):95-106.
[26] JIANG Bin, MA Ding. How complex is a fractal? Head/Tail breaks and fractional hierarchy[J]. Journal of Geovisualization and Spatial Analysis, 2018, 2(1):6.
[27] TÖPFER F, PILLEWIZER W. The principles of selection[J]. The Cartographic Journal, 1966, 3(1):10-16.
[28] 杨福家. 原子物理学[M]. 北京:高等教育出版社, 1998. YANG Fujia. Atomic physics[M]. Beijing:Higher Education Press, 1998.
[29] MONGIN P. Spurious unanimity and the Pareto principle[J]. Economics & Philosophy, 2016, 32(3):511-532.
[30] ARKIN E M, CHEW L P, HUTTENLOCHER D P, et al. An efficiently computable metric for comparing polygonal shapes[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1991, 13(3):209-216.