001    /*
002     * Resample
003     * 
004     * Copyright (c) 2001, 2002, 2003 Marco Schmidt.
005     * All rights reserved.
006     */
007    
008    package net.sourceforge.jiu.geometry;
009    
010    import net.sourceforge.jiu.data.PixelImage;
011    import net.sourceforge.jiu.data.IntegerImage;
012    import net.sourceforge.jiu.ops.ImageToImageOperation;
013    import net.sourceforge.jiu.ops.MissingParameterException;
014    import net.sourceforge.jiu.ops.WrongParameterException;
015    
016    /* This is the beginning of resample.pas, the Unit on which this class is based:
017    // -----------------------------------------------------------------------------
018    // Project:     bitmap resampler
019    // Module:      resample
020    // Description: Interpolated Bitmap Resampling using filters.
021    // Version:     01.03
022    // Release:     4
023    // Date:        29-JUN-1999
024    // Target:      Win32, Delphi 2, 3 & 4
025    // Author(s):   anme: Anders Melander, anders@melander.dk
026    // Copyright    (c) 1997-99 by Anders Melander
027    // Formatting:  2 space indent, 8 space tabs, 80 columns.
028    // -----------------------------------------------------------------------------
029    // This software is copyrighted as noted above.  It may be freely copied,
030    // modified, and redistributed, provided that the copyright notice(s) is
031    // preserved on all copies.
032    //
033    // There is no warranty or other guarantee of fitness for this software,
034    // it is provided solely "as is".  Bug reports or fixes may be sent
035    // to the author, who may or may not act on them as he desires.
036    //
037    // You may not include this software in a program or other software product
038    // without supplying the source, or without informing the end-user that the
039    // source is available for no extra charge.
040    //
041    // If you modify this software, you should include a notice in the "Revision
042    // history" section giving the name of the person performing the modification,
043    // the date of modification, and the reason for such modification.
044    // -----------------------------------------------------------------------------
045    // Here's some additional copyrights for you:
046    //
047    // From filter.c:
048    // The authors and the publisher hold no copyright restrictions
049    // on any of these files; this source code is public domain, and
050    // is freely available to the entire computer graphics community
051    // for study, use, and modification.  We do request that the
052    // comment at the top of each file, identifying the original
053    // author and its original publication in the book Graphics
054    // Gems, be retained in all programs that use these files.
055    //
056    // -----------------------------------------------------------------------------
057    // Revision history:
058    //
059    // 0100 110997  anme    - Adapted from Dale Schumacher's fzoom v0.20.
060    //
061    // 0101 110198  anme    - Added Lanczos3 and Mitchell filters.
062    //                      - Fixed range bug.
063    //                        Min value was not checked on conversion from Single to
064    //                        byte.
065    //                      - Numerous optimizations.
066    //                      - Added TImage stretch on form resize.
067    //                      - Added support for Delphi 2 via TCanvas.Pixels.
068    //                      - Renamed module from stretch to resample.
069    //                      - Moved demo code to separate module.
070    //
071    // 0102 150398  anme    - Fixed a problem that caused all pixels to be shifted
072    //                        1/2 pixel down and to the right (in source
073    //                        coordinates). Thanks to David Ullrich for the
074    //                        solution.
075    //
076    // 0103 170898  anme    - Fixed typo: Renamed Strecth function to Stretch.
077    //                        Thanks to Graham Stratford for spotting it.
078    //                        Sorry about that.
079    //      081298  anme    - Added check for too small destination bitmap.
080    //                        Thanks to Jeppe Oland for bringing this problem to my
081    //                        attention.
082    //      260399  anme    - Fixed a problem with resampling of very narrow
083    //                        bitmaps. Thanks to Holger Dors for bringing the
084    //                        problem to my attention.
085    //                      - Removed dependency of math unit.
086    //      290699  jobe    - Subsampling improvements by Josha Beukema.
087    //
088    // -----------------------------------------------------------------------------
089    // Credits:
090    // The algorithms and methods used in this library are based on the article
091    // "General Filtered Image Rescaling" by Dale Schumacher which appeared in the
092    // book Graphics Gems III, published by Academic Press, Inc.
093    //
094    // The edge offset problem was fixed by:
095    //   * David Ullrich <ullrich@hardy.math.okstate.edu>
096    //
097    // The subsampling problem was fixed by:
098    //   * Josha Beukema <jbeukema@inn.nl>
099    // -----------------------------------------------------------------------------
100    // To do (in rough order of priority):
101    // * Implement Dale Schumacher's "Optimized Bitmap Scaling Routines".
102    // * Optimize to use integer math instead of floating point where possible.
103    // -----------------------------------------------------------------------------
104    */
105    
106    /**
107     * Resizes grayscale and truecolor images using filters.
108     * For other image types (including paletted or bilevel images), you might
109     * want to use the {@link ScaleReplication} class or convert the images to
110     * grayscale (or RGB truecolor) first and then use this class.
111     * Several algorithms for resampling are implemented, they differ in resulting image quality 
112     * and computational complexity.
113     *
114     * <h3>Usage example</h3>
115     * This will scale <code>image</code> to 150 percent of its original size
116     * in both directions, using the Lanczos3 filter type:
117     * <pre>
118     * Resample resample = new Resample();
119     * resample.setInputImage(image);
120     * resample.setSize(image.getWidth() * 3 / 2, image.getHeight() * 3 / 2);
121     * resample.setFilter(Resample.FILTER_TYPE_LANCZOS3);
122     * resample.process();
123     * PixelImage scaledImage = resample.getOutputImage();
124     * </pre>
125     * 
126     * <h3>Known problems</h3>
127     * <ul>
128     * <li>Scaling down certain images (with stripe or checkers patterns in them) will
129     *  lead to moire effects in the resulting image.
130     *  These effects can be somewhat reduced by scaling down in several step (e.g.
131     *  first from 1600 x 1200 to 800 x 600, then from 800 x 600 to 400 x 300, and so on).</li>
132     * <li>Scaling down with filter type {@link #FILTER_TYPE_BOX} can lead to errors in the scaled image.
133     *  No fix known yet. Workaround: Use the class {@link ScaleReplication}.</li>
134     * </ul>
135     *
136     * <h3>Origin</h3>
137     * This code is a port of Anders Melander's
138     * Object Pascal (Delphi) unit <tt>resample.pas</tt> to Java.
139     * The Delphi code is an adaptation (with some improvements) of 
140     * Dale Schumacher's <tt>fzoom</tt> C code.
141     * Check out the homepage for the Delphi resample code, a demo application
142     * to compare the different filtering algorithms is also provided:
143     * <a target="_top" href="http://www.melander.dk/delphi/resampler/index.html">http://www.melander.dk/delphi/resampler/index.html</a>.
144     * You will also find the original C code there.
145     *
146     * <h3>Theory</h3>
147     * The theoretical background for all implementations is Dale Schumacher's article
148     * <em>General Filtered Image Rescaling</em>
149     * in <em>Graphics Gems III</em>, editor David Kirk, Academic Press, pages 8-16, 1994.
150     * <p>
151     * The <em>Graphics Gems Repository</em> can be found at
152     * <a target="_top" href="http://www.acm.org/tog/GraphicsGems/">http://www.acm.org/tog/GraphicsGems/</a>.
153     * It also includes information on the books and how to order them.
154     *
155     * @author Marco Schmidt
156     */
157    public class Resample extends ImageToImageOperation
158    {
159            /**
160             * Constant for the Box filter (also known as Nearest Neighbor filter).
161             */
162            public static final int FILTER_TYPE_BOX = 0;
163    
164            /**
165             * Constant for the Triangle filter (also known as Linear filter or Bilinear filter).
166             */
167            public static final int FILTER_TYPE_TRIANGLE = 1;
168    
169            /**
170             * Constant for the Hermite filter.
171             */
172            public static final int FILTER_TYPE_HERMITE = 2;
173    
174            /**
175             * Constant for the Bell filter.
176             */
177            public static final int FILTER_TYPE_BELL = 3;
178    
179            /**
180             * Constant for the B-Spline filter.
181             */
182            public static final int FILTER_TYPE_B_SPLINE = 4;
183    
184            /**
185             * Constant for the Lanczos3 filter.
186             */
187            public static final int FILTER_TYPE_LANCZOS3 = 5;
188    
189            /**
190             * Constant for the Mitchell filter.
191             */
192            public static final int FILTER_TYPE_MITCHELL = 6;
193            class Contributor
194            {
195                    int pixel; // Source pixel
196                    float weight; // Pixel weight
197            }
198            class CList
199            {
200                    int n;
201                    Contributor[] p;
202            }
203            private Integer outWidth;
204            private Integer outHeight;
205            private ResampleFilter filter;
206    
207            private static ResampleFilter createFilter(int filterType)
208            {
209                    switch(filterType)
210                    {
211                            case(FILTER_TYPE_BOX): return new BoxFilter();
212                            case(FILTER_TYPE_TRIANGLE): return new TriangleFilter();
213                            case(FILTER_TYPE_HERMITE): return new HermiteFilter();
214                            case(FILTER_TYPE_BELL): return new BellFilter();
215                            case(FILTER_TYPE_B_SPLINE): return new BSplineFilter();
216                            case(FILTER_TYPE_LANCZOS3): return new Lanczos3Filter();
217                            case(FILTER_TYPE_MITCHELL): return new MitchellFilter();
218                            default:
219                            {
220                                    throw new IllegalArgumentException("Unknown filter type in Resample: " + filterType);
221                            }
222                    }
223            }
224    
225            /**
226             * Returns the filter to be used in this operation.
227             * @return ResampleFilter object or <code>null</code> if none was defined yet
228             */
229            public ResampleFilter getFilter()
230            {
231                    return filter;
232            }
233    
234            /**
235             * Returns the names of all predefined filters.
236             * Each FILTER_TYPE_xyz constant can be used as an index into the array that is returned.
237             * Names are retrieved by creating an object of each predefined filter class and calling its
238             * getName method.
239             * @return String array with filter names
240             */
241            public static String[] getFilterNames()
242            {
243                    String[] result = new String[getNumFilters()];
244                    for (int i = 0; i < getNumFilters(); i++)
245                    {
246                            ResampleFilter filter = createFilter(i);
247                            result[i] = filter.getName();
248                    }
249                    return result;
250            }
251    
252            /**
253             * Returns the number of predefined filters.
254             * @return number of filters
255             */
256            public static int getNumFilters()
257            {
258                    return 7;
259            }
260    
261            /**
262             * This method does the actual work of rescaling an image.
263             */
264            private void process(IntegerImage in, IntegerImage out)
265            {
266                    if (out == null)
267                    {
268                            out = (IntegerImage)in.createCompatibleImage(outWidth.intValue(), outHeight.intValue());
269                            setOutputImage(out);
270                    }
271                    if (filter == null)
272                    {
273                            filter = new TriangleFilter();
274                    }
275                    float fwidth = filter.getSamplingRadius();
276                    final int dstWidth = outWidth.intValue();
277                    final int dstHeight = outHeight.intValue();
278                    final int srcWidth = in.getWidth();
279                    final int srcHeight = in.getHeight();
280                    /* if (SrcWidth < 1) or (SrcHeight < 1) then
281        raise Exception.Create('Source bitmap too small');*/
282                    // Create intermediate image to hold horizontal zoom
283                    IntegerImage work = (IntegerImage)in.createCompatibleImage(dstWidth, srcHeight);
284                    float xscale;
285                    float yscale;
286                    if (srcWidth == 1)
287                    {
288                            xscale = (float)dstWidth / (float)srcWidth;
289                    }
290                    else
291                    {
292                            xscale = (float)(dstWidth - 1) / (float)(srcWidth - 1);
293                    }
294                    if (srcHeight == 1)
295                    {
296                            yscale = (float)dstHeight / (float)srcHeight;
297                    }
298                    else
299                    {
300                            yscale = (float)(dstHeight - 1) / (float)(srcHeight - 1);
301                    }
302    
303                    /* Marco: the following two variables are used for progress notification */
304                    int processedItems = 0;
305                    int totalItems = /*dstWidth +*/ srcHeight + /*dstHeight +*/ dstWidth;
306    
307                    // --------------------------------------------
308                    // Pre-calculate filter contributions for a row
309                    // -----------------------------------------------
310                    CList[] contrib = new CList[dstWidth];
311                    for (int i = 0; i < contrib.length; i++)
312                    {
313                            contrib[i] = new CList();
314                    }
315                    
316                    // Horizontal sub-sampling
317                    // Scales from bigger to smaller width
318                    if (xscale < 1.0f)
319                    {
320                            float width = fwidth / xscale;
321                            float fscale = 1.0f / xscale;
322                            int numPixels = (int)(width * 2.0f + 1);
323                            for (int i = 0; i < dstWidth; i++)
324                            {
325                                    contrib[i].n = 0;
326                                    contrib[i].p = new Contributor[numPixels];
327                                    for (int j = 0; j < contrib[i].p.length; j++)
328                                    {
329                                            contrib[i].p[j] = new Contributor();
330                                    }
331                                    float center = i / xscale;
332                                    int left = (int)Math.floor(center - width);
333                                    int right = (int)Math.ceil(center + width);
334                                    for (int j = left; j <= right; j++)
335                                    {
336                                            float weight = filter.apply((center - j) / fscale) / fscale;
337                                            if (weight == 0.0f)
338                                            {
339                                                    continue;
340                                            }
341                                            int n;
342                                            if (j < 0)
343                                            {
344                                                    n = -j;
345                                            }
346                                            else
347                                            if (j >= srcWidth)
348                                            {
349                                                    n = srcWidth - j + srcWidth - 1;
350                                            }
351                                            else
352                                            {
353                                                    n = j;
354                                            }
355                                            int k = contrib[i].n;
356                                            contrib[i].n = contrib[i].n + 1;
357                                            contrib[i].p[k].pixel = n;
358                                            contrib[i].p[k].weight = weight;
359                                    }
360                                    //setProgress(processedItems++, totalItems);
361                            }
362                    }
363                    else
364            // Horizontal super-sampling
365                    // Scales from smaller to bigger width
366            {
367                            int numPixels = (int)(fwidth * 2.0f + 1);
368                            for (int i = 0; i < dstWidth; i++)
369                            {
370                            contrib[i].n = 0;
371                                    contrib[i].p = new Contributor[numPixels];
372                                    for (int j = 0; j < contrib[i].p.length; j++)
373                                    {
374                                            contrib[i].p[j] = new Contributor();
375                                    }
376                                    float center = i / xscale;
377                                    int left = (int)Math.floor(center - fwidth);
378                                    int right = (int)Math.ceil(center + fwidth);
379                                    for (int j = left; j <= right; j++)
380                                    {
381                                            float weight = filter.apply(center - j);
382                                            if (weight == 0.0f)
383                                            {
384                                                    continue;
385                                            }
386                                            int n;
387                                            if (j < 0)
388                                            {
389                                                    n = -j;
390                                            }
391                                            else
392                                            if (j >= srcWidth)
393                                            {
394                                                    n = srcWidth - j + srcWidth - 1;
395                                            }
396                                            else
397                                            {
398                                                    n = j;
399                                            }
400                                            int k = contrib[i].n;
401                                            if (n < 0 || n >= srcWidth)
402                                            {
403                                                    weight = 0.0f;
404                                            }
405                                            contrib[i].n = contrib[i].n + 1;
406                                            contrib[i].p[k].pixel = n;
407                                            contrib[i].p[k].weight = weight;
408                                    }
409                                    //setProgress(processedItems++, totalItems);
410                            }
411                    }
412                    
413                    // ----------------------------------------------------
414                    // Apply filter to sample horizontally from Src to Work
415                    // ----------------------------------------------------
416    
417                    // start of Java-specific code
418                    // Marco: adjusted code to work with multi-channel images
419                    //        where each channel can have a different maximum sample value (not only 255)
420                    final int NUM_CHANNELS = work.getNumChannels();
421                    final int[] MAX = new int[NUM_CHANNELS];
422                    for (int k = 0; k < NUM_CHANNELS; k++)
423                    {
424                            MAX[k] = work.getMaxSample(k);
425                    }
426                    // end of Java-specific code
427    
428                    for (int k = 0; k < srcHeight; k++)
429                    {
430                            for (int i = 0; i < dstWidth; i++)
431                            {
432                                    for (int channel = 0; channel < NUM_CHANNELS; channel++)
433                                    {
434                                            float sample = 0.0f;
435                                            for (int j = 0; j < contrib[i].n; j++)
436                                            {
437                                                    float weight = contrib[i].p[j].weight;
438                                                    if (weight == 0.0f)
439                                                    {
440                                                            continue;
441                                                    }
442                                                    int color = in.getSample(channel, contrib[i].p[j].pixel, k);
443                                                    sample = sample + color * weight;
444                                            }
445                                            // Marco: procedure BoundRound included directly
446                                            int result = Math.round(sample);
447                                            if (result < 0)
448                                            {
449                                                    result = 0;
450                                            }
451                                            else
452                                            if (result > MAX[channel])
453                                            {
454                                                    result = MAX[channel];
455                                            }
456                                            work.putSample(channel, i, k, result);
457                                    }
458                            }
459                            setProgress(processedItems++, totalItems);
460                    }
461    
462                    /* Marco: no need for "free memory" code as Java has garbage collection:
463                        // Free the memory allocated for horizontal filter weights
464                    for i := 0 to DstWidth-1 do
465                            FreeMem(contrib^[i].p);
466    
467                        FreeMem(contrib);
468                    */
469    
470                    // -----------------------------------------------
471                    // Pre-calculate filter contributions for a column
472                    // -----------------------------------------------
473    
474            /*GetMem(contrib, DstHeight* sizeof(TCList));*/
475                    contrib = new CList[dstHeight];
476                    for (int i = 0; i < contrib.length; i++)
477                    {
478                            contrib[i] = new CList();
479                    }
480                    // Vertical sub-sampling
481                    // Scales from bigger to smaller height
482                    if (yscale < 1.0f)
483                    {
484                            float width = fwidth / yscale;
485                            float fscale = 1.0f / yscale;
486                            int numContributors = (int)(width * 2.0f + 1);
487                            for (int i = 0; i < dstHeight; i++)
488                            {
489                                    contrib[i].n = 0;
490                                    contrib[i].p = new Contributor[numContributors];
491                                    for (int j = 0; j < contrib[i].p.length; j++)
492                                    {
493                                            contrib[i].p[j] = new Contributor();
494                                    }
495                                    float center = i / yscale;
496                                    int left = (int)Math.floor(center - width);
497                                    int right = (int)Math.ceil(center + width);
498                                    for (int j = left; j <= right; j++)
499                                    {
500                                            float weight = filter.apply(center - j);
501                                            if (weight == 0.0f)
502                                            {
503                                                    continue;
504                                            }
505                                            int n;
506                                            if (j < 0)
507                                            {
508                                                    n = -j;
509                                            }
510                                            else
511                                            if (j >= srcHeight)
512                                            {
513                                                    n = srcHeight - j + srcHeight - 1;
514                                            }
515                                            else
516                                            {
517                                                    n = j;
518                                            }
519                                            int k = contrib[i].n;
520                                            contrib[i].n = contrib[i].n + 1;
521                                            if (n < 0 || n >= srcHeight)
522                                            {
523                                                    weight = 0.0f;// Flag that cell should not be used
524                                            }
525                                            contrib[i].p[k].pixel = n;
526                                            contrib[i].p[k].weight = weight;
527                                    }
528                                    //setProgress(processedItems++, totalItems);
529                            }
530                    }
531                    else
532                    // Vertical super-sampling
533                    // Scales from smaller to bigger height
534                    {
535                            int numContributors = (int)(fwidth * 2.0f + 1);
536                            for (int i = 0; i < dstHeight; i++)
537                            {
538                                    contrib[i].n = 0;
539                                    contrib[i].p = new Contributor[numContributors];
540                                    for (int j = 0; j < contrib[i].p.length; j++)
541                                    {
542                                            contrib[i].p[j] = new Contributor();
543                                    }
544                                    float center = i / yscale;
545                                    int left = (int)Math.floor(center - fwidth);
546                                    int right = (int)Math.ceil(center + fwidth);
547                                    for (int j = left; j <= right; j++)
548                                    {
549                                            float weight = filter.apply(center - j);
550                                            if (weight == 0.0f)
551                                            {
552                                                    continue;
553                                            }
554                                            int n;
555                                            if (j < 0)
556                                            {
557                                                    n = -j;
558                                            }
559                                            else
560                                            if (j >= srcHeight)
561                                            {
562                                                    n = srcHeight - j + srcHeight - 1;
563                                            }
564                                            else
565                                            {
566                                                    n = j;
567                                            }
568                                            int k = contrib[i].n;
569                                            contrib[i].n = contrib[i].n + 1;
570                                            if (n < 0 || n >= srcHeight)
571                                            {
572                                                    weight = 0.0f;// Flag that cell should not be used
573                                            }
574                                            contrib[i].p[k].pixel = n;
575                                            contrib[i].p[k].weight = weight;
576                                    }
577                                    //setProgress(processedItems++, totalItems);
578                            }
579                    }
580    
581                    // --------------------------------------------------
582                    // Apply filter to sample vertically from Work to Dst
583                    // --------------------------------------------------
584                    for (int k = 0; k < dstWidth; k++)
585                    {
586                            for (int i = 0; i < dstHeight; i++)
587                            {
588                                    for (int channel = 0; channel < NUM_CHANNELS; channel++)
589                                    {
590                                            float sample = 0.0f;
591                                            for (int j = 0; j < contrib[i].n; j++)
592                                            {
593                                                    float weight = contrib[i].p[j].weight;
594                                                    if (weight == 0.0f)
595                                                    {
596                                                            continue;
597                                                    }
598                                                    float color = work.getSample(channel, k, contrib[i].p[j].pixel);
599                                                    sample = sample + color * weight;
600                                                    int result = Math.round(sample);
601                                                    if (result < 0)
602                                                    {
603                                                            result = 0;
604                                                    }
605                                                    else
606                                                    if (result > MAX[channel])
607                                                    {
608                                                            result = MAX[channel];
609                                                    }
610                                                    out.putSample(channel, k, i, result);
611                                            }
612                                    }
613                            }
614                            setProgress(processedItems++, totalItems);
615                    }
616            }
617    
618            public void process() throws
619                    MissingParameterException,
620                    WrongParameterException
621            {
622                    ensureInputImageIsAvailable();
623                    if (outWidth == null && outHeight == null && getOutputImage() != null)
624                    {
625                            PixelImage out = getOutputImage();
626                            outWidth = new Integer(out.getWidth());
627                            outHeight = new Integer(out.getHeight());
628                    }
629                    if (outWidth == null)
630                    {
631                            throw new MissingParameterException("Output width has not been initialized");
632                    }
633                    if (outHeight == null)
634                    {
635                            throw new MissingParameterException("Output width has not been initialized");
636                    }
637                    PixelImage image = getInputImage();
638                    if (image.getWidth() == outWidth.intValue() && 
639                        image.getHeight() == outHeight.intValue())
640                    {
641                            throw new WrongParameterException("Input image already has the size specified by setSize.");
642                    }
643                    ensureOutputImageResolution(outWidth.intValue(), outHeight.intValue());
644                    if (image instanceof IntegerImage)
645                    {
646                            process((IntegerImage)image, (IntegerImage)getOutputImage());
647                    }
648                    else
649                    {
650                            throw new WrongParameterException("Input image must implement IntegerImage.");
651                    }
652            }
653    
654            /**
655             * Set the pixel resolution of the output image.
656             * @param width the horizontal resolution of the output image
657             * @param height the vertical resolution of the output image
658             */
659            public void setSize(int width, int height)
660            {
661                    outWidth = new Integer(width);
662                    outHeight = new Integer(height);
663            }
664    
665            /**
666             * Set a new filter object to be used with this operation.
667             * @param newFilter a resample filter to be used for scaling
668             */
669            public void setFilter(ResampleFilter newFilter)
670            {
671                    filter = newFilter;
672            }
673    
674            /**
675             * Sets a new filter type, using the default sampling radius of that filter.
676             * @param filterType the new filter type, one of the FILTER_TYPE_xyz constants of this class
677             */
678            public void setFilter(int filterType)
679            {
680                    setFilter(createFilter(filterType));
681            }
682    
683            /**
684             * Sets a new filter type with a user-defined sampling radius.
685             * @param filterType the new filter type, one of the FILTER_TYPE_xyz constants of this class
686             * @param samplingRadius the sampling radius to be used with that filter, must be larger than 0.0f
687             */
688            public void setFilter(int filterType, float samplingRadius)
689            {
690                    ResampleFilter newFilter = createFilter(filterType);
691                    newFilter.setSamplingRadius(samplingRadius);
692                    setFilter(newFilter);
693            }
694    }