Package gov.nih.mipav.model.algorithms

Class AlgorithmHoughHyperbola

java.lang.Object
java.lang.Thread
gov.nih.mipav.model.algorithms.AlgorithmBase
gov.nih.mipav.model.algorithms.AlgorithmHoughHyperbola
All Implemented Interfaces:
ActionListener, WindowListener, Runnable, EventListener
public class AlgorithmHoughHyperbola extends AlgorithmBase
This work is made possible by the following mathematical theorem proved by Professor Alan Horwitz of Penn State University: Finding the Center of a Hyperbola, H, given three nonparallel tangent lines to H and the corresponding points of tangency. Theorem: Let P1,P2,P3 be any three distinct points on the hyperbola, H; Let L1,L2,L3 be the tangent lines to H at P1,P2,P3, and assume that no two of the Lj are parallel. Let t12 = Intersection Point of L1 invalid input: '&' L2, t23 = Intersection Point of L2 invalid input: '&' L3, m12 = midpoint of P1P2, m23 = midpoint of P2P3, J1 = line thru t12 invalid input: '&' m12, J2 = line thru t23 invalid input: '&' m23 Then the Intersection Point of J1 invalid input: '&' J2 is the center of H This Hough transform uses (xi, yi) points in the original image space to generate p, q, r1, r2, and theta points in the Hough transform. This Hough transform module only works with binary images. Before it is used the user must compute the gradient of an image and threshold it to obtain a binary image. Noise removal and thinning should also be performed, if necessary, before this program is run. 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 Hough ellipse writeups 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 I use the array for higher speed and incur a higher memory cost. If need be, memory can be saved by rewriting this application to used a linked list. Pixel neighbors: 0 1 2 3 4 5 6 7 The algorithm works as follows: 1.) Skeletonization is performed. Branches with 2 or less pixels are pruned off. 2.) When a pixel has a diagonal neighbor adjacent to a horizontal or vertical neighbor, the horizontal or vertical neighbor is deleted. 3.) Remove points with 2 or more neighbors. 4.) Find the 1 or 2 neighbors of every point Find the number of end points, that is, points with only 1 neighbor Delete isolated points with no neighbors 5.) Find the starting positions and lengths of the open curves Delete all open curves with only 2 points 6.) For the open curves find the slope and y axis intercept of the tangent line to the curve at a point With a user specified sidePointsForTangent on each side of a point find the tangent line that minimizes the sum of the squared distances from these side points to the tangent line 7.) Find a position and length of closed curve 8.) For the closed curve find the slope and y axis intercept of the tangent line to the curve at a point With a user specified sidePointsForTangent on each side of a point find the tangent line that minimizes the sum of the squared distances from these side points to the tangent line 9.) Calculate the desired number of bins that would be used for each parameter if memory were not a limitation. This desired bin number = (maximum parameter value - minimum parameter value)/maximum bin width 10.) Shrink the number of each bins used for each parameter by the fifth root of desiredBytes/actualBytesAvailable to keep the buffer size down to user specified actualBytesAvailable. 11.) User a random number generator to select 3 of the points. If 2 of the 3 points are closer than the user specified minimum distance or farther than the user specified maximum distance, then run the random number generator again to find another point within the permissible distance range. If 2 of the points have tangents with the same slope, then run the random number generator again. 12.) Find the intersection of the tangent line for point 1 and the tangent line for point2, t12. Find the point midway between point 1 and point 2, point m12. Find the intersection of the tangent line for point 2 and the tangent line for point3, t23. Find the point midway between point 2 and point 3, point m23. The center is found at the intersection of t12m12 and t23m23. If the center is not inside the bounds of the image, go back and run the random number generator for 3 new points. 13.) Translate the center of the hyperbola to the origin by subtracting xCenter, yCenter from point 1, point 2, and point 3. 14.) Solve for the other 3 hyberbola parameters a, b, and c in a*x**2 + 2*b*x*y + c*y**2 = 1 by solving: [x1**2 2*x1*y1 y1**2] [a] [1] [x2**2 2*x2*y2 y2**2] [b] = [1] [x3**2 2*x3*y3 y3**2] [c] [1] 15.) The inequality a*c - b**2 invalid input: '<' 0 is true if the parameters represent a valid hyperbola. If this inequality is false, it implies that either the 3 pixels do not lie on the same hyperbola, or that the estimates of the tangents were inaccurate. In either case, we discard the parameters and run the random number generator to find a new pixel triplet. 16.) Convert a, b, and c to semi major axis r1, semi minor axis r2, and orientation angle theta. Find the combined index value for these 5 parameters from the 5 individual index values and the bin numbers for the 5 parameters. Add the respective parameters to xCenterArray[index], yCenterArray[index], r1Array[index], r2Array[index], and thetaArray[index]. Increment countArray[index]. 17.) Keep collecting point triplets until the user specified pointSetsRequired have been collected. 18.) Find the maxIndex yielding the largest value of countArray[index]. If countArray[index] > countThreshold, then proceed with step 19. Otherwise zero the Hough buffer and start to collect a new set of pointSetsRequired point triplets. 19.) Divide xCenterArray[maxIndex], yCenterArray[maxIndex], r1Array[maxIndex], r2Array[maxIndex], and thetaArray[maxIndex] by countArray[maxIndex]. For xCenter, yCenter, r1, r2, and theta, find the number of pixels near the perimiter of the hyperbola. For xCenter, yCenter, r1, r2, and theta - 90 degrees, find the number of pixels near the perimiter of the hyperbola. The correct one of these 2 cases has the largest number of pixels near the perimiter of the hyperbola. If the correct case finds more pixels than minPixels, then the hyberbola is considered as valid. If the correct case has fewer than minPixels, then this set of parameters is discarded and we return to step 18. 20.) If an hyperbola has been found, but the algorithm still has not found the user specified numHyperbolas number of hyperbolas, then delete the points found along its perimiter from indexArray, slopeArray, and interceptArray before running the Hough transform again. xCenterArray, yCenterArray, r1Array, r2Array, thetaArray, and countArray are zeroed before the next Hough transform is acquired. 21.) Perform no more than maxHyperbolaFindCycles of pointSetsRequired triplet set acquisitions. When this number of triplet set acquisitions has occurred, stop trying to find new hyperbolas. 22.) Create a dialog with numHyperbolasFound xCenterArray[i], yCenterArray[i], r1Array[i], r2Array[i], thetaArray[i], and countArray[i] values, where the user will select a check box to have that hyperbola drawn. References: 1.) Private communication from Professor Alan Horwitz of Penn State University 2.) The Randomized Hough Transform used for ellipse detection by Andrew Schuler 3.) Technical Report - Randomized Hough Transform: Improved Ellipse Detection with Comparison by Robert A. Mclaughlin 4.) 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. 5.) Shape Detection in Computer Vision Using the Hough Transform by V. F. Leavers, Springer-Verlag, 1992.

  • Field Details

    • minPixels

      private int minPixels

    • sidePointsForTangent

      private int sidePointsForTangent

    • maxPixelBinWidth

      private double maxPixelBinWidth

    • maxDegreesBinWidth

      private double maxDegreesBinWidth

    • minPointDistance

      private double minPointDistance

    • maxPointDistance

      private double maxPointDistance

    • pointSetsRequired

      private int pointSetsRequired

    • numHyperbolas

      private int numHyperbolas

    • maxHyperbolaFindCycles

      private int maxHyperbolaFindCycles

    • maxBufferSize

      private int maxBufferSize

    • countThreshold

      private int countThreshold

    • hyperbolaRangeTolerance

      private double hyperbolaRangeTolerance

    • testImage

      private ModelImage testImage

  • Constructor Details

    • AlgorithmHoughHyperbola

      public AlgorithmHoughHyperbola()
      AlgorithmHoughHyperbola - default constructor.

    • AlgorithmHoughHyperbola

      public AlgorithmHoughHyperbola(ModelImage destImg, ModelImage srcImg, int minPixels, int sidePointsForTangent, double maxPixelBinWidth, double maxDegreesBinWidth, double minPointDistance, double maxPointDistance, int pointSetsRequired, int countThreshold, double hyperbolaRangeTolerance, int numHyperbolas, int maxHyperbolaFindCycles, int maxBufferSize)
      AlgorithmHoughHyperbola.
      Parameters:
      destImg - Image with hyperbolas filled in
      srcImg - Binary source image that has hyperbolas and near hyperbola shapes with gaps
      minPixels - Minimum number of points on a found hyperbola for it to be valid.
      sidePointsForTangent - Maximum number of points to take from each side of a point on a curve in determining the tangent
      maxPixelBinWidth - Maximum pixel difference allowed for xCenter, yCenter, r1, and r2 for 5 values to be placed into an existing bin
      maxDegreesBinWidth - Maximum degrees difference allowed for theta for 5 values to be placed into an existing bin
      minPointDistance - Smallest allowable distance between 2 of 3 picked points
      maxPointDistance - Largest allowable distance between 2 of 3 picked points
      pointSetsRequired - Number of point triplets acquired before each hyperbola find is performed
      countThreshold - Number of counts required to find a hyperbola
      hyperbolaRangeTolerance - Maximum percent by which perimiter pixels can deviate from the hyperbola equation
      numHyperbolas - number of hyperbolas to be found
      maxHyperbolaFindCycles - Maximum number of pointSetsRequired triplet point acquisitions that is allowed to occur
      maxBufferSize - maximum Hough transform size in megabytes

  • Method Details