Analysis of an image of a pattern of discrete objects

• US 6,289,117 B1
• Filed: 12/16/1999
• Issued: 09/11/2001
• Est. Priority Date: 07/16/1997
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Li, David
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Werner, Brian P.
• Application Number:
  US09/461,412
• Time in Patent Office: 635 Days
• Field of Search: 382/145, 382/146, 382/151, 382/152, 382/197, 382/201, 382/215, 382/216, 382/217, 382/218, 382/294, 382/295, 382/296, 382/142, 382/149, 382/168, 382/173, 382/124, 382/125, 382/126, 382/289, 382/291, 382/150, 345/433-439, 348/94, 348/87, 348/126, 348/130, 250/559.29, 250/559.3, 250/559.34, 250/559.37, 356/394, 356/237.4, 356/237.5
• US Class Current: 382/150
• CPC Class Codes: G06T 2207/30148 Semiconductor; IC; Wafer
• CPC Class Codes: G06T 2207/30152 Solder
• CPC Class Codes: G06T 7/0006 using a design-rule based approach
• CPC Class Codes: G06T 7/75 involving models

Abstract

An image of an actual pattern of discrete objects is analyzed 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. 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.

Claims

1. A computer-based method of analyzing an image of actual pattern of discrete balls of a ball grid array with respect to a model representing a predefined ideal pattern of the balls arranged on a regular grid, the image comprising a set of digital data representing an array of pixels of the image, the method comprising

arranging the model to express locations of the balls in terms of vectors which represent standard spacings of the balls along two dimensions and fill information indicating the existence or nonexistence of a ball at each location of an array defined by the vectors,

performing initial processing of only a portion of the image associated with ones of the balls located in an original neighborhood within the image to determine information about an affine transformation of the actual pattern of the balls relative to the predefine ideal pattern, the initial processing comprising

identifying a first one of the balls in the image,

identifying locations of adjacent other balls in the original neighborhood relative to the first ball,

expressing locations of the adjacent other balls relative to the first ball in angular coordinates, and

matching the angular coordinate information against the model to determine a rotational element of the affine transformation, and

performing additional processing of other portions of the image based on the results of the initial processing, including deriving information about additional ones of the balls located in other portions of the image that are farther away from the first ball than are the balls in the original neighborhood, and wherein less processing is required for balls that are more distant from the first ball, and

performing ball inspection using the image, to compare the balls in the image against a predefined standard.

2. A method for inspecting a digital representation of an actual arrangement of a set of discrete objects, said inspecting comprising determining certain characteristics of the discrete objects within the set, said method comprising:

selecting a subset digital representation representing a subset in a limited area of said discrete objects, said selecting comprising choosing, from within said set, a given reference object and neighbor objects nearby said given reference object;

performing initial processing on said subset digital representation, said initial processing comprising;

confirming that said given reference object is indeed one of said discrete objects, and identifying locations of neighbor objects relative to said given reference object;

analyzing locations of said given reference object and said neighbor objects to determine information about an affine transformation of said set of discrete objects;

expressing locations of said neighbor objects relative to said give reference object in angular coordinates;

matching the angular coordinate information against a model to determine a rotational element of the affine transformation, wherein said model expresses locations of said discrete objects in terms of vectors representing standard spacings of said discrete objects along two dimensions and fill information indicating an existence or non-existence of a discrete object at each location of an array defined by said vectors; and

performing additional processing of other portions of said set discrete objects outside of said subset digital representation based on results of the initial processing.

3. The method according to claim 2, wherein said initial processing includes expressing locations of said neighbor objects relative to said given reference object in radial coordinates.

4. The method according to claim 3, wherein said analyzing comprises:

matching the radial coordinate information against the model to determine a scalar element of the affine transformation.

5. The method according to claim 3, wherein said analyzing comprises:

operating only on information of said digital representation that falls within a window in the vicinity of one of said nearby objects; and

determining the radial coordinate information based on results of said operating.

6. The method according to claim 2, wherein said digital representation comprises an array of pixels.

7. The method according to claim 2, wherein said set of discrete objects is arranged on a regular grid.

8. The method according to claim 7, wherein said regular grid is rectangular.

9. The method according to claim 2, wherein said additional processing comprises:

deriving information about additional ones of said discrete objects located in another portion of said actual arrangement that are farther away from said given reference object than said neighbor objects nearby said given reference object, and wherein less processing is performed for objects more distant from said given reference object.

10. The method according to claim 2, wherein said discrete objects comprise balls of a ball grid array.

11. Computer software, residing on a computer-readable storage medium, comprising instructions for use in a computer system to inspect a digital representation of an actual arrangement of a set of discrete objects, the instructions causing the computer system to perform acts including:

selecting a subset digital representation representing a subset in a limited area of said discrete objects, said selecting comprising choosing, from within said set, a given reference object and neighbor objects nearby said given reference object;

performing initial processing on said subset digital representation said initial processing including;

confirming that said given reference object is indeed one of said discrete objects, and identifying locations of neighbor objects relative to said given reference object;

analyzing locations of said given reference and said neighbor objects to determine information about an affine transformation of said set of discrete objects;

expressing locations of said neighbor objects relative to said given reference object in angular coordinates;

matching the angular coordinate information against a model to determine a rotational element of the affine transformation, wherein said model expresses locations of said discrete objects in terms of vectors representing standard spacings of said discrete objects along two dimensions and fill information indicating an existence or non-existence of a discrete object at each location of an array defined by said vectors; and

performing additional processing on other portions of said set of discrete objects outside of said subset digital representation based on results of the initial processing.