Fast Hysteresis Thresholding in Canny Edge Detection

• US 20110081087A1
• Filed: 10/02/2009
• Published: 04/07/2011
• Est. Priority Date: 10/02/2009
• Status: Abandoned Application

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Moore, Darnell J.
• Application Number:
  US12/572,704
• Publication Number:
  US 20110081087A1
• Time in Patent Office: Days
• US Class Current: 382/199
• CPC Class Codes: G06T 7/13 Edge detection
• CPC Class Codes: G06V 20/40 in video content extracting overlay text G06V20/62; video retrieval G06F16/70; processing of video elementary streams in video servers H04N21/234; processing of video elementary streams in video clients H04N21/44

Abstract

A method of image processing is provided which includes non-recursive hysteresis thresholding in Canny edge detection. The non-recursive hysteresis thresholding reduces computational complexity and eliminates the potential for call stack overflow. More specifically, hysteresis thresholding is performed in a raster-scan order pass over the image data to connect edge segments to form continuous edges.

Claims

1. A method of image processing comprising:

generating an edge map of a block of pixels, wherein each pixel is identified as a non-edge pixel or a possible edge pixel; and

performing hysteresis thresholding on the edge map to identify edge pixels using an upper gradient magnitude threshold and a lower gradient magnitude threshold, wherein the hysteresis thresholding comprises;

identifying a pixel as an edge pixel and adding a location of the pixel in the edge map to an edge data structure when a gradient magnitude of the pixel is above the upper gradient magnitude threshold and the pixel is identified as a possible edge pixel in the edge map, wherein the edge data structure stores locations of edge pixels to be checked for connection to possible edge pixels; and

identifying edge pixels connected to the pixel by

selecting an edge pixel from the edge data structure,

identifying a neighboring pixel of the selected edge pixel as an edge pixel and adding a location of the neighboring pixel in the edge map to the edge data structure when a gradient magnitude of the neighboring pixel is greater than the lower gradient threshold and the neighboring pixel is identified as a possible edge pixel in the edge map, and

repeating selecting an edge pixel and identifying a neighboring pixel until all edge pixels in the edge data structure have been selected.

2. The method of claim 1, further comprising:

identifying all pixels in the edge map that are identified as possible edge pixels as non-edge pixels after hysteresis thresholding.

3. The method of claim 1, further comprising:

identifying boundary pixels in the block of pixels as non-edge pixels.

4. The method of claim 1, wherein identifying a pixel further comprises:

identifying the pixel as an edge pixel and adding the location of the pixel to the edge data structure when the gradient magnitude of the pixel is equal to the upper gradient magnitude threshold.

5. The method of claim 1, wherein identifying a neighboring pixel further comprises:

identifying the neighboring pixel as an edge pixel and adding the location of the neighboring pixel to the edge data structure when the gradient magnitude of the neighboring pixel is equal to the lower gradient threshold.

6. The method of claim 1, wherein selecting an edge pixel comprises:

removing the selected edge pixel from the edge data structure.

7. The method of claim 1, further comprising:

applying a Gaussian filter to the block of pixels to remove noise;

applying a gradient filter to the filtered block of pixels to measure horizontal and vertical gradients at each pixel and to estimate a gradient magnitude for each pixel based on the horizontal gradient and vertical gradient of the pixel; and

generating the edge map by performing non-maximum suppression on the filtered block of pixels using the horizontal and vertical gradients and the gradient magnitudes.

8. A digital image processing system comprising:

a memory configured to store an edge map of a block of pixels, wherein each pixel is identified as a non-edge pixel or a possible edge pixel and an edge data structure for storing locations of edge pixels to be checked for connection to possible edge pixels; and

an edge detection component configured to

generate the edge map; and

perform hysteresis thresholding on the edge map to identify edge pixels using an upper gradient magnitude threshold and a lower gradient magnitude threshold, wherein the hysteresis thresholding comprises;

identifying a pixel as an edge pixel and adding a location of the pixel in the edge map to the edge data structure when a gradient magnitude of the pixel is above the upper gradient magnitude threshold and the pixel is identified as a possible edge pixel in the edge map; and

identifying edge pixels connected to the pixel by

selecting a location of an edge pixel from the edge data structure,

identifying a neighboring pixel of the selected edge pixel as an edge pixel and adding a location of the neighboring pixel in the edge map to the edge data structure when a gradient magnitude of the neighboring pixel is greater than the lower gradient threshold and the neighboring pixel is identified as a possible edge pixel in the edge map, and

repeating selecting a location of an edge pixel and identifying a neighboring pixel until all edge pixels in the edge data structure have been selected.

9. The digital image processing system of claim 8, wherein the edge detection component is further configured to:

identify all pixels in the edge map that are identified as possible edge pixels as non-edge pixels after hysteresis thresholding.

10. The digital image processing system of claim 8, wherein the edge detection component is further configured to:

identifying boundary pixels in the block of pixels as non-edge pixels.

11. The digital image processing system of claim 8, wherein identifying a pixel comprises:

identifying the pixel as an edge pixel and adding the location of the pixel to the edge data structure when the gradient magnitude of the pixel is equal to the upper gradient magnitude threshold.

12. The digital image processing system of claim 8, wherein identifying a neighboring pixel further comprises:

identifying the neighboring pixel as an edge pixel and adding the location of the neighboring pixel to the edge data structure when the gradient magnitude of the neighboring pixel is equal to the lower gradient threshold.

13. The digital image processing system of claim 8, wherein selecting an edge pixel comprises:

removing the selected edge pixel from the edge data structure.

14. The digital image processing system of claim 8, wherein the edge detection component is further configured to:

apply a Gaussian filter to the block of pixels to remove noise;

apply a gradient filter to the filtered block of pixels to measure horizontal and vertical gradients at each pixel and to estimate a gradient magnitude for each pixel based on the horizontal gradient and vertical gradient of the pixel; and

generate the edge map by performing non-maximum suppression on the filtered block of pixels using the horizontal and vertical gradients and the gradient magnitudes.

15. A computer readable medium comprising executable instructions to cause a digital system to perform a method of image processing, the method comprising:

generating an edge map of a block of pixels, wherein each pixel is identified as a non-edge pixel or a possible edge pixel; and

performing hysteresis thresholding on the edge map to identify edge pixels using an upper gradient magnitude threshold and a lower gradient magnitude threshold, wherein the hysteresis thresholding comprises;

identifying a pixel as an edge pixel and adding a location of the pixel in the edge map to an edge data structure when a gradient magnitude of the pixel is above the upper gradient magnitude threshold and the pixel is identified as a possible edge pixel in the edge map, wherein the edge data structure stores locations of edge pixels to be checked for connection to possible edge pixels; and

identifying edge pixels connected to the pixel by

selecting a location of an edge pixel from the edge data structure,

identifying a neighboring pixel of the selected edge pixel as an edge pixel and adding a location of the neighboring pixel in the edge map to the edge data structure when a gradient magnitude of the neighboring pixel is greater than the lower gradient threshold and the neighboring pixel is identified as a possible edge pixel in the edge map, and

repeating selecting a location of an edge pixel and identifying a neighboring pixel until all locations of edge pixels in the edge data structure have been selected.

16. The computer readable medium comprising of claim 15, wherein the method further comprises:

identifying all pixels in the edge map that are identified as possible edge pixels as non-edge pixels after hysteresis thresholding.

17. The computer readable medium comprising of claim 15, wherein the method further comprises:

identifying boundary pixels in the block of pixels as non-edge pixels.

18. The computer readable medium comprising of claim 15, wherein identifying a pixel further comprises:

identifying the pixel as an edge pixel and adding the location of the pixel to the edge data structure when the gradient magnitude of the pixel is equal to the upper gradient magnitude threshold.

19. The computer readable medium comprising of claim 15, wherein identifying a neighboring pixel further comprises:

identifying the neighboring pixel as an edge pixel and adding the location of the neighboring pixel to the edge data structure when the gradient magnitude of the neighboring pixel is equal to the lower gradient threshold.

20. The computer readable medium comprising of claim 15, wherein the method further comprises:

applying a Gaussian filter to the block of pixels to remove noise;

applying a gradient filter to the filtered block of pixels to measure horizontal and vertical gradients at each pixel and to estimate a gradient magnitude for each pixel based on the horizontal gradient and vertical gradient of the pixel; and

generating the edge map by performing non-maximum suppression on the filtered block of pixels using the horizontal and vertical gradients and the gradient magnitudes.