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 }