Image analysis – Pattern recognition – Template matching
Reexamination Certificate
2006-06-06
2006-06-06
Miriam, Daniel (Department: 2625)
Image analysis
Pattern recognition
Template matching
C382S199000
Reexamination Certificate
active
07058225
ABSTRACT:
A method and apparatus are provided for identifying differences between a stored pattern and a matching image subset, where variations in pattern position, orientation, and size do not give rise to false differences. The invention is also a system for analyzing an object image with respect to a model pattern so as to detect flaws in the object image. The system includes extracting pattern features from the model pattern; generating a vector-valued function using the pattern features to provide a pattern field; extracting image features from the object image; evaluating each image feature, using the pattern field and an n-dimensional transformation that associates image features with pattern features, so as to determine at least one associated feature characteristic; and using at least one feature characteristic to identify at least one flaw in the object image. The invention can find at least two distinct kinds of flaws: missing features, and extra features. The invention provides pattern inspection that is faster and more accurate than any known prior art method by using a stored pattern that represents an ideal example of the object to be found and inspected, and that can be translated, rotated, and scaled to arbitrary precision much faster than digital image re-sampling, and without pixel grid quantization errors. Furthermore, since the invention does not use digital image re-sampling, there are no pixel quantization errors to cause false differences between the pattern and image that can limit inspection performance.
REFERENCES:
patent: 3069654 (1962-12-01), Hough et al.
patent: 3986007 (1976-10-01), Ruoff, Jr.
patent: 4146924 (1979-03-01), Birk et al.
patent: 4581762 (1986-04-01), Lapidus et al.
patent: 4618989 (1986-10-01), Tsukune et al.
patent: 4707647 (1987-11-01), Coldren et al.
patent: 4972359 (1990-11-01), Silver et al.
patent: 5245674 (1993-09-01), Cass et al.
patent: 5343390 (1994-08-01), Doi et al.
patent: 5351310 (1994-09-01), Califano et al.
patent: 5459636 (1995-10-01), Gee et al.
patent: 5515453 (1996-05-01), Hennessey et al.
patent: 5544254 (1996-08-01), Hartley et al.
patent: 5550937 (1996-08-01), Bell et al.
patent: 5694482 (1997-12-01), Maali et al.
patent: 5703960 (1997-12-01), Soest
patent: 5828769 (1998-10-01), Burns
patent: 6026186 (2000-02-01), Fan
patent: 6128405 (2000-10-01), Fujii
patent: 6226418 (2001-05-01), Miller et al.
Gorman “Recognition of incomplete polygonal objects”, IEEE, pp. 518-522, 1989.
Hügli, et al. “Geometric matching of 3D objects assessing the range of successful initial configurations”, IEEE, pp. 101106, 1997.
Cognex Corporation, “Description Sobel Search,” Natick, MA USA, 1998 but public before the above-referenced filing date.
Cognex Corporation, “Chapter 7 CONLPAS,” Cognex 3000/4000/5000 Programmable Vision Engines, Vision Tools, 1996, pp. 307-340, Revision 7.4 590-0136, Natick, MA USA.
Hu, Yu Hen, “CORDIC-Based VLSI Architectures for Digital Signal Processing,” IEE Signal Processing Magazine, Jul. 1992, pp. 16-35, 1053-5888/92, USA.
Hu, et al, “Expanding the Range of Convergence of the CORDIC Algorithm,” IEEE Transactions on computers, Jan. 1991, pp. 13-21, vol. 40, No. 1, USA.
Ballard, D.H., “Generalizing the Hough Transform to Detect Arbitrary Shapes,” Pattern Recognition, 1981, pp. 111-122, vol. 13, No. 2, Pergaman Press Ltd., UK.
Lin, et al., “On-Line CORDIC Algorithms,” IEEE Transactions on Computers, pp. 1038-1052, vol. 39, No. 8, USA.
Wallack, Aaron Samuel, “Chapter 4 Robust Algorithms for Object Localization,” Algorithms and Techniques for Manugacturing, 1995, pp. 97-148 (and Bibliography pp. 324-335) PhD thesis, Unversity of California at Berkeley, USA.
James D. Foley, Andries Van Dam, Steven K. Feiner, John F. Hughes, Second Edition in C, Introduction to Computer Graphics, pp. 36-49, Addison-Wesley Publishing Company, 1994, USA.
Lisa Gottesfeld Brown,A Survey of Image Registration Techniques, Department of Computer Science, Columbia University, New York, NY 10027, ACM Computing Surveys, vol. 24, No. 4, Dec. 1992.
Gunilla Borgefors,Hierarchical Chamfer Matching:A Parametric Edge Matching Algorithm, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. 10, No. 6, Nov. 1988.
Daniel P. Huttenlocher and William J. Rucklidge,A Multi-Resolution Technique for Comparing Images Using the Hausdorff Distance, Department of Computer Science, Cornell University, Ithaca, NY 14853.
I.J. Cox and J.B. Kruskal (AT&T Bell Laboratories, Murray Hill, NJ),On the Congruence of Noisy Images to Line Segment Models, IEEE, 1988.
Daniel P. Huttenlocher, Gregory A. Klanderman and William J. Rucklidge,Comparing Images Unsing the Hausdorff Distance, IEEE Transaction on Pattern Analysis and Machine Intelligence, Vo. 15, No. 9, Sep. 1993.
Akinori Kawamura, Koji Yura, Tatsuya Hayama, Yutaka Hidai, Tadatashi Minamikawa, Akio Tanaka and Shoichi Masuda, On-lineRecognition of Freely Handwritten Japanese Characters Using Directional Features Densities, IEEE 1992.
Silver William
Wagman Adam
Wallack Aaron
Cognex Corporation
Miriam Daniel
Weinzimmer Russ
LandOfFree
Fast high-accuracy multi-dimensional pattern inspection does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fast high-accuracy multi-dimensional pattern inspection, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast high-accuracy multi-dimensional pattern inspection will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3616158