3 added files
CDMS/src/CDMS/Partridge/ImageComparison
diff -N ImageData.java
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ ImageData.java 4 Sep 2010 01:25:37 -0000 1.1
@@ -0,0 +1,222 @@
+/*
+ * ImageData.java
+ */
+package CDMS.Partridge.ImageComparison;
+
+import java.awt.image.BufferedImage;
+
+/**
+ * Encapsulate the RGB color information associated with an image.
+ *
+ * @author Richard Partridge
+ */
+public class ImageData {
+
+ private PixelArray _pixarray;
+ private int[][] _RGB;
+
+ /**
+ * Construct an empty image.
+ *
+ * @param pixarray pixel array descriptor
+ */
+ public ImageData(PixelArray pixarray) {
+ _pixarray = pixarray;
+ _RGB = new int[pixarray.getNRow()][pixarray.getNCol()];
+ }
+
+ /**
+ * Construct an image using the RGB data contained in a BufferedImage
+ *
+ * @param pixarray pixel array descriptor
+ * @param image image
+ */
+ public ImageData(PixelArray pixarray, BufferedImage image) {
+ _pixarray = pixarray;
+
+ // Check that the image sizes match
+ if (_pixarray.getNRow() != image.getHeight() || _pixarray.getNCol() != image.getWidth())
+ throw new RuntimeException("Image size does not match pixel array descriptor");
+
+ // Translate the image data into the RGB scheme used for the CDMS image analysis and
+ // store it locally
+ for (int row=0; row<_pixarray.getNRow(); row++) {
+ for (int col=0; col<_pixarray.getNCol(); col++) {
+ int RGB = image.getRGB(col, row);
+ _RGB[row][col] = translateBufferedImageRGB(RGB);
+ }
+ }
+ }
+
+ /**
+ * Return the pixel array descriptor
+ *
+ * @return pixel array descriptor
+ */
+ public PixelArray getPixelArray() {
+ return _pixarray;
+ }
+
+ /**
+ * Return the blue color data
+ *
+ * @param RGB packed color data
+ * @return blue color data
+ */
+ public int getBlue(int RGB) {
+ return RGB & 0xff;
+ }
+
+ /**
+ * Return the green color data
+ *
+ * @param RGB packed color data
+ * @return green color data
+ */
+ public int getGreen(int RGB) {
+ return (RGB & 0xff00) >> 8;
+ }
+
+ /**
+ * Return the red color data
+ *
+ * @param RGB packed color data
+ * @return red color data
+ */
+ public int getRed(int RGB) {
+ return (RGB & 0xff0000) >> 16;
+ }
+
+ /**
+ * Return the intensity from the color data
+ *
+ * @param red red color data
+ * @param green green color data
+ * @param blue blue color data
+ * @return intensity
+ */
+ public double getIntensity(int red, int green, int blue) {
+ return Math.sqrt((red * red + green * green + blue * blue) / 3);
+ }
+
+ /**
+ * Return the intensity from the packed color data
+ *
+ * @param RGB packed color data
+ * @return intensity
+ */
+ public double getIntensity(int RGB) {
+ return getIntensity(getRed(RGB), getGreen(RGB), getBlue(RGB));
+ }
+
+ /**
+ * Return the intensity for a given row/col in the pixel array
+ * @param row image row
+ * @param col image col
+ * @return intensity
+ */
+ public double getIntensity(int row, int col) {
+ return getIntensity(getRGB(row, col));
+ }
+
+ /**
+ * Set the packed color data for a pixel
+ * @param row image row
+ * @param col image column
+ * @param RGB packed color data
+ */
+ public void setRGB(int row, int col, int RGB) {
+ _RGB[row][col] = RGB;
+ }
+
+ /**
+ * Set the packed color data for a pixel
+ * @param row image row
+ * @param col image column
+ * @param red red color data
+ * @param green green color data
+ * @param blue blue color data
+ */
+ public void setRGB(int row, int col, int red, int green, int blue) {
+ setRGB(row, col, makeRGB(red, green, blue));
+ }
+
+ /**
+ * Set the packed color data for a pixel
+ *
+ * @param pixel pixel number as specified by the pixel array descriptor
+ * @param RGB packed color data
+ */
+ public void setRGB(long pixel, int RGB) {
+ setRGB(_pixarray.getRow(pixel), _pixarray.getCol(pixel), RGB);
+ }
+
+ /**
+ * Set the packed color data for a pixel
+ *
+ * @param pixel pixel number as specified by the pixel array descriptor
+ * @param red red color data
+ * @param green green color data
+ * @param blue blue color data
+ */
+ public void setRGB(long pixel, int red, int green, int blue) {
+ setRGB(pixel, makeRGB(red, green, blue));
+ }
+
+ /**
+ * Return the packed color data for a given element in the image
+ *
+ * @param row image row
+ * @param col image column
+ * @return packed color data
+ */
+ public int getRGB(int row, int col) {
+ return _RGB[row][col];
+ }
+
+ /**
+ * Return the packed color data for a pixel
+ *
+ * @param pixel pixel number as specified by the pixel array descriptor
+ * @return packed color data
+ */
+ public int getRGB(long pixel) {
+ return getRGB(_pixarray.getRow(pixel), _pixarray.getCol(pixel));
+ }
+
+ /**
+ * Translate from the BufferedImage color scheme to the one used here. At
+ * present, it is believe these schemes are the same based on trial and
+ * error techniques. Since it is not entirely clear what format is used
+ * for RGB data in a BufferedImage, keep this simple method as a place
+ * holder for dealing with possible future complications and for now
+ * just mask off the upper 8 bits.
+ *
+ * @param RGB color data for a BufferedImage pixel
+ * @return packed color data
+ */
+ private int translateBufferedImageRGB(int RGB) {
+ // Since the pixel RGB scheme is believed to match the BufferedImage convention,
+ // skip decoding the BufferedImage convention
+ // int blue = pixel & 0x000000ff;
+ // int green = (pixel & 0x0000ff00) >> 8;
+ // int red = (pixel & 0x00ff0000) >> 16;
+ // return makePixel(red, green, blue);
+ return RGB & 0xffffff;
+ }
+
+ /**
+ * Return the packed color given the color components
+ *
+ * @param red red color data
+ * @param green green color data
+ * @param blue blue color data
+ * @return packed color data
+ */
+ private int makeRGB(int red, int green, int blue) {
+ if (red < 0 || red > 0xff) throw new RuntimeException("Invalid RGB data for red: "+red);
+ if (green < 0 || green > 0xff) throw new RuntimeException("Invalid RGB data for green: "+green);
+ if (blue < 0 || blue > 0xff) throw new RuntimeException("Invalid RGB data for blue: "+blue);
+ return (red << 16) + (green << 8) + red;
+ }
+}
CDMS/src/CDMS/Partridge/ImageComparison
diff -N NearestNeighborClustering.java
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ NearestNeighborClustering.java 4 Sep 2010 01:25:37 -0000 1.1
@@ -0,0 +1,178 @@
+/*
+ * NearestNeighborClusteringAlgorithm.java
+ */
+package CDMS.Partridge.ImageComparison;
+
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+
+/**
+ * This class uses a nearest neighbor algorithm to find clusters of pixels
+ * that are different between two images.
+ *
+ * The algorithm first finds possible cluster seeds that are above the seed
+ * threshold. Starting from a seed, the neighbor pixels are searched
+ * to see if we have hits above the neighbor threshold. Neighbor channels
+ * are added until we have a cluster where every neighboring channel is below
+ * the neighbor threshold.
+ *
+ * HashMaps are used to speed up the algorithm when there are large numbers
+ * of possible cluster seeds, and the algorithm is expected to scale as N*log(N)
+ * with the number seeds N.
+ *
+ * @author Richard Partridge
+ */
+public class NearestNeighborClustering {
+
+ private double _seed_threshold;
+ private double _neighbor_threshold;
+
+ /**
+ * Instantiate NearestNeighborClusteringAlgorithm with specified thresholds.
+ * Seed threshold is the minimum deviation to initiate a cluster. Neighbor
+ * threshold is the minimum deviation to add a neighboring cell to a cluster.
+ *
+ * @param seed_threshold seed threhold
+ * @param neighbor_threshold neighbor threshold
+ */
+ public NearestNeighborClustering(double seed_threshold, double neighbor_threshold) {
+
+ _seed_threshold = seed_threshold;
+ _neighbor_threshold = neighbor_threshold;
+ }
+
+ /**
+ * Set the seed threshold.
+ *
+ * @param seed_threshold seed threshold
+ */
+ public void setSeedThreshold(double seed_threshold) {
+ _seed_threshold = seed_threshold;
+ }
+
+ /**
+ * Set the neighbor threshold.
+ *
+ * @param neighbor_threshold neighbor threshold
+ */
+ public void setNeighborThreshold(double neighbor_threshold) {
+ _neighbor_threshold = neighbor_threshold;
+ }
+
+ /**
+ * Return the seed threshold.
+ *
+ * @return seed threshold
+ */
+ public double getSeedThreshold() {
+ return _seed_threshold;
+ }
+
+ /**
+ * Return the neighbor threshold.
+ *
+ * @return neighbor threshold
+ */
+ public double getNeighborThreshold() {
+ return _neighbor_threshold;
+ }
+
+ /**
+ * Form clusters of pixels with deviations above threshold using
+ * the nearest neighbor clustering algorithm.
+ *
+ * @param pixarray pixel array descriptor
+ * @param pixmap map containing deviations for pixels selected for clustering
+ * @return list of clusters, with a cluster being a list of pixels
+ */
+ public List<List<Long>> findClusters(PixelArray pixarray, Map<Long, Double> pixmap) {
+
+ // Check that the seed threshold is at least as large as the neighbor threshold
+ if (_seed_threshold < _neighbor_threshold)
+ throw new RuntimeException("Clustering error: seed threshold below neighbor threshold");
+
+ // Create a map that shows the pixel clustering status
+ int mapsize = 2 * pixmap.size();
+ Map<Long, Boolean> clusterable = new HashMap<Long, Boolean>(mapsize);
+
+ // Create list of pixels to be used as cluster seeds
+ List<Long> cluster_seeds = new ArrayList<Long>();
+
+ // Loop over the input pixels and mark pixels available for clustering and find cluster seeds
+ for (Entry<Long, Double> entry : pixmap.entrySet()) {
+
+ Long pixel = entry.getKey();
+ Double deviation = Math.abs(entry.getValue());
+
+ // Mark this hit as available for clustering if it is above the neighbor threshold
+ clusterable.put(pixel, deviation >= _neighbor_threshold);
+
+ // Add this hit to the list of seeds if it is above the seed threshold
+ if (deviation >= _seed_threshold) {
+ cluster_seeds.add(pixel);
+ }
+ }
+
+ // Create a list of clusters
+ List<List<Long>> clusterlist = new ArrayList<List<Long>>();
+
+ // Loop over the cluster seeds
+ for (Long seed_pixel : cluster_seeds) {
+
+ // First check if this hit is still available for clustering
+ if (!clusterable.get(seed_pixel)) continue;
+
+ // Create a new cluster
+ List<Long> cluster = new ArrayList<Long>();
+
+ // Create a queue to hold channels whose neighbors need to be checked for inclusion
+ LinkedList<Long> unchecked = new LinkedList<Long>();
+
+ // Add the seed channel to the unchecked list and mark it as unavailable for clustering
+ unchecked.addLast(seed_pixel);
+ clusterable.put(seed_pixel, false);
+
+ // Check the neighbors of pixels added to the cluster
+ while (unchecked.size() > 0) {
+
+ // Pull the next pixel off the queue and add it to the cluster
+ long clustered_pixel = unchecked.removeFirst();
+ cluster.add(clustered_pixel);
+
+ // Get the neigbor channels
+ Set<Long> neighbor_pixels = pixarray.getNeighbors(clustered_pixel);
+
+ // Now loop over the neighbors and see if we can add them to the cluster
+ for (long pixel : neighbor_pixels) {
+
+ // Get the status of this channel
+ Boolean addpixel = clusterable.get(pixel);
+
+ // If the map entry is null, this pixel isn't a candidate for clustering
+ if (addpixel == null) continue;
+
+ // Check if this neighbor pixel is still available for clustering
+ if (!addpixel) continue;
+
+ // Add channel to the list of unchecked clustered channels
+ // and mark it unavailable for clustering
+ unchecked.addLast(pixel);
+ clusterable.put(pixel, false);
+
+ } // end of loop over neighbor cells
+ } // end of loop over unchecked cells
+
+ // Finished with this cluster - add it to the list of clusters
+ clusterlist.add(cluster);
+
+ } // end of loop over seed pixels
+
+ // Finished finding clusters
+ return clusterlist;
+ }
+}
\ No newline at end of file
CDMS/src/CDMS/Partridge/ImageComparison
diff -N PixelArray.java
--- /dev/null 1 Jan 1970 00:00:00 -0000
+++ PixelArray.java 4 Sep 2010 01:25:38 -0000 1.1
@@ -0,0 +1,386 @@
+/*
+ * PixelArray.java
+ */
+
+package CDMS.Partridge.ImageComparison;
+
+import java.awt.image.BufferedImage;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Map.Entry;
+import java.util.Set;
+
+/**
+ * This class encapsulates a description of a pixel array associated with a physical
+ * object. Sufficient information is available to provide convert between a pixel
+ * identifier, x/y coordinates, and row/column of the image.
+ *
+ * The pixel array may have associated with it non-overlapping subarrays. This
+ * allows pixel array descriptions to be composed of smaller pixel arrays stitched
+ * together to form a much larger pixel array descriptor.
+ *
+ * @author Richard Partridge
+ */
+public class PixelArray {
+
+ private int _nrow;
+ private int _ncol;
+ private double _xc;
+ private double _yc;
+ private double _dx;
+ private double _dy;
+ private Map<Integer, PixelArray> _subarraymap;
+ private double _eps = 1.e-4; // set tolerance to 0.1 um
+
+ /**
+ * Fully qualified constructor
+ *
+ * @param nrow number of rows for this pixel array
+ * @param ncol number of columns for this pixel array
+ * @param xc x coordinate of the center of the pixel array
+ * @param yc y coordinate of the center of the pixel array
+ * @param dx x pixel size
+ * @param dy y pixel size
+ */
+ public PixelArray(int nrow, int ncol, double xc, double yc, double dx, double dy) {
+ _nrow = nrow;
+ _ncol = ncol;
+ _xc = xc;
+ _yc = yc;
+ _dx = dx;
+ _dy = dy;
+ if (_nrow < 0 || _ncol < 0) throw new RuntimeException("Negative array size - nrow: "+nrow+" ncol: "+ncol);
+ if (_dx <= 0. || _dy <= 0.) throw new RuntimeException("Negative pixel size - dx: "+_dx+" dy: "+dy);
+ _subarraymap = new HashMap<Integer, PixelArray>();
+ }
+
+ /**
+ * Constructor that uses a Buffered Image to specify the number of row/columns in
+ * the pixel array
+ *
+ * @param bufimage BufferedImage represented by this pixel array descriptor
+ * @param xc x coordinate of the center of the pixel array
+ * @param yc y coordinate of the center of the pixel array
+ * @param dx x pixel size
+ * @param dy y pixel size
+ */
+ public PixelArray(BufferedImage bufimage, double xc, double yc, double dx, double dy) {
+ this(bufimage.getHeight(), bufimage.getWidth(), xc, yc, dx, dy);
+ }
+
+ /**
+ * Return the row number for a given pixel
+ *
+ * @param pixel pixel identifier
+ * @return row number
+ */
+ public int getRow(long pixel) {
+ int row = (int) ((pixel >> 32) & 0xffffffffL);
+ if (row < 0 || row >= _nrow) throw new RuntimeException("Invalid pixel number"+pixel);
+ return row;
+ }
+
+ /**
+ * Return the row number for a given y coordinate
+ *
+ * @param y y coordinate
+ * @return row number
+ */
+ public int getRow(double y) {
+ int ipix = (int) Math.ceil((y - _yc) / _dy + _nrow / 2.);
+ if (ipix < 0 || ipix >= _nrow) throw new RuntimeException("Row outside pixel array for y = "+y);
+ return ipix;
+ }
+
+ /**
+ * Return the column number for a given pixel
+ * @param pixel pixel identifier
+ * @return column number
+ */
+ public int getCol(long pixel) {
+ int col = (int) (pixel & 0xffffffffL);
+ if (col < 0 || col >= _ncol) throw new RuntimeException("Invalid pixel number"+pixel);
+ return col;
+ }
+
+ /**
+ * Return the column number for a given x coordinate
+ *
+ * @param x x coordinate
+ * @return column number
+ */
+ public int getCol(double x) {
+ int ipix = (int) Math.ceil((x - _xc) / _dx + _ncol / 2.);
+ if (ipix < 0 || ipix >= _ncol) throw new RuntimeException("Col outside pixel array for x = "+x);
+ return ipix;
+ }
+
+ /**
+ * Return the pixel identifier for a given row and column
+ * @param row row number
+ * @param col column number
+ * @return pixel identifier
+ */
+ public long getPixel(int row, int col) {
+ if (row < 0 || row >= _nrow) throw new RuntimeException("Invalid row number"+row);
+ if (col < 0 || col >= _ncol) throw new RuntimeException("Invalid col number"+col);
+ long lrow = row;
+ long lcol = col;
+ return (lrow << 32) + lcol;
+ }
+
+ /**
+ * Return the pixel identifier for a given x,y coordinate
+ *
+ * @param x x coordinate
+ * @param y y coordinate
+ * @return pixel identifier
+ */
+ public long getPixel(double x, double y) {
+ return getPixel(getRow(y), getCol(x));
+ }
+
+ /**
+ * Return the number of rows associated with this pixel array
+ *
+ * @return number of rows
+ */
+ public int getNRow() {
+ return _nrow;
+ }
+
+ /**
+ * Return the number of columns associated with this pixel array
+ *
+ * @return number of columns
+ */
+ public int getNCol() {
+ return _ncol;
+ }
+
+ /**
+ * Return the x coordinate of a given pixel
+ *
+ * @param pixel pixel identifier
+ * @return x coordinate
+ */
+ public double getX(long pixel) {
+ return _xc + (getCol(pixel) - (_ncol - 1.) / 2.) * _dx;
+ }
+
+ /**
+ * Return the y coordinate of a given pixel
+ *
+ * @param pixel pixel identifier
+ * @return y coordinate
+ */
+ public double getY(long pixel) {
+ return _yc + (getRow(pixel) - (_nrow - 1.) / 2.) * _dy;
+ }
+
+ /**
+ * Return the x coordinate of the center of the pixel array
+ *
+ * @return x center coordinate
+ */
+ public double getXC() {
+ return _xc;
+ }
+
+ /**
+ * Return the y coordinate of the center of the pixel array
+ *
+ * @return y center coordinate
+ */
+ public double getYC() {
+ return _yc;
+ }
+
+ /**
+ * Return the width in x of a pixel
+ *
+ * @return x pixel size
+ */
+ public double getXSize() {
+ return _dx;
+ }
+
+ /**
+ * Return the height in y of a pixel
+ *
+ * @return y pixel size
+ */
+ public double getYSize() {
+ return _dy;
+ }
+
+ /**
+ * Return the minimum x coordinate for the pixel array
+ *
+ * @return minimum x coordinate
+ */
+ public double getXMin() {
+ return _xc - 0.5 * _ncol * _dx;
+ }
+
+ /**
+ * Return the maximum x coordinate for the pixel array
+ *
+ * @return maximum x coordinate
+ */
+ public double getXMax() {
+ return _xc + 0.5 * _ncol * _dx;
+ }
+
+ /**
+ * Return the minimum y coordinate of the pixel array
+ *
+ * @return minimum y coordinate
+ */
+ public double getYMin() {
+ return _yc - 0.5 * _nrow * _dy;
+ }
+
+ /**
+ * Return the maximum y coordinate of the pixel array
+ *
+ * @return maximum y coordinate
+ */
+ public double getYMax() {
+ return _yc + 0.5 * _nrow * _dy;
+ }
+
+ /**
+ * Check whether a given x coordinate is within the pixel array
+ *
+ * @param x x coordinate
+ * @return true if inside
+ */
+ public boolean xInside(double x) {
+ return Math.abs(x -_xc) < 0.5 * _ncol * _dx + _eps;
+ }
+
+ /**
+ * Check whether a given y coordinate is within the pixel array
+ *
+ * @param y y coordinate
+ * @return true if inside
+ */
+ public boolean yInside(double y) {
+ return Math.abs(y -_yc) < 0.5 * _nrow * _dy + _eps;
+ }
+
+ /**
+ * Check whether a given x,y coordinate is within the pixel array
+ *
+ * @param x x coordinate
+ * @param y y coordinate
+ * @return true if inside
+ */
+ public boolean Inside(double x, double y) {
+ return xInside(x) && yInside(y);
+ }
+
+ /**
+ * Check whether a given pixel identifier describes a pixel within the pixel array
+ *
+ * @param pixel pixel identifier
+ * @return true if inside
+ */
+ public boolean Inside(long pixel) {
+ return Inside(getX(pixel), getY(pixel));
+ }
+
+ /**
+ * Add a subarray to this pixel array. The subarray must be fully contained
+ * within the pixel array and not overlap any other subarrays that are present.
+ *
+ * @param id identifier for this subarray (must be >=0)
+ * @param sub subarray
+ */
+ public void addSubArray(int id, PixelArray sub) {
+
+ // Check that we have a positive subarray identifer (negative values will be used to
+ // identify error conditions)
+ if (id < 0) throw new RuntimeException("Subarray ID must be non-negative - ID: "+id);
+
+ // Make sure that the identifier is unique
+ if (_subarraymap.containsKey(id)) throw new RuntimeException("Duplicate subarray identifier");
+
+ // Make sure subarray is entirely inside this pixel array
+ if (!Inside(sub.getXMin(), sub.getYMin()) || !Inside(sub.getXMax(), sub.getYMax()))
+ throw new RuntimeException("Subarray is not contained within this pixel array");
+
+ // Loop over the other subarrays and make sure that we don't overlap any of them
+ for (PixelArray check : _subarraymap.values()) {
+ long ll = getPixel(0, 0);
+ long lr = getPixel(0, check.getNCol() -1);
+ long ul = getPixel(check.getNRow() - 1, 0);
+ long ur = getPixel(check.getNRow() - 1, check.getNCol() - 1);
+ if (Inside(ll) || Inside(lr) || Inside(ul) || Inside(ur))
+ throw new RuntimeException("New subarray overlaps an existing subarray");
+ }
+
+ // Put the subarray into the map that contains the subarrays and their identifiers
+ _subarraymap.put(id, sub);
+ }
+
+ /**
+ * Get the subarray identifier associated with a given x,y position. Returns
+ * a value of -1 if there is no subarray containing these coordinates.
+ *
+ * @param x x coordinate
+ * @param y y coordinate
+ * @return subarray identifier
+ */
+ public int getSubArrayID(double x, double y) {
+ for (Entry<Integer, PixelArray> sub : _subarraymap.entrySet()) {
+ if (sub.getValue().Inside(x, y)) return sub.getKey();
+ }
+ return -1;
+ }
+
+ /**
+ * Return the subarray descriptor associated with a given x,y position
+ *
+ * @param x x coordinate
+ * @param y y coordinate
+ * @return subarray
+ */
+ public PixelArray getSubArray(double x, double y) {
+ int id = getSubArrayID(x, y);
+ return _subarraymap.get(id);
+ }
+
+ /**
+ * Return the subarray descriptor for a given ID
+ *
+ * @param id subarray identifier
+ * @return subarray
+ */
+ public PixelArray getSubArray(int id) {
+ return _subarraymap.get(id);
+ }
+
+ /**
+ * Return a list of neighbors to a given pixel
+ *
+ * @param pixel pixel identifier
+ * @return set of neighbor pixels
+ */
+ public Set<Long> getNeighbors(long pixel) {
+ Set<Long> nbrs = new HashSet<Long>();
+ int row = getRow(pixel);
+ int col = getCol(pixel);
+ for (int irow=row-1; irow<=row+1; irow++) {
+ if (irow < 0 || irow >= _nrow) continue;
+ for (int icol=col-1; icol<=col+1; icol++) {
+ if (icol < 0 || icol > _ncol) continue;
+ nbrs.add(getPixel(irow, icol));
+ }
+ }
+ return nbrs;
+ }
+
+}
CVSspam 0.2.8