import ij.IJ;
import ij.ImagePlus;
import ij.WindowManager;
import ij.gui.OvalRoi;
import ij.gui.PolygonRoi;
import ij.gui.Roi;
import ij.measure.Measurements;
import ij.measure.ResultsTable;
import ij.plugin.filter.Analyzer;
import ij.plugin.filter.PlugInFilter;
import ij.process.ImageProcessor;
import ij.process.ImageStatistics;
import java.awt.Point;
import java.awt.Rectangle;
import java.awt.geom.Point2D;
/**
* Plugin for ImageJ.
* Finds and draws a convex hull
* by Thomas R. Roy, University of Alberta, Canada.
* Finds the smallest bounding circle using three points of
* the convex hull for a binary image, as proposed by Xavier Draye, and
* a modification in the case that this algorithm does not work, using
* the largest triangle made from points on the hull.
* The image has to be binary.
* @since date: 2002-2004
* @since updated January 1, 2005
* @since updated to check for binary images May 23, 2005
* @author A. Karperien
* Charles Sturt University, Australia
* @author Thomas R. Roy
* University of Alberta, Canada
* @author Wayne Rasband, NIH
*/
public class Hull_And_Circle implements PlugInFilter, Measurements {
/**variables for circularity*/
float majorcircle=0, minorcircle=0, midx=0, midy=0;
/**Variable for bounding circle's diameter.*/
double diameter=0;
private int width,height; //width and height of window
private int imgHeight, imgWidth; //dimensions of pixelated area
//private float centrex, centrey;
private int left, top, right, bottom;
private int topxc, rightyc, leftyc, bottomxc;
private String filename;
private ImagePlus img;
ImageStatistics stats=null;
int foreground = 0;
int X[] = new int [maxImageWidth * 2];
int Y[] = new int [maxImageWidth * 2];
private static final int maxImageWidth = 5000;
/**
* Returns the array of ints based on the doubles.
*
* @param A array of doubles
* @param length length of array to convert
* @return int array
*/
public static int[] DoubleArrayToIntArray(double[] A, int length) {
int[]N=new int[length];
for (int i = 0; i < length; i++)
N[i]=(int)(A[i]);
return N;
}
/**
* Gets the centre and diameter for
* the circle from the passed three points
* (a,b), (c,d), and (e,f). Solves three equations
* simultaneously using the basic
* equation for a circle.
* (h-x)2+(k-y)2=r2
* Does not check for colinearity.
* @param a x coordinate of first point
* @param b y coordinate of first point
* @param c x coordinate of second point
* @param d y coordinate of second point
* @param e x coordinate of third point
* @param f y coordinate of third point
* @return double [] containing
* the centre coordinates(h, k) and the diameter
* of the circle
*/
public double[] getCircle(double a, double b,
double c, double d, double e, double f) {
b=-b;
d=-d;
f=-f;
double k = ((sq(a)+sq(b))*(e-c)
+ (sq(c)+sq(d))*(a-e) + (sq(e)+sq(f))*(c-a)) /
(2*(b*(e-c)+d*(a-e)+f*(c-a))) ;
double h = ((sq(a)+sq(b))*(f-d) + (sq(c)+sq(d))*(b-f) +
(sq(e)+sq(f))*(d-b)) / (2*(a*(f-d)+c*(b-f)+e*(d-b)));
double r = Math.sqrt(sq(a-h) + sq(b-k));
return new double []{h, -k, 2*r};
} /**
* Returns the bounding circle for the binary image.
*
* Finds three points on the passed convex hull then
* calls the {@link #getCircle getCircle} method
* @param XX int array of x coordinates for the convex hull
* @param YY int array of y coordinates for the convex hull
* @param ip ImageProcessor of binary image that the convex
* hull is for
* @return OvalRoi the bounding circle
*/
public OvalRoi FindBoundingCircle(int[] XX, int[] YY, ImageProcessor ip) {
//find the distance between the first two points
double max = Math.abs(Point2D.distance(
(double)XX[0], (double)YY[0], (double)XX[0], (double)YY[0]));
double oldmax=max;
int max_i = 0;
int max_i2= 0;
double min = 0;
//find the greatest distance between two points on the
//convex hull
for (int anchor=0; anchoroldmax)
{oldmax=max;
max_i=i;max_i2=anchor;}
}}
//draws the line
double x1=XX[max_i];
double y1=YY[max_i];
double x2=XX[max_i2];
double y2=YY[max_i2];
// ip.drawLine((int)x1, (int)y1, (int)x2, (int)y2);
majorcircle=(float)max;
//finds the midpoint
midx = (float)((x1+x2)/2.0);
midy =(float)((y1+y2)/2.0);
// ip.drawDot((int)midx, (int)midy);
//finds the maximum distance from the midpoint of
//that line to another point in the convex hull
max = Math.abs(Point2D.distance((double)XX[0],
(double)YY[0], midx, midy));
oldmax=max;
min=max;
int thirdpoint = max_i;
for (int i = 0; i< XX.length; i++) {
{double dist = Math.abs(Point2D.distance((double)XX[i],
(double)YY[i], midx, midy));
max = Math.max(dist, max);
min = Math.min(dist, min);
if (max>oldmax)
{oldmax=max;
thirdpoint=i;
}
}
}
double thirdx=XX[thirdpoint];
double thirdy=YY[thirdpoint];
boolean isdiameter=false;
if((max_i==thirdpoint)||(thirdpoint==max_i2)) {
isdiameter=true;
}
//decides if the point is on the current line
//draws a line from the midpoint
//of the first line to a next furthest point on the convex hull
//ip.drawLine((int)midx, (int)midy, (int)XX[thirdpoint],
//(int)YY[thirdpoint]);
minorcircle=(float)max;
//Gets the bounding circle from the three points
//just found then draws it
double [] circ = getCircle(XX[max_i], YY[max_i],
XX[max_i2], YY[max_i2], thirdx, thirdy);
int [] Circ =
DoubleArrayToIntArray(circ, circ.length);
//IJ.showMessage("A"+Circ[0]+"A"+Circ[1]+"A"+Circ[2]);
OvalRoi boundingCircle = null;
if (!isdiameter) {
diameter=Circ[2];
boundingCircle=
new OvalRoi(Circ[0]-Circ[2]/2,
Circ[1]-Circ[2]/2,
Circ[2], Circ[2]);
midx=Circ[0]-Circ[2]/2;
midy=Circ[1]-Circ[2]/2;
}
else {
diameter=(float)(2.0*max);
boundingCircle=
new OvalRoi((int)midx-(int)(max), (int)midy-(int)(max),
(int)(2*max), (int)(2*max));
midx = (int)midx-(int)(max);
midy=(int)midy-(int)(max);
}
//ip.drawPolygon(boundingCircle.getPolygon());
return boundingCircle;
}
/**
* ImageJ set up
* @param arg arguments to run plugin = null
* @param imp ImageProcessor on which to work
* @return int an integer
*/
public int setup(String arg, ImagePlus imp) {
if (imp==null)
return(DONE);
else { stats=imp.getStatistics();
IJ.register(this.getClass());
filename=imp.getTitle();
return IJ.setupDialog(imp, DOES_8G);
}
}
/**
* Draws the convex hull for the current ImageProcessor,
* makes some measurements, and draws the bounding circle
* on the image. The bounding circle is currently
* drawn only; to access it, use the BoundingCircle
* roi made in this method.
* @param ip ImageProcessor on which to work
* @see GetDimensions
* @see getPolygon
* @see FindTriangle
*/
public void run(ImageProcessor ip) {
if (true) {
if (stats.histogram[0]>stats.histogram[255])
foreground = 255;
else foreground = 0;
{//ImageStatistics stats = imp.getStatistics();
if (stats.histogram[0]+stats.histogram[255]!=stats.pixelCount) {
IJ.error("8-bit binary image (0 and 255) required.");
return;
}
}
GetDimensions(ip);
PolygonRoi poly = this.getPolygon(ip);
img.setRoi(poly);
int ms = Analyzer.getMeasurements();
ms |= AREA+PERIMETER+CENTER_OF_MASS;//;+ELLIPSE;
Analyzer.setMeasurements(ms);
Analyzer ana = new Analyzer();
stats = img.getStatistics(ms);
Roi roi = img.getRoi();
ana.saveResults(stats, roi);
ResultsTable rt =Analyzer.getResultsTable();
ip.drawPolygon(poly.getPolygon());
OvalRoi BoundingCircle = FindTriangle(X, Y, ip, poly);
ip.drawPolygon(BoundingCircle.getPolygon());
int cr = rt.getCounter();
double area = rt.getValue(ResultsTable.AREA, cr-1);
double perimeter = rt.getValue(ResultsTable.PERIMETER, cr-1);
double circul = (perimeter*perimeter)/area;
rt.addValue("Circularity",
perimeter==0.0?0.0:4.0*Math.PI*(area/(perimeter*perimeter)));
rt.addValue("Roundness", circul);
rt.addLabel("FileName", filename);
// float major = rt.getValue(ResultsTable.MAJOR, cr-1);
// float minor = rt.getValue(ResultsTable.MINOR, cr-1);
// rt.addValue("Axis1", major);
// rt.addValue("Axis2", minor);
img.killRoi();
//Rectangle rect =poly.getBoundingRect();
//// ip.drawPolygon(poly.getPolygon());
//// OvalRoi BoundingCircle = FindTriangle(X, Y, ip, poly);
//// ip.drawPolygon(BoundingCircle.getPolygon());
rt.addValue("Bounding Circle Diameter", diameter);
ana.displayResults();
ana.updateHeadings();
}
}
/**Returns the square of the passed variable.
*@param N a double
*@return N*N
*/
public double sq(double N){ return (N*N);}
/**
* This method determines the vertices of a polygon which forms a convex
* hull around the image. It does this by first mapping the vertical
* contours of the image. (Horizontal or vertical contours could have
* been used, but only one is necessary.) After they are mapped, all of
* the points which can be enclosed by connecting any other points are
* eliminated. This leaves only the outermost points, the ones that form
* the convex hull. Returns a polygon created with these points.
* @param ip ImageProcessor to work on
* @return PolygonRoi the convex hull
*@see mapTopContours
*@see mapBottomContours
*@see removeContours
*@author Thomas R. Roy, University of Alberta
*/
public PolygonRoi getPolygon(ImageProcessor ip){
Point coords[] = new Point[maxImageWidth * 2];
for (int i = 0; i < maxImageWidth * 2; i++)
coords[i] = new Point();
int[] histogram = new int[256];
int vertCount=0;
int y, x;
Point farLeft, farRight;
//Start by mapping farthest left point
x = this.left;
y=top-2;
do{
y++;
ip.setRoi(x, y, 1, 1);
histogram = ip.getHistogram();
} while (( histogram[ this.foreground ]==0 ) && y<=bottom);
farLeft = new Point(x,y);
int index = x;
coords[0].x=index;
coords[0].y=y;
//Find the furthest right point
x = this.right;
y=top-2;
do{
y++;
ip.setRoi(x, y, 1, 1);
histogram = ip.getHistogram();
} while (( histogram[ this.foreground ]==0 ) && y<=bottom);
farRight = new Point(x,y);
//Map the top and bottom contours
vertCount = mapTopContours(farLeft, farRight, coords, vertCount, ip);
int endPoint = vertCount;
vertCount = mapBottomContours(farLeft, farRight, coords, vertCount, ip);
vertCount++;
coords[vertCount]=coords[0];
//Remove the concave contours, leaving only concave ones
coords = removeContours(coords, vertCount, endPoint);
//Produce an array for the output
X = new int [coords.length];
Y = new int [coords.length];
for (int i = 0; i < coords.length; i++) {
X[i]=coords[i].x;
Y[i]=coords[i].y;
}
return new PolygonRoi(X, Y, coords.length, img,Roi.POLYGON);
}
/**Maps the bottom contours of the image.
@param farLeft Point
@param farRight Point
@param coords Point[]
@param vertCount int
@param ip ImageProcessor
@return int for vertical count*/
public int mapBottomContours(Point farLeft, Point farRight,
Point[] coords, int vertCount, ImageProcessor ip){
//Begin mapping bottom contours, right to left
int[] histogram = new int[256];
for (int index = farRight.x; index >= farLeft.x; index--){
int y = this.bottom;
do{
y--;
ip.setRoi(index, y, 1, 1);
histogram = ip.getHistogram();
} while (( histogram[ this.foreground ]==0 ) && y>=top);
if (y>top){
vertCount++;
coords[vertCount].x = index;
coords[vertCount].y=y;
}
}
return vertCount;
}
/**Maps top contours.
*@param farLeft Point
*@param farRight Point
*@param coords Point[]
*@param vertCount int
*@param ip ImageProcessor
*@return int for top count*/
public int mapTopContours(Point farLeft, Point farRight,
Point[] coords, int vertCount, ImageProcessor ip){
//Begin mapping contours left to right
int[] histogram = new int[256];
for (int index = farLeft.x; index <= farRight.x; index++){
int y = this.top;
do{
y++;
ip.setRoi(index, y, 1, 1);
histogram = ip.getHistogram();
} while (( histogram[ this.foreground ]==0 ) && y<=(bottom));
if (yoldmin)
{oldmin=min;
max_i=i;max_i2=anchor;}
}}
int I=0, J=0, A=0;
double maxdist=0;
for (int anchor=0; anchor=min)||(dist2>=min)||(dist3>=min))
{ double newdist=dist1+dist2+dist3;
if (newdist>maxdist){
maxdist=newdist;
I=i;
J=j;
A=anchor;
double [] circ = getCircle(XX[I], YY[I],
XX[J], YY[J], XX[A], YY[A]);
int [] Circ =
DoubleArrayToIntArray(circ, circ.length);
//IJ.showMessage("A"+Circ[0]+"A"+Circ[1]+"A"+Circ[2]);
if (true) {
diameter=Circ[2];
boundingCircle=
new OvalRoi(Circ[0]-Circ[2]/2,
Circ[1]-Circ[2]/2,
Circ[2], Circ[2]);
midx=Circ[0]-Circ[2]/2;
midy=Circ[1]-Circ[2]/2;
}
} }
}
}
}
}
return boundingCircle;
}
}//end class