1 /*
2 * SmartSprites Project
3 *
4 * Copyright (C) 2007-2009, Stanisław Osiński.
5 * All rights reserved.
6 *
7 * Redistribution and use in source and binary forms, with or without modification,
8 * are permitted provided that the following conditions are met:
9 *
10 * - Redistributions of source code must retain the above copyright notice, this
11 * list of conditions and the following disclaimer.
12 *
13 * - Redistributions in binary form must reproduce the above copyright notice, this
14 * list of conditions and the following disclaimer in the documentation and/or
15 * other materials provided with the distribution.
16 *
17 * - Neither the name of the SmartSprites Project nor the names of its contributors
18 * may be used to endorse or promote products derived from this software
19 * without specific prior written permission.
20 *
21 * - We kindly request that you include in the end-user documentation provided with
22 * the redistribution and/or in the software itself an acknowledgement equivalent
23 * to the following: "This product includes software developed by the SmartSprites
24 * Project."
25 *
26 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
27 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
28 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
29 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR
30 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
31 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
32 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
33 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
34 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
35 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
36 */
37 package amd;
38
39 /**
40 * (#)Quantize.java 0.90 9/19/00 Adam Doppelt
41 * <p>
42 * An efficient color quantization algorithm, adapted from the C++ implementation quantize.c in
43 * <a href="http://www.imagemagick.org/">ImageMagick</a>. The pixels for an image are placed into an oct tree. The oct
44 * tree is reduced in size, and the pixels from the original image are reassigned to the nodes in the reduced tree.
45 * <p>
46 * Here is the copyright notice from ImageMagick:
47 *
48 * <pre>
49 * %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
50 * % Permission is hereby granted, free of charge, to any person obtaining a %
51 * % copy of this software and associated documentation files ("ImageMagick"), %
52 * % to deal in ImageMagick without restriction, including without limitation %
53 * % the rights to use, copy, modify, merge, publish, distribute, sublicense, %
54 * % and/or sell copies of ImageMagick, and to permit persons to whom the %
55 * % ImageMagick is furnished to do so, subject to the following conditions: %
56 * % %
57 * % The above copyright notice and this permission notice shall be included in %
58 * % all copies or substantial portions of ImageMagick. %
59 * % %
60 * % The software is provided "as is", without warranty of any kind, express or %
61 * % implied, including but not limited to the warranties of merchantability, %
62 * % fitness for a particular purpose and noninfringement. In no event shall %
63 * % E. I. du Pont de Nemours and Company be liable for any claim, damages or %
64 * % other liability, whether in an action of contract, tort or otherwise, %
65 * % arising from, out of or in connection with ImageMagick or the use or other %
66 * % dealings in ImageMagick. %
67 * % %
68 * % Except as contained in this notice, the name of the E. I. du Pont de %
69 * % Nemours and Company shall not be used in advertising or otherwise to %
70 * % promote the sale, use or other dealings in ImageMagick without prior %
71 * % written authorization from the E. I. du Pont de Nemours and Company. %
72 * % %
73 * %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
74 * </pre>
75 *
76 * @author <a href="http://www.gurge.com/amd/">Adam Doppelt</a>
77 *
78 * @version 0.90 19 Sep 2000
79 */
80 public class Quantize {
81
82 /**
83 * <pre>
84 * %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
85 * % %
86 * % %
87 * % %
88 * % QQQ U U AAA N N TTTTT IIIII ZZZZZ EEEEE %
89 * % Q Q U U A A NN N T I ZZ E %
90 * % Q Q U U AAAAA N N N T I ZZZ EEEEE %
91 * % Q QQ U U A A N NN T I ZZ E %
92 * % QQQQ UUU A A N N T IIIII ZZZZZ EEEEE %
93 * % %
94 * % %
95 * % Reduce the Number of Unique Colors in an Image %
96 * % %
97 * % %
98 * % Software Design %
99 * % John Cristy %
100 * % July 1992 %
101 * % %
102 * % %
103 * % Copyright 1998 E. I. du Pont de Nemours and Company %
104 * % %
105 * % Permission is hereby granted, free of charge, to any person obtaining a %
106 * % copy of this software and associated documentation files ("ImageMagick"), %
107 * % to deal in ImageMagick without restriction, including without limitation %
108 * % the rights to use, copy, modify, merge, publish, distribute, sublicense, %
109 * % and/or sell copies of ImageMagick, and to permit persons to whom the %
110 * % ImageMagick is furnished to do so, subject to the following conditions: %
111 * % %
112 * % The above copyright notice and this permission notice shall be included in %
113 * % all copies or substantial portions of ImageMagick. %
114 * % %
115 * % The software is provided "as is", without warranty of any kind, express or %
116 * % implied, including but not limited to the warranties of merchantability, %
117 * % fitness for a particular purpose and noninfringement. In no event shall %
118 * % E. I. du Pont de Nemours and Company be liable for any claim, damages or %
119 * % other liability, whether in an action of contract, tort or otherwise, %
120 * % arising from, out of or in connection with ImageMagick or the use or other %
121 * % dealings in ImageMagick. %
122 * % %
123 * % Except as contained in this notice, the name of the E. I. du Pont de %
124 * % Nemours and Company shall not be used in advertising or otherwise to %
125 * % promote the sale, use or other dealings in ImageMagick without prior %
126 * % written authorization from the E. I. du Pont de Nemours and Company. %
127 * % %
128 * %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
129 * %
130 * % Realism in computer graphics typically requires using 24 bits/pixel to
131 * % generate an image. Yet many graphic display devices do not contain
132 * % the amount of memory necessary to match the spatial and color
133 * % resolution of the human eye. The QUANTIZE program takes a 24 bit
134 * % image and reduces the number of colors so it can be displayed on
135 * % raster device with less bits per pixel. In most instances, the
136 * % quantized image closely resembles the original reference image.
137 * %
138 * % A reduction of colors in an image is also desirable for image
139 * % transmission and real-time animation.
140 * %
141 * % Function Quantize takes a standard RGB or monochrome images and quantizes
142 * % them down to some fixed number of colors.
143 * %
144 * % For purposes of color allocation, an image is a set of n pixels, where
145 * % each pixel is a point in RGB space. RGB space is a 3-dimensional
146 * % vector space, and each pixel, pi, is defined by an ordered triple of
147 * % red, green, and blue coordinates, (ri, gi, bi).
148 * %
149 * % Each primary color component (red, green, or blue) represents an
150 * % intensity which varies linearly from 0 to a maximum value, cmax, which
151 * % corresponds to full saturation of that color. Color allocation is
152 * % defined over a domain consisting of the cube in RGB space with
153 * % opposite vertices at (0,0,0) and (cmax,cmax,cmax). QUANTIZE requires
154 * % cmax = 255.
155 * %
156 * % The algorithm maps this domain onto a tree in which each node
157 * % represents a cube within that domain. In the following discussion
158 * % these cubes are defined by the coordinate of two opposite vertices:
159 * % The vertex nearest the origin in RGB space and the vertex farthest
160 * % from the origin.
161 * %
162 * % The tree's root node represents the the entire domain, (0,0,0) through
163 * % (cmax,cmax,cmax). Each lower level in the tree is generated by
164 * % subdividing one node's cube into eight smaller cubes of equal size.
165 * % This corresponds to bisecting the parent cube with planes passing
166 * % through the midpoints of each edge.
167 * %
168 * % The basic algorithm operates in three phases: Classification,
169 * % Reduction, and Assignment. Classification builds a color
170 * % description tree for the image. Reduction collapses the tree until
171 * % the number it represents, at most, the number of colors desired in the
172 * % output image. Assignment defines the output image's color map and
173 * % sets each pixel's color by reclassification in the reduced tree.
174 * % Our goal is to minimize the numerical discrepancies between the original
175 * % colors and quantized colors (quantization error).
176 * %
177 * % Classification begins by initializing a color description tree of
178 * % sufficient depth to represent each possible input color in a leaf.
179 * % However, it is impractical to generate a fully-formed color
180 * % description tree in the classification phase for realistic values of
181 * % cmax. If colors components in the input image are quantized to k-bit
182 * % precision, so that cmax= 2k-1, the tree would need k levels below the
183 * % root node to allow representing each possible input color in a leaf.
184 * % This becomes prohibitive because the tree's total number of nodes is
185 * % 1 + sum(i=1,k,8k).
186 * %
187 * % A complete tree would require 19,173,961 nodes for k = 8, cmax = 255.
188 * % Therefore, to avoid building a fully populated tree, QUANTIZE: (1)
189 * % Initializes data structures for nodes only as they are needed; (2)
190 * % Chooses a maximum depth for the tree as a function of the desired
191 * % number of colors in the output image (currently log2(colormap size)).
192 * %
193 * % For each pixel in the input image, classification scans downward from
194 * % the root of the color description tree. At each level of the tree it
195 * % identifies the single node which represents a cube in RGB space
196 * % containing the pixel's color. It updates the following data for each
197 * % such node:
198 * %
199 * % n1: Number of pixels whose color is contained in the RGB cube
200 * % which this node represents;
201 * %
202 * % n2: Number of pixels whose color is not represented in a node at
203 * % lower depth in the tree; initially, n2 = 0 for all nodes except
204 * % leaves of the tree.
205 * %
206 * % Sr, Sg, Sb: Sums of the red, green, and blue component values for
207 * % all pixels not classified at a lower depth. The combination of
208 * % these sums and n2 will ultimately characterize the mean color of a
209 * % set of pixels represented by this node.
210 * %
211 * % E: The distance squared in RGB space between each pixel contained
212 * % within a node and the nodes' center. This represents the quantization
213 * % error for a node.
214 * %
215 * % Reduction repeatedly prunes the tree until the number of nodes with
216 * % n2 > 0 is less than or equal to the maximum number of colors allowed
217 * % in the output image. On any given iteration over the tree, it selects
218 * % those nodes whose E count is minimal for pruning and merges their
219 * % color statistics upward. It uses a pruning threshold, Ep, to govern
220 * % node selection as follows:
221 * %
222 * % Ep = 0
223 * % while number of nodes with (n2 > 0) > required maximum number of colors
224 * % prune all nodes such that E <= Ep
225 * % Set Ep to minimum E in remaining nodes
226 * %
227 * % This has the effect of minimizing any quantization error when merging
228 * % two nodes together.
229 * %
230 * % When a node to be pruned has offspring, the pruning procedure invokes
231 * % itself recursively in order to prune the tree from the leaves upward.
232 * % n2, Sr, Sg, and Sb in a node being pruned are always added to the
233 * % corresponding data in that node's parent. This retains the pruned
234 * % node's color characteristics for later averaging.
235 * %
236 * % For each node, n2 pixels exist for which that node represents the
237 * % smallest volume in RGB space containing those pixel's colors. When n2
238 * % > 0 the node will uniquely define a color in the output image. At the
239 * % beginning of reduction, n2 = 0 for all nodes except a the leaves of
240 * % the tree which represent colors present in the input image.
241 * %
242 * % The other pixel count, n1, indicates the total number of colors
243 * % within the cubic volume which the node represents. This includes n1 -
244 * % n2 pixels whose colors should be defined by nodes at a lower level in
245 * % the tree.
246 * %
247 * % Assignment generates the output image from the pruned tree. The
248 * % output image consists of two parts: (1) A color map, which is an
249 * % array of color descriptions (RGB triples) for each color present in
250 * % the output image; (2) A pixel array, which represents each pixel as
251 * % an index into the color map array.
252 * %
253 * % First, the assignment phase makes one pass over the pruned color
254 * % description tree to establish the image's color map. For each node
255 * % with n2 > 0, it divides Sr, Sg, and Sb by n2 . This produces the
256 * % mean color of all pixels that classify no lower than this node. Each
257 * % of these colors becomes an entry in the color map.
258 * %
259 * % Finally, the assignment phase reclassifies each pixel in the pruned
260 * % tree to identify the deepest node containing the pixel's color. The
261 * % pixel's value in the pixel array becomes the index of this node's mean
262 * % color in the color map.
263 * %
264 * % With the permission of USC Information Sciences Institute, 4676 Admiralty
265 * % Way, Marina del Rey, California 90292, this code was adapted from module
266 * % ALCOLS written by Paul Raveling.
267 * %
268 * % The names of ISI and USC are not used in advertising or publicity
269 * % pertaining to distribution of the software without prior specific
270 * % written permission from ISI.
271 * %
272 * </pre>
273 */
274
275 /** The Constant QUICK. */
276 static final boolean QUICK = false;
277
278 /** The Constant MAX_RGB. */
279 static final int MAX_RGB = 255;
280
281 /** The Constant MAX_NODES. */
282 static final int MAX_NODES = 266817;
283
284 /** The Constant MAX_TREE_DEPTH. */
285 static final int MAX_TREE_DEPTH = 8;
286
287 /** The squares. These are precomputed in advance. */
288 static int[] SQUARES;
289
290 /** The shift. */
291 static int[] SHIFT;
292
293 static {
294 SQUARES = new int[MAX_RGB + MAX_RGB + 1];
295 for (int i = -MAX_RGB; i <= MAX_RGB; i++) {
296 SQUARES[i + MAX_RGB] = i * i;
297 }
298
299 SHIFT = new int[MAX_TREE_DEPTH + 1];
300 for (int i = 0; i < MAX_TREE_DEPTH + 1; ++i) {
301 SHIFT[i] = 1 << (15 - i);
302 }
303 }
304
305 /**
306 * Instantiates a new quantize.
307 */
308 private Quantize() {
309 // Prevent Instantiation
310 }
311
312 /**
313 * Reduce the image to the given number of colors. The pixels are reduced in place.
314 *
315 * @param pixels
316 * the pixels
317 * @param maxColors
318 * the max colors
319 *
320 * @return The new color palette.
321 */
322 public static int[] quantizeImage(int[][] pixels, int maxColors) {
323 Cube cube = new Cube(pixels, maxColors);
324 cube.classification();
325 cube.reduction();
326 cube.assignment();
327 return cube.colormap;
328 }
329
330 /**
331 * The Class Cube.
332 */
333 static class Cube {
334
335 /** The pixels. */
336 int[][] pixels;
337
338 /** The max colors. */
339 int maxColors;
340
341 /** The colormap. */
342 int[] colormap;
343
344 /** The root. */
345 Node root;
346
347 /** The depth. */
348 int depth;
349
350 // counter for the number of colors in the cube. this gets
351 /** The colors. */
352 // recalculated often.
353 int colors;
354
355 /** The nodes. */
356 // counter for the number of nodes in the tree
357 int nodes;
358
359 /**
360 * Instantiates a new cube.
361 *
362 * @param pixels
363 * the pixels
364 * @param maxColors
365 * the max colors
366 */
367 Cube(int[][] pixels, int maxColors) {
368 this.pixels = pixels;
369 this.maxColors = maxColors;
370
371 int i = maxColors;
372 // tree_depth = log max_colors
373 // 4
374 for (depth = 1; i != 0; depth++) {
375 i /= 4;
376 }
377 if (depth > 1) {
378 --depth;
379 }
380 if (depth > MAX_TREE_DEPTH) {
381 depth = MAX_TREE_DEPTH;
382 } else if (depth < 2) {
383 depth = 2;
384 }
385
386 root = new Node(this);
387 }
388
389 /**
390 * Procedure Classification begins by initializing a color description tree of sufficient depth to represent
391 * each possible input color in a leaf. However, it is impractical to generate a fully-formed color description
392 * tree in the classification phase for realistic values of cmax. If colors components in the input image are
393 * quantized to k-bit precision, so that cmax= 2k-1, the tree would need k levels below the root node to allow
394 * representing each possible input color in a leaf. This becomes prohibitive because the tree's total number of
395 * nodes is 1 + sum(i=1,k,8k).
396 * <p>
397 * A complete tree would require 19,173,961 nodes for k = 8, cmax = 255. Therefore, to avoid building a fully
398 * populated tree, QUANTIZE: (1) Initializes data structures for nodes only as they are needed; (2) Chooses a
399 * maximum depth for the tree as a function of the desired number of colors in the output image (currently
400 * log2(colormap size)).
401 * <p>
402 * For each pixel in the input image, classification scans downward from the root of the color description tree.
403 * At each level of the tree it identifies the single node which represents a cube in RGB space containing It
404 * updates the following data for each such node:
405 * <p>
406 * number_pixels : Number of pixels whose color is contained in the RGB cube which this node represents;
407 * <p>
408 * unique : Number of pixels whose color is not represented in a node at lower depth in the tree; initially, n2
409 * = 0 for all nodes except leaves of the tree.
410 * <p>
411 * total_red/green/blue : Sums of the red, green, and blue component values for all pixels not classified at a
412 * lower depth. The combination of these sums and n2 will ultimately characterize the mean color of a set of
413 * pixels represented by this node.
414 */
415 void classification() {
416 int[][] pixels = this.pixels;
417
418 int width = pixels.length;
419 int height = pixels[0].length;
420
421 // convert to indexed color
422 for (int x = width; x-- > 0;) {
423 for (int y = height; y-- > 0;) {
424 int pixel = pixels[x][y];
425 int red = pixel >> 16 & 0xFF;
426 int green = pixel >> 8 & 0xFF;
427 int blue = pixel >> 0 & 0xFF;
428
429 // a hard limit on the number of nodes in the tree
430 if (nodes > MAX_NODES) {
431 System.out.println("pruning");
432 root.pruneLevel();
433 --depth;
434 }
435
436 // walk the tree to depth, increasing the
437 // number_pixels count for each node
438 Node node = root;
439 for (int level = 1; level <= depth; ++level) {
440 int id = (red > node.midRed ? 1 : 0) << 0 | (green > node.midGreen ? 1 : 0) << 1
441 | (blue > node.midBlue ? 1 : 0) << 2;
442 if (node.child[id] == null) {
443 new Node(node, id, level);
444 }
445 node = node.child[id];
446 node.numberPixels += SHIFT[level];
447 }
448
449 ++node.unique;
450 node.totalRed += red;
451 node.totalGreen += green;
452 node.totalBlue += blue;
453 }
454 }
455 }
456
457 /**
458 * Reduction.
459 * <p>
460 * reduction repeatedly prunes the tree until the number of nodes with unique > 0 is less than or equal to the
461 * maximum number of colors allowed in the output image.
462 * <p>
463 * When a node to be pruned has offspring, the pruning procedure invokes itself recursively in order to prune
464 * the tree from the leaves upward. The statistics of the node being pruned are always added to the
465 * corresponding data in that node's parent. This retains the pruned node's color characteristics for later
466 * averaging.
467 */
468 void reduction() {
469 int threshold = 1;
470 while (colors > maxColors) {
471 colors = 0;
472 threshold = root.reduce(threshold, Integer.MAX_VALUE);
473 }
474 }
475
476 /**
477 * The result of a closest color search.
478 */
479 static class Search {
480
481 /** The distance. */
482 int distance;
483
484 /** The color number. */
485 int colorNumber;
486 }
487
488 /**
489 * Assignment.
490 * <p>
491 * Procedure assignment generates the output image from the pruned tree. The output image consists of two parts:
492 * (1) A color map, which is an array of color descriptions (RGB triples) for each color present in the output
493 * image; (2) A pixel array, which represents each pixel as an index into the color map array.
494 * <p>
495 * First, the assignment phase makes one pass over the pruned color description tree to establish the image's
496 * color map. For each node with n2 > 0, it divides Sr, Sg, and Sb by n2. This produces the mean color of all
497 * pixels that classify no lower than this node. Each of these colors becomes an entry in the color map.
498 * <p>
499 * Finally, the assignment phase reclassifies each pixel in the pruned tree to identify the deepest node
500 * containing the pixel's color. The pixel's value in the pixel array becomes the index of this node's mean
501 * color in the color map.
502 */
503 void assignment() {
504 colormap = new int[colors];
505
506 colors = 0;
507 root.colormap();
508
509 int[][] pixels = this.pixels;
510
511 int width = pixels.length;
512 int height = pixels[0].length;
513
514 Search search = new Search();
515
516 // convert to indexed color
517 for (int x = width; x-- > 0;) {
518 for (int y = height; y-- > 0;) {
519 int pixel = pixels[x][y];
520 int red = pixel >> 16 & 0xFF;
521 int green = pixel >> 8 & 0xFF;
522 int blue = pixel >> 0 & 0xFF;
523
524 // walk the tree to find the cube containing that color
525 Node node = root;
526 for (;;) {
527 int id = (red > node.midRed ? 1 : 0) << 0 | (green > node.midGreen ? 1 : 0) << 1
528 | (blue > node.midBlue ? 1 : 0) << 2;
529 if (node.child[id] == null) {
530 break;
531 }
532 node = node.child[id];
533 }
534
535 if (QUICK) {
536 // if QUICK is set, just use that
537 // node. Strictly speaking, this isn't
538 // necessarily best match.
539 pixels[x][y] = node.colorNumber;
540 } else {
541 // Find the closest color.
542 search.distance = Integer.MAX_VALUE;
543 node.parent.closestColor(red, green, blue, search);
544 pixels[x][y] = search.colorNumber;
545 }
546 }
547 }
548 }
549
550 /**
551 * A single Node in the tree.
552 */
553 static class Node {
554
555 /** The cube. */
556 Cube cube;
557
558 /** The parent. */
559 // parent node
560 Node parent;
561
562 /** The child. */
563 // child nodes
564 Node[] child;
565
566 /** The nchild. */
567 int nchild;
568
569 /** The id. */
570 // our index within our parent
571 int id;
572
573 /** The level. */
574 // our level within the tree
575 int level;
576
577 /** The mid red. */
578 // our color midpoint
579 int midRed;
580
581 /** The mid green. */
582 int midGreen;
583
584 /** The mid blue. */
585 int midBlue;
586
587 /** The number pixels. */
588 // the pixel count for this node and all children
589 int numberPixels;
590
591 /** The unique. */
592 // the pixel count for this node
593 int unique;
594
595 /** The total red. */
596 // the sum of all pixels contained in this node
597 int totalRed;
598
599 /** The total green. */
600 int totalGreen;
601
602 /** The total blue. */
603 int totalBlue;
604
605 /** The color number. */
606 // used to build the colormap
607 int colorNumber;
608
609 /**
610 * Instantiates a new node.
611 *
612 * @param cube
613 * the cube
614 */
615 Node(Cube cube) {
616 this.cube = cube;
617 this.parent = this;
618 this.child = new Node[8];
619 this.id = 0;
620 this.level = 0;
621
622 this.numberPixels = Integer.MAX_VALUE;
623
624 this.midRed = (MAX_RGB + 1) >> 1;
625 this.midGreen = (MAX_RGB + 1) >> 1;
626 this.midBlue = (MAX_RGB + 1) >> 1;
627 }
628
629 /**
630 * Instantiates a new node.
631 *
632 * @param parent
633 * the parent
634 * @param id
635 * the id
636 * @param level
637 * the level
638 */
639 Node(Node parent, int id, int level) {
640 this.cube = parent.cube;
641 this.parent = parent;
642 this.child = new Node[8];
643 this.id = id;
644 this.level = level;
645
646 // add to the cube
647 ++cube.nodes;
648 if (level == cube.depth) {
649 ++cube.colors;
650 }
651
652 // add to the parent
653 ++parent.nchild;
654 parent.child[id] = this;
655
656 // figure out our midpoint
657 int bi = 1 << (MAX_TREE_DEPTH - level) >> 1;
658 midRed = parent.midRed + ((id & 1) > 0 ? bi : -bi);
659 midGreen = parent.midGreen + ((id & 2) > 0 ? bi : -bi);
660 midBlue = parent.midBlue + ((id & 4) > 0 ? bi : -bi);
661 }
662
663 /**
664 * Remove this child node, and make sure our parent absorbs our pixel statistics.
665 */
666 void pruneChild() {
667 --parent.nchild;
668 parent.unique += unique;
669 parent.totalRed += totalRed;
670 parent.totalGreen += totalGreen;
671 parent.totalBlue += totalBlue;
672 parent.child[id] = null;
673 --cube.nodes;
674 cube = null;
675 parent = null;
676 }
677
678 /**
679 * Prune the lowest layer of the tree.
680 */
681 void pruneLevel() {
682 if (nchild != 0) {
683 for (int i = 0; i < 8; i++) {
684 if (child[i] != null) {
685 child[i].pruneLevel();
686 }
687 }
688 }
689 if (level == cube.depth) {
690 pruneChild();
691 }
692 }
693
694 /**
695 * Remove any nodes that have fewer than threshold pixels. Also, as long as we're walking the tree:
696 *
697 * <pre>
698 * - figure out the color with the fewest pixels
699 * - recalculate the total number of colors in the tree
700 * </pre>
701 *
702 * @param threshold
703 * the threshold
704 * @param nextThreshold
705 * the next threshold
706 *
707 * @return the int
708 */
709 int reduce(int threshold, int nextThreshold) {
710 if (nchild != 0) {
711 for (int i = 0; i < 8; i++) {
712 if (child[i] != null) {
713 nextThreshold = child[i].reduce(threshold, nextThreshold);
714 }
715 }
716 }
717 if (numberPixels <= threshold) {
718 pruneChild();
719 } else {
720 if (unique != 0) {
721 cube.colors++;
722 }
723 if (numberPixels < nextThreshold) {
724 nextThreshold = numberPixels;
725 }
726 }
727 return nextThreshold;
728 }
729
730 /**
731 * Colormap.
732 * <p>
733 * colormap traverses the color cube tree and notes each colormap entry. A colormap entry is any node in the
734 * color cube tree where the number of unique colors is not zero.
735 */
736 void colormap() {
737 if (nchild != 0) {
738 for (int i = 0; i < 8; i++) {
739 if (child[i] != null) {
740 child[i].colormap();
741 }
742 }
743 }
744 if (unique != 0) {
745 int r = (totalRed + (unique >> 1)) / unique;
746 int g = (totalGreen + (unique >> 1)) / unique;
747 int b = (totalBlue + (unique >> 1)) / unique;
748 cube.colormap[cube.colors] = 0xFF << 24 | (r & 0xFF) << 16 | (g & 0xFF) << 8 | (b & 0xFF) << 0;
749 colorNumber = cube.colors++;
750 }
751 }
752
753 /**
754 * Closest color.
755 * <p>
756 * ClosestColor traverses the color cube tree at a particular node and determines which colormap entry best
757 * represents the input color.
758 *
759 * @param red
760 * the red
761 * @param green
762 * the green
763 * @param blue
764 * the blue
765 * @param search
766 * the search
767 */
768 void closestColor(int red, int green, int blue, Search search) {
769 if (nchild != 0) {
770 for (int i = 0; i < 8; i++) {
771 if (child[i] != null) {
772 child[i].closestColor(red, green, blue, search);
773 }
774 }
775 }
776
777 if (unique != 0) {
778 int color = cube.colormap[colorNumber];
779 int distance = distance(color, red, green, blue);
780 if (distance < search.distance) {
781 search.distance = distance;
782 search.colorNumber = colorNumber;
783 }
784 }
785 }
786
787 /**
788 * Figure out the distance between this node and som color.
789 *
790 * @param color
791 * the color
792 * @param r
793 * the r
794 * @param g
795 * the g
796 * @param b
797 * the b
798 *
799 * @return the int
800 */
801 static final int distance(int color, int r, int g, int b) {
802 return SQUARES[(color >> 16 & 0xFF) - r + MAX_RGB] + SQUARES[(color >> 8 & 0xFF) - g + MAX_RGB]
803 + SQUARES[(color >> 0 & 0xFF) - b + MAX_RGB];
804 }
805
806 @Override
807 public String toString() {
808 StringBuilder buf = new StringBuilder();
809 if (parent == this) {
810 buf.append("root");
811 } else {
812 buf.append("node");
813 }
814 buf.append(' ');
815 buf.append(level);
816 buf.append(" [");
817 buf.append(midRed);
818 buf.append(',');
819 buf.append(midGreen);
820 buf.append(',');
821 buf.append(midBlue);
822 buf.append(']');
823 return new String(buf);
824 }
825 }
826 }
827 }