Finding fiducials on printed circuit boards to sub pixel accuracy

• US 5,086,478 A
• Filed: 12/27/1990
• Issued: 02/04/1992
• Est. Priority Date: 12/27/1990
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Stafford, James M., Kelly-Mahaffey, William L.
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Johns, Andrew W.
• Application Number:
  US07/634,642
• Time in Patent Office: 404 Days
• Field of Search: 382/8, 382/18, 382/22, 382/29, 382/48, 358/101, 358/107
• US Class Current: 382/151
• CPC Class Codes: G06V 10/44 Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis
• CPC Class Codes: H05K 1/0266 Marks, test patterns or identification means
• CPC Class Codes: H05K 3/30 Assembling printed circuits with electric components, e.g. with resistor

Abstract

A method is disclosed for determining the presence and position of fiducials on the surface of a printed circuit substrate in grey level images to sub-pixel accuracy. A summation profile technique is utilized to decrease the amount of computation required and thereby increase throughput for enabling real time operation in a total component placement system.

Claims

1. A method for locating a circular or symmetrical convex polygonal fiducial of known dimensions on a circuitized substrate comprising the steps of:

determining fiducial presence by;

acquiring a two dimensional digitized image array;

selecting a subarray representing a predetermined area within which a fiducial is expected;

calculating summation profiles of rows and columns in said selected subarray;

constructing a first difference profile corresponding to each calculated summation profile; and

screening said first difference profiles for choosing presumptive leading and trailing edges of the fiducial;

finding approximate fiducial center by taking midpoints between presumptive leading edges and trailing edges; and

calculating fiducial center to sub pixel accuracy by selecting from said two dimensional array of digitized image data, four two dimensional subarrays located a predetermined distance on either side of the X and Y coordinates found in said fining step;

determining first differences for each of said four subarrays;

choosing maximum and minimum values for X from said firt differences from subarrays located on either side of the X value found in said finding step;

choosing maximum and minimum values for Y first differences from said subarrays on either side of the Y value found in said finding step; and

averaging chosen values for X and Y, respectively, to find exact X and Y values.

2. The method of claim 1 wherein said screening step further includes:

repeatedly compairing pairs of plus and minus peaks from first differences of said summation profiles for obtaining candidate peak valley pairs separated by a distance within one fourth of expected fiducial radius dimension;

picking from said condidate peak-valley pairs of pair whose distance apart most closely matches expected fiducial diameter dimension.

3. The method of claim 1 wherein said selecting from said two dimensional array step additionally includes:

examining seven rows of pixels centered about X coordinate of approximate center;

retrieiving pixel data along each row from 0.75 to 1.25 fiducial radius distance and from -1.25 to -0.75 radius disance from X;

examininmg 7 columns of pixels centered about Y coordinate of apprxoimate center; and

retrieving pixel data along each column from 0.75 to 1.25 radius distance and from -1.25 to -0.75 radius distance from Y.

7. The method of claim 3 including the additional steps of:

examining four subarrays of pixel data selected as a function of their location in relation to established approximate X, Y center coordinates;

finding first differences in each subarray; and

averaging maximum and minimum values in each subarray.

4. A method of locating a fiducial center to sub pixel accuracy comprising the steps of:

finding leading and trailing edges and apprxoimate center coordinates through analysis of one dimensional first differences of summation profile arrays, said finding step including;

obtaining a digitized image array of whole scene;

examining a predetermined two dimensional subarray wherein object is expected;

forming one dimensional summation profiles for rows and columns of pixels in said subarray;

calculating row summations of pixel values in said subarray for structuring a one dimensional profile array;

calculating column summations of pixel values in said subarray for structuring a one dimensional profile array;

assuming leading edge of the object to correspond to a high positive difference and trailing edge to correspond to a low negative difference in each on dimensional profile array;

establishing approximate X, Y center coordinates, at points midway between said high and low differences;

determining exact center coordinates through analysis of four narrowly constrained, two dimensional pixel arrays whose locations are chosen as a function of distance from approximate center coordinates, said determining step including;

examining four subarrays of pixel data selected as a function of their location in relation to established apprxoimate X, Y center coordinates;

finding first differences in each subarray; and

averaging maximum and minimum values in each subarray.

5. A method of precisely locating an object in a field of view comprising the steps of:

obtaining a digitized image array of a whole scene in the field of view;

examining a predetermined two dimensional subarray of said digitized image array wherein an object is expected;

forming one dimensional summation profiles for rows and columns of pixels in said subarray by calculating row summations of pixel values in said subarray for structuring a one dimensional profile array, and calculating column summations of pixel values in said subarray for structuring a one dimensional profile array;

assuming the object'"'"'s leading edge to correspond to a high positive difference and its trailing edge to correspond to a low negative difference in each one dimensional profile array;

establishing approximate X, Y center coordinates, at points midway between said high and low differences;

examining four subarrays of pixel data selected as a function of their location in relation to established approximate X, Y center coordinates;

finding first differences in each subarray; and

averaging maximum and minimum values in each subarray.

6. The method of claim 5, including the additional step of finding object center to sub pixel accuracy comprising:

establishing 2 pairs of concentric bounding arcs about coordinates of approximate object center as a function of distance therefrom;

finding first differences in pixel data within said concentric bounding arcs; and

averaging maximum and minimum first difference values within concentric bounding arc pairs.