Image registration with uncertainty analysis

• US 7,912,321 B1
• Filed: 12/19/2005
• Issued: 03/22/2011
• Est. Priority Date: 12/19/2005
• Status: Active Grant

• Current Assignee: National Technology & Engineering Solutions Of Sandia LLC (Honeywell International Inc.)
• Original Assignee: Sandia Corporation (Martin Marietta Corporation)
• Inventors: Simonson, Katherine M.
• Primary Examiner(s): Le; Vu
• Assistant Examiner(s): Allison; Andrae S
• Application Number:
  US11/305,903
• Time in Patent Office: 1,919 Days
• Field of Search: 382128-132, 382/199, 382/190, 382293-294
• US Class Current: 382/294
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06T 7/35 using statistical methods

Abstract

In an image registration method, edges are detected in a first image and a second image. A percentage of edge pixels in a subset of the second image that are also edges in the first image shifted by a translation is calculated. A best registration point is calculated based on a maximum percentage of edges matched. In a predefined search region, all registration points other than the best registration point are identified that are not significantly worse than the best registration point according to a predetermined statistical criterion.

Claims

1. An image registration method comprising:

acquiring a first image and a second image of a scene using a processor to perform the steps of;

detecting edges in the first image and the second image;

calculating a percentage of pixels corresponding to a detected edge in a subset of the second image that match a detected edge in the first image shifted by a translation;

defining a best registration point based on a maximum percentage of edges matched;

applying within a pre-defined search region an alpha-level statistical test of a null hypothesis that average match probabilities are equal between the best registration point and each remaining point in the pre-defined search region;

using the alpha-level statistical test to identify all registration points within the pre-defined search region, other than the best registration point, that have a p-value exceeding a specified alpha level; and

determining a 100(1-alpha) % statistical confidence set consisting of the best registration point and all other registration points having the p-value exceeding the specified alpha level, in the alpha-level statistical test of the null hypothesis.

5. The method according to claim 1 further comprising:

transforming the first image and the second image from grayscale to binary format by the edge detecting step;

mapping to a logic value one pixels representing edge locations; and

mapping to a logic value zero pixels representing other than the edge locations.

6. The method according to claim 1 further comprising:

conducting a binary registration transformation as a two-dimensional translation comprising a row shift and a column shift; and

checking the two-dimensional translation within user-selected limits in full-pixel row and column shifts.

7. The method according to claim 1 further comprising:

conducting a binary registration transformation as a two-dimensional translation comprising a row shift and a column shift;

checking the two-dimensional translation within user-selected limits in the row shift and the column shift; and

interpolating the first image and the second image to an increased resolution prior to detecting edges whereby the two-dimensional translation is checked to a sub-pixel precision.

8. The method according to claim 1 further comprising:

conducting registration over a subset of pixels that are detected as edges in the second image; and

deriving the subset of pixels from a combination of sets of rectangular chips containing edge pixels derived from structures in a set of image scenes.

2. An image registration method comprising:

acquiring a first image and a second image of a scene using a processor to perform the steps of;

detecting edges in the first image and the second image;

conducting registration over a subset of pixels detected as edges in the second image for a total of N edge pixels;

translating according to a candidate translation (h,k) with a row shift h and a column shift k between the first and second images within a user-selected range of shifts;

calculating a percentage p(h,k) of the N edge pixels that also correspond to edges in the first image shifted by the candidate translation (h,k);

analyzing match percentages p(h,k) over a set of the candidate translations (h,k) to generate a set of analyzed match percentages p(h,k);

defining a maximum match percentage as a maximum of the set of analyzed match percentages p(h,k);

defining a best registration point based on a maximum percentage of edges matched;

determining whether the maximum match percentage enables registration at a predefined confidence level; and

if the maximum match percentage enables registration, statistically determining which candidate translations (h,k) have match percentages p(h,k) that are not significantly lower than the maximum match percentage.

3. The method according to claim 2 further comprising:

determining a maximum match percentage p(h*,k*) such that p(h*,k*)≧

p(h,k) for all candidate translations (h,k);

comparing the maximum match percentage p(h*,k*) to a threshold value P* for 0<

P*≦

1; and

designating the maximum match percentage p(h*,k*) as sufficient to enable confident registration for the maximum match percentage p(h*,k*) that exceeds the threshold value P*.

4. The method according to claim 3 further comprising:

calculating a sum A_i of a total number of pixels i corresponding to detected edges matched at a translation (h*,k*) corresponding to the maximum match percentage p(h*,k*) but not matched at the candidate translation (h,k);

calculating a sum B_i of a total number of pixels i corresponding to detected edges matched at a candidate translation (h,k) but not matched at the translation (h*,k*);

calculating a normalized test statistic M according to an equation;

9. A system adapted for image registration comprising:

an edge detector adapted to transform a first grayscale image and a second grayscale image from grayscale to binary format to form a first binary format image and a second binary format image;

a transformation engine adapted to register translation between detected edges in the first binary format image and the second binary format image; and

a controller adapted to calculate a percentage of pixels corresponding to a detected edge in a subset of the second binary format image that match a detected edge in the first binary format image shifted by a translation, define a best registration point according to a maximum percentage of edges matched, apply within a pre-defined search region an alpha-level statistical test of a null hypothesis that average match probabilities are equal between the best registration point and each remaining point in the pre-defined search region, use the alpha-level statistical test to identify all registration points within the pre-defined search region, other than the best registration point, that have a p-value exceeding a specified alpha level, and determine a 100(1−

alpha) % statistical confidence set consisting of the best registration point and all other registration points having the p-value exceeding the specified alpha level, in the alpha-level statistical test of the null hypothesis.

13. The system according to claim 9 further comprising:

the transformation engine adapted to conduct a binary registration transformation as a two-dimensional translation comprising a row shift and a column shift; and

the controller adapted to check translations within selected limits in full-pixel row and column shifts.

14. The system according to claim 9 further comprising:

the transformation engine adapted to conduct a binary registration transformation as a two-dimensional translation comprising a row shift and a column shift; and

the controller adapted to check translations within limits in the row shift and the column shift; and

an interpolator adapted to interpolate the first and second grayscale images to an increased resolution prior to the edge detector whereby the translations are checked to a sub-pixel precision.

15. The system according to claim 9 further comprising:

the transformation engine adapted to conduct registration over a subset of pixels that are detected as edges in the second grayscale image, the subset being derived from a union of a set of rectangular chips containing edge pixels derived from structures in a set of selected image scenes.

10. A system adapted for image registration comprising:

an edge detector adapted to transform a first grayscale image and a second grayscale image from grayscale to binary format to form a first binary format image and a second binary format image;

a transformation engine adapted to register translation between detected edges in the first binary format image and the second binary format image, wherein the transformation engine is adapted to conduct registration over a subset of pixels detected as edges in the second image for a total of N edge pixels and translate according to a candidate translation (h,k) with a row shift h and a column shift k between the first and second images within a range of shifts; and

a controller adapted to calculate a percentage of pixels corresponding to a detected edge in a subset of the second binary format image that match a detected edge in the first binary format image shifted by a translation, define a best registration point according to a maximum percentage of edges matched, apply within a search region an alpha-level statistical test of a null hypothesis that average match probabilities are equal between the best registration point and each remaining point in the search region, use the alpha-level statistical test to identify all registration points within the search region, other than the best registration point, that have a p-value exceeding a specified alpha level, and determine a 100(1-alpha) % statistical confidence set consisting of the best registration point and all other registration points having the p-value exceeding the specified alpha level, in the alpha-level statistical test of the null hypothesis, wherein the controller is adapted to calculate a percentage p(h,k) of the N edge pixels that correspond to detected edges in the first image shifted by the candidate translation (h,k), analyze match percentages p(h,k) over a set of candidate translations (h,k) to generate analyzed match percentages p(h,k), define a maximum match percentage as a maximum of the analyzed match percentages p(h,k), determine whether the maximum match percentage enables registration, and if the maximum match percentage enables registration, statistically determine which candidate translations (h,k) have match percentages p(h,k) that are not significantly lower than the maximum match percentage.

11. The system according to claim 10 further comprising:

the controller adapted to determine a maximum match percentage p(h*,k*) such that p(h*,k*)≧

p(h,k) for all candidate translations (h,k), compare the maximum match percentage p(h*,k*) to a threshold value P* for 0<

P*≦

1, and designate the maximum match percentage p(h*,k*) as sufficient to enable confident registration if the maximum match percentage p(h*,k*) exceeds the threshold value P*.

12. The system according to claim 11 further comprising:

the controller adapted to calculate a sum A_i of a total number of pixels i corresponding to detected edges matched at a translation (h*,k*) corresponding to the maximum match percentage p(h*,k*) but not matched at a candidate translation (h,k), calculate a sum B_i of a total number of pixels i corresponding to detected edges matched at the candidate translation (h,k) but not matched at the translation (h*,k*), calculate a normalized test statistic M according to an equation;

16. A system adapted for image registration comprising:

an edge detector;

a transformation engine coupled to the edge detector and adapted to receive a first image and a second image from the edge detector and to register translation over a subset of pixels detected as edges in the second image for a total of N edge pixels and translate according to a candidate translation (h,k) with a row shift h and a column shift k between the first image and the second image within a range of shifts; and

a controller adapted to calculate a percentage p(h,k) of the N edge pixels that match edges in the first image shifted by the candidate translation (h,k), analyze match percentages p(h,k) over a set of candidate translations (h,k), determine whether a maximum match percentage is sufficient to enable registration to a confidence level, apply if the maximum match percentage is sufficient an alpha-level statistical test of a null hypothesis that average match probabilities are equal between the best registration point and each remaining point in the pre-defined search region, use the alpha-level statistical test to identify all registration points within the pre-defined search region, other than the best registration point, that have a p-value exceeding a specified alpha level, and determine a 100(1-alpha) % statistical confidence set consisting of the best registration point and all other registration points having the p-value exceeding the specified alpha level, in the alpha-level statistical test of the null hypothesis.