Package gov.nih.mipav.model.algorithms

Class AlgorithmHoughCardioid

java.lang.Object

java.lang.Thread

gov.nih.mipav.model.algorithms.AlgorithmBase

gov.nih.mipav.model.algorithms.AlgorithmHoughCardioid

All Implemented Interfaces:

ActionListener, WindowListener, Runnable, EventListener

public class AlgorithmHoughCardioid
extends AlgorithmBase

This Hough transform uses (xi, yi) points in the original image space to generate theta0, a0 points in the Hough transform. xc and yc of the cusp are obtained from finding the point of maximum curvature. Hough space is used to check the (xcdim * ycdim) possibilities of xc-xchalf to xc + xchalf, yc - ychalf to yc + ychalf, where xchalf = (xcdim - 1)/2 and ychalf = (ycdim - 1)/2. 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 user is asked for the number of theta0 bins, a0 bins, side points for curvature, and number of cardioids. The default size for theta0Num is 720 and the default size for a0Num is min(512, 2*max(image.getExtents()[0], image.getExtents()[1]). The default number of cardioids is 1. The program generates a Hough transform of the source image using the basic equations: theta = atan2(y - yc, x - xc) where xc and yc are the cusp points. Calculate d2 = sqrt((x - d1)**2 + (y - d2)**2)/(1 - cos(theta + theta0)) if theta != -theta0 In general: sqrt((x - xc)**2 + (y - yc)**2) = a*(1 - cos(theta + theta0)) ((x-xc)**2 + (y-yc)**2 - a*((x-xc)*cos*(theta0) - (y-yc)*sin(theta0)) = a*sqrt((x-xc)**2 + (y-yc)**2) dy/dx = (-2*(x-xc) + a*cos(theta0) + a*(x-xc)/sqrt((x-xc)**2 + (y-yc)**2))/ (2*(y-yc) - a*sin(theta0) - a*(y-yc)/sqrt((x-xc)**2 + (y-yc)**2)) x = xc + a*cos(theta)*(1 - cos(theta + theta0)) = xc + a*(-0.5*cos(theta0) + cos(theta) - 0.5*cos(2*theta + theta0)) y = yc + a*sin(theta)*(1 - cos(theta + theta0)) = yc + a*(0.5*sin(theta0) + sin(theta) -0.5*sin(2*theta + theta0)) dy/dx = dy/dtheta/dx/dtheta = (-cos(2*theta + theta0) + cos(theta))/(sin(2*theta + theta0) - sin(theta)) = tan((1/2)*(3*theta + theta0)) Every slope value occurs 3 times so we must use the second derivative to find which of the 3 theta values is correct. dy'/dtheta = -a*sin(theta) + 2a*sin(2*theta + theta0) d2y/dx2 = dy'/dtheta/dx/dtheta = (-sin(theta) + 2*sin(2*theta + theta0))/(-sin(theta) + sin(2*theta + theta0)) curvature(theta) = ((dx/dtheta)*(d2y/dtheta2) - (dy/dtheta)*(d2x/dtheta2))/((dx/dtheta)**2 + (dy/dtheta)**2)**1.5 d2x/dtheta2 = -a*cos(theta) + 2*a*cos(2*theta + theta0) d2y/dtheta2 = -a*sin(theta) + 2*a*sin(2*theta + theta0) curvature(theta) = 3/(2*sqrt(2)*a*sqrt(1 - cos(theta+theta0)) so the curvature is infinite at theta = -theta0. All cusp chords are of length 2 * a. The tangents to the endpoints of a cusp chord are perpindicular. If 3 points have parallel tangents, the lines from the cusp to these 3 points make equal angles of 2*PI/3 at the cusp. For cusp on the left: sqrt((x - xc)**2 + (y - yc)**2) = a*(1 + cos(theta)). x = xc + (a/2)*(1 + 2*cos(theta) + cos(2*theta))) = xc + a*cos(theta)*(1 + cos(theta)) y = yc + (a/2)*(2*sin(theta) + sin(2*theta)) = yc + a*sin(theta)*(1 + cos(theta)) For cusp on the right: sqrt((x - xc)**2 + (y - yc)**2) = a*(1 - cos(theta)). x = xc + (a/2)*(-1 + 2*cos(theta) - cos(2*theta))) = xc + a*cos(theta)*(1 - cos(theta)) y = yc + (a/2)*(2*sin(theta) - sin(2*theta)) = yc + a*sin(theta)*(1 - cos(theta)) For cusp on top: sqrt((x - xc)**2 + (y - yc)**2) = a*(1 + sin(theta)). x = xc + (a/2)*(2*cos(theta) + sin(2*theta))) = xc + a*cos(theta)*(1 + sin(theta)) y = yc + (a/2)*(1 + 2*sin(theta) - cos(2*theta)) = yc + a*sin(theta)*(1 + sin(theta)) For cusp on bottom: sqrt((x - xc)**2 + (y - yc)**2) = a*(1 - sin(theta)). x = xc + (a/2)*(2*cos(theta) - sin(2*theta))) = xc + a*cos(theta)*(1 - sin(theta)) y = yc + (a/2)*(-1 + 2*sin(theta) + cos(2*theta)) = yc + a*sin(theta)*(1 - sin(theta)) The program finds the cardioids containing the largest number of points. The program produces a dialog which allows the user to select which cardioids should be drawn. The Hough transform for the entire image is generated a separate time to find each cardioid. Calculate theta = atan2(y - yc, x - xc). Calculate d3 = sqrt((x - xc)**2 + (y - yc)**2)/(1 - cos(theta + theta0)) if theta != -theta0 Don't calculate d2 if theta = -theta0. d2 goes from 0 to maxA = sqrt((xDim-1)**2 + (yDim-1)**2)/2.0. s2 is the dimension 2 scaling factor. s2 * (a0 - 1) = maxA. s2 = maxA/(a0 - 1) m = d2*(a0 - 1)/maxA. Only calculate the Hough transform for d2 invalid input: '<'= maxA. Find the peak point in the theta0, a0 Hough transform space. Put the values for this peak point in xcArray[c], ycArray[c], a0Array[c], and countArray[c]. If more cardioids are to be found, then zero the houghBuffer and run through the same Hough transform a second time, but on this second run instead of incrementing the Hough buffer, zero the values in the source buffer that contributed to the peak point in the Hough buffer. So on the next run of the Hough transform the source points that contributed to the Hough peak value just detected will not be present. Create a dialog with numCardioidsFound xcArray[i], ycArray[i], a0Array[i], and countArray[i] values, where the user will select a check box to have that cardioid drawn. References: 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. 2.) Shape Detection in Computer Vision Using the Hough Transform by V. F. Leavers, Springer-Verlag, 1992.

Nested Class Summary

Nested classes/interfaces inherited from class java.lang.Thread

Thread.Builder, Thread.State, Thread.UncaughtExceptionHandler

Field Summary

Fields

Modifier and Type	Field	Description
private int	a0Num
private int	numCardioids
private int	sidePointsForCurvature
private ModelImage	testImage
private int	theta0Num

Fields inherited from class gov.nih.mipav.model.algorithms.AlgorithmBase

destFlag, destImage, image25D, mask, maxProgressValue, minProgressValue, multiThreadingEnabled, nthreads, progress, progressModulus, progressStep, runningInSeparateThread, separable, srcImage, threadStopped

Fields inherited from class java.lang.Thread

MAX_PRIORITY, MIN_PRIORITY, NORM_PRIORITY

Constructor Summary

Constructors

Constructor	Description
AlgorithmHoughCardioid()	AlgorithmHoughCardioid - default constructor.
AlgorithmHoughCardioid(ModelImage destImg, ModelImage srcImg, int theta0Num, int a0Num, int numCardioids, int sidePointsForCurvature)	AlgorithmHoughCardioid.

Method Summary

Modifier and Type	Method	Description
void	finalize()	finalize -
void	runAlgorithm()	Starts the program.

Methods inherited from class gov.nih.mipav.model.algorithms.AlgorithmBase

actionPerformed, addListener, addProgressChangeListener, calculateImageSize, calculatePrincipleAxis, computeElapsedTime, computeElapsedTime, convertIntoFloat, delinkProgressToAlgorithm, delinkProgressToAlgorithmMulti, displayError, errorCleanUp, fireProgressStateChanged, fireProgressStateChanged, fireProgressStateChanged, fireProgressStateChanged, fireProgressStateChanged, generateProgressValues, getDestImage, getElapsedTime, getMask, getMaxProgressValue, getMinProgressValue, getNumberOfThreads, getProgress, getProgressChangeListener, getProgressChangeListeners, getProgressModulus, getProgressStep, getProgressValues, getSrcImage, isCompleted, isImage25D, isMultiThreadingEnabled, isRunningInSeparateThread, isThreadStopped, linkProgressToAlgorithm, linkProgressToAlgorithm, makeProgress, notifyListeners, removeListener, removeProgressChangeListener, run, setCompleted, setImage25D, setMask, setMaxProgressValue, setMinProgressValue, setMultiThreadingEnabled, setNumberOfThreads, setProgress, setProgressModulus, setProgressStep, setProgressValues, setProgressValues, setRunningInSeparateThread, setSrcImage, setStartTime, setThreadStopped, startMethod, windowActivated, windowClosed, windowClosing, windowDeactivated, windowDeiconified, windowIconified, windowOpened

Methods inherited from class java.lang.Thread

activeCount, checkAccess, clone, countStackFrames, currentThread, dumpStack, enumerate, getAllStackTraces, getContextClassLoader, getDefaultUncaughtExceptionHandler, getId, getName, getPriority, getStackTrace, getState, getThreadGroup, getUncaughtExceptionHandler, holdsLock, interrupt, interrupted, isAlive, isDaemon, isInterrupted, isVirtual, join, join, join, join, ofPlatform, ofVirtual, onSpinWait, resume, setContextClassLoader, setDaemon, setDefaultUncaughtExceptionHandler, setName, setPriority, setUncaughtExceptionHandler, sleep, sleep, sleep, start, startVirtualThread, stop, suspend, threadId, toString, yield

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, wait, wait, wait

Field Details

theta0Num

private int theta0Num

a0Num

private int a0Num

numCardioids

private int numCardioids

testImage

private ModelImage testImage

sidePointsForCurvature

private int sidePointsForCurvature

Constructor Details

AlgorithmHoughCardioid

public AlgorithmHoughCardioid()

AlgorithmHoughCardioid - default constructor.

AlgorithmHoughCardioid

public AlgorithmHoughCardioid(ModelImage destImg,
 ModelImage srcImg,
 int theta0Num,
 int a0Num,
 int numCardioids,
 int sidePointsForCurvature)

AlgorithmHoughCardioid.

Parameters:

destImg - Image with lines filled in

srcImg - Binary source image that has lines with gaps

theta0Num - number of dimension 1 bins in Hough transform space

a0Num - number of dimension 2 bins in Hough transform space

numCardioids - number of cardioids to be found

sidePointsForCurvature - Maximum number of points to take from each side of a point on a curve in determining the tangent

Method Details

finalize

public void finalize()

finalize -

Overrides:

finalize in class AlgorithmBase

runAlgorithm

public void runAlgorithm()

Starts the program.

Specified by:

runAlgorithm in class AlgorithmBase