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 & L2, t23 = Intersection Point of L2 & L3, m12 = midpoint of P1P2, m23 = midpoint of P2P3, J1 = line thru t12 & m12, J2 = line thru t23 & m23 Then the Intersection Point of J1 & 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 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.