Image analysis – Pattern recognition – Feature extraction
Reexamination Certificate
2005-02-15
2005-02-15
Dastouri, Mehrdad (Department: 2623)
Image analysis
Pattern recognition
Feature extraction
C382S228000
Reexamination Certificate
active
06856698
ABSTRACT:
A method and apparatus are provided for rapidly refining a given approximate location of a pattern to produce a more accurate location. The invention employs a multi-dimensional space that includes translation, orientation, and scale. The invention can serve as a replacement for the fine resolution phase of any coarse-fine system for pattern location. Patterns and images are represented by a feature-based description that can be translated, rotated, and scaled to arbitrary precision much faster than digital image re-sampling, and without pixel grid quantization errors. Thus, accuracy is not limited by the ability of a grid to represent small changes in position, orientation, or size (or other degrees of freedom). The invention determines an accurate object pose from an approximate starting pose in a small, fixed number of increments that is independent of the number of dimensions of the space, and independent of the distance between the starting and final poses, provided that the starting pose is within the “capture range” of the true pose. Thus, accuracy need not be sacrificed to keep execution time acceptable for practical applications. Specifying locations in four or more dimensions will often result in better matches between the pattern and image than two-dimensional location systems, thereby improving accuracy. Accuracy is not degraded if some portion of the object is missing or occluded, or if unexpected extra features are present.
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: 5406642 (1995-04-01), Maruya
patent: 5459636 (1995-10-01), Gee et al.
patent: 5515453 (1996-05-01), Hennessey et al.
patent: 5524064 (1996-06-01), Oddou et al.
patent: 5557684 (1996-09-01), Wang et al.
patent: 5559901 (1996-09-01), Lobregt
patent: 5570430 (1996-10-01), Sheehan et al.
patent: 5631975 (1997-05-01), Riglet et al.
patent: 5694482 (1997-12-01), Maali et al.
patent: 5703960 (1997-12-01), Soest
patent: 5862245 (1999-01-01), Renouard et al.
patent: 5881170 (1999-03-01), Araki et al.
patent: 5930391 (1999-07-01), Kinjo
patent: 5995953 (1999-11-01), Rindtorff et al.
patent: 6061086 (2000-05-01), Reimer et al.
patent: 6363173 (2002-03-01), Stentz et al.
patent: 6453069 (2002-09-01), Matsugu et al.
Huttenlocker, et al, “comparing Images Using the Hausdorff Distance,”IEEE Transactions on Pattern Analysis and Machine Intelligence, Sep. 1993, pp. 850-863, vol. 15, No. 9, USA.
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,”IEEE 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, Pergamon 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 Manufacturing, 1995, pp. 97-148 (and Bibliography pp. 324-335) PhD thesis, University of California at Berkeley, USA.
James D. Foley, Andries Van Dam, Steven K. Feiner, John F. Hughes, Second Edition in C, Computer Graphics Principles and Practice,Programming in the Simple Raster Graphics Package, pp. 48-50, Addison-Wesley Publishing Company, 1996, USA.
Silver William
Wagman Adam
Wallack Aaron
Cognex Corporation
Dastouri Mehrdad
Weinzimmer Russ
LandOfFree
Fast high-accuracy multi-dimensional pattern localization 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 localization, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast high-accuracy multi-dimensional pattern localization will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3493802