Fast high-accuracy multi-dimensional pattern inspection

Details Fast high-accuracy multi-dimensional pattern inspection Fast high-accuracy multi-dimensional pattern inspection

2006-01-10

2006-01-10

Miriam, Daniel (Department: 2625)

Image analysis

Pattern recognition

Feature extraction

Reexamination Certificate

active

06985625

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: 3899771 (1975-08-01), Saraga et al.
patent: 3986007 (1976-10-01), Ruoff, Jr.
patent: 4146924 (1979-03-01), Birk et al.
patent: 4213150 (1980-07-01), Robinson 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: 4849914 (1989-07-01), Medioni 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: 5515453 (1996-05-01), Hennessey et al.
patent: 5559901 (1996-09-01), Lobregt
patent: 5694482 (1997-12-01), Maali et al.
patent: 5703960 (1997-12-01), Soest
patent: 5828769 (1998-10-01), Burns
patent: 5875040 (1999-02-01), Matraszek et al.
patent: 6760483 (2004-07-01), Elichai et al.
Miller, et al. (Template Based Method Of Edge Linking Using a Weighted Decision), IEEE, pp. 1808-1815, 1993.
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 Architecture 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.

Affiliated with

Also associated with

Rating

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.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3578023