System and method for automatically inspecting arrays of geometric targets

• US 6,459,448 B1
• Filed: 04/19/2000
• Issued: 10/01/2002
• Est. Priority Date: 04/19/2000
• Status: Expired due to Term

• Current Assignee: VY Corporation
• Original Assignee: K-G Devices Corporation
• Inventors: Martel, Thomas Joseph
• Primary Examiner(s): Le, Vu
• Application Number:
  US09/552,685
• Time in Patent Office: 895 Days
• Field of Search: 348/86-92, 348/125-130, 348/180, 382/141-152, 356/429-431, 356/237--23, 356/238--23, 356/239--23, 356/240.1, 702/35, 364/468.17
• US Class Current: 348/125
• CPC Class Codes: G01N 21/956 Inspecting patterns on the surface of objects contactless testing of electronic circuits G01R31/308; testing currency G07D; manufacturing processes per se of semiconductor devices implementing a measuring step H01L22/10
• CPC Class Codes: G06T 2207/30121 CRT, LCD or plasma display
• CPC Class Codes: G06T 7/0006 using a design-rule based approach
• CPC Class Codes: G06V 10/457 by analysing connectivity, e.g. edge linking, connected component analysis or slices
• CPC Class Codes: H04N 7/18 Closed-circuit television [CCTV] systems, i.e. systems in which the video signal is not broadcast

Abstract

A system and method for using electronically acquired imagery from a one-dimensional camera, to inspect an object for tolerance, color, blemishes, cracks or a wide variety of manufacturing defects that might be present in an object. The method used to detect manufacturing defects includes an algorithm for analyzing the pattern of annular elements in an array and detecting deviations from numerical acceptance norms, such as diameter, spacing, and symmetry, for the annular elements. In the inventive system, a one-dimensional video camera captures a single one-dimensional “slice” of target shape of an object with every line it scans. Each slice is broken down into “segments” consisting of sets of adjacent pixels that are similar in brightness, hue, or both. The one-dimensional camera delivers the segments to the system where they are sequenced. The system identifies every segment to determine what feature of the target shape the segment represents. Thereafter, predefined rules are used to determine if each identified segment deviates from numerical acceptance norms. The inventive method is thus used to analyze periodic arrays of any arbitrary target shape, thereby working in a range of different object acceptance norms and being easily adaptable to change from one set of norms to another.

Claims

1. A method in a system for using electronically acquired imagery from a one-dimensional camera to inspect an object for a wide variety of manufacturing defects, the method comprising the steps of:

capturing, by the one-dimensional camera, a one-dimensional scan line of the electronically acquired imagery whereby each scan line includes an array of geometric elements;

delivering the scan line to the system;

sequencing the scan line, passing a horizontal line through the array of geometric elements, and reducing the scan line to a plurality of run-length integers whereby each run-length integer represents one run;

systematically accounting for all possible interpretations of each run using a plurality of predefined rules to determine deviations from a set of acceptance norms for the array of geometric elements; and

systematically testing each interpretation wherein invalid interpretations are ignored.

2. The method of claim 1, wherein each geometric element in the array has a same geometric shape.

3. The method of claim 2, wherein the array of geometric elements is an array of annular elements.

4. The method of claim 3, wherein the step of systematically accounting further comprises the step of assigning a symbolic designation to each run of the annular element.

5. The method of claim 4, wherein the step of assigning a symbolic designation further comprises the steps of:

designating a dark run as a sliver run when the horizontal line passes through dark sections on a top or bottom of the annular element in the array of geometric elements;

designating the dark run as an entry vertical run when the horizontal line passes through dark sections on a left of a center of the annular element in the array of geometric elements;

designating the dark run as an exit vertical run when the horizontal line passes through dark sections on a right of the center of the annular element in the array of geometric elements;

designating a light run as a HOLE run when the horizontal line passes through a light center of the annular element in the array of geometric elements; and

designating the light run as a LAND run when the horizontal line passes through a light section between two annular elements in the array of geometric elements.

6. The method of claim 5, wherein the step of systematically accounting further comprises the step of applying each run to a search tree table having rows and columns and systematically accounting for every possible interpretation of each of the plurality of run-length integers.

7. The method of claim 6, wherein each interpretation is an interpretation path in the search tree table.

8. The method of claim 7, wherein the step of systematically accounting further comprises the step of corresponding each run to a column in the search tree table, whereby a top of each column shows a length of the run and a word or letter designating an illumination state of the run as either light or dark.

9. The method of claim 8, wherein the step of systematically accounting further comprises the step of corresponding each interpretation of a run to a row in the search tree table.

10. The method of claim 9, wherein the step of corresponding each interpretation further comprises the step of basing designations of a current column, in the interpretation path, on designation in a previous column in the same interpretation path.

11. The method of claim 10, wherein as soon as the interpretation path contains two sliver runs, a lattice constant parameter may be estimated using a lattice constant rule whereby the lattice constant rule is used estimate the distance between previous runs in the interpretation path.

12. The method of claim 11, wherein as soon as the interpretation path contains two hole runs, a lattice constant parameter may be estimated using the lattice constant rule whereby the lattice constant rule is used estimate the distance between previous runs in the interpretation path.

13. The method of claim 11 or 12, wherein the step for estimating the lattice constant parameter comprises the steps of:

calculating a first center point of the first sliver or hole run by dividing the length of the first sliver or hole run by two and rounding to a next integer;

adding the length of the first sliver or hole run to the length of the next run in an interpretation path;

calculating a second center point of a next sliver or hole run by dividing the length of the second sliver or hole run by two, rounding to a second integer and adding the second integer to the length of a cumulative length of all preceding runs in a path;

subtracting the first center point from the second center point;

determining if there is discrepancy in spacing between two sliver or two hole runs and terminating the interpretation path if there is discrepancy.

14. The method of claim 1, wherein the step of delivering is performed by the one-dimensional camera in conjunction with other ancillary electronic data processing means and methods.

15. The method of claim 1, wherein the step of reducing further comprises the step of defining a run as a consecutive set of all dark or light pixels in the array of geometric elements through which the horizontal line passes.

16. The method of claim 15, wherein the step of reducing further comprises the step of creating a collection of numbers, each representing a brightness of a particular pixel in a run-length encoded data.

17. The method of claim 16, wherein the step of reducing further comprises the steps of:

breaking down the scan line into segments, whereby each segment comprises sets of adjacent pixels that are similar in brightness or hue or similar in brightness and hue; and

representing each segment with one of the plurality of run-length integers.

18. The method of claim 17, wherein the step of reducing further comprises the step of identifying every segment to determine what features of the object the segment represents.

19. The method of claim 18, wherein the step of identifying every segment comprises the step of locating at least one set of labels in which every segment in the scan line has at least one label that defines the segment.

20. The method of claim 19, wherein the step of reducing further comprises the step of reducing data in the scan line to black and white images by determining if the data is darker or brighter than a predefined threshold and reducing each pixel to a single bit in the system.

21. The method of claim 19 or 20, wherein the step of reducing further comprises the step of defining a run as a light run if the horizontal line passes through a light part of the geometric element.

22. The method of claim 21, wherein the step of reducing further comprises the step of defining a run as a dark run if the horizontal line passes through a dark part of the geometric element.

23. The method of claim 19, wherein the step of reducing further comprises the step of reducing data in the scan line to non-binary format whereby the data is reduced to multiple bits.

24. The method of claim 1, wherein one of the predefined rules is a lattice constant rule for measuring spacing between the geometric elements in the array of geometric elements whereby a lattice constant is be measured without prior knowledge of the scan line being observed.

25. The method of claim 1, wherein one of the predefined rules is a pattern rule that is derived from a geometry of the geometric elements.

26. A system for using a one-dimensional camera to inspect electronically acquired imagery of an object for a wide variety of manufacturing defects, the system comprises:

a one-dimensional camera for capturing a one-dimensional scan line of the electronically acquired imagery whereby each scan line includes an array of geometric elements;

means for delivering the scan line from the one-dimensional camera to a computer system; and

software means in the computer system for processing and reducing the scan line to a plurality of run-length integers whereby each run-length integer represents one run, systematically accounting for all possible interpretations of each run using a plurality of predefined rules to determine deviations from a set of acceptance norms for the array of geometric elements, systematically testing each interpretation, and ignoring invalid interpretations.

27. The system of claim 26, wherein each geometric element in the array has a same geometric shape.

28. The system of claim 26, wherein the array of geometric elements is an array of annular elements.

29. The system of claim 26, wherein means for delivering the scan line is performed in the one-dimensional camera in conjunction with other ancillary electronic data processing means.

30. The system of claim 26, wherein the software means:

defines a run as a consecutive set of all dark or light pixels in the array of geometric element through which a horizontal line passes;

creates a collection of numbers each representing a brightness of a particular pixel in a run-length encoded data;

breaks down the scan line into segments, whereby each segment comprises sets of adjacent pixels that are similar in brightness or hue or similar in brightness and hue;

represents each segment with one of the plurality of run-length integers; and

identifies every segment by locating at least one set of labels in which every segment in the scan line has at least one label that defines the segment.

31. The system of claim 30, wherein the software means:

reduces data in a scan line to black and white images by determining if the data is darker or brighter than a predefined threshold and reducing each pixel to a single bit in the system;

or

reduces data in a scan line to non-binary format whereby the data is reduced to multiple bits.

32. The system of claim 31, wherein the software means:

defines the run as a light run if the horizontal line passes through a light part of the geometric element; and

defines the run as a dark run if the horizontal line passes through a dark part of the geometric element.

33. The system of claim 26, wherein the predefined rules comprises:

a lattice constant rule for measuring spacing between the geometric elements in the array, whereby a lattice constant is be measured without prior knowledge of the scan line being observed; and

a pattern rule that is derived from a geometry of the geometric elements.

34. The system of claim 26, wherein the software means assigns a symbolic designation to each run by:

designating a dark run as a sliver run when the horizontal line passes through dark sections on a top or bottom of an annular element in the array of geometric elements;

designating the dark run as an entry vertical run when the horizontal line passes through dark sections on the left of a center of the annular element;

designating the dark run as an exit vertical run when the horizontal line passes through dark sections on a right of the center of the annular element;

designating a light run as a HOLE run when the horizontal line passes through a light center of the annular element; and

designating the light run as a LAND run when the horizontal line passes through a light section between two annular elements.

35. The system of claim 34, wherein the software means applies each run to a search tree table having rows and columns and systematically accounts for every possible interpretation of each of the plurality of run-length integers by creating an interpretation path in the search tree table for each interpretation.

36. The system of claim 35, wherein the software means

corresponds each run to a column in the search tree table, whereby a top of each column shows a length of the run and a word or letter designating illumination state of the run as either light or dark;

and

corresponds each interpretation of a run to a row in the table, and bases designations of a current column, in an interpretation path, on designation of a previous column in the same interpretation path.

37. The system of claim 36, wherein as soon as the interpretation path contains two sliver runs, a lattice constant parameter is estimated using a lattice constant rule whereby the lattice constant rule is used to estimate the distance between previous runs in the path, the lattice constant parameter is estimated by

calculating a first center point of a first sliver or hole run by dividing the length of the first sliver or hole run by two and rounding to a first integer;

adding the length of the first sliver or hole run to the length of the next run in an interpretation path;

calculating a second center point of a second sliver or hole run by dividing the length of the second sliver or hole run by two, rounding to a second integer and adding the second integer to the length of a cumulative length of all preceding runs in a path;

subtracting the first center point from the second center point;

determining if there is discrepancy in spacing between two sliver or two hole runs and terminating the interpretation if there is discrepancy.

38. A software component in a computer system for inspecting electronically acquired imagery of an object for a wide variety of manufacturing defects, the software component comprises:

first processing mean for processing and reducing a scan line, with an array of geometric elements, to a plurality of run-length integers whereby each run-length integer represents one run;

second processing means for systematically accounting for all possible interpretations of each run using a plurality of predefined rules to determine deviations from a set of acceptance norms for the array of geometric elements;

third processing means for systematically testing each interpretation and for ignoring invalid interpretations.

39. The software component of claim 38, wherein the first processing means:

defines a run as a consecutive set of all dark or light pixels in the array of geometric element through which a horizontal line passes;

creates a collection of numbers each representing the brightness of a particular pixel in a run-length encoded data;

breaks down the scan line into segments, whereby each segment comprises sets of adjacent pixels that are similar in brightness or hue or similar in brightness and hue;

represents each segment with one of the plurality of run-length integers; and

identifies every segment by locating at least one set of labels in which every segment in the scan line has at least one label that defines the segment.

40. The software component of claim 39, wherein the first processing means:

reduces data in a scan line to black and white images by determining if the data is darker or brighter than a predefined threshold and reducing each pixel to a single bit in the system;

or

reduces data in the scan line to non-binary format whereby the data is reduced to multiple bits.

41. The software component of claim 40, wherein the first processing means:

defines the run as a light run if the horizontal line passes through a light part of the geometric element in the array of geometric elements; and

defines the run as a dark run if the horizontal line passes through a dark part of the geometric element in the array of geometric elements.

42. The software component of claim 38, wherein the predefined rules comprises:

a lattice constant rule for measuring spacing between the geometric elements in the array, whereby a constant can be measured without prior knowledge of the scan line being observed; and

a pattern rule that is derived from the geometry of the geometric elements.

43. The software component of claim 38, wherein the second processing means assigns a symbolic designation to each run by:

designating a dark run as a sliver run when the horizontal line passes through dark sections on a top or bottom of an annular element in the array of geometric elements;

designating the dark run as a entry vertical run when the horizontal line passes through dark sections on a left of a center of the annular element in the array of geometric elements;

designating the dark run as an exit vertical run when the horizontal line passes through dark sections on a right of the center of the annular element in the array of geometric elements;

designating a light run as a HOLE run when the horizontal line passes through a light center of the annular element in the array of geometric elements; and

designating the light run as a LAND run when the horizontal line passes through a light section between two annular elements in the array of geometric elements.

44. The software component of claim 38, wherein the third processing means applies each run to a search tree table having rows and columns and systematically accounts for every possible interpretation of each of the plurality of run-length integers by creating an interpretation path in the search tree table for each interpretation.

45. The software component of claim 44, wherein the third processing means

corresponds each run to a column in the search tree table, whereby the top of each column shows a length of the run and a word or letter designating an illumination state of the run as either light or dark;

corresponds each interpretation of a run to a row in the table; and

bases designations for a current column, in the interpretation path, on designation in a previous column in the same interpretation path.

46. The software component of claim 45, wherein as soon as the interpretation path contains two sliver runs, a lattice constant parameter is estimated using a lattice constant rule whereby the lattice constant rule is used to estimate the distance between previous runs in the path, the lattice constant parameter is estimated by

calculating a first center point of a first sliver or hole run by dividing the length of the first sliver or hole run by two and rounding to a first integer;

adding the length of the first sliver or hole run to the length of the next run in the interpretation path;

calculating a second center point of a second sliver or hole run by dividing the length of the second sliver or hole run by two, rounding to a second integer and adding the second integer to a cumulative length of all preceding runs in a path;

subtracting the first center point from the second center point;

determining if there is discrepancy in the spacing between two sliver or two hole runs and terminating the interpretation if there is discrepancy.

47. A system for using a one-dimensional camera to inspect electronically acquired imagery of an object for a wide variety of manufacturing defects, the system comprises:

a one-dimensional camera for capturing a one-dimensional scan line of the electronically acquired imagery whereby each scan line includes an array of geometric elements;

means for delivering the scan line from the one-dimensional camera to a computer system; and

software means in the computer system for processing and reducing the scan line to a plurality of run-length integers whereby each run-length integer represents one run, systematically accounting for all possible interpretations of each run using a plurality of predefined rules to determine deviations from a set of acceptance norms for the array of geometric elements, systematically testing each interpretation, and ignoring invalid interpretations; and

a plurality of simple processors for parallel processing of a plurality of interpretations at very high speed.