Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1997-02-20
2002-12-10
Ahmed, Samir (Department: 2623)
Image analysis
Pattern recognition
Template matching
C382S199000
Reexamination Certificate
active
06493465
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to a matching point extracting method, in determining distance information on an object based on plural images of such an object taken from mutually different positions, for extracting mutually matching points in such images.
2. Related Background Art
Such an apparatus for extracting the matching points of the images has conventionally been utilized, for example, in producing a control program for a moving robot or cutting out the image data of a predetermined object from image data of a phototaken image.
In such a matching point extracting apparatus, for determining the distance to the object in the image, there are known, for example, a method shown in
FIG. 1A
of employing two or more cameras
133
a
,
133
b
for taking the images of the object
131
from different viewing points and utilizing the parallax between the images obtained by such cameras
133
a
,
133
b
, and a method shown in
FIG. 1B
of employing one camera
134
, and moving such a camera
134
for taking the images of the object
132
from different viewing points and utilizing the parallax between the time-sequentially obtained images. In these methods shown in
FIGS. 1A and 1B
, the extraction of the matching points is executed for obtaining the parallax required in the determination of the object distance.
More specifically, in the method shown in
FIG. 1A
, the matching points are determined in all the points (pixels) in the image data of the image obtained by the left-side camera
133
a
and in those of the image obtained in synchronization by the right-side camera
133
b
. Also in the method shown in
FIG. 1B
, the matching points are determined in all the points (pixels) in the image data of an image obtained at a certain position and in those of another image obtained at a position after movement. The determination is made in all the pixels (points) of the image data because the area of the object within the image is not known.
Among the representative methods for such a matching point extraction, there is known a template matching method. In this method, around a point P for which a matching point is to be determined, in
FIG. 2A
, a template (template image)
143
is prepared as shown in FIG.
2
A and is moved over the entire area of a searched image
142
as shown in
FIG. 2B
, with a calculation of the similarity at every point and a point showing the highest similarity is determined as the matching point.
As the evaluation function for determining the similarity, there can be employed a following function (1) utilizing the difference in the luminance (pixel values) or a following function (2) utilizing the correlation of the luminance (pixel values):
E
(
x
,
y
)
=
∑
i
∑
j
[
F
(
i
,
j
)
-
A
(
i
-
x
,
j
-
y
)
]
2
(
1
)
σ
(
x
,
y
)
=
∑
i
∑
j
{
(
i
,
j
)
-
A
(
i
-
x
,
j
-
y
)
}
∑
i
∑
j
F
2
(
i
,
j
)
·
∑
i
∑
j
A
2
(
i
,
j
)
(
2
)
In the foregoing equations (1) and (2), F(i, j) indicates the luminance value of the pixel at a coordinate (i, j) on the template image, and A(i, j) indicates the luminance value of the pixel at a coordinate (i-x, i-y) on the image to be searched (hereinafter, called a search image). Thus, the function (1) or (2) represents the similarity when the position of the template image is moved by (x, y) on the search image.
With the function (1), the matching point is indicated at a point where E(x, y) reaches a minimum, which can theoretically reach 0 at a minimum. With the function (2), the matching point is indicated at a point where &sgr;(x, y) reaches a maximum, which can theoretically reach 1 at a maximum.
For determining the similarity there is also known the following other evaluation function (3). It determines the number of pixels, within the entire template, for which the difference between the luminance value (pixel value) of such a pixel and the luminance value of a pixel in the search image is within a predetermined threshold value &egr;, namely it determines the numbers of the pixels in the template, having differences in the luminance value within a predetermined value from each pixel of the search image, and a point on the search images showing the largest number of such pixels is defined as the matching point to the center point of the template:
kij
=
{
1
(
&LeftDoubleBracketingBar;
F
(
i
,
j
)
-
A
(
i
-
x
,
j
-
y
)
&RightDoubleBracketingBar;
<
ϵ
)
0
(
&LeftDoubleBracketingBar;
F
(
i
,
j
)
-
A
(
i
-
x
,
j
-
y
)
&RightDoubleBracketingBar;
≥
ϵ
)
C
(
x
,
y
)
=
∑
i
∑
j
kij
(
3
)
With this function (3), the matching point is indicated at a point where C(x, y) reaches a maximum, which can theoretically reach the number of all the pixels in the template at a maximum.
Conventionally, the object distance is determined from the images, by extracting the matching points from the images, determining the amount of parallax in each point of the image, and effecting trigonometry based on such amount of parallax, focal length and positional information of the camera.
Such a template matching method, however, in extracting the matching points between the images that have recorded an object at a finite distance from the cameras, has been associated with a drawback that the precision of extraction becomes significantly deteriorated at a certain portion of the object.
Such a drawback will be explained with reference to
FIGS. 3A
to
3
C, which show images having recorded a car as the main object, by the two cameras
133
a
,
133
b
shown in
FIG. 1A
, wherein
FIG. 3A
shows an image obtained by the left-side camera
133
a
while
FIGS. 3B and 3C
show images obtained by the right-side camera
133
b
. For the convenience of explanation, the car is considered as the main object while the house and the tree are considered as the background and are assumed to be distant from the car and positioned in the back of the scene.
Now, there is considered a case of cutting out a template (template image) from the image shown in
FIG. 3A
, taken as a reference image. In this operation, a certain size is required for the template.
This is because the area of a point A in the sky or a point B in the door of the car in the image shown in
FIG. 3A
shows little change in the luminance, lacking conspicuous features and having similar luminance values therearound. Also, the area of superposed leaves of the tree at a point C has the area of similar luminance distribution therearound, and, for the extraction of exact matching points in such areas A, B and C, the template needs a certain size for detecting the variation in the distribution of the luminance.
For example, if the template is defined in the illustrated size around the point B in
FIG. 3A
, the template
151
contains a type in addition to the door of the car, thus showing a large variation in the luminance and allowing an exact determination of the matching point.
Now, let us consider a point D at an end of the car, which is the main object in the image shown in FIG.
3
A. If the template
152
is prepared around the point D, with a same size as around the point B, the template
152
includes the house in the background, in addition to the car constituting the main object. The matching point extraction with such a template
512
results as shown in
FIG. 3C
, in an erroneous matching point F instead of the correct matching point E.
Such an erroneous matching results from a fact that, in the calculation of the evaluation function (similarity) in the example shown in
FIGS. 3A
to
3
C, with respect to a point E of the search image, an area corresponding to the car in the template image shows a high similarity because the image remains the same in the template image and in the search image and an
Iijima Katsumi
Mori Katsuhiko
Yano Kotaro
Ahmed Samir
Canon Kabushiki Kaisha
Fitzpatrick ,Cella, Harper & Scinto
LandOfFree
Matching point extracting method and apparatus therefor does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Matching point extracting method and apparatus therefor, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Matching point extracting method and apparatus therefor will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2932454