001    /*
002     * ConvolutionKernelFilter
003     * 
004     * Copyright (c) 2001, 2002, 2003 Marco Schmidt.
005     * All rights reserved.
006     */
007    
008    package net.sourceforge.jiu.filters;
009    
010    import net.sourceforge.jiu.data.GrayIntegerImage;
011    import net.sourceforge.jiu.data.IntegerImage;
012    import net.sourceforge.jiu.data.PixelImage;
013    import net.sourceforge.jiu.data.RGBIntegerImage;
014    import net.sourceforge.jiu.ops.ImageToImageOperation;
015    import net.sourceforge.jiu.ops.MissingParameterException;
016    import net.sourceforge.jiu.ops.OperationFailedException;
017    import net.sourceforge.jiu.ops.WrongParameterException;
018    
019    /**
020     * Applies a convolution kernel filter to an image.
021     * <h3>Supported image types</h3>
022     * Only image types that store intensity samples are supported.
023     * Right now, this only includes {@link net.sourceforge.jiu.data.GrayIntegerImage} and
024     * {@link net.sourceforge.jiu.data.RGBIntegerImage}.
025     * <h3>Usage example</h3>
026     * Standard approach (set up everything yourself):
027     * <pre>
028     * ConvolutionKernelFilter filter = new ConvolutionKernelFilter();
029     * filter.setKernel(ConvolutionKernelFilter.TYPE_SHARPEN);
030     * filter.setInputImage(image);
031     * filter.process();
032     * PixelImage sharpenedImage = filter.getOutputImage();</pre>
033     * Use static convenience method on image <code>img</code>:
034     * <pre>
035     * PixelImage filteredImage = ConvolutionKernelFilter.filter(img, ConvolutionKernelFilter.TYPE_BLUR);
036     * </pre>
037     * <h3>Credits</h3>
038     * The implementation of the filter was created by members of the Java newsgroup 
039     * <a href="news://de.comp.lang.java">de.comp.lang.java</a> and adapted to the JIU
040     * framework by Marco Schmidt.
041     * As it was done in a contest style where people improved other people's work, and even
042     * more people suggested ideas, tested results and discussed the contest it is (1)
043     * hard to tell who won the contest and (2) only fair to list all persons involved.
044     * <p>
045     * The resulting implementation is significantly faster than the
046     * <a href="http://groups.yahoo.com/group/dclj/files/CONTEST/Vorschlag/">reference implementation</a>.
047     * The contest was started by the posting <em>[JPEC#3] Vorschläge</em> to de.comp.lang.java
048     * by Marco Schmidt (2001-02-18) and was ended by the posting <em>[JPEC#3] Ergebnisse</em>
049     * (2001-03-07).
050     * A Usenet archive like <a href="http://groups.google.com">Google Groups</a> should be 
051     * able to provide the postings.
052     *
053     * @author Bernd Eckenfels
054     * @author Carl Rosenberger
055     * @author Dietmar Münzenberger
056     * @author Karsten Schulz
057     * @author Marco Kaiser
058     * @author Marco Schmidt
059     * @author Peter Luschny
060     * @author Peter Schneider
061     * @author Ramin Sadre
062     * @author Roland Dieterich
063     * @author Thilo Schwidurski
064     */
065    public class ConvolutionKernelFilter extends ImageToImageOperation
066    {
067            public static final int TYPE_BLUR = 0;
068            public static final int TYPE_SHARPEN = 1;
069            public static final int TYPE_EDGE_DETECTION = 2;
070            public static final int TYPE_EMBOSS = 3;
071            public static final int TYPE_PSYCHEDELIC_DISTILLATION = 4;
072            public static final int TYPE_LITHOGRAPH = 5;
073            public static final int TYPE_HORIZONTAL_SOBEL = 6;
074            public static final int TYPE_VERTICAL_SOBEL = 7;
075            public static final int TYPE_HORIZONTAL_PREWITT = 8;
076            public static final int TYPE_VERTICAL_PREWITT = 9;
077    
078            private static final int[] BLUR_DATA = {1, 1, 1, 1, 1, 1, 1, 1, 1};
079            private static final int[] SHARPEN_DATA = {0, -1, 0, -1, 5, -1, 0, -1, 0};
080            private static final int[] EDGE_DETECTION_DATA = {-1, -1, -1, -1, 8, -1, -1, -1, -1};
081            private static final int[] EMBOSS_DATA = {1, 1, 0, 1, 0, -1, 0, -1, -1};
082            private static final int[] PSYCHEDELIC_DISTILLATION_DATA = {0, -1, -2, -3, -4, 0, -1,  3,  2,  1, 0, -1, 10,  2,  1, 0, -1,  3,  2,  1, 0, -1, -2, -3, -4};
083            private static final int[] LITHOGRAPH_DATA = {-1, -1, -1, -1, -1, -1,-10,-10,-10, -1, -1,-10, 98,-10, -1, -1,-10,-10,-10, -1, -1, -1, -1, -1, -1};
084            private static final int[] HORIZONTAL_SOBEL_DATA = {-1, 0, 1, -2, 0, 2, -1, 0, 1};
085            private static final int[] VERTICAL_SOBEL_DATA = {-1, -2, -1, 0, 0, 0, 1, 2, 1};
086            private static final int[] HORIZONTAL_PREWITT_DATA = {-1, 0, 1, -1, 0, 1, -1, 0, 1};
087            private static final int[] VERTICAL_PREWITT_DATA = {-1, -1, -1, 0, 0, 0, 1, 1, 1};
088            private static ConvolutionKernelData[] PREDEFINED_KERNELS = 
089            {
090                    new ConvolutionKernelData("Blur", BLUR_DATA, 3, 3, 9, 0),
091                    new ConvolutionKernelData("Sharpen", SHARPEN_DATA, 3, 3, 1, 0),
092                    new ConvolutionKernelData("Edge detection", EDGE_DETECTION_DATA, 3, 3, 1, 0),
093                    new ConvolutionKernelData("Emboss", EMBOSS_DATA, 3, 3, 1, 128),
094                    new ConvolutionKernelData("Psychedelic Distillation", PSYCHEDELIC_DISTILLATION_DATA, 5, 5, 1, 0),
095                    new ConvolutionKernelData("Lithograph", LITHOGRAPH_DATA, 5, 5, 1, 0),
096                    new ConvolutionKernelData("Horizontal Sobel", HORIZONTAL_SOBEL_DATA, 3, 3, 1, 0),
097                    new ConvolutionKernelData("Vertical Sobel", VERTICAL_SOBEL_DATA, 3, 3, 1, 0),
098                    new ConvolutionKernelData("Horizontal Prewitt", HORIZONTAL_PREWITT_DATA, 3, 3, 1, 0),
099                    new ConvolutionKernelData("Vertical Prewitt", VERTICAL_PREWITT_DATA, 3, 3, 1, 0)
100            };
101            private int kernelBias;
102            private int[] kernelData;
103            private int kernelDiv;
104            private int kernelHeight;
105            private int kernelWidth;
106    
107            /**
108             * Copies row data from input image to buffer and replicates 
109             * samples at the left and right border.
110             */
111            private void copyRow(IntegerImage srcImage, int srcChannelIndex, int rowIndex, int[] dest, int destOffset, int numBorderColumns)
112            {
113                    /*
114                    row has a width of N + 1 samples at positions 0 to N
115                    X X 0 1 ... N Y Y
116                    copy byte at 0 to all X positions
117                    copy byte at N to all Y positions
118                    */
119                    final int WIDTH = srcImage.getWidth();
120                    srcImage.getSamples(srcChannelIndex, 0, rowIndex, WIDTH, 1, dest, destOffset + numBorderColumns);
121                    // copy leftmost sample to X X positions
122                    int srcOffset = destOffset + numBorderColumns;
123                    int offset = numBorderColumns - 1;
124                    while (offset >= 0)
125                    {
126                            dest[offset--] = dest[srcOffset];
127                    }
128                    // copy rightmost sample to Y Y positions
129                    srcOffset = destOffset + numBorderColumns + WIDTH - 1;
130                    offset = srcOffset + 1;
131                    int n = numBorderColumns;
132                    while (n-- > 0)
133                    {
134                            dest[offset++] = dest[srcOffset];
135                    }
136            }
137    
138            /**
139             * Filters argument image with argument kernel type and returns output image.
140             * Static convenience method to do filtering with one line of code:
141             * <pre>PixelImage blurredImage = ConvolutionKernelFilter.filter(in, ConvolutionKernelFilter.TYPE_BLUR);</pre>
142             */
143            public static PixelImage filter(PixelImage input, int kernelType)
144            {
145                    return filter(input, PREDEFINED_KERNELS[kernelType]);
146            }
147    
148            public static PixelImage filter(PixelImage input, ConvolutionKernelData data)
149            {
150                    ConvolutionKernelFilter op = new ConvolutionKernelFilter();
151                    op.setKernel(data);
152                    op.setInputImage(input);
153                    try
154                    {
155                            op.process();
156                            return op.getOutputImage();
157                    }
158                    catch (OperationFailedException ofe)
159                    {
160                            return null;
161                    }
162            }
163    
164            /**
165             * Applies the kernel to one of the channels of an image.
166             * @param channelIndex index of the channel to be filtered, must be from 0 to ByteChannelImage.getNumChannels() - 1
167             */
168            private void process(int channelIndex, IntegerImage in, IntegerImage out)
169            {
170                    final int H_DIM = kernelWidth;
171                    final int H_DIM_2 = (H_DIM / 2);
172                    final int V_DIM = kernelHeight;
173                    final int V_DIM_2 = (V_DIM / 2);
174                    final int HEIGHT = in.getHeight();
175                    final int WIDTH = in.getWidth();
176                    final int NEW_WIDTH = WIDTH + 2 * H_DIM_2;
177                    final int NEW_HEIGHT = HEIGHT + 2 * V_DIM_2;
178                    final int MAX = in.getMaxSample(channelIndex);
179                    int processedItems = channelIndex * HEIGHT;
180                    final int TOTAL_ITEMS = in.getNumChannels() * HEIGHT;
181                    int[] src = new int[NEW_WIDTH * NEW_HEIGHT];
182                    // fill src with data
183                    for (int y = 0, offs = V_DIM_2 * NEW_WIDTH; y < HEIGHT; y++, offs += NEW_WIDTH)
184                    {
185                            copyRow(in, channelIndex, y, src, offs, H_DIM_2);
186                    }
187                    // copy row H_DIM_2 to 0 .. H_DIM_2 - 1
188                    int srcOffset = V_DIM_2 * NEW_WIDTH;
189                    for (int y = 0; y < V_DIM_2; y++)
190                    {
191                            System.arraycopy(src, srcOffset, src, y * NEW_WIDTH, NEW_WIDTH);
192                    }
193                    // copy row H_DIM_2 + HEIGHT - 1 to H_DIM_2 + HEIGHT .. 2 * H_DIM_2 + HEIGHT - 1 
194                    srcOffset = (HEIGHT + V_DIM_2 - 1) * NEW_WIDTH;
195                    for (int y = V_DIM_2 + HEIGHT; y < NEW_HEIGHT; y++)
196                    {
197                            System.arraycopy(src, srcOffset, src, y * NEW_WIDTH, NEW_WIDTH);
198                    }
199                    // do the filtering
200                    int count = H_DIM * V_DIM;
201                    final int[] kernelLine = new int[count];
202                    final int[] kernelD = new int[count];
203                    int p;
204                    count = 0;
205                    final int j = H_DIM - 1;
206                    for (int x = H_DIM; x-- > 0;)
207                    {
208                            for (int y = V_DIM; y-- > 0;)
209                            {
210                                    int index = y * H_DIM + x;
211                                    if (kernelData[index] != 0)
212                                    {
213                                            kernelLine[count] = kernelData[index];
214                                            kernelD[count] = y * NEW_WIDTH + x;
215                                            count++;
216                                    }
217                            }
218                    }
219                    // all kernel elements are zero => nothing to do, resulting channel will be full of zeroes
220                    if (count == 0)
221                    {
222                            setProgress(channelIndex, in.getNumChannels());
223                            return;
224                    }
225                    p = (HEIGHT - 1) * NEW_WIDTH + (WIDTH - 1);
226                    int[] dest = new int[WIDTH];
227                    for (int y = HEIGHT; y-- > 0;)
228                    {
229                            for (int x = WIDTH; x-- > 0;)
230                            {
231                                    int sum = 0;
232                                    for (int i = count; i-- > 0;)
233                                    {
234                                            sum += (src[p + kernelD[i]] & MAX) * kernelLine[i];
235                                    }
236                                    sum = (sum / kernelDiv) + kernelBias;
237                                    if (sum <= 0)
238                                    {
239                                            dest[x] = 0;
240                                    }
241                                    else
242                                    if (sum >= MAX)
243                                    {
244                                            dest[x] = MAX;
245                                    }
246                                    else
247                                    {
248                                            dest[x] = sum;
249                                    }
250                                    // (byte)(((0xFFFFFF00 & sum) == 0) ? sum : ((sum >>> 31) - 1));
251                                    p--;
252                            }
253                            out.putSamples(channelIndex, 0, y, WIDTH, 1, dest, 0);
254                            p -= j;
255                            setProgress(processedItems++, TOTAL_ITEMS);
256                    }
257            }
258    
259            private void process(IntegerImage in, IntegerImage out)
260            {
261                    final int TOTAL_ITEMS = in.getNumChannels() * in.getHeight();
262                    for (int channelIndex = 0; channelIndex < in.getNumChannels(); channelIndex++)
263                    {
264                            process(channelIndex, in, out);
265                    }
266            }
267    
268            public void process() throws
269                    MissingParameterException,
270                    WrongParameterException
271            {
272                    ensureInputImageIsAvailable();
273                    ensureImagesHaveSameResolution();
274                    PixelImage in = getInputImage();
275                    if (in instanceof GrayIntegerImage || in instanceof RGBIntegerImage)
276                    {
277                            PixelImage out = getOutputImage();
278                            if (out == null)
279                            {
280                                    out = (IntegerImage)in.createCompatibleImage(in.getWidth(), in.getHeight());
281                                    setOutputImage(out);
282                            }
283                            process((IntegerImage)in, (IntegerImage)out);
284                    }
285                    else
286                    {
287                            throw new WrongParameterException("Input image must implement GrayIntegerImage or RGBIntegerImage.");
288                    }
289            }
290    
291            /**
292             * Sets properties of the kernel to be used in this operation.
293             * @param data the kernel coefficients; this one-dimensional array stores
294             *   them in order top-to-bottom, left-to-right; the length of this
295             *   array must be at least width times height
296             * @param width the width of the kernel; must not be even
297             * @param height the height of the kernel; must not be even
298             * @param div the result is divided by this value after the addition of value
299             *  (so this value must not be zero)
300             * @param bias this value is added to the result before the division
301             */
302            public void setKernel(int[] data, int width, int height, int div, int bias)
303            {
304                    if (data == null)
305                    {
306                            throw new IllegalArgumentException("Kernel data must be non-null.");
307                    }
308                    if (width < 1)
309                    {
310                            throw new IllegalArgumentException("Kernel width must be at least 1.");
311                    }
312                    if (width % 2 != 1)
313                    {
314                            throw new IllegalArgumentException("Kernel width must not be even.");
315                    }
316                    if (height < 1)
317                    {
318                            throw new IllegalArgumentException("Kernel height must be at least 1.");
319                    }
320                    if (height % 2 != 1)
321                    {
322                            throw new IllegalArgumentException("Kernel width must not be even.");
323                    }
324                    if (data.length < width * height)
325                    {
326                            throw new IllegalArgumentException("Kernel data must have a length >= " + 
327                                    (width * height) + " to hold " + width + " times " + height + 
328                                    " elements.");
329                    }
330                    if (div == 0)
331                    {
332                            throw new IllegalArgumentException("The div parameter must not be zero.");
333                    }
334                    kernelData = data;
335                    kernelWidth = width;
336                    kernelHeight = height;
337                    kernelDiv = div;
338                    kernelBias = bias;
339            }
340    
341            /**
342             * Sets kernel data to be used for filtering.
343             * @param ckd all information necessary for filtering
344             */
345            public void setKernel(ConvolutionKernelData ckd)
346            {
347                    setKernel(ckd.getData(), ckd.getWidth(), ckd.getHeight(), ckd.getDiv(), ckd.getBias());
348            }
349    
350            /**
351             * Sets one of the predefined kernel types to be used for filtering.
352             * @param type one of the TYPE_xyz constants of this class
353             * @throws IllegalArgumentException if the argument is not a valid TYPE_xyz constant
354             */
355            public void setKernel(int type)
356            {
357                    if (type < 0 || type >= PREDEFINED_KERNELS.length)
358                    {
359                            throw new IllegalArgumentException("Not a valid type index for predefined kernels: " + type);
360                    }
361                    else
362                    {
363                            setKernel(PREDEFINED_KERNELS[type]);
364                    }
365            }
366    }