1 /*
2 * Copyright (c) 2005, 2017, 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 * @see #canCreatePalette
89 */
90 public static RenderedImage createIndexedImage(RenderedImage src) {
91 PaletteBuilder pb = new PaletteBuilder(src);
92 pb.buildPalette();
93 return pb.getIndexedImage();
94 }
95
96 /**
97 * Creates an palette representing colors from given image
98 * {@code img}. If number of colors in the given image exceeds
99 * maximum palette size closest colors would be merged.
100 *
101 * @exception IllegalArgumentException if {@code img} is
102 * {@code null}.
103 *
104 * @exception UnsupportedOperationException if implemented method
105 * is unable to create approximation of {@code img}
106 * and {@code canCreatePalette} returns {@code false}.
107 *
108 * @see #createIndexedImage
109 * @see #canCreatePalette
110 */
111 public static IndexColorModel createIndexColorModel(RenderedImage img) {
112 PaletteBuilder pb = new PaletteBuilder(img);
113 pb.buildPalette();
114 return pb.getIndexColorModel();
115 }
116
117 /**
118 * Returns {@code true} if PaletteBuilder is able to create
119 * palette for given image type.
120 *
121 * @param type an instance of {@code ImageTypeSpecifier} to be
122 * indexed.
123 *
124 * @return {@code true} if the {@code PaletteBuilder}
125 * is likely to be able to create palette for this image type.
126 *
127 * @exception IllegalArgumentException if {@code type}
128 * is {@code null}.
129 */
130 public static boolean canCreatePalette(ImageTypeSpecifier type) {
131 if (type == null) {
132 throw new IllegalArgumentException("type == null");
133 }
134 return true;
135 }
136
137 /**
138 * Returns {@code true} if PaletteBuilder is able to create
139 * palette for given rendered image.
140 *
141 * @param image an instance of {@code RenderedImage} to be
142 * indexed.
143 *
144 * @return {@code true} if the {@code PaletteBuilder}
145 * is likely to be able to create palette for this image type.
146 *
147 * @exception IllegalArgumentException if {@code image}
148 * is {@code null}.
149 */
150 public static boolean canCreatePalette(RenderedImage image) {
151 if (image == null) {
152 throw new IllegalArgumentException("image == null");
153 }
154 ImageTypeSpecifier type = new ImageTypeSpecifier(image);
155 return canCreatePalette(type);
156 }
157
158 protected RenderedImage getIndexedImage() {
159 IndexColorModel icm = getIndexColorModel();
160
161 BufferedImage dst =
162 new BufferedImage(src.getWidth(), src.getHeight(),
163 BufferedImage.TYPE_BYTE_INDEXED, icm);
164
165 WritableRaster wr = dst.getRaster();
166 for (int y =0; y < dst.getHeight(); y++) {
167 for (int x = 0; x < dst.getWidth(); x++) {
168 Color aColor = getSrcColor(x,y);
169 wr.setSample(x, y, 0, findColorIndex(root, aColor));
170 }
171 }
172
173 return dst;
174 }
175
176
177 protected PaletteBuilder(RenderedImage src) {
178 this(src, 256);
179 }
180
181 protected PaletteBuilder(RenderedImage src, int size) {
182 this.src = src;
183 this.srcColorModel = src.getColorModel();
184 this.srcRaster = src.getData();
185
186 this.transparency =
187 srcColorModel.getTransparency();
188
189 this.requiredSize = size;
190 }
191
192 private Color getSrcColor(int x, int y) {
193 int argb = srcColorModel.getRGB(srcRaster.getDataElements(x, y, null));
194 return new Color(argb, transparency != Transparency.OPAQUE);
195 }
196
197 protected int findColorIndex(ColorNode aNode, Color aColor) {
198 if (transparency != Transparency.OPAQUE &&
199 aColor.getAlpha() != 0xff)
200 {
201 return 0; // default transparnt pixel
202 }
203
204 if (aNode.isLeaf) {
205 return aNode.paletteIndex;
206 } else {
207 int childIndex = getBranchIndex(aColor, aNode.level);
208
209 return findColorIndex(aNode.children[childIndex], aColor);
210 }
211 }
212
213 protected void buildPalette() {
214 reduceList = new ColorNode[MAXLEVEL + 1];
215 for (int i = 0; i < reduceList.length; i++) {
216 reduceList[i] = null;
217 }
218
219 numNodes = 0;
220 maxNodes = 0;
221 root = null;
222 currSize = 0;
223 currLevel = MAXLEVEL;
224
225 /*
226 from the book
227
228 */
229
230 int w = src.getWidth();
231 int h = src.getHeight();
232 for (int y = 0; y < h; y++) {
233 for (int x = 0; x < w; x++) {
234
235 Color aColor = getSrcColor(w - x - 1, h - y - 1);
236 /*
237 * If transparency of given image is not opaque we assume all
238 * colors with alpha less than 1.0 as fully transparent.
239 */
240 if (transparency != Transparency.OPAQUE &&
241 aColor.getAlpha() != 0xff)
242 {
243 if (transColor == null) {
244 this.requiredSize --; // one slot for transparent color
245
246 transColor = new ColorNode();
247 transColor.isLeaf = true;
248 }
249 transColor = insertNode(transColor, aColor, 0);
250 } else {
251 root = insertNode(root, aColor, 0);
252 }
253 if (currSize > requiredSize) {
254 reduceTree();
255 }
256 }
257 }
258 }
259
260 protected ColorNode insertNode(ColorNode aNode, Color aColor, int aLevel) {
261
262 if (aNode == null) {
263 aNode = new ColorNode();
264 numNodes++;
265 if (numNodes > maxNodes) {
266 maxNodes = numNodes;
267 }
268 aNode.level = aLevel;
269 aNode.isLeaf = (aLevel > MAXLEVEL);
270 if (aNode.isLeaf) {
271 currSize++;
272 }
273 }
274 aNode.colorCount++;
275 aNode.red += aColor.getRed();
276 aNode.green += aColor.getGreen();
277 aNode.blue += aColor.getBlue();
278
279 if (!aNode.isLeaf) {
280 int branchIndex = getBranchIndex(aColor, aLevel);
281 if (aNode.children[branchIndex] == null) {
282 aNode.childCount++;
283 if (aNode.childCount == 2) {
284 aNode.nextReducible = reduceList[aLevel];
285 reduceList[aLevel] = aNode;
286 }
287 }
288 aNode.children[branchIndex] =
289 insertNode(aNode.children[branchIndex], aColor, aLevel + 1);
290 }
291 return aNode;
292 }
293
294 protected IndexColorModel getIndexColorModel() {
295 int size = currSize;
296 if (transColor != null) {
297 size ++; // we need place for transparent color;
298 }
299
300 byte[] red = new byte[size];
301 byte[] green = new byte[size];
302 byte[] blue = new byte[size];
303
304 int index = 0;
305 palette = new ColorNode[size];
306 if (transColor != null) {
307 index ++;
308 }
309
310 if (root != null) {
311 findPaletteEntry(root, index, red, green, blue);
312 }
313
314 IndexColorModel icm = null;
315 if (transColor != null) {
316 icm = new IndexColorModel(8, size, red, green, blue, 0);
317 } else {
318 icm = new IndexColorModel(8, currSize, red, green, blue);
319 }
320 return icm;
321 }
322
323 protected int findPaletteEntry(ColorNode aNode, int index,
324 byte[] red, byte[] green, byte[] blue)
325 {
326 if (aNode.isLeaf) {
327 red[index] = (byte)(aNode.red/aNode.colorCount);
328 green[index] = (byte)(aNode.green/aNode.colorCount);
329 blue[index] = (byte)(aNode.blue/aNode.colorCount);
330 aNode.paletteIndex = index;
331
332 palette[index] = aNode;
333
334 index++;
335 } else {
336 for (int i = 0; i < 8; i++) {
337 if (aNode.children[i] != null) {
338 index = findPaletteEntry(aNode.children[i], index,
339 red, green, blue);
340 }
341 }
342 }
343 return index;
344 }
345
346 protected int getBranchIndex(Color aColor, int aLevel) {
347 if (aLevel > MAXLEVEL || aLevel < 0) {
348 throw new IllegalArgumentException("Invalid octree node depth: " +
349 aLevel);
350 }
351
352 int shift = MAXLEVEL - aLevel;
353 int red_index = 0x1 & ((0xff & aColor.getRed()) >> shift);
354 int green_index = 0x1 & ((0xff & aColor.getGreen()) >> shift);
355 int blue_index = 0x1 & ((0xff & aColor.getBlue()) >> shift);
356 int index = (red_index << 2) | (green_index << 1) | blue_index;
357 return index;
358 }
359
360 protected void reduceTree() {
361 int level = reduceList.length - 1;
362 while (reduceList[level] == null && level >= 0) {
363 level--;
364 }
365
366 ColorNode thisNode = reduceList[level];
367 if (thisNode == null) {
368 // nothing to reduce
369 return;
370 }
371
372 // look for element with lower color count
373 ColorNode pList = thisNode;
374 int minColorCount = pList.colorCount;
375
376 int cnt = 1;
377 while (pList.nextReducible != null) {
378 if (minColorCount > pList.nextReducible.colorCount) {
379 thisNode = pList;
380 minColorCount = pList.colorCount;
381 }
382 pList = pList.nextReducible;
383 cnt++;
384 }
385
386 // save pointer to first reducible node
387 // NB: current color count for node could be changed in future
388 if (thisNode == reduceList[level]) {
389 reduceList[level] = thisNode.nextReducible;
390 } else {
391 pList = thisNode.nextReducible; // we need to process it
392 thisNode.nextReducible = pList.nextReducible;
393 thisNode = pList;
394 }
395
396 if (thisNode.isLeaf) {
397 return;
398 }
399
400 // reduce node
401 int leafChildCount = thisNode.getLeafChildCount();
402 thisNode.isLeaf = true;
403 currSize -= (leafChildCount - 1);
404 int aDepth = thisNode.level;
405 for (int i = 0; i < 8; i++) {
406 thisNode.children[i] = freeTree(thisNode.children[i]);
407 }
408 thisNode.childCount = 0;
409 }
410
411 protected ColorNode freeTree(ColorNode aNode) {
412 if (aNode == null) {
413 return null;
414 }
415 for (int i = 0; i < 8; i++) {
416 aNode.children[i] = freeTree(aNode.children[i]);
417 }
418
419 numNodes--;
420 return null;
421 }
422
423 /**
424 * The node of color tree.
425 */
426 protected class ColorNode {
427 public boolean isLeaf;
428 public int childCount;
429 ColorNode[] children;
430
431 public int colorCount;
432 public long red;
433 public long blue;
434 public long green;
435
436 public int paletteIndex;
437
438 public int level;
439 ColorNode nextReducible;
440
441 public ColorNode() {
442 isLeaf = false;
443 level = 0;
444 childCount = 0;
445 children = new ColorNode[8];
446 for (int i = 0; i < 8; i++) {
447 children[i] = null;
448 }
449
450 colorCount = 0;
451 red = green = blue = 0;
452
453 paletteIndex = 0;
454 }
455
456 public int getLeafChildCount() {
457 if (isLeaf) {
458 return 0;
459 }
460 int cnt = 0;
461 for (int i = 0; i < children.length; i++) {
462 if (children[i] != null) {
463 if (children[i].isLeaf) {
464 cnt ++;
465 } else {
466 cnt += children[i].getLeafChildCount();
467 }
468 }
469 }
470 return cnt;
471 }
472
473 public int getRGB() {
474 int r = (int)red/colorCount;
475 int g = (int)green/colorCount;
476 int b = (int)blue/colorCount;
477
478 int c = 0xff << 24 | (0xff&r) << 16 | (0xff&g) << 8 | (0xff&b);
479 return c;
480 }
481 }
482 }