Image analysis – Pattern recognition – Template matching
Reexamination Certificate
2000-01-04
2002-05-07
Chang, Jon (Department: 2623)
Image analysis
Pattern recognition
Template matching
C382S278000, C382S291000
Reexamination Certificate
active
06385340
ABSTRACT:
TECHNICAL FIELD
The present invention relates to a system for digital processing of images and deals more particularly with a system for automatically locating patterns that are characterized by edges. A specially constructed template is moved about various points in the image to locate a pattern. As the template scans the image, it is altered in a manner that is dependent on how well it fits the image pattern at the various points.
BACKGROUND OF THE INVENTION
Introduction
In electronic digital image processing hardware, images are stored in discrete memory devices. The image is often segmented into an array of values, where each memory location corresponds to a particular spatial coordinate point and the value at that memory location, called a picture element (pixel), corresponds to the brightness of the image at that coordinate point.
FIG. 1A
shows an example of an object in an image where the brightness is given by numbers at each pixel coordinate point.
Image and Template Correlation
One common technique to automatically locate objects in an image of a machine vision system is to use a correlation or convolution. There are several types of image correlation methods including convolution, normalized correlation, the least mean squares error, and the least mean absolute error. A definition of a correlation method requires the determination and use of a template or kernel which is a separate small image with the same shape as the object to be located.
FIG. 1B
shows a template shaped like the object shown in the image of FIG.
1
A. Like the object, the template may be represented by spatial coordinate points with a brightness value for each point. The template is selectively displaced and moved from location to location around a region of interest in the image. At each new template location in the image the sum of products is computed for the value of a template pixel with each corresponding image pixel at a common spatial coordinate point.
FIG. 1C
shows one location of the template in
FIG. 1B
displaced on the image. In this case there is no overlap at that displacement, and the sum of products is zero. The computational output of the correlation or convolution is at a maximum at the location where the shape of the template pattern most closely matches the shape of a pattern in the image.
FIG. 1D
shows the correlation for all possible displacements of the template across the image. The numeric values are rather large, so
FIG. 1D
shows only an approximate and relative indication of the correlation by the intensity of shading.
The formula for a discrete two dimensional convolution is given by
corr
(
x
,
y
)
=
∑
u
∑
v
I
(
x
-
u
,
y
-
v
)
K
(
u
,
v
)
(
1
)
where I is an image, K is a kernel, and x and y are image coordinates defining a spatial coordinate point. The summation over u and v range over the template. In practice, the template is smaller than the image containing the object whose location is being determined.
Normalized correlation is a well known method similar to correlation, except that the value of each element of the template is multiplied by a constant scale factor, and a constant offset is added. At each template displacement the scale factor and offset are independently adjusted to give a minimum error in the correlation of the template at each image location. The normalized correlation method in template matching is covered in detail in an article entitled “Alignment and Gauging Using Normalized Correlation Search” by William Silver, in
VISION'
87
Conference Proceedings,
pp. 5-33-5-55, which is incorporated herein by reference.
In the least mean squared error method each template point is subtracted from the corresponding image point; each difference is squared; and the average of all differences are computed. The formula for the least squared error is
E
2
(
x
,
y
)
=
I
N
∑
u
∑
v
(
I
(
x
-
u
.
y
-
v
)
-
K
(
u
,
v
)
)
2
(
2
)
where N is the number of pixels in the kernel. The computational output of the least mean squared error is at a minimum where the template pattern matches a pattern in the image. In the least mean absolute error method each template point is subtracted from the corresponding image point; the absolute value of each difference is computed; and the average of all differences are computed. The formula for the least absolute error is
E
(
x
,
y
)
=
I
N
∑
u
∑
v
abs
I
(
I
)
(
x
-
u
,
y
-
v
)
-
K
(
u
,
v
)
I
(
3
)
The computation output of the least mean absolute error is also at a minimum where the patterns match.
The techniques described above are substantially the same in the sense that a template, itself is a gray level image, is displaced from location to location about a corresponding gray level image containing an object whose coordinate location is within the image is of interest. At each location a function is applied to neighboring image pixel values and the corresponding template values at common coordinate points. The result is another image where each pixel at a coordinate point is a single number that represents how well the template fits the object in the image at that point.
Binary Vector Correlation
Vector correlation or convolution provides an alternative approach to the correlation methods discussed above. In vector correlation the image and selected template are composed of pixels which are vectors. The theory behind binary vector correlation is covered in a paper entitled “Vector Morphology and Iconic Neural Networks” by S. S. Wilson in
IEEE Transactions on Systems, Man, and Cybernetics,
November/December, 1989, vol. 19, no. 6, pp. 1636-1644, which is incorporated by reference. A similar technique was further discussed in the paper entitled “Teaching network connections for real-time object recognition”, by S. S. Wilson in
Neural and Intelligent Systems Integration,
pp. 135-160, Wiley-Interscience, 1991. Briefly, the most common form of binary vector correlation consists of transforming a gray level image to several binary images, where the composite of binary images represents a vector in the sense that each pixel in the vector image has several components—each from one of the binary images. Next, a vector template is defined for the purpose of recognizing a pattern. The vector template also consists of the same number of components as the vector image.
The position of the vector template is displaced and moved from location to location around the region of interest in the image. At each location, the sum of inner products (or dot product) is computed for a vector pixel in the template and a vector pixel in the image for a corresponding coordinate point. In mathematical terms, the formula for a discrete two dimensional vector convolution is given by
corr
(
x
,
y
)
=
∑
u
∑
v
I
(
x
-
u
,
y
-
v
)
·
K
(
u
,
v
)
(
4
)
where I is a vector image and K is a vector kernel, and x and y are image coordinates. The summation over u and v range over the template.
A detailed description of one technique of vector correlation follows. Starting with an input image, the first step is to form another image called the horizontal finite difference by subtracting from the value of a pixel of the input image, the value of a neighboring pixel displaced a small distance to the right. The resulting image will contain large positive or negative values around those coordinate points where there is a significant vertical edge. A positive value in the horizontal finite difference image is called an east edge and represents an edge that decreases in intensity from left to right. A negative value in the horizontal finite difference image is called a west edge and represents an edge that increases in intensity from left to right.
The second step is to form another image called the vertical finite difference by subtracting from the value of a pixel of the input image, the value of a neighboring pixel displaced a small distance upward. The resulting ima
Applied Intelligent Systems Inc.
Chang Jon
Young & Basile
LandOfFree
Vector correlation system for automatically locating... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Vector correlation system for automatically locating..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vector correlation system for automatically locating... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2858692