A FRAMEWORK FOR GENERIC SPATIAL SEARCH IN 3D POINT CLOUDS

Abstract. Modern data acquisition with active or passive photogrammetric imaging techniques generally results in 3D point clouds. Depending on the acquisition or processing method, the spacing of the individual points is either uniform or irregular. In the latter case, the neighbourhood definition like for digital images (4- or 8-neighbourhood, etc.) cannot be applied. Instead, analysis requires a local point neighbourhood. The local point neighbourhood with conventional k-nearest neighbour or fixed distance searches often produce sub-optimal results suffering from the inhomogeneous point distribution. In this article, we generalize the neighbourhood definition and present a generic spatial search framework which explicitly deals with arbitrary point patterns and aims at optimizing local point selection for specific processing tasks like interpolation, surface normal estimation and point feature extraction, spatial segmentation, and such like. The framework provides atomic 2D and 3D search strategies, (i) k-nearest neighbour, (ii) region query, (iii) cell based selection, and (iv) quadrant/octant based selection. It allows to freely combine the individual strategies to form complex, conditional search queries as well as specifically tailored point sub-selection. The benefits of such a comprehensive neighbourhood search approach are showcased for feature extraction and surface interpolation of irregularly distributed points.