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

• US 8,320,670 B1
• Filed: 11/21/2008
• Issued: 11/27/2012
• Est. Priority Date: 08/29/2008
• Status: Active Grant

• Current Assignee: Adobe Inc.
• Original Assignee: Adobe Systems Incorporated (Adobe Inc.)
• Inventors: Chen, Simon, Chien, Jen-Chan, Li, Xinju
• Primary Examiner(s): CHANG, JON CARLTON
• Application Number:
  US12/276,101
• Time in Patent Office: 1,467 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 each of the one or more edge pixels and the center pixel, calculating a range of angles for each of the one or more edge pixels that contains one or more beams that each pass through both the edge pixel and the center pixel;

using the range of angles 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 angles; and

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

2. The method of claim 1, 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.

3. The method of claim 2,

wherein said finding the edge pixel 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 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.

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

6. 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.

7. The method of claim 6,

wherein the one or more features comprise one or more of corners or rings.

8. The method of claim 6, 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.

9. The method of claim 1,

wherein said voting comprises using binary votes.

10. 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.

11. 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.

12. 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.

13. 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 implement;

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 each of the one or more edge pixels and the center pixel, calculating a range of angles for each of the one or more edge pixels that contains one or more beams that pass through both the edge pixel and the center pixel;

using the range of angles 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 angles; and

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

14. The system of claim 13, 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.

15. The system of claim 13,

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.

16. The system of claim 13, 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.

17. The system of claim 13,

wherein said voting comprises using binary votes.

18. The system of claim 13,

wherein said voting comprises using weighted votes, wherein each weighted vote corresponds to a respective gradient magnitude for each pixel.

19. A computer-readable storage medium storing program instructions executable to implement:

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 each of the one or more edge pixels and the center pixel, calculating a range of angles for each of the one or more edge pixels that contains one or more beams that pass through both the edge pixel and the center pixel;

using the range of angles 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 angles; and

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

20. The computer-readable storage medium of claim 19, 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.

21. The computer-readable storage medium of claim 19,

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 substantially orthogonal to a line between the first pixel and the center pixel.

22. The computer-readable storage medium of claim 19, 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.

23. The computer-readable storage medium of claim 19,

wherein said voting comprises using binary votes.

24. The computer-readable storage medium of claim 19,

wherein said voting comprises using weighted votes, wherein each weighted vote corresponds to a respective gradient magnitude for each pixel.

25. The computer-readable storage medium of claim 19, wherein the program instructions are executable to further implement:

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

26. A computer-implemented method, comprising:

executing instructions on a computing platform so that binary digital electronic signals representing a portion of an image in a first domain are converted to a second domain, wherein the portion of the image comprises a plurality of pixels including a center pixel, wherein each pixel has a value;

executing instructions on the computing platform so that a relaxed Hough transform is applied on binary digital electronic signals representing the converted portion of the image, wherein applying the relaxed Hough transform comprises;

determining one or more edge pixels in the portion of the image according to a weight function on the gradient magnitude of each of the plurality of pixels in the portion of the image;

calculating a range of angles for a possible one or more features common to each edge pixel relative to the center pixel;

quantizing the range of angles into a plurality of bins;

voting for each edge pixel in a histogram using the plurality of bins using weighted votes; and

executing instructions on the computing platform so that binary digital electronic signals representing the histogram are used to detect one or more features in the portion of the image.

27. The method of claim 26,

wherein the weight function is dependent on an angle between the gradient direction of each edge pixel and a line between each edge pixel and the center pixel.

28. The method of claim 26,

wherein each respective pixel of the plurality of pixels is determined to be an edge pixel only if its respective gradient has a direction that is substantially orthogonal to a line between the respective pixel and the center pixel.

29. The method of claim 26, 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.

30. The method of claim 26,

wherein said voting comprises using binary votes.

31. The method of claim 26,

wherein said voting comprises using weighted votes, wherein each weighted vote corresponds to a respective gradient magnitude for each pixel.