001: /*
002: * Helma License Notice
003: *
004: * The contents of this file are subject to the Helma License
005: * Version 2.0 (the "License"). You may not use this file except in
006: * compliance with the License. A copy of the License is available at
007: * http://adele.helma.org/download/helma/license.txt
008: *
009: * Copyright 1998-2003 Helma Software. All Rights Reserved.
010: *
011: * $RCSfile$
012: * $Author: root $
013: * $Revision: 8604 $
014: * $Date: 2007-09-28 15:16:38 +0200 (Fre, 28 Sep 2007) $
015: */
016:
017: package helma.image;
018:
019: import java.awt.AlphaComposite;
020: import java.awt.Graphics2D;
021: import java.awt.image.BufferedImage;
022: import java.awt.image.DataBufferByte;
023: import java.awt.image.DataBufferInt;
024: import java.awt.image.IndexColorModel;
025:
026: /*
027: * Modifications by Juerg Lehni:
028: *
029: * - Ported to Java from C
030: * - Support for alpha-channels.
031: * - Returns a BufferedImage of TYPE_BYTE_INDEXED with a IndexColorModel.
032: * - Dithering of images through helma.image.DiffusionFilterOp by setting
033: * the dither parameter to true.
034: * - Support for a transparent color, which is correctly rendered by GIFEncoder.
035: * All pixels with alpha < 0x80 are converted to this color when the parameter
036: * alphaToBitmask is set to true.
037: */
038: /*
039: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
040: % %
041: % %
042: % %
043: % QQQ U U AAA N N TTTTT IIIII ZZZZZ EEEEE %
044: % Q Q U U A A NN N T I ZZ E %
045: % Q Q U U AAAAA N N N T I ZZZ EEEEE %
046: % Q QQ U U A A N NN T I ZZ E %
047: % QQQQ UUU A A N N T IIIII ZZZZZ EEEEE %
048: % %
049: % %
050: % Methods to Reduce the Number of Unique Colors in an Image %
051: % %
052: % %
053: % Software Design %
054: % John Cristy %
055: % July 1992 %
056: % %
057: % %
058: % Copyright (C) 2003 ImageMagick Studio, a non-profit organization dedicated %
059: % to making software imaging solutions freely available. %
060: % %
061: % Permission is hereby granted, free of charge, to any person obtaining a %
062: % copy of this software and associated documentation files ("ImageMagick"), %
063: % to deal in ImageMagick without restriction, including without limitation %
064: % the rights to use, copy, modify, merge, publish, distribute, sublicense, %
065: % and/or sell copies of ImageMagick, and to permit persons to whom the %
066: % ImageMagick is furnished to do so, subject to the following conditions: %
067: % %
068: % The above copyright notice and this permission notice shall be included in %
069: % all copies or substantial portions of ImageMagick. %
070: % %
071: % The software is provided "as is", without warranty of any kind, express or %
072: % implied, including but not limited to the warranties of merchantability, %
073: % fitness for a particular purpose and noninfringement. In no event shall %
074: % ImageMagick Studio be liable for any claim, damages or other liability, %
075: % whether in an action of contract, tort or otherwise, arising from, out of %
076: % or in connection with ImageMagick or the use or other dealings in %
077: % ImageMagick. %
078: % %
079: % Except as contained in this notice, the name of the ImageMagick Studio %
080: % shall not be used in advertising or otherwise to promote the sale, use or %
081: % other dealings in ImageMagick without prior written authorization from the %
082: % ImageMagick Studio. %
083: % %
084: %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
085: %
086: % Realism in computer graphics typically requires using 24 bits/pixel to
087: % generate an image. Yet many graphic display devices do not contain the
088: % amount of memory necessary to match the spatial and color resolution of
089: % the human eye. The Quantize methods takes a 24 bit image and reduces
090: % the number of colors so it can be displayed on raster device with less
091: % bits per pixel. In most instances, the quantized image closely
092: % resembles the original reference image.
093: %
094: % A reduction of colors in an image is also desirable for image
095: % transmission and real-time animation.
096: %
097: % QuantizeImage() takes a standard RGB or monochrome images and quantizes
098: % them down to some fixed number of colors.
099: %
100: % For purposes of color allocation, an image is a set of n pixels, where
101: % each pixel is a point in RGB space. RGB space is a 3-dimensional
102: % vector space, and each pixel, Pi, is defined by an ordered triple of
103: % red, green, and blue coordinates, (Ri, Gi, Bi).
104: %
105: % Each primary color component (red, green, or blue) represents an
106: % intensity which varies linearly from 0 to a maximum value, Cmax, which
107: % corresponds to full saturation of that color. Color allocation is
108: % defined over a domain consisting of the cube in RGB space with opposite
109: % vertices at (0,0,0) and (Cmax, Cmax, Cmax). QUANTIZE requires Cmax =
110: % 255.
111: %
112: % The algorithm maps this domain onto a tree in which each node
113: % represents a cube within that domain. In the following discussion
114: % these cubes are defined by the coordinate of two opposite vertices:
115: % The vertex nearest the origin in RGB space and the vertex farthest from
116: % the origin.
117: %
118: % The tree's root node represents the the entire domain, (0,0,0) through
119: % (Cmax,Cmax,Cmax). Each lower level in the tree is generated by
120: % subdividing one node's cube into eight smaller cubes of equal size.
121: % This corresponds to bisecting the parent cube with planes passing
122: % through the midpoints of each edge.
123: %
124: % The basic algorithm operates in three phases: Classification,
125: % Reduction, and Assignment. Classification builds a color description
126: % tree for the image. Reduction collapses the tree until the number it
127: % represents, at most, the number of colors desired in the output image.
128: % Assignment defines the output image's color map and sets each pixel's
129: % color by restorage_class in the reduced tree. Our goal is to minimize
130: % the numerical discrepancies between the original colors and quantized
131: % colors (quantization error).
132: %
133: % Classification begins by initializing a color description tree of
134: % sufficient depth to represent each possible input color in a leaf.
135: % However, it is impractical to generate a fully-formed color description
136: % tree in the storage_class phase for realistic values of Cmax. If
137: % colors components in the input image are quantized to k-bit precision,
138: % so that Cmax= 2k-1, the tree would need k levels below the root node to
139: % allow representing each possible input color in a leaf. This becomes
140: % prohibitive because the tree's total number of nodes is 1 +
141: % sum(i=1, k, 8k).
142: %
143: % A complete tree would require 19,173,961 nodes for k = 8, Cmax = 255.
144: % Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
145: % Initializes data structures for nodes only as they are needed; (2)
146: % Chooses a maximum depth for the tree as a function of the desired
147: % number of colors in the output image (currently log2(colormap size)).
148: %
149: % For each pixel in the input image, storage_class scans downward from
150: % the root of the color description tree. At each level of the tree it
151: % identifies the single node which represents a cube in RGB space
152: % containing the pixel's color. It updates the following data for each
153: % such node:
154: %
155: % n1: Number of pixels whose color is contained in the RGB cube which
156: % this node represents;
157: %
158: % n2: Number of pixels whose color is not represented in a node at
159: % lower depth in the tree; initially, n2 = 0 for all nodes except
160: % leaves of the tree.
161: %
162: % Sr, Sg, Sb: Sums of the red, green, and blue component values for all
163: % pixels not classified at a lower depth. The combination of these sums
164: % and n2 will ultimately characterize the mean color of a set of
165: % pixels represented by this node.
166: %
167: % E: The distance squared in RGB space between each pixel contained
168: % within a node and the nodes' center. This represents the
169: % quantization error for a node.
170: %
171: % Reduction repeatedly prunes the tree until the number of nodes with n2
172: % > 0 is less than or equal to the maximum number of colors allowed in
173: % the output image. On any given iteration over the tree, it selects
174: % those nodes whose E count is minimal for pruning and merges their color
175: % statistics upward. It uses a pruning threshold, Ep, to govern node
176: % selection as follows:
177: %
178: % Ep = 0
179: % while number of nodes with (n2 > 0) > required maximum number of colors
180: % prune all nodes such that E <= Ep
181: % Set Ep to minimum E in remaining nodes
182: %
183: % This has the effect of minimizing any quantization error when merging
184: % two nodes together.
185: %
186: % When a node to be pruned has offspring, the pruning procedure invokes
187: % itself recursively in order to prune the tree from the leaves upward.
188: % n2, Sr, Sg, and Sb in a node being pruned are always added to the
189: % corresponding data in that node's parent. This retains the pruned
190: % node's color characteristics for later averaging.
191: %
192: % For each node, n2 pixels exist for which that node represents the
193: % smallest volume in RGB space containing those pixel's colors. When n2
194: % > 0 the node will uniquely define a color in the output image. At the
195: % beginning of reduction, n2 = 0 for all nodes except a the leaves of
196: % the tree which represent colors present in the input image.
197: %
198: % The other pixel count, n1, indicates the total number of colors within
199: % the cubic volume which the node represents. This includes n1 - n2
200: % pixels whose colors should be defined by nodes at a lower level in the
201: % tree.
202: %
203: % Assignment generates the output image from the pruned tree. The output
204: % image consists of two parts: (1) A color map, which is an array of
205: % color descriptions (RGB triples) for each color present in the output
206: % image; (2) A pixel array, which represents each pixel as an index
207: % into the color map array.
208: %
209: % First, the assignment phase makes one pass over the pruned color
210: % description tree to establish the image's color map. For each node
211: % with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the mean
212: % color of all pixels that classify no lower than this node. Each of
213: % these colors becomes an entry in the color map.
214: %
215: % Finally, the assignment phase reclassifies each pixel in the pruned
216: % tree to identify the deepest node containing the pixel's color. The
217: % pixel's value in the pixel array becomes the index of this node's mean
218: % color in the color map.
219: %
220: % This method is based on a similar algorithm written by Paul Raveling.
221: %
222: %
223: */
224:
225: public class ColorQuantizer {
226: public static final int MAX_NODES = 266817;
227: public static final int MAX_TREE_DEPTH = 8;
228: public static final int MAX_CHILDREN = 16;
229: public static final int MAX_RGB = 255;
230:
231: static class ClosestColor {
232: int distance;
233: int colorIndex;
234: }
235:
236: static class Node {
237: Cube cube;
238: Node parent;
239: Node children[];
240: int numChildren;
241:
242: int id;
243: int level;
244:
245: int uniqueCount;
246:
247: int totalRed;
248: int totalGreen;
249: int totalBlue;
250: int totalAlpha;
251: long quantizeError;
252:
253: int colorIndex;
254:
255: Node(Cube cube) {
256: this (cube, 0, 0, null);
257: this .parent = this ;
258: }
259:
260: Node(Cube cube, int id, int level, Node parent) {
261: this .cube = cube;
262: this .parent = parent;
263: this .id = id;
264: this .level = level;
265: this .children = new Node[MAX_CHILDREN];
266: this .numChildren = 0;
267: if (parent != null) {
268: parent.children[id] = this ;
269: parent.numChildren++;
270: }
271: cube.numNodes++;
272: }
273:
274: void pruneLevel() {
275: // Traverse any children.
276: if (numChildren > 0)
277: for (int id = 0; id < MAX_CHILDREN; id++)
278: if (children[id] != null)
279: children[id].pruneLevel();
280: if (level == cube.depth)
281: prune();
282: }
283:
284: void pruneToCubeDepth() {
285: // Traverse any children.
286: if (numChildren > 0)
287: for (int id = 0; id < MAX_CHILDREN; id++)
288: if (children[id] != null)
289: children[id].pruneToCubeDepth();
290: if (level > cube.depth)
291: prune();
292: }
293:
294: void prune() {
295: // Traverse any children.
296: if (numChildren > 0)
297: for (int id = 0; id < MAX_CHILDREN; id++)
298: if (children[id] != null)
299: children[id].prune();
300: // Merge color statistics into parent.
301: parent.uniqueCount += uniqueCount;
302: parent.totalRed += totalRed;
303: parent.totalGreen += totalGreen;
304: parent.totalBlue += totalBlue;
305: parent.totalAlpha += totalAlpha;
306: parent.children[id] = null;
307: parent.numChildren--;
308: cube.numNodes--;
309: }
310:
311: void reduce(long pruningThreshold) {
312: // Traverse any children.
313: if (numChildren > 0)
314: for (int id = 0; id < MAX_CHILDREN; id++)
315: if (children[id] != null)
316: children[id].reduce(pruningThreshold);
317: if (quantizeError <= pruningThreshold)
318: prune();
319: else {
320: // Find minimum pruning threshold.
321: if (uniqueCount > 0)
322: cube.numColors++;
323: if (quantizeError < cube.nextThreshold)
324: cube.nextThreshold = quantizeError;
325: }
326: }
327:
328: void findClosestColor(int red, int green, int blue, int alpha,
329: ClosestColor closest) {
330: // Traverse any children.
331: if (numChildren > 0)
332: for (int id = 0; id < MAX_CHILDREN; id++)
333: if (children[id] != null)
334: children[id].findClosestColor(red, green, blue,
335: alpha, closest);
336: if (uniqueCount != 0) {
337: // Determine if this color is "closest".
338: int dr = (cube.colorMap[0][colorIndex] & 0xff) - red;
339: int dg = (cube.colorMap[1][colorIndex] & 0xff) - green;
340: int db = (cube.colorMap[2][colorIndex] & 0xff) - blue;
341: int da = (cube.colorMap[3][colorIndex] & 0xff) - alpha;
342: int distance = da * da + dr * dr + dg * dg + db * db;
343: if (distance < closest.distance) {
344: closest.distance = distance;
345: closest.colorIndex = colorIndex;
346: }
347: }
348: }
349:
350: int fillColorMap(byte colorMap[][], int index) {
351: // Traverse any children.
352: if (numChildren > 0)
353: for (int id = 0; id < MAX_CHILDREN; id++)
354: if (children[id] != null)
355: index = children[id].fillColorMap(colorMap,
356: index);
357: if (uniqueCount != 0) {
358: // Colormap entry is defined by the mean color in this cube.
359: colorMap[0][index] = (byte) (totalRed / uniqueCount + 0.5);
360: colorMap[1][index] = (byte) (totalGreen / uniqueCount + 0.5);
361: colorMap[2][index] = (byte) (totalBlue / uniqueCount + 0.5);
362: colorMap[3][index] = (byte) (totalAlpha / uniqueCount + 0.5);
363: colorIndex = index++;
364: }
365: return index;
366: }
367: }
368:
369: static class Cube {
370: Node root;
371:
372: int numColors;
373: boolean addTransparency;
374: // firstColor is set to 1 when when addTransparency is true!
375: int firstColor;
376: byte colorMap[][];
377:
378: long nextThreshold;
379:
380: int numNodes;
381: int depth;
382:
383: Cube(int maxColors) {
384: this .depth = getDepth(maxColors);
385: this .numColors = 0;
386: root = new Node(this );
387: }
388:
389: int getDepth(int numColors) {
390: // Depth of color tree is: Log4(colormap size)+2.
391: int depth;
392: for (depth = 1; numColors != 0; depth++)
393: numColors >>= 2;
394: if (depth > MAX_TREE_DEPTH)
395: depth = MAX_TREE_DEPTH;
396: if (depth < 2)
397: depth = 2;
398: return depth;
399: }
400:
401: void classifyImageColors(BufferedImage image,
402: boolean alphaToBitmask) {
403: addTransparency = false;
404: firstColor = 0;
405:
406: Node node, child;
407: int x, px, y, index, level, id, count;
408: int pixel, red, green, blue, alpha;
409: int bisect, midRed, midGreen, midBlue, midAlpha;
410:
411: int width = image.getWidth();
412: int height = image.getHeight();
413:
414: // Classify the first 256 colors to a tree depth of MAX_TREE_DEPTH.
415: int levelThreshold = MAX_TREE_DEPTH;
416: // create a BufferedImage of only 1 pixel height for fetching the rows
417: // of the image in the correct format (ARGB)
418: // This speeds up things by more than factor 2, compared to the standard
419: // BufferedImage.getRGB solution
420: BufferedImage row = new BufferedImage(width, 1,
421: BufferedImage.TYPE_INT_ARGB);
422: Graphics2D g2d = row.createGraphics();
423: int pixels[] = ((DataBufferInt) row.getRaster()
424: .getDataBuffer()).getData();
425: // make sure alpha values do not add up for each row:
426: g2d.setComposite(AlphaComposite.Src);
427: // calculate scanline by scanline in order to safe memory.
428: // It also seems to run faster like that
429: for (y = 0; y < height; y++) {
430: g2d.drawImage(image, null, 0, -y);
431: // now pixels contains the rgb values of the row y!
432: if (numNodes > MAX_NODES) {
433: // Prune one level if the color tree is too large.
434: root.pruneLevel();
435: depth--;
436: }
437: for (x = 0; x < width;) {
438: pixel = pixels[x];
439: red = (pixel >> 16) & 0xff;
440: green = (pixel >> 8) & 0xff;
441: blue = (pixel >> 0) & 0xff;
442: alpha = (pixel >> 24) & 0xff;
443: if (alphaToBitmask)
444: alpha = alpha < 0x80 ? 0 : 0xff;
445:
446: // skip same pixels, but count them
447: px = x;
448: for (++x; x < width; x++)
449: if (pixels[x] != pixel)
450: break;
451: count = x - px;
452:
453: // Start at the root and descend the color cube tree.
454: if (alpha > 0) {
455: index = MAX_TREE_DEPTH - 1;
456: bisect = (MAX_RGB + 1) >> 1;
457: midRed = bisect;
458: midGreen = bisect;
459: midBlue = bisect;
460: midAlpha = bisect;
461: node = root;
462: for (level = 1; level <= levelThreshold; level++) {
463: id = (((red >> index) & 0x01) << 3
464: | ((green >> index) & 0x01) << 2
465: | ((blue >> index) & 0x01) << 1 | ((alpha >> index) & 0x01));
466: bisect >>= 1;
467: midRed += (id & 8) != 0 ? bisect : -bisect;
468: midGreen += (id & 4) != 0 ? bisect
469: : -bisect;
470: midBlue += (id & 2) != 0 ? bisect : -bisect;
471: midAlpha += (id & 1) != 0 ? bisect
472: : -bisect;
473: child = node.children[id];
474: if (child == null) {
475: // Set colors of new node to contain pixel.
476: child = new Node(this , id, level, node);
477: if (level == levelThreshold) {
478: numColors++;
479: if (numColors == 256) {
480: // More than 256 colors; classify to the
481: // cube_info.depth tree depth.
482: levelThreshold = depth;
483: root.pruneToCubeDepth();
484: }
485: }
486: }
487: // Approximate the quantization error represented by
488: // this node.
489: node = child;
490: int r = red - midRed;
491: int g = green - midGreen;
492: int b = blue - midBlue;
493: int a = alpha - midAlpha;
494: node.quantizeError += count
495: * (r * r + g * g + b * b + a * a);
496: root.quantizeError += node.quantizeError;
497: index--;
498: }
499: // Sum RGB for this leaf for later derivation of the mean
500: // cube color.
501: node.uniqueCount += count;
502: node.totalRed += count * red;
503: node.totalGreen += count * green;
504: node.totalBlue += count * blue;
505: node.totalAlpha += count * alpha;
506: } else if (!addTransparency) {
507: addTransparency = true;
508: numColors++;
509: firstColor = 1; // start at 1 as 0 will be the transparent color
510: }
511: }
512: }
513: }
514:
515: void reduceImageColors(int maxColors) {
516: nextThreshold = 0;
517: while (numColors > maxColors) {
518: long pruningThreshold = nextThreshold;
519: nextThreshold = root.quantizeError - 1;
520: numColors = firstColor;
521: root.reduce(pruningThreshold);
522: }
523: }
524:
525: BufferedImage assignImageColors(BufferedImage image,
526: boolean dither, boolean alphaToBitmask) {
527: // Allocate image colormap.
528: colorMap = new byte[4][numColors];
529: root.fillColorMap(colorMap, firstColor);
530: // create the right color model, depending on transparency settings:
531: IndexColorModel icm;
532:
533: int colorDepth = getDepth(numColors);
534: int width = image.getWidth();
535: int height = image.getHeight();
536:
537: if (alphaToBitmask) {
538: if (addTransparency) {
539: icm = new IndexColorModel(depth, numColors,
540: colorMap[0], colorMap[1], colorMap[2], 0);
541: } else {
542: icm = new IndexColorModel(depth, numColors,
543: colorMap[0], colorMap[1], colorMap[2]);
544: }
545: } else {
546: icm = new IndexColorModel(depth, numColors,
547: colorMap[0], colorMap[1], colorMap[2],
548: colorMap[3]);
549: }
550:
551: // create the indexed BufferedImage:
552: BufferedImage dest = new BufferedImage(width, height,
553: BufferedImage.TYPE_BYTE_INDEXED, icm);
554:
555: boolean firstOut = true;
556: if (dither)
557: new DiffusionFilterOp().filter(image, dest);
558: else {
559: ClosestColor closest = new ClosestColor();
560: // convert to indexed color
561: byte[] dst = ((DataBufferByte) dest.getRaster()
562: .getDataBuffer()).getData();
563:
564: // create a BufferedImage of only 1 pixel height for fetching
565: // the rows of the image in the correct format (ARGB)
566: // This speeds up things by more than factor 2, compared to the
567: // standard BufferedImage.getRGB solution
568: BufferedImage row = new BufferedImage(width, 1,
569: BufferedImage.TYPE_INT_ARGB);
570: Graphics2D g2d = row.createGraphics();
571: int pixels[] = ((DataBufferInt) row.getRaster()
572: .getDataBuffer()).getData();
573: // make sure alpha values do not add up for each row:
574: g2d.setComposite(AlphaComposite.Src);
575: // calculate scanline by scanline in order to safe memory.
576: // It also seems to run faster like that
577: Node node;
578: int x, y, i, id;
579: int pixel, red, green, blue, alpha;
580: int pos = 0;
581: for (y = 0; y < height; y++) {
582: g2d.drawImage(image, null, 0, -y);
583: // now pixels contains the rgb values of the row y!
584: // filter this row now:
585: for (x = 0; x < width;) {
586: pixel = pixels[x];
587: red = (pixel >> 16) & 0xff;
588: green = (pixel >> 8) & 0xff;
589: blue = (pixel >> 0) & 0xff;
590: alpha = (pixel >> 24) & 0xff;
591:
592: if (alphaToBitmask)
593: alpha = alpha < 128 ? 0 : 0xff;
594:
595: byte col;
596: if (alpha == 0 && addTransparency) {
597: col = 0; // transparency color is at position 0 of color map
598: } else {
599: // walk the tree to find the cube containing that
600: // color
601: node = root;
602: for (i = MAX_TREE_DEPTH - 1; i > 0; i--) {
603: id = (((red >> i) & 0x01) << 3
604: | ((green >> i) & 0x01) << 2
605: | ((blue >> i) & 0x01) << 1 | ((alpha >> i) & 0x01));
606: if (node.children[id] == null)
607: break;
608: node = node.children[id];
609: }
610:
611: // Find the closest color.
612: closest.distance = Integer.MAX_VALUE;
613: node.parent.findClosestColor(red, green,
614: blue, alpha, closest);
615: col = (byte) closest.colorIndex;
616: }
617:
618: // first color
619: dst[pos++] = col;
620:
621: // next colors the same?
622: for (++x; x < width; x++) {
623: if (pixels[x] != pixel)
624: break;
625: dst[pos++] = col;
626: }
627: }
628: }
629: }
630: return dest;
631: }
632: }
633:
634: static BufferedImage quantizeImage(BufferedImage image,
635: int maxColors, boolean dither, boolean alphaToBitmask) {
636: Cube cube = new Cube(maxColors);
637: cube.classifyImageColors(image, alphaToBitmask);
638: cube.reduceImageColors(maxColors);
639: return cube.assignImageColors(image, dither, alphaToBitmask);
640: }
641:
642: }
|