Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1997-12-19
2001-06-19
Au, Amelia M. (Department: 2623)
Image analysis
Pattern recognition
Template matching
C382S270000
Reexamination Certificate
active
06249608
ABSTRACT:
BACKGROUND OF THE INVENTION
The present invention relates to a field of a computer application apparatus, especially an image processor and an image processing apparatus using it.
Furthermore, more in detail, the present invention is related with template matching to extract a region resembling a template image from an object image, and with moving-average filtering for an image data of each pixel, which are executed by using pixels in a rectangular filtering region including the pixel, in an object image, the size of the rectangular region being preset.
The present invention relates to a pattern recognition method and an apparatus using the method which are used for positioning elements in a semiconductor apparatus, searching parts in a FA line, a remote sensing, and so forth.
In various fields using an image processing, a template matching method is used to search a partial area in an image (referred to as a search image) obtained by a sensor, which resembles a specified image pattern (referred to as a template). Such a template matching method is disclosed, for example, in “Image Analysis Handbook”, by Mikio Takagi and Akihisa Shimoda, University of Tokyo Press (1991). In a template matching method, it is often performed that each pixel is represented by a n-bit data for expressing a multilevel gradation image data, and a normalized correlation coefficient is used as a measure for a similarity of patterns. A normalized correlation coefficient r(i, j) is expressed by the following equation in which t(m, n) (m=0, 1, . . . , M−1; n=0, 1, . . . , N−1) is a data value of a pixel in a template, s(i+m, j+n) (m=0, 1, . . . , M−1; n=0, 1, . . . , N−1); and (i, j) is a starting point of a sub-image) is the sub-image in a search image, of which a similarity to the template is to be evaluated, and P is the number of pixels in the template.
r
(
i
,
j
)
=
∑
n
=
0
N
-
1
∑
m
=
0
M
-
1
(
s
(
i
+
m
,
j
+
n
)
·
t
(
i
,
j
)
)
-
1
P
(
∑
n
=
0
N
-
1
∑
m
=
0
M
-
1
(
s
(
i
+
m
,
j
+
n
)
)
·
(
∑
n
=
0
N
-
1
∑
m
=
0
M
-
1
t
(
i
,
j
)
)
∑
n
=
0
N
-
1
∑
m
=
0
M
-
1
(
s
(
i
+
m
,
j
+
n
)
)
2
-
1
P
(
∑
n
=
0
N
-
1
∑
m
=
0
M
-
1
s
(
i
+
m
,
j
+
n
)
)
2
·
∑
n
=
0
N
-
1
∑
m
=
0
M
-
1
(
t
(
i
,
j
)
)
2
-
1
P
(
∑
n
=
0
N
-
1
∑
m
=
0
M
-
1
t
(
i
,
j
)
)
2
(
2
)
In performing template matching, the above-described normalized correlation coefficient is obtained for each of a plurality of sub-images, and one or plural sub-images which are determined to resemble a template are selected in accordance with the obtained normalized correlation coefficients. A method using a normalized correlation coefficient can perform template matching without receiving effects of variations between image data values of pixels in a template image and those of pixels in a search image, the variation being caused, for example, by changes in lighting.
Since calculation steps or data amount to be calculated are very huge in a pattern matching method using the above-mentioned normalized correlation coefficient, a method for efficiently obtaining a normalized correlation coefficient has been investigated.
In one of existing methods for performing a template matching method at a high speed, absolute values of differences between image data values of pixels in a template image and those of pixels in a sub-image to be processed, of a search image, are accumulated while a normalized correlation coefficient is obtained for the sub-image, and the process for calculating the normalized correlation coefficient is closed, if a sum of the accumulated absolute values exceeds a preset threshold value.
In the above-mentioned existing measure, since the accumulated sum of absolute values of differences between image data values of pixels in a template image and those of pixels in a sub-image to be processed is used to close a process for obtaining a normalized correlation coefficient, there exists a problem in which if variations of image data values of pixels in a template image and those of pixels in a sub-image of a search image are caused, for example, by changes in lighting, a process for obtaining a normalized correlation coefficient is wrongly closed for even a sub-image which has a high similarity to the template image because of the large accumulated sum of absolute value of the differences. In the following, this problem will be explained in detail with reference to FIG.
13
and FIG.
14
.
FIG. 13
is an example of a template image, and
FIG. 14
is an example of a search image for which a sub-image resembling the template image is searched. In these figures, squares shows pixels, and values shown in the squares indicate levels in gradation of images. The similarity between two images is to be determined, not based on the nearness between absolute image data values of pixels in the two images, but on the nearness between relative local changing tendencies in image data values of pixels in the two images. Therefore, a sub-image, in the search image shown in
FIG. 14
, most resembling the template image shown in
FIG. 13
, is a sub-image shown at the right-upper part in
FIG. 14
, which are composed of pixels
1403
,
1404
,
1405
,
1408
,
1409
,
1410
,
1413
,
1414
and
1415
. In fact, a normalized correlation coefficient between the template image and the sub-image is 1.0. However, the value in a accumulated sum of absolute values of difference between image data values, which is used to close a process for obtaining a normalized correlation coefficient in the existing methods, is 360 for the sub-image at the right-upper part, and is much larger than 80 for a sub-image at the left-lower part, which is composed of pixels
1411
,
1412
,
1413
,
1416
,
1417
,
1418
,
1421
,
1422
and
1423
. Therefore, if a threshold value of the accumulated sum, which is set to close a process for obtaining a normalized correlation coefficient, is preset to a value in a range 80 to 460, the sub-image at the left-lower part is searched, but searching the sub-image at the right-upper part is closed in the midst. Hereupon, the sub-image at the left-lower part is an image of a laterally striped pattern.
Furthermore, in many cases including the above example, it is difficult to set an adequate threshold value for the above-mentioned accumulated sum.
Furthermore, an image processing technique is indispensable to fields using a microscope, medical equipment, etc., and also to a remote sensing technique, an inspection technique of a product, etc. In image processing, a filtering method to remove noise components, or to improve the quality of a processed image takes an important role, and various algorithms for implementing filtering methods have been devised, and some of them have been incorporated into hardware systems.
A moving-average filtering method used as one of filtering methods performs filtering for an image data of each object pixel in an image to be processed, by averaging image data values of pixels in a rectangular region including the object pixel, the size of the rectangular (kernel size) being usually preset. In the following, outline of a moving-average filtering method will be explained with reference to
FIGS. 35A and 35B
. Hereupon,
FIG. 35A
is an image composed of 9 pixels in the column direction (the lateral direction)×8 pixels in the row direction. Numerals
211
-
289
indicate pixels.
FIG. 35B
shows an image obtained by executing moving-average filtering with a kernel size of 5 pixels×5 pixels, for image data of pixels shown in FIG.
35
A. Numerals
211
′-
289
′ indicated pixels of which image data values were filtered. For example, an image data value of a pixel
233
′ is an average value of image data values of pixels in a region for 5 pixels in the row direction and 5 pixels in the column direction, in which the pixel
2
Hotta Takashi
Ikeda Mitsuji
Katsura Koyo
Nakashima Keisuke
Shibukawa Shigeru
Au Amelia M.
Hitachi , Ltd.
Kenyon & Kenyon
Miller Martin
LandOfFree
Template matching image processor utilizing sub image pixel... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Template matching image processor utilizing sub image pixel..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Template matching image processor utilizing sub image pixel... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2506496