## HOUGH

The HOUGH function implements the Hough transform, used to detect straight lines within a two-dimensional image. This function can be used to return either the Hough transform, which transforms each nonzero point in an image to a sinusoid in the Hough domain, or the Hough backprojection, where each point in the Hough domain is transformed to a straight line in the image.

#### Hough Transform Theory

The Hough transform is defined for a function A(x, y) as:

where d is the Dirac delta-function. With A(xy), each point (xy) in the original image, A, is transformed into a sinusoid r = xcosq - ysinq, where r is the perpendicular distance from the origin of a line at an angle q (The angle q will be limited to 0 <= q < p which could result in negative r values.):

Points that lie on the same line in the image will produce sinusoids that all cross at a single point in the Hough transform. For the inverse transform, or backprojection, each point in the Hough domain is transformed into a straight line in the image.

Usually, the Hough function is used with binary images, in which case H(q, r) gives the total number of sinusoids that cross at point (q, r), and hence, the total number of points making up the line in the original image. By choosing a threshold T for H(q, r), and using the inverse Hough function, you can filter the original image to keep only lines that contain at least T points.

##### How IDL Implements the Hough Transform

Consider an image Amn of dimensions M by N, with array indices = 0,..., M-1 and = 0,..., N-1.

The discrete formula for the HOUGH function for Amn is:

where the brackets [ ] indicate rounding to the nearest integer, and

The pixels are assumed to have spacing Dx and Dy in the x and y directions. The delta-function is defined as:

##### How IDL Implements the Hough Backprojection

The backprojection, Bmn, contains all of the straight lines given by the (qr) points given in H(qr). The discrete formula is

where the slopes and offsets are given by:

### Syntax

Hough Transform:

Result = HOUGH( Array [, /DOUBLE] [, DRHO=scalar] [, DX=scalar] [, DY=scalar] [, /GRAY] [, NRHO=scalar] [, NTHETA=scalar] [, RHO=variable] [, RMIN=scalar] [, THETA=variable] [, XMIN=scalar] [, YMIN=scalar] )

Hough Backprojection:

Result = HOUGH( Array, /BACKPROJECT, RHO=variable, THETA=variable [, /DOUBLE] [, DX=scalar] [, DY=scalar] [, NX=scalar] [, NY=scalar] [, XMIN=scalar] [, YMIN=scalar] )

### Return Value

The result of this function is a two-dimensional floating-point array, or a complex array if the input image is complex. If Array is double-precision, or if the DOUBLE keyword is set, the result is double-precision, otherwise, the result is single-precision.

### Arguments

#### Array

The two-dimensional array of size M by N which will be transformed. If the keyword GRAY is not set, then, for the forward transform, Array is treated as a binary image with all nonzero pixels considered as 1.

### Keywords

#### BACKPROJECT

If set, the backprojection is computed, otherwise, the forward transform is computed. When BACKPROJECT is set, Result will be an array of dimension NX by NY.

 Note
The Hough transform is not one-to-one: each point (xy) is not mapped to a single (q, r). Therefore, instead of the original image, the backprojection, or inverse transform, returns an image containing the set of all lines given by the (q, r) points.

#### DOUBLE

Set this keyword to force the computation to be done using double-precision arithmetic.

#### DRHO

Set this keyword equal to a scalar specifying the spacing Dr between r coordinates, expressed in the same units as Array. The default is 1/SQRT(2) times the diagonal distance between pixels, [(DX2  + DY2)/2]1/2. A larger value produces a coarser resolution by mapping multiple pixels onto a single r; this is useful for images that do not contain perfectly straight lines. A smaller value may produce undersampling by trying to map fractional pixels onto r, and is not recommended. If BACKPROJECT is specified, this keyword is ignored.

#### DX

Set this keyword equal to a scalar specifying the spacing between the horizontal (X) coordinates. The default is 1.0.

#### DY

Set this keyword equal to a scalar specifying the spacing between the vertical (Y) coordinates. The default is 1.0.

#### GRAY

Set this keyword to perform a weighted Hough transform, with the weighting given by the pixel values. If GRAY is not set, the image is treated as a binary image with all nonzero pixels considered as 1. If BACKPROJECT is specified, this keyword is ignored.

#### NRHO

Set this keyword equal to a scalar specifying the number of r coordinates to use. The default is 2 CEIL([MAX(X2 + Y2)]1/2 / DRHO) + 1. If BACKPROJECT is specified, this keyword is ignored.

#### NTHETA

Set this keyword equal to a scalar specifying the number of q coordinates to use over the interval [0,p]. The default is CEIL(p [MAX(X2  + Y2)]1/2 / DRHO). A larger value will produce smoother results, and is useful for filtering before backprojection. A smaller value will result in broken lines in the transform, and is not recommended. If BACKPROJECT is specified, this keyword is ignored.

#### NX

If BACKPROJECT is specified, set this keyword equal to a scalar specifying the number of horizontal coordinates in the output array. The default is FLOOR(2 MAX(|RHO|)(DX2 + DY2)-1/2 + 1). For the forward transform this keyword is ignored.

#### NY

If BACKPROJECT is specified, set this keyword equal to a scalar specifying the number of vertical coordinates in the output array. The default is FLOOR(2 MAX(|RHO|)(DX2 + DY2)-1/2 + 1). For the forward transform, this keyword is ignored.

#### RHO

For the forward transform, set this keyword to a named variable that, on exit, will contain the radial (r) coordinates. If BACKPROJECT is specified, this keyword must contain the r coordinates of the input Array.

#### RMIN

Set this keyword equal to a scalar specifying the minimum r coordinate to use for the forward transform. The default is -0.5(NRHO - 1) DRHO. If BACKPROJECT is specified, this keyword is ignored.

#### THETA

For the forward transform, set this keyword to a named variable containing a vector of angular (q) coordinates to use for the transform. If NTHETA is specified instead, and THETA is set to a named variable, then on exit THETA will contain the q coordinates. If BACKPROJECT is specified, this keyword must contain the q coordinates of the input Array. HOUGH returns q in [0,p)

#### XMIN

Set this keyword equal to a scalar specifying the X coordinate of the lower-left corner of the input Array. The default is -(M-1)/2, where Array is an M by N array. If BACKPROJECT is specified, set this keyword equal to a scalar specifying the X coordinate of the lower-left corner of the Result. In this case the default is -DX (NX-1)/2.

#### YMIN

Set this keyword equal to a scalar specifying the Y coordinate of the lower-left corner of the input Array. The default is -(N-1)/2, where Array is an M by N array. If BACKPROJECT is specified, set this keyword equal to a scalar specifying the Y coordinate of the lower-left corner of the Result. In this case the default is
-DY (NY-1)/2.

### Examples

This example computes the Hough transform of a random set of pixels:

```PRO hough_example

;Create an image with a random set of pixels
seed = 12345   ; remove this line to get different random images
array = RANDOMU(seed,128,128) GT 0.95

;Draw three lines in the image
x = FINDGEN(32)*4
array[x,0.5*x+20] = 1b
array[x,0.5*x+30] = 1b
array[-0.5*x+100,x] = 1b

;Create display window, set graphics properties
WINDOW, XSIZE=330,YSIZE=630, TITLE='Hough Example'
!P.BACKGROUND = 255  ; white
!P.COLOR = 0 ; black
!P.FONT=2
ERASE

XYOUTS, .1, .94, 'Noise and Lines', /NORMAL
;Display the image. 255b changes black values to white:
TVSCL, 255b - array, .1, .72, /NORMAL

;Calculate and display the Hough transform
result = HOUGH(array, RHO=rho, THETA=theta)
XYOUTS, .1, .66, 'Hough Transform', /NORMAL
TVSCL, 255b - result, .1, .36, /NORMAL

;Keep only lines that contain more than 20 points:
result = (result - 20) > 0

;Find the Hough backprojection and display the output
backproject = HOUGH(result, /BACKPROJECT, RHO=rho, THETA=theta)
XYOUTS, .1, .30, 'Hough Backprojection', /NORMAL
TVSCL, 255b - backproject, .1, .08, /NORMAL

END
```

The following figure displays the output of this example. The top image shows three lines drawn within a random array of pixels that represent noise. The center image shows the Hough transform, displaying sinusoids for points that lie on the same line in the original image. The bottom image shows the Hough backprojection, after setting the threshold to retain only those lines that contain more than 20 points. The Hough inverse transform, or backprojection, transforms each point in the Hough domain into a straight line in the image.

### References

1. Gonzalez, R.C., and R.E. Woods. Digital Image Processing. Reading, MA: Addison Wesley, 1992.
2. Jain, Anil K. Fundamentals of Digital Image Processing. Englewood Cliffs, NJ: Prentice-Hall, 1989.
3. Toft, Peter. The Radon Transform: Theory and Implementation. Denmark: Technical University; 1996. Ph.D. Thesis.
4. Weeks, Arthur. R. Fundamentals of Electronic Image Processing. New York: SPIE Optical Engineering Press, 1996.

Introduced: 5.4