Difference between revisions of "Hough Transform"

From MIPAV
Jump to: navigation, search
m (See also)
 
Line 335: Line 335:
  
 
HOUGH TRANSFORMS, by David Young, January 1993, revised January 1994 - [http://www.sussex.ac.uk/Users/davidy/teachvision/vision4.html]
 
HOUGH TRANSFORMS, by David Young, January 1993, revised January 1994 - [http://www.sussex.ac.uk/Users/davidy/teachvision/vision4.html]
 
HTML MIPAV help - [http://mipav.cit.nih.gov/documentation/HTML%20Algorithms/HoughTransform.html|HoughTransform.html]
 
  
 
Digital Image Processing, Second Edition by Richard C. Gonzalez and Richard E. Woods, Section 10.2.2 Global Processing via the Hough Transform, Prentice-Hall, Inc., 2002, pp. 587-591.  
 
Digital Image Processing, Second Edition by Richard C. Gonzalez and Richard E. Woods, Section 10.2.2 Global Processing via the Hough Transform, Prentice-Hall, Inc., 2002, pp. 587-591.  

Latest revision as of 15:18, 25 April 2013

Image types

The Hough transform module in MIPAV only works with binary images. Before running the algorithm, the user should apply Gradient Magnitude to the original image, and then threshold the result image to obtain a binary image. Noise removal and thinning should also be performed, if necessary, before this program is run.

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 \le \sqrt{((xDim - 1) ^2 - (yDim - 1)^2},

where

- \pi/2 \le \theta \le + \pi/2

</math>

Where,

<math>\rho </math> has <math>n_1</math> cells and <math>\theta</math> has <math>n_2</math> cells;

d is the maximum distance in the 2D image from the point at (0, 0) to (xDim - 1, yDim - 1) or from (xDim - 1, 0) to (0, yDim - 1); and

<math> d=\sqrt{((xDim-1)^2 + (yDim-1)^2)} </math>

  • For each (xi, yi) point in the original image, where xi not equal to zero and yi not equal to zero, the algorithm calculates n2 values of theta using the following approach:

<math> for k \in [0; n_2-1], \theta(k) = -\pi/2 + k*\pi/2

and

\rho = x* cos(\theta) + y *\sin(\theta) </math>

  • Then, it finds which of n1 bins rho belongs to by calculating the following parameter j, where <math>j = (\rho + d)*n_1/(2*d)</math>, with j going from 0 to <math>n_1-1</math>;
  • If <math>j = n_1</math>, the algorithm sets it equal to <math>n_1-1</math>;
  • For each point in the Hough transform, the algorithm creates a list of the x and y values that were used to generate it;
  • Then, it generates the Hough transform image;
  • It finds which <math>(rho, theta)</math> points are the peak points in the rho, theta plane. Note that only peaks in the rho, theta plane are considered so that the algorithm does not make selections from the spread around the peak;
  • Finally, it forms rho, theta, and count arrays for these lines and creates an image with lines detected.

If the Fill in the gaps option is selected, the algorithm allows the user to select which lines should be filled in and specify for selected lines the maximum length of the gaps to be filled.

By setting the maximum distance equal to 0.0, the user can have this module function solely for line detection and not perform any line filling.

Detecting circles

The same procedure is used to detect other shapes or curves with analytical descriptions. For instance, in order to recognize circles, the following parametric equation is used <math> (x-a)^2 + (y-b)^2 = r^2 </math>

Where, a and b are the coordinates of the center of the circle and r is the radius.

In this case, the computational complexity of the algorithm increases as now we have three coordinates in the parameter space, and therefore, a 3-D accumulator should be used.

Outline of the Hough circle detection algorithm

The algorithm generates a Hough transform of the source image using the basic equation:

<math> (x - x_0)^2 + (y - y_0)^2 = rad^2 </math>

This MIPAV algorithm finds the circles containing the largest number of points. The algorithm takes as an input the following user defined parameters:

  • number of circles to be isolated,
  • number of x_0 and y_0 bins,
  • number of rad bins.

For each (x_i, y_i) point in the original image, where xi and yi not both zero, the algorithm calculates the following:

  • the first dimension value <math>d_1 = j * (xDim - 1)/(x_0 - 1), with j = 0 to x_0 - 1</math>;
  • the second dimension value <math>d_2 = k * (yDim - 1)/(y_0 - 1), with k = 0 to y_0 - 1; </math>
  • the third dimension value d_3, where

<math> d_3=\sqrt{((xDim-1)^2 + (yDim-1)^2)}, where d_3 \in [0, maxRad] </math>

and

<math> maxRad = max \frac{(xDim-1; yDim-1)}{2} </math>

For d_3 less or equal to maxRad, the algorithm multiplies d_3 by (number of dimension 3 bins - 1)/maxRad to obtain the third dimension bin number s_3.

<math> s_3*(rad-1)=maxRad, s_3=\frac{maxRad}{(rad-1)*m}=d_3*\frac{rad-1}{maxRad} </math>

The algorithm finds the peak point in the x0, y0, rad Hough transform space. Then, it stores the values for this peak point into a Hough buffer and also in an array (x_0Array[c], y_0Array[c], radArray[c], and countArray[c]).

The algorithm must be run once for each circle found. Before each run the source buffer values that contributed to the previous Hough buffer peak are deleted.

Default values

The default size for x_0 is a minimum of 512 and the image x dimension. The default size for y_0 is a minimum of 512 and the image y dimension. The default size for rad is the minimum of 512 and the largest dimension size. The default number of circles is one.

Isolating ellipses using the Hough transform

Calculating a center of an ellipse: x1, x2, x3 - three ellipse points; (t, x1), (t, x2) and (t, x3) the tangents of the points x1, x2 and x3 correspondingly; m is the midpoint of (x1, x2), m1 is the midpoint of (x2, x3); o is the center of the ellipse found as the intersection of (t, m) and (t1, m1)

Ellipse equation

An ellipse can be defined using the following equation:

<math>

a(x-p)^2 + 2b(x-p)(y-q) + c(y-q)^2 = 1,

where, ac-b^2>0.

</math>

Isolating ellipses

This equation is non-linear with respect to five parameters a, b, c, p, and q. Therefore, finding the unique ellipse that passes through five given pixels requires solving the system of five non-linear equations, which is impractical. However, this can be reduced to a linear problem using the approach that employs the features of the geometry of ellipses. Refer to [4] in "References" .

For a given ellipse, the center of the ellipse lays on the line (t, m), where

  • t is the intersection of the tangents of any two ellipse points x_1 and x_2,
  • m is the midpoint m of (x_1, x_2), see the Figure on right.

Now, for the same ellipse, the algorithm takes another point x_3. It plots the tangents of the points x_3 and x_2. The intersection of the tangents of the points x_3 and x_2 will be another point t_1. It also plots the midpoint m1 of (x_2, x_3). The intersection of two lines (t, m) and (t_1, m_1) is the ellipse center. See Figure 34 for detail.

The next step is to estimate three remaining ellipse parameters. In order to do that, the algorithm, first, translates the ellipse so its center is at the origin. This reduces Hough Transform#Ellipse equation to the following:

<math> ax^2 +2*bxy + cy^2 = 1 </math>

Then, it translates the center of the ellipse to the origin by subtracting the ellipse center (p, q) from point 1, point 2, and point 3. This produces the system of three simultaneous linear equations:

<math> \begin{bmatrix} (x_1^2)& (2 * x_1*y_1) & (y_1^2) & a & 1\\ (x_2^2)& (2 * x_2*y_2) & (y_2^2) & b & 1\\ (x_3^2)& (2 * x_3*y_3) & (y_3^2) & c & 1\\ \end{bmatrix} </math>


It solves Hough Transform#Ellipse equation for a, b, and c, which gives the remaining three ellipse parameters.

Next, the algorithm checks the validity of ac-b2>0. This is true if a combination of parameters a, b, and c represents a valid ellipse. If it is false, that means that either x1, x2, and x3 do not belong to the same ellipse, or the estimates of tangents were wrong. In both cases, the algorithm discards the parameters and chooses a new pixel triplet.

Finally, the algorithm converts parameters a, b, c, p, and q to p, q, r1, r2, and theta, where r1 and r2 are the major and minor radii of the ellipse and theta is the angle of the major axis.

If an ellipse has been found, but the algorithm still has not found all the user specified ellipses, then it deletes the points found along its perimeter from the buffers before running the Hough transform again.

Algorithm notes

The code for finding the best tangent for a point on a curve uses a port of findOptimalTangent.m from the Randomized Hough Transform used for ellipse detection MATLAB code by Andrew Schuler. The rest of the code is not ported, but is derived from the write-ups by Andrew Schuler and Robert A. McLaughlin. Robert A. Mclaughlin uses a linked list to save memory at the cost of slower speed. Andrew Schuler uses an array to achieve higher speed at the cost of more memory usage. In this application, we use the array for higher speed and incur a higher memory cost.

Hough Parabola

This Hough transform uses (xi, yi) points in the original image space to generate (xv, yv, phi, p) points in the Hough transform in order to isolate parabolas. The algorithm uses the following representation of parabola:

<math> [(y-vy)*cos(\phi)-(x-vx)*sin(\phi)]2 = 4*p*[(y-vy)*sin(\phi)+(x-vx)*cos(\phi)] </math>

Where, vx, vy are the coordinates of the parabola vertex and p is the distance between the vertex and focus of the parabola. The upper left corner of image is the origin of coordinate system.

The user is asked for the number of xv bins, yv bins, phi bins, phi constant value, p bins, pMin value, pMax value, maxBufferSize, and number of parabolas.

The algorithm finds the parabolas containing the largest number of points. If the number of parabolas to be found is more that one, the Hough transform for the entire image is generated a separate time to find each parabola.

Default and desired values

The default size for xv is a minimum of 512 and the image x dimension. The default size for yv is a minimum of 512 and the image y dimension. The default size for phi is 360. The default value for pBins is the minimum of 512 and the largest dimension size. The desired value for pMax is the maximum of 512 and the largest dimension size, where the default value for pMin is 0.1. The default number of parabolas is one.

Outline of the algorithm:

  • For each (xi, yi) point in the original image, where xi and yi both not zero, the algorithm calculates the first dimension value xvArray[j] = j * (xDim - 1)/(xvBins - 1), with j = 0 to xvBins - 1.
  • It calculates the second dimension value yvArray[k] = k * (yDim - 1)/(yvBins - 1), with k = 0 to yvBins - 1.
  • It calculates the third dimension phiArray[m] = m * 2.0 * PI/phiBins, with m going from 0 to phiBins - 1.
  • It calculates p = [(y - vy)*cos(phi) - (x - vx)*sin(phi)]2/[4*[(y - vy)*sin(phi) + (x - vx)*cos(phi)]], where, p goes from pMin to pMax, because the algorithm calculates the Hough transform only for those p that fit the interval [pMax, pMin].
  • It calculates the following values also:

pMin + s4 * (pBins - 1) = pMax

s4 = (pMax - pMin)/(pBins - 1)

n = (p - pMin)*(pBins - 1)/(pMax - pMin)

Then it finds the peak point in the (vx, vy, phi, p) Hough transform space. The peak point identifies the parabola segment in the original image space.

Note: Ideally, the Hough domain has to be searched for a maximum only once. In situations where a picture contains many patterns of different size and, therefore, many parabolas are to be found, the algorithm takes out, first, those patterns in the original image space that correspond to clearly identifiable peaks in the Hough domain, and then repeats the process until all parabolas be found.


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 - [1]

Digital Image Processing, Second Edition by Richard C. Gonzalez and Richard E. Woods, Section 10.2.2 Global Processing via the Hough Transform, Prentice-Hall, Inc., 2002, pp. 587-591.

Digital Image Processing, Third Edition by Richard C. Gonzalez and Richard E. Woods, Pearson Prentice Hall, 2008, Global processing using the Hough transform, pp. 733-738.

Shape Detection in Computer Vision Using the Hough Transform by V. F. Leavers, Springer-Verlag, 1992.

Technical Report - Randomized Hough Transform: Improved Ellipse Detection with Comparison by Robert A. McLaughlin.

See also