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.