Image analysis – Image transformation or preprocessing – Changing the image coordinates
Reexamination Certificate
1998-05-28
2001-03-27
Au, Amelia (Department: 2723)
Image analysis
Image transformation or preprocessing
Changing the image coordinates
Reexamination Certificate
active
06208769
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to signal processing and analysis and is particularly useful in the fields of image analysis and machine vision.
BACKGROUND OF THE INVENTION
In computer or machine vision applications, an image is represented by a two-dimensional array of pixels. Each pixel typically has one gray value or 3 values representing each of the basic colors. Each value is an integer between 0 and a saturation (maximum) value, such as 255 in a typical 8-bit system.
One of the most important applications of industrial machine vision systems is accurate positioning: determining the coordinates of a given object within the field of view. Many high-precision manufacturing systems require very accurate object positioning. One way to improve accuracy is to increase the resolution of the vision system, which requires more expensive cameras and slows down the processing, since the image analysis time is usually proportional to the number of pixels in the image. The alternative approach is to use more accurate methods to calculate the fractional (sub-pixel) position of a pattern.
The cost and timing constraints mentioned above require many manufacturing systems to have accuracy much higher than the image resolution (pixel size), with a maximum allowed error only a few hundredths of a pixel.
The most widely used method of pattern matching is a normalized correlation algorithm. The normalized correlation coefficient between image pixels I
i,j
and pattern (template) pixels T
i,j
is defined as:
n
*
∑
i
,
j
(
I
i
,
j
*
T
i
,
j
)
-
∑
i
,
j
I
i
,
j
*
∑
i
,
j
T
i
,
j
[
n
*
∑
i
,
j
I
i
,
j
2
-
(
∑
i
,
j
I
i
,
j
)
2
]
*
[
n
*
∑
i
,
j
T
i
,
j
2
-
(
∑
i
,
j
T
i
,
j
)
2
]
(
1
)
When the pixel values of the image are proportional to the corresponding pixel values of the template, i.e. I
i,j
=a+b*T
i,j
, with constant coefficients a and b, the normalized correlation coefficient reaches a maximum value of one (1.0).
If image pixel values are statistically independent of the template values, the correlation coefficient is close to zero (0.0). Thus defined, the normalized correlation score is insensitive to contrast and uniform lighting variation. This property makes it a very robust measure of similarity between two images.
Using normalized correlation for accurate match position determination typically involves two steps:
1. Search for a given pattern in the whole or part of the image. Find approximate positions of normalized correlation score maxima; and
2. Compute normalized correlation scores in a neighborhood around the approximate position of each local maximum. Fit a curve through this surface of score values, and compute the location of the maximum value on this curve.
The problem of interpolation of a smooth function from values sampled at regular grid intervals has received considerable attention in applied mathematics. Most interpolation algorithms are concerned with minimizing the error (absolute or mean square) between the interpolated and actual value at a given point (x,y).
One fairly simple and common way to find the maximum position is to approximate the function S(x,y) by a quadratic surface (paraboloid). This operation generally involves inverting a 6×6 matrix. The grid coordinates x and y are known beforehand, so the matrix can be inverted only once and the coefficients can be obtained by vector multiplication. After obtaining the coefficients, a simple linear transformation is required to reduce the quadratic form to a canonical one and find the position and value of the maximum.
This algorithm has been previously been implemented in commercial products developed by the assignee of this invention. It has an accuracy (maximum error in x or y direction) of about 0.05-0.1 pixel ({fraction (1/20)}-{fraction (1/10)} of pixels size).
SUMMARY OF THE INVENTION
Accordingly, the present invention features a method of accurately locating a sub-pixel maximum on a two-dimensional grid having a x and a y axis. The method, which is especially suitable for locating a sub-pixel maximum which falls intermediate grid point locations, includes the following steps.
First, a grid point location having a maximum grid point value is determined. Then, a quadrangle containing a sub-pixel maximum is determined by locating neighboring grid points along the x and y axes, which have the next greatest grid point values. Next, four one-dimensional, fractional maxima are computed, each one-dimensional, fractional maximum being located along each side of the four sides of the quadrangle. Once the four, one-dimensional, fractional maxima are computed, straight lines are computed which connect the one-dimensional, fractional maxima located on opposite sides of the quadrange. Finally, a location for the sub-pixel maximum is calculated as the location of the two computed lines.
Each one-dimensional, fractional maximum is calculated as follows:
First, a grid point location having a maximum grid point value (the “grid point maximum”) is located is identified by comparing grid point values of grid points located adjacent to and on opposite sides of the grid point maximum. Then a grid interval within which the one-dimensional, fractional maximum is located. Next, four sample grid points are selected. A first and second of the four sample grid points are located on a first side of the one-dimensional, fractional maximum. Third and fourth sample grid points are located on a second side of the one-dimensional, fractional maximum. Finally, a left and a right estimate of the position of the one-dimensional, fractional maximum are calculated using three-point parabolic approximations centered at grid points flanking the grid point maximum.
REFERENCES:
patent: 4275413 (1981-06-01), Sakamoto et al.
patent: 4897805 (1990-01-01), Wang
patent: 4918622 (1990-04-01), Granger et al.
patent: 5129051 (1992-07-01), Cain
patent: 5384648 (1995-01-01), Seidner et al.
patent: 5432898 (1995-07-01), Curb et al.
patent: 5495537 (1996-02-01), Bedrosian et al.
patent: 5511137 (1996-04-01), Okada
patent: 5602937 (1997-02-01), Bedrosian et al.
patent: 5671298 (1997-09-01), Markandey et al.
patent: 5689425 (1997-11-01), Sainio et al.
patent: 5717785 (1998-02-01), Silver
patent: 5930407 (1999-07-01), Jensen
patent: 5991463 (1999-11-01), Greggian et al.
patent: 6005978 (1999-12-01), Garakani
patent: 6009213 (1999-12-01), Miyake
Li et al., “Subpixel edge detection and estimation with a microprocessor-controlled line scan camera”, IEEE Transactions on Industrail Electronics, Feb. 1988.
Acuity Imaging, LLC
Au Amelia
Bourque & Associates P.A.
Miller Martin E.
LandOfFree
Method of accurately locating the fractional position of a... 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 accurately locating the fractional position of a..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of accurately locating the fractional position of a... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2440103