高级搜索

留言板

尊敬的读者、作者、审稿人, 关于本刊的投稿、审稿、编辑和出版的任何问题, 您可以本页添加留言。我们将尽快给您答复。谢谢您的支持!

姓名
邮箱
手机号码
标题
留言内容
验证码

高效前缀约简的三维Hilbert空间填充曲线编解码算法

贾连印 范瑶 丁家满 李晓武 游进国

贾连印, 范瑶, 丁家满, 李晓武, 游进国. 高效前缀约简的三维Hilbert空间填充曲线编解码算法[J]. 电子与信息学报, 2024, 46(2): 633-642. doi: 10.11999/JEIT230013
引用本文: 贾连印, 范瑶, 丁家满, 李晓武, 游进国. 高效前缀约简的三维Hilbert空间填充曲线编解码算法[J]. 电子与信息学报, 2024, 46(2): 633-642. doi: 10.11999/JEIT230013
JIA Lianyin, FAN Yao, DING Jiaman, LI Xiaowu, YOU Jinguo. 3D Hilbert Space Filling Curve Encoding and Decoding Algorithms Based on Efficient Prefix Reduction[J]. Journal of Electronics & Information Technology, 2024, 46(2): 633-642. doi: 10.11999/JEIT230013
Citation: JIA Lianyin, FAN Yao, DING Jiaman, LI Xiaowu, YOU Jinguo. 3D Hilbert Space Filling Curve Encoding and Decoding Algorithms Based on Efficient Prefix Reduction[J]. Journal of Electronics & Information Technology, 2024, 46(2): 633-642. doi: 10.11999/JEIT230013

高效前缀约简的三维Hilbert空间填充曲线编解码算法

doi: 10.11999/JEIT230013
基金项目: 国家自然科学基金(62262035, 62262034, 62062046)
详细信息
    作者简介:

    贾连印:男,博士,副教授,研究方向为数据库、数据挖掘、信息检索等

    范瑶:男,硕士生,研究方向为数据库、信息检索

    丁家满:男,硕士,教授,研究方向为数据挖掘、云计算等

    李晓武:男,博士,讲师,研究方向为数据库等

    游进国:男,博士,副教授,研究方向为数据库、数据挖掘等

    通讯作者:

    丁家满 jiamanding@kust.end.cn

  • 中图分类号: TN911.2; TP301.6

3D Hilbert Space Filling Curve Encoding and Decoding Algorithms Based on Efficient Prefix Reduction

Funds: The National Natural Science Foundation of China (62262035, 62262034, 62062046)
  • 摘要: 3维Hilbert空间填充曲线(3D HSFC)的编码和解码效率对空间查询处理、图像处理等领域的应用举足轻重。现有的3维编解码算法独立编解码每一个点,忽略了Hilbert曲线的局部保持特性。为了提高编解码效率,该文设计了高效的3D状态视图,并提出一种新的前缀约简的3D HSFC编码算法(PR-3HE)和前缀约简3D HSFC解码算法(PR-3HD),这两个算法通过公共前缀的定义和识别、公共前缀约简及多种优化技术来最小化需要编码的阶数,从而提高3D HSFC的编解码效率。理论上证明:当编码或解码一个$k$阶的窗体(窗体内总共含有${2^k} \times {2^k} \times {2^k}$个点)时,PR-3HE平均每个点的编码阶数不超过2,PR-3HD平均解码阶数不超过8/7。相对于传统的基于迭代的方法,编解码时间复杂度从$O(k)$降低到了$O(1)$。实验结果表明,该文算法在模拟数据集和真实数据集上的表现显著优于现有算法。
  • 图  1  24种基础状态

    图  2  1阶Hilbert曲线

    图  3  2阶Hilbert曲线

    图  4  编码示例

    图  6  迭代编码的次数(3阶)

    图  5  编码当前点$q$的流程图

    图  7  离散数据集上编码效率对比

    图  8  窗体数据集上编码效率对比

    图  9  GeoLife数据集上编码效率对比

    图  10  离散数据集上解码效率对比

    图  11  窗体数据集上解码效率对比

    图  12  GeoLife数据集上解码效率对比

    表  1  CHM

    状态000001010011100101110111
    001327645
    101763245
    203127465
    307163425
    403741265
    507341625
    621305647
    761705243
    823105467
    967105423
    1043705261
    1147305621
    1221563047
    1361527043
    1423541067
    1567541023
    1643527061
    1747563021
    1825163407
    1965127403
    2025341607
    2165741203
    2245327601
    2345763201
    下载: 导出CSV

    表  2  CSM

    状态000001010011100101110111
    051130132250
    1307237131
    241932194162
    3192179133
    422121254104
    501515041155
    66712116201112
    7216197791
    88189108101418
    9153879793
    108232381010411
    116171761151110
    1212131218617176
    1319121313015150
    14142014161516820
    159515131413155
    16142216162214217
    17121117311121716
    1818181912823238
    1913191819221212
    20202014222162214
    217214192021194
    22202216221602023
    23182310110231822
    下载: 导出CSV
    算法1 PR-3HE
     输入:${H_p}$:$p$的编码;$|{P_{p,q}}|$:$p$和$q$的公共前缀长度;
        $q$:当前点;$r$:后邻点;$k$:阶数
     输出:${H_q}$:当前点$q$的Hilbert编码;$|{P_{p,r} }|$:$q$和$r$的公共前缀
        长度;
     1. ${H_q}$←$ \overrightarrow {H_p^{|{P_{p,q}}|}} $
     2. $|{P_{p,r}}|$←计算qr的最大公共前缀长度
     3. $s$←$ M[\text{|}{P}_{p,q}|+1] $
     4. FOR $i$←$ \text{|}{P}_{p,q}| $+1 to $k$
     5.   ${H_q} = {H_q} < <3|{ { {\rm{CHM} }[s][x} }_q^i][y_q^i][z_q^i]$
     6.   $s = {\text{CSM}}[s][x_q^i][y_q^i][z_q^i]$
     7.   IF $i <= |{P_{q,r} }|$
     8.     $M[i + 1] = s$
     9.   END IF
     10. END FOR
    下载: 导出CSV

    表  3  HCM

    状态01234567
    0000001011010110111101100
    1000001101100110111011010
    2000010011001101111110100
    3000010110100101111011001
    4000100101001011111110010
    5000100110010011111101001
    6011001000010110100101111
    7011001101111110100000010
    8011010000001101100110111
    9011010110111101100000001
    10011111101001000100110010
    11011111110010000100101001
    12101001000100110010011111
    13101001011111110010000100
    14101100000001011010110111
    15101100110111011010000001
    16101111011001000010110100
    17101111110100000010011001
    18110010000100101001011111
    19110010011111101001000100
    20110100000010011001101111
    21110100101111011001000010
    22110111011010000001101100
    23110111101100000001011010
    下载: 导出CSV

    表  4  HSM

    状态01234567
    051013502213
    1301731237
    243219421619
    3123913179
    425421241021
    504515051115
    61176121162012
    7967197211
    81098181081418
    9789379153
    108111023810423
    116101117611517
    1217131261712186
    1315121301513190
    14161514201614820
    151314155131595
    16141716221416222
    17121617111217311
    1823191882318128
    1921181922119132
    20222120142220614
    211920214192174
    22202322162022016
    23182223101823110
    下载: 导出CSV
    算法2 PR-3HD
     输入:${X_p}$, ${Y_p}$,${Z_p}$$p$的坐标分量;$|{P_{Hp,Hq} }|$:$Hp$和$Hq$的最大公共前
        缀长度;${H_q}$, ${H_r}$:$q$和$r$的Hilbert编码;$k$:阶数
     输出:$q$的坐标分量;$|{P_{Hq,Hr} }|$:$Hq$和$Hr$的最大公共前缀长度;
     1. ${X_q}$,${Y_q}$,${Z_q}$←$(\overleftarrow{X_p^{ {\text{|} }{P_{ {H_p},{H_q} } }|} },\overleftarrow{Y_p^{ {\text{|} }{P_{ {H_p},{H_q} } }|}},\overleftarrow{Z_p^{ {\text{|} }{P_{ {H_p},{H_q} } }|}})$
     2. $ {\text{|}}{P_{{H_q},{H_r}}}| $←计算HqHr的最大公共前缀长度
     3. $s$←$ M{\text{[|}}{P_{{H_p},{H_q}}}| + 1] $
     4. FOR $i$←$ {\text{|}}{P_{{H_p},{H_q}}}| $+1 to $k$
     5.     $x_q^iy_q^iz_q^i = {\text{HCM}}[s][H_q^i]$
     6.     ${X_q} = {X_q} < < 1|x_q^i$
     7.     ${Y_q} = {Y_q} < < 1|y_q^i$
     8.     ${Z_q} = {Z_1} << 1|z_q^i$
     9.     $s = {\text{HSM}}[s][H_q^i]$
     10.     IF $i <= |{P_{ {H_q},{H_r} } }|$
     11.      $M[i + 1] = s$
     12.     END IF
     13. END FOR
    下载: 导出CSV
  • [1] YAO Zhixin, ZHANG Jianqin, LI Taizeng, et al. A trajectory big data storage model incorporating partitioning and spatio-temporal multidimensional hierarchical organization[J]. ISPRS International Journal of Geo-Information, 2022, 11(12): 621. doi: 10.3390/ijgi11120621.
    [2] LIU Zhaoman, WU Lei, MENG Weizhi, et al. Accurate range query with privacy preservation for outsourced location-based service in IOT[J]. IEEE Internet of Things Journal, 2021, 8(18): 14322–14337. doi: 10.1109/JIOT.2021.3068566.
    [3] ZHANG Xuncai, WANG Lingfei, ZHOU Zheng, et al. A chaos-based image encryption technique utilizing Hilbert curves and H-fractals[J]. IEEE Access, 2019, 7: 74734–74746. doi: 10.1109/ACCESS.2019.2921309.
    [4] CHEN Jiafeng, YU Lu, and WANG Wenyi. Hilbert space filling curve based scan-order for point cloud attribute compression[J]. IEEE Transactions on Image Processing, 2022, 31: 4609–4621. doi: 10.1109/TIP.2022.3186532.
    [5] 贾连印, 陈明鲜, 李孟娟, 等. 基于状态视图的高效Hilbert编码和解码算法[J]. 电子与信息学报, 2020, 42(6): 1494–1501. doi: 10.11999/JEIT190501.

    JIA Lianyin, CHEN Mingxian, LI Mengjuan, et al. State view based efficient Hilbert encoding and decoding algorithms[J]. Journal of Electronics &Information Technology, 2020, 42(6): 1494–1501. doi: 10.11999/JEIT190501.
    [6] BÖHM C, PERDACHER M, and PLANT C. A novel Hilbert curve for cache-locality preserving loops[J]. IEEE Transactions on Big Data, 2021, 7(2): 241–254. doi: 10.1109/TBDATA.2018.2830378.
    [7] 贾连印, 孔明, 王维晨, 等. 数据偏斜分布下的二维Hilbert编解码算法[J]. 清华大学学报(自然科学版), 2022, 62(9): 1426–1434. doi: 10.16511/j.cnki.qhdxxb.2021.21.043.

    JIA Lianyin, KONG Ming, WANG Weichen, et al. 2-D Hilbert encoding and decoding algorithms on skewed data[J]. Journal of Tsinghua University (Science and Technology), 2022, 62(9): 1426–1434. doi: 10.16511/j.cnki.qhdxxb.2021.21.043.
    [8] 李绍俊, 钟耳顺, 王少华, 等. 基于状态转移矩阵的Hilbert码快速生成算法[J]. 地球信息科学学报, 2014, 16(6): 846–851. doi: 10.3724/SP.J.1047.2014.00846.

    LI Shaojun, ZHONG Ershun, WANG Shaohua, et al. An algorithm for Hilbert ordering code based on state-transition matrix[J]. Journal of Geo-Information Science, 2014, 16(6): 846–851. doi: 10.3724/SP.J.1047.2014.00846.
    [9] HAVERKORT H. How many three-dimensional Hilbert curves are there?[J]. Journal of Computational Geometry, 2017, 8(1): 206–281. doi: 10.20382/jocg.v8i1a10.
    [10] WEISSENBÖCK J, FRÖHLER B, GRÖLLER E, et al. Dynamic volume lines: Visual comparison of 3D volumes through space-filling curves[J]. IEEE Transactions on Visualization and Computer Graphics, 2019, 25(1): 1040–1049. doi: 10.1109/TVCG.2018.2864510.
    [11] WU Yuhao, CAO Xuefeng, and AN Zipeng. A spatiotemporal trajectory data index based on the Hilbert curve code[C]. IOP Conference Series: Earth and Environmental Science, Beijing, China, 2020: 012005.
    [12] TSINGANOS P, CORNELIS B, CORNELIS J, et al. Hilbert sEMG data scanning for hand gesture recognition based on deep learning[J]. Neural Computing and Applications, 2021, 33(7): 2645–2666. doi: 10.1007/s00521-020-05128-7.
    [13] 陈晓宏, 储飞黄, 方胜良, 等. 基于剖分网格改进A*算法的航迹规划研究[J]. 电光与控制, 2022, 29(7): 17–21. doi: 10.3969/j.issn.1671-637X.2022.07.004.

    CHEN Xiaohong, CHU Feihuang, FANG Shengliang, et al. Trajectory planning based on A* algorithm improved by subdivision grid[J]. Electronics Optics &Control, 2022, 29(7): 17–21. doi: 10.3969/j.issn.1671-637X.2022.07.004.
    [14] MOORE D. Fast Hilbert curve generation, sorting, and range queries[EB/OL]. https://github.com/Cheedoong/hilbert, 2021.
    [15] 李晨阳, 张杨, 冯玉才. N维Hilbert编码的计算[J]. 计算机辅助设计与图形学学报, 2006, 18(7): 1032–1038. doi: 10.3321/j.issn:1003-9775.2006.07.024.

    LI Chenyang, ZHANG Yang, and FENG Yucai. Calculation of N-dimensional Hilbert codes[J]. Journal of Computer-Aided Design &Computer Graphics, 2006, 18(7): 1032–1038. doi: 10.3321/j.issn:1003-9775.2006.07.024.
    [16] ZHANG Jian and KAMATA S I. A generalized 3-D Hilbert scan using look-up tables[J]. Journal of Visual Communication and Image Representation, 2012, 23(3): 418–425. doi: 10.1016/j.jvcir.2011.12.005.
    [17] JIA Lianyin, LIANG Binbin, LI Mengjuan, et al. Efficient 3D Hilbert curve encoding and decoding algorithms[J]. Chinese Journal of Electronics, 2022, 31(2): 277–284. doi: 10.1049/cje.2020.00.171.
    [18] ZHENG Yu, XIE Xing, and MA Weiying. GeoLife: A collaborative social networking service among user, location and trajectory[J]. IEEE Data Engineering Bulletin, 2010, 33(2): 32–39.
  • 加载中
图(12) / 表(6)
计量
  • 文章访问数:  458
  • HTML全文浏览量:  274
  • PDF下载量:  61
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-01-12
  • 修回日期:  2023-06-01
  • 网络出版日期:  2023-06-20
  • 刊出日期:  2024-02-29

目录

    /

    返回文章
    返回