|
|
IDL Reference Guide: Procedures and Functions |
|
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.
The Hough transform is defined for a function A(x, y) as:
where d is the Dirac delta-function. With A(x, y), each point (x, y) 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.
Consider an image Amn of dimensions M by N, with array indices m = 0,..., M–1 and n = 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:
The backprojection, Bmn, contains all of the straight lines given by the (q, r) points given in H(q, r). The discrete formula is
where the slopes and offsets are given by:
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] )
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.
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.
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 (x, y) 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. |
Set this keyword to force the computation to be done using double-precision arithmetic.
Set this keyword equal to a scalar specifying the spacing Dr between r coordinates, expressed in the same units as Array. The default is [(DX2 + DY2)/2]1/2, which is 1/SQRT(2) times the diagonal distance between pixels. 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.
Set this keyword equal to a scalar specifying the spacing between the horizontal (X) coordinates. The default is 1.0.
Set this keyword equal to a scalar specifying the spacing between the vertical (Y) coordinates. The default is 1.0.
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.
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.
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.
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.
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.
For the forward transform, set this keyword to a named variable that, on exit, will contain the radial (r) coordinates, in units defined by the DX and DY keywords (pixels by default). If BACKPROJECT is specified, this keyword must contain the r coordinates of the input Array.
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.
For the forward transform, set this keyword to a named variable containing a vector of angular (q) coordinates (in radians) 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)
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.
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.
| Note Also see Transforming to and from the Hough and Radon Domains. |
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.
 |
IDL Online Help (March 06, 2007)
