US6738532B1
Expired / Lapsed
US
⏱️ 0.0 years remaining
Image registration using reduced resolution transform space
Assignee: Boeing Co
•
Filing: 2000-08-30
•
Granted: 2004-05-18
•
Expires: 2020-08-30
Abstract
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.
Inventors
- 👤 Lawrence A. Oldroyd
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-09 11:48
CPC Classifications
G; G06; G06T; G06T3/00; G06T3/60; G06T3/602; G06T7/00; G06T7/30; G06T7/32; G06V; G06V10/00; G06V10/70; G06V10/74; G06V10/75; G06V10/751; G06V10/7515
Claims Analysis
Total Claims: 35
Claim 1
Independent Claim
188 words
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.
Claim 2
Independent Claim
188 words
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.
Claim 3
Dependent Claim
36 words
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.
Claim 4
Dependent Claim
51 words
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.
Claim 5
Dependent Claim
58 words
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.
Claim 6
Dependent Claim
17 words
The method of claim 4 wherein said pre-selected rotational increment further comprises two degree increments or less.
Claim 7
Dependent Claim
75 words
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.
Claim 8
Dependent Claim
41 words
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.
Claim 9
Dependent Claim
28 words
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.
Claim 10
Dependent Claim
31 words
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.
Claim 11
Dependent Claim
45 words
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.
Claim 12
Dependent Claim
31 words
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.
Claim 13
Dependent Claim
23 words
The method of claim 2 wherein said pre-selected scale is selected to provide images that are small enough to enable brute force matching.
Claim 14
Dependent Claim
18 words
The method of claim 12 Wherein said images are less than or equal to 64 by 64 pixels.
Claim 15
Independent Claim
463 words
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.
Claim 16
Independent Claim
463 words
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.
Claim 17
Dependent Claim
35 words
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.
Claim 18
Dependent Claim
32 words
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.
Claim 19
Dependent Claim
45 words
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.
Claim 20
Dependent Claim
67 words
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.
Claim 21
Dependent Claim
32 words
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.
Claim 22
Dependent Claim
43 words
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.
Claim 23
Dependent Claim
13 words
The method of claim 20 wherein said correlation further comprises a Fourier transform.
Claim 24
Dependent Claim
52 words
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.
Claim 25
Dependent Claim
71 words
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.
Claim 26
Dependent Claim
53 words
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.
Claim 27
Dependent Claim
36 words
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.
Claim 28
Dependent Claim
36 words
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.
Claim 29
Dependent Claim
34 words
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.
Claim 30
Dependent Claim
22 words
The method of claim 27 wherein a statistical adjustment is used to produce a set of parameters that specify the mathematical functions.
Claim 31
Dependent Claim
38 words
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.
Claim 32
Dependent Claim
19 words
The method of claim 29 further comprising inspecting the errors to determine if the registration mapping produces excessive error.
Claim 33
Dependent Claim
72 words
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.
Claim 34
Dependent Claim
58 words
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.
Claim 35
Dependent Claim
17 words
The method of claim 32 wherein said pre-selected rotational increment further comprises two degree increments or less.
References Cited (Backward Citations)
US4635293A
Cited
US5495535A
Cited
US5550937A
Cited
US5611000A
Cited
US5649032A
Cited
US6178271B1
Cited
US6577744B1
Cited
US6097854A
Cited
US6266452B1
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2007-05-18 | 2007-11-17 | 2008-05-18 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2011-05-18 | 2011-11-17 | 2012-05-18 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2015-05-18 | 2015-11-17 | 2016-05-18 | $7700.00 | Window Closed / Lapsed |