Using a geometry shader to perform a hough transform

• US 8,040,351 B1
• Filed: 11/02/2007
• Issued: 10/18/2011
• Est. Priority Date: 07/31/2007
• Status: Active Grant

• Current Assignee: NVIDIA Corporation
• Original Assignee: NVIDIA Corporation
• Inventors: Diard, Franck R.
• Primary Examiner(s): Wu; Xiao
• Assistant Examiner(s): Hoang; Phi
• Application Number:
  US11/934,725
• Time in Patent Office: 1,446 Days
• Field of Search: 382/149, 382/173, 382/103, 382/167, 702/185, 375/240, 375/240.1, 345/520
• US Class Current: 345/426
• CPC Class Codes: G06T 1/20 Processor architectures; Processor configuration, e.g. pipelining
• CPC Class Codes: G06T 15/005 General purpose rendering architectures
• CPC Class Codes: G06T 15/80 Shading
• CPC Class Codes: G06T 17/00 Three dimensional [3D] modelling, e.g. data description of 3D objects
• CPC Class Codes: G06T 17/005 Tree description, e.g. octree, quadtree
• CPC Class Codes: G06T 2200/28 involving image processing hardware
• CPC Class Codes: G06T 2210/21 Collision detection, intersection
• CPC Class Codes: G06T 7/13 Edge detection

Abstract

A system and method uses the capabilities of a geometry shader unit within the multi-threaded graphics processor to execute a geometry shader program and perform a Hough transform.

Claims

1. A computer-implemented method for using a geometry shader program to perform a Hough transform, comprising:

executing a pixel shader program by a multithreaded processor to compute input data defining a Hough map that includes coordinate pairs in Hough space representing lines of an input image in image space, wherein the pixel shader program is configured to compute the input data for the Hough map by rendering a graphics primitive that covers the entire input image and by intersecting the lines of the input image with the graphics primitive to generate the coordinate pairs;

executing the geometry shader program by the multithreaded processor to identify local maxima of the input data; and

storing the local maxima in an output buffer.

2. The method of claim 1, further comprising the step of determining regions of the input image, wherein each region of the input image is represented by a portion of the input data.

3. The method of claim 2, further comprising the step of generating a vertex for each one of the regions to produce a set of vertices.

4. The method of claim 3, wherein the step of processing the input data comprises executing the geometry shader program for each vertex in the set of vertices to produce portions of the local maxima.

5. The method of claim 4, wherein the geometry shader program is executed in parallel using a multithreaded processing core that is configured to allocate an execution thread to each vertex in the set of vertices.

6. The method of claim 4, wherein a y coordinate of each vertex in the set of vertices specifies a row in the output buffer.

7. The method of claim 1, wherein the geometry shader program is configured to disable clamping operations during the processing of the input data.

8. The method of claim 1, wherein the coordinate pairs include an angle and a distance.

9. A non-transitory computer readable medium including

instructions that when executed by

a multithreaded processor, cause the multithreaded processor to perform a Hough transform, by performing the steps of:

computing, according to a pixel shader program, input data defining a Hough map that includes coordinate pairs in Hough space representing lines within of image in image space, wherein the pixel shader program is configured to compute the input data for the Hough map by rendering a graphics primitive that covers the entire input image and by intersecting the lines of the input image with the graphics primitive to generate the coordinate pairs;

processing the input data according to a geometry shader program to identify local maxima of the input data; and

storing the local maxima in an output buffer.

10. The computer readable medium of claim 9, further comprising the step of determining regions of the input image, wherein each region of the input image is represented by a portion of the input data.

11. The computer readable medium of claim 10, further comprising the step of generating a vertex for each one of the regions to produce a set of vertices.

12. The computer readable medium of claim 11, wherein the step of processing the input data comprises executing the geometry shader program for each vertex in the set of vertices to produce portions of the local maxima.

13. The computer readable medium of claim 12, wherein the geometry shader program is executed in parallel using a multithreaded processing core that is configured to allocate an execution thread to each vertex in the set of vertices.

14. The computer readable medium of claim 12, wherein a y coordinate of each vertex in the set of vertices specifies a row in the output buffer.

15. A parallel processing unit configured to perform a Hough transform, the parallel processing unit comprising:

a memory configured to store a Hough map and an output buffer;

multiple processing cores configured to execute a pixel shader program and geometry shader program, which when executed, causes the multiple processing cores to;

compute, according to a pixel shader program, input data defining the Hough map that includes coordinate pairs in Hough space, the input data representing lines of an image in image space, wherein the pixel shader program cause the multiple processing cores to compute the input data for the Hough map by rendering a graphics primitive that covers the entire input image and by intersecting the lines of the input image with the graphics primitive to generate the coordinate pairs;

process the input data according to a geometry shader program to identify local maxima of the input data; and

store the local maxima in an output buffer.

16. The parallel processing unit of claim 15, wherein the geometry shader program further configures the parallel processing unit to divide the image into multiple regions and allocate a different execution thread to each one of the multiple regions in order to execute the geometry shader program in parallel.

17. The parallel processing unit of claim 16, wherein the geometry shader program further configures the parallel processing unit to generate a vertex for each one of the regions to produce a set of vertices.