Efficient entry point encoding and decoding algorithms on 2D Hilbert space filling curve

Mengjuan Li; Yao Fan; Shaowen Sun; Lianyin Jia; Teng Liang; Mengjuan Li; Yao Fan; Shaowen Sun; Lianyin Jia; Teng Liang

doi:10.3934/mbe.2023914

Mathematical Biosciences and Engineering

2023, Volume 20, Issue 12: 20668-20682. doi: 10.3934/mbe.2023914

Previous Article Next Article

Research article Special Issues

Efficient entry point encoding and decoding algorithms on 2D Hilbert space filling curve

1.
Library, Yunnan Normal University, Kunming 650500, China
2.
Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
3.
School of Communications Information Engineering, Yunnan Communications Vocational and Technical College, Kunming 650500, China

Academic Editor: Peng-Yeng Yin

Received: 08 September 2023 Revised: 02 November 2023 Accepted: 06 November 2023 Published: 16 November 2023

The Hilbert curve is an important method for mapping high-dimensional spatial information into one-dimensional spatial information while preserving the locality in the high-dimensional space. Entry points of a Hilbert curve can be used for image compression, dimensionality reduction, corrupted image detection and many other applications. As far as we know, there is no specific algorithms developed for entry points. To address this issue, in this paper we present an efficient entry point encoding algorithm (EP-HE) and a corresponding decoding algorithm (EP-HD). These two algorithms are efficient by exploiting the m consecutive 0s in the rear part of an entry point. We further found that the outputs of these two algorithms are a certain multiple of a certain bit of s, where s is the starting state of these m levels. Therefore, the results of these m levels can be directly calculated without iteratively encoding and decoding. The experimental results show that these two algorithms outperform their counterparts in terms of processing entry points.
- Hilbert space filling curve,
- entry point,
- EP-HE,
- EP-HD
Citation: Mengjuan Li, Yao Fan, Shaowen Sun, Lianyin Jia, Teng Liang. Efficient entry point encoding and decoding algorithms on 2D Hilbert space filling curve[J]. Mathematical Biosciences and Engineering, 2023, 20(12): 20668-20682. doi: 10.3934/mbe.2023914

Related Papers:

Abstract

The Hilbert curve is an important method for mapping high-dimensional spatial information into one-dimensional spatial information while preserving the locality in the high-dimensional space. Entry points of a Hilbert curve can be used for image compression, dimensionality reduction, corrupted image detection and many other applications. As far as we know, there is no specific algorithms developed for entry points. To address this issue, in this paper we present an efficient entry point encoding algorithm (EP-HE) and a corresponding decoding algorithm (EP-HD). These two algorithms are efficient by exploiting the m consecutive 0s in the rear part of an entry point. We further found that the outputs of these two algorithms are a certain multiple of a certain bit of s, where s is the starting state of these m levels. Therefore, the results of these m levels can be directly calculated without iteratively encoding and decoding. The experimental results show that these two algorithms outperform their counterparts in terms of processing entry points.

References

[1]	T. Corcoran, R. Zamora-Resendiz, X. Liu, S. Crivelli, A spatial mapping algorithm with applications in deep learning-based structure classification, preprint, arXiv: 1802.02532.
[2]	B. Yin, M. Balvert, D. Zambrano, A. Schönhuth, S. Bohte, An image representation based convolutional network for DNA classification, preprint, arXiv: 1806.04931.
[3]	P. Tsinganos, B. Cornelis, J. Cornelis, B. Jansen, A. Skodras, Hilbert sEMG data scanning for hand gesture recognition based on deep learning, Neural Comput. Appl., 33 (2021), 2645–2666. https://doi.org/10.1007/s00521-020-05128-7 doi: 10.1007/s00521-020-05128-7
[4]	J. H. Bappy, C. Simons, L. Nataraj, B. S. Manjunath, A. K. Roy-Chowdhury, Hybrid LSTM and encoder–decoder architecture for detection of image forgeries, IEEE Trans. Image Process., 28 (2019), 3286–3300. https://doi.org/10.1109/TIP.2019.2895466 doi: 10.1109/TIP.2019.2895466
[5]	S. Dhahbi, W. Barhoumi, J. Kurek, B. Swiderski, M. Kruk, E. Zagrouba, False-positive reduction in computer-aided mass detection using mammographic texture analysis and classification, Comput. Methods Programs Biomed., 160 (2018), 75–83. https://doi.org/10.1016/j.cmpb.2018.03.026 doi: 10.1016/j.cmpb.2018.03.026
[6]	Z. Yao, J. Zhang, T. Li, Y. Ding, A trajectory big data storage model incorporating partitioning and spatio-temporal multidimensional hierarchical organization, ISPRS Int. J. Geo-Inform., 11 (2022), 621. https://doi.org/10.3390/ijgi11120621 doi: 10.3390/ijgi11120621
[7]	Z. Liu, L. Wu, W. Meng, H. Wang, W. Wang, Accurate range query with privacy preservation for outsourced location-based service in IOT, IEEE Int. Things J., 8 (2021), 14322–14337. https://doi.org/10.1109/JIOT.2021.3068566 doi: 10.1109/JIOT.2021.3068566
[8]	X. Zhang, L. Wang, Z. Zhou, Y. Niu, A chaos-based image encryption technique utilizing Hilbert curves and H-fractals, IEEE Access, 7 (2019), 74734–74746. https://doi.org/10.1109/ACCESS.2019.2921309 doi: 10.1109/ACCESS.2019.2921309
[9]	P. Li, Z. Xie, Z. Zhou, G. Yue, S. Zheng, X. Yang, A source-location privacy preservation method based on hilbert-filling-curve routing protocol in marine wireless sensor networks (in Chinese), J. Electron. Inform. Technol., 42 (2020), 1510–1518.
[10]	C. Böhm, M. Perdacher, C. Plant, A novel hilbert curve for cache-locality preserving loops, IEEE Trans. Big Data, 2018.
[11]	L. Jia, H. Tang, M. Li, B. Zhao, S. Wei, H. Zhou, An efficient association rule mining-based spatial keyword index, Int. J. Data Warehous. Mining, 19 (2023), 1–19. https://doi.org/10.4018/IJDWM.316161 doi: 10.4018/IJDWM.316161
[12]	J. Chen, L. Yu, W. Wang, Hilbert space filling curve based scan-order for point cloud attribute compression, IEEE Trans. Image Process., 31 (2022), 4609–4621. https://doi.org/10.1109/TIP.2022.3186532 doi: 10.1109/TIP.2022.3186532
[13]	A. R. Butz, Alternative algorithm for Hilbert's space-filling curve, IEEE Trans. Comput., 100 (1971), 424–426. https://doi.org/10.1109/T-C.1971.223258 doi: 10.1109/T-C.1971.223258
[14]	Fast Hilbert Curve Generation, Sorting, and Range Queries. Available from: https://github.com/Cheedoong/hilbert.
[15]	Convert between 1D and 2D coordinates of Hilbert Curve. Available from: http://people.math.sc.edu/Burkardt/c_src/hilbert_curve/hilbert_curve.html.
[16]	S. Li, E. Zhong, S. Wang, An algorithm for Hilbert ordering code based on state-transition matrix (in Chinese), J. Geo-Inform. Sci., 16 (2014), 846–851.
[17]	Hilbert_spatial_index. Available from: https://github.com/xcTorres/hilbert_spatial_index.
[18]	L. Jia, M. Chen, M. Li, J. You, J. Ding, State view based efficient Hilbert encoding and decoding algorithms (in Chinese), J. Electron. Inform. Technol., 42 (2020), 1494–1501.
[19]	J. Zhang, S. Kamata, A generalized 3-D Hilbert scan using look-up tables, J. Visual Commun. Image Represent., 23 (2012), 418–425. https://doi.org/10.1016/j.jvcir.2011.12.005 doi: 10.1016/j.jvcir.2011.12.005
[20]	L. Jia, B. Liang, M. Li, Y. Liu, Y. Chen, J. Ding, Efficient 3D Hilbert curve encoding and decoding algorithms, Chinese J. Electron., 31 (2022), 1–8. https://doi.org/10.1049/cje.2020.00.171 doi: 10.1049/cje.2020.00.171
[21]	H. Liu, T. Cui, W. Leng, L. Zhang, Encoding and decoding algorithms for arbitrary dimensional Hilbert order, preprint, arXiv: 1601.01274.
[22]	T-Drive trajectory data sample. Available from: https://www.microsoft.com/en-us/research/publication/t-drive-trajectory-data-sample/.
[23]	C. Tian, Y. Zhang, W. Zuo, C. W. Lin, D. Zhang, Y. Yuan, A heterogeneous group CNN for image super-resolution, IEEE Trans. Neural Networks Learn. Syst., 2022. https://doi.org/10.1109/TNNLS.2022.3210433 doi: 10.1109/TNNLS.2022.3210433
[24]	Q. Zhang, J. Xiao, C. Tian, J. C. Lin, S. Zhang, A robust deformed convolutional neural network (CNN) for image denoising, CAAI Trans. Intell. Technol., 8 (2023), 331–342. https://doi.org/10.1049/cit2.12110 doi: 10.1049/cit2.12110
[25]	C. Tian, M. Zheng, W. Zuo, B. Zhang, Y. Zhang, D. Zhang, Multi-stage image denoising with the wavelet transform, Pattern Recogn., 134 (2023), 109050. https://doi.org/10.1016/j.patcog.2022.109050 doi: 10.1016/j.patcog.2022.109050
[26]	Z. Chen, L. Chen, G. Cong, C. S. Jensen, Location-and keyword-based querying of geo-textual data: A survey, VLDB J., 30 (2021), 603–640. https://doi.org/10.1007/s00778-021-00661-w doi: 10.1007/s00778-021-00661-w
[27]	L. Jia, J. Tang, M. Li, J. You, J. Ding, Y. Chen, TWE‐WSD: An effective topical word embedding based word sense disambiguation, CAAI Trans. Intell. Technol., 6 (2021), 72–79. https://doi.org/10.1049/cit2.12006 doi: 10.1049/cit2.12006

Reader Comments

Your name:*

Email:*
© 2023 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)