Hough transform method for linear ribbon and circular ring detection in the gradient domain

• US 8,526,731 B2
• Filed: 09/15/2012
• Issued: 09/03/2013
• Est. Priority Date: 08/29/2008
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Chen, Simon, Li, Xinju, Chien, Jen-Chen
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US13/621,180
• Publication Number:
  US 20130011057A1
• Time in Patent Office: 353 Days
• Field of Search: 382/168, 382/199, 382/276, 382/190, 382/281
• US Class Current: 382/168
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

A method for converting a portion of an image from a first domain to a second domain. The method may apply a Hough transform on the converted portion of the image, including calculating a range of angles for each tested pixel q relative to a center pixel p, quantizing the range of angles into a plurality of bins, voting each tested pixel q using a range of bins using a weighted voting schema; and detecting one or more features in the portion of the image. The methods may be implemented by program instructions executing in parallel on CPU(s) or GPUs.

Claims

1. A computer-implemented method, comprising:

converting a portion of an image from a first domain to a second domain to generate a converted portion of the image, wherein the portion of the image comprises a plurality of pixels, wherein each pixel has a value, wherein the converted portion of the image comprises gradient magnitudes corresponding to changes in values for respective pixels in the portion of the image, wherein the plurality of pixels comprises a center pixel;

finding one or more edge pixels in the portion of the image using a weight function applied to a gradient magnitude of the one or more edge pixels, the weight function being based on an angle between a gradient direction of the one or more edge pixels, and a line between the one or more edge pixels and the center pixel;

using each of the one or more edge pixels and the center pixel, calculating a range of radii for each of the one or more edge pixels that contains one or more rings that pass through both the edge pixel and the center pixel;

using the range of radii for each of the one or more edge pixels, voting for each of the one or more edge pixels in a histogram having plurality of bins, wherein each bin of the plurality of bins corresponds to a quantization of radii; and

using the histogram, detecting one or more features in the portion of the image.

2. The method of claim 1, wherein one or more of the edge pixels is found to be an edge pixel based on its respective gradient having a direction that is orthogonal within a specified amount to a line between the first pixel and the center pixel.

3. The method of claim 1, wherein said finding the one or more edge pixels in the portion of the image comprises using pixels of the plurality of pixels having a gradient magnitude greater than a first threshold.

4. The method of claim 1, wherein the one or more rings have a maximum predetermined width.

5. The method of claim 1, wherein said detecting the one or more features comprises:

combining votes in the histogram corresponding to a same edge direction to create a merged histogram;

finding candidates for the one or more features based on peaks in the merged histogram.

6. The method of claim 5, further comprising:

merging two or more peaks in the histogram if the distance between the two or more peaks is smaller than a second threshold.

7. The method of claim 1, wherein said voting comprises using binary votes.

8. The method of claim 1, wherein said voting comprises using weighted votes, wherein each weighted vote corresponds to a respective gradient magnitude for each pixel.

9. The method of claim 1, further comprising:

un-warping the image prior to said converting, wherein said un-warping operates to correct one or more geometric distortions in the image.

10. The method of claim 1, further comprising:

un-warping the image during one or more of said finding, said calculating, or said voting;

wherein said un-warping operates to correct one or more geometric distortions in the image.

11. The method of claim 1, wherein a sliding window is used to define the portion of the image, and wherein the method further comprises moving the sliding window to one or more other portions of the image to detect one or more features in the one or more other portions of the image.

12. A system, comprising:

one or more processors; and

a memory coupled to the one or more processors, wherein the memory stores program instructions executable by the one or more processors to perform operations including;

converting a portion of an image from a first domain to a second domain to generate a converted portion of the image, wherein the portion of the image comprises a plurality of pixels, wherein each pixel has a value, wherein the converted portion of the image comprises gradient magnitudes corresponding to changes in values for of pixels comprises a center pixel;

finding one or more edge pixels in the portion of the image;

using each of the one or more edge pixels and the center pixel, calculating a range of radii for each of the one or more edge pixels that contains one or more rings that pass through both the edge pixel and the center pixel;

using the range of radii for each of the one or more edge pixels, voting for each of the one or more edge pixels in a histogram having plurality of bins, wherein each bin of the plurality of bins corresponds to a quantization of radii; and

using the histogram, detecting one or more features in the portion of the image by;

combining votes in the histogram corresponding to a same edge direction to create a merged histogram; and

finding candidates for the one or more features based on peaks in the merged histogram.

13. The system of claim 12, wherein a first pixel of the plurality of pixels is found to be an edge pixel according to a weight function on its gradient magnitude, wherein the weight function is dependent on an angle between the first pixel'"'"'s gradient direction and a line between the first pixel and the center pixel.

14. The system of claim 12, wherein a first pixel of the plurality of pixels is found to be an edge pixel only if its respective gradient has a direction that is orthogonal within a specified amount to a line between the first pixel and the center pixel.

15. The system of claim 12, wherein said voting comprises using binary votes.

16. The system of claim 12, wherein said voting comprises using weighted votes, wherein each weighted vote corresponds to a respective gradient magnitude for each pixel.

17. The system of claim 12, wherein a sliding window is used to define the portion of the image, and wherein the operations further include moving the sliding window to one or more other portions of the image to detect one or more features in the one or more other portions of the image.

18. A computer-readable storage medium storing program instructions executable to implement operations comprising:

un-warping an image to correct one or more geometric distortions in the image;

converting a portion of the image from a first domain to a second domain to generate a converted portion of the image, wherein the portion of the image comprises a plurality of pixels, wherein each pixel has a value, wherein the converted portion of the image comprises gradient magnitudes corresponding to changes in values for respective pixels in the portion of the image, wherein the plurality of pixels comprises a center pixel;

finding one or more edge pixels in the portion of the image;

using each of the one or more edge pixels and the center pixel, calculating a range of radii for each of the one or more edge pixels that contains one or more rings that pass through both the edge pixel and the center pixel;

using the range of radii for each of the one or more edge pixels, voting for each of the one or more edge pixels in a histogram having plurality of bins, wherein each bin of the plurality of bins corresponds to a quantization of radii; and

using the histogram, detecting one or more features in the portion of the image.

19. The computer-readable storage medium of claim 18, wherein a first pixel of the plurality of pixels is found to be an edge pixel according to a weight function on its gradient magnitude, wherein the weight function is dependent on an angle between the first pixel'"'"'s gradient direction and a line between the first pixel and the center pixel.

20. The computer-readable storage medium of claim 18, wherein a first pixel of the plurality of pixels is found to be an edge pixel only if its respective gradient has a direction that is orthogonal within a specified amount to a line between the first pixel and the center pixel.

21. The computer-readable storage medium of claim 18, wherein said detecting the one or more features comprises:

combining votes in the histogram corresponding to a same edge direction to create a merged histogram;

finding candidates for the one or more features based on peaks in the merged histogram.

22. The computer-readable storage medium of claim 18, wherein said voting comprises using binary votes.

23. The computer-readable storage medium of claim 18, wherein said voting comprises using weighted votes, wherein each weighted vote corresponds to a respective gradient magnitude for each pixel.

24. The computer-readable storage medium of claim 18, wherein a sliding window is used to define the portion of the image, and wherein the operations further include moving the sliding window to one or more other portions of the image to detect one or more features in the one or more other portions of the image.