View Javadoc
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 }