001    /*
002     * ErrorDiffusionDithering
003     * 
004     * Copyright (c) 2001, 2002, 2003, 2004 Marco Schmidt.
005     * All rights reserved.
006     */
007    
008    package net.sourceforge.jiu.color.dithering;
009    
010    import net.sourceforge.jiu.color.quantization.RGBQuantizer;
011    import net.sourceforge.jiu.data.BilevelImage;
012    import net.sourceforge.jiu.data.Gray8Image;
013    import net.sourceforge.jiu.data.IntegerImage;
014    import net.sourceforge.jiu.data.MemoryBilevelImage;
015    import net.sourceforge.jiu.data.MemoryGray8Image;
016    import net.sourceforge.jiu.data.MemoryPaletted8Image;
017    import net.sourceforge.jiu.data.Paletted8Image;
018    import net.sourceforge.jiu.data.PixelImage;
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 class is used to apply error diffusion dithering to images that are being reduced in their color depth.
027     * Works with {@link net.sourceforge.jiu.data.GrayIntegerImage} and
028     * {@link net.sourceforge.jiu.data.RGBIntegerImage} objects.
029     * For RGB images, a quantizer must be specified via {@link #setQuantizer}.
030     * That quantizer must have been initialized (it must have searched for / given a palette that it can map to).
031     * <p>
032     * This class offers six predefined types of error diffusion dithering.
033     * In addition, user-defined types can be integrated by providing a
034     * information on how the error is to be distributed; see the 
035     * description of {@link #setTemplateData}.
036     *
037     * <h3>Usage examples</h3>
038     * <h4>Color</h4>
039     * This small program maps some RGB24Image object to a Paletted8Image
040     * with 120 entries in its palette, using Stucki error
041     * diffusion dithering in combination with an octree color quantizer.
042     * <pre>
043     * MemoryRGB24Image image = ...; // some RGB image
044     * OctreeColorQuantizer quantizer = new OctreeColorQuantizer();
045     * quantizer.setInputImage(image);
046     * quantizer.setPaletteSize(120);
047     * quantizer.init();
048     * ErrorDiffusionDithering edd = new ErrorDiffusionDithering();
049     * edd.setType(ErrorDiffusionDithering.TYPE_STUCKI);
050     * edd.setQuantizer(quantizer);
051     * edd.setInputImage(image);
052     * edd.process();
053     * PixelImage quantizedImage = edd.getOutputImage();
054     * </pre>
055     * <h4>Grayscale to black and white</h4>
056     * In this example, a {@link net.sourceforge.jiu.data.Gray8Image} object
057     * is reduced to black and white using Floyd-Steinberg dithering.
058     * <pre>
059     * Gray8Image image = ...; // some grayscale image
060     * ErrorDiffusionDithering edd = new ErrorDiffusionDithering();
061     * edd.setGrayscaleOutputBits(1);
062     * edd.setInputImage(image);
063     * edd.process();
064     * PixelImage ditheredImage = edd.getOutputImage();
065     * // if you need something more specific than PixelImage: 
066     * BilevelImage output = null;
067     * // ditheredImage should be a BilevelImage...
068     * if (ditheredImage instanceof BilevelImage
069     * {
070     *   // ... and it is!
071     *   output = (BilevelImage)ditheredImage;
072     * }
073     * </pre>
074     * <h3>TODO</h3>
075     * Adjust this class to be able to process 16 bits per sample.
076     * <h3>Theoretical background</h3>
077     * The predefined templates were taken from the book <em>Bit-mapped 
078     * graphics</em> (2nd edition) by Steve Rimmer, published by 
079     * Windcrest / McGraw-Hill, ISBN 0-8306-4208-0.
080     * The part on error diffusion dithering starts on page 375.
081     * <p>
082     * Several sources recommend Robert Ulichney's book
083     * <a target="_top"
084     * href="http://crl.research.compaq.com/who/people/ulichney/bib/DigitalHalftoning/Digital-Halftoning.html"><em>Digital
085     * Halftoning</em></a> for this topic (published by The MIT Press, ISBN 0-262-21009-6).
086     * Unfortunately, I wasn't able to get a copy (or the CD-ROM version published by
087     * <a target="_top" href="http://www.ddj.com">Dr. Dobb's Journal</a>).
088     *
089     * @since 0.5.0
090     * @author Marco Schmidt
091     */
092    public class ErrorDiffusionDithering extends ImageToImageOperation implements RGBIndex
093    {
094            /**
095             * Constant for Floyd-Steinberg error diffusion.
096             * The quantization error is distributed to four neighboring pixels.
097             */
098            public static final int TYPE_FLOYD_STEINBERG = 0;
099    
100            /**
101             * Constant for Stucki error diffusion.
102             * The quantization error is distributed to twelve neighboring pixels.
103             */
104            public static final int TYPE_STUCKI = 1;
105    
106            /**
107             * Constant for Burkes error diffusion.
108             * The quantization error is distributed to seven neighboring pixels.
109             */
110            public static final int TYPE_BURKES = 2;
111    
112            /**
113             * Constant for Burkes error diffusion.
114             * The quantization error is distributed to ten neighboring pixels.
115             */
116            public static final int TYPE_SIERRA = 3;
117    
118            /**
119             * Constant for Burkes error diffusion.
120             * The quantization error is distributed to twelve neighboring pixels.
121             */
122            public static final int TYPE_JARVIS_JUDICE_NINKE= 4;
123    
124            /**
125             * Constant for Burkes error diffusion.
126             * The quantization error is distributed to twelve neighboring pixels.
127             */
128            public static final int TYPE_STEVENSON_ARCE = 5;
129    
130            /**
131             * The default error diffusion type, to be used if none is specified by the user.
132             */
133            public static final int DEFAULT_TYPE = TYPE_FLOYD_STEINBERG;
134    
135            /**
136             * The index for the horizontal position of a neighbor pixel.
137             * For a description, see the constructor {@link #setTemplateData}.
138             */
139            public static final int INDEX_X_POS = 0;
140    
141            /**
142             * The index for the vertical position of a neighbor pixel.
143             * For a description, see the constructor {@link #setTemplateData}.
144             */
145            public static final int INDEX_Y_POS = 1;
146    
147            /**
148             * The index of the numerator of the relative part of the error of a neighbor pixel.
149             * For a description, see the constructor {@link #setTemplateData}.
150             */
151            public static final int INDEX_ERROR_NUMERATOR = 2;
152    
153            /**
154             * The index of the denominator of the relative part of the error of a neighbor pixel.
155             * For a description, see the constructor {@link #setTemplateData}.
156             */
157            public static final int INDEX_ERROR_DENOMINATOR = 3;
158    
159            private static final int[][] FLOYD_STEINBERG_DATA =
160                    {{ 1,  0, 7, 16},
161                     {-1,  1, 3, 16},
162                     { 0,  1, 5, 16},
163                     { 1,  1, 1, 16}};
164            private static final int[][] STUCKI_DATA =
165                    {{ 1,  0, 8, 42},
166                     { 2,  0, 4, 42},
167                     {-2,  1, 2, 42},
168                     {-1,  1, 4, 42},
169                     { 0,  1, 8, 42},
170                     { 1,  1, 4, 42},
171                     { 2,  1, 2, 42},
172                     {-2,  2, 1, 42},
173                     {-1,  2, 2, 42},
174                     { 0,  2, 4, 42},
175                     { 1,  2, 2, 42},
176                     { 2,  2, 1, 42}};
177            private static final int[][] BURKES_DATA =
178                    {{ 1,  0, 8, 32},
179                     { 2,  0, 4, 32},
180                     {-2,  1, 2, 32},
181                     {-1,  1, 4, 32},
182                     { 0,  1, 8, 32},
183                     { 1,  1, 4, 32},
184                     { 2,  1, 2, 32}};
185            private static final int[][] SIERRA_DATA =
186                    {{ 1,  0, 5, 32},
187                     { 2,  1, 3, 32},
188                     {-2,  1, 2, 32},
189                     {-1,  1, 4, 32},
190                     { 0,  1, 5, 32},
191                     { 1,  1, 4, 32},
192                     { 2,  1, 2, 32},
193                     {-1,  2, 2, 32},
194                     { 0,  2, 3, 32},
195                     { 1,  2, 2, 32}};
196            private static final int[][] JARVIS_JUDICE_NINKE_DATA =
197                    {{ 1,  0, 7, 48},
198                     { 2,  0, 5, 48},
199                     {-2,  1, 3, 48},
200                     {-1,  1, 5, 48},
201                     { 0,  1, 7, 48},
202                     { 1,  1, 5, 48},
203                     { 2,  1, 3, 48},
204                     {-2,  2, 1, 48},
205                     {-1,  2, 3, 48},
206                     { 0,  2, 5, 48},
207                     { 1,  2, 3, 48},
208                     { 2,  2, 1, 48}};
209            private static final int[][] STEVENSON_ARCE_DATA =
210                    {{ 2,  0, 32, 200},
211                     {-3,  1, 12, 200},
212                     {-1,  1, 26, 200},
213                     { 1,  1, 30, 200},
214                     { 3,  1, 16, 200},
215                     {-2,  2, 12, 200},
216                     { 0,  2, 26, 200},
217                     { 2,  2, 12, 200},
218                     {-3,  3,  5, 200},
219                     {-1,  3, 12, 200},
220                     { 1,  3, 12, 200},
221                     { 3,  3,  5, 200}};
222            private int grayBits;
223            private int imageWidth;
224            private int leftColumns;
225            private int rightColumns;
226            private int newWidth;
227            private int numRows;
228            private int[][] templateData;
229            private int[] errorNum;
230            private int[] errorDen;
231            private int[] indexLut;
232            private RGBQuantizer quantizer;
233            private boolean useTruecolorOutput;
234    
235            /**
236             * Creates a new object of this class and set the dithering type to
237             * {@link #DEFAULT_TYPE}.
238             */
239            public ErrorDiffusionDithering()
240            {
241                    setTemplateType(DEFAULT_TYPE);
242            }
243    
244            /**
245             * Clamps the argument value to interval 0..max.
246             * @param value the value to be adjusted
247             * @param max the maximum allowed value (minimum is always 0)
248             * @return the adjusted value
249             */
250            private static int adjust(int value, int max)
251            {
252                    if (value <= 0)
253                    {
254                            return 0;
255                    }
256                    else
257                    if (value > max)
258                    {
259                            return max;
260                    }
261                    else
262                    {
263                            return value;
264                    }
265            }
266    
267            /**
268             * Copies data from input image to argument buffer.
269             * @param channelIndex index of the channel of the input image from which data is to be copied
270             * @param rowIndex index of the row of the input image from which data is to be copied
271             * @param dest the array to which data is to be copied
272             * @param destOffset index of the first element in the dest array to which data will be copied
273             */
274            private void fillBuffer(int channelIndex, int rowIndex, int[] dest, int destOffset)
275            {
276                    IntegerImage in = (IntegerImage)getInputImage();
277                    final int LAST = destOffset + imageWidth;
278                    int x = 0;
279                    while (destOffset != LAST)
280                    {
281                            dest[destOffset++] = in.getSample(channelIndex, x++, rowIndex);
282                    }
283            }
284    
285            private void init(int[][] data, int imageWidth)
286            {
287                    if (data == null)
288                    {
289                            throw new IllegalArgumentException("Data must not be null.");
290                    }
291                    if (imageWidth < 1)
292                    {
293                            throw new IllegalArgumentException("Image width must be larger than 0.");
294                    }
295                    this.imageWidth = imageWidth;
296                    leftColumns = 0;
297                    rightColumns = 0;
298                    numRows = 1;
299                    errorNum = new int[data.length];
300                    errorDen = new int[data.length];
301                    for (int i = 0; i < data.length; i++)
302                    {
303                            if (data[i] == null)
304                            {
305                                    throw new IllegalArgumentException("Each int[] array of data must be initialized; array #" + i + " is not.");
306                            }
307                            if (data[i].length != 4)
308                            {
309                                    throw new IllegalArgumentException("Each int[] array of data must be of length 4; array #" + i + " has length " + data[i].length + ".");
310                            }
311                            int x = data[i][INDEX_X_POS];
312                            if (x < 0)
313                            {
314                                    x = - x;
315                                    if (x > leftColumns)
316                                    {
317                                            leftColumns = x;
318                                    }
319                            }
320                            else
321                            if (x > 0)
322                            {
323                                    if (x > rightColumns)
324                                    {
325                                            rightColumns = x;
326                                    }
327                            }
328                            int y = data[i][INDEX_Y_POS];
329                            if (y < 0)
330                            {
331                                    throw new IllegalArgumentException("The y values must be >= 0; that is not true for array index #" + i + ".");
332                            }
333                            if (y > numRows - 1)
334                            {
335                                    numRows = y + 1;
336                            }
337                            if (x <= 0 && y == 0)
338                            {
339                                    throw new IllegalArgumentException("If y is equal to 0, x must not be <= 0; this is true for array index #" + i + ".");
340                            }
341                            if (data[i][INDEX_ERROR_NUMERATOR] == 0 || data[i][INDEX_ERROR_DENOMINATOR] == 0)
342                            {
343                                    throw new IllegalArgumentException("Neither numerator nor denominator can be 0; this is the case for array index #" + i + ".");
344                            }
345                            errorNum[i] = data[i][INDEX_ERROR_NUMERATOR];
346                            errorDen[i] = data[i][INDEX_ERROR_DENOMINATOR];
347                    }
348                    newWidth = imageWidth + leftColumns + rightColumns;
349                    //System.out.println("new width=" + newWidth);
350                    indexLut = new int[data.length];
351                    for (int i = 0; i < indexLut.length; i++)
352                    {
353                            indexLut[i] =  data[i][INDEX_Y_POS] * newWidth + data[i][INDEX_X_POS];
354                            //System.out.println("lut i=" + i + "=" + indexLut[i]);
355                    }
356            }
357    
358            /**
359             * Quantizes the input image, distributing quantization errors to neighboring
360             * pixels.
361             * Works for {@link Gray8Image} (then {@link #setGrayscaleOutputBits(int)}
362             * must have been called to set a number of output bits between 1 and 7) objects and 
363             * {@link RGB24Image} (then a quantizer must be specified using 
364             * {@link #setQuantizer(RGBQuantizer)}) objects.
365             */
366            public void process() throws
367                    MissingParameterException,
368                    WrongParameterException
369            {
370                    ensureInputImageIsAvailable();
371                    ensureImagesHaveSameResolution();
372                    PixelImage in = getInputImage();
373                    PixelImage out = getOutputImage();
374                    if (in instanceof Gray8Image)
375                    {
376                            init(templateData, in.getWidth());
377                            if (grayBits == 1)
378                            {
379                                    process((Gray8Image)in, (BilevelImage)out);
380                            }
381                            else
382                            if (grayBits > 1 && grayBits < 8)
383                            {
384                                    process((Gray8Image)in, (Gray8Image)out);
385                            }
386                            else
387                            {
388                                    throw new WrongParameterException("Cannot handle gray bits other than 1..7.");
389                            }
390                    }
391                    else
392                    if (in instanceof RGB24Image)
393                    {
394                            init(templateData, in.getWidth());
395                            if (quantizer == null)
396                            {
397                                    throw new MissingParameterException("No quantizer was specified.");
398                            }
399                            if (useTruecolorOutput)
400                            {
401                                    process((RGB24Image)in, (RGB24Image)out);
402                            }
403                            else
404                            {
405                                    process((RGB24Image)in, (Paletted8Image)out);
406                            }
407                    }
408                    else
409                    {
410                            throw new WrongParameterException("Cannot handle this image: " + in.toString());
411                    }
412            }
413    
414            private void process(Gray8Image in, BilevelImage out)
415            {
416                    final int HEIGHT = in.getHeight();
417                    final int WIDTH = in.getWidth();
418                    if (out == null)
419                    {
420                            out = new MemoryBilevelImage(WIDTH, HEIGHT);
421                    }
422                    final int NUM_ERROR_PIXELS = errorNum.length;
423                    // create buffer
424                    int[] buffer = new int[newWidth * numRows];
425                    //System.out.println("buffer  length=" + buffer.length);
426                    // fill buffer with numRows (or HEIGHT, whatever is smaller) rows of data
427                    int n = Math.min(numRows, HEIGHT);
428                    int offset = leftColumns;
429                    int bufferYIndex = 0;
430                    while (n-- > 0)
431                    {
432                            fillBuffer(0, bufferYIndex++, buffer, offset);
433                            offset += newWidth;
434                    }
435                    int bufferLastRowOffset = offset - newWidth;
436                    // set complete output image to black
437                    out.clear(BilevelImage.BLACK);
438                    for (int y = 0; y < HEIGHT; y++)
439                    {
440                            int bufferIndex = leftColumns;
441                            for (int x = 0; x < WIDTH; x++)
442                            {
443                                    int value = buffer[bufferIndex];
444                                    if (value < 0)
445                                    {
446                                            value = 0;
447                                    }
448                                    else
449                                    if (value > 255)
450                                    {
451                                            value = 255;
452                                    }
453                                    int error;
454                                    if ((value & 0x80) == 0)
455                                    {
456                                            // black pixel need not be written to output image
457                                            // because all of its pixels have initially been set
458                                            // to that color
459                                            error = value;
460                                    }
461                                    else
462                                    {
463                                            // white
464                                            out.putWhite(x, y);
465                                            error = value - 255;
466                                    }
467                                    for (int i = 0; i < NUM_ERROR_PIXELS; i++)
468                                    {
469                                            int errorPart = error * errorNum[i] / errorDen[i];
470                                            buffer[bufferIndex + indexLut[i]] += errorPart;
471                                    }
472                                    bufferIndex++;
473                            }
474                            for (int i = 0, j = newWidth; j < buffer.length; i++, j++)
475                            {
476                                    buffer[i] = buffer[j];
477                            }
478                            if (bufferYIndex < HEIGHT)
479                            {
480                                    fillBuffer(0, bufferYIndex++, buffer, bufferLastRowOffset);
481                            }
482                            setProgress(y, HEIGHT);
483                    }
484                    setOutputImage(out);
485            }
486    
487            private void process(Gray8Image in, Gray8Image out)
488            {
489                    final int HEIGHT = in.getHeight();
490                    final int WIDTH = in.getWidth();
491                    final int RIGHT_SHIFT = 8 - grayBits;
492                    final int[] GRAY_LUT = new int[1 << grayBits];
493                    for (int i = 0; i < GRAY_LUT.length; i++)
494                    {
495                            GRAY_LUT[i] = i * 255 / (GRAY_LUT.length - 1);
496                    }
497                    if (out == null)
498                    {
499                            out = new MemoryGray8Image(WIDTH, HEIGHT);
500                    }
501                    final int NUM_ERROR_PIXELS = errorNum.length;
502                    // create buffer
503                    int[] buffer = new int[newWidth * numRows];
504                    // fill buffer with numRows (or HEIGHT, whatever is smaller) rows of data
505                    int n = Math.min(numRows, HEIGHT);
506                    int offset = leftColumns;
507                    int bufferYIndex = 0;
508                    while (n-- > 0)
509                    {
510                            fillBuffer(0, bufferYIndex++, buffer, offset);
511                            offset += newWidth;
512                    }
513                    int bufferLastRowOffset = offset - newWidth;
514                    for (int y = 0; y < HEIGHT; y++)
515                    {
516                            int bufferIndex = leftColumns;
517                            for (int x = 0; x < WIDTH; x++)
518                            {
519                                    int value = buffer[bufferIndex];
520                                    if (value < 0)
521                                    {
522                                            value = 0;
523                                    }
524                                    else
525                                    if (value > 255)
526                                    {
527                                            value = 255;
528                                    }
529                                    int quantized = GRAY_LUT[value >> RIGHT_SHIFT];
530                                    out.putSample(0, x, y, quantized);
531                                    int error = value - quantized;
532                                    for (int i = 0; i < NUM_ERROR_PIXELS; i++)
533                                    {
534                                            int errorPart = error * errorNum[i] / errorDen[i];
535                                            buffer[bufferIndex + indexLut[i]] += errorPart;
536                                    }
537                                    bufferIndex++;
538                            }
539                            for (int i = 0, j = newWidth; j < buffer.length; i++, j++)
540                            {
541                                    buffer[i] = buffer[j];
542                            }
543                            if (bufferYIndex < HEIGHT)
544                            {
545                                    fillBuffer(0, bufferYIndex++, buffer, bufferLastRowOffset);
546                            }
547                            setProgress(y, HEIGHT);
548                    }
549                    setOutputImage(out);
550            }
551    
552            private void process(RGB24Image in, Paletted8Image out)
553            {
554                    final int HEIGHT = in.getHeight();
555                    final int WIDTH = in.getWidth();
556                    final int MAX = 255;
557                    if (out == null)
558                    {
559                            out = new MemoryPaletted8Image(WIDTH, HEIGHT, quantizer.createPalette());
560                    }
561                    final int NUM_ERROR_PIXELS = errorNum.length;
562                    // create buffers
563                    int[] redBuffer = new int[newWidth * numRows];
564                    int[] greenBuffer = new int[newWidth * numRows];
565                    int[] blueBuffer = new int[newWidth * numRows];
566                    //System.out.println("buffer  length=" + buffer.length);
567                    // fill buffer with numRows (or HEIGHT, whatever is smaller) rows of data
568                    int n = Math.min(numRows, HEIGHT);
569                    int offset = leftColumns;
570                    int bufferYIndex = 0;
571                    while (n-- > 0)
572                    {
573                            fillBuffer(INDEX_RED, bufferYIndex, redBuffer, offset);
574                            fillBuffer(INDEX_GREEN, bufferYIndex, greenBuffer, offset);
575                            fillBuffer(INDEX_BLUE, bufferYIndex++, blueBuffer, offset);
576                            offset += newWidth;
577                    }
578                    int bufferLastRowOffset = offset - newWidth;
579                    int[] originalRgb = new int[3];
580                    int[] quantizedRgb = new int[3];
581                    for (int y = 0; y < HEIGHT; y++)
582                    {
583                            int bufferIndex = leftColumns;
584                            for (int x = 0; x < WIDTH; x++)
585                            {
586                                    originalRgb[INDEX_RED] = adjust(redBuffer[bufferIndex], MAX);
587                                    originalRgb[INDEX_GREEN] = adjust(greenBuffer[bufferIndex], MAX);
588                                    originalRgb[INDEX_BLUE] = adjust(blueBuffer[bufferIndex], MAX);
589                                    int paletteIndex = quantizer.map(originalRgb, quantizedRgb);
590                                    out.putSample(0, x, y, paletteIndex);
591                                    // red
592                                    int error = originalRgb[INDEX_RED] - quantizedRgb[INDEX_RED];
593                                    for (int i = 0; i < NUM_ERROR_PIXELS; i++)
594                                    {
595                                            int errorPart = error * errorNum[i] / errorDen[i];
596                                            redBuffer[bufferIndex + indexLut[i]] += errorPart;
597                                    }
598                                    // green
599                                    error = originalRgb[INDEX_GREEN] - quantizedRgb[INDEX_GREEN];
600                                    for (int i = 0; i < NUM_ERROR_PIXELS; i++)
601                                    {
602                                            int errorPart = error * errorNum[i] / errorDen[i];
603                                            greenBuffer[bufferIndex + indexLut[i]] += errorPart;
604                                    }
605                                    // blue
606                                    error = originalRgb[INDEX_BLUE] - quantizedRgb[INDEX_BLUE];
607                                    for (int i = 0; i < NUM_ERROR_PIXELS; i++)
608                                    {
609                                            int errorPart = error * errorNum[i] / errorDen[i];
610                                            blueBuffer[bufferIndex + indexLut[i]] += errorPart;
611                                    }
612                                    bufferIndex++;
613                            }
614                            System.arraycopy(redBuffer, newWidth, redBuffer, 0, redBuffer.length - newWidth);
615                            System.arraycopy(greenBuffer, newWidth, greenBuffer, 0, greenBuffer.length - newWidth);
616                            System.arraycopy(blueBuffer, newWidth, blueBuffer, 0, blueBuffer.length - newWidth);
617                            if (bufferYIndex < HEIGHT)
618                            {
619                                    fillBuffer(INDEX_RED, bufferYIndex, redBuffer, bufferLastRowOffset);
620                                    fillBuffer(INDEX_GREEN, bufferYIndex, greenBuffer, bufferLastRowOffset);
621                                    fillBuffer(INDEX_BLUE, bufferYIndex++, blueBuffer, bufferLastRowOffset);
622                            }
623                            setProgress(y, HEIGHT);
624                    }
625                    setOutputImage(out);
626            }
627    
628            private void process(RGB24Image in, RGB24Image out)
629            {
630                    final int HEIGHT = in.getHeight();
631                    final int WIDTH = in.getWidth();
632                    final int MAX = 255;
633                    if (out == null)
634                    {
635                            out = (RGB24Image)in.createCompatibleImage(WIDTH, HEIGHT);
636                    }
637                    final int NUM_ERROR_PIXELS = errorNum.length;
638                    // create buffers
639                    int[] redBuffer = new int[newWidth * numRows];
640                    int[] greenBuffer = new int[newWidth * numRows];
641                    int[] blueBuffer = new int[newWidth * numRows];
642                    // fill buffer with numRows (or HEIGHT, whatever is smaller) rows of data
643                    int n = Math.min(numRows, HEIGHT);
644                    int offset = leftColumns;
645                    int bufferYIndex = 0;
646                    while (n-- > 0)
647                    {
648                            fillBuffer(INDEX_RED, bufferYIndex, redBuffer, offset);
649                            fillBuffer(INDEX_GREEN, bufferYIndex, greenBuffer, offset);
650                            fillBuffer(INDEX_BLUE, bufferYIndex++, blueBuffer, offset);
651                            offset += newWidth;
652                    }
653                    int bufferLastRowOffset = offset - newWidth;
654                    int[] originalRgb = new int[3];
655                    int[] quantizedRgb = new int[3];
656                    for (int y = 0; y < HEIGHT; y++)
657                    {
658                            int bufferIndex = leftColumns;
659                            for (int x = 0; x < WIDTH; x++)
660                            {
661                                    originalRgb[INDEX_RED] = adjust(redBuffer[bufferIndex], MAX);
662                                    originalRgb[INDEX_GREEN] = adjust(greenBuffer[bufferIndex], MAX);
663                                    originalRgb[INDEX_BLUE] = adjust(blueBuffer[bufferIndex], MAX);
664                                    /*int paletteIndex = quantizer.map(originalRgb, quantizedRgb);
665                                    out.putSample(0, x, y, paletteIndex);*/
666                                    out.putSample(INDEX_RED, x, y, quantizedRgb[INDEX_RED]);
667                                    out.putSample(INDEX_GREEN, x, y, quantizedRgb[INDEX_GREEN]);
668                                    out.putSample(INDEX_BLUE, x, y, quantizedRgb[INDEX_BLUE]);
669                                    // red
670                                    int error = originalRgb[INDEX_RED] - quantizedRgb[INDEX_RED];
671                                    for (int i = 0; i < NUM_ERROR_PIXELS; i++)
672                                    {
673                                            int errorPart = error * errorNum[i] / errorDen[i];
674                                            redBuffer[bufferIndex + indexLut[i]] += errorPart;
675                                    }
676                                    // green
677                                    error = originalRgb[INDEX_GREEN] - quantizedRgb[INDEX_GREEN];
678                                    for (int i = 0; i < NUM_ERROR_PIXELS; i++)
679                                    {
680                                            int errorPart = error * errorNum[i] / errorDen[i];
681                                            greenBuffer[bufferIndex + indexLut[i]] += errorPart;
682                                    }
683                                    // blue
684                                    error = originalRgb[INDEX_BLUE] - quantizedRgb[INDEX_BLUE];
685                                    for (int i = 0; i < NUM_ERROR_PIXELS; i++)
686                                    {
687                                            int errorPart = error * errorNum[i] / errorDen[i];
688                                            blueBuffer[bufferIndex + indexLut[i]] += errorPart;
689                                    }
690                                    bufferIndex++;
691                            }
692                            /*for (int i = 0, j = newWidth; j < buffer.length; i++, j++)
693                            {
694                                    buffer[i] = buffer[j];
695                            }*/
696                            System.arraycopy(redBuffer, newWidth, redBuffer, 0, redBuffer.length - newWidth);
697                            System.arraycopy(greenBuffer, newWidth, greenBuffer, 0, greenBuffer.length - newWidth);
698                            System.arraycopy(blueBuffer, newWidth, blueBuffer, 0, blueBuffer.length - newWidth);
699                            if (bufferYIndex < HEIGHT)
700                            {
701                                    fillBuffer(INDEX_RED, bufferYIndex, redBuffer, bufferLastRowOffset);
702                                    fillBuffer(INDEX_GREEN, bufferYIndex, greenBuffer, bufferLastRowOffset);
703                                    fillBuffer(INDEX_BLUE, bufferYIndex++, blueBuffer, bufferLastRowOffset);
704                            }
705                            setProgress(y, HEIGHT);
706                    }
707                    setOutputImage(out);
708            }
709    
710            /**
711             * Sets the number of bits to be in the output image when a grayscale image 
712             * is quantized.
713             * If the input image is of type {@link Gray8Image}, only values between 1 and 7
714             * are valid.
715             * @param numBits the number of bits in the output image
716             */
717            public void setGrayscaleOutputBits(int numBits)
718            {
719                    grayBits = numBits;
720            }
721    
722            /**
723             * Sets the color quantizer to be used (if the input image is
724             * a truecolor image).
725             * @param q an object of a class implementing the RGBQuantizer interface
726             */
727            public void setQuantizer(RGBQuantizer q)
728            {
729                    quantizer = q;
730            }
731    
732            /**
733             * Set information on how errors are to be distributed by this error diffusion
734             * dithering operation.
735             * <p>
736             * Error diffusion dithering works by quantizing each pixel and distributing the
737             * resulting error to neighboring pixels.
738             * Quantizing maps a pixel to another pixel.
739             * Each pixel is made up of one or more samples (as an example, three samples
740             * r<sub>orig</sub>, g<sub>orig</sub> and b<sub>orig</sub> for the 
741             * original pixel of an RGB image and r<sub>quant</sub>, g<sub>quant</sub> and 
742             * b<sub>quant</sub> for the quantized pixel).
743             * <p>
744             * The process of quantization attempts to find a quantized pixel that is as
745             * close to the original as possible.
746             * In the ideal case, the difference between original and quantized pixel is
747             * zero for each sample.
748             * Otherwise, this <em>quantization error</em> is non-zero, positive or negative.
749             * Example: original pixel (12, 43, 33), quantized pixel (10, 47, 40); the 
750             * error is (12 - 10, 43 - 47, 40 - 33) = (2, -4, 7).
751             * The error (2, -4, 7) is to be distributed to neighboring pixels.
752             * <p>
753             * The <code>data</code> argument of this constructor describes how to do that.
754             * It is a two-dimensional array of int values.
755             * Each of the one-dimensional int arrays of <code>data</code> describe
756             * one neighboring pixel and the relative amount of the error that it gets.
757             * That is why <code>data.length</code> specifies the number of neighboring
758             * pixels involved in distributing the error.
759             * Let's call the pixel that was just quantized the <em>current pixel</em>.
760             * It is at image position (x, y).
761             * <p>
762             * Each of the one-dimensional arrays that are part of <code>data</code>
763             * must have a length of 4.
764             * The meaning of these four values is now described.
765             * The values can be accessed by the INDEX_xyz constants of this class.
766             * These four values describe the position of one neighboring pixel and 
767             * the relative amount of the error that will be added to or subtracted
768             * from it.
769             * <ul>
770             * <li>{@link #INDEX_X_POS} (0): 
771             *     the difference between the horizontal position of the current pixel, x,
772             *     and the neighboring pixel; can take a positive or negative value,
773             *     or zero; exception: the y position of the current pixel is zero;
774             *     in that case, this value must be larger than zero, because 
775             *     neighboring pixels that get part of the error must be to the right of
776             *     or below the current pixel</li>
777             * <li>{@link #INDEX_Y_POS} (1): 
778             *     the difference between the vertical position of the current pixel, y,
779             *     and the neighboring pixel; must be equal to or larger than 0</li>
780             * <li>{@link #INDEX_ERROR_NUMERATOR} (2): 
781             *     the numerator of the relative part of the error that wil be added
782             *     to this neighboring pixel; must not be equal to 0</li>
783             * <li>{@link #INDEX_ERROR_DENOMINATOR} (3): 
784             *     the denominator of the relative part of the error that wil be added
785             *     to this neighboring pixel; must not be equal to 0</li>
786             * </ul>
787             * Example: the predefined dithering type Floyd-Steinberg.
788             * It has the following <code>data</code> array:
789             * <pre>
790             * int[][] FLOYD_STEINBERG = {{ 1,  0, 7, 16},
791             *   {-1,  1, 3, 16},
792             *   { 0,  1, 5, 16},
793             *   { 1,  1, 1, 16}};
794             * </pre>
795             * Each of the one-dimensional arrays is of length 4.
796             * Accidentally, there are also four one-dimensional arrays.
797             * The number of arrays is up to the designer.
798             * The first array {1, 0, 7, 16} is interpreted as follows--go to
799             * the pixel with a horizontal difference of 1 and a vertical difference of 0
800             * (so, the pixel to the right of the current pixel) and add 7 / 16th of the 
801             * quantization error to it.
802             * Then go to the pixel at position (-1, 1) (one to the left, one row below the
803             * current row) and add 3 / 16th of the error to it.
804             * The other two one-dimensional arrays are processed just like that.
805             * <p>
806             * As you can see, the four relative errors 1/16, 3/16, 5/16 and 7/16 sum up to
807             * 1 (or 16/16); this is in a precondition to make sure that the error
808             * is distributed completely.
809             *
810             * @param data contains a description of how the error is to be distributed
811             */
812            public void setTemplateData(int[][] data)
813            {
814                    templateData = data;
815            }
816    
817            /**
818             * When dithering an RGB input image, this method specifies whether the 
819             * output will be an {@link net.sourceforge.jiu.data.RGBIntegerImage}
820             * (<code>true</code>) or a {@link net.sourceforge.jiu.data.Paletted8Image} (<code>false</code>).
821             * @param truecolor true if truecolor output is wanted
822             */
823            public void setTruecolorOutput(boolean truecolor)
824            {
825                    useTruecolorOutput = truecolor;
826            }
827    
828            /**
829             * Sets a new template type.
830             * The argument must be one of the TYPE_xyz constants of this class.
831             * @param type int value, one of the TYPE_xyz constants of this class
832             * @throws IllegalArgumentException if the argument is not of the TYPE_xyz constants
833             */
834            public void setTemplateType(int type)
835            {
836                    switch(type)
837                    {
838                            case(TYPE_FLOYD_STEINBERG):
839                            {
840                                    templateData = FLOYD_STEINBERG_DATA;
841                                    break;
842                            }
843                            case(TYPE_STUCKI):
844                            {
845                                    templateData = STUCKI_DATA;
846                                    break;
847                            }
848                            case(TYPE_BURKES):
849                            {
850                                    templateData = BURKES_DATA;
851                                    break;
852                            }
853                            case(TYPE_SIERRA):
854                            {
855                                    templateData = SIERRA_DATA;
856                                    break;
857                            }
858                            case(TYPE_JARVIS_JUDICE_NINKE):
859                            {
860                                    templateData = JARVIS_JUDICE_NINKE_DATA;
861                                    break;
862                            }
863                            case(TYPE_STEVENSON_ARCE):
864                            {
865                                    templateData = STEVENSON_ARCE_DATA;
866                                    break;
867                            }
868                            default:
869                            {
870                                    throw new IllegalArgumentException("Unknown template type: " + type + ".");
871                            }
872                    }
873            }
874    }