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