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 }