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    }