Method and system for simultaneously registering multi-dimensional topographical points

• US 20060013443A1
• Filed: 07/15/2004
• Published: 01/19/2006
• Est. Priority Date: 07/15/2004
• Status: Active Grant

• Current Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Original Assignee: Harris Corporation (L3Harris Technologies, Inc.)
• Inventors: Rahmes, Mark, McDowall, Tom, Fermo, Ray, Auxier, Jake
• Granted Patent: US 7,567,731 B2
• Time in Patent Office: Days
• US Class Current: 382/109
• CPC Class Codes: G01S 3/7864 T.V. type tracking systems
• CPC Class Codes: G06T 7/35 using statistical methods

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.

Claims

1. A method for registering multi-dimensional topographical digital elevation model data points representing a multi-dimensional object, the method comprising:

a) receiving a plurality of digital elevation model data 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.

2. The method of claim 1, wherein step b) comprises organizing the points in each frame into a k-D tree structure and searching the k-D tree for the closest point for each point.

3. The method of claim 1, wherein each point is represented by x, y, z coordinates and Mahalanobis distances are used to align points in the z direction.

4. The method of claim 1 further comprising applying a rigid transform to a plurality of frames.

5. The method of claim 5 further comprising integrating the frames to produce an integrated surface representing the multi-dimensional object.

7. The method of claim 5, wherein the multi-dimensional topographical data points comprise points derived from a target partially obstructed by obstructions above the geographical area and the method further comprises integrating the frames to produce an integrated surface representing the geographic area and the target.

6. The method of claim 6 further comprising displaying the integrated surface.

8. The method of claim 8 further comprising displaying the integrated surface and the target.

9. A system for registering multi-dimensional digital elevation model topographical points representing a multi-dimensional object, the system comprising:

a registration engine for finding for each point in a first frame a corresponding closest point in each of a plurality of subsequent frames;

a processor for determining a rotation and translation transformation for each of the plurality of subsequent frames and for determining a cost for performing each rotation and translation transformation; and

a logic routine for repeating the determinations of rotation and translation and cost for additional frames until an abort criterion is reached.

10. The system of claim 9, further comprising a ground finder for receiving a plurality of frames of data points representing a partially obscured ground surface and producing a plurality of frames of data point sets representing only the ground surface.

11. The system of claim 9, further comprising logic for applying a rigid transform to the frames using the cost determined by the processor.

12. The system of claim 9, further comprising a k-D tree representing the points of each frame for searching in the subsequent frames for the point closest to each of the points in the first frame.

13. The system of claim 9, further comprising a frame integrator for integrating the frames to provide an integrated surface representing the multi dimensional object.

14. The system of claim 9 further comprising a display for displaying the multi dimensional object.

15. A computer readable medium comprising program instructions for:

a) receiving a plurality of digital elevation model points representing a plurality of overlapping frames of a surface of a 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 instructions b) through d) for additional frames to provide an optimum transformation.

16. The medium of claim 15 wherein instruction b) comprises an instruction for organizing the points in each frame into a k-D tree structure and searching the k-D tree for the closest point for each point.

17. The medium of claim 15 wherein each point is represented by x, y, z coordinates and Mahalanobis distances are used to align points in the z direction.

18. The medium of claim 15 further comprising an instruction for applying a rigid transform to a plurality of frames.