Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1998-01-06
2001-08-07
Bella, Matthew C. (Department: 2621)
Image analysis
Pattern recognition
Template matching
C382S217000, C358S451000
Reexamination Certificate
active
06272246
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to a positioning device for carrying out a pattern-matching process.
BACKGROUND OF THE INVENTION
Conventionally, positioning of an object is carried out by a pattern-matching process using a template. In accordance with this pattern-matching process, a window is set in image data obtained by photographing the object, and the degree of coincidence or the degree of similarity between the image of the object within the window and a reference image that has been preliminarily registered is calculated. By carrying out these calculations as well as successively scanning the window within the image data, it is possible to find out the position at which the highest degree of coincidence or the highest degree of similarity is obtained, and the positioning is carried out based upon this position.
Correlation coefficients are used as one of the indicators for the degree of similarity. In this method, for example, a reference image with N×N pixels, preliminarily registered, is superposed on a search area (M−N+1)×(M−N+1) within the target image with M×M pixels that is larger than the reference image. Further, it is and shifted so as to find the position of the upper left corner of the reference image that makes the result of the following equation (1) maximum.
c
(
a
,
b
)
=
∑
m
=
0
N
-
1
∑
n
=
0
N
-
1
{
I
(
a
,
b
)
(
m
,
n
)
-
I
_
}
{
T
(
m
,
n
)
-
T
_
}
(
I
σ
a
,
b
·
T
σ
)
where
I
_
=
1
N
2
∑
m
=
0
N
-
1
∑
n
=
0
N
-
1
I
(
a
,
b
)
(
m
,
n
)
T
_
=
1
N
2
∑
m
=
0
N
-
1
∑
n
=
0
N
-
1
T
(
a
,
b
)
(
m
,
n
)
I
σ
a
,
b
=
1
N
2
∑
m
=
0
N
-
1
∑
n
=
0
N
-
1
{
I
(
a
,
b
)
(
m
,
n
)
-
I
_
}
2
T
σ
=
1
N
2
∑
m
=
0
N
-
1
∑
n
=
0
N
-
1
{
T
(
m
,
n
)
-
T
_
}
2
(
1
)
In the above equation (1), (a, b) indicates the upper right corner of the reference image within the target image, I
(a, b)
(m, n) indicates a partial image within the target image, and T(m, n) indicates the reference image.
However, since the above-mentioned equation (1) requires a large amount of calculations, the application of the equation results in a problem of requirement of large-scale hardware upon carrying out operations at high speeds. In general, in order to solve this problem, an approximate positioning, that is, a rough search, is carried out on an image with a reduced resolution so as to find out candidate points. Further, a more accurate positioning is carried out in the proximity of these candidate points.
Here, in one of the known positioning devices (for example, Japanese Laid-Open Patent Publication No. 157577/1992 (Tokukaihei 4-157577)), a gradation conversion, which converts the density bit numbers of the original images of the reference image and a target image into fewer density bit numbers, is carried out so as to reduce the amount of calculations required for the positioning. The the degree of coincidence between the edge of the reference image and the edge of the target image is calculated by carrying out noise elimination and edge extraction.
In the above-mentioned positioning device, as disclosed in Japanese Laid-Open Patent Publication No. 157577/1992 (Tokukaihei 4-157577), however, upon carrying out the gradation conversion between the original images of the reference image and the target image so as to reduce the amount of calculations required for the positioning between the reference image and the target image, the gradation of the original image is merely compressed by eliminating lower bits by carrying out dividing operations, etc., regardless of the contrast of the image.
However, in the case of poor contrast in the original image, such as in the case of target images that are too dark or too bright, the image obtained after the gradation conversion tends to become an image with extremely few gradations. In such a case, the further the density bit number after the gradation conversion is reduced, the worse the operation accuracy in the degree of similarity on correlation coefficients, etc., Further, since effective bits related to contrast tend to be buried and become inconspicuous, it is difficult to carry out the rough search effectively.
SUMMARY OF THE INVENTION
The objective of the present invention is to provide a positioning device which, even if the contrast of an original image is poor, can reduce the amount of calculations for finding the degree of similarity between the reference image and the target image without impairing the operation accuracy in finding the degree of similarity, and consequently can carry out an effective rough search.
In order to achieve the above-mentioned objective, the positioning device of the present invention, which is a positioning device for carry out a positioning between a preliminarily registered reference image and a newly inputted target image, is provided with: a first calculating section for calculating the features of the target image; a first gradation conversion section which converts the gradation of the target image so as to produce a rough target image based upon the results of calculations in the first calculating section so that information related to contrast of the target image is maintained to a greater extent, and so that the number of density levels of the target image is reduced; a rough search section for finding the degree of similarity between a rough reference image whose gradation has been converted and the rough target image so as to find a maximum matching candidate point; and a precise search section for finding a maximum matching point between the reference image and the target image in the proximity of the maximum matching candidate point.
With the above-mentioned arrangement, the gradation converting operation in the first gradation conversion section is adjusted in accordance with the features of the target image that have been calculated by the first calculating section. As a result, even if it merely has low gradation as compared with the target image, the rough target image, produced by the first gradation conversion section, contains more information related to contrast of the target image as compared with the case in which the target image is always gradation-converted by the same gradation-converting operation, such as a case in which the gradation is simply compressed.
Consequently, even in the case when the target image has less density change (has poor contrast), such as in cases when the target image is dark as a whole and when it is bright as a whole, the rough search section can maintain proper operation accuracy in finding the degree of similarity. Therefore, as compared with the prior-art arrangement in which the rough search section has an extreme degradation in its operation accuracy in the case of poor contrast, it becomes possible to improve the operation accuracy and consequently to carry out the rough search more effectively.
Moreover, the rough search section finds a maximum matching candidate point based upon the rough target image with low gradation and the rough reference image, and the precise search section finds a maximum matching point in the proximity of the maximum matching candidate point based upon the reference image and target image with high gradation Therefore, as compared with a case where the maximum matching point is directly found from the target image and the reference image, the amount of calculations can be greatly reduced, and the circuit scale of the positioning device can be minimized.
Meanwhile, various arrangements are proposed with respect to the construction in which the gradation-converting operation of the first gradation conversion section is adjusted in accordance with the features of the target image. For example, in one pr
Bella Matthew C.
Desire Gregory
Sharp Kabushiki Kaisha
LandOfFree
Positioning device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Positioning device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Positioning device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2453375