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    }