GNOME Bugzilla – Bug 162250
Feature Request: Better image scaling algorithms.
Last modified: 2007-05-07 10:20:58 UTC
Better image scaling algorithms for GIMP would make it more useful for high-end work. Currently, the best interpolation technique in the GIMP is Cubic Interpolation. I would (very much!) like to see the option of using stair interpolation, and especially Lanczos interpolation algorithms.
References to good descriptions of these algorithms would help. Patches to the code would help even more. An implementation in a plug-in might also be valuable as a proof-of-concept.
I'm no programmer, but here are the references I can find. Some of it is over my head, so I'm not sure it all applies. I'm an "end user" with above average computer knowledge, but not in the area of programming, so I can't be of help with proof of concept code, but here is what my research has turned up. Hopefully it will help. Stair interpolation is using a series of small steps to upsample an image to the size you want. Instead of going from 100% to 400%, for example, you might go in 10% increments, like 100%>110%, etc until you reach the desired size. If GIMP does not already implement this feature, it would seem a simple thing to do. I'd suggest having the ability to choose what percentage of upsampling each step was, like between 1% and 50% or something. ImageMagick appears to have the capacity to use a few interpolation methods that are superior to Cubic Interp, such as Mitchell, Information about Lanczos: http://www.netlib.org/lanczos/ http://medimage.bme.columbia.edu/index.php?p=project&ID=4 R. S. Ferguson, Practical algorithms for 3D computer graphics. Natic, Mass, 2001. Pyramid Interpolation (appears to be the only one better than Lanczos as per http://heim.ifi.uio.no/~gisle/photo/interpolation.html): http://sepwww.stanford.edu/public/docs/sep105/morgan1/paper_html/node6.html http://epubs.siam.org/sam-bin/dbq/article/33029 http://www.wisdom.weizmann.ac.il/~mblank/CVfall04/handouts/pyramid83.pdf Spline Pyramid w/source: http://bigwww.epfl.ch/sage/pyramids/ http://www.andrew.cmu.edu/user/sowen/topics/interp.html http://www-inst.eecs.berkeley.edu/~ee290t/sp04/lectures/lec5.pdf http://www.rpi.edu/~yut/Papers/asilomar.pdf I don't understand a lot of this stuff, so perhaps I am not so good a researcher for this as I had hoped to be, but I have sent a few e-mails requesting information on where to find the information you need. Hopefully, what I have listed will be of some help.
I'll have a look at it if nobody want's to take this up.
I have had a response to one of my e-mails requesting information. This is what was returned to me. Hopefully, it will be of some assistance: Hello Shannon, I do not have any links to public domain source code or some descussions of specific code. But I can provide some references to papers describing resampling algorithms. First of all, you can study the NEDI algorithm: http://neuron2.net/library/nedi.pdf The you can turn to some improvements of the original algorithm: http://www.cs.ucdavis.edu/~bai/ECS231/finaltzeng.pdf http://www.ics.ele.tue.nl/~dehaan/papers.html Best regards, Alexey
Created attachment 35386 [details] [review] Patch adds Lanczos scaling algorithm This patch adds the lanczos scaling algorithm. app/base/base-enums.h app/paint-funcs/paint-funcs.c Currently Lanczos2 can be modified by changing #define LANCZOS_WIDTH (2) #define LANCZOS_WIDTH (2...6)
PS:#5 Only tested on B/W image.
paint-funcs.c is already way too large. We should split the scale functions out into separate files. We also need a better description of the algorithm than "Lanczos".
better description ? "windowed sinc filter" splitting up -> app/paint-funcs/paint-funcs-scale.c
Created attachment 35473 [details] [review] Patch adds Lanczos scaling algorithm ! (also add 3 new files which follow) Add Lanczos scaling algorithm and split paint-funcs.[ch] in paint-funcs.[ch] scale-funcs.[ch] RCS file: /cvs/gnome/gimp/app/base/base-enums.h,v RCS file: /cvs/gnome/gimp/app/paint-funcs/paint-funcs.c,v RCS file: /cvs/gnome/gimp/app/paint-funcs/paint-funcs.h,v RCS file: /cvs/gnome/gimp/app/paint-funcs/Makefile.am,v RCS file: /cvs/gnome/gimp/app/core/gimpdrawable.c,v RCS file: /cvs/gnome/gimp/app/core/gimpdrawable-transform.c,v new files cvs diff: I know nothing about ./app/paint-funcs/scale-funcs.c cvs diff: I know nothing about ./app/paint-funcs/scale-funcs.h cvs diff: I know nothing about ./app/paint-funcs/scale-funcs-types.h
Created attachment 35474 [details] completes patch : 35473 scale-funcs.c completes patch : 35473 /cvs/gimp/app/paint-funcs/scale-funcs.c
Created attachment 35475 [details] completes patch : 35473 scale-funcs.h completes patch : 35473 adds file /cvs/gimp/app/paint-funcs/scale-funcs.h
Created attachment 35476 [details] 35475: completes patch : 35473 scale-funcs-types.h completes patch : 35473 adds file /cvs/gimp/app/paint-funcs/scale-funcs-types.h
Adding scale-funcs-types.h is wrong. The *-types.h files are a per-directory thing and the directory is called "paint-funcs". Please read devel-docs/includes.txt
Created attachment 35489 [details] [review] Patch adds Lanczos scaling algorithm ! (removed scale-funcs-types.h) Same as 35473 but scale-funcs-types.h removed RCS file: /cvs/gnome/gimp/app/base/base-enums.h,v RCS file: /cvs/gnome/gimp/app/paint-funcs/paint-funcs.c,v RCS file: /cvs/gnome/gimp/app/paint-funcs/paint-funcs.h,v RCS file: /cvs/gnome/gimp/app/paint-funcs/Makefile.am,v RCS file: /cvs/gnome/gimp/app/core/gimpdrawable.c,v RCS file: /cvs/gnome/gimp/app/core/gimpdrawable-transform.c,v
Created attachment 35493 [details] completes patch : 35489 scale-funcs.c changed include in codde back to paint-func-types.h
The patch would have better attached to bug #158127, but oh well ...
2005-01-11 Sven Neumann <neumann@jpk.com> * app/base/base-enums.[ch] * app/core/gimpdrawable-transform.c * app/core/gimpdrawable.c * app/paint-funcs/Makefile.am * app/paint-funcs/paint-funcs.[ch] * app/paint-funcs/scale-funcs.[ch]: applied patch by Geert Jordaens (after a good deal of reformatting for coding style compliance). This factors the scale routines into their own file and adds a sinc-based (Lanczos) interpolation routine (bug #162250).
*** Bug 158127 has been marked as a duplicate of this bug. ***
Does it make sense to keep this report open as a general request for better interpolation routines or can it be closed as FIXED now?
Please call it Lanczos2, or Lanczos3, or whatever it is. There are several Lanczos functions. This will be a nice improvement over what the Gimp has now, but... Truncating the sinc() function is surprisingly destructive. You'd think all those tiny little terms amount to nothing, but they add up. So, while I an really glad to see this, please leave the bugs open until something wider is implemented. This is especially so if you used Lanczos2 instead of Lanczos3 or higher. If a large window, say 256x256, is too slow then you might try doing the operations in frequency space. BTW, I think you can split up an FFT according to the way the Gimp tiles an image.
Currently it is Lanczos2 however it can be very easely changed to 3..4..n by changing #define LANCZOS_WIDTH (2) in scale-funcs.h. As far as I've looked into the FFT you'd need a base 2 sized image to be able to perform a FFT on it. Without using any kind of specialized library. After implementing Lanczos i also was looking for a way to implement the pyramid algorithm. All hints are welcome.
Well then... how high can you go before performance is intolerable? If Lanczos3 isn't much slower, just use that. Otherwise, it would be good to give the user both. In any case, advanced users will want to know what they're getting. (this is for the menu label) For an FFT, you really should use the FFTW library in any case. It will be much faster than the typical code a person might write, even for images with power-of-2 dimensions. It'll also work on arbitrary sizes. BTW, all of these algorithms will work much better on linear data. While you can declare that users should just work with linear images on a linear display (washing your hands of the mess), reality is that people use sRGB. When parts of the image come out a bit dark, they'll just write it off to general inaccuracy. A choice like this would take care of things: (*) Image data is sRGB (normal gamma) ( ) Image data is linear (gamma=1.0)
Some of us are willing to wait for higher quality scaling if we have to. Maybe you should offer an option to trade off quality for time. I'd much rather have the highest possible quality associated with my name when I produce an image than be impatient, personally.
It appears that: Sinc 256 == Lanczos8 Sinc 1024 == Lanczos10 There's an interesting benchmark here: http://photocreations.ca/fast_test/index.html The note at the bottom is particularly interesting: "The time difference between Nearest neighbor, Bilinear, Poly3, Spline16, Spline36, and Spline64 are some small compared to the quality it does not make sense to run anything lower than Spline36." Probably this is related to memory and cache behavior. If I'm right that "Poly3" is cubic, then perhaps the lower-quality gimp filters could be junked. At least, the default should be set to higher quality.
I just tested the existing code, at best quality. (cubic, with supersampling) Words can't describe it. I'll attach the original zone plate image, along with the result after 36 rotations. I used 15-degree rotations, because I can do them quickly w/o a script. I used clipping for speed, and thus ended up with a circle... but doing otherwise does NOT give a square. (it's edge treatment and alpha again, making a mess)
Created attachment 35872 [details] original zone plate test image rotate this 36 times to test interpolation
Created attachment 35873 [details] test results this is after 36 15-degree rotations (cubic, with supersampling)
This test is completely artificial and has almost no meaning for real-world usage scenarios.
The test is quantitative. What alternative is there? "Gee, it scaled once without glaringly obvious damage." Counting rings is easy and, plus-or-minus one, repeatable by anyone. There's almost nothing subjective about it. If you can pass the zone plate test, interpolation works. It's as simple as that, unless you do something really weird with color channels. Except for NOP interpolation (pick nearest pixel), which is needed for indexed images, anything that can't keep at least a half dozen rings visible is ripe for deletion.
Unless I got you wrong you were trying to show that Cubic interpolation would be completely broken. Even though it fails your little test, it is still a reasonably good interpolation routine for a lot of tasks and there's no reason to "junk" them. Ultra-high quality interpolation routines should be left to plug-ins, they don't belong into the GIMP core. I am not saying that we should not improve things further but I don't see a point in trying to optimize an artificial test case.
I think that cubic ("Poly-3") should be the quick-and-dirty choice. That it doesn't pass my test is a shock to me. I think it has some sort of a bug. Cubic should work better AFAIK, though of course not the best.
Ultra-high quality interpolation routines need to be in the gimp core unless the core provides a way for a plug-in to hook into the normal places where interpolation is used. For example: the rotate tool, scale layer, scale image... (there seem to be many places -- I'm sure you can count far more) If the ultra-high quality interpolation routines go into plug-ins, then the others can go as well. They belong on an even footing, especially with respect to distribution and user interface. Even though my computer is slow, I want to be sure that I never use any interpolation that is less than the best. This means that my choice sticks, across the whole Gimp UI, in every tool, even if I restart the Gimp. (excepting indexed images, which can only be done via nearest pixel)
a) Lanzcos may be best for scaling up, however it is actually worse than nearest-neighbor when scaling down. it looks the same as NN but it creates invisible colors. i tried it on a b/w image made quickly with penciltool and fill -- it increased colorcount 2->3 while looking identical to nearest-neighbour interpolation. On more complex images it invisibly multiplied the colorcount by 100 or more. Cubic should still be counted as best overall. b) some artifacts can appear when scaling up. see the attached images.
Created attachment 36117 [details] lanzcos bug: image before scaling.
Created attachment 36118 [details] lanzcos bug: image after scaling 2x. note the artifact in bottom-left corner.
Regarding comment #33: Keeping a b/w image as b/w is a special request. (you're weird) Depending on the image, you may wish to: a. blur (to undither), scale w/ a lanczos scaler, and re-dither b. scale with nearest-neighbor c. trace to create vectors, scale that, and then render a bitmap d. use a hack like HQ4X (the above applies in general to cartoon-like images) The artifacts you see are mostly expected and correct. Essentially, you can't make a silk purse from a sow's ear. Still, I have to say it did a pretty decent job! The artifacts are similar to JPEG ones, and will generally go unseen by humans. Higher levels will be nicer. (Lanczos3 instead of Lanczos2, etc.)
Ok, I'll assume you're not purposely acting lame and you just misunderstood me... GIMP's Lanczos interpolation does not interpolate in any sensible way when scaling down. It does not create the antialiasing normally created when the block of pixels corresponding to a particular result pixel are different colors. Compare with linear or cubic, both produce sensible results here, whereas lanczos is directly comparable to nearest-neighbour. I'm attaching a comparison between scaling my testcase down by 50% using gimp, and scaling it down 50% using ImageMagick. In both cases i used Lanczos interpolation ( "-filter Lanczos" is how to tell imagemagick to use it)
Created attachment 36120 [details] side by side comparison of GIMP vs Imagemagick Lanczos interpolation Gimp on left, ImageMagick on right.
Have you tried increasing the lanczos window like suggested in #21? Lanczos2 as it is now in cvs is rather a low value. The value is for me still a open issue. what value should we set(speed/accuracy)?
I increased it to 5 (identical results) then 64(complete blankness -- obviously too high).
I'll take this up and check (may take a while) so be patient. :-)
I suggest that before any further changes to the code are done that the crashes in the drawable transformation code are fixed. It would probably make sense to port that code to use the pixel_surround utility function. Unless this is fixed soon, we will have to revert the addition of the new interpolation routine and I would like not to have to dig through too many changes when this should become necessary.
fine by me, I'll look in to it asap. (however I've probably not much time to spend this week). All observations / testcases are welcome.
Created attachment 36233 [details] [review] gimpdrawable-transform.c now Lanczos routine uses pixel surround. Modified : gimpdrawable-transform.c now Lanczos routine uses pixel surround.
Since it does fix the crash, I've applied that patch (after some minor cleanups): 2005-01-19 Sven Neumann <sven@gimp.org> * app/core/gimpdrawable-transform.c: applied a patch from Geert Jordaens that fixes the crash in the drawable transformations using the Lanczos interpolation type. The result is somewhat wrong though :( The result of the transformation doesn't look quite right though.
Created attachment 36235 [details] [review] Correction for scale-funcs.c scaling up looks better. Correction for scale-funcs.c scaling up looks better.
It got a good deal slower but scaling up now does actually look a lot better. The results for scaling down are still rather unsatisfactory though and the drawable transformations using the lanczos routines are obviously broken. 2005-01-20 Sven Neumann <sven@gimp.org> * app/paint-funcs/scale-funcs.[ch]: applied patch from Geert Jordaens that improves results of the Lanczos interpolation routine.
Created attachment 36301 [details] [review] gimpdrawable-transform.c now Lanczos routine uses pixel surround. and the transformation of images seems to be working also.
That last patch looks as if it would not apply against CVS. Note that I already applied your earlier patch.
probably difference between anoncvs and cvs I'll give it another try tomorrow.
Created attachment 36326 [details] [review] gimpdrawable-transform.c fixes transform
Congrats, seems to work nicely now: 2005-01-21 Sven Neumann <sven@gimp.org> * app/core/gimpdrawable-transform.c: applied a patch from Geert Jordaens that seems to fix drawable transformation using the new Lanczos interpolation routine :)
Now back to the discussion on whether this is good enough to close this report as FIXED. I would suggest that the discussion is somehow brought to an end here soon and that new reports are opened if there are further enhancement requests. Having too many comments in a single bug report makes it unlikely that it will be picked up anytime later.
It doesn't act like a color to alpha filter anymore, but is still buggy. Try the following: - create a square image, e.g. 200x200 pixels, filled with any color - place two guides at 100 on both axes - use the rotate tool to rotate the layer by 15 degrees - repeat two more times You now have a layer that is rotated by 45 degrees, so the corners should by on the guides you added before. This is true for cubic interpolation (try this with a copy of the same layer for reference), but Lanczos moves the layer a noticeable amount downwards, and a bit to the right. Other transformations might suffer from similiar problems.
Closing as FIXED on the basis of comment #53 -- i.e., this bug report has gotten too long. Problems with scaling should be reported as new bugs. Note in particular bug #162250.
Aargh! Note bug #167956, that should have been.
*** Bug 436548 has been marked as a duplicate of this bug. ***