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

作者：贾连印; 范瑶; 丁家满^*; 李晓武; 游进国

来源：电子与信息学报, 2023, 1-10.

• 3维Hilbert空间填充曲线
• 3维状态视图
• 前缀约简
• PR-3HE
• PR-3HD

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

• 单位
  昆明理工大学; 自动化学院