gov.nih.mipav.model.algorithms
Class AlgorithmHoughEllipse
java.lang.Object
java.lang.Thread
gov.nih.mipav.model.algorithms.AlgorithmBase
gov.nih.mipav.model.algorithms.AlgorithmHoughEllipse
- All Implemented Interfaces:
- ActionListener, WindowListener, Runnable, EventListener
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.
Fields inherited from class gov.nih.mipav.model.algorithms.AlgorithmBase |
destFlag, destImage, image25D, mask, maxProgressValue, minProgressValue, multiThreadingEnabled, nthreads, progress, progressModulus, progressStep, runningInSeparateThread, srcImage, threadStopped |
Constructor Summary |
AlgorithmHoughEllipse()
AlgorithmHoughEllipse - default constructor. |
AlgorithmHoughEllipse(ModelImage destImg,
ModelImage srcImg,
double minCoverage,
int sidePointsForTangent,
double maxPixelBinWidth,
double maxDegreesBinWidth,
double minPointDistance,
double maxPointDistance,
int pointSetsRequired,
int countThreshold,
double ellipseRangeTolerance,
int numEllipses,
int maxEllipseFindCycles,
int maxBufferSize)
AlgorithmHoughEllipse. |
Methods inherited from class gov.nih.mipav.model.algorithms.AlgorithmBase |
actionPerformed, addListener, addProgressChangeListener, calculatePrincipleAxis, computeElapsedTime, convertIntoFloat, delinkProgressToAlgorithm, displayError, errorCleanUp, fireProgressStateChanged, fireProgressStateChanged, fireProgressStateChanged, fireProgressStateChanged, fireProgressStateChanged, generateProgressValues, getDestImage, getElapsedTime, getMask, getMaxProgressValue, getMinProgressValue, getNumberOfThreads, getProgress, getProgressChangeListener, getProgressChangeListeners, getProgressModulus, getProgressStep, getProgressValues, isCompleted, isImage25D, isMultiThreadingEnabled, isRunningInSeparateThread, isThreadStopped, linkProgressToAlgorithm, makeProgress, notifyListeners, removeListener, removeProgressChangeListener, run, setCompleted, setImage25D, setMask, setMaxProgressValue, setMinProgressValue, setMultiThreadingEnabled, setNumberOfThreads, setProgress, setProgressModulus, setProgressStep, setProgressValues, setProgressValues, setRunningInSeparateThread, setStartTime, setThreadStopped, startMethod, windowActivated, windowClosed, windowClosing, windowDeactivated, windowDeiconified, windowIconified, windowOpened |
Methods inherited from class java.lang.Thread |
activeCount, checkAccess, countStackFrames, currentThread, destroy, dumpStack, enumerate, getAllStackTraces, getContextClassLoader, getDefaultUncaughtExceptionHandler, getId, getName, getPriority, getStackTrace, getState, getThreadGroup, getUncaughtExceptionHandler, holdsLock, interrupt, interrupted, isAlive, isDaemon, isInterrupted, join, join, join, resume, setContextClassLoader, setDaemon, setDefaultUncaughtExceptionHandler, setName, setPriority, setUncaughtExceptionHandler, sleep, sleep, start, stop, stop, suspend, toString, yield |
AlgorithmHoughEllipse
public AlgorithmHoughEllipse()
- AlgorithmHoughEllipse - default constructor.
AlgorithmHoughEllipse
public AlgorithmHoughEllipse(ModelImage destImg,
ModelImage srcImg,
double minCoverage,
int sidePointsForTangent,
double maxPixelBinWidth,
double maxDegreesBinWidth,
double minPointDistance,
double maxPointDistance,
int pointSetsRequired,
int countThreshold,
double ellipseRangeTolerance,
int numEllipses,
int maxEllipseFindCycles,
int maxBufferSize)
- AlgorithmHoughEllipse.
- Parameters:
destImg
- Image with ellipses filled insrcImg
- Binary source image that has ellipses and near ellipse shapes with gapsminCoverage
- Minimum percentage of the perimiter of a found ellipse that must be covered by points
for it to be valid.sidePointsForTangent
- Maximum number of points to take from each side of a point on a curve
in determining the tangentmaxPixelBinWidth
- Maximum pixel difference allowed for xCenter, yCenter, r1, and r2 for 5 values
to be placed into an existing binmaxDegreesBinWidth
- Maximum degrees difference allowed for theta for 5 values to be placed into
an existing binminPointDistance
- Smallest allowable distance between 2 of 3 picked pointsmaxPointDistance
- Largest allowable distance between 2 of 3 picked pointspointSetsRequired
- Number of point triplets acquired before each ellipse find is performedcountThreshold
- Number of counts required to find an ellipseellipseRangeTolerance
- Maximum percent by which perimiter pixels can deviate from the
ellipse equationnumEllipses
- number of ellipses to be foundmaxEllipseFindCycles
- Maximum number of pointSetsRequired triplet point acqusitions that
is allowed to occurmaxBufferSize
- maximum Hough transform size in megabytes
finalize
public void finalize()
- finalize -
- Overrides:
finalize
in class AlgorithmBase
runAlgorithm
public void runAlgorithm()
- Starts the program.
- Specified by:
runAlgorithm
in class AlgorithmBase