HOUGH TRANSFORM FOR CIRCLES

• US 20140153834A1
• Filed: 12/03/2012
• Published: 06/05/2014
• Est. Priority Date: 12/03/2012
• Status: Active Grant

• Current Assignee: Analog Devices, Inc.
• Original Assignee: Analog Devices, Inc.
• Inventors: Poyil, Bijesh, Sripadarao, Anil M.
• Granted Patent: US 9,053,389 B2
• Time in Patent Office: Days
• US Class Current: 382/199
• CPC Class Codes: G06F 18/213 Feature extraction, e.g. by transforming the feature space; Summarisation; Mappings, e.g. subspace methods
• CPC Class Codes: G06T 7/62 of area, perimeter, diameter or volume
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation
• CPC Class Codes: G06V 20/582 of traffic signs
• CPC Class Codes: G06V 40/193 Preprocessing; Feature extraction

Abstract

The Hough transform for circles can be implemented in a manner that avoids random access to the Hough accumulator array by successively identifying center candidates in each line of the image based on edge pixels in corresponding lines voting on the line of interest.

Claims

1. A method for detecting circles in digital images, the method comprising:

(a) computationally detecting edge pixels in an image and storing coordinate information of the detected edge pixels in a plurality of edge buffers based on edge angles associated with the pixels; and

(b) computationally identifying, successively in each of at least one selected line of the image, centers of circles having radii within a specified range by (i) identifying, for each edge angle, lines of edge pixels whose distance from the selected line is within the specified range of radii, (ii) parsing the identified lines of edge pixels and, based at least in part on the edge angle and the coordinate information of the detected edge pixels, accumulating votes from the edge pixels on the selected line, and (iii) identifying the centers in the selected lines based at least in part on the accumulated votes.

2. The method of claim 1, wherein each of the plurality of edge buffers stores coordinate information only of edge pixels whose edge directions are within a bin of edge directions associated with that buffer.

3. The method of claim 2, wherein the plurality of edge buffers collectively provide bins for all possible edge directions.

4. The method of claim 1, wherein the coordinate information is stored in two one-dimensional edge buffers for each edge angle, the first edge buffer storing horizontal positions of the edge pixels and the second buffer storing cumulative total numbers of edge pixels associated with each line of the image.

5. The method of claim 1, further comprising, prior to step (b), eliminating lines of the image for which the cumulative number of edge pixels within respective lines of edge pixels whose distance from said line of the image is within the specified range of radii falls below a specified threshold for a specified positive number of edge directions, the non-eliminated lines constituting the selected lines of step (b).

6. The method of claim 5, wherein the specified number of edge directions is one.

7. The method of claim 5, wherein the specified number of edge directions is at least two.

8. The method of claim 1, wherein the votes from the edge pixels on the selected line are accumulated in a one-dimensional accumulator buffer.

9. The method of claim 8, wherein the one-dimensional accumulator buffer is reused successively for each of the at least one selected line.

10. The method of claim 1, wherein parsing the identified lines of edge pixels comprises iterating through the radii within the specified range and, for each iteration, determining an associated line of edge pixels and parsing the identified line of edge pixels to accumulate votes on the selected line of the image by computing a center coordinate associate with each pixel and incrementing a counter for the center coordinate.

11. The method of claim 1, wherein centers in the selected lines are identified based further on at least one of a vote threshold or a specified total number of circle centers.

12. The method of claim 1, further comprising, for each of the identified circle centers, determining an associated radius by accumulating votes from edge pixels for all edge angles for the radii within the specified range and identifying a maximum of the accumulated votes.

13. A system for detecting circles in a digital image comprising a stored array of pixels, the system comprising:

memory for storing coordinate information of edge pixels in the image in a plurality of edge buffers based on edge angles associated with the pixels; and

a processor configured to identify, successively in each of at least one selected line of the image, centers of circles having radii within a specified range by (i) identifying, for each edge angle, lines of edge pixels whose distance from the selected line is within the specified range of radii, (ii) parsing the identified lines of edge pixels and, based at least in part on the edge angle and the coordinate information of the detected edge pixels, accumulating votes from the edge pixels on the selected line, and (iii) identifying the centers in the selected lines based at least in part on the accumulated votes.

14. The system of claim 13, wherein each of the plurality of edge buffers stores coordinate information only of edge pixels whose edge directions are within a bin of edge directions associated with that buffer.

15. The system of claim 13, wherein the plurality of edge buffers collectively provide bins for all possible edge directions.

16. The system of claim 13, wherein the coordinate information is stored in two one-dimensional edge buffers for each edge angle, the first edge buffer storing horizontal positions of the edge pixels and the second buffer storing cumulative total numbers of edge pixels associated with each line of the image.

17. The system of claim 13, wherein the processor is further configured to eliminate lines of the image for which the cumulative number of edge pixels within respective lines of edge pixels whose distance from said line of the image is within the specified range of radii falls below a specified threshold for a specified positive number of edge directions, the non-eliminated lines constituting the selected lines.

18. The system of claim 13, wherein the processor is further configured to accumulate the votes from the edge pixels on the selected line in a one-dimensional accumulator buffer.

19. The system of claim 18, wherein the one-dimensional accumulator buffer is reusable successively for each of the at least one selected line.

20. The system of claim 13, wherein the processor is further configured to parse the identified lines of edge pixels by iterating through the radii within the specified range and, for each iteration, determining an associated line of edge pixels and parsing the identified line of edge pixels to accumulate votes on the selected line of the image by computing a center coordinate associate with each pixel and incrementing a counter for the center coordinate.

21. The method of claim 13, wherein the processor is further configured to identify the centers in the selected lines based further on at least one of a vote threshold or a specified total number of circle centers.

22. The system of claim 13, wherein the processor is further configured to determine, for each of the identified circle centers, an associated radius by accumulating votes from edge pixels for all edge angles for the radii within the specified range and identifying a maximum of the accumulated votes.