A point cloud is a 3D data set collected by various sensors, such as light detection-and-ranging “LIDAR” sensors, depth cameras, and others. Point cloud registration iteratively aligns a new frame of a 3D data set with previous aligned frames, referred to as a “map.” In many applications, a sensor moves in a 3D space with six degrees of freedom and each new frame relates to a previous frame or to a set of aligned previous frames by a spatial transformation. The registration of a sequence of frames of 3D data set is a process that involves finding the rigid transformations, consisting of translations and rotations, that align the frames in a selected coordinate system.
Point cloud registration has a broad range of applications in areas including computer vision, simultaneous localization and mapping (“SLAM”), robotic move planning, autonomous driving, object recognition, medical imaging, magnetic resonance imaging, virtual and augmented reality, and 3D model construction in remote sensing. Many new applications have become possible, in recent years, due to rapid advances in sensing and computing technologies, as a result of which 3D-data-set registration is becoming an increasingly significant component within many scientific, technological, and commercial applications and fields.
Iterative Closest Point (“ICP”) and Iterative Closest Point (“GICP”) are widely adopted approaches for point-cloud registration. As suggested by its name, ICP depends on iterative searching of 3D spaces and, indeed, its performance is dominated by the cost of such searches. K-d trees and other tree-based approaches are used to search of closest points, and these tree-based approaches involve expensive tree traversals. Empirical testing has shown that it is unrealistic to perform real-time point-cloud registration with any known tree-based approaches to 3D-space searching.
A point cloud frame is generally compressed by sampling to reduce its cardinality prior to frame alignment in order to decrease processing costs. To ensure that the compression does not result in significant decrease in accuracy, many compression techniques are designed to remove any data points over a threshold number of data points from each 3D voxel of a selected size. Octree has been suggested and used for these compression techniques, which requires a storage space of a size proportional to the product of the ranges of the spatial coordinates in each of the three dimensions and which requires processing times proportional to the logarithm of the size of the octree for each point examined. The aligned point cloud frames, or map, produced by point-cloud registration is stored in a data repository. The data repository is incrementally built up along with the processing of each new frame, and, at the same time, needs to be searched for each point in each frame.
As is well understood by those familiar with science and technology, the computational efficiency of a method or subsystem within a computer system, measured by the number of instructions processed and the amount of memory used to carry out particular tasks, is directly related to thermodynamic efficiency of the computer system, and is a significant real-word, physical characteristic of electromechanical computing systems. The time efficiency of a method or subsystem within a computer system is directly related to the real-world performance of the physical computer system and is often a significant determinant of the practical utility of the computer system in real-world applications. As with any significant component of an application, technology, or system, researchers, designers, developers, manufacturers, and vendors continuously seek more efficient and faster 3D-data-set-registration methods and systems, and seek improved efficiencies in many other, related applications and problem domains.