| Wand.java |
package ij.gui;
import ij.*;
import ij.process.*;
import ij.plugin.WandToolOptions;
import java.awt.*;
/** This class implements ImageJ's wand (tracing) tool.
* The wand selects pixels of equal or similar value or thresholded pixels
* forming a contiguous area.
* The wand creates selections that have only one boundary line (inner holes
* are not excluded from the selection). There may be holes at the boundary,
* however, if the boundary line touches the same vertex twice (both in
* 4-connected and 8-connected mode).
*
* Version 2009-06-01 (code refurbished; tolerance, 4- & 8-connected options added)
*/
public class Wand {
/** Wand operation type: trace outline of 4-connected pixels */
public final static int FOUR_CONNECTED = 4;
/** Wand operation type: trace outline of 8-connected pixels */
public final static int EIGHT_CONNECTED = 8;
/** Wand operation type similar to that of ImageJ 1.42p and before; for backwards
* compatibility.
* In this mode, no checking is done whether the foreground or the background
* gets selected; four- or 8-connected behaviour depends on foreground/background
* and (if no selection) on whether the initial pixel is on a 1-pixel wide line. */
public final static int LEGACY_MODE = 1;
/** The number of points in the generated outline. */
public int npoints;
private int maxPoints = 1000; // will be increased if necessary
/** The x-coordinates of the points in the outline.
A vertical boundary at x separates the pixels at x-1 and x. */
public int[] xpoints = new int[maxPoints];
/** The y-coordinates of the points in the outline.
A horizontal boundary at y separates the pixels at y-1 and y. */
public int[] ypoints = new int[maxPoints];
private final static int THRESHOLDED_MODE = 256; //work on threshold
private ImageProcessor ip;
private byte[] bpixels;
private int[] cpixels;
private short[] spixels;
private float[] fpixels;
private int width, height;
private float lowerThreshold, upperThreshold;
private int xmin; // of selection created
private boolean exactPixelValue; // For color, match RGB, not gray value
private static boolean allPoints; // output contains intermediate points
/** Constructs a Wand object from an ImageProcessor. */
public Wand(ImageProcessor ip) {
this.ip = ip;
Object pixels = ip.getPixels();
if (pixels instanceof byte[])
bpixels = (byte[])pixels;
else if (pixels instanceof int[])
cpixels = (int[])pixels;
else if (pixels instanceof short[])
spixels = (short[])pixels;
else if (pixels instanceof float[])
fpixels = (float[])pixels;
width = ip.getWidth();
height = ip.getHeight();
}
/** Traces an object defined by lower and upper threshold values.
* 'mode' can be FOUR_CONNECTED or EIGHT_CONNECTED.
* ('LEGACY_MODE' is also supported and may result in selection of
* interior holes instead of the thresholded area if one clicks left
* of an interior hole).
* The start coordinates must be inside the area or left of it.
* When successful, npoints>0 and the boundary points can be accessed
* in the public xpoints and ypoints fields. */
public void autoOutline(int startX, int startY, double lower, double upper, int mode) {
lowerThreshold = (float)lower;
upperThreshold = (float)upper;
autoOutline(startX, startY, 0.0, mode|THRESHOLDED_MODE);
}
/** Traces an object defined by lower and upper threshold values or an
* interior hole; whatever is found first ('legacy mode').
* For compatibility with previous versions of ImageJ.
* The start coordinates must be inside the area or left of it.
* When successful, npoints>0 and the boundary points can be accessed
* in the public xpoints and ypoints fields. */
public void autoOutline(int startX, int startY, double lower, double upper) {
autoOutline(startX, startY, lower, upper, THRESHOLDED_MODE|LEGACY_MODE);
}
/** This is a variation of legacy autoOutline that uses int threshold arguments. */
public void autoOutline(int startX, int startY, int lower, int upper) {
autoOutline(startX, startY, (double)lower, (double)upper, THRESHOLDED_MODE|LEGACY_MODE);
}
/** Traces the boundary of an area of uniform color, where
* 'startX' and 'startY' are somewhere inside the area.
* When successful, npoints>0 and the boundary points can be accessed
* in the public xpoints and ypoints fields.
* For compatibility with previous versions of ImageJ only; otherwise
* use the reliable method specifying 4-connected or 8-connected mode
* and the tolerance. */
public void autoOutline(int startX, int startY) {
autoOutline(startX, startY, 0.0, LEGACY_MODE);
}
/** Traces the boundary of the area with pixel values within
* 'tolerance' of the value of the pixel at the starting location.
* 'tolerance' is in uncalibrated units.
* 'mode' can be FOUR_CONNECTED or EIGHT_CONNECTED.
* Mode LEGACY_MODE is for compatibility with previous versions of ImageJ;
* ignored if tolerance > 0.
* Mode bit THRESHOLDED_MODE for internal use only; it is set by autoOutline
* with 'upper' and 'lower' arguments.
* When successful, npoints>0 and the boundary points can be accessed
* in the public xpoints and ypoints fields. */
public void autoOutline(int startX, int startY, double tolerance, int mode) {
if (startX<0 || startX>=width || startY<0 || startY>=height) return;
if (fpixels!=null && Float.isNaN(getPixel(startX, startY))) return;
WandToolOptions.setStart(startX, startY);
exactPixelValue = tolerance==0;
boolean thresholdMode = (mode & THRESHOLDED_MODE) != 0;
boolean legacyMode = (mode & LEGACY_MODE) != 0 && tolerance == 0;
if (!thresholdMode) {
double startValue = getPixel(startX, startY);
lowerThreshold = (float)(startValue - tolerance);
upperThreshold = (float)(startValue + tolerance);
}
int x = startX;
int y = startY;
int seedX; // the first inside pixel
if (inside(x,y)) { // find a border when coming from inside
seedX = x; // (seedX, startY) is an inside pixel
do {x++;} while (inside(x,y));
} else { // find a border when coming from outside (thresholded only)
do {
x++;
if (x>=width) return; // no border found
} while (!inside(x,y));
seedX = x;
}
boolean fourConnected;
if (legacyMode)
fourConnected = !thresholdMode && !(isLine(x, y));
else
fourConnected = (mode & FOUR_CONNECTED) != 0;
//now, we have a border between (x-1, y) and (x,y)
boolean first = true;
while (true) { // loop until we have not traced an inner hole
boolean insideSelected = traceEdge(x, y, fourConnected);
if (legacyMode) return; // in legacy mode, don't care what we have got
if (insideSelected) { // not an inner hole
if (first) return; // started at seed, so we got it (sucessful)
if (xmin<=seedX) { // possibly the correct particle
Polygon poly = new Polygon(xpoints, ypoints, npoints);
if (poly.contains(seedX, startY))
return; // successful, particle contains seed
}
}
first = false;
// we have traced an inner hole or the wrong particle
if (!inside(x,y)) do {
x++; // traverse the hole
if (x>width) throw new RuntimeException("Wand Malfunction"); //should never happen
} while (!inside(x,y));
do {x++;} while (inside(x,y)); //retry here; maybe no inner hole any more
}
}
/* Trace the outline, starting at a point (startX, startY).
* Pixel (startX-1, startY) must be outside, (startX, startY) must be inside,
* or reverse. Otherwise an endless loop will occur (and eat up all memory).
* Traces 8-connected inside pixels unless fourConnected is true.
* Returns whether the selection created encloses an 'inside' area
* and not an inner hole.
*/
private boolean traceEdge(int startX, int startY, boolean fourConnected) {
// Let us name the crossings between 4 pixels vertices, then the
// vertex (x,y) marked with '+', is between pixels (x-1, y-1) and (x,y):
//
// pixel x-1 x
// y-1 |
// ----+----
// y |
//
// The four principal directions are numbered such that the direction
// number * 90 degrees gives the angle in the mathematical sense; and
// the directions to the adjacent pixels (for inside(x,y,direction) are
// at (number * 90 - 45) degrees:
// walking pixel
// directions: 1 directions: 2 | 1
// 2 + 0 ----+----
// 3 3 | 0
//
// Directions, like angles, are cyclic; direction -1 = direction 3, etc.
//
// The algorithm: We walk along the border, from one vertex to the next,
// with the outside pixels always being at the left-hand side.
// For 8-connected tracing, we always trying to turn left as much as
// possible, to encompass an area as large as possible.
// Thus, when walking in direction 1 (up, -y), we start looking
// at the pixel in direction 2; if it is inside, we proceed in this
// direction (left); otherwise we try with direction 1 (up); if pixel 1
// is not inside, we must proceed in direction 0 (right).
//
// 2 | 1 (i=inside, o=outside)
// direction 2 < ---+---- > direction 0
// o | i
// ^ direction 1 = up = starting direction
//
// For 4-connected pixels, we try to go right as much as possible:
// First try with pixel 1; if it is outside we go in direction 0 (right).
// Otherwise, we examine pixel 2; if it is outside, we go in
// direction 1 (up); otherwise in direction 2 (left).
//
// When moving a closed loop, 'direction' gets incremented or decremented
// by a total of 360 degrees (i.e., 4) for counterclockwise and clockwise
// loops respectively. As the inside pixels are at the right side, we have
// got an outline of inner pixels after a cw loop (direction decremented
// by 4).
//
npoints = 0;
xmin = width;
final int startDirection;
if (inside(startX,startY)) // inside at left, outside right
startDirection = 1; // starting in direction 1 = up
else {
startDirection = 3; // starting in direction 3 = down
startY++; // continue after the boundary that has direction 3
}
int x = startX;
int y = startY;
int direction = startDirection;
do {
int newDirection;
if (fourConnected) {
newDirection = direction;
do {
if (!inside(x, y, newDirection)) break;
newDirection++;
} while (newDirection < direction+2);
newDirection--;
} else { // 8-connected
newDirection = direction + 1;
do {
if (inside(x, y, newDirection)) break;
newDirection--;
} while (newDirection >= direction);
}
if (allPoints || newDirection!=direction)
addPoint(x,y); // a corner point of the outline polygon: add to list
switch (newDirection & 3) { // '& 3' is remainder modulo 4
case 0: x++; break;
case 1: y--; break;
case 2: x--; break;
case 3: y++; break;
}
direction = newDirection;
} while (x!=startX || y!=startY || (direction&3)!=startDirection);
if (xpoints[0]!=x && !allPoints) // if the start point = end point is a corner: add to list
addPoint(x, y);
return (direction <= 0); // if we have done a clockwise loop, inside pixels are enclosed
}
// add a point x,y to the outline polygon
private void addPoint (int x, int y) {
if (npoints==maxPoints) {
int[] xtemp = new int[maxPoints*2];
int[] ytemp = new int[maxPoints*2];
System.arraycopy(xpoints, 0, xtemp, 0, maxPoints);
System.arraycopy(ypoints, 0, ytemp, 0, maxPoints);
xpoints = xtemp;
ypoints = ytemp;
maxPoints *= 2;
}
xpoints[npoints] = x;
ypoints[npoints] = y;
npoints++;
if (xmin > x) xmin = x;
}
// check pixel at (x,y), whether it is inside traced area
private boolean inside(int x, int y) {
if (x<0 || x>=width || y<0 || y>=height)
return false;
float value = getPixel(x, y);
return value>=lowerThreshold && value<=upperThreshold;
}
// check pixel in a given direction from vertex (x,y)
private boolean inside(int x, int y, int direction) {
switch(direction & 3) { // '& 3' is remainder modulo 4
case 0: return inside(x, y);
case 1: return inside(x, y-1);
case 2: return inside(x-1, y-1);
case 3: return inside(x-1, y);
}
return false; //will never occur, needed for the compiler
}
// get a pixel value; returns Float.NaN if outside the field.
private float getPixel(int x, int y) {
if (x<0 || x>=width || y<0 || y>=height)
return Float.NaN;
if (bpixels!=null)
return bpixels[y*width + x] & 0xff;
else if (spixels!=null)
return spixels[y*width + x] & 0xffff;
else if (fpixels!=null)
return fpixels[y*width + x];
else if (exactPixelValue) //RGB for exact match
return cpixels[y*width + x] & 0xffffff; //don't care for upper byte
else //gray value of RGB
return ip.getPixelValue(x,y);
}
/* Are we tracing a one pixel wide line? Makes Legacy mode 8-connected instead of 4-connected */
private boolean isLine(int xs, int ys) {
int r = 5;
int xmin=xs;
int xmax=xs+2*r;
if (xmax>=width) xmax=width-1;
int ymin=ys-r;
if (ymin<0) ymin=0;
int ymax=ys+r;
if (ymax>=height) ymax=height-1;
int area = 0;
int insideCount = 0;
for (int x=xmin; (x<=xmax); x++)
for (int y=ymin; y<=ymax; y++) {
area++;
if (inside(x,y))
insideCount++;
}
if (IJ.debugMode)
IJ.log((((double)insideCount)/area<0.25?"line ":"blob ")+insideCount+" "+area+" "+IJ.d2s(((double)insideCount)/area));
return ((double)insideCount)/area<0.25;
}
/** Set 'true' and output will contain intermediate points for straight lines longer than one pixel. */
public static void setAllPoints(boolean b) {
allPoints = b;
}
/** Returns 'true' if output contains intermediate points for straight lines longer than one pixel. */
public static boolean allPoints() {
return allPoints;
}
}