高效前綴約簡的三維Hilbert空間填充曲線編解碼算法

賈連印; 范瑤; 丁家滿; 李曉武; 游進(jìn)國

doi:10.11999/JEIT230013

高效前綴約簡的三維Hilbert空間填充曲線編解碼算法

doi: 10.11999/JEIT230013

1.
昆明理工大學(xué)信息與自動(dòng)化學(xué)院昆明 650500
2.
云南省計(jì)算機(jī)應(yīng)用重點(diǎn)實(shí)驗(yàn)室昆明 650500

基金項(xiàng)目: 國家自然科學(xué)基金(62262035, 62262034, 62062046)

詳細(xì)信息

作者簡介:
賈連印：男，博士，副教授，研究方向?yàn)閿?shù)據(jù)庫、數(shù)據(jù)挖掘、信息檢索等

范瑤：男，碩士生，研究方向?yàn)閿?shù)據(jù)庫、信息檢索

丁家滿：男，碩士，教授，研究方向?yàn)閿?shù)據(jù)挖掘、云計(jì)算等

李曉武：男，博士，講師，研究方向?yàn)閿?shù)據(jù)庫等

游進(jìn)國：男，博士，副教授，研究方向?yàn)閿?shù)據(jù)庫、數(shù)據(jù)挖掘等

通訊作者:
丁家滿　jiamanding@kust.end.cn

中圖分類號: TN911.2; TP301.6
計(jì)量
- 文章訪問數(shù): 613
- HTML全文瀏覽量: 350
- PDF下載量: 69
- 被引次數(shù): 0
出版歷程
- 收稿日期: 2023-01-12
- 修回日期: 2023-06-01
- 網(wǎng)絡(luò)出版日期: 2023-06-20
- 刊出日期: 2024-02-29

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

JIA Lianyin^{1, 2},
FAN Yao¹,
DING Jiaman^{1
, ,},
LI Xiaowu¹,
YOU Jinguo¹

1.
Faculty of Information Engineering and Automation, Kunming University of Science and Technology, Kunming 650500, China
2.
Key Laboratory of Computer Technology Application of Yunnan Province, Kunming 650500, China

Funds: The National Natural Science Foundation of China (62262035, 62262034, 62062046)

摘要

摘要: 3維Hilbert空間填充曲線(3D HSFC)的編碼和解碼效率對空間查詢處理、圖像處理等領(lǐng)域的應(yīng)用舉足輕重?，F(xiàn)有的3維編解碼算法獨(dú)立編解碼每一個(gè)點(diǎn)，忽略了Hilbert曲線的局部保持特性。為了提高編解碼效率，該文設(shè)計(jì)了高效的3D狀態(tài)視圖，并提出一種新的前綴約簡的3D HSFC編碼算法(PR-3HE)和前綴約簡3D HSFC解碼算法(PR-3HD)，這兩個(gè)算法通過公共前綴的定義和識別、公共前綴約簡及多種優(yōu)化技術(shù)來最小化需要編碼的階數(shù)，從而提高3D HSFC的編解碼效率。理論上證明：當(dāng)編碼或解碼一個(gè)$k$階的窗體(窗體內(nèi)總共含有${2^k} \times {2^k} \times {2^k}$個(gè)點(diǎn))時(shí)，PR-3HE平均每個(gè)點(diǎn)的編碼階數(shù)不超過2，PR-3HD平均解碼階數(shù)不超過8/7。相對于傳統(tǒng)的基于迭代的方法，編解碼時(shí)間復(fù)雜度從$O(k)$降低到了$O(1)$。實(shí)驗(yàn)結(jié)果表明，該文算法在模擬數(shù)據(jù)集和真實(shí)數(shù)據(jù)集上的表現(xiàn)顯著優(yōu)于現(xiàn)有算法。
- 3維Hilbert空間填充曲線 /
- 3維狀態(tài)視圖 /
- 前綴約簡 /
- 3D HSFC編碼算法 /
- 3D HSFC解碼算法
Abstract: The encoding and decoding efficiency of 3D Hilbert Space Filling Curve (3D HSFC) is key for the application of spatial query processing, image processing. The existing 3D encoding and decoding algorithms encode and decode each point independently, ignoring the local preservation characteristic of Hilbert curve. To improve the efficiency of encoding and decoding, an efficient 3D state view is designed in this paper, and a new Prefix Reduction 3D HSFC Encoding Algorithm (PR-3HE) and Prefix Reduction 3D HSFC Decoding Algorithm (PR-3HD) are proposed. These two algorithms minimize the orders to be processed through the definition and identification of common prefix, common prefix reduction and various optimization techniques, thus improving 3D HSFC encoding and decoding efficiency. Theoretical proof is provided in this paper, demonstrating that when encoding or decoding a k-order window (all ${2^k} \times {2^k} \times {2^k}$ points in a window), PR-3HE passively encodes no more than 2 orders for each coordinate on average, while PR-3HD passively decodes no more than 8/7 orders for each Hilbert code on average. The encoding and decoding time complexity can be reduced from $O(k)$ to $O(1)$. Experimental results show on both synthetic and real dataset the benefits of our algorithms over the other counterparts.
- 3D Hilbert Space Filling Curve (3D HSFC) /
- 3D state view /
- Prefix reduction /
- 3D HSFC encoding algorithm /
- 3D HSFC decoding algorithm

HTML全文

圖 1 24種基礎(chǔ)狀態(tài)

下載: 全尺寸圖片幻燈片

圖 2 1階Hilbert曲線

下載: 全尺寸圖片幻燈片

圖 3 2階Hilbert曲線

下載: 全尺寸圖片幻燈片

圖 4 編碼示例

下載: 全尺寸圖片幻燈片

圖 6 迭代編碼的次數(shù)(3階)

下載: 全尺寸圖片幻燈片

圖 5 編碼當(dāng)前點(diǎn)$q$的流程圖

下載: 全尺寸圖片幻燈片

圖 7 離散數(shù)據(jù)集上編碼效率對比

下載: 全尺寸圖片幻燈片

圖 8 窗體數(shù)據(jù)集上編碼效率對比

下載: 全尺寸圖片幻燈片

圖 9 GeoLife數(shù)據(jù)集上編碼效率對比

下載: 全尺寸圖片幻燈片

圖 10 離散數(shù)據(jù)集上解碼效率對比

下載: 全尺寸圖片幻燈片

圖 11 窗體數(shù)據(jù)集上解碼效率對比

下載: 全尺寸圖片幻燈片

圖 12 GeoLife數(shù)據(jù)集上解碼效率對比

下載: 全尺寸圖片幻燈片

表 1 CHM

狀態(tài)	000	001	010	011	100	101	110	111
0	0	1	3	2	7	6	4	5
1	0	1	7	6	3	2	4	5
2	0	3	1	2	7	4	6	5
3	0	7	1	6	3	4	2	5
4	0	3	7	4	1	2	6	5
5	0	7	3	4	1	6	2	5
6	2	1	3	0	5	6	4	7
7	6	1	7	0	5	2	4	3
8	2	3	1	0	5	4	6	7
9	6	7	1	0	5	4	2	3
10	4	3	7	0	5	2	6	1
11	4	7	3	0	5	6	2	1
12	2	1	5	6	3	0	4	7
13	6	1	5	2	7	0	4	3
14	2	3	5	4	1	0	6	7
15	6	7	5	4	1	0	2	3
16	4	3	5	2	7	0	6	1
17	4	7	5	6	3	0	2	1
18	2	5	1	6	3	4	0	7
19	6	5	1	2	7	4	0	3
20	2	5	3	4	1	6	0	7
21	6	5	7	4	1	2	0	3
22	4	5	3	2	7	6	0	1
23	4	5	7	6	3	2	0	1

下載: 導(dǎo)出CSV

表 2 CSM

狀態(tài)	000	001	010	011	100	101	110	111
0	5	1	13	0	13	22	5	0
1	3	0	7	23	7	1	3	1
2	4	19	3	2	19	4	16	2
3	1	9	2	17	9	1	3	3
4	2	21	21	2	5	4	10	4
5	0	15	15	0	4	11	5	5
6	6	7	12	11	6	20	11	12
7	21	6	1	9	7	7	9	1
8	8	18	9	10	8	10	14	18
9	15	3	8	7	9	7	9	3
10	8	23	23	8	10	10	4	11
11	6	17	17	6	11	5	11	10
12	12	13	12	18	6	17	17	6
13	19	12	13	13	0	15	15	0
14	14	20	14	16	15	16	8	20
15	9	5	15	13	14	13	15	5
16	14	22	16	16	22	14	2	17
17	12	11	17	3	11	12	17	16
18	18	18	19	12	8	23	23	8
19	13	19	18	19	2	21	21	2
20	20	20	14	22	21	6	22	14
21	7	21	4	19	20	21	19	4
22	20	22	16	22	16	0	20	23
23	18	23	10	1	10	23	18	22

下載: 導(dǎo)出CSV

算法1 PR-3HE
輸入：${H_p}$：$p$的編碼；$\|{P_{p,q}}\|$：$p$和$q$的公共前綴長度；
$q$：當(dāng)前點(diǎn)；$r$：后鄰點(diǎn)；$k$：階數(shù)
輸出：${H_q}$：當(dāng)前點(diǎn)$q$的Hilbert編碼；$\|{P_{p,r} }\|$：$q$和$r$的公共前綴　　　　長度；
1. ${H_q}$←$ \overrightarrow {H_p^{\|{P_{p,q}}\|}} $
2. $\|{P_{p,r}}\|$←計(jì)算q和r的最大公共前綴長度
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

下載: 導(dǎo)出CSV

表 3 HCM

狀態(tài)	0	1	2	3	4	5	6	7
0	000	001	011	010	110	111	101	100
1	000	001	101	100	110	111	011	010
2	000	010	011	001	101	111	110	100
3	000	010	110	100	101	111	011	001
4	000	100	101	001	011	111	110	010
5	000	100	110	010	011	111	101	001
6	011	001	000	010	110	100	101	111
7	011	001	101	111	110	100	000	010
8	011	010	000	001	101	100	110	111
9	011	010	110	111	101	100	000	001
10	011	111	101	001	000	100	110	010
11	011	111	110	010	000	100	101	001
12	101	001	000	100	110	010	011	111
13	101	001	011	111	110	010	000	100
14	101	100	000	001	011	010	110	111
15	101	100	110	111	011	010	000	001
16	101	111	011	001	000	010	110	100
17	101	111	110	100	000	010	011	001
18	110	010	000	100	101	001	011	111
19	110	010	011	111	101	001	000	100
20	110	100	000	010	011	001	101	111
21	110	100	101	111	011	001	000	010
22	110	111	011	010	000	001	101	100
23	110	111	101	100	000	001	011	010

下載: 導(dǎo)出CSV

表 4 HSM

狀態(tài)	0	1	2	3	4	5	6	7
0	5	1	0	13	5	0	22	13
1	3	0	1	7	3	1	23	7
2	4	3	2	19	4	2	16	19
3	1	2	3	9	1	3	17	9
4	2	5	4	21	2	4	10	21
5	0	4	5	15	0	5	11	15
6	11	7	6	12	11	6	20	12
7	9	6	7	1	9	7	21	1
8	10	9	8	18	10	8	14	18
9	7	8	9	3	7	9	15	3
10	8	11	10	23	8	10	4	23
11	6	10	11	17	6	11	5	17
12	17	13	12	6	17	12	18	6
13	15	12	13	0	15	13	19	0
14	16	15	14	20	16	14	8	20
15	13	14	15	5	13	15	9	5
16	14	17	16	22	14	16	2	22
17	12	16	17	11	12	17	3	11
18	23	19	18	8	23	18	12	8
19	21	18	19	2	21	19	13	2
20	22	21	20	14	22	20	6	14
21	19	20	21	4	19	21	7	4
22	20	23	22	16	20	22	0	16
23	18	22	23	10	18	23	1	10

下載: 導(dǎo)出CSV

算法2 PR-3HD
輸入：${X_p}$, ${Y_p}$,${Z_p}$：$p$的坐標(biāo)分量；$\|{P_{Hp,Hq} }\|$：$Hp$和$Hq$的最大公共前　　　　綴長度；${H_q}$, ${H_r}$：$q$和$r$的Hilbert編碼；$k$：階數(shù)
輸出：$q$的坐標(biāo)分量；$\|{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}}}\| $←計(jì)算Hq和Hr的最大公共前綴長度
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

下載: 導(dǎo)出CSV

參考文獻(xiàn)(18)

[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]	賈連印, 陳明鮮, 李孟娟, 等. 基于狀態(tài)視圖的高效Hilbert編碼和解碼算法[J]. 電子與信息學(xué)報(bào), 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]	賈連印, 孔明, 王維晨, 等. 數(shù)據(jù)偏斜分布下的二維Hilbert編解碼算法[J]. 清華大學(xué)學(xué)報(bào)(自然科學(xué)版), 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]	李紹俊, 鐘耳順, 王少華, 等. 基于狀態(tài)轉(zhuǎn)移矩陣的Hilbert碼快速生成算法[J]. 地球信息科學(xué)學(xué)報(bào), 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]	陳曉宏, 儲飛黃, 方勝良, 等. 基于剖分網(wǎng)格改進(jìn)A^算法的航跡規(guī)劃研究[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ì)算[J]. 計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 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.