Apparatus and method for detecting and sub-pixel location of edges in a digital image

• US 6,408,109 B1
• Filed: 10/07/1996
• Issued: 06/18/2002
• Est. Priority Date: 10/07/1996
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Wallack, Aaron, Silver, William, Garakani, Arman
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): CHAWAN, SHEELA C
• Application Number:
  US08/727,721
• Time in Patent Office: 2,080 Days
• Field of Search: 382/263, 382/266, 382/269, 382/199, 382/189, 382/190, 382/203, 382/281
• US Class Current: 382/300
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/12 Edge-based segmentation

Abstract

The invention provides a fast, computationally inexpensive, and highly accurate method and apparatus for edge detection in a digital image, even for edges that are not substantially parallel to the axes of the pixel grid, by exploiting computationally inexpensive estimates of gradient magnitude and direction. In particular, the method includes the steps of: estimating gradient magnitude and direction at a plurality of regularly-spaced pixel points in the image so as to provide a plurality of estimates of gradient magnitude and direction, each such estimate being associated with a respective gradient point of a regularly-spaced gradient grid; using gradient direction associated with each gradient point to select a respective set of neighboring gradient points; comparing gradient magnitude associated with each gradient point with each gradient magnitude of the respective set of neighboring gradient magnitudes so as to determine which of the gradient magnitudes is a local maximum in approximately the gradient direction; and using the local maximum of gradient magnitude and a set of neighboring gradient magnitudes to determine an interpolated edge position along a one-dimensional gradient magnitude profile. Another aspect of the invention for providing two-dimensional edge position interpolation further includes the step of determining a plane position line normal to the gradient direction of a gradient point associated with the local maximum of gradient magnitude, the plane position line also passing through the interpolated edge position, along which plane position line at least one two-dimensional interpolated position of the edge can be determined.

Claims

1. An apparatus for detection and sub-pixel location of edges in a digital image, said digital image including a plurality of pixel values, each pixel value being associated with a respective pixel point of a regularly-spaced pixel grid, said apparatus comprising:

a gradient estimator for estimating gradient magnitude and gradient direction at a plurality of regularly-spaced gradient points in said digital image, so as to provide a plurality of estimates of gradient magnitude and gradient direction, each said estimate of gradient magnitude and gradient direction being associated with a respective gradient point of a regularly-spaced gradient grid;

a peak detector, cooperative with said gradient estimator, operating such that gradient direction associated with each gradient point is used to select a respective set of neighboring gradient points, and operating such that gradient magnitude associated with each gradient point is compared with each gradient magnitude of said respective set of neighboring gradient magnitudes so as to determine which of said gradient magnitudes is a local maximum of gradient magnitude in approximately said gradient direction; and

a sub-pixel interpolator, cooperative with said peak detector, operating such that said local maximum of gradient magnitude and a set of neighboring gradient magnitudes are used to determine an interpolated edge position along a one-dimensional gradient magnitude profile including a gradient point associated with said local maximum of gradient magnitude and each gradient point associated with said set of neighboring gradient magnitudes.

2. The apparatus of claim 1, further comprising:

a plane positioner, cooperative with said interpolator and said gradient estimator, said plane positioner operating so as to determine a plane position line normal to the gradient direction of a gradient point associated with said local maximum of gradient magnitude, said plane position line also passing through said interpolated edge position, along which plane position line at least one two-dimensional interpolated position of the edge can be determined.

3. The apparatus of claim 2, wherein said plane positioner operates so as to determine said at least one two-dimensional interpolated position of the edge as being at an intersection point of two lines:

a gradient direction line extending from a gradient point associated with said local maximum of gradient magnitude, said gradient direction line extending along said gradient direction of said gradient point; and

said plane position line that is normal to said gradient direction, also passing through said interpolated edge position.

4. The apparatus of claim 1, wherein said interpolator includes at least one interpolation function.

5. The apparatus of claim 1, wherein said interpolator includes a plurality of interpolation functions, each interpolation function being selected for use in accordance with gradient direction at each said local maximum of gradient magnitude.

6. The apparatus of claim 1, further including an edge position bias element, cooperative with said interpolator, that operates to adjust an edge position provided by said interpolator.

7. The apparatus of claim 6, wherein said edge position bias element adjusts edge position provided by said interpolator in accordance with gradient direction at each said local maximum of gradient magnitude.

8. The apparatus of claim 1, wherein said gradient estimator includes apparatus for implementing the CORDIC algorithm.

9. The apparatus of claim 1, wherein said gradient estimator includes an orthogonal gradient component estimator for providing orthogonal gradient components, cooperative with a gradient magnitude and gradient direction approximator for using said orthogonal gradient components to provide gradient magnitude and gradient direction approximations.

10. The apparatus of claim 1, wherein said peak detector operates such that said respective set of neighboring gradient points is co-linear.

11. Apparatus for detection and sub-pixel location of edges in a digital image, said digital image including a plurality of pixel values, each pixel value being associated with a respective pixel point of a regularly-spaced pixel grid, said apparatus comprising:

gradient estimation means for estimating gradient magnitude and gradient direction at a plurality of regularly-spaced gradient points in said digital image, so as to provide a plurality of estimates of gradient magnitude and gradient direction, each said estimate of gradient magnitude and gradient direction being associated with a respective gradient point of a regularly-spaced gradient grid;

peak detection means, cooperative with said gradient estimation means, for using gradient direction associated with each gradient point to select a respective set of neighboring gradient points, and for comparing gradient magnitude associated with each gradient point with each gradient magnitude of said respective set of neighboring gradient magnitudes so as to determine which of said gradient magnitudes is a local maximum of gradient magnitude in approximately said gradient direction; and

sub-pixel interpolation means, cooperative with said peak detection means, for using said local maximum of gradient magnitude and a set of neighboring gradient magnitudes to determine an interpolated edge position along a one-dimensional gradient magnitude profile including a gradient point associated with said local maximum of gradient magnitude and each gradient point associated with said set of neighboring gradient magnitudes.

12. The apparatus of claim 11, further comprising:

plane position means, cooperative with said interpolation means and said gradient estimation means, said plane position means for determining a plane position line normal to the gradient direction of a gradient point associated with said local maximum of gradient magnitude, said plane position line also passing through said interpolated edge position, along which plane position line at least one two-dimensional interpolated position of the edge can be determined.

13. The apparatus of claim 12, wherein said plane position means also includes means for determining said at least one two-dimensional interpolated position of the edge as being at an intersection point of two lines:

a gradient direction line extending from a gradient point associated with said local maximum of gradient magnitude, said gradient direction line extending along said gradient direction of said gradient point; and

said plane position line that is normal to said gradient direction, also passing through said interpolated edge position.

14. The apparatus of claim 11, wherein said interpolation means includes at least one interpolation function.

15. The apparatus of claim 11, wherein said interpolation means includes:

a plurality of interpolation functions; and

selection means for selecting, in accordance with gradient direction at each said local maximum of gradient magnitude, an interpolation function from said plurality of interpolation functions.

16. The apparatus of claim 11, further including edge position bias means, cooperative with said interpolation means, for adjusting an edge position provided by said interpolation means.

17. The apparatus of claim 16, wherein said edge position bias means adjusts edge position provided by said interpolation means in accordance with gradient direction at each said local maximum of gradient magnitude.

18. The apparatus of claim 11, wherein said gradient estimation means includes CORDIC algorithm means.

19. The apparatus of claim 11, wherein said gradient estimation means includes orthogonal gradient component estimation means for providing orthogonal gradient components, cooperative with gradient magnitude and gradient direction approximation means for using said orthogonal gradient components to provide gradient magnitude and gradient direction approximations.

20. The apparatus of claim 11, wherein said peak detector operates such that said respective set of neighboring gradient points is co-linear.

21. A method for detection and sub-pixel location of edges in a digital image, said digital image including a plurality of pixel values, each pixel value being associated with a respective pixel point of a regularly-spaced pixel grid, the method comprising the steps of:

estimating gradient magnitude and gradient direction at a plurality of regularly-spaced gradient points in said digital image, so as to provide a plurality of estimates of gradient magnitude and gradient direction , each said estimate of gradient magnitude and gradient direction being associated with a respective gradient point of a regularly-spaced gradient grid;

using gradient direction associated with each gradient point to select a respective set of neighboring gradient points, and comparing gradient magnitude associated with each gradient point with each gradient magnitude of said respective set of neighboring gradient magnitudes so as to determine which of said gradient magnitudes is a local maximum of gradient magnitude in approximately said gradient direction; and

using said local maximum of gradient magnitude and a set of neighboring gradient magnitudes to determine an interpolated sub-pixel edge position along a one-dimensional gradient magnitude profile including a gradient point associated with said local maximum of gradient magnitude and each gradient point associated with said set of neighboring gradient magnitudes.

22. The method of claim 21, further comprising the step of:

determining a plane position line normal to the gradient direction of a gradient point associated with said local maximum of gradient magnitude, said plane position line also passing through said interpolated edge position, along which plane position line at least one two-dimensional interpolated position of the edge can be determined.

23. The method of claim 22, further including the step of:

determining said at least one two-dimensional interpolated position of the edge as being at an intersection point of two lines;

a gradient direction line extending from a gradient point associated with said local maximum of gradient magnitude, said gradient direction line extending along said gradient direction of said gradient point; and

said plane position line that is normal to said gradient direction, also passing through said interpolated edge position.

24. The method of claim 21, said step of determining an interpolated edge position further includes the step of using an interpolation function.

25. The method of claim 24, wherein said step of using an interpolation function includes the step of:

selecting from among a plurality of interpolation functions, in accordance with gradient direction at each said local maximum of gradient magnitude, an interpolation function from said plurality of interpolation functions.

26. The method of claim 21, further including the step of:

adjusting the interpolated edge position in accordance with a power law curve.

27. The method of claim 26, further including the step of:

adjusting edge position in accordance with gradient direction at each said local maximum of gradient magnitude.

28. A method for detection and sub-pixel location of edges in a digital image, said digital image including a plurality of pixel values, each pixel value being associated with a respective pixel point of a regularly-spaced pixel grid, the method comprising the steps of:

estimating gradient magnitude and gradient direction at a plurality of regularly-spaced gradient points in said digital image, so as to provide a plurality of estimates of gradient magnitude and gradient direction, each said estimate of gradient magnitude and gradient direction being associated with a respective gradient point of a regularly-spaced gradient grid;

using gradient direction associated with each gradient point to select a respective set of neighboring gradient points, and comparing gradient magnitude associated with each gradient point with each gradient magnitude of said respective set of neighboring gradient magnitudes so as to determine which of said gradient magnitudes is a local maximum of gradient magnitude in approximately said gradient direction;

using said local maximum of gradient magnitude and a set of neighboring gradient magnitudes to determine an interpolated edge position along a one-dimensional gradient magnitude profile including a gradient point associated with said local maximum of gradient magnitude and each gradient point associated with said set of neighboring gradient magnitudes;

determining a plane position line normal to the gradient direction of a gradient point associated with said local maximum of gradient magnitude, said plane position line also passing through said interpolated edge position, along which plane position line at least one two-dimensional interpolated position of the edge can be determined; and

determining said at least one two-dimensional interpolated position of the edge as being at an intersection point of two lines;

a gradient direction line extending from a gradient point associated with said local maximum of gradient magnitude, said gradient direction line extending along said gradient direction of said gradient point, and said plane position line that is normal to said gradient direction, also passing through said interpolated edge position.

29. The method of claim 28, said step of determining an interpolated edge position further includes the step of:

using an interpolation function by selecting an interpolation function from among a plurality of interpolation functions, selecting in accordance with gradient direction at each said local maximum of gradient magnitude.

30. The method of claim 29, wherein said plurality of interpolation functions includes a parabolic function and a linear function.

31. The method of claim 28, further including the step of:

adjusting the interpolated edge position in accordance with a power law curve.

32. The method of claim 28, further including the step of:

adjusting edge position in accordance with gradient direction at each said local maximum of gradient magnitude.

33. An apparatus for detection and sub-pixel location of edges in a digital image, said digital image including a plurality of pixel values, each pixel value being associated with a respective pixel point of a regularly-spaced pixel grid, said apparatus comprising:

a gradient estimator for estimating gradient magnitude and gradient direction at a plurality of regularly-spaced gradient points in said digital image, so as to provide a plurality of estimates of gradient magnitude and gradient direction, each said estimate of gradient magnitude and gradient direction being associated with a respective gradient point of a regularly-spaced gradient grid, said gradient estimator including apparatus for implementing Sobel edge detection, and apparatus for implementing the CORDIC algorithm;

a peak detector, cooperative with said gradient estimator, operating such that gradient direction associated with each gradient point is used to select a respective set of neighboring gradient points, operating such that gradient magnitude associated with each gradient point is compared with each gradient magnitude of said respective set of neighboring gradient magnitudes so as to determine which of said gradient magnitudes is a local maximum of gradient magnitude in approximately said gradient direction, and operating such that said respective set of neighboring gradient points is co-linear,

an interpolator, cooperative with said peak detector, operating such that said local maximum of gradient magnitude and a set of neighboring gradient magnitudes are used to determine an interpolated edge position along a one-dimensional gradient magnitude profile including a gradient point associated with said local maximum of gradient magnitude and each gradient point associated with said set of neighboring gradient magnitudes, said interpolator including a parabolic interpolation function;

an edge position bias element, cooperative with said interpolator, that operates to adjust an edge position provided by said interpolator; and

a plane positioner, cooperative with said edge position bias element and said gradient estimator, said plane positioner operating so as to determine a plane position line normal to the gradient direction of a gradient point associated with said local maximum of gradient magnitude, said plane position line also passing through said interpolated edge position, along which plane position line at least one two-dimensional interpolated position of the edge can be determined, wherein said plane positioner operates so as to determine said at least one two-dimensional interpolated position of the edge as being at an intersection point of two lines;

a gradient direction line extending from a gradient point associated with said local maximum of gradient magnitude, said gradient direction line extending along said gradient direction of said gradient point; and

said plane position line that is normal to said gradient direction, also passing through said interpolated edge position.

34. The apparatus of claim 33, wherein said edge position bias element adjusts edge position provided by said interpolator in accordance with gradient direction at each said local maximum of gradient magnitude.