001: /*
002: * $RCSfile: OctTreeOpImage.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:23 $
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.util.ArrayList;
020: import java.util.Hashtable;
021: import java.util.LinkedList;
022: import java.util.ListIterator;
023: import java.util.Map;
024: import javax.media.jai.ImageLayout;
025: import javax.media.jai.LookupTableJAI;
026: import javax.media.jai.OpImage;
027: import javax.media.jai.PixelAccessor;
028: import javax.media.jai.PlanarImage;
029: import javax.media.jai.ROI;
030: import javax.media.jai.ROIShape;
031: import javax.media.jai.UnpackedImageData;
032: import com.sun.media.jai.util.ImageUtil;
033:
034: /**
035: * An <code>OpImage</code> implementing the "ColorQuantizer" operation as
036: * described in <code>javax.media.jai.operator.ExtremaDescriptor</code>
037: * based on the oct-tree algorithm.
038: *
039: * An efficient color quantization algorithm, adapted from the C++
040: * implementation quantize.c in <a
041: * href="http://www.imagemagick.org/">ImageMagick</a>. The pixels for
042: * an image are placed into an oct tree. The oct tree is reduced in
043: * size, and the pixels from the original image are reassigned to the
044: * nodes in the reduced tree.<p>
045: *
046: * Here is the copyright notice from ImageMagick:
047: *
048: * <pre>
049: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
050: % Permission is hereby granted, free of charge, to any person obtaining a %
051: % copy of this software and associated documentation files ("ImageMagick"), %
052: % to deal in ImageMagick without restriction, including without limitation %
053: % the rights to use, copy, modify, merge, publish, distribute, sublicense, %
054: % and/or sell copies of ImageMagick, and to permit persons to whom the %
055: % ImageMagick is furnished to do so, subject to the following conditions: %
056: % %
057: % The above copyright notice and this permission notice shall be included in %
058: % all copies or substantial portions of ImageMagick. %
059: % %
060: % The software is provided "as is", without warranty of any kind, express or %
061: % implied, including but not limited to the warranties of merchantability, %
062: % fitness for a particular purpose and noninfringement. In no event shall %
063: % E. I. du Pont de Nemours and Company be liable for any claim, damages or %
064: % other liability, whether in an action of contract, tort or otherwise, %
065: % arising from, out of or in connection with ImageMagick or the use or other %
066: % dealings in ImageMagick. %
067: % %
068: % Except as contained in this notice, the name of the E. I. du Pont de %
069: % Nemours and Company shall not be used in advertising or otherwise to %
070: % promote the sale, use or other dealings in ImageMagick without prior %
071: % written authorization from the E. I. du Pont de Nemours and Company. %
072: % %
073: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
074: </pre>
075: *
076: * In this <code>OpImage</code>, two significant bugs in the original code are
077: * fix: (1) The computation of tree depth; (2) The computation of the pixels
078: * on each node.
079: *
080: * @see javax.media.jai.operator.ExtremaDescriptor
081: * @see ExtremaCRIF
082: */
083: public class OctTreeOpImage extends ColorQuantizerOpImage {
084: /** The size of the histogram. */
085: private int treeSize;
086:
087: private int maxTreeDepth = 8;
088:
089: // these are precomputed in advance
090: private int squares[];
091:
092: {
093: squares = new int[(maxColorNum << 1) + 1];
094: for (int i = -maxColorNum; i <= maxColorNum; i++) {
095: squares[i + maxColorNum] = i * i;
096: }
097: }
098:
099: /**
100: * Constructs an <code>OctTreeOpImage</code>.
101: *
102: * @param source The source image.
103: */
104: public OctTreeOpImage(RenderedImage source, Map config,
105: ImageLayout layout, int maxColorNum, int upperBound,
106: ROI roi, int xPeriod, int yPeriod) {
107: super (source, config, layout, maxColorNum, roi, xPeriod,
108: yPeriod);
109:
110: colorMap = null;
111: this .treeSize = upperBound;
112: }
113:
114: protected synchronized void train() {
115: Cube cube = new Cube(getSourceImage(0), maxColorNum);
116: cube.constructTree();
117: cube.reduction();
118: cube.assignment();
119:
120: colorMap = new LookupTableJAI(cube.colormap);
121: setProperty("LUT", colorMap);
122: setProperty("JAI.LookupTable", colorMap);
123: }
124:
125: class Cube {
126: PlanarImage source;
127: int max_colors;
128: byte[][] colormap = new byte[3][];
129:
130: Node root;
131: int depth;
132:
133: // counter for the number of colors in the cube. this gets
134: // recalculated often.
135: int colors;
136:
137: // counter for the number of nodes in the tree
138: int nodes;
139:
140: Cube(PlanarImage source, int max_colors) {
141: this .source = source;
142: this .max_colors = max_colors;
143:
144: int i = max_colors;
145: // tree_depth = log max_colors
146: // 2
147: for (depth = 0; i != 0; depth++) {
148: i >>>= 1;
149: }
150:
151: if (depth > maxTreeDepth) {
152: depth = maxTreeDepth;
153: } else if (depth < 2) {
154: depth = 2;
155: }
156:
157: root = new Node(this );
158: }
159:
160: void constructTree() {
161: if (roi == null)
162: roi = new ROIShape(source.getBounds());
163:
164: // Cycle throw all source tiles.
165: int minTileX = source.getMinTileX();
166: int maxTileX = source.getMaxTileX();
167: int minTileY = source.getMinTileY();
168: int maxTileY = source.getMaxTileY();
169: int xStart = source.getMinX();
170: int yStart = source.getMinY();
171:
172: for (int y = minTileY; y <= maxTileY; y++) {
173: for (int x = minTileX; x <= maxTileX; x++) {
174: // Determine the required region of this tile.
175: // (Note that getTileRect() instersects tile and
176: // image bounds.)
177: Rectangle tileRect = source.getTileRect(x, y);
178:
179: // Process if and only if within ROI bounds.
180: if (roi.intersects(tileRect)) {
181: // If checking for skipped tiles determine
182: // whether this tile is "hit".
183: if (checkForSkippedTiles
184: && tileRect.x >= xStart
185: && tileRect.y >= yStart) {
186: // Determine the offset within the tile.
187: int offsetX = (xPeriod - ((tileRect.x - xStart) % xPeriod))
188: % xPeriod;
189: int offsetY = (yPeriod - ((tileRect.y - yStart) % yPeriod))
190: % yPeriod;
191:
192: // Continue with next tile if offset
193: // is larger than either tile dimension.
194: if (offsetX >= tileRect.width
195: || offsetY >= tileRect.height) {
196: continue;
197: }
198: }
199: // construct the tree
200: constructTree(source.getData(tileRect));
201: }
202: }
203: }
204: }
205:
206: private void constructTree(Raster source) {
207: if (!isInitialized) {
208: srcPA = new PixelAccessor(getSourceImage(0));
209: srcSampleType = srcPA.sampleType == PixelAccessor.TYPE_BIT ? DataBuffer.TYPE_BYTE
210: : srcPA.sampleType;
211: isInitialized = true;
212: }
213:
214: Rectangle srcBounds = getSourceImage(0).getBounds()
215: .intersection(source.getBounds());
216:
217: LinkedList rectList;
218: if (roi == null) { // ROI is the whole Raster
219: rectList = new LinkedList();
220: rectList.addLast(srcBounds);
221: } else {
222: rectList = roi.getAsRectangleList(srcBounds.x,
223: srcBounds.y, srcBounds.width, srcBounds.height);
224: if (rectList == null) {
225: return; // ROI does not intersect with Raster boundary.
226: }
227: }
228: ListIterator iterator = rectList.listIterator(0);
229: int xStart = source.getMinX();
230: int yStart = source.getMinY();
231:
232: while (iterator.hasNext()) {
233: Rectangle rect = srcBounds
234: .intersection((Rectangle) iterator.next());
235: int tx = rect.x;
236: int ty = rect.y;
237:
238: // Find the actual ROI based on start and period.
239: rect.x = startPosition(tx, xStart, xPeriod);
240: rect.y = startPosition(ty, yStart, yPeriod);
241: rect.width = tx + rect.width - rect.x;
242: rect.height = ty + rect.height - rect.y;
243:
244: if (rect.isEmpty()) {
245: continue; // no pixel to count in this rectangle
246: }
247:
248: UnpackedImageData uid = srcPA.getPixels(source, rect,
249: srcSampleType, false);
250: switch (uid.type) {
251: case DataBuffer.TYPE_BYTE:
252: constructTreeByte(uid);
253: break;
254: }
255: }
256: }
257:
258: /*
259: * Procedure Classification begins by initializing a color
260: * description tree of sufficient depth to represent each
261: * possible input color in a leaf. However, it is impractical
262: * to generate a fully-formed color description tree in the
263: * classification phase for realistic values of cmax. If
264: * colors components in the input image are quantized to k-bit
265: * precision, so that cmax= 2k-1, the tree would need k levels
266: * below the root node to allow representing each possible
267: * input color in a leaf. This becomes prohibitive because the
268: * tree's total number of nodes is 1 + sum(i=1,k,8k).
269: *
270: * A complete tree would require 19,173,961 nodes for k = 8,
271: * cmax = 255. Therefore, to avoid building a fully populated
272: * tree, QUANTIZE: (1) Initializes data structures for nodes
273: * only as they are needed; (2) Chooses a maximum depth for
274: * the tree as a function of the desired number of colors in
275: * the output image (currently log2(colormap size)).
276: *
277: * For each pixel in the input image, classification scans
278: * downward from the root of the color description tree. At
279: * each level of the tree it identifies the single node which
280: * represents a cube in RGB space containing It updates the
281: * following data for each such node:
282: *
283: * number_pixels : Number of pixels whose color is contained
284: * in the RGB cube which this node represents;
285: *
286: * unique : Number of pixels whose color is not represented
287: * in a node at lower depth in the tree; initially, n2 = 0
288: * for all nodes except leaves of the tree.
289: *
290: * total_red/green/blue : Sums of the red, green, and blue
291: * component values for all pixels not classified at a lower
292: * depth. The combination of these sums and n2 will
293: * ultimately characterize the mean color of a set of pixels
294: * represented by this node.
295: */
296: private void constructTreeByte(UnpackedImageData uid) {
297: Rectangle rect = uid.rect;
298: byte[][] data = uid.getByteData();
299: int lineStride = uid.lineStride;
300: int pixelStride = uid.pixelStride;
301: byte[] rBand = data[0];
302: byte[] gBand = data[1];
303: byte[] bBand = data[2];
304:
305: int lineInc = lineStride * yPeriod;
306: int pixelInc = pixelStride * xPeriod;
307:
308: int lastLine = rect.height * lineStride;
309:
310: for (int lo = 0; lo < lastLine; lo += lineInc) {
311: int lastPixel = lo + rect.width * pixelStride;
312:
313: for (int po = lo; po < lastPixel; po += pixelInc) {
314: int red = rBand[po + uid.bandOffsets[0]] & 0xff;
315: int green = gBand[po + uid.bandOffsets[1]] & 0xff;
316: int blue = bBand[po + uid.bandOffsets[2]] & 0xff;
317:
318: // a hard limit on the number of nodes in the tree
319: if (nodes > treeSize) {
320: root.pruneLevel();
321: --depth;
322: }
323:
324: // walk the tree to depth, increasing the
325: // number_pixels count for each node
326: Node node = root;
327: for (int level = 1; level <= depth; ++level) {
328: int id = ((red > node.mid_red ? 1 : 0)
329: | ((green > node.mid_green ? 1 : 0) << 1) | ((blue > node.mid_blue ? 1
330: : 0) << 2));
331: if (node.child[id] == null) {
332: node = new Node(node, id, level);
333: } else
334: node = node.child[id];
335: node.number_pixels++;
336: }
337:
338: ++node.unique;
339: node.total_red += red;
340: node.total_green += green;
341: node.total_blue += blue;
342: }
343: }
344: }
345:
346: /*
347: * reduction repeatedly prunes the tree until the number of
348: * nodes with unique > 0 is less than or equal to the maximum
349: * number of colors allowed in the output image.
350: *
351: * When a node to be pruned has offspring, the pruning
352: * procedure invokes itself recursively in order to prune the
353: * tree from the leaves upward. The statistics of the node
354: * being pruned are always added to the corresponding data in
355: * that node's parent. This retains the pruned node's color
356: * characteristics for later averaging.
357: */
358: void reduction() {
359: int totalSamples = (source.getWidth() + xPeriod - 1)
360: / xPeriod * (source.getHeight() + yPeriod - 1)
361: / yPeriod;
362: int threshold = Math
363: .max(1, totalSamples / (max_colors * 8));
364: while (colors > max_colors) {
365: colors = 0;
366: threshold = root.reduce(threshold, Integer.MAX_VALUE);
367: }
368: }
369:
370: /*
371: * Procedure assignment generates the output image from the
372: * pruned tree. The output image consists of two parts: (1) A
373: * color map, which is an array of color descriptions (RGB
374: * triples) for each color present in the output image; (2) A
375: * pixel array, which represents each pixel as an index into
376: * the color map array.
377: *
378: * First, the assignment phase makes one pass over the pruned
379: * color description tree to establish the image's color map.
380: * For each node with n2 > 0, it divides Sr, Sg, and Sb by n2.
381: * This produces the mean color of all pixels that classify no
382: * lower than this node. Each of these colors becomes an entry
383: * in the color map.
384: *
385: * Finally, the assignment phase reclassifies each pixel in
386: * the pruned tree to identify the deepest node containing the
387: * pixel's color. The pixel's value in the pixel array becomes
388: * the index of this node's mean color in the color map.
389: */
390: void assignment() {
391: colormap = new byte[3][colors];
392:
393: colors = 0;
394: root.colormap();
395: }
396:
397: /**
398: * A single Node in the tree.
399: */
400: class Node {
401: Cube cube;
402:
403: // parent node
404: Node parent;
405:
406: // child nodes
407: Node child[];
408: int nchild;
409:
410: // our index within our parent
411: int id;
412: // our level within the tree
413: int level;
414: // our color midpoint
415: int mid_red;
416: int mid_green;
417: int mid_blue;
418:
419: // the pixel count for this node and all children
420: int number_pixels;
421:
422: // the pixel count for this node
423: int unique;
424: // the sum of all pixels contained in this node
425: int total_red;
426: int total_green;
427: int total_blue;
428:
429: // used to build the colormap
430: int color_number;
431:
432: Node(Cube cube) {
433: this .cube = cube;
434: this .parent = this ;
435: this .child = new Node[8];
436: this .id = 0;
437: this .level = 0;
438:
439: this .number_pixels = Integer.MAX_VALUE;
440:
441: this .mid_red = (maxColorNum + 1) >> 1;
442: this .mid_green = (maxColorNum + 1) >> 1;
443: this .mid_blue = (maxColorNum + 1) >> 1;
444: }
445:
446: Node(Node parent, int id, int level) {
447: this .cube = parent.cube;
448: this .parent = parent;
449: this .child = new Node[8];
450: this .id = id;
451: this .level = level;
452:
453: // add to the cube
454: ++cube.nodes;
455: if (level == cube.depth) {
456: ++cube.colors;
457: }
458:
459: // add to the parent
460: ++parent.nchild;
461: parent.child[id] = this ;
462:
463: // figure out our midpoint
464: int bi = (1 << (maxTreeDepth - level)) >> 1;
465: mid_red = parent.mid_red + ((id & 1) > 0 ? bi : -bi);
466: mid_green = parent.mid_green
467: + ((id & 2) > 0 ? bi : -bi);
468: mid_blue = parent.mid_blue + ((id & 4) > 0 ? bi : -bi);
469: }
470:
471: /**
472: * Remove this child node, and make sure our parent
473: * absorbs our pixel statistics.
474: */
475: void pruneChild() {
476: --parent.nchild;
477: parent.unique += unique;
478: parent.total_red += total_red;
479: parent.total_green += total_green;
480: parent.total_blue += total_blue;
481: parent.child[id] = null;
482: --cube.nodes;
483: cube = null;
484: parent = null;
485: }
486:
487: /**
488: * Prune the lowest layer of the tree.
489: */
490: void pruneLevel() {
491: if (nchild != 0) {
492: for (int id = 0; id < 8; id++) {
493: if (child[id] != null) {
494: child[id].pruneLevel();
495: }
496: }
497: }
498: if (level == cube.depth) {
499: pruneChild();
500: }
501: }
502:
503: /**
504: * Remove any nodes that have fewer than threshold
505: * pixels. Also, as long as we're walking the tree:
506: *
507: * - figure out the color with the fewest pixels
508: * - recalculate the total number of colors in the tree
509: */
510: int reduce(int threshold, int next_threshold) {
511: if (nchild != 0) {
512: for (int id = 0; id < 8; id++) {
513: if (child[id] != null) {
514: next_threshold = child[id].reduce(
515: threshold, next_threshold);
516: }
517: }
518: }
519:
520: if (number_pixels <= threshold) {
521: pruneChild();
522: } else {
523: if (unique != 0) {
524: cube.colors++;
525: }
526:
527: if (number_pixels < next_threshold) {
528: next_threshold = number_pixels;
529: }
530: }
531:
532: return next_threshold;
533: }
534:
535: /*
536: * colormap traverses the color cube tree and notes each
537: * colormap entry. A colormap entry is any node in the
538: * color cube tree where the number of unique colors is
539: * not zero.
540: */
541: void colormap() {
542: if (nchild != 0) {
543: for (int id = 0; id < 8; id++) {
544: if (child[id] != null) {
545: child[id].colormap();
546: }
547: }
548: }
549: if (unique != 0) {
550: cube.colormap[0][cube.colors] = (byte) ((total_red + (unique >> 1)) / unique);
551: cube.colormap[1][cube.colors] = (byte) ((total_green + (unique >> 1)) / unique);
552: cube.colormap[2][cube.colors] = (byte) ((total_blue + (unique >> 1)) / unique);
553: color_number = cube.colors++;
554: }
555: }
556: }
557: }
558: }
|