Image analysis – Pattern recognition – Template matching
Reexamination Certificate
2001-06-29
2003-10-28
Dastouri, Mehrdad (Department: 2623)
Image analysis
Pattern recognition
Template matching
C382S170000, C382S278000, C382S296000, C382S298000
Reexamination Certificate
active
06640008
ABSTRACT:
TECHNICAL FIELD
This invention is related to image processing and pattern recognition and more particularly to improving template matching to be largely independent of size and rotation variation.
1. Background of the Invention
Pattern matching is a simple yet powerful machine vision tool. The normalized correlation method has been widely used in many machine vision applications. The match score of normalized correlation is largely independent of linear variations in object shading caused by reflectivity or illumination variations. However, the normalized correlation method does not work well when the pattern being searched is subject to rotation or size variations. The match score could drop significantly when only a few degrees of rotation or a small percentage of size change occurs.
2. Prior Art
Pattern matching is a simple yet powerful machine vision tool. A type of pattern matching, normalized correlation, (Ballard D H and Brown C M, “Computer Vision”, Prentice-Hall Inc. 1982 pp. 68-70) has been widely used in many machine vision applications. The match score from normalized correlation is largely independent of linear variations in object shading caused by reflectivity or illumination variations. However, the normalized correlation method does not work well when the pattern being searched is subject to rotation or size variations. The match score could drop significantly even for only a few degrees of rotation or a few percent size difference from the template.
One prior approach to resolving this sensitivity is to rotate and scale the pattern template, making multiple templates and then try all possible scale and rotation combinations. However, this is very computationally expensive and has not been widely used. Another prior art approach is to use a geometric pattern matching method such as PatMax introduced by Cognex (Silver, B, “Geometric Pattern Matching for General-Purpose Inspection in Industrial Machine Vision”, Intelligent Vision '99 Conference—Jun. 28-29, 1999). This approach uses geometric information in place of pixel grid-based normalized correlation. For example, it interprets a square as four line segments and a football as two arcs. It extracts key geometric features within an object image using a method such as boundary encoding and from the extracted features measures characteristics such as shape, dimensions, angle, arcs, and shading. It then adjusts the spatial relationships in the pattern template (by scaling and rotation) to match the key features of the new input image. However, this prior art approach requires high edge contrast and low noise between patterns and background to reliably extract the key geometric features for matching. This prior art approach fails when edges of the key features are noisy or indefinite. This is the inherent problem when using a geometric approach in place of a pixel grid based approach.
OBJECTS AND ADVANTAGES
It is an object of the invention to provide a fast pattern search method that can accurately locate patterns of interest in instances where they vary in size or orientation, when their appearance is degraded, and even when they are partially hidden from view.
It is an object of the invention to achieve the advantages of rotation and scale invariance while using the pixel grid based approach on low contrast and noisy images.
It is an object of the invention to use a multi-resolution coarse-to-fine search approach for fast template searching.
It is an object of the invention to perform fast correlation using a weighted histogram sum to compute the correlation score. When the number of gray scale values is limited, this can decrease the computation time required. This technique is particularly applicable for large pattern templates.
It is an object of the invention to implement the fast search method in a general purpose computer platform without any special hardware. This reduces cost and system complexity.
SUMMARY OF THE INVENTION
This invention generates a polar coordinate representation of the pattern template image or a feature enhanced template image that allows for fast search of scale along the radial axis and rotation along the angular axis. Fast search can be achieved by projecting image intensities into the radial axis and transforming them to create multiple scale templates for scale search and projecting image intensities into angular axis for rotation angle search by one dimensional pattern matching. Furthermore, a multi-resolution coarse to fine search approach can be used to further increase the search speed. In this approach, wide search ranges are applied only using the lower resolution images or profiles and a fine-tuning search is applied using higher resolution images or profiles. This efficiently achieves wide search range and fine search resolution.
REFERENCES:
patent: 6088479 (2000-07-01), Ikeshoji et al.
patent: 6185318 (2001-02-01), Jain et al.
patent: 6256409 (2001-07-01), Wang
patent: 6289117 (2001-09-01), Li
patent: 09-102039 (1997-04-01), None
Khorsheed et al, “Spectral Features for Arabic Word Recognition”, Jun. 9, 2000, IEEE Proceedings, ISBN: 0-7803-6293, vol. 6, pp. 3574-3577.*
Khorsheed et al, “Multi-Font Arabic Word Recognition Using Spectral Features”, Sep. 7, 2000, IEEE Proceedings ISBN: 0-7695-0750, vol. 4, pp. 543-546.
Lee Shih-Jong J.
Oh Seho
Seghers Ryan K
LandOfFree
Rotation and scale invariant pattern matching method does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Rotation and scale invariant pattern matching method, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Rotation and scale invariant pattern matching method will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3136295