METHOD AND SYSTEM FOR REAL TIME 3D-SPACE SEARCH AND POINT-CLOUD REGISTRATION USING A DIMENSION-SHUFFLE TRANSFORM

摘要

The current document is directed to a dimensional shuffle transform ("DST") that maps a 3D space to a one-dimensional space that preserves 3D neighborhoods within ID neighborhoods within a recursive hierarchical structure. The search for points in a 3D subspace is reduced, by the DST, to one or more searches in the transformed ID space. The search is performed by either recursive decomposition of the 3D space indexed by the transform into subspaces, exploiting the transformed space structure, or by direct indexing into the region of interest. The searches over the subspaces generated by recursive decomposition are independent from one another, providing many opportunities for a variety of parallel, DST enabled search methods. The DST provides a basis for fast and efficient compression of point clouds while avoiding construction and traversal of tree-like data structures.