An nD-histogram technique for querying non-uniformly distributed point cloud data

Journal Article (2025)
Author(s)

Haicheng Liu (China South-to-North Water Diversion Group Water Networks Intelligent Technology Co., Ltd.)

Zhiwei Li (China South-to-North Water Diversion Group Water Networks Intelligent Technology Co., Ltd.)

Peter van Oosterom (TU Delft - Digital Technologies)

B.M. Meijers (TU Delft - Digital Technologies)

Chuqi Zhang (China South-to-North Water Diversion Group Water Networks Intelligent Technology Co., Ltd.)

Research Group
Digital Technologies
DOI related publication
https://doi.org/10.1016/j.isprsjprs.2025.03.014
More Info
expand_more
Publication Year
2025
Language
English
Research Group
Digital Technologies
Bibliographical Note
Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project https://www.openaccess.nl/en/you-share-we-take-care Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.@en
Volume number
224
Pages (from-to)
1-18
Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Abstract

Point cloud data contains abundant information besides XYZ, such as Level of Importance (LoI) and intensity. These non-spatial dimensions are also frequently used and queried. Therefore, developing an efficient nD solution for managing and querying point clouds is imperative. Previous researchers have developed PlainSFC that maps both nD points and queries into a one-dimensional Space Filling Curve (SFC) space and uses B+-tree for indexing. However, when computing SFC ranges for selection, PlainSFC subdivides the nD space mechanically to approach the query window without considering the point distribution. Then, excessive ranges are generated in vacant areas, and ranges generated in dense point areas are coarse. Consequently, a large number of false positives are selected, slowing down the whole querying process. This paper develops a new solution called HistSFC to resolve the issue. HistSFC builds an nD-histogram which records point data distribution, and uses it to compute ranges for selecting data. Also, this paper discovers a novel statistical metric, Cumulative Hypercubic Coverage (CHC), to measure the uniformity of the point cloud data. Theory is established and it indicates that the nD-histogram is more beneficial when CHC is smaller. Thus, CHC can be used to guide the building of HistSFC. In addition, the paper conducts simulations and benchmark tests to examine the improvement on PlainSFC. It turns out that using the nD-histogram can decrease the false positive rate by orders of magnitude. HistSFC is also evaluated against state-of-the-art solutions. The result shows that HistSFC leads the performance in nearly all the tests.

Files

License info not available
warning

File under embargo until 28-09-2025