001    /*
002     * ArbitraryPaletteQuantizer
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    
021    /**
022     * A color quantizer that maps an {@link net.sourceforge.jiu.data.RGBImage} 
023     * to any given palette.
024     * This operation is restricted to RGB24Image and palettes with up to 256 colors.
025     * It picks the color from the palette which is closest to the 
026     * color to be quantized (with the minimum distance).
027     * This is a rather naive implementation which, for any given color
028     * to be quantized, computes the distance between it and each color
029     * in the palette (read: this operation is rather slow with a large palette and input image).
030     * <p>
031     * It uses <a target="_top" href="http://hissa.nist.gov/dads/HTML/manhttndstnc.html">Manhattan distance</a> (L<sub>1</sub>) 
032     * instead of <a target="_top" href="http://hissa.nist.gov/dads/HTML/euclidndstnc.html">Euclidean distance</a> (L<sub>2</sub>).
033     * This saves a square root operation per distance computation.
034     * <p>
035     * There are more sophisticated <a target="_top" 
036     * href="http://www.cs.sunysb.edu/~algorith/files/nearest-neighbor.shtml">nearest 
037     * neighbor</a> algorithms available, left for future extensions.
038     *
039     * <h3>Usage example</h3>
040     * <p>This example maps an RGB truecolor image to some palette
041     * we create.</p>
042     * <pre>
043     * RGB24Image image = ...; // initialize this
044     * // create some Palette object that you want to map the image to
045     * Palette palette = new Palette(3); // create palette with three entries
046     * palette.put(0, 33, 00, 244); // set first color
047     * palette.put(1, 0, 240, 193); // set second color
048     * palette.put(2, 245, 126, 136); // set third color
049     * ArbitraryPaletteQuantizer quantizer = new ArbitraryPaletteQuantizer(palette);
050     * quantizer.setInputImage(image);
051     * quantizer.process();
052     * PixelImage quantizedImage = quantizer.getOutputImage();
053     * </pre>
054     *
055     * @author Marco Schmidt
056     * @since 0.5.0
057     */
058    public class ArbitraryPaletteQuantizer extends ImageToImageOperation implements RGBIndex, RGBQuantizer
059    {
060            private final int[] RED;
061            private final int[] GREEN;
062            private final int[] BLUE;
063            private Palette palette;
064            private int numEntries;
065    
066            /**
067             * Creates a quantizer that will be able to map pixels (or a complete image)
068             * to the argument palette.
069             */
070            public ArbitraryPaletteQuantizer(Palette palette)
071            {
072                    this.palette = palette;
073                    numEntries = palette.getNumEntries();
074                    // create 1D lookup tables for the three components and fill them with
075                    // the palette entry data
076                    RED = new int[numEntries];
077                    GREEN = new int[numEntries];
078                    BLUE = new int[numEntries];
079                    for (int i = 0; i < numEntries; i++)
080                    {
081                            RED[i] = palette.getSample(INDEX_RED, i);
082                            GREEN[i] = palette.getSample(INDEX_GREEN, i);
083                            BLUE[i] = palette.getSample(INDEX_BLUE, i);
084                    }
085            }
086    
087            /**
088             * Returns a copy of the palette that was given to the
089             * constructor of this class.
090             * @return new copy of the palette this quantizer works on
091             */
092            public Palette createPalette()
093            {
094                    return (Palette)palette.clone();
095            }
096    
097            public int map(int[] origRgb, int[] quantizedRgb)
098            {
099                    int r = origRgb[INDEX_RED];
100                    int g = origRgb[INDEX_GREEN];
101                    int b = origRgb[INDEX_BLUE];
102                    int minIndex = 0;
103                    int minDistance = Integer.MAX_VALUE;
104                    for (int index = 0; index < numEntries; index++)
105                    {
106                            int v = r - RED[index];
107                            int distance = v * v; 
108                            v = g - GREEN[index];
109                            distance += v * v;
110                            v = b - BLUE[index];
111                            distance += v * v;
112                            if (distance < minDistance)
113                            {
114                                    minDistance = distance;
115                                    minIndex = index;
116                            }
117                    }
118                    quantizedRgb[INDEX_RED] = RED[minIndex];
119                    quantizedRgb[INDEX_GREEN] = GREEN[minIndex];
120                    quantizedRgb[INDEX_BLUE] = BLUE[minIndex];
121                    return minIndex;
122            }
123    
124            /**
125             * Finds the best match for the argument color in the palette and returns 
126             * its index.
127             * Similar to {@link #map(int[], int[])}, the quantized color is not required
128             * and thus a few assignemnts are saved by this method.
129             * @param red red sample of the pixel to be quantized
130             * @param green green sample of the pixel to be quantized
131             * @param blue blue sample of the pixel to be quantized
132             * @return index of the color in the palette that is closest to the argument color
133             */
134            public int map(int red, int green, int blue)
135            {
136                    int minIndex = 0;
137                    int minDistance = Integer.MAX_VALUE;
138                    for (int index = 0; index < numEntries; index++)
139                    {
140                            int v = red - RED[index];
141                            int distance = v * v; 
142                            v = green - GREEN[index];
143                            distance += v * v;
144                            v = blue - BLUE[index];
145                            distance += v * v;
146                            if (distance < minDistance)
147                            {
148                                    minDistance = distance;
149                                    minIndex = index;
150                            }
151                    }
152                    return minIndex;
153            }
154    
155            private void process(RGB24Image in, Paletted8Image out)
156            {
157                    final int WIDTH = in.getWidth();
158                    final int HEIGHT = in.getHeight();
159                    if (out == null)
160                    {
161                            out = new MemoryPaletted8Image(WIDTH, HEIGHT, createPalette());
162                    }
163                    for (int y = 0; y < HEIGHT; y++)
164                    {
165                            for (int x = 0; x < WIDTH; x++)
166                            {
167                                    out.putSample(0, x, y, map(in.getSample(INDEX_RED, x, y), in.getSample(INDEX_GREEN, x, y), in.getSample(INDEX_BLUE, x, y)));
168                            }
169                            setProgress(y, HEIGHT);
170                    }
171                    setOutputImage(out);
172            }
173    
174            /**
175             * Maps the input image to an output image, using the palette given to the constructor.
176             */
177            public void process() throws 
178                    MissingParameterException,
179                    WrongParameterException
180            {
181                    ensureInputImageIsAvailable();
182                    PixelImage in = getInputImage();
183                    if (!(in instanceof RGB24Image))
184                    {
185                            throw new WrongParameterException("Input image must be of type RGB24Image.");
186                    }
187                    PixelImage out = getOutputImage();
188                    if (out != null && !(out instanceof Paletted8Image))
189                    {
190                            throw new WrongParameterException("Output image must be of type Paletted8Image.");
191                    }
192                    process((RGB24Image)in, (Paletted8Image)out);
193            }
194    }