001: /*
002: * $RCSfile: PaletteBuilder.java,v $
003: *
004: * Copyright (c) 2005 Sun Microsystems, Inc. All rights reserved.
005: *
006: * Redistribution and use in source and binary forms, with or without
007: * modification, are permitted provided that the following conditions
008: * are met:
009: *
010: * - Redistribution of source code must retain the above copyright
011: * notice, this list of conditions and the following disclaimer.
012: *
013: * - Redistribution in binary form must reproduce the above copyright
014: * notice, this list of conditions and the following disclaimer in
015: * the documentation and/or other materials provided with the
016: * distribution.
017: *
018: * Neither the name of Sun Microsystems, Inc. or the names of
019: * contributors may be used to endorse or promote products derived
020: * from this software without specific prior written permission.
021: *
022: * This software is provided "AS IS," without a warranty of any
023: * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND
024: * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY,
025: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY
026: * EXCLUDED. SUN MIDROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL
027: * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF
028: * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
029: * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR
030: * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL,
031: * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND
032: * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR
033: * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
034: * POSSIBILITY OF SUCH DAMAGES.
035: *
036: * You acknowledge that this software is not designed or intended for
037: * use in the design, construction, operation or maintenance of any
038: * nuclear facility.
039: *
040: * $Revision: 1.3 $
041: * $Date: 2007/08/31 00:06:00 $
042: * $State: Exp $
043: */
044:
045: package com.sun.media.imageioimpl.common;
046:
047: import java.awt.Transparency;
048: import java.awt.image.BufferedImage;
049: import java.awt.image.RenderedImage;
050: import java.awt.image.ColorModel;
051: import java.awt.image.IndexColorModel;
052: import java.awt.image.Raster;
053: import java.awt.image.WritableRaster;
054: import java.awt.Color;
055: import javax.imageio.ImageTypeSpecifier;
056:
057: /**
058: * This class implements the octree quantization method
059: * as it is described in the "Graphics Gems"
060: * (ISBN 0-12-286166-3, Chapter 4, pages 297-293)
061: */
062: public class PaletteBuilder {
063:
064: /**
065: * maximum of tree depth
066: */
067: protected static final int MAXLEVEL = 8;
068:
069: protected RenderedImage src;
070: protected ColorModel srcColorModel;
071: protected Raster srcRaster;
072:
073: protected int requiredSize;
074:
075: protected ColorNode root;
076:
077: protected int numNodes;
078: protected int maxNodes;
079: protected int currLevel;
080: protected int currSize;
081:
082: protected ColorNode[] reduceList;
083: protected ColorNode[] palette;
084:
085: protected int transparency;
086: protected ColorNode transColor;
087:
088: /**
089: * Creates an image representing given image
090: * <code>src</code> using <code>IndexColorModel<code>.
091: *
092: * Lossless conversion is not always possible (e.g. if number
093: * of colors in the given image exceeds maximum palette size).
094: * Result image then is an approximation constructed by octree
095: * quantization method.
096: *
097: * @exception IllegalArgumentException if <code>src</code> is
098: * <code>null</code>.
099: *
100: * @exception UnsupportedOperationException if implemented method
101: * is unable to create approximation of <code>src</code>
102: * and <code>canCreatePalette</code> returns <code>false</code>.
103: *
104: * @see createIndexColorModel
105: *
106: * @see canCreatePalette
107: *
108: */
109: public static RenderedImage createIndexedImage(RenderedImage src) {
110: PaletteBuilder pb = new PaletteBuilder(src);
111: pb.buildPalette();
112: return pb.getIndexedImage();
113: }
114:
115: /**
116: * Creates an palette representing colors from given image
117: * <code>img</code>. If number of colors in the given image exceeds
118: * maximum palette size closest colors would be merged.
119: *
120: * @exception IllegalArgumentException if <code>img</code> is
121: * <code>null</code>.
122: *
123: * @exception UnsupportedOperationException if implemented method
124: * is unable to create approximation of <code>img</code>
125: * and <code>canCreatePalette</code> returns <code>false</code>.
126: *
127: * @see createIndexedImage
128: *
129: * @see canCreatePalette
130: *
131: */
132: public static IndexColorModel createIndexColorModel(
133: RenderedImage img) {
134: PaletteBuilder pb = new PaletteBuilder(img);
135: pb.buildPalette();
136: return pb.getIndexColorModel();
137: }
138:
139: /**
140: * Returns <code>true</code> if PaletteBuilder is able to create
141: * palette for given image type.
142: *
143: * @param type an instance of <code>ImageTypeSpecifier</code> to be
144: * indexed.
145: *
146: * @return <code>true</code> if the <code>PaletteBuilder</code>
147: * is likely to be able to create palette for this image type.
148: *
149: * @exception IllegalArgumentException if <code>type</code>
150: * is <code>null</code>.
151: */
152: public static boolean canCreatePalette(ImageTypeSpecifier type) {
153: if (type == null) {
154: throw new IllegalArgumentException("type == null");
155: }
156: return true;
157: }
158:
159: /**
160: * Returns <code>true</code> if PaletteBuilder is able to create
161: * palette for given rendered image.
162: *
163: * @param image an instance of <code>RenderedImage</code> to be
164: * indexed.
165: *
166: * @return <code>true</code> if the <code>PaletteBuilder</code>
167: * is likely to be able to create palette for this image type.
168: *
169: * @exception IllegalArgumentException if <code>image</code>
170: * is <code>null</code>.
171: */
172: public static boolean canCreatePalette(RenderedImage image) {
173: if (image == null) {
174: throw new IllegalArgumentException("image == null");
175: }
176: ImageTypeSpecifier type = new ImageTypeSpecifier(image);
177: return canCreatePalette(type);
178: }
179:
180: protected RenderedImage getIndexedImage() {
181: IndexColorModel icm = getIndexColorModel();
182:
183: BufferedImage dst = new BufferedImage(src.getWidth(), src
184: .getHeight(), BufferedImage.TYPE_BYTE_INDEXED, icm);
185:
186: WritableRaster wr = dst.getRaster();
187: int minX = src.getMinX();
188: int minY = src.getMinY();
189: for (int y = 0; y < dst.getHeight(); y++) {
190: for (int x = 0; x < dst.getWidth(); x++) {
191: Color aColor = getSrcColor(x + minX, y + minY);
192: wr.setSample(x, y, 0, findColorIndex(root, aColor));
193: }
194: }
195:
196: return dst;
197: }
198:
199: protected PaletteBuilder(RenderedImage src) {
200: this (src, 256);
201: }
202:
203: protected PaletteBuilder(RenderedImage src, int size) {
204: this .src = src;
205: this .srcColorModel = src.getColorModel();
206: this .srcRaster = src.getData();
207:
208: this .transparency = srcColorModel.getTransparency();
209:
210: if (transparency != Transparency.OPAQUE) {
211: this .requiredSize = size - 1;
212: transColor = new ColorNode();
213: transColor.isLeaf = true;
214: } else {
215: this .requiredSize = size;
216: }
217: }
218:
219: private Color getSrcColor(int x, int y) {
220: int argb = srcColorModel.getRGB(srcRaster.getDataElements(x, y,
221: null));
222: return new Color(argb, transparency != Transparency.OPAQUE);
223: }
224:
225: protected int findColorIndex(ColorNode aNode, Color aColor) {
226: if (transparency != Transparency.OPAQUE
227: && aColor.getAlpha() != 0xff) {
228: return 0; // default transparnt pixel
229: }
230:
231: if (aNode.isLeaf) {
232: return aNode.paletteIndex;
233: } else {
234: int childIndex = getBranchIndex(aColor, aNode.level);
235:
236: return findColorIndex(aNode.children[childIndex], aColor);
237: }
238: }
239:
240: protected void buildPalette() {
241: reduceList = new ColorNode[MAXLEVEL + 1];
242: for (int i = 0; i < reduceList.length; i++) {
243: reduceList[i] = null;
244: }
245:
246: numNodes = 0;
247: maxNodes = 0;
248: root = null;
249: currSize = 0;
250: currLevel = MAXLEVEL;
251:
252: /*
253: from the book
254:
255: */
256:
257: int w = src.getWidth();
258: int h = src.getHeight();
259: int minX = src.getMinX();
260: int minY = src.getMinY();
261: for (int y = 0; y < h; y++) {
262: for (int x = 0; x < w; x++) {
263:
264: Color aColor = getSrcColor(w - x + minX - 1, h - y
265: + minY - 1);
266: /*
267: * If transparency of given image is not opaque we assume all
268: * colors with alpha less than 1.0 as fully transparent.
269: */
270: if (transparency != Transparency.OPAQUE
271: && aColor.getAlpha() != 0xff) {
272: transColor = insertNode(transColor, aColor, 0);
273: } else {
274: root = insertNode(root, aColor, 0);
275: }
276: if (currSize > requiredSize) {
277: reduceTree();
278: }
279: }
280: }
281: }
282:
283: protected ColorNode insertNode(ColorNode aNode, Color aColor,
284: int aLevel) {
285:
286: if (aNode == null) {
287: aNode = new ColorNode();
288: numNodes++;
289: if (numNodes > maxNodes) {
290: maxNodes = numNodes;
291: }
292: aNode.level = aLevel;
293: aNode.isLeaf = (aLevel > MAXLEVEL);
294: if (aNode.isLeaf) {
295: currSize++;
296: }
297: }
298: aNode.colorCount++;
299: aNode.red += aColor.getRed();
300: aNode.green += aColor.getGreen();
301: aNode.blue += aColor.getBlue();
302:
303: if (!aNode.isLeaf) {
304: int branchIndex = getBranchIndex(aColor, aLevel);
305: if (aNode.children[branchIndex] == null) {
306: aNode.childCount++;
307: if (aNode.childCount == 2) {
308: aNode.nextReducible = reduceList[aLevel];
309: reduceList[aLevel] = aNode;
310: }
311: }
312: aNode.children[branchIndex] = insertNode(
313: aNode.children[branchIndex], aColor, aLevel + 1);
314: }
315: return aNode;
316: }
317:
318: protected IndexColorModel getIndexColorModel() {
319: int size = currSize;
320: if (transparency != Transparency.OPAQUE) {
321: size++; // we need place for transparent color;
322: }
323:
324: byte[] red = new byte[size];
325: byte[] green = new byte[size];
326: byte[] blue = new byte[size];
327:
328: int index = 0;
329: palette = new ColorNode[size];
330: if (transparency != Transparency.OPAQUE) {
331: index++;
332: }
333:
334: int lastIndex = findPaletteEntry(root, index, red, green, blue);
335:
336: IndexColorModel icm = null;
337: if (transparency != Transparency.OPAQUE) {
338: icm = new IndexColorModel(8, size, red, green, blue, 0);
339: } else {
340: icm = new IndexColorModel(8, currSize, red, green, blue);
341: }
342: return icm;
343: }
344:
345: protected int findPaletteEntry(ColorNode aNode, int index,
346: byte[] red, byte[] green, byte[] blue) {
347: if (aNode.isLeaf) {
348: red[index] = (byte) (aNode.red / aNode.colorCount);
349: green[index] = (byte) (aNode.green / aNode.colorCount);
350: blue[index] = (byte) (aNode.blue / aNode.colorCount);
351: aNode.paletteIndex = index;
352:
353: palette[index] = aNode;
354:
355: index++;
356: } else {
357: for (int i = 0; i < 8; i++) {
358: if (aNode.children[i] != null) {
359: index = findPaletteEntry(aNode.children[i], index,
360: red, green, blue);
361: }
362: }
363: }
364: return index;
365: }
366:
367: protected int getBranchIndex(Color aColor, int aLevel) {
368: if (aLevel > MAXLEVEL || aLevel < 0) {
369: throw new IllegalArgumentException(
370: "Invalid octree node depth: " + aLevel);
371: }
372:
373: int shift = MAXLEVEL - aLevel;
374: int red_index = 0x1 & ((0xff & aColor.getRed()) >> shift);
375: int green_index = 0x1 & ((0xff & aColor.getGreen()) >> shift);
376: int blue_index = 0x1 & ((0xff & aColor.getBlue()) >> shift);
377: int index = (red_index << 2) | (green_index << 1) | blue_index;
378: return index;
379: }
380:
381: protected void reduceTree() {
382: int level = reduceList.length - 1;
383: while (reduceList[level] == null && level >= 0) {
384: level--;
385: }
386:
387: ColorNode this Node = reduceList[level];
388: if (this Node == null) {
389: // nothing to reduce
390: return;
391: }
392:
393: // look for element with lower color count
394: ColorNode pList = this Node;
395: int minColorCount = pList.colorCount;
396:
397: int cnt = 1;
398: while (pList.nextReducible != null) {
399: if (minColorCount > pList.nextReducible.colorCount) {
400: this Node = pList;
401: minColorCount = pList.colorCount;
402: }
403: pList = pList.nextReducible;
404: cnt++;
405: }
406:
407: // save pointer to first reducible node
408: // NB: current color count for node could be changed in future
409: if (this Node == reduceList[level]) {
410: reduceList[level] = this Node.nextReducible;
411: } else {
412: pList = this Node.nextReducible; // we need to process it
413: this Node.nextReducible = pList.nextReducible;
414: this Node = pList;
415: }
416:
417: if (this Node.isLeaf) {
418: return;
419: }
420:
421: // reduce node
422: int leafChildCount = this Node.getLeafChildCount();
423: this Node.isLeaf = true;
424: currSize -= (leafChildCount - 1);
425: int aDepth = this Node.level;
426: for (int i = 0; i < 8; i++) {
427: this Node.children[i] = freeTree(this Node.children[i]);
428: }
429: this Node.childCount = 0;
430: }
431:
432: protected ColorNode freeTree(ColorNode aNode) {
433: if (aNode == null) {
434: return null;
435: }
436: for (int i = 0; i < 8; i++) {
437: aNode.children[i] = freeTree(aNode.children[i]);
438: }
439:
440: numNodes--;
441: return null;
442: }
443:
444: /**
445: * The node of color tree.
446: */
447: protected class ColorNode {
448: public boolean isLeaf;
449: public int childCount;
450: ColorNode[] children;
451:
452: public int colorCount;
453: public long red;
454: public long blue;
455: public long green;
456:
457: public int paletteIndex;
458:
459: public int level;
460: ColorNode nextReducible;
461:
462: public ColorNode() {
463: isLeaf = false;
464: level = 0;
465: childCount = 0;
466: children = new ColorNode[8];
467: for (int i = 0; i < 8; i++) {
468: children[i] = null;
469: }
470:
471: colorCount = 0;
472: red = green = blue = 0;
473:
474: paletteIndex = 0;
475: }
476:
477: public int getLeafChildCount() {
478: if (isLeaf) {
479: return 0;
480: }
481: int cnt = 0;
482: for (int i = 0; i < children.length; i++) {
483: if (children[i] != null) {
484: if (children[i].isLeaf) {
485: cnt++;
486: } else {
487: cnt += children[i].getLeafChildCount();
488: }
489: }
490: }
491: return cnt;
492: }
493:
494: public int getRGB() {
495: int r = (int) red / colorCount;
496: int g = (int) green / colorCount;
497: int b = (int) blue / colorCount;
498:
499: int c = 0xff << 24 | (0xff & r) << 16 | (0xff & g) << 8
500: | (0xff & b);
501: return c;
502: }
503: }
504: }
|