001 /* 002 * MedianCutContourRemoval 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 java.util.Hashtable; 011 import java.util.Vector; 012 import net.sourceforge.jiu.codecs.BMPCodec; 013 import net.sourceforge.jiu.codecs.CodecMode; 014 import net.sourceforge.jiu.codecs.ImageLoader; 015 import net.sourceforge.jiu.color.analysis.MatrixCreator; 016 import net.sourceforge.jiu.color.analysis.MeanDifference; 017 import net.sourceforge.jiu.color.data.CoOccurrenceFrequencyMatrix; 018 import net.sourceforge.jiu.color.data.CoOccurrenceMatrix; 019 import net.sourceforge.jiu.data.Palette; 020 import net.sourceforge.jiu.data.Paletted8Image; 021 import net.sourceforge.jiu.data.PixelImage; 022 import net.sourceforge.jiu.data.RGB24Image; 023 import net.sourceforge.jiu.data.RGBIndex; 024 import net.sourceforge.jiu.ops.ImageToImageOperation; 025 import net.sourceforge.jiu.ops.MissingParameterException; 026 import net.sourceforge.jiu.ops.OperationFailedException; 027 import net.sourceforge.jiu.ops.WrongParameterException; 028 import net.sourceforge.jiu.util.ComparatorInterface; 029 import net.sourceforge.jiu.util.Sort; 030 import net.sourceforge.jiu.util.Statistics; 031 032 /** 033 * A data structure for storing the index values of a pair of 034 * contouring colors plus their respective self co-occurrence 035 * frequency values. 036 * @author Marco Schmidt 037 * @see MedianCutContourRemoval 038 */ 039 class ContouringColorPair implements ComparatorInterface 040 { 041 private int index1; 042 private int index2; 043 private double scof1; 044 private double scof2; 045 046 /** 047 * Creates a new object of this class. 048 */ 049 public ContouringColorPair() 050 { 051 } 052 053 /** 054 * Creates a new object of this class. 055 * @param i1 palette index of first color 056 * @param i2 palette index of second color 057 * @param sf1 self co-occurrence frequency value of first color 058 * @param sf2 self co-occurrence frequency value of second color 059 */ 060 public ContouringColorPair(int i1, int i2, double sf1, double sf2) 061 { 062 index1 = i1; 063 index2 = i2; 064 scof1 = sf1; 065 scof2 = sf2; 066 } 067 068 public int compare(Object o1, Object o2) 069 { 070 ContouringColorPair p1 = (ContouringColorPair)o1; 071 ContouringColorPair p2 = (ContouringColorPair)o2; 072 double sum1 = p1.scof1 + p1.scof2; 073 double sum2 = p2.scof1 + p2.scof2; 074 if (sum1 < sum2) 075 { 076 return -1; 077 } 078 else 079 if (sum1 > sum2) 080 { 081 return 1; 082 } 083 else 084 { 085 return 0; 086 } 087 } 088 089 public int getColorIndex(boolean smaller) 090 { 091 if (smaller) 092 { 093 return scof1 < scof2 ? index1 : index2; 094 } 095 else 096 { 097 return scof1 < scof2 ? index2 : index1; 098 } 099 } 100 } 101 102 /** 103 * Performs the <em>Median Cut</em> color quantization algorithm in combination with 104 * a contour removal algorithm. 105 * <p> 106 * Quantization is an operation that reduces the number of colors in 107 * an image while trying to remain as close to the original image 108 * as possible. 109 * Standard Median Cut quantization is implemented in the 110 * {@link net.sourceforge.jiu.color.quantization.MedianCutQuantizer} 111 * class. 112 * <p> 113 * This class implements an algorithm that improves the standard 114 * implementation. 115 * It repeatedly calls the original quantizer and adjusts the palette 116 * in order to reduce the amount of contouring errors. 117 * <h3>Image types</h3> 118 * This operation requires an {@link net.sourceforge.jiu.data.RGB24Image} 119 * object as input and produces a {@link net.sourceforge.jiu.data.Paletted8Image} 120 * as output. 121 * <h3>Usage example</h3> 122 * <pre> 123 * RGB24Image inputImage = ...; // image to be processed, from a file etc. 124 * MedianCutQuantizer quantizer = new MedianCutQuantizer(); 125 * quantizer.setPaletteSize(256); 126 * MedianCutContourRemoval removal = new MedianCutContourRemoval(); 127 * removal.setQuantizer(quantizer); 128 * removal.setInputImage(inputImage); 129 * removal.setTau(11.0); 130 * removal.setNumPasses(3); 131 * removal.process(); 132 * PixelImage outputImage = removal.getOutputImage(); 133 * </pre> 134 * <h3>Rationale - why an extension to Median Cut?</h3> 135 * Quantization without dithering can lead to contouring (banding) in the output image. 136 * The contours introduced that way are not only ugly but they may lead to erroneous 137 * results when processing that quantized image. 138 * Dithering, an alternative group of algorithms used in combination with quantizers 139 * to improve output quality, leads to output which is more pleasant to the human eye. 140 * However, it introduces noise that may not be acceptable when the output image 141 * is to be further processed by image processing algorithms. 142 * Instead, this algorithm attempts to adjust the palette found by the Median 143 * Cut algorithm. 144 * The adjustments aim at reducing the amount of contouring caused by a 145 * palette found in a previous Median Cut operation. 146 * <h3><a name="howitworks">How the contour removal algorithm works</a></h3> 147 * <ul> 148 * <li> 149 * First, a normal Median Cut quantization operation is performed. 150 * The class 151 * {@link net.sourceforge.jiu.color.quantization.MedianCutQuantizer} 152 * is used for that purpose. 153 * This results in a palette and an output image that was mapped from 154 * the original using the palette. 155 * </li> 156 * <li> 157 * Now a {@link net.sourceforge.jiu.color.data.CoOccurrenceFrequencyMatrix} is created 158 * from a {@link net.sourceforge.jiu.color.data.CoOccurrenceMatrix}, which is in 159 * turn created from the paletted image that was produced in the previous step. 160 * The co-occurrence frequency matrix stores how often a pixel value j is the 161 * neighbor of pixel i in the image, in relation to all occurrences of i. 162 * The matrix stores this information as <code>double</code> values between 163 * <code>0.0</code> and <code>1.0</code>. 164 * If the value is <code>0.6</code>, j makes 60 percent of all neighboring 165 * pixels of i. 166 * </li> 167 * <li> 168 * Using certain heuristics that take advantage of the above mentioned matrices, 169 * colors are classified into three groups: 170 * <ul> 171 * <li>contouring color pairs which contribute significantly to the contouring,</li> 172 * <li>compressible color pairs, two colors which are similar to each other and not contouring, and</li> 173 * <li>all colors which are not part of one of the two color pair types described before.</li> 174 * </ul> 175 * The tau value which can be specified with {@link #setTau(double)} is a 176 * distance value in RGB space (tau is adjusted for an RGB cube where each 177 * axis can take values from 0 to 255). 178 * It is used to define a threshold for similar colors. 179 * A pair of compressible colors may not differ by more than tau. 180 * It is guaranteed that no color can be both compressible and contouring. 181 * </li> 182 * <li> 183 * Note that each palette color generated by the Median Cut algorithm represents a 184 * cuboid part of the RGB color cube. 185 * For each pair of compressible colors, their corresponding cuboids are neighbors in the cube. 186 * Now a number N of palette entries is changed. 187 * That number N is either the number of compressible color pairs found, or the number 188 * of contouring color pairs found, whichever is smaller. 189 * If N equals zero, nothing can be done and the algorithm terminates. 190 * </li> 191 * <li> 192 * Now N swap operations are performed on the palette. 193 * Two palette entries of a compressible color pair are merged to form one palette entry. 194 * Their colors are similar so it will not decrease image quality much. 195 * The newly freed palette entry is used to split one color of a contouring color pair 196 * into two, thus allowing to represent a gradient type section in the image with an 197 * additional color. 198 * </li> 199 * <li> 200 * The original truecolor image is mapped to the new, modified palette. 201 * This whole process can now be performed again with the modified palette. 202 * That's why this operation has a {@link #setNumPasses(int)} method. 203 * Usually, more than eight iterations do not make a difference. 204 * </li> 205 * </ul> 206 * For an in-depth description of the algorithm see the journal article mentioned in the 207 * <em>Credits</em> section below. 208 * <h3>Credits</h3> 209 * The algorithm was developed by 210 * <a target="_top" href="http://www-2.cs.cmu.edu/afs/cs.cmu.edu/user/js/www/homepage.html">Jefferey 211 * Shufelt </a> and described in 212 * his article 213 * <em>Texture Analysis for Enhanced Color Image Quantization.</em> 214 * CVGIP: Graphical Model and Image Processing 59(3): 149-163 (1997). 215 * @see MedianCutQuantizer 216 * @author Marco Schmidt 217 */ 218 public class MedianCutContourRemoval extends ImageToImageOperation 219 { 220 /** 221 * The default tau value, used if none is specified 222 * with {@link #setTau(double)}. 223 * Check the class documentation to find out more about 224 * the meaning of tau: {@link MedianCutContourRemoval}. 225 */ 226 public static final double DEFAULT_TAU = 12; 227 228 /** 229 * The default number of passes, used if they are not specified 230 * with {@link #setNumPasses(int)}. 231 * Check the class documentation to find out more about 232 * the meaning of that number of passes: {@link MedianCutContourRemoval}. 233 */ 234 public static final int DEFAULT_NUM_PASSES = 8; 235 236 private Vector compressibleNodes; 237 private Vector contouringPairs; 238 private MedianCutNode[] leaves; 239 private double[] meanC; 240 private double meanS; 241 private int numPasses = DEFAULT_NUM_PASSES; 242 private Palette palette; 243 private MedianCutQuantizer quantizer; 244 private double stdDevS; 245 private double[] stdDevC; 246 private double sumMeanStdDevS; 247 private double tau = DEFAULT_TAU; 248 249 private double computeDistance(int index1, int index2) 250 { 251 return RGBColor.computeDistance( 252 palette.getSample(RGBIndex.INDEX_RED, index1), 253 palette.getSample(RGBIndex.INDEX_GREEN, index1), 254 palette.getSample(RGBIndex.INDEX_BLUE, index1), 255 palette.getSample(RGBIndex.INDEX_RED, index2), 256 palette.getSample(RGBIndex.INDEX_GREEN, index2), 257 palette.getSample(RGBIndex.INDEX_BLUE, index2) 258 ); 259 } 260 261 /** 262 * Computes the mean and standard deviation (stddev) values and 263 * from the argument matrix and initializes the mean / stddev 264 * fields of this class with them. 265 * @param matrix 266 */ 267 private void computeStatistics(CoOccurrenceFrequencyMatrix matrix) 268 { 269 final int N = quantizer.getPaletteSize(); 270 double values[] = new double[N]; 271 // compute mean of self co-occurrence frequencies 272 for (int i = 0; i < N; i++) 273 { 274 values[i] = matrix.getValue(i, i); 275 } 276 meanS = Statistics.computeMean(values); 277 // compute mean of self co-occurrence frequencies 278 stdDevS = Statistics.computeStandardDeviation(values, meanS); 279 sumMeanStdDevS = meanS + stdDevS; 280 // compute mean and standard deviation of co-occurrence frequencies 281 meanC = new double[N]; 282 stdDevC = new double[N]; 283 for (int j = 0; j < N; j++) 284 { 285 for (int i = 0; i < N; i++) 286 { 287 values[i] = matrix.getValue(i, j); 288 } 289 meanC[j] = Statistics.computeMean(values); 290 stdDevC[j] = Statistics.computeStandardDeviation(values, meanC[j]); 291 } 292 } 293 294 /** 295 * Takes 296 * @return 297 */ 298 private Vector createContouringIndexList() 299 { 300 Hashtable table = new Hashtable(contouringPairs.size() * 2); 301 Vector indexes = new Vector(); 302 Object[] contouringPairArray = toArray(contouringPairs); 303 Sort.sort(contouringPairArray, new ContouringColorPair()); 304 for (int i = contouringPairArray.length - 1; i >= 0; i--) 305 { 306 ContouringColorPair pair = (ContouringColorPair)contouringPairArray[i]; 307 Integer index = new Integer(pair.getColorIndex(false)); 308 if (table.get(index) == null) 309 { 310 table.put(index, index); 311 indexes.addElement(index); 312 } 313 index = new Integer(pair.getColorIndex(true)); 314 if (table.get(index) == null) 315 { 316 table.put(index, index); 317 indexes.addElement(index); 318 } 319 } 320 return indexes; 321 } 322 323 private void findColorPairs(CoOccurrenceFrequencyMatrix matrix, final CoOccurrenceMatrix A) 324 { 325 compressibleNodes = new Vector(); 326 contouringPairs = new Vector(); 327 final int N = quantizer.getPaletteSize(); 328 for (int i = 0; i < N; i++) 329 { 330 final double SI = matrix.getValue(i); 331 for (int j = i + 1; j < N; j++) 332 { 333 final double SJ = matrix.getValue(j); 334 if (SI > sumMeanStdDevS && SJ > sumMeanStdDevS) 335 { 336 // potential contouring pair 337 if (matrix.getValue(i, j) > meanC[j] + stdDevC[j] && 338 matrix.getValue(j, i) > meanC[i] + stdDevC[i] && 339 computeDistance(i, j) <= tau) 340 { 341 contouringPairs.addElement(new ContouringColorPair(i, j, SI, SJ)); 342 } 343 } 344 else 345 if (SI < meanS && SJ < meanS) 346 { 347 MedianCutNode parentI = leaves[i].getParentNode(); 348 MedianCutNode parentJ = leaves[j].getParentNode(); 349 // potential compressible pair 350 if (parentI == parentJ && A.getValue(i, j) == 0 && parentI.getNumColors() > 1) 351 { 352 System.out.println("compressible: " + i + "/" + j); 353 compressibleNodes.addElement(parentI); 354 } 355 } 356 } 357 } 358 } 359 360 /** 361 * Small command line application that performs a contour removal 362 * on an image. 363 * The first and only argument must be the name of image file from 364 * which the image to be quantized is loaded. 365 * @param args program arguments; must have length one, the only argument being the input image file name 366 * @throws Exception 367 */ 368 public static void main(String[] args) throws Exception 369 { 370 PixelImage inputImage = ImageLoader.load(args[0]); 371 if (inputImage == null) 372 { 373 System.err.println("Could not load image from " + args[0]); 374 return; 375 } 376 MedianCutQuantizer quantizer = new MedianCutQuantizer(); 377 quantizer.setPaletteSize(256); 378 MedianCutContourRemoval removal = new MedianCutContourRemoval(); 379 removal.setQuantizer(quantizer); 380 removal.setInputImage(inputImage); 381 removal.process(); 382 BMPCodec codec = new BMPCodec(); 383 codec.setImage(removal.getOutputImage()); 384 codec.setFile(args[1], CodecMode.SAVE); 385 codec.process(); 386 codec.close(); 387 MeanDifference diff = new MeanDifference(); 388 diff.setImages(inputImage, removal.getOutputImage()); 389 diff.process(); 390 System.out.println("Mean difference: " + diff.getDifference()); 391 } 392 393 private void mergeAndSplit() 394 { 395 Vector contouringIndexes = createContouringIndexList(); 396 final int ITERATIONS = Math.min(contouringIndexes.size(), compressibleNodes.size()); 397 int index = 0; 398 do 399 { 400 // make the node a leaf by setting its two successors (which are leaves) to null 401 MedianCutNode compressibleNode = (MedianCutNode)compressibleNodes.elementAt(index); 402 compressibleNode.setSuccessors(null, null); 403 // split the contouring color into two 404 Integer contouringIndex = (Integer)contouringIndexes.elementAt(index); 405 MedianCutNode contouringNode = leaves[contouringIndex.intValue()]; 406 quantizer.splitNode(contouringNode); 407 index++; 408 } 409 while (index < ITERATIONS); 410 } 411 412 public void process() throws MissingParameterException, OperationFailedException, WrongParameterException 413 { 414 if (quantizer == null) 415 { 416 throw new MissingParameterException("No MedianCutQuantizer object was specified."); 417 } 418 ensureInputImageIsAvailable(); 419 PixelImage pixelImage = getInputImage(); 420 if (!(pixelImage instanceof RGB24Image)) 421 { 422 throw new WrongParameterException("Input image must implement RGB24Image."); 423 } 424 RGB24Image originalImage = (RGB24Image)pixelImage; 425 quantizer.setInputImage(originalImage); 426 quantizer.setMapping(true); // we want the quantizer to create an output image 427 quantizer.setTruecolorOutput(false); // that output image must be paletted 428 quantizer.process(); 429 for (int currentPass = 0; currentPass < numPasses; currentPass++) 430 { 431 Paletted8Image palImage = (Paletted8Image)quantizer.getOutputImage(); 432 palette = palImage.getPalette(); 433 // create co-occurrence matrix for paletted image 434 CoOccurrenceMatrix com = MatrixCreator.createCoOccurrenceMatrix(palImage); 435 // create co-occurrence frequency matrix for co-occurrence matrix 436 CoOccurrenceFrequencyMatrix cofm = MatrixCreator.createCoOccurrenceFrequencyMatrix(com); 437 // compute certain statistics from the co-occurrence frequency matrix 438 computeStatistics(cofm); 439 // find pairs of contouring and compressible colors 440 leaves = quantizer.createLeafList(); 441 findColorPairs(cofm, com); 442 if (compressibleNodes.size() == 0 || 443 contouringPairs.size() == 0) 444 { 445 //System.out.println("Compressible=" + compressibleNodes.size() + contouring=" + contouringPairs.size() + " in iteration " + currentPass); 446 break; 447 } 448 // adjust Median-Cut-specific data structures: 449 // merge compressible and split contouring nodes 450 System.out.println((currentPass + 1) + " " + 451 compressibleNodes.size() + " " + contouringPairs.size()); 452 mergeAndSplit(); 453 // create a new version of the paletted image: 454 // (1) reassign palette index values for the nodes 455 quantizer.setAllPaletteIndexValues(); 456 // (2) make it recompute the representative colors 457 quantizer.findAllRepresentativeColors(); 458 // (3) create a new Palette object 459 palette = quantizer.createPalette(); 460 // (4) give that to the paletted image 461 Paletted8Image out = (Paletted8Image)quantizer.getOutputImage(); 462 out.setPalette(palette); 463 // (5) map original to that new palette 464 quantizer.mapImage(originalImage, out); 465 } 466 setOutputImage(quantizer.getOutputImage()); 467 } 468 469 /** 470 * Set the 471 * {@link net.sourceforge.jiu.color.quantization.MedianCutQuantizer} 472 * object to be used with this contour removal operation. 473 * This is a mandatory parameter. 474 * If process gets called before the quantizer object was specified, 475 * a {@link MissingParameterException} is thrown. 476 * @param medianCutQuantizer the quantizer object that will get used by this operation 477 */ 478 public void setQuantizer(MedianCutQuantizer medianCutQuantizer) 479 { 480 quantizer = medianCutQuantizer; 481 } 482 483 /** 484 * Specify the number of contour removal passes to be performed. 485 * Check out the section <a href="#howitworks">How the contour removal algorithm works</a> 486 * to learn more about the meaning of this value. 487 * If this method is not called the default value {@link #DEFAULT_NUM_PASSES} 488 * is used. 489 * @param newValue number of passes, 1 or higher 490 * @throws IllegalArgumentException if the argument is 0 or smaller 491 */ 492 public void setNumPasses(int newValue) 493 { 494 if (newValue < 1) 495 { 496 throw new IllegalArgumentException("Number of passes must be 1 or larger."); 497 } 498 numPasses = newValue; 499 } 500 501 /** 502 * Specify the tau value to be used by this operation. 503 * Check out the section <a href="#howitworks">How the contour removal algorithm works</a> 504 * to learn more about the meaning of this value. 505 * If this method is not called the default value {@link #DEFAULT_TAU} 506 * is used. 507 * @param newValue tau value, 0.0 or higher 508 * @throws IllegalArgumentException if the argument is smaller than 0.0 509 */ 510 public void setTau(double newValue) 511 { 512 if (newValue < 0.0) 513 { 514 throw new IllegalArgumentException("Tau value must be 0.0 or larger."); 515 } 516 tau = newValue; 517 } 518 519 /** 520 * Converts a Vector to an Object array. 521 * Since Java 1.2 Vector has a toArray method, but we cannot rely 522 * on 1.2 being available. 523 * @param list Vector with objects 524 * @return Object array with elements from list, in the same order 525 */ 526 private Object[] toArray(Vector list) 527 { 528 Object[] result = new Object[list.size()]; 529 for (int i = 0; i < list.size(); i++) 530 { 531 result[i] = list.elementAt(i); 532 } 533 return result; 534 } 535 }