Accelerating the hough transform

• US 8,150,207 B2
• Filed: 12/31/2007
• Issued: 04/03/2012
• Est. Priority Date: 12/31/2007
• Status: Expired due to Fees

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Li, Wenlong, Wang, Tao, Zhang, Yimin
• Primary Examiner(s): Chen, Wenpeng
• Application Number:
  US11/967,701
• Publication Number:
  US 20090169130A1
• Time in Patent Office: 1,555 Days
• Field of Search: 382/281, 701/28
• US Class Current: 382/281
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

The present disclosure describes a method and apparatus for accelerating computation of a Hough transform of a plurality of digital images of known width and height dimensions. The method includes determining a plurality of Hough values for each pixel location based on the width and height dimensions. The method further includes generating a lookup table comprising an array of Hough values corresponding to one or more Hough parameters of at least one geometric shape in at least one digital image. Each element in the array of Hough values may be based on a value of one or more Hough parameters and at least one of a height value or a width value. The method may include receiving a plurality of digital images having known width and height dimensions. The method may further include selecting, for at least one nonzero pixel of at least one of the plurality of digital images, the Hough values from the lookup table. Of course, many alternatives, variations and modifications are possible without departing from this embodiment.

Claims

1. A method of accelerating computation of a Hough transform of a plurality of digital images of known width and height dimensions, comprising:

determining a plurality of Hough values for each pixel location based on the width and height dimensions;

generating a lookup table stored in memory comprising an array of Hough values corresponding to one or more Hough parameters of at least one geometric shape in at least one digital image, wherein each element in said array of Hough values is based on a value of said one or more Hough parameters and at least one of a height value or a width value;

sorting detected shapes;

determining a maximum accumulated number of waveforms;

selectively erasing nearby maximums of accumulated numbers of waveforms;

filling gaps between short line segments;

linking line segments that are nearby; and

outputting parametric data.

2. The method of claim 1, further comprising:

receiving a plurality of digital images having known width and height dimensions; and

selecting, for at least one nonzero pixel of at least one of the plurality of digital images, one or more Hough values from said lookup table.

3. The method of claim 1, wherein said geometric shape is a line and said Hough parameters are a length of a normal to said line and an angle between said normal and a horizontal axis.

4. The method of claim 1, wherein said geometric shape is a circle and said Hough parameters are coordinates of a center of said circle and a radius of said circle.

5. The method of claim 1, wherein each said element in said array of Hough values is based on a height value and a width value.

6. A processor for detecting a geometric shape in a digital image of known width and height dimensions comprising:

electronic circuitry configured to determine a plurality of Hough values for each pixel location based on the width and height dimensions;

configured to generate a lookup table comprising an array of Hough values corresponding to one or more Hough parameters of at least one geometric shape in at least one digital image, wherein each element in said array of Hough values is based on a value of said one or more Hough parameters and at least one of a height value or a width value;

configured to sort detected shapes;

configured to determine a maximum accumulated number of waveforms;

configured to selectively erase nearby maximums of accumulated numbers of waveforms;

configured to fill gaps between short line segments;

configured to link line segments that are nearby; and

configured to output parametric data.

7. The processor of claim 6, further comprising:

electronic circuitry configured to receive a plurality of digital images having known width and height dimensions; and

configured to select, for at least one nonzero pixel of at least one of the plurality of digital images, one or more Hough values from said lookup table.

8. The processor of claim 7, wherein said processor is a vector processor further comprising electronic circuitry configured to operate on a plurality of Hough values simultaneously.

9. The processor of claim 7, wherein said processor comprises a plurality of vector processors wherein each said vector processor further comprises electronic circuitry configured to operate on a plurality of Hough values simultaneously and wherein said vector processors share memory.

10. The processor of claim 8, wherein said processor is configured to operate on four Hough values simultaneously.

11. The processor of claim 9, wherein each said processor is configured to operate on four Hough values simultaneously.

12. An article, comprising:

a non-transitory storage medium having stored thereon instructions that when executed by a processor results in the following;

determining a plurality of Hough values for each pixel location based on the width and height dimensions;

generating a lookup table comprising an array of Hough values corresponding to one or more Hough parameters of at least one geometric shape in at least one digital image, wherein each element in said array of Hough values is based on a value of said one or more Hough parameters and at least one of a height value or a width value;

sorting detected shapes;

determining a maximum accumulated number of waveforms;

selectively erasing nearby maximums of accumulated numbers of waveforms;

filling gaps between short line segments;

linking line segments that are nearby; and

outputting parametric data.

13. The article of claim 12, wherein said instructions that when executed by said processor result in the following additional operations:

receiving a plurality of digital images having known width and height dimensions; and

selecting, for at least one nonzero pixel of at least one of the plurality of digital images, one or more Hough values from said lookup table.

14. The article of claim 12, wherein said instructions that when executed by said processor result in the following additional operations:

receiving a plurality of digital images having known width and height dimensions; and

selecting, for at least one nonzero pixel of at least one of the plurality of digital images, a plurality Hough values simultaneously from said lookup table.

15. The article of claim 14, wherein said instructions that when executed by said processor result in the following additional operations:

operating on said plurality of Hough values simultaneously and determining a Hough transform for said nonzero pixel.