Image analysis – Applications – 3-d or stereo imaging analysis
Reexamination Certificate
2000-01-20
2002-11-12
Boudreau, Leo (Department: 2721)
Image analysis
Applications
3-d or stereo imaging analysis
C382S106000, C382S173000, C382S190000, C348S047000, C356S011000, C356S012000
Reexamination Certificate
active
06480620
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a method of and an apparatus for 3-dimensional structure estimation which is used for obtaining 3-dimensional information of an object from 2-dimensional image data of the object, and more particularly to those based on triangular surveying making use of multiple sets of 2-dimensional image data of an object taken from multiple viewing positions.
There is a 3-dimensional structure estimation technique called stereo-method, which estimates 3-dimansional structure of an object based on the triangular surveying from multiple sets of 2-dimensional image data taken from multiple viewing positions. A conventional example of the stereo-method is described in a paper entitled “A Multiple-Baseline Stereo” by Okutomi et al, IEEE Transaction on Pattern Analysis and Machine Intelligence, pp. 353-363, Vol. 15, No. 4, April 1993.
First, principle of the stereo-method is described referring to a schematic diagram of FIG.
6
.
Suppose a first camera
10
-
1
, with a lens having a focal distance F, which is positioned on an X-Y plane, perpendicular to the sheet of
FIG. 6
, so that center of the lens is at coordinates (X
1
,
0
) and optical axis is perpendicular to the X-Y plane, and a second camera
10
-
2
, with its lens having the same focal distance F, which is positioned parallel to the first camera
10
-
1
so that center of its lens is at coordinates (X
2
,
0
).
Defining the coordinates (X
1
,
0
) and (X
2
,
0
) as viewing positions of the first camera
10
-
1
and the second camera
10
-
2
, respectively, a distance B =X
2
−X
1
between the two viewing positions is hereafter called the baseline B of the first and the second camera
10
-
1
and
10
-
2
.
When a first and a second picture of an object
1
are taken by the first and the second camera
10
-
1
and
10
-
2
having the baseline B, and a position P of the object
1
is projected at points p
1
and p
2
of the first and the second picture, that is, on focal planes of the first and the second camera
10
-
1
and
10
-
2
, respectively, a disparity d between the points p
1
and p
2
is represented as follows:
d=x
2
−x
1
=BF/z,
(1)
where x
1
and x
2
are x-components of coordinates of the points p
1
and p
2
on x-y planes having their origins on the centers of the first and the second picture, respectively, and z is a depth, that is, a distance to the X-Y plane of the position P of the object
1
.
Therefore, information of
3
-dimensional structure of the object
1
can be estimated from the disparity d if each point p
1
of the first picture is known to correspond to which point p
2
of the second picture.
In general, the stereo-method is performed according to an algorithm wherein a depth z at an interesting point p
1
of the first picture is estimated by retrieving a point p
2
of the second picture having correspondence to the interesting point p
1
, and by repeating above procedure for each point p
1
of the first picture, depth of each position P of the object
1
is estimated on the first picture taken by the first camera
10
-
1
.
In many algorithms, the correspondence is discriminated when an evaluation value such as brightness difference between the concerning two points p
1
and p
2
, or sum of brightness differences between two small regions around the concerning two points p
1
and p
2
becomes minimum in a retrieving range defined as follows. When a possible depth z to be obtained is between z
min
to z
max
, the disparity d should be between d
min
=BF/z
max
to d
max
=BF/z
min
from the equation (1).
Therefore, the corresponding point P
2
should be retrieved in a range x
1
+d
min≦x
2
≦x
1
+d
max
.
In some algorithms, points in the retrieving range showing the evaluation value, brightness difference for example, within a threshold value are selected as candidates of the corresponding point, and one of the candidates which gives the most smooth variation of the depth z is determined as the corresponding point. Further, when there is known an obstacle
2
as illustrated in
FIG. 7
in front of the object
1
, correspondence retrieved in a range where the obstacle
2
should exists are rejected in many algorithms as correspondence physically impossible.
Returning to the equation (1), the disparity d is in proportion to the baseline B for the same depth z, and preciseness of the disparity d is limited according to the picture resolution. Therefore, the larger disparity d gives the higher precision of the estimated depth z, and the longer baseline B is preferable for the purpose. However, a longer baseline B gives a wider retrieving range as above described, causing a greater possibility of a false correspondence.
Therefore, there is a tradeoff between precision and false frequency of the estimation.
Techniques for dealing with this tradeoff can be classified into two methods. In one method, a coarse estimation is performed by retrieving correspondence between a pair of low resolution images, then a precise estimation is performed with a pair of high resolution images eliminating false correspondence inconsistent with the coarse estimation. Another approach is a method (hereafter called the multi-baseline stereo method) wherein multiple images of an object taken from multiple viewing positions having different baselines are used so that the evaluation value varies greatly according to whether there is correspondence or not.
In the prior paper beforehand mentioned of Okutomi et al., the latter approach, namely, the multi-baseline stereo method is applied.
Now, the multi-baseline stereo-method in the prior paper is described referring to a schematic diagram of FIG.
8
.
In
FIG. 8
, n pictures of an object
1
are taken by a first to n-th cameras
10
-
1
to
10
-n, each having a lens with a focal distance F and positioned at each of viewing positions (X
1
,
0
) to (X
n
,
0
) on an X-Y plane so as to have optical axis thereof perpendicular to the X-Y plane, n being a positive integer. Each of baselines B
1,2
to B
1,n
is that between the first camera
10
-
1
and each of the other cameras
10
-
2
to
10
-n. A position P having a depth z of the object
1
is projected at points p
1
to p
n
of the n pictures, x
1
to x
n
being distances of the points p
1
to p
n
in X-direction to centers of the n pictures.
Here, n−1 disparities d
1,2
to d
1,n
between n−1 pairs of points p
1
and p
2
to p
1
and p
n
are obtained as follows:
d
1
,
2
=
x
2
-
x
1
=
B
1
,
2
F
/
z
d
1
,
3
=
x
3
-
x
1
=
B
1
,
3
F
/
z
⋮
d
1
,
n
=
x
n
-
x
1
=
B
1
,
n
F
/
z
}
(
2
)
Therefore, for a depth estimation z of a position P, correspondence between n−1 pairs of points represented by the above equations (2) can be checked, enabling to improve the estimation precision making use of long baselines and reducing false correspondence at the same time.
In the algorithm of the multi-baseline stereo method, a similar step to the algorithm with two cameras described in connection with
FIG. 6
of retrieving a corresponding point to an interesting point p
1
of the first picture is performed for each of the other pictures taken by the second to the n-th cameras
10
-
2
to
10
-n, and above procedure is repeated for each point of the first picture.
In the algorithm with two cameras, the retrieving range is defined concerning the disparity d. However, in the multi-baseline stereo-method of the prior paper, the retrieving range is defined with an inverse distance 1/z, namely a reciprocal of the depth z, and the corresponding point giving a minimum of an evaluation value is retrieved in each of the other pictures according to the equations (2) by varying the inverse distance from
1
/z
max
to
1
/z
min
.
As to the evaluation value, sum of the sums of squared-difference values between small regions of each pair of pictures is applied in the prior paper.
FIG. 9
is a schematic diagram illustrating the small regions
115
-
1
to
115
-n of n pictures of
Boudreau Leo
Chawan Sheela
Foley & Lardner
LandOfFree
Method of and an apparatus for 3-dimensional structure... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of and an apparatus for 3-dimensional structure..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of and an apparatus for 3-dimensional structure... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2926626