Run length coding and efficient compression of hexagonal raster data supported by Gosper curve

doi:10.11947/j.AGCS.2019.20180216

Abstract

Abstract:

By introducing the Gosper curve into hexagonal grid, a new form of run length coding is established.Based on this, the lossless compression coding and loss compression coding of raster data are carried out. First, the bidirectional correspondence between Gosper curve and hexagonal raster data is established to provide guidance and support for data coding. Then, the Gosper coding value of each raster cell is determined. The lossless compression is realized by making run length coding for the coding set of target region. On this basis, loss compression utilizes the good spatial aggregation of Gosper curve to fuse adjacent regions and eliminate details. Under certain threshold constraints and following the direction of Gosper curve, the number of coding objects can be reduced by changing the ownership of partial raster units.The data is recoded through run length coding to simply the coding of target region. At last, the validity of this method is verified by experiment. Based on the realization of compression coding methods, data compression of multi-resolution and different fusion thresholds is explored.In addition, it is compared with other methodes to highlight its advantages.

Key words: grid coding, run length coding, data compression, hexagonal grids, Gosper curve

CLC Number:

P208

XIN Rui, AI Tinghua. Run length coding and efficient compression of hexagonal raster data supported by Gosper curve[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48(2): 226-237.

References

[1] 邬伦, 刘瑜. 地理信息系统:原理、方法和应用[M]. 北京:科学出版社, 2001. WU Lun, LIU Yu. Geographic information system:theories, methods and applications[M]. Beijing:Science Press, 2001.
[2] 张宏, 温永宁, 刘爱利, 等. 地理信息系统算法基础[M]. 北京:科学出版社, 2006. ZHANG Hong, WEN Yongning, LIU Aili, et al. Foundation of geographic information system algorithm[M]. Beijing:Science Press, 2006.
[3] HOFMANN P, TIEDE D. Image segmentation based on hexagonal sampling grids[J]. South-Eastern European Journal of Earth Observation and Geomatics, 2014, 3:173-177.
[4] BIRCH C P D, OOM S P, BEECHAM J A. Rectangular and hexagonal grids used for observation, experiment and simulation in ecology[J]. Ecological Modelling, 2007, 206(3-4):347-359.
[5] CARR D B, OLSEN A R, WHITE D. Hexagon mosaic maps for display of univariate and bivariate geographical data[J]. Cartography and Geographic Information Systems, 1992, 19(4):228-236.
[6] SCOTT D W. A note on choice of bivariate histogram bin shape[J]. Journal of Official Statistics, 1988, 4(1):47-51.
[7] COPPOLA D M, PURVES H R, MCCOY A N, et al. The distribution of oriented contours in the real world[J]. Proceedings of the National Academy of Sciences of the United States of America, 1998, 95(7):4002-4006.
[8] CARR D B. Looking at large data sets using binned data plots[R]. Richland, WA (USA):Pacific Northwest Laboratory, 1990.
[9] CARR D B, LITTLEFIELD R J, NICHOLSON W L, et al. Scatterplot matrix techniques for large N[J]. Journal of the American Statistical Association, 1987, 82(398):424-436.
[10] BATTERSBY S E, STREBE D, FINN M P. Shapes on a plane:evaluating the impact of projection distortion on spatial binning[J]. Cartography and Geographic Information Science, 2017, 44(5):410-421.
[11] 童晓冲, 贲进, 张永生. 全球多分辨率六边形网格剖分及地址编码规则[J]. 测绘学报, 2007, 36(4):428-435. DOI:10.3321/j.issn:1001-1595.2007.04.012. TONG Xiaochong, BEN Jin, ZHANG Yongsheng. The subdivision of global multi-resolution hexagonal grid and the rules of address coding[J]. Acta Geodaetica et Cartographica Sinica, 2007, 36(4):428-435. DOI:10.3321/j.issn:1001-1595.2007.04.012.
[12] 贲进. 地球空间信息离散网格数据模型的理论与算法研究[D]. 郑州:信息工程大学, 2005. BEN Jin. A study of the theory and algorithms of discrete global grid data model for geospatial information management[D]. Zhengzhou:Information Engineering University, 2005.
[13] 赵学胜, 贲进, 孙文彬, 等. 地球剖分格网研究进展综述[J]. 测绘学报, 2016, 45(S1):1-14. DOI:10.11947/j.AGCS.2016.F001. ZHAO Xuesheng, BEN Jin, SUN Wenbin, et al. Overview of the research progress in the earth tessellation grid[J]. Acta Geodaetica et Cartographica Sinica, 2016, 45(S1):1-14. DOI:10.11947/j.AGCS.2016.F001.
[14] SUESS M, MATOS P, GUTIERREZ A, et al. Processing of SMOS level 1C data onto a discrete global grid[C]//Proceedings of 2004 IEEE International Geoscience and Remote Sensing Symposium. Anchorage, AK, USA:IEEE, 2004, 3:1914-1917.
[15] DHARMAWAN R D, SUHARYADI, FARDA N M. Geovisualization using hexagonal tessellation for spatiotemporal earthquake data analysis in indonesia[C]//Proceedings of International Conference on Soft Computing in Data Science. Singapore:Springer, 2017:177-187.
[16] SHELTON T, POORTHUIS A, GRAHAM M, et al. Mapping the data shadows of hurricane sandy:uncovering the sociospatial dimensions of ‘big data’[J]. Geoforum, 2014, 52:167-179.
[17] POLISCIUC E, MAÇÃS C, ASSUNÇÃO F, et al. Hexagonal gridded maps and information layers:a novel approach for the exploration and analysis of retail data[C]//Proceedings of SIGGRAPH ASIA 2016 Symposium on Visualization. Macau, China:ACM, 2016:Article No. 6.
[18] ROTH R E, ROSS K S, MACEACHREN A M. User-centered design for interactive maps:a case study in crime analysis[J]. ISPRS International Journal of Geo-Information, 2015, 4(1):262-301.
[19] 白建军. 基于正八面体的四孔六边形球面格网编码及索引[J]. 遥感学报, 2011, 15(6):1125-1137. BAI Jianjun. Location coding and indexing aperture 4 hexagonal discrete global grid based on octahedron[J]. Journal of Remote Sensing, 2011, 15(6):1125-1137.
[20] 王蕊, 贲进, 杜灵瑀, 等. 平面四孔六边形格网系统编码运算[J]. 测绘学报, 2018, 47(7):1018-1025. DOI:10.11947/j.AGCS.2018.20170374. WANG Rui, BEN Jin, DU Lingyu, et al. Encoding and operation for the planar aperture 4 hexagon grid system[J]. Acta Geodaetica et Cartographica Sinica, 2018, 47(7):1018-1025. DOI:10.11947/j.AGCS.2018.20170374.
[21] MANDELBROT B B, AIZENMAN M. Fractals:form, chance, and dimension[J]. Physics Today, 1979, 32(5):65.
[22] HAVERKORT H, VAN WALDERVEEN F. Locality and bounding-box quality of two-dimensional space-filling curves[J]. Computational Geometry, 2010, 43(2):131-147.
[23] TOBLER W R. A computer movie simulating urban growth in the detroit region[J]. Economic Geography, 1970, 46:234-240.
[24] 信睿, 艾廷华, 何亚坤. Gosper地图的非空间层次数据隐喻表达与分析[J]. 测绘学报, 2017, 46(12):2006-2015. DOI:10.11947/j.AGCS.2017.20160596. XIN Rui, AI Tinghua, HE Yakun. Visualisation and analysis of non-spatial hierarchical data of gosper map[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(12):2006-2015. DOI:10.11947/j.AGCS.2017.20160596.
[25] LINDENMAYER A. Mathematical models for cellular interactions in development[J]. Journal of Theoretical Biology, 1968, 18(3):280-299.
[26] FREEMAN H. On the encoding of arbitrary geometric configurations[J]. IRE Transactions on Electronic Computers, 1961, EC-10(2):260-268.
[27] 吴华意, 龚健雅, 李德仁. 无边界游程编码及其矢栅直接相互转换算法[J]. 测绘学报, 1998, 27(1):63-68. DOI:10.3321/j.issn:1001-1595.1998.01.010. WU Huayi, GONG Jianya, LI Deren. Non-boundary run-length encoding system for raster and its relevant algorithms[J]. Acta Geodaetica et Cartographica Sinica, 1998, 27(1):63-68. DOI:10.3321/j.issn:1001-1595.1998.01.010.
[28] 王结臣, 芮一康, 刘杰. GIS中面的游程编码表达、实现与应用[J]. 测绘科学, 2008, 33(4):26-28. WANG Jiechen, RUI Yikang, LIU Jie. Run-length encoding system about area:representation, implement and applications in GIS[J]. Science of Surveying and Mapping, 2008, 33(4):26-28.
[29] 王家耀. 时空大数据时代的地图学[J]. 测绘学报, 2017, 46(10):1226-1237. DOI:10.11947/j.AGCS.2017.20170308. WANG Jiayao. Cartography in the age of spatio-temporal big data[J]. Acta Geodaetica et Cartographica Sinica, 2017, 46(10):1226-1237. DOI:10.11947/j.AGCS.2017.20170308.