1 /*
2 * Copyright (c) 2005, 2006, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package com.sun.imageio.plugins.common;
27
28 import java.awt.Transparency;
29 import java.awt.image.BufferedImage;
30 import java.awt.image.RenderedImage;
31 import java.awt.image.ColorModel;
32 import java.awt.image.IndexColorModel;
33 import java.awt.image.Raster;
34 import java.awt.image.WritableRaster;
35 import java.awt.Color;
36 import javax.imageio.ImageTypeSpecifier;
37
38
39 /**
40 * This class implements the octree quantization method
41 * as it is described in the "Graphics Gems"
42 * (ISBN 0-12-286166-3, Chapter 4, pages 297-293)
43 */
44 public class PaletteBuilder {
45
46 /**
47 * maximum of tree depth
48 */
49 protected static final int MAXLEVEL = 8;
50
51 protected RenderedImage src;
52 protected ColorModel srcColorModel;
53 protected Raster srcRaster;
54
55 protected int requiredSize;
56
57 protected ColorNode root;
58
59 protected int numNodes;
60 protected int maxNodes;
61 protected int currLevel;
62 protected int currSize;
63
64 protected ColorNode[] reduceList;
65 protected ColorNode[] palette;
66
67 protected int transparency;
68 protected ColorNode transColor;
69
70
71 /**
72 * Creates an image representing given image
73 * {@code src} using {@code IndexColorModel}.
74 *
75 * Lossless conversion is not always possible (e.g. if number
76 * of colors in the given image exceeds maximum palette size).
77 * Result image then is an approximation constructed by octree
78 * quantization method.
79 *
80 * @exception IllegalArgumentException if {@code src} is
81 * {@code null}.
82 *
83 * @exception UnsupportedOperationException if implemented method
84 * is unable to create approximation of {@code src}
85 * and {@code canCreatePalette} returns {@code false}.
86 *
87 * @see createIndexColorModel
88 *
89 * @see canCreatePalette
90 *
91 */
92 public static RenderedImage createIndexedImage(RenderedImage src) {
93 PaletteBuilder pb = new PaletteBuilder(src);
94 pb.buildPalette();
95 return pb.getIndexedImage();
96 }
97
98 /**
99 * Creates an palette representing colors from given image
100 * {@code img}. If number of colors in the given image exceeds
101 * maximum palette size closest colors would be merged.
102 *
103 * @exception IllegalArgumentException if {@code img} is
104 * {@code null}.
105 *
106 * @exception UnsupportedOperationException if implemented method
107 * is unable to create approximation of {@code img}
108 * and {@code canCreatePalette} returns {@code false}.
109 *
110 * @see createIndexedImage
111 *
112 * @see canCreatePalette
113 *
114 */
115 public static IndexColorModel createIndexColorModel(RenderedImage img) {
116 PaletteBuilder pb = new PaletteBuilder(img);
117 pb.buildPalette();
118 return pb.getIndexColorModel();
119 }
120
121 /**
122 * Returns {@code true} if PaletteBuilder is able to create
123 * palette for given image type.
124 *
125 * @param type an instance of {@code ImageTypeSpecifier} to be
126 * indexed.
127 *
128 * @return {@code true} if the {@code PaletteBuilder}
129 * is likely to be able to create palette for this image type.
130 *
131 * @exception IllegalArgumentException if {@code type}
132 * is {@code null}.
133 */
134 public static boolean canCreatePalette(ImageTypeSpecifier type) {
135 if (type == null) {
136 throw new IllegalArgumentException("type == null");
137 }
138 return true;
139 }
140
141 /**
142 * Returns {@code true} if PaletteBuilder is able to create
143 * palette for given rendered image.
144 *
145 * @param image an instance of {@code RenderedImage} to be
146 * indexed.
147 *
148 * @return {@code true} if the {@code PaletteBuilder}
149 * is likely to be able to create palette for this image type.
150 *
151 * @exception IllegalArgumentException if {@code image}
152 * is {@code null}.
153 */
154 public static boolean canCreatePalette(RenderedImage image) {
155 if (image == null) {
156 throw new IllegalArgumentException("image == null");
157 }
158 ImageTypeSpecifier type = new ImageTypeSpecifier(image);
159 return canCreatePalette(type);
160 }
161
162 protected RenderedImage getIndexedImage() {
163 IndexColorModel icm = getIndexColorModel();
164
165 BufferedImage dst =
166 new BufferedImage(src.getWidth(), src.getHeight(),
167 BufferedImage.TYPE_BYTE_INDEXED, icm);
168
169 WritableRaster wr = dst.getRaster();
170 for (int y =0; y < dst.getHeight(); y++) {
171 for (int x = 0; x < dst.getWidth(); x++) {
172 Color aColor = getSrcColor(x,y);
173 wr.setSample(x, y, 0, findColorIndex(root, aColor));
174 }
175 }
176
177 return dst;
178 }
179
180
181 protected PaletteBuilder(RenderedImage src) {
182 this(src, 256);
183 }
184
185 protected PaletteBuilder(RenderedImage src, int size) {
186 this.src = src;
187 this.srcColorModel = src.getColorModel();
188 this.srcRaster = src.getData();
189
190 this.transparency =
191 srcColorModel.getTransparency();
192
193 this.requiredSize = size;
194 }
195
196 private Color getSrcColor(int x, int y) {
197 int argb = srcColorModel.getRGB(srcRaster.getDataElements(x, y, null));
198 return new Color(argb, transparency != Transparency.OPAQUE);
199 }
200
201 protected int findColorIndex(ColorNode aNode, Color aColor) {
202 if (transparency != Transparency.OPAQUE &&
203 aColor.getAlpha() != 0xff)
204 {
205 return 0; // default transparnt pixel
206 }
207
208 if (aNode.isLeaf) {
209 return aNode.paletteIndex;
210 } else {
211 int childIndex = getBranchIndex(aColor, aNode.level);
212
213 return findColorIndex(aNode.children[childIndex], aColor);
214 }
215 }
216
217 protected void buildPalette() {
218 reduceList = new ColorNode[MAXLEVEL + 1];
219 for (int i = 0; i < reduceList.length; i++) {
220 reduceList[i] = null;
221 }
222
223 numNodes = 0;
224 maxNodes = 0;
225 root = null;
226 currSize = 0;
227 currLevel = MAXLEVEL;
228
229 /*
230 from the book
231
232 */
233
234 int w = src.getWidth();
235 int h = src.getHeight();
236 for (int y = 0; y < h; y++) {
237 for (int x = 0; x < w; x++) {
238
239 Color aColor = getSrcColor(w - x - 1, h - y - 1);
240 /*
241 * If transparency of given image is not opaque we assume all
242 * colors with alpha less than 1.0 as fully transparent.
243 */
244 if (transparency != Transparency.OPAQUE &&
245 aColor.getAlpha() != 0xff)
246 {
247 if (transColor == null) {
248 this.requiredSize --; // one slot for transparent color
249
250 transColor = new ColorNode();
251 transColor.isLeaf = true;
252 }
253 transColor = insertNode(transColor, aColor, 0);
254 } else {
255 root = insertNode(root, aColor, 0);
256 }
257 if (currSize > requiredSize) {
258 reduceTree();
259 }
260 }
261 }
262 }
263
264 protected ColorNode insertNode(ColorNode aNode, Color aColor, int aLevel) {
265
266 if (aNode == null) {
267 aNode = new ColorNode();
268 numNodes++;
269 if (numNodes > maxNodes) {
270 maxNodes = numNodes;
271 }
272 aNode.level = aLevel;
273 aNode.isLeaf = (aLevel > MAXLEVEL);
274 if (aNode.isLeaf) {
275 currSize++;
276 }
277 }
278 aNode.colorCount++;
279 aNode.red += aColor.getRed();
280 aNode.green += aColor.getGreen();
281 aNode.blue += aColor.getBlue();
282
283 if (!aNode.isLeaf) {
284 int branchIndex = getBranchIndex(aColor, aLevel);
285 if (aNode.children[branchIndex] == null) {
286 aNode.childCount++;
287 if (aNode.childCount == 2) {
288 aNode.nextReducible = reduceList[aLevel];
289 reduceList[aLevel] = aNode;
290 }
291 }
292 aNode.children[branchIndex] =
293 insertNode(aNode.children[branchIndex], aColor, aLevel + 1);
294 }
295 return aNode;
296 }
297
298 protected IndexColorModel getIndexColorModel() {
299 int size = currSize;
300 if (transColor != null) {
301 size ++; // we need place for transparent color;
302 }
303
304 byte[] red = new byte[size];
305 byte[] green = new byte[size];
306 byte[] blue = new byte[size];
307
308 int index = 0;
309 palette = new ColorNode[size];
310 if (transColor != null) {
311 index ++;
312 }
313
314 if (root != null) {
315 findPaletteEntry(root, index, red, green, blue);
316 }
317
318 IndexColorModel icm = null;
319 if (transColor != null) {
320 icm = new IndexColorModel(8, size, red, green, blue, 0);
321 } else {
322 icm = new IndexColorModel(8, currSize, red, green, blue);
323 }
324 return icm;
325 }
326
327 protected int findPaletteEntry(ColorNode aNode, int index,
328 byte[] red, byte[] green, byte[] blue)
329 {
330 if (aNode.isLeaf) {
331 red[index] = (byte)(aNode.red/aNode.colorCount);
332 green[index] = (byte)(aNode.green/aNode.colorCount);
333 blue[index] = (byte)(aNode.blue/aNode.colorCount);
334 aNode.paletteIndex = index;
335
336 palette[index] = aNode;
337
338 index++;
339 } else {
340 for (int i = 0; i < 8; i++) {
341 if (aNode.children[i] != null) {
342 index = findPaletteEntry(aNode.children[i], index,
343 red, green, blue);
344 }
345 }
346 }
347 return index;
348 }
349
350 protected int getBranchIndex(Color aColor, int aLevel) {
351 if (aLevel > MAXLEVEL || aLevel < 0) {
352 throw new IllegalArgumentException("Invalid octree node depth: " +
353 aLevel);
354 }
355
356 int shift = MAXLEVEL - aLevel;
357 int red_index = 0x1 & ((0xff & aColor.getRed()) >> shift);
358 int green_index = 0x1 & ((0xff & aColor.getGreen()) >> shift);
359 int blue_index = 0x1 & ((0xff & aColor.getBlue()) >> shift);
360 int index = (red_index << 2) | (green_index << 1) | blue_index;
361 return index;
362 }
363
364 protected void reduceTree() {
365 int level = reduceList.length - 1;
366 while (reduceList[level] == null && level >= 0) {
367 level--;
368 }
369
370 ColorNode thisNode = reduceList[level];
371 if (thisNode == null) {
372 // nothing to reduce
373 return;
374 }
375
376 // look for element with lower color count
377 ColorNode pList = thisNode;
378 int minColorCount = pList.colorCount;
379
380 int cnt = 1;
381 while (pList.nextReducible != null) {
382 if (minColorCount > pList.nextReducible.colorCount) {
383 thisNode = pList;
384 minColorCount = pList.colorCount;
385 }
386 pList = pList.nextReducible;
387 cnt++;
388 }
389
390 // save pointer to first reducible node
391 // NB: current color count for node could be changed in future
392 if (thisNode == reduceList[level]) {
393 reduceList[level] = thisNode.nextReducible;
394 } else {
395 pList = thisNode.nextReducible; // we need to process it
396 thisNode.nextReducible = pList.nextReducible;
397 thisNode = pList;
398 }
399
400 if (thisNode.isLeaf) {
401 return;
402 }
403
404 // reduce node
405 int leafChildCount = thisNode.getLeafChildCount();
406 thisNode.isLeaf = true;
407 currSize -= (leafChildCount - 1);
408 int aDepth = thisNode.level;
409 for (int i = 0; i < 8; i++) {
410 thisNode.children[i] = freeTree(thisNode.children[i]);
411 }
412 thisNode.childCount = 0;
413 }
414
415 protected ColorNode freeTree(ColorNode aNode) {
416 if (aNode == null) {
417 return null;
418 }
419 for (int i = 0; i < 8; i++) {
420 aNode.children[i] = freeTree(aNode.children[i]);
421 }
422
423 numNodes--;
424 return null;
425 }
426
427 /**
428 * The node of color tree.
429 */
430 protected class ColorNode {
431 public boolean isLeaf;
432 public int childCount;
433 ColorNode[] children;
434
435 public int colorCount;
436 public long red;
437 public long blue;
438 public long green;
439
440 public int paletteIndex;
441
442 public int level;
443 ColorNode nextReducible;
444
445 public ColorNode() {
446 isLeaf = false;
447 level = 0;
448 childCount = 0;
449 children = new ColorNode[8];
450 for (int i = 0; i < 8; i++) {
451 children[i] = null;
452 }
453
454 colorCount = 0;
455 red = green = blue = 0;
456
457 paletteIndex = 0;
458 }
459
460 public int getLeafChildCount() {
461 if (isLeaf) {
462 return 0;
463 }
464 int cnt = 0;
465 for (int i = 0; i < children.length; i++) {
466 if (children[i] != null) {
467 if (children[i].isLeaf) {
468 cnt ++;
469 } else {
470 cnt += children[i].getLeafChildCount();
471 }
472 }
473 }
474 return cnt;
475 }
476
477 public int getRGB() {
478 int r = (int)red/colorCount;
479 int g = (int)green/colorCount;
480 int b = (int)blue/colorCount;
481
482 int c = 0xff << 24 | (0xff&r) << 16 | (0xff&g) << 8 | (0xff&b);
483 return c;
484 }
485 }
486 }