001: /*
002: * $RCSfile: MedianCutOpImage.java,v $
003: *
004: * Copyright (c) 2005 Sun Microsystems, Inc. All rights reserved.
005: *
006: * Use is subject to license terms.
007: *
008: * $Revision: 1.2 $
009: * $Date: 2005/05/10 01:03:22 $
010: * $State: Exp $
011: */
012: package com.sun.media.jai.opimage;
013:
014: import java.awt.Image;
015: import java.awt.Rectangle;
016: import java.awt.image.DataBuffer;
017: import java.awt.image.Raster;
018: import java.awt.image.RenderedImage;
019: import java.awt.image.WritableRaster;
020: import java.util.ArrayList;
021: import java.util.Hashtable;
022: import java.util.LinkedList;
023: import java.util.ListIterator;
024: import java.util.Map;
025: import javax.media.jai.ImageLayout;
026: import javax.media.jai.LookupTableJAI;
027: import javax.media.jai.OpImage;
028: import javax.media.jai.PixelAccessor;
029: import javax.media.jai.PlanarImage;
030: import javax.media.jai.ROI;
031: import javax.media.jai.ROIShape;
032: import javax.media.jai.UnpackedImageData;
033: import com.sun.media.jai.util.ImageUtil;
034:
035: /**
036: * An <code>OpImage</code> implementing the "ColorQuantizer" operation as
037: * described in <code>javax.media.jai.operator.ExtremaDescriptor</code>
038: * based on the median-cut algorithm.
039: *
040: * @see javax.media.jai.operator.ExtremaDescriptor
041: * @see ExtremaCRIF
042: */
043: public class MedianCutOpImage extends ColorQuantizerOpImage {
044: /** The size of the histogram. */
045: private int histogramSize;
046:
047: /** The counts of the colors. */
048: private int[] counts;
049:
050: /** The colors for the color histogram. */
051: private int[] colors;
052:
053: /** The partition of the RGB color space. Each cube contains one
054: * cluster.
055: */
056: private Cube[] partition;
057:
058: /** The maximum number of bits to contains 32768 colors. */
059: private int bits = 8;
060:
061: /** The mask to generate the low bits colors from the original colors. */
062: private int mask;
063:
064: /** The histgram hash. */
065: HistogramHash histogram;
066:
067: /**
068: * Constructs an <code>MedianCutOpImage</code>.
069: *
070: * @param source The source image.
071: */
072: public MedianCutOpImage(RenderedImage source, Map config,
073: ImageLayout layout, int maxColorNum, int upperBound,
074: ROI roi, int xPeriod, int yPeriod) {
075: super (source, config, layout, maxColorNum, roi, xPeriod,
076: yPeriod);
077:
078: colorMap = null;
079: this .histogramSize = upperBound;
080: }
081:
082: protected synchronized void train() {
083: PlanarImage source = getSourceImage(0);
084: if (roi == null)
085: roi = new ROIShape(source.getBounds());
086:
087: // Cycle throw all source tiles.
088: int minTileX = source.getMinTileX();
089: int maxTileX = source.getMaxTileX();
090: int minTileY = source.getMinTileY();
091: int maxTileY = source.getMaxTileY();
092: int xStart = source.getMinX();
093: int yStart = source.getMinY();
094:
095: histogram = new HistogramHash(histogramSize);
096:
097: while (true) {
098: histogram.init();
099: int oldbits = bits;
100: mask = (255 << 8 - bits) & 255;
101: mask = mask | (mask << 8) | (mask << 16);
102:
103: for (int y = minTileY; y <= maxTileY; y++) {
104: for (int x = minTileX; x <= maxTileX; x++) {
105: // Determine the required region of this tile.
106: // (Note that getTileRect() instersects tile and
107: // image bounds.)
108: Rectangle tileRect = source.getTileRect(x, y);
109:
110: // Process if and only if within ROI bounds.
111: if (roi.intersects(tileRect)) {
112:
113: // If checking for skipped tiles determine
114: // whether this tile is "hit".
115: if (checkForSkippedTiles
116: && tileRect.x >= xStart
117: && tileRect.y >= yStart) {
118: // Determine the offset within the tile.
119: int offsetX = (xPeriod - ((tileRect.x - xStart) % xPeriod))
120: % xPeriod;
121: int offsetY = (yPeriod - ((tileRect.y - yStart) % yPeriod))
122: % yPeriod;
123:
124: // Continue with next tile if offset
125: // is larger than either tile dimension.
126: if (offsetX >= tileRect.width
127: || offsetY >= tileRect.height) {
128: continue;
129: }
130: }
131:
132: // add the histogram.
133: computeHistogram(source.getData(tileRect));
134: if (histogram.isFull())
135: break;
136: }
137: }
138:
139: if (histogram.isFull())
140: break;
141: }
142:
143: if (oldbits == bits) {
144: counts = histogram.getCounts();
145: colors = histogram.getColors();
146: break;
147: }
148: }
149:
150: medianCut(maxColorNum);
151: setProperty("LUT", colorMap);
152: setProperty("JAI.LookupTable", colorMap);
153: }
154:
155: private void computeHistogram(Raster source) {
156: if (!isInitialized) {
157: srcPA = new PixelAccessor(getSourceImage(0));
158: srcSampleType = srcPA.sampleType == PixelAccessor.TYPE_BIT ? DataBuffer.TYPE_BYTE
159: : srcPA.sampleType;
160: isInitialized = true;
161: }
162:
163: Rectangle srcBounds = getSourceImage(0).getBounds()
164: .intersection(source.getBounds());
165:
166: LinkedList rectList;
167: if (roi == null) { // ROI is the whole Raster
168: rectList = new LinkedList();
169: rectList.addLast(srcBounds);
170: } else {
171: rectList = roi.getAsRectangleList(srcBounds.x, srcBounds.y,
172: srcBounds.width, srcBounds.height);
173: if (rectList == null) {
174: return; // ROI does not intersect with Raster boundary.
175: }
176: }
177:
178: ListIterator iterator = rectList.listIterator(0);
179: int xStart = source.getMinX();
180: int yStart = source.getMinY();
181:
182: while (iterator.hasNext()) {
183: Rectangle rect = srcBounds
184: .intersection((Rectangle) iterator.next());
185: int tx = rect.x;
186: int ty = rect.y;
187:
188: // Find the actual ROI based on start and period.
189: rect.x = startPosition(tx, xStart, xPeriod);
190: rect.y = startPosition(ty, yStart, yPeriod);
191: rect.width = tx + rect.width - rect.x;
192: rect.height = ty + rect.height - rect.y;
193:
194: if (rect.isEmpty()) {
195: continue; // no pixel to count in this rectangle
196: }
197:
198: UnpackedImageData uid = srcPA.getPixels(source, rect,
199: srcSampleType, false);
200: switch (uid.type) {
201: case DataBuffer.TYPE_BYTE:
202: computeHistogramByte(uid);
203: break;
204: }
205: }
206: }
207:
208: private void computeHistogramByte(UnpackedImageData uid) {
209: Rectangle rect = uid.rect;
210: byte[][] data = uid.getByteData();
211: int lineStride = uid.lineStride;
212: int pixelStride = uid.pixelStride;
213: byte[] rBand = data[0];
214: byte[] gBand = data[1];
215: byte[] bBand = data[2];
216:
217: int lineInc = lineStride * yPeriod;
218: int pixelInc = pixelStride * xPeriod;
219:
220: int lastLine = rect.height * lineStride;
221:
222: for (int lo = 0; lo < lastLine; lo += lineInc) {
223: int lastPixel = lo + rect.width * pixelStride;
224:
225: for (int po = lo; po < lastPixel; po += pixelInc) {
226: int p = ((rBand[po + uid.bandOffsets[0]] & 0xff) << 16)
227: | ((gBand[po + uid.bandOffsets[1]] & 0xff) << 8)
228: | (bBand[po + uid.bandOffsets[2]] & 0xff);
229: if (!histogram.insert(p & mask)) {
230: bits--;
231: return;
232: }
233: }
234: }
235: }
236:
237: /** Applies the Heckbert's median-cut algorithm to partition the color
238: * space into <code>maxcubes</code> cubes. The centroids
239: * of each cube are are used to create a color table.
240: */
241: public void medianCut(int expectedColorNum) {
242: int k;
243: int num, width;
244:
245: Cube cubeA, cubeB;
246:
247: // Creates the first color cube
248: partition = new Cube[expectedColorNum];
249: int numCubes = 0;
250: Cube cube = new Cube();
251: int numColors = 0;
252: for (int i = 0; i < histogramSize; i++) {
253: if (counts[i] != 0) {
254: numColors++;
255: cube.count = cube.count + counts[i];
256: }
257: }
258:
259: cube.lower = 0;
260: cube.upper = numColors - 1;
261: cube.level = 0;
262: shrinkCube(cube);
263: partition[numCubes++] = cube;
264:
265: //Partition the cubes until the expected number of cubes are reached, or
266: // cannot further partition
267: while (numCubes < expectedColorNum) {
268: // Search the list of cubes for next cube to split, the lowest level cube
269: int level = 255;
270: int splitableCube = -1;
271:
272: for (k = 0; k < numCubes; k++) {
273: if (partition[k].lower != partition[k].upper
274: && partition[k].level < level) {
275: level = partition[k].level;
276: splitableCube = k;
277: }
278: }
279:
280: // no more cubes to split
281: if (splitableCube == -1)
282: break;
283:
284: // Find longest dimension of this cube: 0 - red, 1 - green, 2 - blue
285: cube = partition[splitableCube];
286: level = cube.level;
287:
288: // Weigted with luminosities
289: int lr = 77 * (cube.rmax - cube.rmin);
290: int lg = 150 * (cube.gmax - cube.gmin);
291: int lb = 29 * (cube.bmax - cube.bmin);
292:
293: int longDimMask = 0;
294: if (lr >= lg && lr >= lb)
295: longDimMask = 0xFF0000;
296: if (lg >= lr && lg >= lb)
297: longDimMask = 0xFF00;
298: if (lb >= lr && lb >= lg)
299: longDimMask = 0xFF;
300:
301: // Sort along "longdim"
302: quickSort(colors, cube.lower, cube.upper, longDimMask);
303:
304: // Find median
305: int count = 0;
306: int median = cube.lower;
307: for (; median <= cube.upper - 1; median++) {
308: if (count >= cube.count / 2)
309: break;
310: count = count + counts[median];
311: }
312:
313: // Now split "cube" at the median and add the two new
314: // cubes to the list of cubes.
315: cubeA = new Cube();
316: cubeA.lower = cube.lower;
317: cubeA.upper = median - 1;
318: cubeA.count = count;
319: cubeA.level = cube.level + 1;
320: shrinkCube(cubeA);
321: partition[splitableCube] = cubeA; // add in old slot
322:
323: cubeB = new Cube();
324: cubeB.lower = median;
325: cubeB.upper = cube.upper;
326: cubeB.count = cube.count - count;
327: cubeB.level = cube.level + 1;
328: shrinkCube(cubeB);
329: partition[numCubes++] = cubeB; // add in new slot */
330: }
331:
332: // creates the lookup table and the inverse mapping
333: createLUT(numCubes);
334: }
335:
336: /** Shrinks the provided <code>Cube</code> to a smallest contains
337: * the same colors defined in the histogram.
338: */
339: private void shrinkCube(Cube cube) {
340: int rmin = 255;
341: int rmax = 0;
342: int gmin = 255;
343: int gmax = 0;
344: int bmin = 255;
345: int bmax = 0;
346: for (int i = cube.lower; i <= cube.upper; i++) {
347: int color = colors[i];
348: int r = color >> 16;
349: int g = (color >> 8) & 255;
350: int b = color & 255;
351: if (r > rmax)
352: rmax = r;
353: else if (r < rmin)
354: rmin = r;
355:
356: if (g > gmax)
357: gmax = g;
358: else if (g < gmin)
359: gmin = g;
360:
361: if (b > bmax)
362: bmax = b;
363: else if (b < bmin)
364: bmin = b;
365: }
366:
367: cube.rmin = rmin;
368: cube.rmax = rmax;
369: cube.gmin = gmin;
370: cube.gmax = gmax;
371: cube.bmin = bmin;
372: cube.bmax = bmax;
373: }
374:
375: /** Creates the lookup table and computes the inverse mapping. */
376: private void createLUT(int ncubes) {
377: if (colorMap == null) {
378: colorMap = new LookupTableJAI(new byte[3][ncubes]);
379: }
380:
381: byte[] rLUT = colorMap.getByteData(0);
382: byte[] gLUT = colorMap.getByteData(1);
383: byte[] bLUT = colorMap.getByteData(2);
384:
385: float scale = 255.0f / (mask & 255);
386:
387: for (int k = 0; k < ncubes; k++) {
388: Cube cube = partition[k];
389: float rsum = 0.0f, gsum = 0.0f, bsum = 0.0f;
390: int r, g, b;
391: for (int i = cube.lower; i <= cube.upper; i++) {
392: int color = colors[i];
393: r = color >> 16;
394: rsum += (float) r * (float) counts[i];
395: g = (color >> 8) & 255;
396: gsum += (float) g * (float) counts[i];
397: b = color & 255;
398: bsum += (float) b * (float) counts[i];
399: }
400:
401: // Update the color map
402: rLUT[k] = (byte) (rsum / (float) cube.count * scale);
403: gLUT[k] = (byte) (gsum / (float) cube.count * scale);
404: bLUT[k] = (byte) (bsum / (float) cube.count * scale);
405: }
406: }
407:
408: void quickSort(int a[], int lo0, int hi0, int longDimMask) {
409: // Based on the QuickSort method by James Gosling from Sun's SortDemo applet
410:
411: int lo = lo0;
412: int hi = hi0;
413: int mid, t;
414:
415: if (hi0 > lo0) {
416: mid = a[(lo0 + hi0) / 2] & longDimMask;
417: while (lo <= hi) {
418: while ((lo < hi0) && ((a[lo] & longDimMask) < mid))
419: ++lo;
420: while ((hi > lo0) && ((a[hi] & longDimMask) > mid))
421: --hi;
422: if (lo <= hi) {
423: t = a[lo];
424: a[lo] = a[hi];
425: a[hi] = t;
426:
427: t = counts[lo];
428: counts[lo] = counts[hi];
429: counts[hi] = t;
430:
431: ++lo;
432: --hi;
433: }
434: }
435: if (lo0 < hi)
436: quickSort(a, lo0, hi, longDimMask);
437: if (lo < hi0)
438: quickSort(a, lo, hi0, longDimMask);
439: }
440: }
441: }
442:
443: class Cube { // structure for a cube in color space
444: int lower; // one corner's index in histogram
445: int upper; // another corner's index in histogram
446: int count; // cube's histogram count
447: int level; // cube's level
448: int rmin, rmax;
449: int gmin, gmax;
450: int bmin, bmax;
451:
452: Cube() {
453: count = 0;
454: }
455: }
456:
457: /** A hash table for the color histogram. This is based on the first
458: * hashtable algorithm I learnt.
459: */
460: class HistogramHash {
461: int capacity;
462: int[] colors;
463: int[] counts;
464: int size;
465: int hashsize;
466: boolean packed = false;
467: int[] newColors;
468: int[] newCounts;
469:
470: public HistogramHash(int capacity) {
471: this .capacity = capacity;
472: this .hashsize = capacity * 4 / 3;
473: this .colors = new int[hashsize];
474: this .counts = new int[hashsize];
475: }
476:
477: void init() {
478: this .size = 0;
479: this .packed = false;
480: for (int i = 0; i < hashsize; i++) {
481: colors[i] = -1;
482: counts[i] = 0;
483: }
484: }
485:
486: boolean insert(int node) {
487: int hashPos = hashCode(node);
488: if (colors[hashPos] == -1) {
489: colors[hashPos] = node;
490: counts[hashPos]++;
491: size++;
492: return size <= capacity;
493: } else if (colors[hashPos] == node) {
494: counts[hashPos]++;
495: return size <= capacity;
496: } else {
497: for (int next = hashPos + 1; next != hashPos; next++) {
498: next %= hashsize;
499: if (colors[next] == -1) {
500: colors[next] = node;
501: counts[next]++;
502: size++;
503: return size <= capacity;
504: } else if (colors[next] == node) {
505: counts[next]++;
506: return size <= capacity;
507: }
508: }
509: }
510: return size <= capacity;
511: }
512:
513: boolean isFull() {
514: return size > capacity;
515: }
516:
517: void put(int node, int value) {
518: int hashPos = hashCode(node);
519: if (colors[hashPos] == -1) {
520: colors[hashPos] = node;
521: counts[hashPos] = value;
522: size++;
523: return;
524: } else if (colors[hashPos] == node) {
525: counts[hashPos] = value;
526: return;
527: } else {
528: for (int next = hashPos + 1; next != hashPos; next++) {
529: next %= hashsize;
530: if (colors[next] == -1) {
531: colors[next] = node;
532: counts[next] = value;
533: size++;
534: return;
535: } else if (colors[next] == node) {
536: counts[next] = value;
537: return;
538: }
539: }
540: }
541: return;
542: }
543:
544: int get(int node) {
545: int hashPos = hashCode(node);
546: if (colors[hashPos] == node) {
547: return counts[hashPos];
548: } else {
549: for (int next = hashPos + 1; next != hashPos; next++) {
550: next %= hashsize;
551: if (colors[next] == node) {
552: return counts[next];
553: }
554: }
555: }
556: return -1;
557: }
558:
559: int[] getCounts() {
560: if (!packed)
561: pack();
562: return newCounts;
563: }
564:
565: int[] getColors() {
566: if (!packed)
567: pack();
568: return newColors;
569: }
570:
571: void pack() {
572: newColors = new int[capacity];
573: newCounts = new int[capacity];
574:
575: for (int i = 0, j = 0; i < hashsize; i++) {
576: if (colors[i] != -1) {
577: newColors[j] = colors[i];
578: newCounts[j] = counts[i];
579: j++;
580: }
581: }
582:
583: packed = true;
584: }
585:
586: int hashCode(int value) {
587: return ((value >> 16) * 33023 + ((value >> 8) & 255) * 30013 + (value & 255) * 27011)
588: % hashsize;
589:
590: }
591: }
|