Image registration using reduced resolution transform space

• US 6,738,532 B1
• Filed: 08/30/2000
• Issued: 05/18/2004
• Est. Priority Date: 08/30/2000
• Status: Active Grant

• Current Assignee: The Boeing Co.
• Original Assignee: The Boeing Co.
• Inventors: Oldroyd, Lawrence A.
• Primary Examiner(s): Au, Amelia M.
• Assistant Examiner(s): LAROSE, COLIN M
• Application Number:
  US09/651,522
• Time in Patent Office: 1,357 Days
• Field of Search: 382/294, 382/289, 382/295, 382/293, 382/284, 348/95, 250/491.1, 345/634
• US Class Current: 382/294
• CPC Class Codes: G06T 3/602 by block rotation, e.g. by recursive reversal or rotation
• CPC Class Codes: G06T 7/32 using correlation-based methods
• CPC Class Codes: G06V 10/7515 Shifting the patterns to accommodate for positional errors

Abstract

A method of registering images is provided which includes capturing a first original image of a scene under surveillance, capturing a second original image of the scene under surveillance, coarsely matching the first original image to the second original image to give approximate angle and offset parameters of the first original image to the second original image, and finely matching the first original image to the second original image based on the approximate angle and offset parameters of the coarsely matching step. The coarsely matching step involves applying a plurality of rotations to a reduced version of the first original image to form a rotated and reduced first original image and performing a correlation match between the rotated and reduced first original image and a reduced version of the second original image. The finely matching step employs control point matching between the first original image and the second original image using small image patches at a scale of the one of the first original image and the second original image having lower resolution.

Claims

1. A method of registering images comprising:

capturing a first original image of a scene under surveillance;

capturing a second original image of said scene under surveillance;

coarsely matching said first original image to said second original image to give approximate angle and offset parameters of said first original image to said second original image;

finely matching said first original image to said second original image based on the approximate angle and offset parameters of said coarsely matching step;

reducing said first original image to form a second reduced first original image having a common scenic scale as said second original image so that scenic objects appearing in both images have a common extent; and

rotating the second reduced first original image by a rotational difference between the first and second original images to form a second rotated and reduced first original image;

wherein the finely matching step further comprises selecting a plurality of first offset patch images from the second rotated and reduced first original image from a grid of pre-selected locations uniformly and symmetrically spread around an extent of the second rotated and reduced first original image.

2. The method of claim 1 further comprising reducing said first and second original images to a pre-selected scale to form a reduced first original image and a reduced second original image having a common apparent size.

3. The method of claim 2 wherein said coarsely matching step further comprises:

applying a plurality of rotations to the reduced first original image to form a rotated and reduced first original image; and

performing a correlation match between the rotated and reduced first original image and the reduced second original image.

4. The method of claim 3 wherein said applying step further comprises rotating said reduced first original image by a sequence of angle increments that in combination encompass a range of possible rotational mismatches between the first original image and the second original image wherein sequential rotations increase from a minimum of the range by a pre-selected rotational increment.

5. The method of claim 4 wherein said pre-selected rotational increment further comprises two degree increments or less.

6. The method of claim 3 wherein said correlation match further comprises:

transforming said rotated and reduced first original image and said reduced second original image into a Fourier domain by subjecting each to a Fourier transform to produce Fourier images including an array of spatial frequency coefficients;

applying a complex conjugate transform to one of the Fourier images; and

correlating the Fourier images by pixel multiplication in the Fourier domain to yield a product image.

7. The method of claim 6 further comprising:

applying an inverse Fourier transform to the product image to yield a correlation image having pixel values representing correlation coefficients corresponding to offsets given by row and column coordinates of a correlation coefficient pixel.

8. The method of claim 7 further comprising:

creating a set of peak correlation coefficients by collecting peak values from scanning each correlation image for a maximum pixel value.

9. The method of claim 8 wherein:

the rotational difference between the first and second original images is identified by examining the set of peak correlation coefficients for a maximum correlation coefficient.

10. The method of claim 9 wherein:

prior to said selecting step, said second rotated and reduced first original image is shifted by identifying an approximate shift offset between the first and second original images by determining row and column offsets corresponding to the rotational difference.

11. The method of claim 10 further comprising re-scaling said row and column offsets in size according to any reductions applied during said step of reducing said first and second original images.

12. The method of claim 2 wherein said pre-selected scale is selected to provide images that are small enough to enable brute force matching.

13. The method of claim 12 Wherein said images are less than or equal to 64 by 64 pixels.

14. A method of registering images comprising:

capturing a first original image of a scene under surveillance;

capturing a second original image of said scene under surveillance;

reducing said first and second original images to a pre-selected scale to form a reduced first original image and a reduced second original image having a common apparent size;

coarsely matching said first original image to said second original image to give approximate angle and offset parameters of said first original image to said second original image;

finely matching said first original image to said second original image based on the approximate angle and offset parameters of said coarsely matching step;

wherein said coarsely matching step further comprises;

applying a plurality of rotations to the reduced first original image to form a rotated and reduced first original image; and

performing a correlation match between the rotated and reduced first original image and the reduced second original image;

wherein said correlation match further comprises;

transforming said rotated and reduced first original image and said reduced second original image into a Fourier domain by subjecting each to a Fourier transform to produce Fourier images including an array of spatial frequency coefficients;

applying a complex conjugate transform to one of the Fourier images; and

correlating the Fourier images by pixel multiplication in the Fourier domain to yield a product image;

applying an inverse Fourier transform to the product image to yield a correlation image having pixel values representing correlation coefficients corresponding to offsets given by row and column coordinates of a correlation coefficient pixel;

creating a set of peak correlation coefficients by collecting peak values from scanning each correlation image for a maximum pixel value;

identifying a rotational difference between the first and second original images by examining the set of peak correlation coefficients for a maximum correlation coefficient;

identifying an approximate shift offset between the first and second original images by determining row and column offsets corresponding to the rotational difference;

re-scaling said row and column offsets in size according to any reductions applied during said step of reducing said first and second original images;

reducing said first original image to form a second reduced first original image having a common scenic scale as said second original image so that scenic objects appearing in both images have a common extent; and

rotating the second reduced first original image by the rotational difference to form a second rotated and reduced first original image;

wherein the finely matching step further comprises selecting a plurality of first offset patch images from the second rotated and reduced first original image from a grid of pre-selected locations uniformly and symmetrically spread around an extent of the second rotated and reduced first original image as modified by shifting according to the row and column offsets.

15. The method of claim 14 further comprising:

checking each first offset image patch to ensure that each first offset image patch falls completely within the extent of the second rotated and reduced first original image.

16. The method of claim 15 further comprising adjusting a location of a first offset image patch falling outside the extent so that the first offset image patch falls just within the extent.

17. The method of claim 16 further comprising adjusting a location of a corresponding second offset image patch from the second original image according to said step of adjusting the location of the first offset image patch from the second rotated and reduced first original image.

18. The method of claim 17 further comprising re-selecting said first offset image patch from said second rotated and reduced first original image and said corresponding second offset image patch from said second original image if the corresponding second offset image patch falls outside of the extent so that both first and second offset image patches fall outside of their respective image extent by approximately the same amount.

19. The method of claim 14 further comprising selecting a plurality of second image patches from a grid of pre-selected locations uniformly and symmetrically spread around an extent of the second original image.

20. The method of claim 19 further comprising matching the first offset image patches with the second offset image patches by correlation such that each pair of corresponding patches produces one correlation image that is used to produce one control point for image registration.

21. The method of claim 20 wherein said correlation further comprises a Fourier transform.

22. The method of claim 20 further comprising locating the peak correlation value in each correlation image during correlation, the location of the peak correlation value giving the precise offset between the match point in the second original image and a corresponding match point in the second reduced and rotated first original image.

23. The method of claim 22 further comprising adding the precise offset determined during said correlation step and the row and column offset determined in the coarsely matching step to the location of the second offset image patch from the second original image to produce a measured location equivalent to a point in the second reduced and rotated first original image that corresponds with the match point in the second original image.

24. The method of claim 23 further comprising de-rotating and re-scaling the measured location by applying the reverse of the rotation and scaling that was applied to the reduced original image to yield a correct control point location in the first original image that matches a corresponding control point in the second original image.

25. The method of claim 24 wherein a set of all control point pairs gives a control set which is used to obtain a mathematical transformation that provides registration mapping between the first and second original images.

26. The method of claim 25 wherein the control set further comprises a set of pairs of corresponding measured and fiducial points in the first and second original images that define which points in the images coincide.

27. The method of claim 25 wherein the registration mapping further comprises a pair of mathematical functions that map coordinate locations in the first original image into the corresponding locations in the second original image.

28. The method of claim 27 wherein a statistical adjustment is used to produce a set of parameters that specify the mathematical functions.

29. The method of claim 25 further comprising obtaining a measure of remaining distance errors between control point pairs after registration mapping to indicate an accuracy of the registration mapping of the control point pairs in the control set.

30. The method of claim 29 further comprising inspecting the errors to determine if the registration mapping produces excessive error.

31. The method of claim 30 wherein said inspecting step further comprises:

computing a sequence of point coordinates corresponding to a geometric shape in the second original image;

transforming the sequence of point coordinates using the registration mapping into point coordinates in the first original image; and

evaluating the transformed points to determine a closeness of fit of the sequence of point coordinates relative to the geometric shape in the second original image.

32. The method of claim 14 wherein said applying step further comprises rotating said reduced first original image by a sequence of angle increments that in combination encompass a range of possible rotational mismatches between the first original image and the second original image wherein sequential rotations increase from a minimum of the range by a pre-selected rotational increment.

33. The method of claim 32 wherein said pre-selected rotational increment further comprises two degree increments or less.