Image analysis – Applications – Manufacturing or product inspection
Reexamination Certificate
1999-12-16
2001-09-11
Boudreau, Leo (Department: 2621)
Image analysis
Applications
Manufacturing or product inspection
C382S151000, C382S294000
Reexamination Certificate
active
06289117
ABSTRACT:
BACKGROUND OF THE INVENTION
The invention relates to analyzing images.
Many people have had the experience of purchasing a product that is expected to include items or attributes in a predetermined pattern, and of finding that the article's usefulness is diminished by a defect relating to the pattern. If the product is meant to be a component in another product, the pattern-related defect may ruin the second product.
For this reason, products incorporating such predetermined patterns may be inspected for the compliance of the pattern with some standard. Examples include ball grid array devices, micro ball grid arrays, flip chips, and chip-scale packages (together called “BGAs”). BGAs share a common feature in that the contacts on the device are metallic balls that are mounted on one side of the device for forming electrical connections between the package's integrated circuit and a printed circuit board.
To work properly, the balls of BGAs should be properly located to connect to the pads on the circuit board. The balls also should be properly formed (i.e., should have a spherical shape and neither too much nor too little solder, to allow an acceptable electrical connection). The balls also should not be connected by extraneous solder or other material in the spaces between the balls. If these conditions are not met, the BGA may fail to make proper electrical connections or physical durable bonds.
Unlike traditional leaded devices that have contacts exposed on perimeters where some types of defects (e.g., solder bridges or missing solder) can be detected even after soldering, BGAs are harder to inspect after mounting on a circuit board. BGAs therefore are inspected before mounting, either in fully-assembled form or by inspection of ball arrays that are about to be attached to the packages of integrated circuits.
Similar inspections are done on other types of products, e.g., pill blister packs and candy sampler boxes.
SUMMARY OF THE INVENTION
In general, in one aspect, the invention features a computer-based method of analyzing an image of an actual pattern of discrete objects with respect to a model representing a predefined ideal pattern of objects. Initial processing is performed on only a portion of the image associated with ones of the objects located in an original neighborhood within the image to determine information about an affine transformation of the actual pattern of the discrete objects relative to the predefined ideal pattern.
Additional processing is performed on other portions of the image based on the results of the initial processing. Thus, initial affine-related analysis of the image need not involve the entire image, which saves time and computing resources. In addition, the information about the affine transformation may be leveraged to facilitate the determination of other information about the image.
Implementations of the invention may include one or more of the following features. The objects may comprise balls of a ball grid array. The image may be a set of digital data representing an array of pixels of the image;
and the pattern of objects may be arranged on a regular (e.g., rectangular) grid. The initial processing may include identifying a first one of the objects in the image, and identifying locations of adjacent others of the objects in the original neighborhood relative to the first object. The locations of the first object and the adjacent objects may be analyzed to determine the information about the affine transformation. The locations of the adjacent objects may be expressed relative to the first object in radial and angular coordinates. The angular coordinate information may be matched against the model to determine a rotational element of the affine transformation. The radial coordinate information may be matched against the model to determine a scalar element of the affine transformation. It is possible to operate only on information of the image that is within a window in the vicinity of one of the adjacent objects, to produce results that may form a basis for determining the radial coordinate information.
The model may express the locations of the objects in terms of vectors which represent standard spacings of the objects along two dimensions and fill information indicating the existence or nonexistence of an object at each location of an array defined by the vectors. The additional processing may include deriving information about additional ones of the objects located in other portions of the image that are farther away from the one object than are the objects in the original neighborhood. Then less processing may be required for objects that are more distant from the one object.
Object inspection may be performed by comparing the object in the image against a predefined standard.
In general, in another aspect, initial processing is performed with respect to a first part of the image by operating on only a first portion of all of the digital data that represents that first part of the image. Later additional processing is performed with respect to another part of the image by operating on only a second portion of all of the digital data that represents that other part of the image, the second portion being relatively smaller than the first portion so that the additional processing is less intensive than the initial processing.
Other advantages and features will become apparent from the following description and from the claims.
REFERENCES:
patent: 4803735 (1989-02-01), Nishida et al.
patent: 5067162 (1991-11-01), Driscoll, Jr. et al.
patent: 5465152 (1995-11-01), Bilodeau et al.
patent: 5495535 (1996-02-01), Smilansky et al.
patent: 5550763 (1996-08-01), Michael et al.
patent: 5574668 (1996-11-01), Beaty
patent: 5574801 (1996-11-01), Collet-Beillon
patent: 5652658 (1997-07-01), Jackson et al.
patent: 5694482 (1997-12-01), Maali et al.
patent: 5870489 (1999-02-01), Yamazaki et al.
patent: 5943125 (1999-08-01), King et al.
patent: 6118893 (2000-09-01), Li
patent: WO 95/11519 (1995-04-01), None
Deley et al., “Accurate Placement of Ball Grid Array Packages,” reprinted fromElectronic Packaging&Production, Apr. 1996, Cahners Publishing Company, Newton, MA, USA.
Hager, William W., “Chapter 6 Eigenproblems, Section 6-11 The Singular Value Decomposition and the Pseudoinverse,”Applied Numerical Linear Algebra, 1988, pp. 294-303, Prentice Hall, Englewood Cliffs, NJ, USA.
Thomas, JR., “Chapter 14 Partial Differentoation,”Calculus and Analytic Geometry, 1953, pp. 481-532, Addison-Wesley Publishing Company, Inc., Cambridge, MA, USA.
Cognex Corporation, Chapter 7 Mathematics, Coordinate Transformation by Pseudoinverse,Cognex 3000/4000/5000 System Software, 1996, pp. 204-210, Revision 7.4 590-0134, Natick, MA.
Cognex Corporation, “Chapter 1 Searching, Correlation Searching,”Cognex 3000/4000/5000 Vision Tools, 1996, pp. 17-25, Revision 7.4 590-0136, Natick, MA.
Cognex Corporation, “Chapter 11 Ball Grid Array Device Inspection,”SMD Placement Guidance Product User's Manual, 1996, pp. 213-246, Release 2.300 590-1039, Natick, MA.
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.
Grimson et al., On the Sensitivity of the Hough Transform for Object Recognition,IEEE Transactions on Pattern Analysis and Machine Intelligence, Mar. 1990, pp. 255-274, vol. 12. No. 3.
Strang, Gilbert, “Chapter 3 Orthogonal Projections and Least Squares, Section 3.4 The Pseudoinverse and the Singular Value Decomposition,”Linear Algebra and Its Applications, Second Edition, 1980, Academic Press, Inc.,New York, NY, USA.
Silver et al., “Practical Golden Template Comparsion,” Cognex Corporation, Jun. 6, 1990, pp. 2-11, Needham, MA, USA.
“RVSI Vanguard Products,” http://www.vai.net/products/products.htm, pp. 1-2, Jun. 3, 1998.
“RVSI Vanguard VAi 5020,” http://www.vai.net/products/prod01.htm, pp. 1-4, Aug. 3, 1998.
“RVSI Vanguard VAi 5200/VAi 5300,” http://www.vai.net/products/prod02.htm, pp. 1-4 Jul. 30, 1998.
“RVSI Vanguard VAi 6300,” http://www.vai.net/produ
Boudreau Leo
Cognex Corporation
Michaelis Brian
Werner Brian P.
LandOfFree
Analysis of an image of a pattern of discrete objects does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Analysis of an image of a pattern of discrete objects, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Analysis of an image of a pattern of discrete objects will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2483844