Edge peak contour tracker

• US 5,987,172 A
• Filed: 12/06/1995
• Issued: 11/16/1999
• Est. Priority Date: 12/06/1995
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Michael, David
• Primary Examiner(s): Boudreau, Leo H.
• Assistant Examiner(s): Tran, Phuoc
• Application Number:
  US08/567,946
• Time in Patent Office: 1,441 Days
• Field of Search: 382/199, 382/197, 382/266, 382/242
• US Class Current: 382/199
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06T 7/194 involving foreground-background segmentation

Abstract

A method and apparatus for finding an edge contour in an image of an object is provided that is robust against object/background misclassification due to non-uniform illumination across an image, while also being computationally efficient, and avoiding the need to select a classification threshold. The invention can be used to partition an image of a scene into object regions and background regions, or foreground regions and background regions, using edge contours found in the image. The invention is particularly useful for analysis of images of back-lit objects. The edge contour is progressively formed by finding a sequence of one-dimensional edge positions, each one-dimensional edge position being determined by processing a set of pixels arranged along at least one imaginary line.

Claims

1. A method for finding an edge contour in an image, the edge contour including a sequence of contour points, the method comprising the steps of:

determining the position of a current contour point by locating the peak of a first difference signal of a gray value signal using pixels of a pixel set extending across the edge contour;

advancing to determine the position of a next contour point using the position of the current countour point; and

returning to the step of determining the position of a current countour point, the next contour point becoming the current contour point.

2. The method of claim 1, wherein locating the peak of a first difference signal includes the step of:

using said first difference signal to find an interpolated peak.

3. The method of claim 1, wherein the step of locating the peak of a first difference signal of a gray value signal using a pixel set extending across the edge contour is performed using pixels of the set that are disposed along a line parallel to a coordinate axis of the image.

4. The method of claim 1, wherein said first difference signal includes at least three data points.

5. The method of claim 1, wherein locating the peak of said first difference signal of a gray value signal is performed using a pixel set extending across the edge contour in a first direction, the method further including the step of:

locating the peak of a second first difference signal of a second gray value signal using pixels of the pixel set that are disposed across the edge contour in a second direction.

6. A method for finding an edge contour, the method comprising the steps of:

determining the position and direction of an initial current boundary point;

selecting a plurality of pixels along a first line that is non-parallel to the direction of said current boundary point;

computing a first difference signal along said plurality of pixels;

finding the position of a peak of said first difference signal;

using said position of said peak to determine a position and direction of a new current boundary point; and

returning to the step of selecting a plurality of pixels.

7. The method of claim 6, further including the step of:

selecting a plurality of pixels along a second line that is non-parallel to the direction of said current boundary point, and that is non-parallel to the direction of said first line.

8. The method of claim 6, wherein said step of finding the position of a peak of said first difference signal includes the steps of:

fitting a curve to a plurality of data points of said first difference signal; and

finding the position of a maximum of said curve.

9. The method of claim 6, further including the step of:

selecting a plurality of pixels along a third line that is non-parallel to the direction of said current boundary point, that is non-parallel to the direction of said first line, and that is that is non-parallel to the direction of said second line.

10. A method for finding an edge contour in an image, the edge contour including a plurality of contour points, the method comprising the steps of:

determining the position and direction of an initial current contour point;

selecting a plurality of pixels along a first line through said current contour point that is non-parallel to the direction of said current contour point;

computing an edge enhancement signal along said plurality of pixels;

finding the position of a peak of said edge enhancement signal;

using said position of said peak to determine a position and direction of a new current contour point; and

returning to the step of selecting a plurality of pixels.

11. The method of claim 10, further including the step of:

selecting a plurality of pixels along a second line through said current contour point that is non-parallel to the direction of said current contour point, and that is non-parallel to the direction of said first line.

12. The method of claim 10, wherein said step of finding the position of a peak of said edge enhancement signal includes the steps of:

fitting a curve to a plurality of data points of said edge enhancement signal; and

finding the position of a maximum of said curve.

13. The method of claim 10, further including the step of:

selecting a plurality of pixels along a third line through said current contour point that is non-parallel to the direction of said current contour point, that is non-parallel to the direction of said first line, and that is that is non-parallel to the direction of said second line.

14. An apparatus for finding an edge contour in an image, the edge contour including a plurality of contour points, the apparatus comprising:

initial determining means for determining the position and direction of an initial current contour point;

first selecting means, connected to said determining means, for selecting a plurality of pixels along a first line through said current contour point that is non-parallel to the direction of said current contour point;

computing means, connected to said first selecting means, for computing an edge enhancement signal along said plurality of pixels;

finding means, connected to said computing means, for finding the position of a peak of said edge enhancement signal; and

new determining means, connected to said finding means and to said first selecting means, for using said position of said peak to determine a position and direction of a new current contour point.

15. The apparatus of claim 14, further comprising:

second selecting means, connected to said first selecting means, for selecting a plurality of pixels along a second line through said current contour point that is non-parallel to the direction of said current contour point, and that is non-parallel to the direction of said first line.

16. The apparatus of claim 14, wherein said finding means for finding the position of a peak of said edge enhancement signal includes:

fitting means for fitting a curve to a plurality of data points of said edge enhancement signal; and

finding means, connected to said fitting means, for finding the position of a maximum of said curve.

17. The apparatus of claim 14, further comprising:

third selecting means, connected to said first selecting means, for selecting a plurality of pixels along a third line through said current contour point that is non-parallel to the direction of said current contour point, that is non-parallel to the direction of said first line, and that is that is non-parallel to the direction of said second line.