Hough transform supporting methods and arrangements

• US 6,826,311 B2
• Filed: 01/04/2001
• Issued: 11/30/2004
• 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.
• Primary Examiner(s): Mehta, Bhavesh M.
• Assistant Examiner(s): PATEL, KANJIBHAI B
• Application Number:
  US09/754,865
• Publication Number:
  US 20020114518A1
• Time in Patent Office: 1,426 Days
• Field of Search: 382/199, 382/200, 382/276, 382/168, 382/181, 382/190, 382/192, 382/107, 382/205, 382/251, 382/266, 382/273, 382/279, 382/281, 382/306, 382/307, 345/619, 345/418, 345/419, 345/615, 345/441, 378/58
• 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 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, 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.

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 a histogram computation to find a maxima value in a Hough transform voting buffer.

5. The method as recited in claim 1 wherein the performing operation comprises template matching.

6. The method as recited in claim 1 wherein the alpha-blending operation adds a tent function to the accumulators, the tent function characterizing errors associated with the observation.

7. The method as recited in claim 1 wherein the alpha-blending operation adds a Gaussian function to the accumulators, the Gaussian function characterizing errors associated with the observation.

8. The method as recited in claim 1 wherein the graphics processor performs the alpha-blending operation on multiple channels in parallel.

9. The method as recited in claim 1 wherein the graphics processor comprises a 3-Dimensional accelerator.

10. The method as recited in claim 1 wherein the accumulators are arranged in an array wherein related parameters are contiguous.

11. An apparatus comprising:

a host processor configured to provide image data;

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; and

a local memory operatively coupled to the graphics processor, 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.

12. The apparatus as recited in claim 11, wherein the graphics processor is configured to count votes in a resulting Hough transform voting buffer within the local memory.

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

14. The apparatus as recited in claim 11, wherein the graphics processor performs a histogram computation to find a maxima value in a Hough transform voting buffer within the local memory.

15. The apparatus as recited in claim 11 wherein the graphics processor is configured to perform template matching.

16. The apparatus as recited in claim 11 wherein the alpha-blending operation adds a tent function to the accumulators, the tent function characterizing errors associated with the observation.

17. The apparatus as recited in claim 11 wherein the alpha-blending operation adds a Gaussian function to the accumulators, the Gaussian function characterizing errors associated with the observation.

18. The apparatus as recited in claim 11 wherein the graphics processor performs the alpha-blending operation on multiple channels in parallel.

19. The apparatus as recited in claim 11 wherein the graphics processor comprises a 3-Dimensional accelerator.

20. The apparatus as recited in claim 11 wherein the accumulators are arranged in an array wherein related parameters are contiguous.

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

providing image data;

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

,

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

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

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

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

25. The computer-readable medium as recited in claim 21 wherein the performing operation comprises template matching.

26. The computer-readable medium as recited in claim 21 wherein the alpha-blending operation adds a tent function to the accumulators, the tent function characterizing errors associated with the observation.

27. The computer-readable medium as recited in claim 21 wherein the alpha-blending operation adds a Gaussian function to the accumulators, the Gaussian function characterizing errors associated with the observation.

28. The computer-readable medium as recited in claim 21 wherein the graphics processor performs the alpha-blending operation on multiple channels in parallel.

29. The computer-readable medium as recited in claim 21 wherein the graphics processor comprises a 3-Dimensional accelerator.

30. The computer-readable medium as recited in claim 21 wherein the accumulators are arranged in an array wherein related parameters are contiguous.