Method and system for simultaneously registering multi-dimensional topographical points
First Claim
1. A method for registering a set of frames of 3-dimensional digital elevation model data points which include both ground points representing a 3-dimensional surface and obstruction points which represent an obstruction lying above the 3-dimensional surface and are positionally interspersed among the ground points, said method comprising the steps of:
- (a) extracting a ground surface shell from the set based on a plurality of ground points from which the obstruction points have been isolated;
(b) finding a plurality of pairs of corresponding closest points in overlapping frames of said ground surface shell such that a plurality of said pairs of said corresponding closest points are found for each one of a plurality of pairs of said overlapping frames;
(c) determining a plurality of 3-dimensional transformations based on said corresponding closest points found in step (a), each respective one of said transformations defining a 3-dimensional rotation and translation representing an alignment of a first frame and a second frame of a respective one of said overlapping pairs of frames, said transformations being determinable without reliance on ego motion information, and(d) substantially simultaneously registering all frames included in said plurality of pairs of said overlapping frames by performing a rigid transform according to a matrix in which all of said transformations are represented.
1 Assignment
0 Petitions
Accused Products
Abstract
A method for registering multi-dimensional topographical data points representing a multi-dimensional object, comprises: a) receiving a plurality of points representing a plurality of overlapping frames of a surface of the multi-dimensional object; b) finding for each point in a first frame a corresponding closest point in each of a plurality of subsequent frames; c) determining a rotation and translation transformation for each of the plurality of frames so that corresponding closest points are aligned; d) determining a cost for performing each rotation and translation transformation; and e) repeating steps b) through d) for additional frames to provide an optimum transformation.
49 Citations
19 Claims
-
1. A method for registering a set of frames of 3-dimensional digital elevation model data points which include both ground points representing a 3-dimensional surface and obstruction points which represent an obstruction lying above the 3-dimensional surface and are positionally interspersed among the ground points, said method comprising the steps of:
-
(a) extracting a ground surface shell from the set based on a plurality of ground points from which the obstruction points have been isolated; (b) finding a plurality of pairs of corresponding closest points in overlapping frames of said ground surface shell such that a plurality of said pairs of said corresponding closest points are found for each one of a plurality of pairs of said overlapping frames; (c) determining a plurality of 3-dimensional transformations based on said corresponding closest points found in step (a), each respective one of said transformations defining a 3-dimensional rotation and translation representing an alignment of a first frame and a second frame of a respective one of said overlapping pairs of frames, said transformations being determinable without reliance on ego motion information, and (d) substantially simultaneously registering all frames included in said plurality of pairs of said overlapping frames by performing a rigid transform according to a matrix in which all of said transformations are represented. - View Dependent Claims (2, 3, 4, 5, 6, 9, 10, 11, 12, 13, 14)
-
-
7. A system for registering a set of frames of 3-dimensional digital elevation model points which include both ground points representing a 3-dimensional surface and obstruction points which represent an obstruction lying above the 3-dimensional surface and are positionally interspersed among the ground points, said system comprising:
-
a ground finder for isolating the obstruction points from the ground points; a competitive filter for obtaining a ground surface shell from a plurality of ground points provided by said ground finder, said ground surface shell including a representation of each respective one of said frames; a registration engine coupled to said competitive filter for (i) finding a plurality of pairs of corresponding closest points in overlapping frames of said ground surface shell such that a plurality of said pairs of said corresponding closest points are found for each one of a plurality of pairs of said overlapping frames, and (ii) determining a plurality of 3-dimensional transformations based on said corresponding closest points;
each respective one of said transformations defining a 3-dimensional rotation and translation representing an alignment of a first frame and a second frame of a respective one of said overlapping pairs of frames, said transformations being determinable without reliance on ego motion information, anda transform engine coupled to said registration engine for substantially simultaneously registering all of said frames included in said plurality of pairs of said overlapping frames by performing a rigid transform according to a matrix in which all of said transformations are represented. - View Dependent Claims (15, 16, 17)
-
-
8. A computer readable medium comprising program instructions for:
-
(a) extracting a ground surface shell from the set based on a plurality of ground points from which the obstruction points have been isolated; (b) finding a plurality of pairs of corresponding closest points in overlapping frames of said ground surface shell such that a plurality of said pairs of said corresponding closest points are found for each one of a plurality of pairs of said overlapping frames; (c) determining a plurality of 3-dimensional transformations based on said corresponding closest points found in step (a), each respective one of said transformations defining a 3-dimensional rotation and translation representing an alignment of a first frame and a second frame of a respective one of said overlapping pairs of frames, said transformations being determinable without reliance on ego motion information, and (d) substantially simultaneously registering all frames included in said plurality of pairs of said overlapping frames by performing a rigid transform according to a matrix in which all of said transformations are represented. - View Dependent Claims (18, 19)
-
Specification