Package gov.nih.mipav.model.algorithms

Class AlgorithmHoughParabola

java.lang.Object

java.lang.Thread

gov.nih.mipav.model.algorithms.AlgorithmBase

gov.nih.mipav.model.algorithms.AlgorithmHoughParabola

All Implemented Interfaces:

ActionListener, WindowListener, Runnable, EventListener

public class AlgorithmHoughParabola
extends AlgorithmBase

[(y - vy)*cos(phi) - (x - vx)*sin(phi)]**2 = 4*p*[(y - vy)*sin(phi) + (x - vx)*cos(phi)] where vx, vy are the coordinates of the parabola vertex p is the distance between the vertex and focus of the parabola This Hough transform uses (xi, yi) points in the original image space to generate vx, vy, phi, p 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 user is asked for the number of vx bins, vy bins, phi bins, the phi constant value for when phi bins == 1, p bins, pMin value, pMax value, maxBufferSize, and number of parabolas. The desired size for vxBins is min(512, image.getExtents()[0]). The desired size for vyBins is min(512, image.getExtents()[1]). The desired size for phi is 360. The default value for phiConstant is 90 degrees. The default value for pBins is Math.min(512, Math.max(image.getExtents()[0], image.getExtents()[1])). The default value for pMin is 0.1. The default value for pMax is Math.max(image.getExtents()[0], image.getExtents()[1]). The default value for maxBufferSize is 256 megabytes. The default number of parabolas is 1. The program generates a Hough transform of the source image using the basic equation [(y - vy)*cos(phi) - (x - vx)*sin(phi)]**2 = 4*p*[(y - vy)*sin(phi) + (x - vx)*cos(phi)] The program finds the parabolas containing the largest number of points. The program produces a dialog which allows the user to select which parabolas should be drawn. The Hough transform for the entire image is generated a separate time to find each parabola. For each (xi, yi) point in the original image not having a value of zero, calculate the first dimension value vxArray[j] = j * (xDim - 1)/(vxBins - 1), with j = 0 to vxBins - 1. Calculate the second dimension value vyArray[k] = k * (yDim - 1)/(vyBins - 1), with k = 0 to vyBins - 1. calculate the third dimension phiArray[m] = m * 2.0 * PI/phiBins, with m going from 0 to phiBins - 1 Calculate p = [(y - vy)*cos(phi) - (x - vx)*sin(phi)]**2/[4*[(y - vy)*sin(phi) + (x - vx)*cos(phi)]] p goes from pMin to pMax pMin + s4 * (pBins - 1) = pMax. s4 = (pMax - pMin)/(pBins - 1) n = (p - pMin)*(pBins - 1)/(pMax - pMin). Only calculate the Hough transform for pMax >= p >= pMin. Find the peak point in the vx, vy, phi, p Hough transform space. Put the values for this peak point in vxArray[c], vyArray[c], phiArray[c], pArray[c], and countArray[c]. yf = y - vy xf = x - vx [yf*cos(phi)]^2 - 2*yf*sin[phi]*[xf*cos(phi)+ 2*p] + [xf*sin(phi)]^2 -4*p*xf*cos(phi) = 0 ys = (y - vy)*cos(phi) - (x - vx)*sin(phi) xs = (y - vy)*sin(phi) + (x - vx)*cos(phi) ys^2 = 4*p*xs 2*ys*(dys/dxs) = 4p (dys/dxs) = (2p)/ys = (2p)/sqrt(4pxs) = sqrt(p/xs) 2*ys*[(dy/dx)*cos(phi) - sin(phi)] = 4*p*[(dy/dx)*sin(phi) + cos(phi)] (dy/dx) = (ys*sin(phi) + 2*p*cos(phi))/(ys*cos(phi) - 2*p*sin(phi)) Using p = (ys^2)/(4*xs) (dy/dx) = (2*xs*sin(phi) + ys*cos(phi))/(2*xs*cos(phi) - ys*sin(phi)) (dy/dx) = ((x-vx)*cos(phi)*sin(phi) + (y - vy) + (y - vy)*((sin(phi))^2)/((y - vy)*cos(phi)*sin(phi) + (x - vx) + (x - vx)*((cos(phi))^2) Using sin(2*phi) = 2*sin(phi)*cos(phi), ((cos(phi))^2) = (1/2)*(1 + cos(2*phi)), ((sin(phi)^2) = (1/2)*(1 - cos(2*phi)) (dy/dx) = ((x - vx)*sin(2*phi) + 3*(y - vy)- (y - vy)*cos(2*phi))/((y - vy)*sin(2*phi) + 3*(x - vx)+ (x - vx)*cos(2*phi)) Note that 4 possible values of phi, 2 sets of values 180 degrees apart can be found. Without slope you can only calculate p. With slope you can calculate both phi and p. d*cos(2*phi) + e*sin(2*phi) + f = 0 -d*cos(2*phi) = e*sin(2*phi) + f d^2*cos(2*phi)^2 = e^2*sin(2*phi)^2 + 2*e*f*sin(2*phi) + f^2 = 0 d^2 - d^2*sin(2*phi)^2 = e^2*sin(2*phi)^2 + 2*e*f*sin(2*phi) + f^2 = 0 (d^2 + e^2)*sin(2*phi)^2 + 2*e*f*sin(2*phi) + (f^2 - d^2) = 0 sin(2*phi) = (-2*e*f +- sqrt(4*e^2*f^2 - 4*(d^2 + e^2)*(f^2 - d^2)))/(2*(d^2 + e^2)) sin(2*phi) = (-e*f +- d*sqrt(d^2 + e^2 - f^2))/(d^2 + e^2) cos(2*phi) = -(e*sin(2*phi) + f)/d = (-d*f -+ e*sqrt(d^2 + e^2 - f^2))/(d^2 + e^2) Note that + for the sin(2*phi) root corresponds to - for the cos(2*phi) root Real solutions require d^2 + e^2 - f^2 >= 0. Each solution of 2*phi generates 2 solutions of phi, 180 degrees apart. Only use the phi within 90 degrees of arctan(y - vy, x - vx). So only 2 phi are generated. If more parabolas 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 numParabolasFound vxArray[i], vyArray[i], phiArray[i], pArray[i], and countArray[i] values, where the user will select a check box to have that parabola 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.) Form of parabola equation using phi taken from MATLAB routine houghparabola by Clara Isabel Sanchez.

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	maxBufferSize	The maximum Hough transform size in megabytes - default is currently 256
private int	numParabolas
private int	pBins
private int	phiBins
private double	phiConstant
private float	pMax
private float	pMin
private int	sidePointsForTangent
private ModelImage	testImage
private int	vxBins
private int	vyBins

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
AlgorithmHoughParabola()	AlgorithmHoughParabola - default constructor.
AlgorithmHoughParabola(ModelImage destImg, ModelImage srcImg, int vxBins, int vyBins, int phiBins, double phiConstant, int pBins, float pMin, float pMax, int sidePointsForTangent, int maxBufferSize, int numParabolas)	AlgorithmHoughParabola.

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

vxBins

private int vxBins

vyBins

private int vyBins

phiBins

private int phiBins

phiConstant

private double phiConstant

pBins

private int pBins

pMin

private float pMin

pMax

private float pMax

sidePointsForTangent

private int sidePointsForTangent

maxBufferSize

private int maxBufferSize

The maximum Hough transform size in megabytes - default is currently 256

numParabolas

private int numParabolas

testImage

private ModelImage testImage

Constructor Details

AlgorithmHoughParabola

public AlgorithmHoughParabola()

AlgorithmHoughParabola - default constructor.

AlgorithmHoughParabola

public AlgorithmHoughParabola(ModelImage destImg,
 ModelImage srcImg,
 int vxBins,
 int vyBins,
 int phiBins,
 double phiConstant,
 int pBins,
 float pMin,
 float pMax,
 int sidePointsForTangent,
 int maxBufferSize,
 int numParabolas)

AlgorithmHoughParabola.

Parameters:

destImg - Image with lines filled in

srcImg - Binary source image that has lines with gaps

vxBins - number of dimension vx bins in Hough transform space

vyBins - number of dimension vy bins in Hough transform space

phiBins - number of dimension phi bins in Hough transform space

phiConstant - phi value in radians if phiBins == 1

pBins - number of dimension p bins in Hough transform space

pMin - minimum p value

pMax - maximum p value

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

maxBufferSize - maximum Hough transform size in megabytes

numParabolas - number of parabolas to be found

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