001    /*
002     * OrderedDither
003     * 
004     * Copyright (c) 2001, 2002, 2003 Marco Schmidt.
005     * All rights reserved.
006     */
007    
008    package net.sourceforge.jiu.color.dithering;
009    
010    import net.sourceforge.jiu.color.quantization.UniformPaletteQuantizer;
011    import net.sourceforge.jiu.data.BilevelImage;
012    import net.sourceforge.jiu.data.Gray8Image;
013    import net.sourceforge.jiu.data.MemoryBilevelImage;
014    import net.sourceforge.jiu.data.MemoryGray8Image;
015    import net.sourceforge.jiu.data.MemoryPaletted8Image;
016    import net.sourceforge.jiu.data.MemoryRGB24Image;
017    import net.sourceforge.jiu.data.PixelImage;
018    import net.sourceforge.jiu.data.Paletted8Image;
019    import net.sourceforge.jiu.data.RGB24Image;
020    import net.sourceforge.jiu.data.RGBIndex;
021    import net.sourceforge.jiu.ops.ImageToImageOperation;
022    import net.sourceforge.jiu.ops.MissingParameterException;
023    import net.sourceforge.jiu.ops.WrongParameterException;
024    
025    /**
026     * This operation reduces the color depth of RGB truecolor images and grayscale images
027     * by applying ordered dithering.
028     * A relatively nice output image (for a human observer) will be created at the 
029     * cost of introducing noise into the output image.
030     * The algorithm is relatively fast, but its quality is usually inferior to what
031     * can be reached by using {@link ErrorDiffusionDithering} or similar other methods.
032     * <h3>Supported conversions</h3>
033     * <ul>
034     * <li><strong>Grayscale to bilevel</strong> maps GrayIntegerImage objects
035     *  to BilevelImage objects.</li>
036     * <li><strong>Grayscale to grayscale</strong> maps GrayIntegerImage objects
037     *  to other GrayIntegerImage objects.
038     *  Right now, only Gray8Image objects are supported.
039     *  After reducing the number of bits, each sample is immediately scaled back
040     *  to 8 bits per pixel in order to fit into another Gray8Image object.</li>
041     * <li><strong>Truecolor to paletted</strong> maps RGBIntegerImage objects
042     *  to Paletted8Image objects; the sum of the output bits must not be larger
043     *  than 8</li>
044     * </ul>
045     * <h3>Usage example</h3>
046     * The following code snippet demonstrates how to create a paletted
047     * image with 256 colors, using three bits for red and green and two
048     * bits for blue, from an RGB truecolor image.
049     * <pre>
050     * OrderedDither od = new OrderedDither();
051     * od.setRgbBits(3, 3, 2);
052     * od.setInputImage(image);
053     * od.process();
054     * Paletted8Image ditheredImage = (Paletted8Image)od.getOutputImage();
055     * </pre>
056     * @author Marco Schmidt
057     */
058    public class OrderedDither extends ImageToImageOperation implements RGBIndex
059    {
060            private int[] values;
061            private int valueWidth;
062            private int valueHeight;
063            private int grayBits = 3;
064            private int redBits = 3;
065            private int greenBits = 3;
066            private int blueBits = 2;
067    
068            private void process(Gray8Image in, Gray8Image out)
069            {
070                    if (out == null)
071                    {
072                            out = new MemoryGray8Image(in.getWidth(), in.getHeight());
073                            setOutputImage(out);
074                    }
075                    int D1 = 4;
076                    int D2 = 4;
077                    int D1D2 = D1 * D2;
078                    final int[] DITHER_MATRIX = {0, 8, 2, 10, 12, 4, 14, 6, 3, 11, 1, 9, 15, 7, 13, 5};
079                    final int SPACE = 255 / ((1 << grayBits) - 1);
080                    final int SHIFT = 8 - grayBits;
081                    final int NUM_VALUES = 1 << grayBits;
082                    final byte[] OUTPUT_SAMPLES = new byte[NUM_VALUES];
083                    for (int i = 0; i < OUTPUT_SAMPLES.length; i++)
084                    {
085                            OUTPUT_SAMPLES[i] = (byte)((i * 255) / NUM_VALUES);
086                    }
087                    final int[] DITHER_SIGNAL = new int[D1D2];
088                    for (int i = 0; i < D1D2; i++)
089                    {
090                            DITHER_SIGNAL[i] = (2 * DITHER_MATRIX[i] - D1D2 + 1) * SPACE / (2 * D1D2);
091                    }
092                    final int HEIGHT = in.getHeight();
093                    final int WIDTH = in.getWidth();
094                    int rowOffset = 0;
095                    for (int y = 0; y < HEIGHT; y++)
096                    {
097                            int offset = rowOffset;
098                            final int MAX_OFFSET = rowOffset + D1;
099                            for (int x = 0; x < WIDTH; x++)
100                            {
101                                    int sample = in.getSample(0, x, y);
102                                    sample = sample + DITHER_SIGNAL[ offset++ ];
103                                    if (offset == MAX_OFFSET)
104                                    {
105                                            offset = rowOffset;
106                                    }
107                                    if (sample < 0)
108                                    {
109                                            sample = 0;
110                                    }
111                                    else
112                                    if (sample > 255)
113                                    {
114                                            sample = 255;
115                                    }
116                                    out.putByteSample(0, x, y, OUTPUT_SAMPLES[sample >> SHIFT]);
117                            }
118                            rowOffset += D1;
119                            if (rowOffset >= DITHER_SIGNAL.length)
120                            {
121                                    rowOffset = 0;
122                            }
123                            setProgress(y, HEIGHT);
124                    }
125            }
126    
127            private void process(Gray8Image in, BilevelImage out)
128            {
129                    if (out == null)
130                    {
131                            out = new MemoryBilevelImage(in.getWidth(), in.getHeight());
132                            setOutputImage(out);
133                    }
134                    if (values == null)
135                    {
136                            setStandardThresholdValues();
137                    }
138                    out.clear(BilevelImage.BLACK);
139                    int rowOffset = 0;
140                    final int HEIGHT = in.getHeight();
141                    for (int y = 0; y < HEIGHT; y++)
142                    {
143                            int offset = rowOffset;
144                            final int MAX_OFFSET = rowOffset + valueWidth;
145                            for (int x = 0; x < in.getWidth(); x++)
146                            {
147                                    if (in.getSample(x, y) >= values[offset++])
148                                    {
149                                            out.putWhite(x, y);
150                                    }
151                                    if (offset == MAX_OFFSET)
152                                    {
153                                            offset = rowOffset;
154                                    }
155                            }
156                            setProgress(y, HEIGHT);
157                            rowOffset += valueWidth;
158                            if (rowOffset >= values.length)
159                            {
160                                    rowOffset = 0;
161                            }
162                    }
163            }
164    
165            private void process(RGB24Image in, Paletted8Image out)
166            {
167                    UniformPaletteQuantizer upq = new UniformPaletteQuantizer(redBits, greenBits, blueBits);
168                    if (out == null)
169                    {
170                            out = new MemoryPaletted8Image(in.getWidth(), in.getHeight(), upq.createPalette());
171                            setOutputImage(out);
172                    }
173                    int D1 = 4;
174                    int D2 = 4;
175                    int D1D2 = D1 * D2;
176                    final int[] DITHER_MATRIX = {0, 8, 2, 10, 12, 4, 14, 6, 3, 11, 1, 9, 15, 7, 13, 5};
177                    final int RED_SPACE = 255 / ((1 << redBits) - 1);
178                    final int GREEN_SPACE = 255 / ((1 << greenBits) - 1);
179                    final int BLUE_SPACE = 255 / ((1 << blueBits) - 1);
180                    final int RED_SHIFT = 8 - redBits;
181                    final int GREEN_SHIFT = 8 - redBits;
182                    final int BLUE_SHIFT = 8 - redBits;
183                    final int NUM_RED_VALUES = 1 << redBits;
184                    final int NUM_GREEN_VALUES = 1 << greenBits;
185                    final int NUM_BLUE_VALUES = 1 << blueBits;
186                    final int[] RED_DITHER_SIGNAL = new int[D1D2];
187                    final int[] GREEN_DITHER_SIGNAL = new int[D1D2];
188                    final int[] BLUE_DITHER_SIGNAL = new int[D1D2];
189                    for (int i = 0; i < D1D2; i++)
190                    {
191                            RED_DITHER_SIGNAL[i] = (2 * DITHER_MATRIX[i] - D1D2 + 1) * RED_SPACE / (2 * D1D2);
192                            GREEN_DITHER_SIGNAL[i] = (2 * DITHER_MATRIX[i] - D1D2 + 1) * GREEN_SPACE / (2 * D1D2);
193                            BLUE_DITHER_SIGNAL[i] = (2 * DITHER_MATRIX[i] - D1D2 + 1) * BLUE_SPACE / (2 * D1D2);
194                    }
195                    final int HEIGHT = in.getHeight();
196                    final int WIDTH = in.getWidth();
197                    int rowOffset = 0;
198                    for (int y = 0; y < HEIGHT; y++)
199                    {
200                            int offset = rowOffset;
201                            final int MAX_OFFSET = rowOffset + D1;
202                            for (int x = 0; x < WIDTH; x++)
203                            {
204                                    int redSample = in.getSample(INDEX_RED, x, y);
205                                    redSample = redSample + RED_DITHER_SIGNAL[ offset ];
206                                    if (redSample < 0)
207                                    {
208                                            redSample = 0;
209                                    }
210                                    else
211                                    if (redSample > 255)
212                                    {
213                                            redSample = 255;
214                                    }
215                                    int greenSample = in.getSample(INDEX_GREEN, x, y);
216                                    greenSample = greenSample + GREEN_DITHER_SIGNAL[ offset ];
217                                    if (greenSample < 0)
218                                    {
219                                            greenSample = 0;
220                                    }
221                                    else
222                                    if (greenSample > 255)
223                                    {
224                                            greenSample = 255;
225                                    }
226                                    int blueSample = in.getSample(INDEX_BLUE, x, y);
227                                    blueSample = blueSample + BLUE_DITHER_SIGNAL[ offset ];
228                                    if (blueSample < 0)
229                                    {
230                                            blueSample = 0;
231                                    }
232                                    else
233                                    if (blueSample > 255)
234                                    {
235                                            blueSample = 255;
236                                    }
237                                    out.putSample(0, x, y, upq.mapToIndex(redSample, greenSample, blueSample));
238                                    offset++;
239                                    if (offset == MAX_OFFSET)
240                                    {
241                                            offset = rowOffset;
242                                    }
243                            }
244                            rowOffset += D1;
245                            if (rowOffset >= DITHER_MATRIX.length)
246                            {
247                                    rowOffset = 0;
248                            }
249                            setProgress(y, HEIGHT);
250                    }
251            }
252    
253            private void process(RGB24Image in, RGB24Image out)
254            {
255                    //UniformPaletteQuantizer upq = new UniformPaletteQuantizer(redBits, greenBits, blueBits);
256                    //System.out.println("RGB=>RGB, r=" + redBits+  ", g=" + greenBits + ", b=" + blueBits);
257                    if (out == null)
258                    {
259                            out = new MemoryRGB24Image(in.getWidth(), in.getHeight());
260                            setOutputImage(out);
261                    }
262                    int D1 = 4;
263                    int D2 = 4;
264                    int D1D2 = D1 * D2;
265                    final int[] DITHER_MATRIX = {0, 8, 2, 10, 12, 4, 14, 6, 3, 11, 1, 9, 15, 7, 13, 5};
266                    final int RED_SPACE = 255 / ((1 << redBits) - 1);
267                    final int GREEN_SPACE = 255 / ((1 << greenBits) - 1);
268                    final int BLUE_SPACE = 255 / ((1 << blueBits) - 1);
269                    final int RED_SHIFT = 8 - redBits;
270                    final int GREEN_SHIFT = 8 - greenBits;
271                    final int BLUE_SHIFT = 8 - blueBits;
272                    final int MAX_RED = (1 << redBits) - 1;
273                    final int MAX_GREEN = (1 << greenBits) - 1;
274                    final int MAX_BLUE = (1 << blueBits) - 1;
275                    final int NUM_RED_VALUES = 1 << redBits;
276                    final int NUM_GREEN_VALUES = 1 << greenBits;
277                    final int NUM_BLUE_VALUES = 1 << blueBits;
278                    final int[] RED_DITHER_SIGNAL = new int[D1D2];
279                    final int[] GREEN_DITHER_SIGNAL = new int[D1D2];
280                    final int[] BLUE_DITHER_SIGNAL = new int[D1D2];
281                    for (int i = 0; i < D1D2; i++)
282                    {
283                            RED_DITHER_SIGNAL[i] = (2 * DITHER_MATRIX[i] - D1D2 + 1) * RED_SPACE / (2 * D1D2);
284                            GREEN_DITHER_SIGNAL[i] = (2 * DITHER_MATRIX[i] - D1D2 + 1) * GREEN_SPACE / (2 * D1D2);
285                            BLUE_DITHER_SIGNAL[i] = (2 * DITHER_MATRIX[i] - D1D2 + 1) * BLUE_SPACE / (2 * D1D2);
286                    }
287                    final int HEIGHT = in.getHeight();
288                    final int WIDTH = in.getWidth();
289                    int rowOffset = 0;
290                    for (int y = 0; y < HEIGHT; y++)
291                    {
292                            int offset = rowOffset;
293                            final int MAX_OFFSET = rowOffset + D1;
294                            for (int x = 0; x < WIDTH; x++)
295                            {
296                                    // RED
297                                    int redSample = in.getSample(INDEX_RED, x, y);
298                                    redSample = redSample + RED_DITHER_SIGNAL[ offset ];
299                                    if (redSample < 0)
300                                    {
301                                            redSample = 0;
302                                    }
303                                    else
304                                    if (redSample > 255)
305                                    {
306                                            redSample = 255;
307                                    }
308                                    redSample >>= RED_SHIFT;
309                                    out.putSample(RGBIndex.INDEX_RED, x, y, redSample * 255 / MAX_RED);
310                                    // GREEN
311                                    int greenSample = in.getSample(INDEX_GREEN, x, y);
312                                    greenSample = greenSample + GREEN_DITHER_SIGNAL[ offset ];
313                                    if (greenSample < 0)
314                                    {
315                                            greenSample = 0;
316                                    }
317                                    else
318                                    if (greenSample > 255)
319                                    {
320                                            greenSample = 255;
321                                    }
322                                    greenSample >>= GREEN_SHIFT;
323                                    out.putSample(RGBIndex.INDEX_GREEN, x, y, greenSample * 255 / MAX_GREEN);
324                                    // BLUE
325                                    int blueSample = in.getSample(INDEX_BLUE, x, y);
326                                    blueSample = blueSample + BLUE_DITHER_SIGNAL[offset];
327                                    if (blueSample < 0)
328                                    {
329                                            blueSample = 0;
330                                    }
331                                    else
332                                    if (blueSample > 255)
333                                    {
334                                            blueSample = 255;
335                                    }
336                                    blueSample >>= BLUE_SHIFT;
337                                    out.putSample(RGBIndex.INDEX_BLUE, x, y, blueSample * 255 / MAX_BLUE);
338                                    //out.putSample(0, x, y, upq.mapToIndex(redSample, greenSample, blueSample));
339                                    offset++;
340                                    if (offset == MAX_OFFSET)
341                                    {
342                                            offset = rowOffset;
343                                    }
344                            }
345                            rowOffset += D1;
346                            if (rowOffset >= DITHER_MATRIX.length)
347                            {
348                                    rowOffset = 0;
349                            }
350                            setProgress(y, HEIGHT);
351                    }
352            }
353    
354            public void process() throws
355                    MissingParameterException,
356                    WrongParameterException
357            {
358                    ensureInputImageIsAvailable();
359                    ensureImagesHaveSameResolution();
360                    PixelImage in = getInputImage();
361                    PixelImage out = getOutputImage();
362                    if (in instanceof RGB24Image)
363                    {
364                            int sum = redBits + greenBits + blueBits;
365                            if (sum > 8)
366                            {
367                                    process((RGB24Image)in, (RGB24Image)out);
368                            }
369                            else
370                            {
371                                    process((RGB24Image)in, (Paletted8Image)out);
372                            }
373                    }
374                    else
375                    if (grayBits == 1)
376                    {
377                            process((Gray8Image)in, (BilevelImage)out);
378                    }
379                    else
380                    if (grayBits >= 2 && grayBits <= 7)
381                    {
382                            process((Gray8Image)in, (Gray8Image)out);
383                    }
384            }
385    
386            public void setOutputBits(int bits)
387            {
388                    if (bits >= 1 && bits <= 7)
389                    {
390                            grayBits = bits;
391                    }
392                    else
393                    {
394                            throw new IllegalArgumentException("Grayscale output bits must be from 1..7; got " + bits);
395                    }
396            }
397    
398            /**
399             * Sets the number of bits to be used for each RGB component in the output image.
400             * Each argument must be one or larger.
401             * The values defined by this method are only used if the input image implements
402             * RGBIntegerImage.
403             * Later, in {@link #process}, these values are checked against
404             * the actual number of bits per component in the input image.
405             * If any of the arguments of this method is equal to or larger 
406             * than those actual bits per channel values, a WrongParameterException
407             * will then be thrown.
408             * Right now, there is no way how this can be checked, because
409             * the input image may not have been defined yet.
410             * @param red number of bits for the red channel in the output image
411             * @param green number of bits for the green channel in the output image
412             * @param blue number of bits for the blue channel in the output image
413             * @throws IllegalArgumentException if at least one argument is smaller than <code>1</code>
414             */
415            public void setRgbBits(int red, int green, int blue)
416            {
417                    if (red > 0 && green > 0 && blue > 0)
418                    {
419                            redBits = red;
420                            greenBits = green;
421                            blueBits = blue;
422                    }
423                    else
424                    {
425                            throw new IllegalArgumentException("All parameters must be 1 or larger.");
426                    }
427            }
428    
429            /**
430             * Calls {@link #setThresholdValues} with a 16 x 16 matrix.
431             */
432            public void setStandardThresholdValues()
433            {
434                    final int[] VALUES =
435                    {
436                       0,192, 48,240, 12,204, 60,252,  3,195, 51,243, 15,207, 63,255,
437                     128, 64,176,112,140, 76,188,124,131, 67,179,115,143, 79,191,127,
438                      32,224, 16,208, 44,236, 28,220, 35,227, 19,211, 47,239, 31,223,
439                     160, 96,144, 80,172,108,156, 92,163, 99,147, 83,175,111,159, 95,
440                       8,200, 56,248,  4,196, 52,244, 11,203, 59,251,  7,199, 55,247,
441                     136, 72,184,120,132, 68,180,116,139, 75,187,123,135, 71,183,119,
442                      40,232, 24,216, 36,228, 20,212, 43,235, 27,219, 39,231, 23,215,
443                     168,104,152, 88,164,100,148, 84,171,107,155, 91,167,103,151, 87,
444                       2,194, 50,242, 14,206, 62,254,  1,193, 49,241, 13,205, 61,253,
445                     130, 66,178,114,142, 78,190,126,129, 65,177,113,141, 77,189,125,
446                      34,226, 18,210, 46,238, 30,222, 33,225, 17,209, 45,237, 29,221,
447                     162, 98,146, 82,174,110,158, 94,161, 97,145, 81,173,109,157, 93,
448                      10,202, 58,250,  6,198, 54,246,  9,201, 57,249,  5,197, 53,245,
449                     138, 74,186,122,134, 70,182,118,137, 73,185,121,133, 69,181,117,
450                      42,234, 26,218, 38,230, 22,214, 41,233, 25,217, 37,229, 21,213,
451                     170,106,154, 90,166,102,150, 86,169,105,153, 89,165,101,149, 85
452                    };
453                    setThresholdValues(VALUES, 16, 16);
454            }
455    
456            /**
457             * Defines a matrix of threshold values that will be used for grayscale
458             * dithering.
459             * @param values the int values to use for comparing
460             * @param valueWidth 
461             * @param valueHeight
462             */
463            public void setThresholdValues(int[] values, int valueWidth, int valueHeight)
464            {
465                    if (values == null)
466                    {
467                            throw new IllegalArgumentException("The value array must be non-null.");
468                    }
469                    if (valueWidth < 1)
470                    {
471                            throw new IllegalArgumentException("The width argument must be at least 1.");
472                    }
473                    if (valueHeight < 1)
474                    {
475                            throw new IllegalArgumentException("The height argument must be at least 1.");
476                    }
477                    if (valueHeight * valueWidth < values.length)
478                    {
479                            throw new IllegalArgumentException("The array must have at least valuesWidth * valuesHeight elements..");
480                    }
481                    this.values = values;
482                    this.valueWidth = valueWidth;
483                    this.valueHeight = valueHeight;
484            }
485    }