CN110945499A - Method and system for real-time three-dimensional space search and point cloud registration by using dimension shuffle transformation - Google Patents

Abstract

This document relates to a Dimension Shuffle Transform (DST) that maps a three-dimensional space to a one-dimensional space and preserves three-dimensional neighbor relationships among one-dimensional neighbor relationships in a recursive hierarchy. The search for points in the three-dimensional subspace is translated into one or more searches in the transformed one-dimensional space by DST. The search is performed by recursively decomposing the three-dimensional space indexed by the transformation into subspaces, using the transformed spatial structure, or by directly indexing to the region of interest. The search of the subspaces resulting from the recursive decomposition is completely independent of each other, providing many opportunities for various parallel DST-based search methods. DST provides a basis for fast and efficient point cloud compression, while avoiding the construction and traversal of tree-form data structures.

Description

Method and system for real-time three-dimensional space search and point cloud registration by using dimension shuffle transformation

CROSS-REFERENCE TO RELATED APPLICATIONS

The present disclosure claims the benefit of provisional application No. 62/478,422 filed on 29/3/2017.

Technical Field

The present disclosure relates to computational transformations, searches, data sampling, and other operations that can achieve significant computation and thermodynamic efficiencies in a number of problem domains, including point cloud registration.

Background

The point cloud is a three-dimensional dataset collected by various sensors, such as laser detection and ranging "LiDAR" sensors, Depth cameras (Depth cameras), or other devices. Point cloud registration (Point cloud registration) iteratively aligns new frames of a three-dimensional dataset with previously aligned frames, also known as "Map" registration. In many application scenarios, the sensor is moved in six degrees of freedom in three-dimensional space, and each new frame is associated by a spatial transformation with a previous frame or with a set of previously aligned frames. Registration of a series of frames of a three-dimensional data set is a process of finding a rigid transformation, which includes displacement and rotation and is used to align the frames in a selected coordinate system.

Point cloud registration has wide applications in many areas, including computer vision, Simultaneous Localization and Mapping ("SLAM"), robotic action planning, autopilot, object recognition, medical imaging, magnetic resonance imaging, virtual and augmented reality, and remote sensing three-dimensional modeling. In recent years, due to the rapid development of sensing and computing technologies, many new applications have become possible, which makes three-dimensional dataset registration an increasingly important component in many scientific, technical, commercial applications and fields.

Iterative Closest Point ("ICP") and Iterative Closest Point ("GICP") are methods that are widely used for Point cloud registration. As the name implies, ICP relies on an iterative search of three dimensions, and therefore in practice its performance is largely determined by the cost of the search. K-d tree and other tree based methods are used to search for the closest point and these tree based methods involve expensive tree traversal. Experimental tests have shown that it is impractical to perform real-time point cloud registration by performing a three-dimensional space search using any known tree-based method.

Point cloud frames are typically compressed by sampling to reduce their cardinality (cardinality) before the frames are aligned, thereby reducing processing costs. To ensure that compression does not result in a significant reduction in accuracy, many compression techniques are designed to remove any data points from each three-dimensional voxel of a selected size that exceed the threshold data point number. Octree (Octree) has been proposed to implement these compression techniques, which require that the size of the storage space be proportional to the product of the spatial coordinate ranges of each of the three dimensions, and that the processing time be proportional to the logarithm of the size of the Octree for each point examined. The aligned point cloud frames or maps generated by the point cloud registration are stored in a database. The database is built up as each new frame is processed and at the same time needs to be searched for each point in each frame.

As is well known to those skilled in the art of science, the computational efficiency of a method or subsystem in a computer system can be measured in terms of the number of instructions processed and the size of the memory used to perform a particular task, and directly impacts the thermodynamic efficiency of the computer system and is an important realistic physical property of an electromechanical computing system. The time efficiency of a method or subsystem in a computer system is directly related to the actual performance of the physical computer system and is often an important determinant of the utility of the computer system in practical applications. As with any important component of an application, technique, or system, researchers, designers, developers, manufacturers, and vendors are continually seeking more efficient and faster three-dimensional dataset registration methods and systems, and improved efficiencies in many other related applications and problem areas.

Disclosure of Invention

This document relates to a Dimension Shuffle Transform (DST) that maps a three-Dimensional space to a one-Dimensional space and preserves three-Dimensional neighbor relationships among one-Dimensional neighbor relationships in a recursive hierarchy. The search for points in the three-dimensional subspace is translated into one or more searches in the transformed one-dimensional space by DST. The search is performed by recursively decomposing the three-dimensional space indexed by the transformation into subspaces, using the transformed spatial structure, or by directly indexing to the region of interest. Theoretical analysis and experimental testing have demonstrated that this method of searching three-dimensional space using DST transforms is more time and space efficient and provides better performance in terms of Recall (Recall) and precision than the K-d, octree, and many variations thereof, currently used. Furthermore, the search of the subspaces resulting from the recursive decomposition is completely independent of each other, providing many opportunities for various parallel DST-based search methods. DST provides a basis for fast and efficient point cloud compression, while avoiding the construction and traversal of tree-form data structures.

Drawings

FIG. 1 provides a general architecture diagram for various types of computers.

Fig. 2 shows a DST transform.

Fig. 3 shows the inverse DST transform H using the same diagrammatic convention previously used in fig. 1^-1。

Fig. 4 shows a DST mapping between 64 points in three-dimensional space and their corresponding k coordinates in the corresponding linear DST transform space.

Fig. 5 shows the meaning of seven different possible modes returned by the method Pat.

Fig. 6 shows a spherical neighborhood R of radius R and its circumscribed cube with a side length of 2R.

FIG. 7 provides the current H and H basis^-1Illustration of the method of transformation.

Detailed Description

Computer system

FIG. 1 provides a general architecture diagram for various types of computers, including certain computer systems on which the point cloud registration system is implemented. The computer system includes one or more central processing units ("CPUs") 102, 105, one or more electronic memories 108 interconnected to the CPUs by one or more CPU/memory subsystem buses 110, a first Bridge 112 interconnecting the CPU/memory subsystem buses 110 to additional buses 114 and 116, or other types of high-speed interconnection media, including multiple high-speed serial interconnections. These buses or serial interconnects, in turn, connect the CPU and memory to a dedicated processor, such as graphics processor 118, and to one or more additional bridges 120, where the additional bridges 120 are interconnected to a high speed serial link or to multiple controllers 122 and 127, such as to the controller 127, where the multiple controllers 122 and 127 provide access to various different types of large memory devices 128, electronic displays, input devices, and other elements, sub-elements, and computing resources. The computer systems and advanced systems implemented thereon are physical electromechanical systems that consume energy and transform the physical state of many of the subcomponents connected thereto and external systems. The computer system is controlled by computer instructions stored in the physical data storage device. The computer instructions themselves are also physical entities. Otherwise, they cannot be stored and retrieved from the data storage device.

Symbolic convention and basic objects and operations

Discrete three-dimensional space (D)³) May be represented by a set of three coordinates (z, y, X), where z, y, X are integers and are referred to as the coordinates of point p on the Z, Y and X axes of the three-dimensional space, respectively. A point in one-dimensional space is represented by a single coordinate k along a unique axis of the one-dimensional space. Unless otherwise specified, the distance of the space is assumed to be a euclidean metric, although some of the following discussion is valid for other distance metrics, such as the manhattan distance metric.

Let p₁＝(z₁,y₁,x₁) And p₂＝(z₂,y₂,x₂) Is D³Two points in (1). These two points define the regular region R (p) of the cubic shape₁,p₂)：

R(p₁,p₂)＝{p＝(z,y,x)|min(z₁,z₂)≤z≤max(z₁,z₂)；

min(y₁,y₂)≤y≤max(y₁,y₂)；

min(x₁,x₂)≤x≤max(x₁,x₂)}

Note that condition z₁≠z₂、y₁≠y₂And x₁≠x₂Are assumed to prevent that the cube may degenerate into planes, lines or points. Region r¹The requirements for being a sub-region of region r are:

some operations on binary and integer numbers are as follows:

b (x): returning the binary number of the integer x

B^-1(b) The method comprises the following steps If and only if b (x) is b, return x,

get (x, j): returning the jth bit of b (x),

set (x, j, c): the jth bit of b (x) is set to binary bit c and the corresponding integer is returned.

The symbols |, & AND ^ are used to represent Bitwise (Bitwise) AND (AND), OR (OR) AND Exclusive OR (Exclusive OR) operations on two unsigned integers, respectively, while ^ represents the Bitwise complement of the unsigned integer; m and > m denote left and right shifting of an unsigned integer by m bit positions, respectively.

DST transform

The Dimension Shuffle Transform (DST) being from a three-dimensional space D³To a one-dimensional space D¹Where w is the width in bits of the three-dimensional coordinate along the three-dimensional dimension:

given D³The DST transform k ═ h (p) for the point p is also referred to as the key (key) for the point p.

Fig. 2 shows a DST transform. As shown in fig. 2, in the bit array 202 of 12 bits, the three-dimensional coordinates of the point p are each encoded in 4-bit nibbles (nibbles). The bits representing each coordinate are arranged in order of importance from right to left with the least significant bit of the coordinate representation being located at the right end of the nibble. For example, the least significant bit 204 of the nibble 206 representing the x-coordinate is located at the rightmost end of the nibble. The DST transform allocates bits of the three-dimensional coordinate onto a 12-bit representation 208 of the linear coordinate k, as indicated by arrows (e.g., arrow 210) in fig. 2. The 12-bit representation 208 of the linear coordinate k can be seen as a sequence of four three-bit blocks, where each three-bit block comprises ordered triplet bits of particular importance extracted from the corresponding three-dimensional coordinate. The volume of the three-dimensional space includes the number of points of the cube equal to the number of different coordinate values, which can be represented by the number of bits used to represent the three-dimensional coordinates. In the example shown in FIG. 2, each nibble is capable of representing 16 different values, so the three-dimensional space contains 16³4096 points. The number of points in the one-dimensional transformation space is equal to the number of k coordinate values, which can be represented by the number of bits used to represent the one-dimensional coordinates. In the example shown in fig. 2, 12 bits can represent 2¹²4096 points. As the coordinate value v increases, the position of the leftmost bit having a value of 1 increases stepwise in proportion to the base-2 logarithm of v. For this reason, allocating three-dimensional coordinate bits on the k-coordinate representation tends to produce a larger k-coordinate value as the three-dimensional coordinate value increases, because the 1-value bit of the larger three-dimensional coordinate is located further to the left of the nibble representing the three-dimensional coordinate, which 1-value bit is finally located by the DST transform to be further to the left of the k-coordinate representation.

The DST transform H is a double mapping, and therefore, there is an inverse transform H as follows^-1：

The result is returned as a concatenation of the binary form of the three-dimensional coordinates (x, y, z).

Fig. 3 shows the inverse DST transform H using the same diagrammatic convention previously used in fig. 1^-1. As shown in FIG. 3, the three-dimensional coordinate bits allocated on the 12-bit representation 302 of the linear coordinate k are collected back into their respective coordinates representing nibbles in the 4-bit nibble representation of the concatenated three-dimensional coordinate 304. Obviously, the inverse or inverse DST transform H^-1The inverse transformation to that performed by the forward DST transformation H is performed because the only difference between the diagrams shown in fig. 2 and 3 is the direction of the crop representing the corresponding positions of the bits in the linear coordinates k and the bits in the three-dimensional coordinates.

The DST transform has a property of retaining a neighborhood relationship, that is, points adjacent to each other in a three-dimensional space also tend to be adjacent to each other in the transformed space. The DST transform also imposes an implicit hierarchical structure in three-dimensional space, where a first cube with a side length of 2a is divided into 8 sub-cubes with a side length of a. The partitioning may be performed recursively on the subcubes and the subcubes of the subcubes until the number of points along each subcube edge is less than 4. Then, the assertion that DST is a transformation that preserves neighbor relations may be formally judged by the fact that, in this hierarchy, for two integer keys s and t, the DST key for all points in a cube or subcube always forms a set of linear keys [ s, t ] - { k | s ≧ k ≧ t }, which will be referred to as the lower front corner (lower front corner) and the upper corner (upper corner) of the cube or subcube, respectively, with monotonically increasing values.

Fig. 4 shows a DST mapping between 64 points in three-dimensional space and their corresponding k coordinates in the corresponding linear DST transform space. Each point, such as point 402, is labeled with its three-dimensional coordinates (z, y, x) and its corresponding DST transform space k-coordinates or keys, shown in FIG. 4 as

The entire cubic space 404 shown in FIG. 4 includes all points having three-dimensional coordinates, each of which may be represented by two bits. The entire space is contained in a cube with a lower left corner point 406 and an upper right corner point 408, where the three-dimensional/one-dimensional coordinates of the lower left corner point 406 are (0, 0, 0)/0, respectively, and the three-dimensional/one-dimensional coordinates of the upper right corner point 408 are (3, 3, 3)/63, respectively. There are other smaller cubes for which the linear coordinates of the points form a monotonically increasing subset of the linear coordinate axes, for example, the lower left cube 410 includes points with three-dimensional coordinates (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1) and corresponding linear coordinates 0, 1, 2, 3, 4, 5, 6, 7. If a space includes all points whose respective three-dimensional coordinates can be represented using three bits, a cube representing the space will include 512 points, whereas if a space includes all points whose respective three-dimensional coordinates can be represented using four bits, a cube representing the space will include 4096 points.

Region and its Properties

Given two keys k and k¹Defined by these two keys, is denoted as<k₁,k₂>Is given by: { { z, y, x) | min (x)₁,x₂)≤x≤max(x₁,x₂),min(y₁,y₂)≤y≤max(y₁,y₂),min(z₁,z₂)≤max(z₁,z₂) Wherein (z)₁,y₁,x₁)＝H^-1(k₁)，(z₂,y₂,x₂)＝H^-1(k₂). Defined by these two keys, on the other hand, is denoted by k₁,k₂]The linear region of (a) is given by: { (z, y, x) | k₁≤H(z,y,x)≤k₂}. As can be seen,

this is always true. By two keys(k₁,k₂) Precision of the defined region is<k₁,k₂>|/|[k₁,k₂]Where | S | represents the cardinality of the set S. Therefore, the accuracy of the region is always less than or equal to 1. A region with a precision of 1 is called a perfect region, and a region with a precision of 1 and each side length along all dimensions equal to each other is called a perfect cube.

The DST level (level) is a fundamental property of a region, and in other applications, is used during region decomposition operations to determine a partition plane. It is calculated by the following method "Lvl":

given two keys k₁And k₂Then Lvl (k)₁,k₂) Computing regular regions<k₁,k₂>The hierarchy of (a). In the code shown above, w is the width in bits of the binary form of each three-dimensional coordinate. The routine Lvl divides the binary bits in k into consecutive three-bit blocks and then finds the index of the three-bit block containing the leftmost bit of k with a value of 1, where these bits represent the three-dimensional coordinates corresponding to the different keys k₁And k₂One or more most significant bits of (a).

A non-perfect region whose volume is larger than the smallest possible volume of the region can be decomposed into sub-regions with higher precision (if not perfect). The decomposition is performed in a manner that maximizes accuracy. The following method Pat is an ancillary method used in determining the optimal decomposition:

given two keys k₁And k₂And<k₁,k₂>pre-computation hierarchy ofThen Pat (k)₁,k₂) A pattern of the defined region is computed, which is then used in the region decomposition. The pattern is an integer whose value lies in the range 1, …, 7. The pattern is in its binary form (b)₂，b₂，b₁) Indicating the split axis in the decomposition. The regular region has three sets of parallel edges, each set of edges being parallel to a different coordinate axis. Intuitively, the three bits representing the mode returned by the routine Pat indicate the area<k₁,k₂>Has a maximum length of the set of parallel edges. When there is only one such set of edges, the region is decomposed by dividing the region by a plane perpendicular to the edges in that set. When there are two such sets of edges, the region is decomposed by dividing the region by two planes perpendicular to those two sets of edges having the largest length and parallel to a third set of edges having a length shorter than the lengths of the edges in those two sets of edges. When there are three such sets of edges, the region is decomposed by dividing the region by three mutually perpendicular planes, each of which is parallel to a different coordinate axis.

Fig. 5 shows the meaning of seven different possible modes returned by the method Pat. Mode 001(501) indicates division by a plane perpendicular to the X axis. The mode 010(502) indicates division by a plane perpendicular to the Y axis. The pattern 001(503) indicates division by a plane perpendicular to the Z axis. Mode 011(504) indicates a division by two planes, where the first of the two planes is perpendicular to the X-axis and the second is perpendicular to the Y-axis. Mode 101(505) indicates a division by two planes, where the first of the two planes is perpendicular to the X-axis and the second plane is perpendicular to the Z-axis. The mode 110(506) indication is divided by two planes, where a first plane of the two planes is perpendicular to the Y axis and a second plane is perpendicular to the Z axis. The pattern 111(507) indicates division by three mutually perpendicular planes, each of which is perpendicular to a different coordinate axis from the coordinate axes to which the other two planes are perpendicular. Of these seven decompositions, three are binary decompositions, three are quaternary decompositions, and one is an eight-ary decomposition.

Decomposition of

Given a particular level, two secondary methods are used to identify the corner where the point is located in the perfect region. To align the regions along the axis<p₁,p₂>For the division, two additional points are calculated

And

to satisfy it

It is easy to conclude from this that,

must have an and in all axes except the decomposition axis₂The same coordinates. In a similar manner to that described above,

with p only in the decomposition axis₁Different. Given a point's key and hierarchy, the following method LowerFt calculates the lower front corner of the perfect cube to which the point belongs at a given hierarchy. The method LowerFt sets the bit value of each of the least significant 3 x L bits in the key to 0.

Given the key and hierarchy of a point, the method UpperBack calculates the upper back angle of the perfect cube to which the point belongs at a given hierarchy:

given three keys k₁、k₂And k₃Then, using predefined bitmasks XMask ═ (001001 … 001), YMask ═ 010010 … 010), and ZMask ═ 100100 … 100, practical method C below returns a cascaded three-dimensional of pointsCoordinates where the x coordinate of the cascaded three-dimensional coordinates corresponds to k₁Has the same x coordinate as the three-dimensional point of (1), and has the same y coordinate as the x coordinate corresponding to k₂Has the same y-coordinate and its z-coordinate corresponds to k₃The z-coordinates of the three-dimensional points of (a) are the same:

the m-ary decomposition of a given pattern P is denoted as

Are named pi respectively¹、Π²And pi³Can be applied to a region of a given level L<k₁,k₂>An m-ary decomposition is performed, with superscripts representing one of three binary patterns 001, 002, and 004, respectively. The method II¹As follows:

the above method performs a binary decomposition of the region along the X-axis. Similarly, the method constructed Π²And pi⁴Binary decomposition is performed along the Y-axis and Z-axis, respectively.

Method II³Region pair according to mode 011(504 in FIG. 5)<k₁,k₂>Performing quaternary decomposition:

method II⁵And pi⁶Can be constructed in a similar manner. For mode 111(507 in FIG. 5), method Π⁷An octal decomposition is performed along all axes:

given the region R, it is formed by two bonds k₁And k₂The defined non-perfect area is set according to the mode (k)₁,k₂) Decomposing the region to obtain m sub-regions

Setting:

s₁＝k₂-k₁+1, and

then s is easily certified₂<s₁It is always true. Thus, the accuracy of the imperfect area is always improved after the DST decomposition. Further, DST decomposition has the following properties: (1) as a whole, any maximum perfect area contained in this area is always contained in the sub-area and never decomposed; and (2) there is no other total linear magnitude less than s₂The same m-ary decomposition. In this sense, DST decomposition is optimal.

Area search

For a region<k₁,k₂>Is achieved by a method wherein k₁≤k₂In this method, the pattern of the region is first identified, and then the corresponding decomposition method is invoked:

assuming [ s, t ] is an arbitrary region and that the number p between 0 and 1 is the desired precision, where s ≦ t, the following method recursively decomposes the region into sub-regions with precision equal to or higher than p:

thus, searching for regions in three-dimensional space is a recursive process. The sub-regions are further decomposed if and only if the precision of the sub-regions has reached a predefined value. There are other ways to control the recursion. One of these approaches relies on the concept of geometric dimensions. Given a regular region<s,t>And its longest edge l along all dimensions, then the geometric hierarchy of the regular region is [ log ]₂(l)]. It is easy to verify that for a perfect cube at any level, the geometric level and DST level are equal and, more generally, for any region, the former is always less than or equal to the latter. The difference between these two levels of a region can therefore be used to indicate how close the region is to a perfect cube, and so it can be in method Π^RInstead of the precision p. Method Π no matter how the precision value or level difference is selected^RResults with 100% recall (recall) are always produced. The freedom to set different termination thresholds for the recursive divide-and-conquer process allows a trade-off between accuracy and computational speed, which is easily exploited.

Neighborhood inspection (Neighborwood Examination)

Fig. 6 shows a spherical neighborhood R of radius R and its circumscribed cube with a side length of 2R. Let S be (p)_n-1,…,p₀) Is a set of points in three-dimensional space, then q is (z)_q,y_q,x_q) The spherical neighborhood of radius r, which is the reference point, is the set of:

Nbr_s(S,q,r)＝{p|p∈S,Dist(p,q)≤r}

on the other hand, the Cubic Neighborhood (Cubic neighbor) in the same space with q as the reference point is:

Nbr_c(S,q,r){p|p＝(z_p,y_p,x_p)∈S,z_p-z_q≤r|y_p-y_q|≤r|x_p-x_q|≤r}

given a region R in space, a set U of points in the region R, and a set V of points returned by the search, the recall rate of the search is:

and the precision of the search is:

these two metrics are used to evaluate the performance of the search in terms of completeness and accuracy, respectively.

A neighborhood check on a three-dimensional data set S starts with a DST transform H that maps each point p in S into a one-dimensional space and places the whole of these transforms into a repository (Repo) Repo that supports both Put (Repo, k) and Get (Repo, S, t) operations. The former of the two operations places a one-dimensional key in Repo, while the latter returns all points where the key falls between s and t. In alternative implementations, a variety of different types of stack libraries may be employed, including specific in-memory data structures, data structures that use both memory and large data storage devices, and database management systems. Method Φ maps the set of points using transform H, and stores the result in Repo, where w is the width of the binary form of the coordinates along each dimension of the three-dimensional space:

the following method NBR _ c pairs the neighborhood Nbr_c(S, q, r) are calculated, wherein the recall rate is 1 and the precision p is between 0 and 1, which can be selected by the user as appropriate according to the application scenario, wherein the operation Put (Repo, k) stores the point p with the key k ═ h (p) in Repo, and the operation Get (Repo, S, t) returns that the key falls in the closed set [ S, t ]]All points within:

in the above method, S ═ { p ═ p_n-1,…,p₀Is the set of points in three-dimensional space, q is the reference point, r is the radius of the neighborhood, and ρ is the method Π. Parameter cubic? Is a boolean parameter that indicates whether the desired neighborhood is a cube or sphere.

The recall rate was 100% for both cube and sphere neighborhood checks. In other words, any point in the region will appear in the result. The accuracy of the cube neighborhood is controlled by a parameter p, which can be any desired value between 0 and 1. Assuming that the points in space are evenly distributed, the sphere neighborhood can be approximated by circumscribing the cube neighborhood, if desired, which provides the desired accuracy of 52.3598%.

On many problems, it is often desirable to find the k nearest neighbors to a given point, especially for the case where k is 1. Method Nbr_kThe method NBR _ c is used to determine the nearest k neighbors to a given point q in space S:

for small neighborhoods, Result is typically a small set, so the cost of sorting is typically low. An alternative approach to sorting is to save the Result structure as an Ordered List (Ordered List). Then the nearest k neighbors can be found immediately without further sorting.

The neighborhood checking in three-dimensional space is mostly performed directly on this space using a method denoted as Ψ, where the method Ψ is typically based on a K-d tree. The method here differs from the conventional method in that it uses a transformation denoted H to transform this problem into a problem in the one-dimensional spatial domain with specific properties.Neighborhood checking is then performed in the transformed domain using the Π method. The result is then via H^-1(i.e., the inverse of Φ) is converted back into the three-dimensional domain. Expressed in terms of a function symbol, the method in this embodiment can be briefly summarized as Ψ ═ H^-1Π · H. FIG. 7 provides the current H and H basis^-1Illustration of the method of transformation.

Finally, a search method is provided which searches for one or more nearest neighbors of a point by searching for a perfect cube of a certain level to which the point p belongs:

assume that the DST level of a perfect cube calculated from the desired diameter is L_cThen the method ensures that the level to which the point p belongs is L_cAll points in the perfect cube of (1) are searched. Although a search in a perfect cube has a recall of 100%, it is possible that some points closer to point p than the points in the result are not included in the result. This may occur when the position of point p is near an edge or corner of the cube. The effect of this error on the final mapping accuracy is often practically imperceptible.

Point cloud sampling

The purpose of point cloud sampling is to reduce the cardinality of the data set. This process is typically applied to each new data frame to reduce computational cost. The existing method comprises the following steps: (1) removing every kth point from the input for some ordering of data points; and (2) filtering out all but one point in each octree unit using octrees.

The space may be scaled to preserve a level L in the space after the DST transform_s0 or 1 point per perfect cube. The following point cloud sampling method achieves this compression:

the sub-region defined by keys s and t is always a perfect cube; therefore, the process never involves region decomposition. In practice, this is equivalent to sampling through an octree in terms of segmentation. The difference is that the above approach does not require construction of octrees nor any tree traversal. Both of the above methods, although developed for different purposes, search in a perfect cube at a certain level. Point clouds with negative and/or fractional coordinates can always be shifted and scaled so that all coordinates are positive integers before applying the various methods disclosed presently.

The point cloud sampling methods discussed above have improved by orders of magnitude in the computational efficiency of point cloud registration systems. As discussed previously, this represents a tremendous improvement in these types of computing systems from the point of view of energy consumption, storage resource consumption, and real-time performance, pushing point cloud registration from the prototypes and research areas into the field of practical, commercially viable systems that underlie autonomous vehicles and other such practical applications. As fourier transforms are used throughout the scientific arts, DST transforms along with the decomposition methods discussed above can also be advantageously applied in problem domains ranging from image and signal processing to quantum mechanics and molecular structure determination.

Claims (8)

1. A system for transforming a first data set, stored in a physical data storage device or data storage and comprising a digital representation of a three-dimensional point, into a corresponding second data set, stored in the same data storage device or data storage as the data storage device or data storage storing the first data set or in a different physical data storage device or data storage and comprising a digital representation of a corresponding one-dimensional point, the system comprising:

one or more processors;

one or more memories;

one or more data storage devices; and

computer instructions stored in one or more of the one or more memories and the one or more data storage devices that, when executed by one or more of the one or more processors, control the system to perform the steps of:

retrieving a digital representation of each three-dimensional point from the first data set,

for each three-dimensional point, for each digital representation of each three-dimensional coordinate value of the three-dimensional point, for each bit in the digital representation of the three-dimensional coordinate value, generating a corresponding one-dimensional point digital representation,

setting a value of a corresponding bit in the digital representation of the corresponding one-dimensional point to a value of a bit in the digital representation of the three-dimensional coordinate value, an

Storing a digital representation of a one-dimensional point in said second data set, an

Wherein bits in the digital representation of the one-dimensional point that correspond to bits in the digital representation of the three-dimensional coordinate value in the digital representation of the corresponding three-dimensional point are not adjacent to each other in the digital representation of the one-dimensional point.

2. The system of claim 1, wherein the three-dimensional points in the first data set are located in a three-dimensional space represented by a cube having three mutually perpendicular edges that meet at a single point, the three edges representing three cartesian coordinate axes, the number of points along each coordinate axis being equal to the base-2 logarithm of the number of consecutive bits of the three-dimensional coordinate values in the digital representation of the three-dimensional coordinate values used to represent the three-dimensional point.

3. The system of claim 2, wherein three-dimensional points in the cube can be recursively divided into subcubes, each subcube corresponding to a sequence of one-dimensional points in the second data set having monotonically increasing one-dimensional coordinate values.

4. The system of claim 1, wherein each digital representation of three-dimensional coordinate values of the digital representation of a three-dimensional point comprises an ordered set of indices of 0, 1, and 2 of a three-coordinate value bit block;

wherein each coordinate value bit block is an n-bit ordered set having indices of 0, …, n-1, and

wherein the digital representation of the one-dimensional point of each three-dimensional point comprises an ordered set of n three-bit blocks, with indices of 0, …, n-1;

wherein each three-bit block is a three-bit ordered set having indices of 0, 1, and 2;

wherein the bit at index i in the block of bits j of the coordinate value in the digital representation of the three-dimensional point corresponds to the bit with index j in the block of three bits at index i in the digital representation of the corresponding one-dimensional point.

5. A system for transforming a first data set, stored in a physical data storage device or data storage and comprising a digital representation of a one-dimensional point, into a corresponding second data set, stored in the same data storage device or data storage as the data storage device or data storage storing the first data set or in a different physical data storage device or data storage and comprising a digital representation of a corresponding three-dimensional point, the system comprising:

one or more processors;

one or more memories;

one or more data storage devices; and

computer instructions stored in one or more of the one or more memories and the one or more data storage devices that, when executed by one or more of the one or more processors, control the system to perform the steps of:

taking a digital representation of each one-dimensional point from the first data set,

for each one-dimensional point, for each bit in the digital representation of the one-dimensional point, generating a corresponding three-dimensional point digital representation,

setting the value of the corresponding bit in the digital representation of the corresponding three-dimensional point to the value of the bit in the digital representation of the one-dimensional point, an

Storing a digital representation of a three-dimensional point in the second data set,

wherein two adjacent bits in the digital representation of the one-dimensional point are not adjacent to each other in the digital representation of the three-dimensional point.

6. The system of claim 5, wherein the three-dimensional points in the second data set lie in a three-dimensional space represented by a cube having three mutually perpendicular edges that meet at a single point, the three edges representing three Cartesian coordinate axes, the number of points along each coordinate axis being equal to the base-2 logarithm of the number of consecutive bits of the three-dimensional coordinate values in the digital representation of the three-dimensional coordinate values used to represent the three-dimensional point.

7. The system of claim 6, wherein three-dimensional points in the cube can be recursively divided into subcubes, each subcube corresponding to a sequence of one-dimensional points in the first data set having monotonically increasing one-dimensional coordinate values.

8. The system of claim 5, wherein each digital representation of three-dimensional coordinate values of the digital representation of a three-dimensional point comprises an ordered set of indices of 0, 1, and 2 of a three-coordinate value bit block;

wherein each coordinate value bit block is an n-bit ordered set having indices of 0, …, n-1, and

wherein the digital representation of the one-dimensional point of each three-dimensional point comprises an ordered set of n three-bit blocks, with indices of 0, …, n-1;

wherein each three-bit block is a three-bit ordered set having indices of 0, 1, and 2;

wherein the bit at index i in the block of bits j of the coordinate value in the digital representation of the three-dimensional point corresponds to the bit with index j in the block of three bits at index i in the digital representation of the corresponding one-dimensional point.

Images