001    /*
002     * OctreeColorQuantizer
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.quantization.RGBQuantizer;
011    import net.sourceforge.jiu.data.MemoryPaletted8Image;
012    import net.sourceforge.jiu.data.Palette;
013    import net.sourceforge.jiu.data.Paletted8Image;
014    import net.sourceforge.jiu.data.PixelImage;
015    import net.sourceforge.jiu.data.RGB24Image;
016    import net.sourceforge.jiu.data.RGBIndex;
017    import net.sourceforge.jiu.ops.ImageToImageOperation;
018    import net.sourceforge.jiu.ops.MissingParameterException;
019    import net.sourceforge.jiu.ops.WrongParameterException;
020    import net.sourceforge.jiu.util.Sort;
021    
022    /**
023     * Performs the octree color quantization algorithm for a given RGB truecolor image.
024     * The quality is usually somewhat inferior to the results of {@link MedianCutQuantizer}.
025     * Note that you can improve the quality by applying a dithering algorithm.
026     * See {@link net.sourceforge.jiu.color.dithering.ErrorDiffusionDithering}.
027     *
028     * <h3>Usage example</h3>
029     * This reduces some RGB24Image image to a 16 color paletted image:
030     * <pre>
031     * MemoryRGB24Image image = ...; // initialize
032     * OctreeColorQuantizer ocq = new OctreeColorQuantizer();
033     * ocq.setInputImage(image);
034     * ocq.setPaletteSize(16);
035     * ocq.process();
036     * PixelImage quantizedImage = ocq.getOutputImage();
037     * </pre>
038     *
039     * <h3>Credits</h3>
040     * 
041     * @author Marco Schmidt
042     * @since 0.6.0
043     */
044    public class OctreeColorQuantizer extends ImageToImageOperation implements RGBIndex, RGBQuantizer
045    {
046            /**
047             * The default number of colors in the palette.
048             * Will be used when no other value is specified via {@link #setPaletteSize}.
049             */
050            public static final int DEFAULT_PALETTE_SIZE = 256;
051    
052            private int paletteSize = DEFAULT_PALETTE_SIZE;
053            private OctreeNode root;
054            private Palette palette;
055            private int[] redValues;
056            private int[] greenValues;
057            private int[] blueValues;
058    
059            /**
060             * If node is a leaf node, this method assigns palette index values 
061             * and determines the representative color, otherwise it simply
062             * recursively calls itself for all child nodes.
063             * The updated index value is returned.
064             * It is increased whenever a leaf is assigned that index value.
065             *
066             * @param node the node of the octree that will itself (and its children) be processed
067             * @param index the current index in the palette index assignment procedure
068             * @return updated index value; may have been increased while node or its child(ren) -
069             *  were assigned index values
070             */
071            private int assignPaletteIndexValues(OctreeNode node, int index)
072            {
073                    if (node == null)
074                    {
075                            return index;
076                    }
077                    if (node.isLeaf())
078                    {
079                            node.setPaletteIndex(index);
080                            node.determineRepresentativeColor();
081                            return index + 1;
082                    }
083                    else
084                    {
085                            OctreeNode[] children = node.getChildren();
086                            if (children != null)
087                            {
088                                    for (int i = 0; i < 8; i++)
089                                    {
090                                            if (children[i] != null)
091                                            {
092                                                    index = assignPaletteIndexValues(children[i], index);
093                                            }
094                                    }
095                            }
096                            return index;
097                    }
098            }
099    
100            public Palette createPalette()
101            {
102                    if (palette == null)
103                    {
104                            int numValues = assignPaletteIndexValues(root, 0);
105                            palette = new Palette(numValues);
106                            initPalette(root, palette);
107                            redValues = new int[numValues];
108                            greenValues = new int[numValues];
109                            blueValues = new int[numValues];
110                            for (int i = 0; i < numValues; i++)
111                            {
112                                    redValues[i] = palette.getSample(INDEX_RED, i);
113                                    greenValues[i] = palette.getSample(INDEX_GREEN, i);
114                                    blueValues[i] = palette.getSample(INDEX_BLUE, i);
115                            }
116                            return palette;
117                    }
118                    else
119                    {
120                            return (Palette)palette.clone();
121                    }
122            }
123    
124            /**
125             * Creates an octree and prepares this quantizer so that colors can be mapped to
126             * palette index values.
127             * If you use {@link #process()} you must not call this method.
128             * On the other hand, if you want to do the mapping yourself - maybe if you
129             * want to do mapping and dithering interchangeably - call this method first,
130             * then do the mapping yourself.
131             * @throws MissingParameterException if parameters like the input image are missing
132             * @throws WrongParameterException if parameters exist but are of the wrong type
133             */
134            public void init() throws
135                    MissingParameterException,
136                    WrongParameterException
137            {
138                    PixelImage pi = getInputImage();
139                    if (pi == null)
140                    {
141                            throw new MissingParameterException("Input image needed.");
142                    }
143                    if (!(pi instanceof RGB24Image))
144                    {
145                            throw new WrongParameterException("Input image must be of type RGB24Image.");
146                    }
147                    int numUniqueColors = initOctree();
148                    //System.out.println("# of unique colors=" + numUniqueColors);
149                    pruneOctree();
150            }
151    
152            private int initOctree()
153            {
154                    int numUniqueColors = 0;
155                    root = new OctreeNode();
156                    RGB24Image in = (RGB24Image)getInputImage();
157                    for (int y = 0; y < in.getHeight(); y++)
158                    {
159                            for (int x = 0; x < in.getWidth(); x++)
160                            {
161                                    int red = in.getSample(INDEX_RED, x, y);
162                                    int green = in.getSample(INDEX_GREEN, x, y);
163                                    int blue = in.getSample(INDEX_BLUE, x, y);
164                                    if (OctreeNode.add(root, red, green, blue, 8))
165                                    {
166                                            numUniqueColors++;
167                                    }
168                            }
169                    }
170                    root.copyChildSums();
171                    return numUniqueColors;
172            }
173    
174            private void initPalette(OctreeNode node, Palette palette)
175            {
176                    if (node == null)
177                    {
178                            return;
179                    }
180                    if (node.isLeaf())
181                    {
182                            int index = node.getPaletteIndex();
183                            palette.put(index, node.getRed(), node.getGreen(), node.getBlue());
184                            return;
185                    }
186                    OctreeNode[] children = node.getChildren();
187                    if (children == null)
188                    {
189                            return;
190                    }
191                    for (int i = 0; i < children.length; i++)
192                    {
193                            OctreeNode child = children[i];
194                            if (child != null)
195                            {
196                                    initPalette(child, palette);
197                            }
198                    }
199            }
200    
201            /**
202             * Maps an RGB color <code>origRgb</code> to one of the colors in the
203             * color map; that color will be written to <code>quantizedRgb</code>
204             * and its palette index will be returned.
205             * @param origRgb the color to be mapped to the best-possible counterpart in the
206             *  palette; the array is indexed by the constants from {@link RGBIndex}
207             * @param quantizedRgb the resulting color from the palette will be written
208             *  to this array; it is also indexed by the constants from {@link RGBIndex}
209             * @return index of the found color in the palette
210             */
211            public int map(int[] origRgb, int[] quantizedRgb)
212            {
213                    int result = root.map(origRgb, quantizedRgb);
214                    if (result == -1)
215                    {
216                            int minIndex = 0;
217                            int minDistance = Integer.MAX_VALUE;
218                            int i = 0;
219                            int red = origRgb[INDEX_RED];
220                            int green = origRgb[INDEX_GREEN];
221                            int blue = origRgb[INDEX_BLUE];
222                            while (i < redValues.length)
223                            {
224                                    int v = (redValues[i] - red);
225                                    int sum = v * v;
226                                    v = (greenValues[i] - green);
227                                    sum += v * v;
228                                    v = (blueValues[i] - blue);
229                                    sum += v * v;
230                                    if (sum < minDistance)
231                                    {
232                                            minIndex = i;
233                                            minDistance = sum;
234                                    }
235                                    i++;
236                            }
237                            quantizedRgb[INDEX_RED] = redValues[minIndex];
238                            quantizedRgb[INDEX_GREEN] = greenValues[minIndex];
239                            quantizedRgb[INDEX_BLUE] = blueValues[minIndex];
240                            return minIndex;
241                    }
242                    else
243                    {
244                            // quantizedRgb was filled with values in root.map
245                            return result;
246                    }
247            }
248    
249            private void mapImage()
250            {
251                    RGB24Image in = (RGB24Image)getInputImage();
252                    Palette palette = createPalette();
253                    Paletted8Image out = new MemoryPaletted8Image(in.getWidth(), in.getHeight(), palette);
254                    int[] origRgb = new int[3];
255                    int[] quantizedRgb = new int[3];
256                    for (int y = 0; y < in.getHeight(); y++)
257                    {
258                            for (int x = 0; x < in.getWidth(); x++)
259                            {
260                                    origRgb[INDEX_RED] = in.getSample(INDEX_RED, x, y);
261                                    origRgb[INDEX_GREEN] = in.getSample(INDEX_GREEN, x, y);
262                                    origRgb[INDEX_BLUE] = in.getSample(INDEX_BLUE, x, y);
263                                    int index = map(origRgb, quantizedRgb);
264                                    out.putSample(0, x, y, index);
265                            }
266                    }
267                    setOutputImage(out);
268            }
269    
270            /**
271             * Initializes an octree, reduces it have as many leaves (or less) as
272             * the desired palette size and maps the original image to the newly-created
273             * palette.
274             */
275            public void process() throws
276                    MissingParameterException,
277                    WrongParameterException
278            {
279                    init();
280                    mapImage();
281            }
282    
283            /**
284             * Reduces the octree until it has as many leaves (or less) than specified
285             * by the <code>paletteSize</code> argument in the constructor
286             * {@link #OctreeColorQuantizer(int)}.
287             */
288            private void pruneOctree()
289            {
290                    // create an array for as many palette entries as specified by paletteSize
291                    OctreeNode[] a = new OctreeNode[paletteSize];
292                    // initial length is 1, the only element is the root
293                    a[0] = root;
294                    int length = 1;
295                    // create a comparator that will be used to sort the nodes by their pixel count,
296                    // in ascending order
297                    OctreeNode comparator = new OctreeNode();
298                    // loop and split leaves as long as the number of nodes (length) is smaller
299                    // than the desired palette size
300                    while (length < paletteSize)
301                    {
302                            Sort.sort(a, 0, length - 1, comparator);
303                            int index = length - 1;
304                            while (index >= 0)
305                            {
306                                    OctreeNode node = a[index];
307                                    int numChildren = node.getNumChildren();
308                                    // check if current length minus the node which may be split
309                                    // plus the number of its children does not exceed the desired palette size
310                                    if (numChildren > 0 && length - 1 + numChildren < paletteSize)
311                                    {
312                                            // child nodes fit in here
313                                            if (index < length - 1)
314                                            {
315                                                    System.arraycopy(a, index + 1, a, index, length - index - 1);
316                                            }
317                                            length--;
318                                            OctreeNode[] children = node.getChildren();
319                                            for (int i = 0; i < children.length; i++)
320                                            {
321                                                    if (children[i] != null)
322                                                    {
323                                                            a[length++] = children[i];
324                                                    }
325                                            }
326                                            break;
327                                    }
328                                    else
329                                    {
330                                            index--;
331                                    }
332                            }
333                            if (index == -1)
334                            {
335                                    // we could not find a node to be split
336                                    break;
337                            }
338                    }
339                    // in some cases it is not possible to get exactly paletteSize leaves;
340                    // adjust paletteSize to be equal to the number of leaves
341                    // note that length will never be larger than paletteSize, only smaller
342                    // in some cases
343                    paletteSize = length; 
344                    // make all found nodes leaves by setting their child nodes to null
345                    for (int i = 0; i < length; i++)
346                    {
347                            a[i].setChildren(null);
348                    }
349            }
350    
351            public void setPaletteSize(int newPaletteSize)
352            {
353                    if (newPaletteSize < 1)
354                    {
355                            throw new IllegalArgumentException("Palette size must be 1 or larger.");
356                    }
357                    if (newPaletteSize > 256)
358                    {
359                            throw new IllegalArgumentException("Palette size must be 256 or smaller.");
360                    }
361                    paletteSize = newPaletteSize;
362            }
363    }