001 /* 002 * MedianCutQuantizer 003 * 004 * Copyright (c) 2001, 2002, 2003 Marco Schmidt. 005 * All rights reserved. 006 */ 007 008 package net.sourceforge.jiu.color.quantization; 009 010 import net.sourceforge.jiu.color.analysis.Histogram3DCreator; 011 import net.sourceforge.jiu.color.data.Histogram3D; 012 import net.sourceforge.jiu.color.quantization.MedianCutNode; 013 import net.sourceforge.jiu.color.quantization.RGBColor; 014 import net.sourceforge.jiu.color.quantization.RGBColorList; 015 import net.sourceforge.jiu.color.quantization.RGBQuantizer; 016 import net.sourceforge.jiu.data.MemoryPaletted8Image; 017 import net.sourceforge.jiu.data.Palette; 018 import net.sourceforge.jiu.data.Paletted8Image; 019 import net.sourceforge.jiu.data.PixelImage; 020 import net.sourceforge.jiu.data.RGB24Image; 021 import net.sourceforge.jiu.data.RGBIndex; 022 import net.sourceforge.jiu.ops.ImageToImageOperation; 023 import net.sourceforge.jiu.ops.MissingParameterException; 024 import net.sourceforge.jiu.ops.OperationFailedException; 025 import net.sourceforge.jiu.ops.WrongParameterException; 026 027 /** 028 * Performs the <em>Median Cut</em> color quantization algorithm 029 * for a given list of colors. 030 * <h3>Supported image types</h3> 031 * The input image must implement {@link net.sourceforge.jiu.data.RGB24Image}. 032 * <h3>Usage example</h3> 033 * The following code snippet uses the default settings with a palette of 256 entries. 034 * <pre> 035 * MedianCutQuantizer quantizer = new MedianCutQuantizer(); 036 * quantizer.setInputImage(image); 037 * quantizer.setPaletteSize(256); 038 * quantizer.process(); 039 * PixelImage quantizedImage = quantizer.getOutputImage(); 040 * </pre> 041 * If you want to combine Median Cut quantization with error diffusion dithering to 042 * improve the visual quality of the output, try the 043 * {@link net.sourceforge.jiu.color.dithering.ErrorDiffusionDithering} class. 044 * However, note that noise is introduced into the image with dithering methods so 045 * that the resulting image may not be suitable for automatic processing. 046 * <h3>Credits</h3> 047 * The Median Cut algorithm was designed by 048 * <a target="_top" href="http://www.cs.cmu.edu/~ph">Paul Heckbert</a>. 049 * He described it in the article <em>Color image quantization for frame 050 * buffer display</em>. Comput. Graphics 16(3), 1982, 297 - 304. 051 * <a target="_top" href="http://citeseer.nj.nec.com/heckbert80color.html">CiteSeer 052 * page of the article</a>. 053 * @author Marco Schmidt 054 * @see MedianCutContourRemoval 055 * @see net.sourceforge.jiu.color.dithering.ErrorDiffusionDithering 056 */ 057 public class MedianCutQuantizer extends ImageToImageOperation implements RGBIndex, RGBQuantizer 058 { 059 /** 060 * Constant value for a method of determining the representative color 061 * for a set of colors by computing the average of all samples for each 062 * of the three components red, green and blue. 063 * #getMethodToDetermineRepresentativeColors 064 * #setMethodToDetermineRepresentativeColors 065 */ 066 public static final int METHOD_REPR_COLOR_AVERAGE = 0; 067 068 /** 069 * Constant value for a method of determining the representative color 070 * for a set of colors by computing the weighted average of all samples for each 071 * of the three components red, green and blue. 072 * Weighted means that each color is multiplied by the number of times it occurs 073 * in the input image. 074 * The values of samples multiplied by their frequency are then divided by the total 075 * number of times the colors appear in the image. 076 * #getMethodToDetermineRepresentativeColors 077 * #setMethodToDetermineRepresentativeColors 078 */ 079 public static final int METHOD_REPR_COLOR_WEIGHTED_AVERAGE = 1; 080 081 /** 082 * Constant value for a method of determining the representative color 083 * for a set of colors by picking the median value of all samples for each 084 * of the three components red, green and blue. 085 * #getMethodToDetermineRepresentativeColors 086 * #setMethodToDetermineRepresentativeColors 087 */ 088 public static final int METHOD_REPR_COLOR_MEDIAN = 2; 089 090 /** 091 * The default method to determine the representative color 092 * from a list of colors. 093 * Will be used if none is set by the user of this class via 094 * {@link #setMethodToDetermineRepresentativeColors}. 095 */ 096 public static final int DEFAULT_METHOD_REPR_COLOR = METHOD_REPR_COLOR_MEDIAN; 097 098 private boolean doNotMap; 099 private RGBColorList list; 100 private int maxValue; 101 private int method; 102 private boolean outputTruecolor; 103 private int paletteSize; 104 private MedianCutNode root; 105 106 /** 107 * Creates a MedianCutQuantizer object and 108 * initializes its fields to default values. 109 */ 110 public MedianCutQuantizer() 111 { 112 doNotMap = false; 113 maxValue = -1; 114 method = METHOD_REPR_COLOR_AVERAGE; 115 maxValue = 255; 116 outputTruecolor = false; 117 paletteSize = 256; 118 } 119 120 private void addNodes(MedianCutNode[] nodeList, MedianCutNode node) 121 { 122 if (node == null) 123 { 124 return; 125 } 126 if (node.isLeaf()) 127 { 128 int index = node.getPaletteIndex(); 129 if (index >= 0 && index < nodeList.length) 130 { 131 nodeList[index] = node; 132 } 133 else 134 { 135 // ERROR ILLEGAL STATE 136 throw new IllegalStateException("A node's index is invalid."); 137 } 138 } 139 else 140 { 141 addNodes(nodeList, node.getLeftSuccessor()); 142 addNodes(nodeList, node.getRightSuccessor()); 143 } 144 } 145 146 private RGBColorList createColorList(RGB24Image image) throws OperationFailedException 147 { 148 Histogram3DCreator hc = new Histogram3DCreator(); 149 hc.setImage(image, RGBIndex.INDEX_RED, RGBIndex.INDEX_GREEN, RGBIndex.INDEX_BLUE); 150 hc.process(); 151 Histogram3D hist = hc.getHistogram(); 152 if (hist == null) 153 { 154 throw new OperationFailedException("Could not create histogram from input image."); 155 } 156 int numUniqueColors = hist.getNumUsedEntries(); 157 if (numUniqueColors <= paletteSize) 158 { 159 throw new WrongParameterException("Input image has only " + numUniqueColors + 160 " unique color(s), so it cannot be reduced to " + paletteSize + 161 " color(s)."); 162 } 163 return new RGBColorList(hist); 164 } 165 166 /** 167 * Creates a linear list of leaf nodes. 168 * Assumes that {@link #findPalette()} was successfully run before. 169 */ 170 public MedianCutNode[] createLeafList() 171 { 172 MedianCutNode[] result = new MedianCutNode[paletteSize]; 173 addNodes(result, root); 174 return result; 175 } 176 177 /** 178 * Creates a palette with the representative colors of all leaf nodes. 179 * Assumes that {@link #findPalette()} was successfully run before. 180 * @return palette with all representative colors 181 */ 182 public Palette createPalette() 183 { 184 MedianCutNode[] leaves = createLeafList(); 185 Palette result = new Palette(leaves.length); 186 for (int i = 0; i < leaves.length; i++) 187 { 188 int[] reprColor = leaves[i].getRepresentativeColor(); 189 result.putSample(INDEX_RED, i, reprColor[INDEX_RED]); 190 result.putSample(INDEX_GREEN, i, reprColor[INDEX_GREEN]); 191 result.putSample(INDEX_BLUE, i, reprColor[INDEX_BLUE]); 192 } 193 return result; 194 } 195 196 /** 197 * Traverses tree given by argument node and returns leaf with largest distribution 198 * of samples for any of its three components. 199 */ 200 private MedianCutNode findLeafToBeSplit(MedianCutNode node) 201 { 202 if (node == null) 203 { 204 return null; 205 } 206 if (node.canBeSplit()) 207 { 208 if (!node.isAxisDetermined()) 209 { 210 int[] pairAxisDiff = list.findExtrema(node.getLeftIndex(), node.getRightIndex()); 211 if (pairAxisDiff == null) 212 { 213 return null; 214 } 215 node.setLargestDistribution(pairAxisDiff[0], pairAxisDiff[1]); // axis, difference 216 } 217 return node; 218 } 219 else 220 { 221 MedianCutNode node1 = findLeafToBeSplit(node.getLeftSuccessor()); 222 boolean canSplit1 = (node1 != null && node1.canBeSplit()); 223 MedianCutNode node2 = findLeafToBeSplit(node.getRightSuccessor()); 224 boolean canSplit2 = (node2 != null && node2.canBeSplit()); 225 if (canSplit1) 226 { 227 if (canSplit2) 228 { 229 // case 1 of 4: both nodes can be split; find out which one has the largest distribution 230 // of samples for one of the three RGB channels 231 if (node1.getDifferenceOfLargestDistribution() >= node2.getDifferenceOfLargestDistribution()) 232 { 233 return node1; 234 } 235 else 236 { 237 return node2; 238 } 239 } 240 else 241 { 242 // case 2 of 4: node1 can be split, node2 can't => take node1 243 return node1; 244 } 245 } 246 else 247 { 248 if (canSplit2) 249 { 250 // case 3 of 4: node2 can be split, node1 can't => take node2 251 return node2; 252 } 253 else 254 { 255 // case 4 of 4: both nodes cannot be split => return null 256 return null; 257 } 258 } 259 } 260 } 261 262 /** 263 * For a given RGB value, searches the node in the internal node tree whose 264 * representative color is closest to this color. 265 * @param rgb the color for which a match is searched; the array must have at least 266 * three entries; {@link RGBIndex} constants are used to address the samples 267 * @return node with best match 268 */ 269 public MedianCutNode findNearestNeighbor(int[] rgb) 270 { 271 MedianCutNode result = root; 272 while (!result.isLeaf()) 273 { 274 result = result.getSuccessor(rgb); 275 } 276 return result; 277 } 278 279 /** 280 * For each node in the argument array computes the distance between the 281 * representative color of that node and the color given by the three 282 * argument samples. 283 * @return index of the node with the smallest distance or -1 if the array has a length of 0 284 */ 285 public int findNearestNeighbor(MedianCutNode[] nodes, int red, int green, int blue) 286 { 287 int index = -1; 288 double distance = 1000000; 289 for (int i = 0; i < nodes.length; i++) 290 { 291 MedianCutNode node = nodes[i]; 292 int[] reprColor = node.getRepresentativeColor(); 293 double d = RGBColor.computeDistance(red, green, blue, 294 reprColor[INDEX_RED], reprColor[INDEX_GREEN], reprColor[INDEX_BLUE]); 295 if (d < distance) 296 { 297 distance = d; 298 index = i; 299 } 300 } 301 return index; 302 } 303 304 public void findPalette() 305 { 306 int colorsLeft = paletteSize - 1; 307 while (colorsLeft > 0) 308 { 309 // find leaf with largest sample difference 310 MedianCutNode node = findLeafToBeSplit(root); 311 splitNode(node); 312 colorsLeft--; 313 } 314 findRepresentativeColors(root); 315 setAllPaletteIndexValues(); 316 } 317 318 public void findAllRepresentativeColors() 319 { 320 findRepresentativeColors(root); 321 } 322 323 /** 324 * Computes a representative color for a set of colors in the color list. 325 * Returns the color as a length three int array of sample values (which can be accessed using the 326 * index constants from {@link RGBIndex}. 327 * The method of determining the color (the REPR_xxx constants from this class) 328 * has been given to the constructor. 329 */ 330 private int[] findRepresentativeColor(int index1, int index2) 331 { 332 int[] result = new int[3]; 333 long[] temp = new long[3]; 334 temp[0] = 0; 335 temp[1] = 0; 336 temp[2] = 0; 337 switch(method) 338 { 339 case(METHOD_REPR_COLOR_AVERAGE): 340 { 341 int num = index2 - index1 + 1; 342 for (int i = index1; i <= index2; i++) 343 { 344 RGBColor color = list.getColor(i); 345 temp[0] += color.getSample(0); 346 temp[1] += color.getSample(1); 347 temp[2] += color.getSample(2); 348 } 349 result[0] = (int)(temp[0] / num); 350 result[1] = (int)(temp[1] / num); 351 result[2] = (int)(temp[2] / num); 352 return result; 353 } 354 case(METHOD_REPR_COLOR_WEIGHTED_AVERAGE): 355 { 356 long num = 0; 357 for (int i = index1; i <= index2; i++) 358 { 359 RGBColor color = list.getColor(i); 360 int counter = color.getCounter(); 361 temp[0] += color.getSample(0) * counter; 362 temp[1] += color.getSample(1) * counter; 363 temp[2] += color.getSample(2) * counter; 364 num += counter; 365 } 366 if (num == 0) 367 { 368 //System.out.println("ERROR IN FINDREPRESENTATIVECOLOR (WEIGHTED AVERAGE): ZERO COUNTER"); 369 return null; 370 } 371 result[0] = (int)(temp[0] / num); 372 result[1] = (int)(temp[1] / num); 373 result[2] = (int)(temp[2] / num); 374 return result; 375 } 376 case(METHOD_REPR_COLOR_MEDIAN): 377 { 378 RGBColor color = list.getColor((index1 + index2) / 2); 379 result[0] = color.getSample(0); 380 result[1] = color.getSample(1); 381 result[2] = color.getSample(2); 382 return result; 383 } 384 default: throw new IllegalStateException("Unknown method for determining a representative color."); 385 } 386 } 387 388 /** 389 * Calls findRepresentativeColor with node if node is a leaf. 390 * Otherwise, recursively calls itself with both successor nodes. 391 */ 392 private void findRepresentativeColors(MedianCutNode node) 393 { 394 if (node == null) 395 { 396 return; 397 } 398 if (node.isLeaf()) 399 { 400 node.setRepresentativeColor(findRepresentativeColor(node.getLeftIndex(), node.getRightIndex())); 401 } 402 else 403 { 404 findRepresentativeColors(node.getLeftSuccessor()); 405 findRepresentativeColors(node.getRightSuccessor()); 406 } 407 } 408 409 /** 410 * Returns the method (to be) used to determine the representative 411 * color for the list of colors of a node. 412 * Default is {@link #DEFAULT_METHOD_REPR_COLOR}. 413 * @return the method, one of the METHOD_xyz constants 414 */ 415 public int getMethodToDetermineRepresentativeColors() 416 { 417 return method; 418 } 419 420 /** 421 * Returns the number of colors in the destination image. 422 * If output is paletted, this is also the number of entries 423 * in the palette. 424 * @return number of colors in the destination 425 */ 426 public int getPaletteSize() 427 { 428 return paletteSize; 429 } 430 431 /** 432 * Returns if this operation is supposed to generate truecolor or 433 * paletted output. 434 * @return if truecolor images are to be generated 435 * @see #setTruecolorOutput(boolean) 436 */ 437 public boolean getTruecolorOutput() 438 { 439 return outputTruecolor; 440 } 441 442 public int map(int[] origRgb, int[] quantizedRgb) 443 { 444 MedianCutNode node = findNearestNeighbor(origRgb); 445 int[] reprColor = node.getRepresentativeColor(); 446 quantizedRgb[INDEX_RED] = reprColor[INDEX_RED]; 447 quantizedRgb[INDEX_GREEN] = reprColor[INDEX_GREEN]; 448 quantizedRgb[INDEX_BLUE] = reprColor[INDEX_BLUE]; 449 return node.getPaletteIndex(); 450 } 451 452 public void mapImage(RGB24Image in, RGB24Image out) 453 { 454 int[] rgb = new int[3]; 455 for (int y = 0; y < in.getHeight(); y++) 456 { 457 for (int x = 0; x < in.getWidth(); x++) 458 { 459 rgb[INDEX_RED] = in.getSample(INDEX_RED, x, y); 460 rgb[INDEX_GREEN] = in.getSample(INDEX_GREEN, x, y); 461 rgb[INDEX_BLUE] = in.getSample(INDEX_BLUE, x, y); 462 MedianCutNode node = findNearestNeighbor(rgb); 463 int[] reprColor = node.getRepresentativeColor(); 464 out.putSample(INDEX_RED, x, y, reprColor[INDEX_RED]); 465 out.putSample(INDEX_GREEN, x, y, reprColor[INDEX_GREEN]); 466 out.putSample(INDEX_BLUE, x, y, reprColor[INDEX_BLUE]); 467 } 468 } 469 } 470 471 public void mapImage(RGB24Image in, Paletted8Image out) 472 { 473 int[] rgb = new int[3]; 474 for (int y = 0; y < in.getHeight(); y++) 475 { 476 for (int x = 0; x < in.getWidth(); x++) 477 { 478 rgb[INDEX_RED] = in.getSample(INDEX_RED, x, y); 479 rgb[INDEX_GREEN] = in.getSample(INDEX_GREEN, x, y); 480 rgb[INDEX_BLUE] = in.getSample(INDEX_BLUE, x, y); 481 MedianCutNode node = findNearestNeighbor(rgb); 482 out.putSample(0, x, y, node.getPaletteIndex()); 483 } 484 } 485 } 486 487 public void process() throws 488 MissingParameterException, 489 OperationFailedException, 490 WrongParameterException 491 { 492 ensureInputImageIsAvailable(); 493 ensureImagesHaveSameResolution(); 494 PixelImage in = getInputImage(); 495 if (in instanceof RGB24Image) 496 { 497 list = createColorList((RGB24Image)in); 498 } 499 else 500 { 501 throw new WrongParameterException("Input image must implement RGB24Image."); 502 } 503 root = new MedianCutNode(null, 0, list.getNumEntries() - 1); 504 root.setMinColor(0, 0, 0); 505 root.setMaxColor(maxValue, maxValue, maxValue); 506 findPalette(); 507 if (doNotMap) 508 { 509 return; 510 } 511 PixelImage out = getOutputImage(); 512 if (getTruecolorOutput()) 513 { 514 if (out == null) 515 { 516 out = in.createCompatibleImage(in.getWidth(), in.getHeight()); 517 setOutputImage(out); 518 } 519 else 520 { 521 if (!(out instanceof RGB24Image)) 522 { 523 throw new WrongParameterException("Output image must implement RGB24Image."); 524 } 525 } 526 mapImage((RGB24Image)in, (RGB24Image)out); 527 } 528 else 529 { 530 Palette palette = createPalette(); 531 if (out == null) 532 { 533 out = new MemoryPaletted8Image(in.getWidth(), in.getHeight(), palette); 534 setOutputImage(out); 535 } 536 else 537 { 538 if (out instanceof Paletted8Image) 539 { 540 ((Paletted8Image)out).setPalette(palette); 541 } 542 else 543 { 544 throw new WrongParameterException("Output image must implement Paletted8Image."); 545 } 546 } 547 mapImage((RGB24Image)in, (Paletted8Image)out); 548 } 549 } 550 551 public void setAllPaletteIndexValues() 552 { 553 int paletteEntriesAssigned = setPaletteIndexValues(root, 0); 554 if (paletteEntriesAssigned != paletteSize) 555 { 556 throw new IllegalStateException("Assigning palette values did not result in correct number of entries."); 557 } 558 } 559 560 /** 561 * Defines whether process will map the input image to an output image. 562 * If not, only the palette is determined. 563 */ 564 public void setMapping(boolean doMap) 565 { 566 doNotMap = !doMap; 567 } 568 569 /** 570 * Sets the method to determine the representative color 571 * for a list of colors. 572 * After the algorithm has determined sets of colors that lie 573 * closely together in color space and will be 574 * mapped to the same color in the destination image, 575 * the algorithm will determine that color 576 * @param newMethod the new method, one of the METHOD_xyz constants in this class 577 */ 578 public void setMethodToDetermineRepresentativeColors(int newMethod) 579 { 580 if (newMethod != METHOD_REPR_COLOR_AVERAGE && 581 newMethod != METHOD_REPR_COLOR_WEIGHTED_AVERAGE && 582 newMethod != METHOD_REPR_COLOR_MEDIAN) 583 { 584 throw new IllegalArgumentException("Method must be one of the METHOD_xyz constants."); 585 } 586 method = newMethod; 587 } 588 589 /** 590 * Recursively visits node and its descendants, assigning ascending 591 * palette index values to leaves via MedianCutNode.setPaletteIndex(int). 592 * If this method is called with root and 0 as parameters, all leaves 593 * will get a unique palette index. 594 */ 595 private int setPaletteIndexValues(MedianCutNode node, int index) 596 { 597 if (node.isLeaf()) 598 { 599 node.setPaletteIndex(index); 600 index++; 601 return index; 602 } 603 else 604 { 605 index = setPaletteIndexValues(node.getLeftSuccessor(), index); 606 return setPaletteIndexValues(node.getRightSuccessor(), index); 607 } 608 } 609 610 /** 611 * Sets the number of colors that this operations is supposed to reduce 612 * the original image to. 613 * @param newPaletteSize the number of colors 614 * @throws IllegalArgumentException if the argument is smaller than 1 or larger than 256 615 * @see #getPaletteSize 616 */ 617 public void setPaletteSize(int newPaletteSize) 618 { 619 if (newPaletteSize < 1) 620 { 621 throw new IllegalArgumentException("Palette size must be 1 or larger."); 622 } 623 if (newPaletteSize > 256) 624 { 625 throw new IllegalArgumentException("Palette size must be at most 256."); 626 } 627 paletteSize = newPaletteSize; 628 } 629 630 /** 631 * Lets the user specify if the output image is to be truecolor 632 * (argument useTruecolor is <code>true</code>) or paletted 633 * (argument useTruecolor is <code>false</code>). 634 * If the color type is to be changed afterwards, use PromoteToRgb24 635 * to convert from paletted to truecolor. 636 * Reducing a truecolor image that uses only 256 or less colors to 637 * a paletted image can be done with AutoDetectColorType. 638 * @param useTruecolor 639 */ 640 public void setTruecolorOutput(boolean useTruecolor) 641 { 642 outputTruecolor = useTruecolor; 643 } 644 645 public void splitNode(MedianCutNode node) 646 { 647 if (!node.isAxisDetermined()) 648 { 649 int[] pairAxisDiff = list.findExtrema(node.getLeftIndex(), node.getRightIndex()); 650 node.setLargestDistribution(pairAxisDiff[0], pairAxisDiff[1]); // axis, difference 651 } 652 653 list.sortByAxis(node.getLeftIndex(), node.getRightIndex(), node.getAxisOfLargestDistribution()); 654 int middleIndex = node.getMiddleIndex(); 655 int leftIndex = node.getLeftIndex(); 656 int rightIndex = node.getRightIndex(); 657 RGBColor color = list.getColor(middleIndex); 658 int axis = node.getAxisOfLargestDistribution(); 659 int medianValue = color.getSample(axis); 660 node.setMedianValue(medianValue); 661 if (leftIndex == rightIndex) 662 { 663 throw new IllegalArgumentException("Cannot split leaf that only holds one color. This should never happen."); 664 } 665 MedianCutNode left = new MedianCutNode(node, leftIndex, middleIndex); 666 MedianCutNode right = new MedianCutNode(node, middleIndex + 1, rightIndex); 667 node.setSuccessors(left, right); 668 for (int i = 0; i < 3; i++) 669 { 670 int max = node.getMaxColorSample(i); 671 left.setMaxColorSample(i, max); 672 right.setMaxColorSample(i, max); 673 int min = node.getMinColorSample(i); 674 left.setMinColorSample(i, min); 675 right.setMinColorSample(i, min); 676 } 677 left.setMaxColorSample(axis, medianValue); 678 right.setMinColorSample(axis, medianValue + 1); 679 } 680 }