Image analysis – Applications – Motion or velocity measuring
Reexamination Certificate
1999-08-12
2003-04-08
Johnson, Timothy M. (Department: 2625)
Image analysis
Applications
Motion or velocity measuring
C348S154000, C348S155000
Reexamination Certificate
active
06546120
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to a correspondence-between-images detection method and system belonging to, for example, the following technical fields:
1. Image coder-decoder for knowing the correspondence between images consecutive in time sequence and transmitting and storing the images in a small coding amount.
2. Measuring device for finding the correspondence holding between stereoscopic images and measuring a distance.
3. Image processor for compensating motion of an image caused by unintended motion of a camera, such as camera shake.
4. Image processor for integrating a plurality of images into a wide-view image such as a panoramic image.
2. Description of the Related Art
As the viewpoint of a camera or an object moves, the object is projected at a different position in an image. The correspondence between the two projection images can be represented as mapping of a position set on one image to a position set on the other.
There are various models of mappings and the following are known as mappings from point to point: Two-dimensional affine mapping represented in expressions 1 to 3; two-dimensional quadratic form mapping represented in expressions 4 to 6; and planar perspective mapping represented in expressions 7 and 8.
They represent the correspondence between projection images produced by relative motion between an object and a camera sufficiently distant from each other, an instantaneous move of a plane, and an arbitrary move of a plane.
Here, (x, y) and (x′, y′) denote the corresponding image positions between different projection images, superscript letter t denotes transpose of a vector, a matrix, and solid letter x represents coordinates (x, y).
Two-dimensional affine mapping:
x′=P
a
(
x
)
a
(1)
P
a
(
x
)
=
(
x
y
1
0
0
0
0
0
0
x
y
1
)
(
2
)
Parameters of two-dimensional affine mapping:
a
=(
a
0
,a
1
,a
2
,a
3
,a
4
,a
5
)′ (3)
Two-dimensional quadratic form mapping:
x′=P
q
(
x
)
q
(4)
P
q
(
x
)
=
(
x
y
x
2
xy
1
0
0
0
0
0
xy
y
2
0
x
y
1
)
(
5
)
Parameters of two-dimensional quadratic form mapping:
q
=(
q
0
,q
1
,q
2
,q
3
,q
4
,q
5
,q
6
,q
7
)′(6)
Plane perspective mapping:
x
′
=
f
(
x
;
p
)
=
(
p
0
x
+
p
1
y
+
p
2
p
6
x
+
p
7
y
+
1
p
3
x
+
p
4
y
+
p
5
p
6
x
+
p
7
y
+
1
)
(
7
)
Parameters of plane perspective mapping:
p
=(
p
0
,p
1
,p
2
,p
3
,p
4
,p
5
,p
6
,p
7
)′ (8)
If the parameters of each mapping are defined, a function of determining the positional correspondence between different images is defined. If the six parameters shown in expression 3 are found in the two-dimensional affine mapping, the correspondence between the images is described; if the eight parameters shown in expression 6 are found in the two-dimensional quadratic form mapping, the correspondence between the images is described; and if the eight parameters shown in expression 8 are found in the planar perspective mapping, the correspondence between the images is described.
The mapping representing the correspondence between the images is not limited to the point-to-point correspondence; a more general mapping from a position set on one image to a position set on the other is also possible. In the above-described point-to-point correspondence, there is a restriction (plane) on the projection condition and the structure of an object, but mapping generally holding between the different projection images of a rigid body is known as epipolar geometry. It is a mapping from a line to a line, called epipolar mapping in the specification. A mapping from a point to a line exists as generalization of the epipolar mapping. It is represented in expressions 9 and 10 and will be referred to as generalized epipolar mapping. Generalized epipolar mapping:
Line, 1:
{
x
′
|
x
′
-
t
F
x
~
=
0
}
(
9
)
F in expression 9 denotes a 3×3 matrix called a fundamental matrix and symbol ~ denotes homogeneous coordinate representation shown in expression 10 (two-dimensional position coordinates are represented as a three-dimensional vector as (x, y,
1
) rather than (x, y)). For the generalized epipolar mapping, x′ mapped from x satisfies an equation of a line represented by the matrix F. That is, a point is mapped to a line. The mapping parameter is the matrix F itself (a detailed description of the epipolar mapping will be again given in Embodiment).
To find the mapping parameters, hitherto, a method based on feature point correspondence or a method using direct minimization of an intensity error has been used. The planar perspective mapping is taken as an example.
Since the number of parameters to be found is eight in the planar perspective mapping, if four-point correspondence is obtained between different projection images, a function can be defined.
Eight simultaneous equations are obtained from expression 7 with respect to the four-point correspondence, whereby the mapping parameters can be calculated easily. The parameters of the two-dimensional affine mapping can be found from six simultaneous equations in the three-point correspondence and those of the two-dimensional quadratic form mapping can be found from eight simultaneous equations in the four-point correspondence.
{tilde over (x)}
=(
x,y
,
1
)′,
{tilde over (x)}
′=(
x′,y′
,
1
)′, (10)
For the generalized epipolar mapping, a method based on eight-point correspondence by Longuet-Higgins is disclosed in document “H. C. Longuet-Higgins, “A computer algorithm for reconstructing a scene from two projections,” Nature vol. 293, pp. 133-135, 1981.” In the specification, such a method based on the feature point correspondence of projection images will be referred to as a parameter estimation method based on feature point correspondence.
The method of direct minimization of an intensity error is disclosed in, for example, “R. Szeliski, “Video Mosaics for Virtual Environment,” IEEE Computer Graphics and Applications, pp.22-30, March 1996.”
E
=
∑
i
[
I
′
(
x
i
′
,
y
i
′
)
-
I
(
x
i
,
y
i
)
]
2
=
∑
i
e
i
2
(
11
)
This method is to minimize a intensity error defined in expression 11 with respect to the whole screen.
In expression 11, I (xi, yi) represents the intensity of the ith pixel and I′ (xi′, yi′) denotes the intensity at the corresponding point of a different projection image.
Here, the planar perspective mapping defined in expression 7 is used as the mapping and the parameters of the planar perspective mapping are found. In the example in the related art, the intensity error is defined as a square error in expression 11, thus minimization of expression 11 is executed according to Levenberg-Marquart method. The details of the Levenberg-Marquart method are disclosed in “W. H Press et al. “Numerical Receipes in C: The art of Scientific Computing,” Cambridge Univ. Press 1992.”
In the example in the related art, the following steps are repeated for finding mapping parameter p:
Step 1: First, ei shown in expression 11 is calculated from an image.
Step 2: First-order partial differential of expression 11 is found according to expression 12.
∂
e
i
∂
p
0
=
x
i
D
i
∂
I
′
∂
x
′
,
⋯
,
∂
e
i
∂
p
7
=
-
y
i
D
i
[
x
i
′
∂
I
′
∂
x
′
+
y
i
′
∂
I
′
∂
y
′
]
(
12
)
In expression 12, Di is a denominator of expression 11, namely, expression 13.
D
i
=p
6
x
i
+p
7
y
i
+1 (13)
Step 3: Using expression 12, 8×8 matrix A having element ak
1
and column vector b having element bk are found as shown in expression 14.
a
k1
=
∑
i
∂
e
i
∂
e
i
∂
p
k
∂
p
l
,
b
k
=
∑
i
&it
Etoh Minoru
Hata Kouichi
Johnson Timothy M.
Pearne & Gordon LLP
Tabatabai Abolfazl
LandOfFree
Correspondence-between-images detection method and system does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Correspondence-between-images detection method and system, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Correspondence-between-images detection method and system will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3015104