Hough transform supporting methods and arrangements

• US 20020114518A1
• Filed: 01/04/2001
• Published: 08/22/2002
• Est. Priority Date: 01/04/2001
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Wilt, Nicholas P.
• Granted Patent: US 6,826,311 B2
• Time in Patent Office: Days
• US Class Current: 382/199
• CPC Class Codes: G06V 10/48 by mapping characteristic values of the pattern into a parameter space, e.g. Hough transformation

Abstract

The Hough Transform is a computer vision algorithm that can robustly detect a wide variety of features such as lines, circles, and anything else that can be readily parameterized or otherwise cast in terms of a discrete popularity algorithm. Unfortunately, not all processors or like devices are capable of providing the requisite processing capability usually associated with the Hough Transform. The methods and arrangements presented herein leverage the dedicated hardware of a graphics card to provide a portion of the data processing. This is done by: in a pre-processing step, gathering observations that can be mapped into a parameter space of a desired feature or features; then, quantizing the parameter space of the desired feature(s); for each discrete quantized parameter combination, allocating a accumulator and initialize it to 0; for each observation, incrementing all of the accumulators that correspond to parameter combinations that might have produced the observation; and finding maxima in the quantized parameter array. This last step is a post-processing step that is completed by dedicated graphics hardware having an alpha-blending capability programmed to find maxima, i.e., record votes associated with the Hough Transform.

Claims

1. A method comprising:

providing image data; and

performing a Hough transform on the image data using a host processor and an operatively configured graphics processor.

2. The method as recited in claim 1, wherein the graphics processor is configured to count votes in a resulting Hough transform voting buffer.

3. The method as recited in claim 1, wherein the graphics processor is configured to convolve image values and provide corresponding results to the host processor.

4. The method as recited in claim 1, wherein the graphics processor performs an alpha-blending operation that selectively increments accumulators that correspond to parameter combinations that are likely associated with an observation.

5. The method as recited in claim 1, wherein the graphics processor performs a histogram computation to find the maxima value in the Hough transform voting buffer.

6. An apparatus comprising:

a host processor configured to provide image data; and

a graphics processor operatively coupled to the host processor and configured to perform selected steps of a Hough transform algorithm on the image data in association with the host processor.

7. The apparatus as recited in claim 6, further comprising a local memory operatively coupled to the graphics processor and wherein the graphics processor is configured to count votes in a resulting Hough transform voting buffer within the local memory.

8. The apparatus as recited in claim 6, wherein the graphics processor is configured to convolve image values and provide corresponding results to the host processor.

9. The apparatus as recited in claim 6, further comprising a local memory operatively coupled to the graphics processor and wherein the graphics processor performs an alpha-blending operation that selectively increments accumulators within the local memory that correspond to parameter combinations that are likely associated with an observation.

10. The apparatus as recited in claim 6, further comprising a local memory operatively coupled to the graphics processor and wherein the graphics processor performs a histogram computation to find the maxima value in the Hough transform voting buffer within the local memory.

11. A computer-readable medium having computer-executable instructions for performing steps comprising:

providing image data; and

performing a Hough transform on the image data using a host processor and an operatively configured graphics processor.

12. The computer-readable medium as recited in claim 11, having computer-executable instructions that cause the graphics processor to count votes in a resulting Hough transform voting buffer.

13. The computer-readable medium as recited in claim 11, having computer-executable instructions that cause the graphics processor is to convolve image values and provide corresponding results to the host processor.

14. The computer-readable medium as recited in claim 11, having computer-executable instructions that cause the graphics processor to perform an alpha-blending operation that selectively increments accumulators that correspond to parameter combinations that are likely associated with an observation.

15. The computer-readable medium as recited in claim 11, having computer-executable instructions that cause the graphics processor to perform a histogram computation to find the maxima value in the Hough transform voting buffer.

16. A method comprising:

causing dedicated graphics hardware to support a at least one of the following steps associated with a Hough transform algorithm;

quantizing a bounded portion of a parameter space that may contain a desired feature;

for each discrete quantized parameter combination, allocating an incrementable accumulator;

gathering observations that can be mapped into the parameter space;

for each observation, incrementing each of the accumulators that corresponds to parameter combinations that may have produced the observation; and

determining the maxima in a resulting quantized parameter array and the corresponding parameter combinations.