001    /*
002     * ClusteredDotDither
003     * 
004     * Copyright (c) 2002, 2003 Marco Schmidt.
005     * All rights reserved.
006     */
007    
008    package net.sourceforge.jiu.color.dithering;
009    
010    import net.sourceforge.jiu.data.BilevelImage;
011    import net.sourceforge.jiu.data.GrayIntegerImage;
012    import net.sourceforge.jiu.data.MemoryBilevelImage;
013    import net.sourceforge.jiu.data.PixelImage;
014    import net.sourceforge.jiu.ops.ImageToImageOperation;
015    import net.sourceforge.jiu.ops.MissingParameterException;
016    import net.sourceforge.jiu.ops.WrongParameterException;
017    import net.sourceforge.jiu.util.ComparatorInterface;
018    import net.sourceforge.jiu.util.Sort;
019    
020    /**
021     * Apply a clustered dot ordered dither to a grayscale image, converting
022     * it to a bilevel image in the process.
023     * Works with {@link net.sourceforge.jiu.data.GrayIntegerImage} objects
024     * as input and {@link net.sourceforge.jiu.data.BilevelImage} objects
025     * as output.
026     * Resolution of both must be the same.
027     * Use one of the predefined dither matrices or have one compiled from
028     * a <em>spot function</em> (given by an object of a class implementing
029     * {@link net.sourceforge.jiu.color.dithering.SpotFunction}).
030     * There are a couple of classes implementing that spot function interface
031     * in the dithering package.
032     * If no matrix is specified, {@link #process()} creates a default matrix
033     * by calling {@link #setOrder3DitherMatrix()}.
034     * <h3>Usage example</h3>
035     * <pre>
036     * ClusteredDotDither dither = new ClusteredDotDither();
037     * dither.setInputImage(image); // some GrayIntegerImage
038     * dither.setDitherMatrix(8, 8, new DiamondSpotFunction());
039     * dither.process();
040     * PixelImage ditheredImage = dither.getOutputImage();
041     * </pre>
042     *
043     * <h3>Credits</h3>
044     * The predefined dither matrices were taken from
045     * <a target="_top" href="http://netpbm.sourceforge.net">Netpbm</a>'s 
046     * <code>pgmtopbm</code> program (the matrices are stored in the
047     * file <code>dithers.h</code>).
048     * <p>
049     * I learned about spot functions and their use from Austin Donnelly's 
050     * GIMP plugin <em>newsprint</em> - it has extensive comments, and the
051     * <a target="_top" href="http://www.cl.cam.ac.uk/~and1000/newsprint/">newsprint website</a> 
052     * explains the 
053     * <a target="_top" href="http://www.cl.cam.ac.uk/~and1000/newsprint/clustered-dot.html">theoretical background</a>.
054     * @author Marco Schmidt
055     * @since 0.9.0
056     */
057    public class ClusteredDotDither extends ImageToImageOperation
058    {
059            private int ditherHeight;
060            private int ditherWidth;
061            private int[] ditherData;
062    
063            public void process() throws
064                    MissingParameterException,
065                    WrongParameterException
066            {
067                    if (ditherData == null)
068                    {
069                            setDefaults();
070                    }
071                    ensureInputImageIsAvailable();
072                    PixelImage in = getInputImage();
073                    if (!(in instanceof GrayIntegerImage))
074                    {
075                            throw new WrongParameterException("Input image must implement GrayIntegerImage.");
076                    }
077                    PixelImage out = getOutputImage();
078                    if (out == null)
079                    {
080                            out = new MemoryBilevelImage(in.getWidth(), in.getHeight());
081                            setOutputImage(out);
082                    }
083                    else
084                    {
085                            if (!(out instanceof BilevelImage))
086                            {
087                                    throw new WrongParameterException("Output image must implement BilevelImage.");
088                            }
089                            ensureOutputImageResolution(in.getWidth(), in.getHeight());
090                    }
091                    process((GrayIntegerImage)in, (BilevelImage)out);
092            }
093    
094            private void process(GrayIntegerImage in, BilevelImage out)
095            {
096                    // find maximum entry in dither matrix
097                    int maxTableValue = 1;
098                    for (int i = 0; i < ditherData.length; i++)
099                    {
100                            if (ditherData[i] > maxTableValue)
101                            {
102                                    maxTableValue = ditherData[i];
103                            }
104                    }
105                    maxTableValue++;
106    
107                    // create adjusted dither matrix data
108                    final int MAX_SAMPLE = in.getMaxSample(0) + 1;
109                    final int[] data = new int[ditherData.length];
110                    for (int i = 0; i < data.length; i++)
111                    {
112                            data[i] = ditherData[i] * MAX_SAMPLE / maxTableValue;
113                    }
114    
115                    // do the actual dithering
116                    final int HEIGHT = in.getHeight();
117                    final int WIDTH = in.getWidth();
118                    for (int y = 0; y < HEIGHT; y++)
119                    {
120                            int ditherOffset = (y % ditherHeight) * ditherWidth;
121                            int samplesLeft = ditherWidth;
122                            for (int x = 0; x < WIDTH; x++)
123                            {
124                                    if (in.getSample(0, x, y) >= data[ditherOffset++])
125                                    {
126                                            out.putWhite(x, y);
127                                    }
128                                    else
129                                    {
130                                            out.putBlack(x, y);
131                                    }
132                                    if (--samplesLeft == 0)
133                                    {
134                                            samplesLeft = ditherWidth;
135                                            ditherOffset -= ditherWidth;
136                                    }
137                            }
138                            setProgress(y, HEIGHT);
139                    }
140            }
141    
142            private void setDefaults()
143            {
144                    setOrder3DitherMatrix();
145            }
146    
147            /**
148             * Sets the dither matrix to be used in this operation.
149             * @param width number of entries in horizontal direction
150             * @param height number of entries in vertical direction
151             * @param data matrix entries, in order top to bottom, and in each row left to right
152             * @throws IllegalArgumentException if width or height are smaller than one or data
153             *  is <code>null</code> or has not at least width times height entries
154             */
155            public void setDitherMatrix(int width, int height, int[] data)
156            {
157                    if (width < 1)
158                    {
159                            throw new IllegalArgumentException("Width must be one or larger.");
160                    }
161                    if (height < 1)
162                    {
163                            throw new IllegalArgumentException("Height must be one or larger.");
164                    }
165                    if (data == null)
166                    {
167                            throw new IllegalArgumentException("Data must not be null.");
168                    }
169                    if (data.length < width * height)
170                    {
171                            throw new IllegalArgumentException("Data must have at least width times height entries.");
172                    }
173                    ditherWidth =  width;
174                    ditherHeight = height;
175                    ditherData = data;
176            }
177    
178            /**
179             * Creates and sets a dither matrix of user-defined size and 
180             * compiles it from a spot function.
181             * Creates a matrix from the spot function and calls {@link #setDitherMatrix(int, int, int[])}.
182             * @param width width of matrix, must be one or larger
183             * @param height height of matrix, must be one or larger
184             * @param f the spot function to be used for compiling the matrix
185             */
186            public void setDitherMatrix(int width, int height, SpotFunction f)
187            {
188                    class MatrixElement implements ComparatorInterface
189                    {
190                            int index;
191                            double value;
192                            public int compare(Object o1, Object o2)
193                            {
194                                    MatrixElement e1 = (MatrixElement)o1;
195                                    MatrixElement e2 = (MatrixElement)o2;
196                                    if (e1.value < e2.value)
197                                    {
198                                            return -1;
199                                    }
200                                    else
201                                    if (e1.value == e2.value)
202                                    {
203                                            return 0;
204                                    }
205                                    else
206                                    {
207                                            return 1;
208                                    }
209                            }
210                    }
211                    int[] data = new int[width * height];
212                    MatrixElement[] matrixElements = new MatrixElement[data.length];
213                    for (int i = 0; i < data.length;  i++)
214                    {
215                            matrixElements[i] = new MatrixElement();
216                            matrixElements[i].index = i;
217                    }
218                    int index = 0;
219                    for (int y = 0; y < height; y++)
220                    {
221                            for (int x = 0; x < width; x++)
222                            {
223                                    double sx = ((double)x / (width - 1) - 0.5) * 2;
224                                    double sy = ((double)y / (height - 1) - 0.5) * 2;
225                                    double value = f.compute(sx, sy);
226                                    if (value < -1.0)
227                                    {
228                                            value = -1.0;
229                                    }
230                                    else
231                                    if (value > 1.0)
232                                    {
233                                            value = 1.0;
234                                    }
235                                    matrixElements[index++].value = value;
236                            }
237                    }
238                    boolean balanced = f.isBalanced();
239                    if (!balanced)
240                    {
241                            Sort.sort(matrixElements, matrixElements[0]);
242                    }
243                    for (int i = 0; i < data.length; i++)
244                    {
245                            MatrixElement elem = matrixElements[i];
246                            if (balanced)
247                            {
248                                    data[elem.index] = (int)(elem.value * 254);
249                            }
250                            else
251                            {
252                                    data[elem.index] = i * 255 / data.length;
253                            }
254                    }
255                    setDitherMatrix(width, height, data);
256            }
257    
258            /** 
259             * Sets a 6 times 6 elements matrix to be used for dithering.
260             */
261            public void setOrder3DitherMatrix()
262            {
263                    setDitherMatrix(6, 6, new int[]
264                            { 9, 11, 10,  8,  6,  7,
265                             12, 17, 16,  5,  0,  1,
266                             13, 14, 15,  4,  3,  2,
267                              8,  6,  7,  9, 11, 10,
268                              5,  0,  1, 12, 17, 16,
269                              4,  3,  2, 13, 14, 15});
270            }
271    
272            /** 
273             * Sets an 8 times 8 elements matrix to be used for dithering.
274             */
275            public void setOrder4DitherMatrix()
276            {
277                    setDitherMatrix(8, 8, new int[]
278                            {18,20,19,16,13,11,12,15,
279                            27,28,29,22, 4, 3, 2, 9,
280                            26,31,30,21, 5, 0, 1,10,
281                            23,25,24,17, 8, 6, 7,14,
282                            13,11,12,15,18,20,19,16,
283                             4, 3, 2, 9,27,28,29,22,
284                             5, 0, 1,10,26,31,30,21,
285                             8, 6, 7,14,23,25,24,17});
286            }
287    
288            /** 
289             * Sets a 16 times 16 elements matrix to be used for dithering.
290             */
291            public void setOrder8DitherMatrix()
292            {
293                    setDitherMatrix(16, 16, new int[] {
294                             64, 69, 77, 87, 86, 76, 68, 67, 63, 58, 50, 40, 41, 51, 59, 60,
295                             70, 94,100,109,108, 99, 93, 75, 57, 33, 27, 18, 19, 28, 34, 52,
296                             78,101,114,116,115,112, 98, 83, 49, 26, 13, 11, 12, 15, 29, 44,
297                             88,110,123,124,125,118,107, 85, 39, 17,  4,  3,  2,  9, 20, 42,
298                             89,111,122,127,126,117,106, 84, 38, 16,  5,  0,  1, 10, 21, 43,
299                             79,102,119,121,120,113, 97, 82, 48, 25,  8,  6,  7, 14, 30, 45,
300                             71, 95,103,104,105, 96, 92, 74, 56, 32, 24, 23, 22, 31, 35, 53,
301                             65, 72, 80, 90, 91, 81, 73, 66, 62, 55, 47, 37, 36, 46, 54, 61,
302                             63, 58, 50, 40, 41, 51, 59, 60, 64, 69, 77, 87, 86, 76, 68, 67,
303                             57, 33, 27, 18, 19, 28, 34, 52, 70, 94,100,109,108, 99, 93, 75,
304                             49, 26, 13, 11, 12, 15, 29, 44, 78,101,114,116,115,112, 98, 83,
305                             39, 17,  4,  3,  2,  9, 20, 42, 88,110,123,124,125,118,107, 85,
306                             38, 16,  5,  0,  1, 10, 21, 43, 89,111,122,127,126,117,106, 84,
307                             48, 25,  8,  6,  7, 14, 30, 45, 79,102,119,121,120,113, 97, 82,
308                             56, 32, 24, 23, 22, 31, 35, 53, 71, 95,103,104,105, 96, 92, 74,
309                             62, 55, 47, 37, 36, 46, 54, 61, 65, 72, 80, 90, 91, 81, 73, 66});
310            }
311    }