Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1999-03-18
2001-07-24
Boudreau, Leo (Department: 2621)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
C382S280000, C382S295000, C382S296000, C382S298000
Reexamination Certificate
active
06266452
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to the field of imaging, and in particular to a novel method for registering images.
BACKGROUND OF THE INVENTION
A. Image Registration
Image registration is the process of aligning a pattern image over a reference image so that pixels present in both images are disposed in the same location. This process is useful, for example, in the alignment of an acquired image over a template, a time series of images of the same scene, or the separate bands of a composite image (“coregistration”). Two practical applications of this process are the alignment of radiology images in medical imaging and the alignment of satellite images for environmental study.
In typical image registration problems, the reference image and the pattern image are known or are expected to be related to each other in some way. That is, the reference image and the pattern image are known or are expected to have some elements in common, or to be related to the same subject or scene. In these typical image registration problems, the sources of differences between the two images can be segregated into four categories:
1. Differences of alignment: Differences of alignment between images are caused by a spatial mapping from one image to the other. Typical mappings involve translation, rotation, warping, and scaling. For infinite continuous domain images, these differences are a result of a spatial mapping from one image to the other. Changing the orientation or parameters of an imaging sensor, for example, can cause differences of alignment.
2. Differences due to occlusion: Differences due to occlusion occur when part of a finite image moves out of the image frame or new data enters the image frame of a finite image due to an alignment difference or when an obstruction comes between the imaging sensor and the object being imaged. For example, in satellite images, clouds frequently occlude the earth and cause occlusions in images of the earth's surface.
3. Differences due to noise: Differences due to noise may be caused by sampling error and background noise in the image sensor, and from unidentifiably invalid data introduced by image sensor error.
4. Differences due to change: Differences to change are actual differences between the objects or scenes being imaged. In satellite images, lighting, erosion, construction, and deforestation are examples of differences due to change. In some cases, it may be impossible to distinguish between differences due to change and differences due to noise.
Images are typically registered in order to detect the changes in a particular scene. Accordingly, successful registration detects and undoes or accounts for differences due to alignment, occlusion, and noise while preserving differences due to change. Registration methods must assume that change is small with respect to the content of the image; that is, the images being registered are assumed to be “visibly similar” after accounting for differences due to alignment, occlusion, and noise. In addition, a sufficient amount of the object or scene must be visible in both images. For example, it may be assumed that at least 50% of the content of the reference image is also present in the pattern image to be registered against it. In practice, medical and satellite sensors can usually be oriented with enough precision for images to share 90% or more of their content.
B. Rotation-Scale-Translation Transformations
The present invention provides an efficient method for registering two images that differ from each other by a Rotation-Scale-Translation (“RST”) transformation in the presence of noise and occlusion from alignment. The RST transformation is expressed as a combination of three transformation parameters: a single translation vector, a single rotation factor, and a single scale factor, all operating in the plane of the image. The invention recovers these three parameters from the two images, thereby permitting the pattern image to be registered with the reference image by “undoing” the rotation, scale and translation of the pattern image with respect to the reference image. The invention also encompasses novel methods for recovering the rotation or scale factors alone, which may be useful where it is known that the alignment between the reference and pattern images is affected by only one of these factors.
The RST transformation is expressed as a pixel-mapping function, M, that maps a reference image r into a pattern image p. In practice, these functions operate on finite images and can only account for data that does not leave or enter the frame of the image during transformation. If a two-dimensional infinite continuous reference image r and pattern image p are related by an RST transformation such that p=M(r), then each point r(x
r
, y
r
) in r maps to a corresponding point p(x
p
, y
p
) according to the matrix equation:
[
x
p
y
p
1
]
=
[
s
cos
φ
-
s
sin
φ
Δ
x
s
sin
φ
s
cos
φ
Δ
y
0
0
1
]
[
x
r
y
r
1
]
(
1
)
Equivalently, for any pixel p(x, y), it is true that:
r
(
x, y
)=
p
(
&Dgr;x+s
·(
x
cos &phgr;−
y
sin &phgr;),&Dgr;
y+s
·(
x
sin &phgr;+
y
cos &phgr;)) (2)
In this notation, &phgr;, s, and (&Dgr;x, &Dgr;y) are the rotation, scale and translation parameters, respectively, of the transformation, where &phgr; is the angle of rotation in a counter clockwise direction, s is the scale factor, and (&Dgr;x, &Dgr;y) is the translation. For finite discrete r and p, assume r and p are square with pixel area N (size {square root over (N)}×{square root over (N)}). Note that an RST transformation of a finite image introduces differences due to occlusions as some data moves into or out of the image frame.
C. The Fourier-Mellin Invariant
The Fourier transform has certain properties under RST transformations that make it useful for registration problems. Let two two-dimensional infinite continuous images r and p obey the relationship given in Equation (2) above. By the Fourier shift, scale, and rotation theorems, the relationship between F
r
and F
p
, the Fourier transforms of r and p, respectively, is given by:
F
r
(&ohgr;
x
,&ohgr;
y
)=
e
j2&pgr;(&ohgr;
x
&Dgr;x+&ohgr;
y
&Dgr;
y
)/s
s
2
F
p
((&ohgr;
x
cos &phgr;+&ohgr;
y
sin &phgr;)/
s,
(−&ohgr;
x
sin &phgr;+&ohgr;
y
cos &phgr;)/
s
) (3)
Note that the complex magnitude of Fourier transform F
p
is s
2
times the magnitude of F
r
and it is independent of &Dgr;x and &Dgr;y. Also, the magnitude of F
p
is derived from the magnitude of F
r
by rotating F
r
by −&phgr; and shrinking its extent by a factor of s. This enables us to recover the parameters of rotation and scale through separate operations on the magnitude of F
p
.
Equation (3) shows that rotating an image in the pixel domain by angle &phgr; is equivalent to rotating the magnitude of its Fourier transform by &phgr;. Expanding an image in the pixel domain by a scale factor of s is equivalent to shrinking the extent of the magnitude of its Fourier transform by s and multiplying the height (amplitude) of the magnitude of the Fourier transform by S
2
. Translation in the pixel domain has no effect on the magnitude of the Fourier transform. Because of this invariance, the magnitude of a Fourier transform is referred to as the “Fourier-Mellin invariant,” and the Fourier-magnitude space is referred to as the “Fourier-Mellin domain.” The Fourier-Mellin transforms, R and P, of r and p, respectively, are R=|F
r
| and P=|F
p
|.
Many prior art registration techniques operate on the translation-invariant Fourier-Mellin space, then convert to polar-logarithmic (“polar-log”) coordinates so that rotation and scale effects appear as translational shifts along orthogonal &thgr; and log
B
&rgr; axes, where B is global constant logarithm b
Boudreau Leo
Isztwan, Esq. Andrew G.
NEC Research Institute Inc.
Patel Kanji
LandOfFree
Image registration method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Image registration method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Image registration method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2547930