Method and apparatus for locating ball grid array packages from two-dimensional image data

• US 6,151,406 A
• Filed: 10/09/1997
• Issued: 11/21/2000
• Est. Priority Date: 10/09/1997
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Loizeaux, Jane Alice, Chang, Yian Leng, Foster, Nigel John
• Primary Examiner(s): Bella, Matthew
• Assistant Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US08/947,760
• Time in Patent Office: 1,139 Days
• Field of Search: 382/146, 382/147, 382/149, 382/150, 382/151, 382/152, 382/154, 250/308, 250/306, 348/87, 348/94, 348/95, 348/126, 356/388, 356/395, 356/151
• US Class Current: 382/147
• CPC Class Codes: G06T 2207/30152 Solder
• CPC Class Codes: G06T 7/33 using feature-based methods
• CPC Class Codes: G06T 7/75 involving models

Abstract

A ball grid array inspection and location method and apparatus includes a raw feature finding processor which uses a feature finding algorithm to find ball features (irrespective of number) and generate a list of raw features as an X and Y location for each feature located. An angle estimation processor receives the list of raw features, a user estimated orientation angle, and ball-to-ball pitch information and determines an estimated grid angle. An on-grid check processor receives the estimated grid angle, the list of raw features and the ball-to-ball pitch information and produces a set or list of on-grid features in the form of a list X and Y translation parameters for each feature/ball found on-grid. A correspondence processor receives the list of on-grid features and model grid information and searches for correspondence between the two dimensional array of found grid features and the two dimensional array of model grid features to yield a direct mapping of respective two dimensional spatial relationships between model features and found features, which is used to determine the spatial relationship between model space and physical space in order to position/align balls of the device in physical space in accordance with model balls in model space. A least square fit is effected to refine position of the device in terms of its translation and rotation.

Claims

1. A vision system for locating and positioning ball grid array features for placement on an electronic assembly, comprising:

a raw feature finding processor receiving as inputs model information of a ball grid array device, captured image information as a two dimensional image of said ball grid array device, and calibration information comprising a two dimensional transform relating image space to physical space, said raw feature finding processor finding ball features in said captured image and generating a list of ball features as an X and Y location of each ball feature in physical space;

an angle estimation processor receiving said list of ball features from said raw feature finding processor and receiving as additional inputs a user estimated orientation angle and ball-to-ball pitch information from said mode information, said angle estimation processor determining therefrom an estimated grid angle;

an on-grid check processor receiving said estimated grid angle, said list of ball features and said ball-to-ball pitch information and fitting said list of ball features to a grid to eliminate noise features and refining said estimated grid angle, said on-grid check processor producing a set of on-grid balls as a list of X and Y translation parameters for each ball found on-grid; and

a correspondence processor receiving said set of on-grid balls and said model information of said ball grid array device, said correspondence processor searching for correspondence between said on-grid balls and model balls of said model information of said ball grid array device and providing a direct mapping of respective two dimensional spatial relationships between said model balls and said set of on-grid balls

wherein correspondence between said model balls and said set of on-grid balls provides a mapping of model balls to corresponding balls in image space which is used, along with said two dimensional transform relating image space to physical space to position/align balls of said ball grid array device in physical space in accordance with model balls in model space.

2. The vision system of claim 1 wherein said model information is provided to said vision system in a training operation and comprises a device description including dimensions of a device body on which said ball grid array features are located, a type of arrangement of said ball grid array, ball dimensions, X and Y locations of balls in said ball grid array, number of balls along each of two orthogonal axes and pitch between balls in said ball grid array.

3. The vision system of claim 2 wherein said type of arrangement of said ball grid array is one of a regular grid, a checker grid and a reverse checker grid.

4. The vision system of claim 1 wherein said raw feature finding processor uses one of a Hough transform and segmentation via grey level thresholding as a feature finding algorithm to find ball features in said captured image.

5. The vision system of claim 1 wherein said user estimated orientation angle is an estimation within plus or minus 35 degrees of a true orientation angle of said ball grid array in physical space.

6. The vision system of claim 1 wherein in determining said estimated grid angle, said angle estimation processor generates projection data as a plurality of histograms representative of data points corresponding to lines of balls at multiple candidate angles from which a highest density peak projection is selected as indicative of said estimated grid angle.

7. The vision system of claim 6 wherein said projection data is generated in a plurality of passes with each successive pass having a progressively finer angular resolution.

8. The vision system of claim 7 wherein said plurality of passes comprises three passes.

9. The vision system of claim 7 wherein said plurality of passes includes a first pass wherein projections are generated starting from the user estimated orientation angle and a projection is generated at each angle at increments of 2 degrees over a range of +/-35 degrees to yield a first basis angle for generating another plurality of histograms.

10. The vision system of claim 7 wherein said plurality of passes includes a second pass wherein projections are generated starting from a first basis angle and a projection is generated at each angle at increments of one degree over a range of +/- two degrees to yield a second basis angle for generating another plurality of histograms.

11. The vision system of claim 7 wherein said plurality of passes includes a third pass wherein projections are generated starting from a second basis angle and a projection is generated at each angle at increments of one quarter of a degree over a range of +/- one degree to yield said estimated grid angle.

12. The vision system of claim 1 wherein said raw feature finding processor receives captured image information including multiple fields of view.

13. The vision system of claim 12 wherein said on-grid check processor merges features that were found in slightly different locations in said multiple fields of view.

14. The vision system of claim 1 wherein said on-grid check processor determines whether said estimated grid angle is an angle relative to one of a major grid axis and a diagonal axis 45 degrees from said one of said major grid axis.

15. The vision system of claim 1 wherein said correspondence processor uses said set of on-grid features to generate a two dimensional array of found grid features and receives said model grid information as a two dimensional array of model grid features, and said correspondence processor searches for correspondence between said two dimensional array of found grid features and said two dimensional array of model grid features.

16. The vision system of claim 15 wherein said correspondence processor searches for correspondence between said two dimensional array of found grid features and said two dimensional array of model grid features by defining a search rectangle that is at least one row and column greater than said two dimensional array of found grid features, and successively positioning said two dimensional array of model grid features relative said two dimensional array of found grid features to generate a score array each element of which represents a number of balls in said two dimensional array of found grid features that corresponds to balls in said two dimensional array of model grid features.

17. The vision system of claim 1 wherein after said correspondence processor provides said direct mapping of respective two dimensional spatial relationships between said model balls and said set of on-grid balls a least square final fit is effected as a fine alignment to refine positioning of said set of on-grid balls.

18. A method of determining a spatial relationship between a two dimensional grid of model features in model space and a two dimensional grid of found features in image space, for positioning said two dimensional grid of found features in physical space, said method comprising the steps of:

receiving at a processor, inputs including model information of a feature grid array device in model space, captured image information as a two dimensional image of said feature grid array device in image space, and calibration information comprising a two dimensional transform relating image space to physical space;

processing said inputs to find features in said captured image and to generate a list of features as an X and Y location of each feature in physical space;

processing said list of features and additional inputs including a user estimated orientation angle and feature-to-feature pitch information to determine therefrom an estimated grid angle;

processing said estimated grid angle, said list of features and said feature-to-feature pitch information to fit said list of features to a grid to eliminate noise features, to refine said estimated grid angle, and to produce a set of on-grid features as a list of X and Y translation parameters for each feature found on-grid; and

processing said set of on-grid features and said model information of said feature grid array device to search for correspondence between said on-grid features and model features of said model information of said feature grid array device and providing a direct mapping of respective two dimensional spatial relationships between said model features and said set of on-grid features

wherein correspondence between said model features and said set of on-grid features provides a mapping of model features to corresponding features in image space which is used, along with said two dimensional transform relating image space to physical space, to position/align features of said feature grid array device in physical space in accordance with model features in model space.

19. The method of claim 18 further including the step of performing a least square final fit as a fine alignment to refine positioning of said set of on-grid features relative to said model features.