Hough Transform

This topic is a stub. For the HTML MIPAV help refer to [1]

Background

The Hough transform is a technique which is used to determine and isolate features of a particular shape within an image. The classical Hough transform requires that the desired shapes be specified in some parametric form. It is most commonly used for the detection of simple curves such as lines, circles, and ellipses within a given image.

The Hough Transform uses (xi, yi) points in the original 2D image space to generate

• (rho, theta) points in the Hough transform space for lines,
• (x0, y0, radius) points in the Hough transform space for circles,
• (p, q, r1, r2, theta) points in the Hough transform space for ellipses,
• and (xv, yv, phi, p) points in the Hough transform space for parabolas.

Linear Hough transform

A set of image points (a), and how they can be fit into various line segments - (b) and (c)

Parametric Hough transform: (a) a straight line in the original coordinates described in terms of the length of a normal from the origin to the line - r and orientation theta; (b) the Hough plane where points A, B, and C are transformed into three sinusoidal curves

The simplest case of Hough transform is the linear transform used for detecting straight lines. For example, consider a set of discrete image points such as come as an output from an edge detector algorithm. The problem is fitting the points into a set of line segments. The figure on your right shows some possible solutions to this problem.

In the image space, the straight line can be described as y = mx + b and can be graphically plotted for each pair of image points (x, y). In the Hough transform, the idea is to describe the characteristics of the shape in terms of its parameters. In case of a straight line these parameters are the slope parameter m and the intercept parameter b. However, the slope approaches infinity as the line becomes more vertical. This problem is resolved by describing any straight line (A, B) with the parametric line equation:

<math> x_0*cos(\theta) + y_0*sin(\theta)= r (\theta) </math>

where,

- r is the length of a normal from the origin to the line,

- <math>\theta</math> is the orientation of the line with respect to the X axis.

If we plot the all possible point <math>(r_i, \theta_i)</math> defined by each pair of <math>(x_i, y_i)</math> in Cartesian space, they appear as sinusoids in the polar Hough parameter space. This point-to-curve transformation is the Hough transformation for straight lines. When viewed in Hough parameter space, points which are collinear in the Cartesian image space become readily apparent as they yield curves which intersect at a common (r, theta) point. See the figure on your right.

Accumulator

The two bright spots are the Hough parameters of the two lines. From these spots' positions, r and theta parameters for two lines in the input image can be determined

To detect the existence of a particular line y = mx + b in the image, the Hough transform algorithm uses an array, called accumulator. The dimension of the accumulator is equal to the number of unknown parameters of a given Hough transform. Therefore, for localizing straight lines a two dimensional accumulator is used. Three dimensions are used for circles, four dimensions are used for parabolas, and five dimensions are used for ellipses.

The transform is implemented by quantizing the Hough parameter space into finite intervals or accumulator cells. As the algorithm runs, each <math>(x_i, y_i)</math> is transformed into a discrete <math>(r, \theta)</math> curve and the accumulator cells which lie along this curve are incremental. Resulting peaks in the accumulator array represent strong evidence that a corresponding straight line exists in the image.

As the algorithm runs, it takes each point <math>(x_i, y_i)</math> and transforms it into a discrete <math>(r, \theta)</math> curve. Then, it increments the accumulator cells which lie along this curve. Bins with the highest values or peaks in the accumulator array represent strong evidence that a corresponding straight line exists in the image.

Outline of the Hough line detection algorithm

This MIPAV algorithm generates a Hough transform of the source image using the basic Equation 1. The algorithm selects the lines containing the largest number of points. It can select up to 10 lines.

The algorithm utilizes the user defined values for <math>rho</math> and <math>theta</math> such as:

<math> - \sqrt{((xDim -1 )^2 + (yDim - 1)^2)} \le \rho \ge \sqrt{((xDim - 1) ^2 - </math>

Applying Hough transform to images

Running the Hough Transform for Line Filing algorithm

Running the Hough Transform for Line Filling algorithm

To run the algorithm, do the following:

1. Run MIPAV.
2. Open an image of interest. Make sure that the image has a binary type. You might consider processing the image, first, and then running the Hough Transform on the processed image. Processing may include applying Gradient Magnitude (GM), and then thresholding the GM result image to convert it to the binary image.
3. Navigate to Algorithms > Hough Transform > Line Filling.
4. In the Hough Transform for Line Filling dialog box that appears, enter the user defined values into X dimension and Y dimension text boxes. See Figure (a).
5. Press OK. The algorithm begins to run and the progress bar appears with the status. When the algorithm finishes running, the Hough Transform image and the Hough Transform Line Selection dialog box appear, see Figure (b).
6. In the Hough Transform Line Selection dialog box, use the check boxes to select lines and also specify the minimum gap distance.
7. Press OK
8. The result image appears displaying isolated lines. See Figure (c).

Running the Hough Transform for Circle Detection algorithm

Running the Hough Transform for Circle Detection algorithm. Note that only two of three isolated circles are shown in the result image, because only two were checked in the Hough Transform Circle Selection dialog box

To run the algorithm, do the following:

1. Run MIPAV.
2. Open an image of interest. Make sure that the image has a binary type. You might consider processing the image, first, and then running the Hough Transform on the processed image. Processing may include applying Gradient Magnitude (GM), and then thresholding the GM result image to convert it to the binary image.
3. Navigate to Algorithms > Hough Transform >Circle Detection. The Hough Transform Circle Detection dialog box appears.
4. In the Hough Transform Circle Detection dialog box, enter the values for x0, y0, rad and number of circles.
5. Press OK. The algorithm begins to run and the progress bar appears with the status. When the algorithm finishes running, the Hough Transform Circle Selection dialog box appears displaying the number of circles found.
6. The result image with circles appears. See the Figure on right.

Running the Hough Transform for Ellipse Detection algorithm

Running the Hough Transform for Ellipse Detection algorithm. Note that isolated ellipses checked for display appear in red

To run the algorithm, do the following

1. Run MIPAV.
2. Open an image of interest. Make sure that the image has a binary type. You might consider processing the image, first, and then running the Hough Transform on the processed image. Processing may include applying Gradient Magnitude (GM), and then thresholding the GM result image to convert it to the binary image.
3. Navigate to Algorithms > Hough Transform > Ellipse Detection. The Hough Transform Ellipse Detection dialog box appears.
4. Complete the Hough Transform Ellipse Detection dialog box. For the first run of the algorithm enter the number of ellipses, but use the default values for the other entries. Later, you can adjust the values based on the result you received.
5. Press OK. The algorithm begins to run and the progress bar appears with the status. When the algorithm finishes running, the Hough Transform Ellipse Selection dialog box appears displaying the number of ellipses found. Also, the ellipse statistics appears in the Output tab. See the Figure on right.
6. In the Hough Transform Ellipse Selection dialog box, use check boxes to specify which ellipses you would like to isolate in the image. Press OK.
7. The result image appears displaying isolated ellipses in red. See the Figure on right.

Hough Transform for Ellipse Detection dialog box

Minimum percentage of ellipse perimeter with points - minimum percentage of the perimeter of a found ellipse that must be covered by points for it to be valid. The default value is 30.0.

Maximum curve points on each side for tangent - the maximum number of points to take from each side of a point on a curve in determining a tangent. If only one point is available on each side, the algorithm uses average of slopes to each of the neighboring points. By default, it is set to 3.

Desired maximum pixel difference for p, q, r1, or r2 value - the desired maximum pixel difference allowed for p, q, r1, and r2 values within a single bin. If sufficient memory is not available, the actual maximum pixel difference will be greater than the desired pixel difference. By default, it is set to 2.0.

Desired maximum degrees difference for theta value - the maximum degrees difference allowed for theta for five values to be placed into an existing bin. By default, it is set to 3.0. Minimum distance between 2 of 3 picked points - the smallest allowable distance between 2 of 3 picked points. By default, it is set to 3.0.

Maximum distance between 2 of 3 picked points - the largest allowable distance between 2 of 3 triplet points. The maximum distance would be the major axis distance of the largest possible ellipse. By default, it is set to 100.0.

Point triplets required for ellipse find - a number of point triplets acquired before each ellipse find is performed. By default, it is set to 1000.

Counts in a p, q, r1, r2 bin required for an ellipse find - the minimum number of counts that must be present in at least one bin for an ellipse find to occur. By default, it is set to 2.

Maximum percent deviation for perimeter pixels - the max percent, by which perimeter pixels can deviate from the ellipse equation. By default, it is set to 15.

Number of ellipses - a number of ellipses to be found.

Maximum number of ellipse find circles - the maximum number of times that the required number of point triplets will be acquired to find an ellipse. If 1,000 point triplets are required and the maximum number of ellipse find cycles is 80, then 1,000 point triplets can be acquired no more than 80 times. After 1,000 point triplets have been acquired, no ellipses may be detected either because no p, q, r1, r2, theta bin has the required minimum number of counts or because the minimum percentage of the perimeter is not covered. If failures occur because no bin has the required minimum number of counts, the maximum pixel difference and/or maximum degree difference could be increased to create fewer bins with smaller resolution but larger counts.

Maximum Hough transform in megabytes- the maximum allowed size in memory used for Hough transform. As the memory size grows, the pixel and degree width for each bin can decrease. By default, it is set to 256 MB.

Running the Hough Transform for Parabola Detection algorithm

Running the Hough Transform for Parabola Detection algorithm. Note that the detected parabola appears in red

To run the algorithm, do the following:

1. Run MIPAV.
2. Open an image of interest. Make sure that the image has a binary type. You might consider processing the image, first, and then running the Hough Transform on the processed image. Processing may include applying Gradient Magnitude (GM), and then thresholding the GM result image to convert it to the binary image.
3. Navigate to Algorithms > Hough Transform > Parabola Detection. The Hough Transform for Parabola Detection dialog box appears.
4. Complete the dialog box and press OK. For the first run of the algorithm enter the number of parabolas, but use the default values for the other entries. Later, you can adjust the parameters depending on the results you get.
5. The algorithm begins to run and the progress bar appears with the status. When the algorithm finishes running, the Hough Transform Parabola Selection dialog box appears displaying the number of parabolas found.
6. In the Hough Transform Parabola Selection dialog box, use check boxes to specify which parabolas you would like to isolate in the image, see Figure 38. Press OK.
7. The result image appears displaying isolated parabolas.

Hough Transform for Parabola Detection dialog box

The Hough Transform for Parabola Detection dialog box is shown in the Figure on your right.

Desired xv dimension of Hough Transform image is a user defined value of dimension for xv bins in the Hough transform space. By default, it equals 512.

Desired yv dimension of Hough Transform image is a user defined value of dimension for yv bins in the Hough transform space. By default, it equals 512.

Desired phi dimension of Hough Transform image is a user defined value of dimension for phi bins in the Hough transform space. By default, it equals 360.

Phi value in degrees if phi dimension =1 - this is the phi value in radians if the desired phi dimension value equals to 1. By default, it is set to 90.

Desired p dimension of Hough Transform image - the number of dimension p bins in the Hough transform space. By default, it is set to 256.

Maximum curve points on each side for tangent - the maximum number of points to take from each side of a point on a curve in order to determine a tangent. By default, it is set to 3.

Minimum p value - the minimum value for p, by default, it is set to 0.1.

Maximum p value -the maximum value for p, by default, it is set to 256.

Maximum Hough Transform in megabytes - the maximum allowed size in memory used for Hough transform. As the memory size grows, the pixel and degree width for each bin can decrease. By default, it is set to 256 MB.

Number of parabolas - a number of parabolas to be detected. By default, the value is set to 1.

References

HOUGH TRANSFORMS, by David Young, January 1993, revised January 1994 - [2]