Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Arabian Journal for Science and Engineering
Published in: Arabian Journal for Science and Engineering 11/2019

29-06-2019 | Research Article - Computer Engineering and Computer Science

Massive Point Cloud Space Management Method Based on Octree-Like Encoding

Authors: Bin Lu, Qiang Wang, A’Nan Li

Published in: Arabian Journal for Science and Engineering | Issue 11/2019

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Based on the mass point cloud data, this paper proposes a hybrid octree mixing point cloud index structure which combines the KD-tree spatial segmentation idea to realize the efficient management of mass point cloud. In this paper, the space of the point cloud is firstly divided by the KD-tree idea. On this basis, the octree is used for further segmentation to establish an octree-like index structure. Then the point cloud dataset is spatially encoded using the improved encoding to achieve better spatial management and neighborhood search. Finally, using five groups of incremented point cloud set as test data, the experimental results and comparison analysis show that the octree-like space can make the overall structure of the data organization more reasonable, effectively improve the access efficiency and reduce the occupancy of memory space. The index structure not only improves the speed of the traditional KD-tree construction index but also improves the problem that the traditional octree is too large for space occupation and the neighborhood search takes too long. It achieves reasonable management of massive point cloud space.
previous article Microarray Filtering-Based Fuzzy C-Means Clustering and Classification in Genomic Signal Processing
next article An Empirical Study on Using Class Stability as an Indicator of Class Similarity

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Yang, B.; Liang, F.; Huang, R.: Progress, challenges and perspectives of 3D LiDAR point cloud processing. Acta Geod. Cartogr. Sin. 46(10), 1509–1516 (2017)
2.
He, Y.; Zheng, Y.; Pan, H.; et al.: Real three-dimensional modeling and application of complex construction based on the point cloud data. Remote Sens. Technol. Appl. 31(6), 1091–1099 (2016)
3.
Chen, H.; Li, X.; Li, C.: Application of terrestrial 3D laser scanning technology in deformation monitoring. Bull. Surv. Mapp. 12, 74–77 (2014)
4.
Zhang, J.; Lin, X.; Liang, X.: Advances and prospects of information extraction from point clouds. Acta Geod. Cartogr. Sin. 46(10), 1460–1469 (2017)
5.
Akdogan, A.; Demiryurek, U.; Banaeikashani, F., et al.: Voronoi-based geospatial query processing with mapreduce. In: IEEE Second International Conference on Cloud Computing Technology and Science, pp. 9–16. IEEE Computer Society (2010)
6.
Wang, J.; Wu, S.; Gao, H., et al.: Indexing multi-dimensional data in a cloud system. In: ACM SIGMOD International Conference on Management of Data, pp. 591–602. ACM (2010)
7.
8.
Zhao, J.; Wang, J.; Wang, Y.; et al.: A new multilevel spatial index of scattered point cloud data. Geo Inf. Sci. 17(12), 1450–1455 (2015)
9.
Finkel, R.A.; Bentley, J.L.: Quad trees a data structure for retrieval on composite keys. Acta Inf. 4(1), 1–9 (1974)CrossRefMATH
10.
Jackins, C.L.; Tanimoto, S.L.: Oct-trees and their use in representing three-dimensional objects. Comput. Graph. Image Process. 14(3), 249–270 (1980)CrossRef
11.
12.
Garrett, W.F.; Fuchs, H.; Whitton, M.C., et al.: Real-time incremental visualization of dynamic ultrasound volumes using parallel BSP trees. In: Visualization ‘96. Proceedings, pp. 235–240. IEEE (1996)
13.
Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: ACM SIGMOD International Conference on Management of Data, pp. 47–57. ACM (1984)
14.
Sellis, T.K.; Roussopoulos, N.; Faloutsos, C.: The R+-tree: a dynamic index for multi-dimensional objects. In: International Conference on Very Large Data Bases, pp. 507–518. Morgan Kaufmann Publishers Inc. (1987)
15.
Beckmann, N.; Kriegel, H.; Schneider, R., et al.: The R*-tree: an efficient and robust access method for points and rattanglles. In: Proceedings of ACM SIGMOD Conference Atlantic City, NJ, pp. 322–331 (1990)
16.
Kamel, I.; Faloutsos, C.: Hilbert R-tree: an improved R-tree using fractals. In: International Conference on Very Large Data Bases, pp. 500–509. Morgan Kaufmann Publishers Inc. (1994)
17.
Hubbard, P.M.: Interactive collision detection. In: Proceedings of IEEE Symposium on Research Frontiers in Virtual Reality, pp. 24–31 (1993)
18.
Zachmann, G.: Real-time and exact collision detection for interactive virtual prototyping. In: Proceeding of DETC’ 97, California, pp. 90–97. ASME (1997)
19.
Gottschalk, S.; Lin, M.C.; Manocha, D.: OBB-tree a hierarchical structure for rapid interference detection. In: Proceeding of SIGGRAPH’ 96, pp. 171–180. ACM Press, New York (1996)
20.
Klosowski, J.T.; Held, M.; Mitchell, J.S.B.; et al.: Efficient collision detection using bounding volume hierarchies of k-DOPs. IEEE Trans. Vis. Comput. Graph. 4(1), 21–36 (1988)CrossRef
21.
Andrew, A.M.: Another efficient algorithm for convex hulls in two dimensions. Inf. Process. Lett. 9(5), 216–219 (1979)CrossRefMATH
22.
Guttman, A.: R-trees: a dynamic index structure for spatial searching. In: ACM SIGMOD International Conference on Management of Data, pp. 47–57. ACM (1984)
23.
Matsuyama, T.; Hao, L.V.; Nagao, M.: A file organization for geographic information systems based on spatial proximity. Comput. Vis. Graph. Image Process. 23(2), 303–318 (1983)CrossRef
24.
Robinson, J.T.: A search structure for large multidimensional dynamic indexes. In: Proceeding of ACM Sigmod, pp. 10–18 (1981)
25.
Yu, F.; Chen, C.; Wang, L.: Multi-scale visualization and effective management of massive laser point cloud data. Geotech. Investig. Surv. 44(9), 69–73 (2016)
26.
Gong, J.; Ke, S.; Zhu, Q.; et al.: An efficient management method for point cloud data based on octree and 3D R-tree. Acta Geod. Cartogr. Sin. 41(4), 597–604 (2012)
27.
Zhao, E.; Liu, W.; Dang, H.: Data compression and spatial indexing technology for massive 3D point cloud. J. Comput. Appl. 38(1), 146–151 (2018)
28.
Chen, M.; Wan, Y.; Tian, S.; et al.: A method of organizing point clouds based on linear KD tree. Bull. Surv. Mapp. 1, 23–27 (2016)
29.
Cai, Z.; Wang, Y.; Huang, M.: Gauss mean curvature reduction algorithm based on KD tree scattered point cloud data. Bull. Surv. Mapp. S1, 44–46 (2013)
30.
Yu, J.; Wu, L.: Adaptive sphere degenerated octree grid and its encoding method. Geogr. Geo Inf. Sci. 28(1), 14–18 (2012)
31.
Aha, D.W.; Muñoz-Avila, H.: Interactive k–d tree GPU raytracing. In: Symposium on Interactive 3D Graphics and Games, pp. 167–174. ACM (2007)
32.
Hunter, G.M.; Steiglitz, K.: Linear transformation of pictures represented by quad trees. Comput. Graph. Image Process. 10(3), 289–296 (1979)CrossRef
33.
Lin, B.I.; Zhao, H.; Jia, M.T.: Database-oriented storage based on LMDB and linear octree for massive block model. Trans. Nonferrous Metals Soc. China 26(9), 2462–2468 (2016)CrossRef
34.
Sundar, H.; Sampath, R.S.; Biros, G.: Bottom-up construction and 2:1 balance refinement of linear octrees in parallel. SIAM J. Sci. Comput. 30(5), 2675–2708 (2008)MathSciNetCrossRefMATH
35.
Huang, C.-Y.; Chung, K.-L.: Manipulating images by using Run-length Morton codes. Int. J. Pattern Recognit Artif Intell. 11(06), 889–907 (1997)CrossRef
Metadata
Title
Massive Point Cloud Space Management Method Based on Octree-Like Encoding
Authors
Bin Lu
Qiang Wang
A’Nan Li
Publication date
29-06-2019
Publisher
Springer Berlin Heidelberg
Published in
Arabian Journal for Science and Engineering / Issue 11/2019
Print ISSN: 2193-567X
Electronic ISSN: 2191-4281
DOI
https://doi.org/10.1007/s13369-019-03968-7

Other articles of this Issue 11/2019

Arabian Journal for Science and Engineering 11/2019 Go to the issue

Research Article - Computer Engineering and Computer Science

Prediction Using Cuckoo Search Optimized Echo State Network

Research Article - Computer Engineering and Computer Science

On Some Improved Versions of Whale Optimization Algorithm

Research Article - Computer Engineering and Computer Science

A New Heuristic Clustering Algorithm Based on RSU for Internet of Vehicles

Research Article - Computer Engineering and Computer Science

An Advanced DV-Hop Localization Algorithm for Random Mobile Nodes in Wireless Sensor Networks

Research Article - Computer Engineering and Computer Science

Bidirectional Encoder–Decoder Model for Arabic Named Entity Recognition

Research Article - Computer Engineering and Computer Science

Storage Node Allocation Methods for Erasure Code-based Cloud Storage Systems

Premium Partners

    Image Credits