Normalized crosscorrelation of complex gradients for image autoregistration

[0002] The present invention relates generally to aircraft-based and satellite-based imaging systems, and more particularly, to a system and method for computing the degree of translational offset between corresponding blocks extracted from images acquired by different sensors so that the images can be spatially registered.

[0003] The assignee of the present invention has developed and deployed a digital image processing system that registers images acquired under different conditions and using different types of sensors (e.g., electro-optical camera and synthetic aperture radar). This accurate pixel-to-pixel registration improves the exploitation of such imagery in three ways:

[0004] It makes it possible to detect changes in reconnaissance imagery acquired at two different times. It improves the Image Analyst's ability to interpret the imagery by viewing the ground scene in two different spectral bands (e.g., visible and microwave).

[0005] It makes it possible to determine the exact location of objects detected in reconnaissance imagery by transferring them to reference imagery that has been very accurately referenced to the earth.

[0006] In order to properly exploit images acquired by different sensors, the two images must be registered to each other. One prior art technique to perform this image registration is disclosed in U.S. Pat. No. 5,550,937 entitled “Mechanism for Registering Digital Images Obtained from Multiple Sensors Having Diverse Image Collection Geometries”, issued Aug. 27, 1996.

[0007] In the known prior art disclosed in U.S. Pat. No. 5,550,937, methods for matching image blocks using image gradient magnitude information have been developed that work well with two images acquired with the same type of sensor (e.g., radar for both or electro-optical for both). However, heretofore, no method has been developed that uses a fast Fourier transform (for speed) and also makes use of both gradient magnitude and phase (direction) information to reliably and robustly spatially register the images from two different types of sensors.

[0008] Accordingly, it is an objective of the present invention to provide for a system and method for computing the degree of translational offset between corresponding blocks extracted from images acquired by different sensors so that the images can be spatially registered.

[0009] To accomplish the above and other objectives, the present invention provides for a system and method that computes the degree of translational offset between corresponding blocks extracted from images acquired by two sensors, such as electro-optic, infrared sensors, and radar for example, so that the images can be spatially registered. The present invention uses fast Fourier transform (FFT) correlation to provide for speed, and also uses gradient magnitude and phase (direction) information to provide for reliability and robustness.

[0010] In the present invention, two potentially dissimilar images acquired by two potentially different sensors, such as a synthetic aperature radar (SAR) and a visible band camera, for example, are resampled to a common resolution and orientation using image acquisition parameters provided with the imagery. The present invention provides an efficient robust mechanism for computing the degree of translational offset between corresponding blocks extracted from the two resampled images so that they can be spatially registered.

[0011] The present system and method matches image blocks extracted from the two resampled images and makes use of the intensity gradient of both images that are matched. The two points of novelty implemented in the present invention are that both gradient magnitude and phase (direction) information are used by the matching mechanism to improve the robustness and reliability of the matching results, and the matching mechanism uses a fast Fourier transform (FFF) so it can quickly match large image blocks even on a small personal computer.

[0012] The matching mechanism has several advantages over the prior art disclosed in U.S. Pat. No. 5,550,937. The present invention combines both gradient magnitude and phase information so that image structure is automatically and implicitly taken into account by the matcher. The present invention performs magnitude normalization so that the relative differences in intensity bias and gain between image blocks are ignored by the matcher. This normalization also makes the algorithm insensitive to spatial nonstationarity of edges (i.e., varying number of detailed features within each subarea) within the scene. The present invention makes use of the fast Fourier transform (FFT) so that matching results can be computed very rapidly even on a small personal computer.

[0013] The various features and advantages of the present invention may be more readily understood with reference to the following detailed description taken in conjunction with the accompanying drawing, wherein like reference numerals designate like structural elements, and in which:

[0014] FIGS. 1a-1cillustrate the nature of multisensor and multitemporal image matching in which the present invention is employed;

[0015] FIG. 2 illustrates an exemplary image misregistration that is corrected by the present invention;

[0016] FIG. 3 illustrates an exemplary system and method in accordance with the principles of the present invention; and

[0017] FIG. 4 is a flow diagram illustrating an exemplary method in accordance with the principles of the present invention.

[0018] Referring to the drawing figures, FIGS. 1a-1cillustrate the nature of multisensor and multitemporal image matching in which the present invention is employed. The present invention addresses the problem of automatically registering images acquired by potentially very different sensors, such as a synthetic aperture radar (SAR) and a visible band camera. Such images may be derived from sensors disposed on reconnaissance aircraft or an orbiting satellite, for example. The originally acquired images are resampled (using image acquisition parameters supplied with the imagery) to a common scale and orientation. However, corresponding blocks within the images may have residual offsets relative to one another due to errors in the image acquisition parameters. The present invention provides for a system and method for correcting the relative offset between a small image block (site) extracted from a first image and a corresponding image block (site) extracted from a second, potentially very dissimilar image.

[0019] FIG. 1ashows representative response tables for a synthetic aperature radar (SAR) and an electro-optical (EO) camera along with composition of the ground scene imaged by both sensors. The image acquired by a synthetic aperature radar (SAR) shown in FIG. 1bb differs from the image acquired by the electro-optical camera shown in FIG. 1ceven though the ground scene shown in FIG. 1a, is the same for both. This is due to the fact that a given material on the ground (bare earth, region 1) such as water (region 2), concrete (region 3), trees (region 4), and asphalt (region 5), for example) produces different brightness values when viewed by the two sensors. As is shown in FIG. 1b, the ground scene sensed by the synthetic aperture radar has brightness levels of 100 for bare earth, 50 for water, 150 for concrete, 250 for trees, and 200 for asphalt. In contrast, as is shown in FIG. 1c, the ground scene sensed by the electro-optic sensor has brightness levels of 200 for bare earth, 150 for water, 250 for concrete, 100 for trees, and 50 for asphalt. These contrast reversals make conventional intensity-based crosscorrelation methods, such as disclosed in U.S. Pat. No. 5,550,937, unreliable and inaccurate. The property that is consistent in the two images is the location and direction of edges separating different materials in the ground scene. These edges are detected as gradients in the respective gray-scale images.

[0020] Gradients (e.g., derived using a Sobel operator) have, at every pixel, both magnitude and direction (phase). This suggests that the similarity between two images (i.e., SAR and translated electro-optical) can be measured in terms of the amount of correlation between the respective directions of the gradients for all pixels within a prescribed region (i.e., a site). This is accomplished in accordance with the principles of the present invention by crosscorrelating the complex (i.e., magnitude and phase) gradients over the site. In particular, the gradient magnitudes are weighted by a multiplicative function that decreases with increasing difference in the directions of the gradients in the two images.

[0021] Three additional factors are taken into account. A weighting function W(δ+180) must be equal to W(δ), where δ is the difference (in degrees) between the respective gradient angles. This is due to the fact that the phase of the complex gradient can differ by ±180 degrees at a given edge depending on the polarity of the brightness difference across that boundary. A preferred weighting function that is used is W(δ)=cos²ⁿ(δ) where n is a positive integer. In the explanation that follows, n is taken to be unity. The cross correlation function is normalized to reduce the dependence on the magnitudes of the complex gradients. This is because the magnitude of the gradient across a given boundary varies depending on the brightness difference across that boundary. The crosscorrelation function is normalized to reduce the dependence on the number of edges within the site. Without this normalization, the crosscorrelation function would be highest for sites containing the most edges (i.e., clutter).

[0022] FIG. 2 illustrates exemplary image misregistration that is corrected by the present invention. In FIG. 2, image block A is offset horizontally and vertically within image block B to determine the match point. By way of example, suppose image block A has w columns and h rows while image block B has W>w columns and H>h rows.

[0023] Suppose that a w by h chip is extracted from block B with the upper left corner at B(Δ_c,Δ_r) and that this chip is matched with block A. In this case, the range of permissible column and row offsets of image block A relative to image block B is Δ_c=0, . . . , W-w and Δ_r=0, . . . , H-h.

[0024] The present invention provides a near real-time FFT-based realization of a novel match measure: ${\phi }_{\mathrm{BA}}\left({\Delta }_c{\Delta }_r\right)=\frac{\begin{array}{c}\sum _{c=0}^{w-1}\sum _{r=0}^{h-1}\{{\cos }^2\left[{\theta }_A\left(c,r\right)-{\theta }_B\left(c+{\Delta }_c,r+\Delta r\right)\right]\\ {\left|{\nabla }_A\left(c,r\right)\right|}^2{\left|{\nabla }_B\left(c+{\Delta }_c,r+\Delta r\right)\right|}^2\}\end{array}}{\sum _{c=0}^{w-1}\sum _{r=0}^{h-1}\left\{{\left|{\nabla }_A\left(c,r\right)\right|}^2{\left|{\nabla }_B\left(c+{\Delta }_c,r+\Delta r\right)\right|}^2\right\}}$

[0025] between image blocks A and B extracted from different images (which have been resampled, using the image acquisition parameters, so as to have the same scale and orientation), as shown in FIG. 3.

[0026] More particularly, FIG. 3 illustrates an exemplary system 10 and method 20 for providing a normalized crosscorrelation of complex gradients using fast Fourier transforms (FFTs) 16.

[0027] The following symbols are used with reference to the above equation and FIG. 3:

[0028] c: pixel column index

[0029] r: pixel row index

[0030] {A}: a set of pixels in an image block A to which an offset is applied, w: the width of (or number of columns in) image block A, h: the height of (or number of rows in) image block A,

[0031] {B}: a set of pixels in image block B that image block A is offset relative to,

[0032] Δ_c: the column offset of image block A relative to image block B, and

[0033] Δ_r: the row offset of image block A relative to image block B, and

[0034] ∇_A(c,r)=|∇_A(c,r)|^e(c,r)=(∇_A)_H(c,r)+j(∇_A)_V(c,r), and

[0035] ∇_B(c,r)=|∇_B(c,r)|e^jθ(c,r)=(∇_B)_H(c,r)+j(∇_B)_V(c,r) are intensity

[0036] gradients at a pixel with (column, row) coordinates (c, r) in images A and B expressed in magnitude-phase form and horizontal-vertical gradient form.

[0037] Referring to FIG. 3, the system 10 comprises an algorithm that implements the above match measure equation. In FIG. 3, the above equation has been implemented such that the term cos²(a)=½(1+cos 2a).

[0038] The system 10 processes blocks of images acquired by first and second sensors. The images are resampled to a common scale and orientation, and a relative offset exists between a set of pixels {A} extracted from the first image and a corresponding set of pixels {B} extracted from the second image.

[0039] The system 10 has first and second processing paths 11a, 11bthat respectively process a set of pixels {A} in an image block A to which an offset is applied, and a set of pixels {B} in an image block B relative to which image block A is offset. In each processing path 11a, 11b, the respective sets of pixels {A}, {B} are processed using intensity gradient circuits 12a, 12bto generate intensity gradients at each pixel with (column, row) coordinates (c, r) in images A and B expressed in magnitude-phase form and horizontal-vertical gradient form. The intensity gradient circuits 12a, 12bmay comprise Sobel operators, for example.

[0040] Outputs of the intensity gradient circuits 12a, 12bin each processing path 11a, 11bare multiplied together and by a factor of two in a first multiplier 13ato produce complex gradients. Outputs of the first multipliers 13aare input to a first fast Fourier transform 16athat crosscorrelates the respective inputs.

[0041] The outputs of the intensity gradient circuits 12a, 12bin each processing path 11a, 11bare respectively input to squaring circuits 14a, 14b. Outputs of the squaring circuits 14a, 14bin each processing path 11a, 11bare input to a first adder 15awhere they are subtracted. Outputs of the first adders 15ain each processing path 11a, 11bare input to a second fast Fourier transform 16bthat crosscorrelates the respective inputs. The outputs of the first and second fast Fourier transforms 16a, 16bare summed in a third adder 15c.

[0042] Outputs of the squaring circuits 14a, 14bin each processing path 11a, 11bare input to a second adder 15bwhere they are added. Outputs of the second adders 15bin each processing path 11a, 11bare input to a third fast Fourier transform 16cthat crosscorrelates the respective inputs. The output of the third fast Fourier transform 16cis inverted in an inverter circuit 17.

[0043] The output of the third adder 15cand the output of the inverter circuit 17 are multiplied together, and thus normalized, in a second multiplier 13b, which produces a match surface. A maximum value in the match surface is determined in a maximum value circuit 18 to produce a match offset, which is the output of the system 10.

[0044] For the purposes of completeness, FIG. 4 is a flow diagram illustrating an exemplary method 20 in accordance with the principles of the present invention. The exemplary method 20 comprises the following steps.

[0045] First and second images are acquired 21 using first and second sensors. The first and second images are resampled 22 to a common scale and orientation, such that a relative offset exists between a set of pixels {A} extracted from the first image and a corresponding set of pixels {B} extracted from the second image.

[0046] The respective sets of pixels {A}, {B} are processed to generate 23 intensity gradients at each pixel with (column, row) coordinates (c, r) in the images expressed in magnitude-phase form and horizontal-vertical gradient form. The intensity gradients are multiplied together and by a factor of two 24 to produce complex gradients. The complex gradients are crosscorrelated 25 by a first fast Fourier transform 16a.

[0047] The intensity gradients are squared 26, are subtracted 27 from each other, and are crosscorrelated 28 in a second fast Fourier transform 16b. The crosscorrelated intensity gradients produced by the first and second fast Fourier transforms 16a, 16bare summed together 29.

[0048] The squared intensity gradients are added 30 and crosscorrelated 31 in a third fast Fourier transform 16c. The crosscorrelated squared intensity gradients are normalized 32 and are multiplied 33 by the crosscorrelated summed intensity gradients to produce a match surface. The match surface is then processed 34 to generate a maximum value that corresponds to a match offset between the sets of pixels {A } {B}.

[0049] Thus, a system and method for computing the degree of translational offset between corresponding blocks extracted from images acquired by different sensors so that the images can be spatially registered have been disclosed. It is to be understood that the above-described embodiments are merely illustrative of some of the many specific embodiments that represent applications of the principles of the present invention. Clearly, numerous and other arrangements can be readily devised by those skilled in the art without departing from the scope of the invention.