Feature mapping between data sets

• US 7,124,022 B2
• Filed: 05/28/2003
• Issued: 10/17/2006
• Est. Priority Date: 05/31/2002
• Status: Expired due to Fees

• Current Assignee: Atlas Elektronik UK (Holdings) Ltd. (Thyssenkrupp AG)
• Original Assignee: Qinetiq Limited (QinetiQ Group PLC)
• Inventors: Carmichael, Douglas Rayner, Chapman, Sean Alaric
• Primary Examiner(s): Jeanglaude, Gertrude A.
• Application Number:
  US10/516,263
• Publication Number:
  US 20060123050A1
• Time in Patent Office: 1,238 Days
• Field of Search: 701/200, 701/201, 701/208, 340/995.14, 340/995.15, 342/357.01, 342/357.07
• US Class Current: 701/208
• CPC Class Codes: G06T 7/246 using feature-based methods, e.g. the tracking of corners or segments
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06T 7/35 using statistical methods
• CPC Class Codes: G06V 40/10 Human or animal bodies, e.g. vehicle occupants or pedestrians; Body parts, e.g. hands

Abstract

The present invention relates to data mapping and involves the mapping of at least one feature from one data set to a corresponding feature in a second data set. Individual points of the features are initially mapped and an transformation for mapping the entire feature is derived from the individual mappings. The feature mapping may be used to enhance vehicle navigation, in feature tracking algorithms, and in image processing systems.

Claims

1. A method of deriving a feature tracking transformation to map at least one feature from a first data set onto a corresponding feature from a second data set, comprising the following steps:

(a) extracting a first set of points relating to said at least one feature in said first data set;

(b) associating said first set of points with a second set of points in said second data set;

(c) calculating said feature tracking transformation to at least approximately map said first set of points from said first data set to said second set of points in said second data set, wherein said step of calculating said feature tracking transformation comprises the steps of;

(i) for each point in one of said two sets of points, estimating a mapping of said point to a selected point in said other set of points to produce individual point mapping estimates;

(ii) combining said individual point mapping estimates to produce an estimated transformation to map said one set of points to said other set of points;

(iii) applying said estimated transformation to said one set of points to generate an approximate image position;

(iv) repeating said steps (i) to (iii) iteratively to produce an estimated transformation for mapping said other set of points to a set of points from said approximate image position; and

(v) deriving said feature tracking transformation for mapping said first set of points to said second set of points from a combination of said estimated transformations.

2. A method as claimed in claim 1, comprising the further steps of:

iteratively repeating steps (i) to (iii) using said latest approximate image position and alternative first and second sets of points until said approximate image position aligns with said second set of points to within predetermined limits

and deriving said feature tracking transformation from a combination of said estimated transformations.

3. A method as claimed in claim 2, wherein said steps (i) to (iii) are repeated iteratively until applying said estimated transformation to said approximate image produces no movement of said approximate image.

4. A method as claimed in claim 1, wherein step (i) the other points are selected on a nearest neighbour basis by mapping each point in said one set of points to its nearest spatial neighbour in said other set of points.

5. A method as claimed in claim 1, wherein step (i) of estimating the mapping of individual points is done using an optimal assignment algorithm.

6. A method as claimed in claim 1, wherein step (i) of estimating the mapping of individual points includes a deletion step during which any points from said data sets that are mapped over a distance that is greater than a specified distance are deleted from the set of points.

7. A method as claimed in claim 6, wherein said specified distance comprises a multiple number of times the median of the squared distance distribution of the distances between individual points in one set of points and their nearest neighbour in the other set of points.

8. A method as claimed in claim 1, wherein said step of deriving a feature tracking transformation comprises summing said mappings of said estimated transformations.

9. A method as claimed in claim 1, wherein step (a) of extracting said first set of points comprises using an edge detection algorithm to extract said points from said first data set.

10. A method as claimed in claim 1, where said at least one feature comprises bathymetric contours.

11. A method as claimed in claim 1, wherein said estimated transformation and said feature tracking transformation comprise affine transformations comprising a translation and a rotation of the sets of data points.

12. A method according to claim 11, further comprising the steps of:

iteratively repeating steps (i) to (iii) using said latest approximate image position and alternative first and second sets of points until said approximate image position aligns with said second set of points to within predetermined limits

and deriving said feature tracking transformation from a combination of said estimated transformations,

wherein said step (ii) to derive an estimated transformation to map said first set of points to said second set of points comprises combining the individual mappings using the method of least squares or iterative re-weighted least squares, and estimating said parameters of an affine transformation therefrom.

13. A method according to claim 1, wherein said first set of points comprises over one hundred points.

14. A method as claimed in claim 1 wherein sets of vectors having a position and a direction are extracted, associated and mapped rather than sets of points, a constraint being added to said method such that only vectors having similar directional components are mapped onto each other.

15. A method as claimed in claim 14, wherein said constraint comprises only allowing vectors from said first data set to mapped onto vectors from said second data set that have a directional component within +/−

90°

of said first data set vector.

16. A method of deriving a data set transformation for mapping a first data set onto a second data set, comprising a method as claimed in claim 1;

and the further step of outputting said feature tracking transformation as a data set transformation for mapping said first data set to said second data set.

17. A method of deriving a data set transformation as claimed in claim 16, said method comprising a further step of extracting at least one further set of points or vectors relating to at least one further feature from said first data set;

associating said at least one further set of points or vectors with a second further set of points or vectors in a second data set;

calculating at least one further feature tracking transformation to at least approximately map said at least one further first set of points or vectors from said first data set to said further second set of points or vectors from said second data set, by using steps (i) to (v) of claim 1;

combining said at least one feature tracking transformation and said further feature tracking transformation to produce a data set transformation; and

outputting said data set transformation.

18. A method as claimed in claim 17, wherein said at least one feature comprises bathymetric contours of a certain depth and said at least one further feature comprises bathymetric contours of a different depth.

19. A method of enhanced navigation of a vehicle comprising deriving a data set transformation for mapping a first data set onto a second data set according to claim 16, wherein said first data set comprises stored map data of an area to be navigated through and said second data set comprises data detected by detectors on said vehicle during said navigation, said data set transformation being used to adjust navigation controls of said vehicle.

20. A method of enhanced navigation of a vehicle comprising deriving a data set transformation for mapping a first data set onto a second data set according to claim 16, wherein said first data set comprises data detected by detectors monitoring an area in front of said vehicle and said second data set comprises data detected by detectors monitoring an area beneath said vehicle during said navigation, said data set transformation being used to adjust navigation controls of said vehicle.

21. A method of enhanced navigation of a vehicle comprising deriving a data set transformation for mapping a first data set onto a second data set according to claim 16, wherein said first data set comprises both stored map data and where map data is not available data previously detected by detectors on said vehicle during navigation and said second data set comprises data currently detected by said detectors, said data set transformation being used to adjust navigation controls of said vehicle.

22. A method of enhanced navigation according to claim 19, wherein said detectors comprise sonar detectors and said vehicle is an unmanned underwater vehicle.

23. A method of enhanced navigation according to claim 22, wherein said data set transformation is used in conjunction with data from an inertial sensor to navigate said vehicle.

24. An image processing method for producing a map of an area from a plurality of images of said area produced by a sensor sensing said images as it moves relative to said area, said method comprising the following steps:

deriving a data set transformation for mapping a first data set onto a second data set according to claim 16, wherein said first data set comprises an initial image of said area sensed by said sensor and said second data set comprises a subsequent image of said area sensed by said sensor after it has moved a certain distance;

using said data set transformation to estimate said distance moved by said sensor relative to said area between images;

combining said images using said estimated distance; and

repeating said steps for subsequent images to produce a map of said area from said combined images.

25. A feature tracking method for tracking a feature as it moves relative to a sensor comprising a method of deriving a feature tracking transformation to map at least one feature from a first data set onto a corresponding feature from a second data set according to claim 1, wherein said first data set comprises an image sensed by said sensor and said second data set comprises a subsequent image sensed by said sensor, deriving a distance and direction moved by said feature from said feature tracking transformation.

26. A computer program product operable to control a computer to derive a feature tracking transformation to map at least one feature from a first data set onto a corresponding feature from a second data set by controlling said computer to perform the steps of a method according to claim 1.

27. A computer program product operable to control a computer to derive a data set transformation for mapping a first data set onto a second data set by controlling said computer to perform the steps of a method according to claim 16.

31. A navigation system for enhancing the navigation abilities of a vehicle comprising:

storage means operable to store map data;

at least one sensor for detecting said environment outside of said vehicle; and

a signal processor comprising a computer program product according to claim 27 operable to calculate a data set transformation operable to map a first data set comprising said map data stored in said storage means onto a second data set comprising image data sensed by said at least one sensor; and

navigation control means operable to control the navigation of said vehicle, said navigation control means being operable to respond to said calculated data set transformation.

32. A navigation system for enhancing the navigation abilities of a vehicle comprising:

storage means operable to store map data;

at least one sensor for detecting said environment outside of said vehicle; and

a signal processor comprising a computer program product according to claim 27 operable to calculate a data set transformation operable to map a first data set comprising said map data stored in said storage means onto a second data set comprising image data sensed by said at least one sensor; and

navigation control means operable to control the navigation of said vehicle, said navigation control means being operable to respond to said calculated data set transformation.

33. A navigation system for enhancing the navigation abilities of a vehicle comprising:

storage means operable to store map data;

at least one sensor for detecting said environment outside of said vehicle; and

signal processor comprising a computer program product according to claim 27 operable to calculate a data set transformation operable to map a first data set comprising both stored map data and where map data is not available data previously detected by said sensors onto a second data set comprising image data currently sensed by said at least one sensor; and

navigation control means operable to control the navigation of said vehicle, said navigation control means being operable to respond to said calculated data set transformation.

34. A navigation system for enhancing the navigation abilities of a vehicle comprising:

storage means operable to store map data;

at plurality of sensors for detecting said environment outside of said vehicle including an area in front of said vehicle and an area beneath said vehicle; and

a signal processor comprising a computer program product according to claim 27 operable to calculate a data set transformation operable to map a first data set comprising data sensed by said sensors monitoring an area in front of said vehicle onto a second data set comprising data sensed by said sensors monitoring an area beneath said vehicle; and

navigation control means operable to control the navigation of said vehicle, said navigation control means being operable to respond to said calculated data set transformation.

28. A device for deriving a feature tracking transformation to map at least one feature from a first data set onto a corresponding feature from a second data set comprising:

a signal processor operable to extract a first set of points relating to at least one feature from said first data set and to match said first set of point to a second set of points in a second data set;

a calculating circuit operable to calculate a feature tracking transformation to at least approximately map said first set of points from said first data set to said second set of points in said second data set, wherein calculating circuit is operable to perform the following iteration;

for each point in one of said first or said second set of points, said circuit estimates a mapping of said point to a point in said other of said first or said second set of points;

combines said individual point mapping estimates to produce an estimated transformation to map said one set of points to said other set of points;

applies said estimated transformation to said one set of points to generate an approximate image position;

repeats said iterative steps to produce an estimated transformation for mapping said other set of points to a set of points from said approximate image position;

derives said feature tracking transformation for mapping said first set of points to said second points from a combination of said estimated transformations;

said device further comprising an output device for outputting said feature tracking transformation.

29. A device as claimed in claim 28, wherein sets of vectors having a position and a direction are extracted, matched and mapped rather than sets of points, said calculating circuit comprising a constraint such that only vectors having similar directional components are mapped onto each other.

30. A device as claimed in claim 29, wherein said constraint comprises only allowing vectors from said first data set to mapped onto vectors from said second data set that have a directional component within +/−

90°

of said first data set vector.