public class AlgorithmHoughEllipse
extends AlgorithmBase

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 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 ellipse to the origin by subtracting xCenter, yCenter from point 1, point 2, and point 3. 14.) Solve for the other 3 ellipse 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 > 0 is true if the parameters represent a valid ellipse. If this inequality is false, it implies that either the 3 pixels do not lie on the same ellipse, 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 ellipse. For xCenter, yCenter, r1, r2, and theta - 90 degrees, find the number of pixels near the perimiter of the ellipse. The correct one of these 2 cases has the largest number of pixels near the perimiter of the ellipse. If the correct case finds more pixels than minCoverage percent of the perimiter length, then the ellipse is considered as valid. If the correct case has fewer than minCoverage percent of the ellipse perimiter, then this set of parameters is discarded and we return to step 18. 20.) If an ellipse has been found, but the algorithm still has not found the user specified numEllipses number of ellipses, 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 maxEllipseFindCycles of pointSetsRequired triplet set acquisitions. When this number of triplet set acquisitions has occurred, stop trying to find new ellipses. 22.) Create a dialog with numEllipsesFound 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 ellipse drawn. References: 1.) The Randomized Hough Transform used for ellipse detection by Andrew Schuler 2.) Technical Report - Randomized Hough Transform: Improved Ellipse Detection with Comparison by Robert A. Mclaughlin 3.) 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. 4.) Shape Detection in Computer Vision Using the Hough Transform by V. F. Leavers, Springer-Verlag, 1992.