Package gov.nih.mipav.model.algorithms

Class AlgorithmHoughParabola

  • All Implemented Interfaces:
    java.awt.event.ActionListener, java.awt.event.WindowListener, java.lang.Runnable, java.util.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.

    • Field Detail

      • 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

    • Constructor Detail

      • 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