Method and apparatus for locating patterns in an optical image

• US 5,717,785 A
• Filed: 05/09/1994
• Issued: 02/10/1998
• Est. Priority Date: 01/30/1992
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Silver, William M.
• Primary Examiner(s): Mancuso, Joseph
• Assistant Examiner(s): DEL ROSSO, GERARD DOMNICK
• Application Number:
  US08/240,079
• Time in Patent Office: 1,373 Days
• Field of Search: 382/48, 382/8, 382/18, 382/53, 382/141, 382/145, 382/151, 382/194, 382/192, 382/282, 382/273, 348/135, 356/400, 356/401, 250/561
• US Class Current: 382/202
• CPC Class Codes: G06T 2207/30148 Semiconductor; IC; Wafer
• CPC Class Codes: G06T 7/70 Determining position or orientation of objects or cameras camera calibration G06T7/80
• 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,

wherein said mirror symmetry filter means includes means for filtering said projection signal P to generate two mirror symmetry signals, S₁ and S₂, wherein each signal S₁, S₂ is representative of the degree of symmetry of the projection signal P about each point therein, and wherein each signal S₁, S₂ is out of phase with the other,

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

D. 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.

3. An apparatus according to any of claim 1 and 2, wherein said mirror symmetry filter means includes

A. means for filtering a projection signal to generate said mirror symmetry signal, S₁, comprising elements S₁ i, wherein each element S₁ i has a value determined in accord with the mathematical function ##EQU6## B. means for filtering a projection signal to generate said mirror symmetry signal, S₂, comprising elements S₂ i, wherein each element S₂ i has a value determined in accord with the mathematical function ##EQU7##

4. An apparatus according to claim 3, wherein

A. said notch detection means includes means for operating on each said mirror symmetry signal, S₁, S₂, to generate corresponding peak location signals, L₁, L₂,

B. said peak locating means includes

i) means for identifying in said peak location signal L₁ a position and amplitude of a most significant peak,

ii) means for identifying positions and amplitudes of a neighboring point on each side of a most significant peak in said peak location signal L₂, and

iii) means for estimating from the positions and amplitudes of those neighboring points a location of the center of said linear pattern.

2. 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:

A. 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,

B. 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,

wherein said mirror symmetry filter means includes means for filtering said projection signal P to generate two mirror symmetry signals, S₁ and S₂, wherein each signal S₁, S₂ is representative of the degree of symmetry of the projection signal P about each point therein, and wherein each signal S₁, S₂ is out of phase with the other,

C. notch detection means, coupled with said mirror symmetry filter means, for operating on each said mirror symmetry signal with a selected mask to generate a corresponding peak location signal emphasizing a peak in each said mirror symmetry signal corresponding to a location of a center of the corresponding linear pattern,

D. 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

E. center point locating means, coupled with said peak locating means, for determining the center of said cross-hair pattern to lie at an intersection of the estimated locations of said linear patterns.

5. 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 detection means, coupled with said mirror symmetry filter means, for operating on said mirror symmetry signal with a selected mask to generate a peak location signal emphasizing a peak in said mirror symmetry signal corresponding to a location of a center of said linear pattern,

wherein said notch detection means includes means for operating on said mirror symmetry signal S with a selected mask in accord with the mathematical function ##EQU8## where N, P and Z are elements of said mask, each of respective lengths n, p and z, and

D. 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.

7. An apparatus according to any of claims 5 and 6, wherein said notch detection means includes means for generating said peak location signal L by operating on said mirror symmetry signal with a mask signal, M, said mask signal having an amplitude that peaks toward the center.

8. An apparatus according to claim 7, wherein said notch detection means includes means for generating said peak location signal L by operating on said mirror symmetry signal with a mask signal, M, said mask signal having elements M_k, where k is between 1 and 7, and where those elements have respective values 1/2, 1/2, 0, -1, 0, 1/2, 1/2.

6. 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:

A. 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,

B. 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,

C. notch detection means, coupled with said mirror symmetry filter means, for operating on each said mirror symmetry signal with a selected mask to generate a corresponding peak location signal emphasizing a peak in each said mirror symmetry signal corresponding to a location of a center of the corresponding linear pattern,

wherein said notch detection means includes means for operating on said mirror symmetry signal S with a selected mask in accord with the mathematical function ##EQU9## where N, P and Z are elements of said mask, each of respective lengths n, p and z, and

D. 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

E. center point locating means, coupled with said peak locating means, for determining the center of said cross-hair pattern to lie at an intersection of the estimated locations of said 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. 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,

B. 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,

wherein said mirror symmetry filter step includes a step for filtering said projection signal P to generate two mirror symmetry signals, S₁ and S₂, wherein each signal S₁, S₂ is representative of the degree of symmetry of the projection signal P about each point therein, and wherein each signal S₁, S₂ is out of phase with the other,

C. a notch detection step for operating on said mirror symmetry signal with a selected mask to generate a peak location signal emphasizing a peak in said mirror symmetry signal corresponding to a location of a center of said linear pattern, and

D. 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. 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 P_i, where i is an integer between 1 and a length of said image signal along the respective axis,

B. 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,

wherein said mirror symmetry filter step includes a step for filtering said projection signal P to generate two mirror symmetry signals, S₁ and S₂, wherein each signal S₁, S₂ is representative of the degree of symmetry of the projection signal P about each point therein, and wherein each signal S₁, S₂ is out of phase with the other,

C. a notch detection step for operating on each said mirror symmetry signal with a selected mask to generate a corresponding peak location signal emphasizing a peak in each said mirror symmetry signal corresponding to a location of a center of the corresponding linear pattern,

D. 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

E. a center point locating step for determining the center of said cross-hair pattern to lie at 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. a step for filtering a projection signal to generate said mirror symmetry signal, S₁, comprising elements S₁ i, wherein each element S₁ i has a value determined in accord with the mathematical function ##EQU10## B. a step for filtering a projection signal to generate said mirror symmetry signal, S₂, comprising elements S₂ i, wherein each element S₁ i has a value determined in accord with the mathematical function ##EQU11##

12. A method according to claim 11, wherein

A. said notch detection step includes a step for operating on each said mirror symmetry signal, S₁, S₂, to generate corresponding peak location signals, L₁, L₂,

B. said peak locating step includes

i) a step for identifying in said peak location signal L₁ a position and amplitude of a most significant peak,

ii) means for identifying positions and amplitudes of a neighboring points on each side of a most significant peak in said peak location signal L₂, and

iii) means for estimating, from the positions and amplitudes of those neighboring points a location of the center of said linear pattern.

13. 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. 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, wherein i is an integer between 1 and a length of said image signal along said axis,

B. 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,

C. a notch detection step for operating on said mirror symmetry signal with a selected mask to generate a peak location signal emphasizing a peak in said mirror symmetry signal corresponding to a location of a center of said linear pattern,

wherein said notch detection means includes means for operating on said mirror symmetry signal S with a selected mask in accord with the mathematical function ##EQU12## where N, P and Z are elements of said mask, each of respective lengths n, p and z, and

D. 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.

15. A method according to any of claims 13 and 14, wherein said notch detection step includes a step for generating said peak location signal L by operating on said mirror symmetry signal with a mask signal, M, said mask signal having an amplitude that peaks toward the center.

16. A method according to claim 15, wherein said notch detection step includes a step for generating said peak location signal L by operating on said mirror symmetry signal with a mask signal, M, said mask signal having elements M_k, where k is between 1 and 6, and where those elements have respective values 1/2, 1/2, 0, -1, 0, 1/2, 1/2.

14. 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. 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 P_i, where i is an integer between 1 and a length of said image signal along the respective axis,

B. 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,

C. a notch detection step for operating on each said mirror symmetry signal with a selected mask to generate a corresponding peak location signal emphasizing a peak in each said mirror symmetry signal corresponding to a location of a center of the corresponding linear pattern,

wherein said notch detection means includes means for operating on said mirror symmetry signal S with a selected mask in accord with the mathematical function ##EQU13## where N, P and Z are elements of said mask, each of respective lengths n, p and z, and

D. 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

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