Image analysis – Pattern recognition – Template matching
Reexamination Certificate
1999-01-06
2001-04-17
Johns, Andrew W. (Department: 2621)
Image analysis
Pattern recognition
Template matching
Reexamination Certificate
active
06219452
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates to improved methods for performing pattern matching to locate one or more instances of a template image in a target image, wherein the invention includes an efficient method for characterizing the template image, improved methods for performing the pattern matching, and improved methods for locating rotated and/or scaled images.
DESCRIPTION OF THE RELATED ART
In many applications it is necessary or desired to find a template image or image object in a larger target image. Such applications include machine vision applications including process monitoring, feedback control, and laboratory automation; image and video compression; and jitter compensation in video cameras, among others.
Prior art pattern recognition systems have typically used a template matching technique wherein the stored image or pattern to be located, referred to as the template, is iteratively compared with various corresponding portions of an image in which it is desired to locate the template, referred to as the target image.
FIG. 1
illustrates the pattern matching problem as known in the prior art. As shown, the pattern matching problem involves a template image, wherein one or more instances of the template image are desired to be located in the target image. The template image and the target image are provided to a pattern matching algorithm which performs the pattern matching. The pattern matching algorithm generally operates to compare the pixels in the template image, or a selected subset of sample pixels, against each of the possible various locations in the target image. Typically, the pattern matching algorithm involves comparing the template image, or a subset of sample pixels representing the template image, against locations in the target image on a horizontal pixel column basis and horizontal scan line basis. In other words, the sample pixels representing the template image are compared against a portion of the pixels in the target image, such as by using a 2D correlation, the sample pixels representing the template are then moved down or across a one pixel scan line or one pixel column in the target image, and the pattern matching algorithm is repeated, etc. Thus, the pattern matching algorithm generally involves comparing the template image pixels against all possible locations in the target image in an iterative fashion. The pattern matching produces the location of the template in the image, the quality of match and possibly the orientation, size and/or scaling of the template.
The template is compared with portions of the target image typically utilizing a correlation based pattern matching, i.e., using normalized two dimensional correlation (normalized 2D correlation). This 2D correlation is performed by placing the template over the respective portion of the image and performing a complete normalized 2D correlation between the pixels in the template and the pixels in the corresponding portion of the image. This correlation generally produces a correlation value which indicates the degree of correlation or match. For example, the correlation value may range between −1 and +1, wherein +1 indicates a complete match, 0 indicates no match, i.e., that the two images are uncorrelated, and −1 indicates that the two images are anti-correlated, i.e., a complete reversal of a match.
The normalized 2D correlation operation is based on a point-wise multiplication wherein the template is first placed over a portion of the image, each point or pixel of the template is multiplied with the corresponding pixel in the respective portion of the image, and the result is summed over the entire template. Also, as noted above, the template image is generally compared with each possible portion of the target image in an iterative fashion. This correlation-based pattern matching technique is thus very computationally intensive.
Various optimizations or algorithms have been developed to provide a more efficient correlation-based pattern matching. One prior art technique is to use selected samples or pixels from the template image, referred to as sample pixels, to represent the template image and hence to reduce the number of computations in the correlation.
FIG. 2
illustrates the pattern matching process of the prior art which involves characterization of the template with a reduced number of sample pixels. In this process, a characterization of the template is performed to extract features from the template image. In other words, the template is characterized to represent the template image with a lesser number of points or pixels, referred to as sample pixels, which presumably accurately characterize the template image. The template image is characterized in this fashion because the time required for the pattern matching is generally directly proportional to the number of points or pixels representing the template image which are used in the pattern matching. Thus the template is characterized to reduce the number of samples or pixels which are used in the correlation operation, thereby reducing the amount of computation. Once a lesser number of sample pixels have been generated, these sample pixels are then used in the pattern matching algorithm to locate instances of the template image in the target image.
Prior art techniques for characterizing the template image have utilized a homogeneous sampling of the template, such as a grid-based sampling of the template, Another prior art technique is to utilize random points or pixels within the template image and to use these random sample pixels in the correlation-based pattern matching. However, each of the above prior art techniques operates to select a subset of the pixels in the template image which do not necessarily best represent or characterize the template image. In other words, homogeneous sampling or random sampling of the template image does not produce the optimum subset of samples or pixels which best represent the template image.
Therefore, an improved system and method is desired for correlation based pattern matching. More particularly, an improved system and method is desired for characterizing or selecting samples or pixels from a template image which best represent the template image with the fewest samples possible.
In addition, an improved system and method is also desired which reduces the number of correlation operations which are required in a pattern matching operation. Further, improved techniques are desired for performing pattern matching for rotated images, translated images and images which have changed in size.
SUMMARY OF THE INVENTION
The present invention comprises a system and method for performing pattern matching to locate zero or more instances of a template image in a target image. The pattern matching is preferably performed in a computer system. The template image is received and/or stored in the computer system and comprises a first plurality of pixels. The target image is preferably acquired by the system, such as by a camera and provided to the computer system for the pattern matching.
According to a first embodiment, the method and system first comprises sampling the template image using a Low Discrepancy sequence, also referred to as a quasi-random sequence, to determine a plurality of sample pixels in the template image which characterize the template image. The Low Discrepancy sequence is designed to produce sample points which maximizes the distance between sample points. Also, the Low Discrepancy sequence sampling results in fewer points and/or a better characterization of the template image than a random sequence sampling or a uniform sampling. Examples of the Low Discrepancy sequence include Halton, Sobol, Faure, and Niederreiter sequences. The sampling or characterization of the template image is preferably performed off-line prior to receipt of a target image. Thus the sampling or characterization of the template image is preferably not constrained by real time requirements.
After the template image is sampled or characterized, the me
DeKey Samson
Nair Dinesh
Vazquez Nicolas
Wenzel Lothar
Azarian Seyed
Conley Rose & Tayon PC
Hood Jeffrey C.
Johns Andrew W.
National Instruments Corporation
LandOfFree
Pattern matching system and method which performs local... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Pattern matching system and method which performs local..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pattern matching system and method which performs local... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2468895