Method and apparatus for locating patterns in an optical image

• US 6,067,379 A
• Filed: 11/12/1996
• Issued: 05/23/2000
• Est. Priority Date: 12/09/1988
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Silver, William M.
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): CHANG, JON CARLTON
• Application Number:
  US08/747,476
• Time in Patent Office: 1,288 Days
• Field of Search: 382/181, 382/209, 382/216, 382/218, 382/217, 382/151
• US Class Current: 382/216
• CPC Class Codes: G06T 2207/30148 Semiconductor; IC; Wafer
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/507 Summing image-intensity values; Histogram projection analysis

Abstract

The invention provides methods and apparatus for processing an image to identify the position of a linear pattern--for example, a line or a cross-hair comprising a plurality of intersecting lines. The system performs a first processing step for generating a projection of the image along axes aligned with an expected position of the linear patterns. A second processing step performs a mirror symmetry filtering on the projection to bring out a single peak corresponding to the center of the linear pattern. To further isolate that peak, the system performs a further filtering operation to remove peaks of lesser slope angle, so that only a highly sloped spike corresponding to the linear pattern will remain. The position of the center that peak corresponds to the center of the linear pattern in the original input signal.

Claims

1. An apparatus for identifying a linear pattern, having an expected radius less than or equal to a value r, in an image signal, I, said apparatus comprising:

A. projection means for generating a projection signal, P, representative of a projection of said image signal along an axis substantially aligned with an expected orientation of said linear pattern, where said projection signal, P, is comprised of elements P_i, where i is an integer between 1 and a length of said image signal along said axis,

B. mirror symmetry filter means, coupled with said projection means, responsive to said radius and said projection signal for filtering that projection signal to generate a mirror symmetry signal, S, representative of the degree of symmetry of the projection signal P about each point therein,

C. notch detector means, coupled with said mirror symmetry filter means, for operating on said mirror symmetry signal to generate a peak location signal emphasizing a peak corresponding to a location of a center of said linear pattern, and

D. peak locating means, coupled with said notch detector means, for identifying a peak in said peak location signal, and for estimating from a location of that peak a location of a center of said linear pattern.

2. An apparatus for identifying a linear pattern, having an expected radius less than or equal to a value r, in an image signal, I, said apparatus comprising:

projection means for generating a projection signal, P, representative of a projection of said image signal along an axis substantially aligned with an expected orientation of said linear pattern, where said projection signal, P, is comprised of elements P_i, where i is an integer between 1 and a length of said image signal along said axis;

mirror symmetry filter means, coupled with said projection means, responsive to said radius and said projection signal for filtering that projection signal to generate a mirror symmetry signal, S, representative of the degree of symmetry of the projection signal P about each point therein;

notch detection means, coupled with said mirror symmetry filter means, for operating on said mirror symmetry signal to distinguish therein extreme values corresponding to said linear pattern from extreme values corresponding to uniform background, and to generate a peak location signal emphasizing, within the extreme values corresponding to said linear pattern, a peak corresponding to a location of a center of that linear pattern; and

peak locating means, coupled with said notch detection means, for identifying a peak in said peak location signal, and for estimating from a location of that peak a location of a center of said linear pattern.

4. An apparatus according to any of claims 2 and 3, wherein said mirror symmetry filter means includes means for filtering a projection signal to generate a mirror symmetry signal, S, comprising elements Si, wherein each element Si has a value determined in accord with the mathematical function ##EQU6##

5. An apparatus according to any of claims 2 and 3, wherein said mirror symmetry filter means includes a step for filtering a projection signal to generate a mirror symmetry signal, S, comprising elements Si, wherein each element Si has a value determined in accord with the mathematical function

6. An apparatus according to any of claims 2 and 3, wherein said peak locating means includes means for identifying in said peak location signal positions and amplitudes of a most significant peak and a neighboring point on each side of that most significant peak, and for estimating from those positions and amplitudes a location of the center of said linear pattern.

7. An apparatus according to any of claims 2 and 3, wherein said peak locating means includes means for:

identifying in said peak location signal a first line intersecting a most significant peak and a neighboring value of that peak with a smallest amplitude;

determining a slope of said first line;

identifying a second line intersecting said neighboring value with a largest amplitude and having a slope complement to that of said first line;

identifying an intersection of said first and second lines, and

estimating from that intersection a location of the center of said linear pattern.

8. An apparatus according to any of claims 2 and 3, wherein said projection means includes means for generating said projection signal, P, to be representative of a projection of said image signal along an axis substantially aligned with an expected orientation of said linear pattern.

3. An apparatus for identifying a cross-hair comprising a plurality of intersecting linear patterns, having expected radii less than or equal to a value r, in an image signal, I, said apparatus comprising:

projection means for a generating, for each of said linear patterns, a corresponding projection signal, P, representative of a projection of said image signal along an axis substantially aligned with an expected orientation of that linear pattern, where said projection signal, P, is comprised of elements P_i, where i is an integer between 1 and a length of said image signal along the respective axis;

mirror symmetry filter means, coupled with said projection means, and responsive to said radius and each said projection signal, for filtering that projection signal to generate a corresponding mirror symmetry signal, S, representative of the degree of symmetry of the projection signal P about each point therein;

notch detection means, coupled with said mirror symmetry filter means, for operating on each said mirror symmetry signal, S, to distinguish therein extreme values corresponding to said linear pattern from extreme values corresponding to uniform background, and to generate a corresponding peak location signal emphasizing, within the extreme values corresponding to said linear pattern a peak corresponding to a location of a center of that linear pattern;

peak locating means, coupled with said notch detection means, for identifying a peak in each said peak location signal, and for estimating, from a location of that peak, a location of a center of the corresponding linear pattern; and

center point locating means, coupled with said peak locating means, for determining the center of said cross-hair pattern as an intersection of the estimated locations of centers of the corresponding linear patterns.

9. A method for identifying a linear pattern, having an expected radius less than or equal to a value r, in an image signal, I, said method comprising:

a projection step for generating a projection signal, P, representative of a projection of said image signal along an axis substantially aligned with an expected orientation of said linear pattern, where said projection signal, P, is comprised of elements P_i, where i is an integer between 1 and a length of said image signal along said axis;

a mirror symmetry filter step responsive to said radius and said projection signal for filtering that projection signal to generate a mirror symmetry signal, S, representative of the degree of symmetry of the projection signal P about each point therein,

a notch detection step for operating on said mirror symmetry signal to distinguish therein extreme values corresponding to the linear pattern from extreme values corresponding to uniform background and to generate a peak location signal emphasizing, within the extreme values corresponding to the linear patter, a peak corresponding to a location of a center of that linear pattern, and

a peak locating step for identifying a peak in said peak location signal, and for estimating from a location of that peak a location of a center of said linear pattern.

10. A method for identifying a cross-hair comprising a plurality of intersecting linear patterns, having expected radii less than or equal to a value r, in an image signal, I, said method comprising:

a projection step for a generating, for each of said linear patterns, a corresponding projection signal, P, representative of a projection of said image signal along an axis substantially aligned with an expected orientation of that linear pattern, where said projection signal, P, is comprised of elements Pi, where i is an integer between 1 and a length of said image signal along the respective axis;

a mirror symmetry filter step for responding to said radius and each said projection signal for filtering that projection signal to generate a corresponding mirror symmetry signal, S, representative of the degree of symmetry of the projection signal P about each point therein,

a notch detection step for operating on each said mirror symmetry signal to distinguish therein extreme values corresponding the linear pattern from extreme values corresponding to uniform background and to generate a corresponding peak location signal emphasizing, within the values corresponding to the linear pattern, a peak corresponding to a center of that linear pattern;

a peak locating step for identifying a peak in each said peak location signal, and for estimating from a location of that peak a location of a center of the corresponding linear pattern, and

a center point locating step for determining the center of said cross-hair pattern as an intersection of the estimated locations of said linear patterns.

11. A method according to any of claims 9 and 10, wherein said mirror symmetry filter step includes a step of filtering a projection signal to generate a mirror symmetry signal, S, comprising elements Si, wherein each element Si has a value determined in accord with the mathematical function ##EQU7##

12. A method according to any of claims 9 and 10, wherein said mirror symmetry filter step includes a step for filtering a projection signal to generate a mirror symmetry signal, S, comprising elements Si, wherein each element Si has a value determined in accord with the mathematical function

13. A method according to any of claims 9 and 10, wherein said peak locating step includes a step for identifying in said peak location signal positions and amplitudes of a most significant peak and a neighboring point on each side of that most significant peak, and for estimating from those positions and amplitudes a location of the center of said linear pattern.

14. A method according to any of claims 9 and 10, wherein said peak locating step includes the steps of identifying in said peak location signal a first line intersecting a most significant peak and a neighboring value of that peak with a smallest amplitude;

determining a slope of said first line;

identifying a second line intersecting said neighboring value with a largest amplitude and having a slope complement to that of said first line;

identifying an intersection of said first and second lines, and

estimating from that intersection a location of the center of said linear pattern.

15. A method according to any of claims 9 and 10, wherein said projection step includes a step for generating said projection signal, P, to be representative of a projection of said image signal along an axis substantially aligned with an expected orientation of said linear pattern.