001: /*
002: * @(#) $Header
003: *
004: * Copyright (C) 2007 Forklabs Daniel Léonard
005: *
006: * This program is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU General Public License
008: * as published by the Free Software Foundation; either version 2
009: * of the License, or (at your option) any later version.
010: *
011: * This program is distributed in the hope that it will be useful,
012: * but WITHOUT ANY WARRANTY; without even the implied warranty of
013: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
014: * GNU General Public License for more details.
015: *
016: * You should have received a copy of the GNU General Public License
017: * along with this program; if not, write to the Free Software
018: * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
019: */
020:
021: package ca.forklabs.media.jai.opimage;
022:
023: import java.awt.Point;
024: import java.awt.Rectangle;
025: import java.awt.image.Raster;
026: import java.awt.image.RenderedImage;
027: import java.awt.image.WritableRaster;
028: import java.util.Arrays;
029: import java.util.Comparator;
030: import java.util.Map;
031: import java.util.Random;
032: import javax.media.jai.ImageLayout;
033: import javax.media.jai.UntiledOpImage;
034: import javax.media.jai.iterator.RandomIter;
035: import javax.media.jai.iterator.RandomIterFactory;
036: import javax.media.jai.iterator.WritableRandomIter;
037: import ca.forklabs.media.jai.operator.KMeansDescriptor;
038:
039: /**
040: * Class {@code KMeansOpImage} is the {@link OpImage} for operator
041: * <em>kmeans</em>.
042: *
043: * @author <a href="mailto:forklabs at dev.java.net?subject=ca.forklabs.media.jai.opimage.KMeansOpImage">Daniel Léonard</a>
044: * @version $Revision: 1.2 $
045: */
046: public class KMeansOpImage extends UntiledOpImage {
047:
048: //---------------------------
049: // Instance variables
050: //---------------------------
051:
052: /** The number of clusters to make. */
053: protected int clusters;
054:
055: /** The evaluation function. */
056: protected KMeansDescriptor.EvaluationFunction function;
057:
058: /** The number of iteration to perform. */
059: protected int iterations;
060:
061: /** The color map of the segmented image. */
062: protected int[][] color_map;
063:
064: //---------------------------
065: // Constructors
066: //---------------------------
067:
068: /**
069: * Constructor.
070: * @param source the image to segment.
071: * @param clusters the number of desired clusters.
072: * @param function the evaluation function.
073: * @param iterations the maximum number of iterations.
074: * @param color_map the color_map of the segmented image.
075: * @param hints rendering hints.
076: * @param layout image layout.
077: */
078: public KMeansOpImage(RenderedImage source, int clusters,
079: KMeansDescriptor.EvaluationFunction function,
080: int iterations, int[][] color_map, Map<?, ?> hints,
081: ImageLayout layout) {
082: super (source, hints, layout);
083: this .setup(clusters, function, iterations, color_map);
084: }
085:
086: //---------------------------
087: // Accessors and mutators
088: //---------------------------
089:
090: /**
091: * Changes the number of clusters.
092: * @param clusters the new number of clusters.
093: */
094: protected void setClusters(int clusters) {
095: this .clusters = clusters;
096: }
097:
098: /**
099: * Gets the desired number of clusters.
100: * @return the number of clusters.
101: */
102: protected int getClusters() {
103: return this .clusters;
104: }
105:
106: /**
107: * Changes the evaluation function.
108: * @param function the new function.
109: */
110: protected void setEvaluationFunction(
111: KMeansDescriptor.EvaluationFunction function) {
112: this .function = function;
113: }
114:
115: /**
116: * Gets the evaluation function.
117: * @return the function.
118: */
119: protected KMeansDescriptor.EvaluationFunction getEvaluationFunction() {
120: return this .function;
121: }
122:
123: /**
124: * Changes the number of iterations.
125: * @param iterations the new number of iterations.
126: */
127: protected void setIterations(int iterations) {
128: this .iterations = iterations;
129: }
130:
131: /**
132: * Gets the desired number of iterations.
133: * @return the number of iterations.
134: */
135: protected int getIterations() {
136: return this .iterations;
137: }
138:
139: /**
140: * Changes the color map.
141: * @param color_map the new color map.
142: */
143: protected void setColorMap(int[][] color_map) {
144: this .color_map = color_map;
145: }
146:
147: /**
148: * Gets the color map.
149: * @return the color map.
150: */
151: protected int[][] getColorMap() {
152: return this .color_map;
153: }
154:
155: //---------------------------
156: // Instance methods
157: //---------------------------
158:
159: /**
160: * Performs a stable in-place sort of the center from smallest to greatest. A
161: * center is smaller if its square distance from the origin is smaller then
162: * another square distance.
163: * @param centers the center to sort.
164: */
165: protected void sortCenters(double[][] centers) {
166: Arrays.sort(centers, new Comparator<double[]>() {
167: private double squareDistance(double[] array) {
168: double distance = 0.0;
169: for (int i = 0, len = array.length; i < len; i++) {
170: distance += array[i] * array[i];
171: }
172: return distance;
173: }
174:
175: @Override
176: public int compare(double[] array1, double[] array2) {
177: double square_len_1 = this .squareDistance(array1);
178: double square_len_2 = this .squareDistance(array2);
179: int comparison = (int) (square_len_1 - square_len_2);
180: return comparison;
181: }
182: });
183: }
184:
185: /**
186: * Initialize the new centers. It tries to have different values for centers,
187: * but is not always capable of doing so, especially if there are less
188: * segments than clusters.
189: * @param source the source.
190: * @param bounds the source boundaries.
191: * @param function the evaluation function.
192: * @return the initial centers.
193: */
194: @SuppressWarnings("hiding")
195: protected double[][] initializeCenters(Raster source,
196: Rectangle bounds,
197: KMeansDescriptor.EvaluationFunction function) {
198: int clusters = this .getClusters();
199: double[][] centers = new double[clusters][];
200:
201: int min_x = (int) bounds.getMinX();
202: int min_y = (int) bounds.getMinY();
203: int width = (int) bounds.getWidth();
204: int height = (int) bounds.getHeight();
205:
206: // the centers are selected at random, but they all must be different
207: Random random = new Random();
208: RandomIter iterator = RandomIterFactory.create(source, source
209: .getBounds());
210: Point position = new Point();
211: for (int i = 0, tries = 0; (i < clusters);) {
212: position.x = min_x + random.nextInt(width);
213: position.y = min_y + random.nextInt(height);
214:
215: centers[i] = function.invoke(iterator, position).clone();
216:
217: boolean center_already_exist = false;
218: for (int j = 0; (false == center_already_exist) && (j < i); j++) {
219: double[] previous = centers[j];
220: center_already_exist = Arrays.equals(centers[i],
221: previous);
222: }
223:
224: // if the center already exist, we try again,
225: // but if we tried too much, we take what we
226: // have and continue
227: if ((center_already_exist && (tries < 100))) {
228: tries++;
229: } else {
230: i++;
231: tries = 0;
232: }
233: }
234:
235: iterator.done();
236:
237: this .sortCenters(centers);
238:
239: return centers;
240: }
241:
242: /**
243: * Resets the <em>new center</em> data structures.
244: * @param positions the position of the new centers.
245: * @param population the population of each new center.
246: */
247: protected void resetNewCenters(double[][] positions,
248: double[] population) {
249: for (double[] position : positions) {
250: Arrays.fill(position, 0.0);
251: }
252: Arrays.fill(population, 0.0);
253: }
254:
255: /**
256: * Calculate the square of the distance of the pixel from each center pixel.
257: * @param pixel the pixel.
258: * @param centers the center pixels.
259: * @param distances the arrays to store the square distances.
260: * @return {@code distances}.
261: */
262: protected double[] calculateSquareDistances(double[] pixel,
263: double[][] centers, double[] distances) {
264: int num_clusters = centers.length;
265: int num_bands = pixel.length;
266:
267: for (int c = 0; c < num_clusters; c++) {
268: double distance = 0.0;
269: for (int b = 0; b < num_bands; b++) {
270: double diff = pixel[b] - centers[c][b];
271: distance += diff * diff;
272: }
273: distances[c] = distance;
274: }
275: return distances;
276: }
277:
278: /**
279: * Gets the position of the smallest distance.
280: * @param distances the distances.
281: * @return the position.
282: */
283: protected int findClosestCenter(double[] distances) {
284: int cluster = 0;
285: double min = distances[cluster];
286:
287: for (int c = 1, len = distances.length; c < len; c++) {
288: double candidate = distances[c];
289: boolean is_smaller_than_minimum = (candidate < min);
290: if (is_smaller_than_minimum) {
291: cluster = c;
292: min = candidate;
293: }
294: }
295:
296: return cluster;
297: }
298:
299: /**
300: * Gets the error message telling that the raster data type is unknown.
301: * @param type the bad type.
302: * @return the formatted error message.
303: */
304: @SuppressWarnings("boxing")
305: protected String getUnknownDataTypeErrorMessage(int type) {
306: String key = Resources.UNKNOWN_DATA_TYPE;
307: String message = Resources.getLocalizedString(key, type);
308: return message;
309: }
310:
311: /**
312: * Sets up this image.
313: * @param clusters the number of desired clusters.
314: * @param function the evaluation function.
315: * @param iterations the number of desired iterations.
316: * @param color_map the color map.
317: */
318: protected void setup(int clusters,
319: KMeansDescriptor.EvaluationFunction function,
320: int iterations, int[][] color_map) {
321: this .setClusters(clusters);
322: this .setEvaluationFunction(function);
323: this .setIterations(iterations);
324: this .setColorMap(color_map);
325: }
326:
327: //---------------------------
328: // Overriden methods from javax.media.jai.UntiledOpImage
329: //---------------------------
330:
331: /**
332: * Computes the k-means image.
333: * @param sources the source rasters.
334: * @param sink the sink raster.
335: * @param the bounds to work within.
336: */
337: @Override
338: @SuppressWarnings("hiding")
339: protected void computeImage(Raster[] sources, WritableRaster sink,
340: Rectangle bounds) {
341: Raster source = sources[0];
342:
343: KMeansDescriptor.EvaluationFunction function = this
344: .getEvaluationFunction();
345: double[][] centers = this .initializeCenters(source, bounds,
346: function);
347: // for each iteration until stability :
348: // 1) sort and reset the centers
349: // 2) for each row
350: // 2a) for each column
351: // 2ai) get the pixel
352: // 2aii) calculate its distance from each center
353: // 2aiii) find the center that is closest
354: // 2aiv) update the data structure for the next iteration centers
355: // 2av) set the pixel value of the sink to the cluster number and
356: // record if any change occured
357: // 3) calculate the position of the new centers
358:
359: int bands = source.getNumBands();
360: double[] sink_pixel = new double[bands];
361:
362: int clusters = this .getClusters();
363: double[] distances = new double[clusters];
364: double[][] new_centers_position = new double[clusters][bands];
365: double[] new_centers_population = new double[clusters];
366: boolean is_stable = false;
367:
368: RandomIter source_iter = RandomIterFactory.create(source,
369: source.getBounds());
370: WritableRandomIter sink_iter = RandomIterFactory
371: .createWritable(sink, sink.getBounds());
372:
373: int min_x = (int) bounds.getX();
374: int max_x = (int) (min_x + bounds.getWidth());
375: int min_y = (int) bounds.getY();
376: int max_y = (int) (min_y + bounds.getHeight());
377: Point position = new Point();
378:
379: int iterations = this .getIterations();
380: for (int i = 0; (false == is_stable) && (i < iterations); i++) {
381: // 1)
382: this .sortCenters(centers);
383: this .resetNewCenters(new_centers_position,
384: new_centers_population);
385: is_stable = true;
386:
387: // 2)
388: for (int y = min_y; y < max_y; y++) {
389: // 2a)
390: for (int x = min_x; x < max_x; x++) {
391: position.x = x;
392: position.y = y;
393: // 2ai)
394: double[] src_pixel = function.invoke(source_iter,
395: position);
396: // 2aii)
397: distances = this .calculateSquareDistances(
398: src_pixel, centers, distances);
399: // 2aiii)
400: int cluster = this .findClosestCenter(distances);
401: // 2aiv)
402: for (int b = 0; b < bands; b++) {
403: new_centers_position[cluster][b] += src_pixel[b];
404: }
405: new_centers_population[cluster]++;
406: // 2av)
407: sink_iter.getPixel(x, y, sink_pixel);
408: // For a single pixel in the sink image, all its component have the
409: // same value. To determine if the pixel needs to have its color
410: // changed, we only need to check the first element.
411: boolean has_this _pixel_changed = (cluster != sink_pixel[0]);
412: if (has_this _pixel_changed) {
413: Arrays.fill(sink_pixel, cluster);
414: sink_iter.setPixel(x, y, sink_pixel);
415: }
416: is_stable &= !has_this _pixel_changed;
417: }
418: }
419:
420: // 3)
421: for (int c = 0; c < clusters; c++) {
422: for (int b = 0; b < bands; b++) {
423: // BUG : what happens if a center has no population ?
424: centers[c][b] = new_centers_position[c][b]
425: / new_centers_population[c];
426: }
427: }
428: }
429:
430: int[][] color_map = this .getColorMap();
431: for (int y = min_y; y < max_y; y++) {
432: for (int x = min_x; x < max_x; x++) {
433: sink_iter.getPixel(x, y, sink_pixel);
434:
435: int cluster = (int) sink_pixel[0];
436: int[] color = color_map[cluster];
437:
438: sink_iter.setPixel(x, y, color);
439: }
440: }
441:
442: source_iter.done();
443: sink_iter.done();
444:
445: // BUG : set the color model as an indexed color model
446: }
447:
448: }
|