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

• US 6,690,842 B1
• Filed: 04/02/2002
• Issued: 02/10/2004
• Est. Priority Date: 10/07/1996
• Status: Expired due to Term

• Current Assignee: Cognex Corporation
• Original Assignee: Cognex Corporation
• Inventors: Garakani, Arman, Wallack, Aaron, Silver, William
• Primary Examiner(s): Johnson; Timothy M.
• Assistant Examiner(s): Chawan; Sheela
• Application Number:
  US10/114,357
• Time in Patent Office: 679 Days
• Field of Search: 382/263,266,269,199,189,190,203,281,300
• 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 magnitude associated with each gradient point is used to select a plurality of gradient points that substantially have a local maximum of gradient magnitude in approximately said gradient direction; and

a subpixel interpolator, cooperative with said gradient estimator and said peak detector, 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 said local maximum of gradient magnitude and the gradient magnitudes of the respective set of neighboring gradient points 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 respective set of neighboring gradient points.

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 two-dimensional interpolated position of the edge, wherein;

the two-dimensional interpolated position lies along a line that passes through the gradient point associated with said local maximum of gradient magnitude, and that is oriented substantially parallel to the gradient direction of said gradient point, and

the direction from said two-dimensional interpolated position to said interpolated edge position is substantially normal to the gradient direction.

3. The apparatus of claim 1, wherein the respective set of neighboring gradient points is selected from east-west, north-south, northeast-southwest, and northwest-southeast neighbors.

4. The apparatus of claim 1, wherein the interpolator uses a parabolic interpolation function to determine said interpolated edge position.

5. The apparatus of claim 1, wherein the respective set of neighboring gradient points is selected from east-west, north-south, northeast-southwest, and northwest-southeast neighbors, and said interpolator uses a parabolic interpolation function to determine said interpolated edge position.

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

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 magnitude associated with each gradient point to select a plurality of gradient points that substantially have a local maximum of gradient magnitude in approximately said gradient direction; and

subpixel interpolation means, cooperative with said gradient estimation means and said peak detection means, for using gradient direction associated with each gradient point to select a respective set of neighboring gradient points, and for using said local maximum of gradient magnitude and the gradient magnitudes of the respective set of neighboring gradient points 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 respective set of neighboring gradient points.

12. The apparatus of claim 10, wherein the respective set of neighboring gradient points is selected from east-west, north-south, northeast-southwest, and northwest southeast neighbors.

13. The apparatus of claim 10, wherein the interpolation means uses a parabolic interpolation function to determine said interpolated edge position.

14. The apparatus of claim 10, wherein the respective set of neighboring gradient points is selected from east-west, north-south, northeast-southwest, and northwest-southeast neighbors, and said interpolation means uses a parabolic interpolation function to determine said interpolated edge position.

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

16. The apparatus of claim 15, 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.

17. The apparatus of claim 10, wherein said gradient estimation means includes CORDIC algorithm means.

18. The apparatus of claim 10, 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.

11. The apparatus of claimed 10 further comprising:

plane position means, cooperative with said interpolation means and said gradient estimation means, said plane position means for determining a two-dimensional interpolated position of the edge, wherein;

the two-dimensional interpolated position lies along a line that passes through the gradient point associated with said local maximum of gradient magnitude, and that is oriented substantially parallel to the gradient direction of said gradient point, and

the direction from said two-dimensional interpolated position to said interpolated edge position is substantially normal to the gradient direction.

19. 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 magnitude associated with each gradient point to select a plurality of gradient points that substantially have a local maximum of gradient magnitude in approximately said gradient direction;

using gradient direction associated with each gradient point to select a respective set of neighboring gradient points; and

using said local maximum of gradient magnitude and the gradient magnitudes of the respective set of neighboring gradient points to determine a subpixel 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 respective set of neighboring gradient points.

20. The method of claim 19, further comprising the steps of:

determining a two-dimensional interpolated position of the edge, wherein;

the two-dimensional interpolated position lies along a line that passes through the gradient point associated with said local maximum of gradient magnitude, and that is oriented substantially parallel to the gradient direction of said gradient point, and

the direction from said two-dimensional interpolated position to said interpolated edge position is substantially normal to the gradient direction.

21. The method of claim 19, wherein the respective set of neighboring gradient points is selected from east-west, north-south, northeast-southwest, and northwest-southeast neighbors.

22. The method of claim 19, wherein a parabolic interpolation function is used to determine said interpolated edge position.

23. The method of claim 19, wherein the respective set of neighboring gradient points is selected from east-west, north-south, northeast-southwest, and northwest-southeast neighbors, and said interpolated edge position is determined using a parabolic interpolation function.

24. The method of claim 19, further including the step of:

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

25. The method of claim 19, further including the step of:

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

26. The method of claim 19 wherein the step of estimating gradient magnitude and gradient direction includes a CORDIC algorithm.

27. 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 gradient points in said digital image;

using gradient magnitude associated with each gradient point to select a plurality of gradient points that substantially have a local maximum of gradient magnitude;

using gradient direction associated with each gradient point to select a respective set of neighboring gradient points;

using said local maximum of gradient magnitude and the gradient magnitudes of the selected respective set of neighboring gradient points to determine a subpixel interpolated edge position; and

determining a two-dimensional position of the edge, wherein;

the two-dimensional interpolated position lies along a line that passes through the gradient point associated with said local maximum of gradient magnitude, and that is oriented substantially parallel to the gradient direction of said gradient point; and

the direction from said two-dimensional interpolated position to said interpolated edge position is substantially normal to the gradient direction.

28. The method of claim 27, wherein the respective set of neighboring gradient points is selected from east-west, north-south, northeast-southwest, and northwest-southeast neighbors.

29. The method of claim 27, wherein a parabolic interpolation function is used to determine said interpolated edge position.

30. The method of claim 27, wherein the respective set of neighboring gradient points is selected from east-west, north-south, northeast-southwest, and northwest-southeast neighbors, and said interpolated edge position is determined using a parabolic interpolation function.

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

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

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

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

33. The method of claim 27 wherein the step of estimating gradient magnitude and gradient direction includes a CORDIC algorithm.