GNOME Bugzilla – Bug 166130
Better image scaling algorithms, redux
Last modified: 2008-09-07 07:54:32 UTC
A follow-up from bug #162250: Feature Request: Better image scaling algorithms. Sven suggested a new bug report ("Having too many comments in a single bug report makes it unlikely that it will be picked up anytime later.") (Un-disclaimer: I do machine learning and image processing research at BYU.) First, from an algorithmic standpoint (UI excluded), it would be VERY easy to add a few new interpolants. This paper goes over a bunch with symmetrical, separable kernels: http://www.cvgpr.uni-mannheim.de/hornegger/MEDBV/handouts/lehmann.pdf Page 1052 describes the algorithm template they're used in. One other nifty resource I found was this: http://www.ldv.ei.tum.de/media/files/dvi/vorlesung/z03_reconstruction_filters.pdf page 223. From it, I wrote some code for one of my own projects: /* 1/6 * if |x| < 1, (12 - 9*B - 6*C)|x|^3 + (-18 + 12*B + 6*C)|x|^2 + (6 - 2*B) else if |x| < 2, (-B - 6C)|x|^3 + (6*B + 30*C)|x|^2 + (-12*B - 48*C)|x| + (8*B + 24*C) else 0 (B, C) = (1, 0): cubic B-spline (0, C): one-parameter family of cardinal cubics with (0, 0.5) being Catmull-Rom (B, 0): Duff's tensioned B-splines */ static inline float cubicKernel(float x, float b, float c) { float weight; float ax = (float)fabs(x); if (ax > 2) return 0; float x3 = ax * ax * ax; float x2 = ax * ax; if (ax < 1) weight = (12 - 9 * b - 6 * c) * x3 + (-18 + 12 * b + 6 * c) * x2 + (6 - 2 * b); else weight = (-b - 6 * c) * x3 + (6 * b + 30 * c) * x2 + (-12 * b - 48 * c) * ax + (8 * b + 24 * c); return weight * (1.0f / 6.0f); } static inline float bicubicDistWeight(float dy, float dx, float b, float c) { return cubicKernel(dy, b, c) * cubicKernel(dx, b, c); } static inline float bsplineDistWeight(float dy, float dx) { return cubicKernel(dy, 1, 0) * cubicKernel(dx, 1, 0); } static inline float catmullRomDistWeight(float dy, float dx) { return cubicKernel(dy, 0, 0.5f) * cubicKernel(dx, 0, 0.5f); } So if (B,C) = (0,0.5), you've got a Catmull-Rom kernel, which is what GIMP uses right now in scale-funcs.c. If (B,C) = (1,0), it's a B-spline kernel, which results in much a smoother (C-2 continuous) result, which GIMP could *definitely* use. Even better: if the bicubic interpolator were coded to smoothly transition between (0,0.5) and (1,0), GIMP could give the users a sliding scale between "smooth" and "sharp" bicubic interpolation. Photoshop's "Bicubic Smooth" and "Bicubic Sharp" options have nothing on that. General-interest FYI: Albert Cahalan's baby, Lanczos, may be the most "correct" interpolant under a certain set of assumptions. Realize, however, that you can always invent a set of assumptions (along with a set of fitness tests) that makes one interpolant more "correct" than another. In fact, you can *prove* that it's *impossible* to make a perfect generalization about between values from a finite set of samples - a result from machine learning that generally gets overlooked by the image processing community.
*** Bug 166132 has been marked as a duplicate of this bug. ***
Thanks for the material. Of course you are welcome to submit patches that implement some of these things. And of course an important constraint is that ordinary users not be confused by too great a plethora of interpolation methods. It might turn out to be worth creating a scaling plugin that implements methods valuable in some cases but not generally valuable enough to be worth adding to the core tool -- it might also be worth looking into the possibility of doing scaling using modules of the sort used for color selectors.
*** Bug 306455 has been marked as a duplicate of this bug. ***
Pictures would help. I'm very interested in better scaling algorithyms, particularly those that favor 'correct' shape over 'correct' color -- ie treat edges well. I have implemented a scaling plugin already. I might have a go at implementing a prototype of this if you would show a visual comparison of the results of this algorithym versus linear and cubic. Lanczos needs to die. It's worse quality than nearest neighbour for scaling down (it adds colors, but with no visible difference from the nearest-neighbour result), and for scaling up it's just like running a sharpen filter on it after a normal linear scale.
David, lanczos has been removed for reduction, it is not appropriate. Your comments indicate that you are using it as a general filter, it is not . It is primarily a technique for removing pixel quantisation in an expanded digital image. This it does very effectively. It is not a flawless technique althought the articfacts are descrete enough for most photo application, less so on block graphics. Look at current cvs if you want to see the current state of play: lots of recent changes. http://tinyurl.com/kg4no Dont tell me you can do that with linear plus sharpen! Neil, thanks for bringing this whole topic up and for the links. Very useful. As Bill said there is a danger that making this have too many features will meet resistance from some. At the same time it would be shame dumb-down the Gimp for those seeking top quality results. What do we say? "If you want really good image processing the Gimp is not for you. Try PhotoShop." I would suggest an Advanced button that presents a fuller set of choices and a more configurable interface. This keeps it nice and clean for new users while still offering top quality results for more serious users.
I've been looking at implementing some of the splines suggested in #1 , this has brought up some interesting finds. http://tinyurl.com/l2aeg This shows a fairly arbitary b/w test image. Firstly the original at x400% then scaled up 400% using the menu scaling implemented in scale-funcs.c . Respectively , gimp's usual bicubic 4 pt interpolation by Catmull-Rom ; then Neil's Catmull-Rom above; finally the softer cubic B-Spline. First I think this shows the value of adding something like B-spline, it is significantly different from Catmull-Rom. Second I am a little unsure how to interpret the difference between the two Catmull-Rom results. While applying nominally the same maths by different computational methods the results are very different. The first uses an expansion of the matrix multiplication on four adjacent points along the lines discussed here: http://www.mvps.org/directx/articles/catmull/ ; the second uses a lookup table filled basically using Neil's formular above. I would suggest the latter gives better interpolation. Specifically the 45 degree single pixel staircasing gets almost completely smoothed whereas existing cubic method preserves a lot of erroneous detail here. Does this imply an error in one or other methods? Thanks for any enlightened comments.
Created attachment 74450 [details] same image comparing lanczos 8 . Extensive ringing. lanczos8, window 15x15 with lanczos window and blackman window
relating to the difference between the bilinear cubic Catmull-Rom (current method) and applying the same spline using lookup table as shown in images 2 and 3 of the image linked in #6 above: The coefficients used in both methods seem to check out with detailed research I have done on both implementations. My conclusion is that the marked difference is due to the current method being bicubic, ie it interpolates in x then interpolates the resulting data in y. The lookup method interpolates the source data in both axes unmodified. The improvement in the result is so marked that , unless anyone can see a major drawback, I will post submit a patch for this to replace bicubic.
Created attachment 74482 [details] photo image comparing bicubic to lookup implementations of Catmull-Rom bicubic is slightly sharper but shows noticable sampling errors in hair.
Created attachment 74483 [details] bird beak comparison a second "real" image , note the beak. Not just line graphics that have straight edges.
I'd like to regain some momentum on this one. It would be good to have some improvements in the scaling algorithms to offer in 2.4 . It looks like lanczos is now behaving correctly which is a good addition so I'd like to focus on bicubic. It seems there can be little doubt that the removal of the filter artifacts shown in the kingfisher close-up above is a significant improvement. Equally this is clearly demonstrated in the arbitary line graphic linked in #6. http://tinyurl.com/l2aeg When this was discussed on IRC, Sven expressed some reservations about simply replacing existing bicubic with the more complex implementation primarily because of the slight softening it incurs. This can be noted in the line graphic and the zoomed portrait linked in #9. Although this softening is very slight, it is decernable. This may or may not be desirable depending on the nature of the image. So what is the best course of action? 1a) Impose the current filter with heavy artifacts 1b) Replace it with the cleaner but softer one. 2) Add the new filter to enums and allow the user to choose the most suitable for his needs. 3) some other approach. What would be best and should we add a 2.4 milestone? gg
I don't think we still want to do those changes for 2.4. It's way too late for that. But we should address this for 2.6 which is supposed to be released only a few months later. The best solution is probably to improve the existing algorithm. Adding more choices will only confuse the users.
OK, would you like to set the milestone to 2.6 then? At least that will determine a time frame. I do wonder about this "will only confuse the users" approach though. I see it quite often in gimp. You have defined the aim that Gimp will be a "high-end" graphics manipulation program, maybe we need to start aiming at high-end users and not regarding everyone as knumb-nuts who will get confused by the slightest choice in life. Once the user has realised that there is a choice of interpolation method - which isn't immediately obvious - I really can't imagine someone of moderate intelligence being floored by the difference between 4 and 5 choices of technique. I would be happy to have a choice to play with to suit my needs, experiment and see what works best. By your own definitions gimp is not aimed at the "load from my camera and email to my Mum" user base. It claims to be "high-end". Dont you think we need to credit users with having enough savvy to use a dropdown list without too much angst? Give them a reasonable default until they find their feet but once they find thier way around give them the full power gimp can offer, not hold them back in case they get "confused". Look at the OP here. Looks like he's much more clued up on digital image processing than both of us put together. We probably should not be too condecending to those using gimp. It's a recurring issue so worth a bit of thought. Can we expect to create a "high-end" program if we aim it for dummies. I suspect not. There's lots of "lite" software given away with every set of camera/printer/scanner driver CDs that's designed not to confuse anyone at all. As result it's all very limited. I thought that the gimp was setting the bar a bit higher. Getting back to the technical issue here, do you think that this is an inherent trade-off or that we can get the best of both worlds , that both implementations are fautly? gg
PS, "interpolation method -which isn't immediately obvious " not saying there is any fault with the interface here, just that s.o. thinking they just wanted to resize their image is going to say "what's interpolation, what bicubic" . This is quite technical and abstract for s.o. more interested in graphics than in numerical filters. Once they understand that the number of choices is not likely to confuse them, it should be an asset if they produce different features.
We should at least try to find a solution that avoids the introduction of more choices. If it turns out that this is not possible, we can still do it. Such discussion doesn't belong here though. That's what the mailing-list exists for.
Created attachment 89548 [details] [review] Sinc(lanczos3) downscaling patch This is a patch to enable downscaling with Sinc(lanczos3) interpolation for svn (06/07 2007).
Could you please explain what this patch does? It also doesn't follow the GIMP coding style, even breaks the style in a few places where it used to be correct.
OK, I'll explain it. (Coding style... I'll try it...) This is a patch to enable downscaling with Sinc(lanczos3) interpolation for svn (06/07 2007). GIMP's downscaling interpolation algorithms is not lanczos3 if user select "Sinc(lanczos3)" in UI. This is a problem. The patch provides the ability of a downscaling interpolation by Sinc(lanczos3). (to be continued...)
Created attachment 89583 [details] The comparison between some image filters. This is the comparison image between some image filters. ImageMagick's "lanczos" and "sinc", and GIMP's new patched "Sinc(Lanczos3)" and old "Sinc(Lanczos3)" in GIMP 2.3.16. This comparison is provided by 1/2 downscaling of the two 512x512pix images. (Original images are follow)
Created attachment 89584 [details] 512x512 CZP (Circular Zone Plate) One is the 512x512 CZP (Circular Zone Plate) image. It generated by ImageMagick's "convert": % convert -size 512x512 xc: -fx '(1+sin(pi/512*((j-256)*(j-256)+(i-256)*(i-256))))/2' czp512.png This is the test pattern of interpolation algorithm's Moire fringes and blur characteristics.
Created attachment 89585 [details] 512x512 stripes Another is the stripes image. This image is constructed by four images which are generated by ImageMagick's "convert": % convert -size 512x100 xc: -fx 'j&1?1:0' stripes01.bmp % convert -size 512x100 xc: -fx 'j&2?1:0' stripes02.bmp % convert -size 512x100 xc: -fx 'j&4?1:0' stripes04.bmp % convert -size 512x100 xc: -fx 'j&8?1:0' stripes08.bmp This is a test pattern to check algorithm's blur characteristics, more.
The patched GIMP's lanczos3 downscaling is not good in blur resistance characteristics (may be some mistakes in the algorithm...), but good in Moire fringes resistance characteristics. The patch counts out processing performance. The processing speed may be down.
Created attachment 89588 [details] [review] Sinc(lanczos3) downscaling patch Is this better?
I don't quite understand what you are trying to do here. It seems from your attachment to #19 that the "old" ie existing code makes a much better job of preserving detail than your patch or imagemagick's lanczos. Neither do I understand why you say the current code "is not lanczos". Could you explain? Form a quick read of your last patch it seems that you have added a means to have a different lanczos window in x and y. Since it is the order of the lanczos filter (L3, l4. etc) that determines the width of the lanczos kernel this does not tie in with my understanding of the maths. It may be best if you open a discussion on the gimp-devel mailing list if you think there are some fundamental flaws in the current implementation, since this is not the place to post such a discussion. It's great if you have some time to patch this with improvements but we need firstly to agree there is a flaw and secondly to see a patch that improves the output not degrades it. BTW thanks for posting the scripts to create the test images. Good idea.
The circular pattern you posted is an excellent demonstration of the difference of cubic/lanczos on scaling up. The original has moire deffects , cubic is good but retains a fair level of moire artifacts. Lanczos 200% is near perfect. scaling down on current svn gimp produces simliar yet different results with both. L3 seems a bit more contrasty as noted elsewhere but I would not say one was clearly "better" than the other for this single , subjective test. Yuu, please make sure you have current svn. Sven has made some alterations here in the last few days. It seems from your comments that you may be running older code.
Please note that the recent change was done to fix a crash (see bug #443640), not to improve the quality. We absolutely need to stabilize for the 2.4 release.
I believe the Lanczos code is stable. You will note that crash was due to an apparently untested mod to avoid calling the lanczos code on image reduction. Again, my reservations about L here are just suitability of this filter not whether the code will work. I am convinced that it correctly coded and stable.
This patch is relating the patch on bug #443640. I tested it and that's OK. By the way, the current codes interpolate by Lanczos in upscaling, but it don't interpolate by Lanczos in downscaling. Current code is only follow upscaling. I just mention about downscaling, NOT upscaling. The fix of bug #443640 determines only change the calling function to scale_region_lanczos(). However, scale_region_lanczos() interpolate only upscaling case. If you say "It's a feature", you make GIMP a liar. In addition, Cubic and Liner are also not collect in downscaling. These are call same function when downscaling and provide same results. You should check it.
Created attachment 89635 [details] Sample points difference between downscaling and upscaling. This is the difference between downscaling and upscaling. One mass means one pixel. Sample points must be increased when downscaling. However, current scale_region_lanczos() doesn't increase sample-points when downscaling. This is the problem.
Created attachment 89636 [details] less abstract comparison of scaling algorithyms "In addition, Cubic and Linear are also not correct in downscaling." I verify this; cubic and linear produce no difference vs each other in the result of downscaling. This will become relevant when scaling factor is < 50%, since then, decimation should begin to use more than 2x2 input pixels for each output pixel. I have tested this patch to improve the lanczos downscaling, and I agree it is much superior to the old 'lanczos' downscaling, as well as better than the cubic and linear downscaling; in particular it preserves detailed shapes much better. My test was on a much less abstract image - Pixel art by Henk Nieborg, who is known for incorporating an astounding level of detail in his pixel art. It is attached with this comment. It compares cubic/linear, old lanczos (before Yuu's patch) and new lanczos (after Yuu's patch).
>>In addition, Cubic and Liner are also not collect in downscaling. >>These are call same function when downscaling and provide same results. correct, shrink_line does not use Catmull Rom spline, the code is the same for both. I dont know why this was done. I would guess historically for speed since there was thought to be little difference when condensing data. That should probably be reviewed. Improvements could be made. Yuu, thanks for #29 that makes it a bit clearer what you are aiming to do. The current implementation is lanczos3. What you are doing is increasing the order of the lanczos filter as downscaling ratio increases. This brings up several points. 1/ computation goes up horribly as you increase the lanzcos order. Beyond 4 this will become unusable in a lot of cases. 2/ it does not make sense to do this. The more the image is downscaled the less there is any need for added precision. Any improvements should be limitted to small downscale ratios. 3/ you should test your patch on block graphics as well. This is where the major defect of Lanczos, ringing, is most visible. This is the reason I abandoned using L4 on scale up because as well as the vast increase in computation, the ringing got ugly. This may be different on downscaling but you should definately investigate this. 4/ I dont see this a being more correct implementation of Lanczos3 since it is not L3. There may be some case for using L4 on small downscale ratios if this can be shown to produce better results on all image types. It would be great if this is the case. Thanks for your input , it's always good have a fresh look at what's been done.
IMHO, the major improvement to do on all of this would seem to be implenting the catmull-rom spline on downscaling.
The fundemental problem here is that when reducing an image several data points are within the range covered by the new point so other methods are available. Assuming the same Nearest/Linear/Cubic choice is applied is wrong. In fact the current code does *neither* linear nor cubic fit on reduction, it takes a weighted average of several points. This accounts for the softening of the image noted above. Linear scale up also averages data except that in that case it is equivalent to linear interpolation so the label LINEAR is accurate. The misrepresentation of what is being done is due to presenting different functionality (scale up , scale down) within the same interface with the same options. Taking the average could losely be called "linear" , so if cubic did fit a spline we would not be too far off.
Created attachment 89676 [details] comparison of lin/cub/L3 on 50% reduction all shown at 200% with original image order:original-lin-cub-L3 linear is existing "linear" = "cubic" , third image is new catmull-rom code, finally existing lanczos code. I'll submit a patch after some more testing. Started ML topic to discuss this : [Gimp-developer] improving image scale: reduction
Yuu, looking back at your attatched image in #19 I think you are misinterpretting what you see. The fact that your code and ImageMastick produce less moire rings is a defect not a bonus! The only reason there are no rings away from the centre is because those images have lost all detail. If you blur the output of the "old" lanczos you can get rid of the moire effect as well. A better test of the quality would be to count how many of the original concentric rings are still visible in the reduced images. The fact that the existing code shows detail retained right upto the edge is a nice demonstration that gimp>ImageMastick (at least on this transformation) ;)
s/ImageMastick/ImageMagick/g By the way, you have misunderstanding. Upscaling and downscaling/downsampling are differ. In downsampling, lanczos works as Low-pass anti-aliasing filter (LPF) (but not just only LPF). So, hi-frequency parts are cut. Passing these filters are called "decimation". "If you blur the output of the "old" lanczos you can get rid of the moire effect as well." is true. That is OK, because passing the process of blur is also decimation, but different filter window function waveform.
I'd be interested in following up this conversation but it could be quite long and bugzilla is not the place. Could you take this up on gimp-devel or email me directly. (I'm in the CC list below.) Thx.
OK. I'll subscribe gimp-devel ML.
I'm sorry, I'm too late. I understand improvement of image resizing should importing into GEGL. Thx.
No you're not too late. This needs to be correctly implemented. What was suggested be defered to GEGL was the whole None/Lin/Cubic misnoma. These are interpolation techniques. They are neither is needed nor what is being done for downscaling where decimation is required. That will require a major rethink of the interface and the code. That is what has been put off to 2.6 It is intended for lanczos to be included in 2.4 release. I would like to see this technique correctly implemented for decimation. The current code "looks" OK but as you say is not correct theoretically. This has been bugging since this went in and you were right to bring it up. This can easily be modified since it is very close to current lanczos interpolation code. Now I have had time to go over your code I think you are basically correct, I had misunderstood what your diagram in #29 represented. For future reference the following link is a useful explaination of decimation that will also help in the chosing better equivalents for Linear and Cubic when the time comes. http://www.worldserver.com/turk/computergraphics/ResamplingFilters.pdf What worrys me about your patch is the heavy ringing seen most clearly on the straight line portions of your attachment in #19. As a subjective comparison ImageMagick does not produce this artifact. Have you looked at their code? Maybe it used lanczos 2 for decimation. Also, looking at the frequency responces in that link, it would appear that Lanczos 2 would be nearly as good since any passband defects are close to the limit of the 8 bit resolution of Gimp. This would help greatly in keeping CPU load within reason as the decimation kernel gets longer with greater reduction. gg/
Does the proposed patch fix bug #448087 ?
I've not seen that effect and the bug reporter says he does not know how to reproduce it. Have you seen this? I'm working on tidying all this up using Yuu's patch but I am seeing some asymetry using his patch alone. Once I have a consolidated patch I'll try to provoke the bug but if you have any hits about when it occurs pls post. Thanks for flagging the issue.
>#41 Maybe NO, it doesn't, but I cannot reproduce it, too. P.S. I'm continuing debugging of my patch.
please try to debug before submitting a patch.
hmm , why is gimp image properties telling me the zoneplate in #20 is RGB colour space when it's a 16b greyscale?
Because it IS an RGB. * GIMP filters that are RGB-only work on it. * attachment.png PNG 512x512 512x512+0+0 DirectClass 547kb says 'identify' * attachment.png: PNG image data, 512 x 512, 8-bit/color RGB, non-interlaced says 'file' * Converting it to Greyscale and resaving it reduces file size from 560k -> 200k Your sense of what is a colorspace needs reeducation. Of course an RGB image can hold exclusively greyscales -- it just wastes space, it's not illegal (and it can be convenient if you plan to apply color effects to it later.).
Thanks for the explaination. So it seems I have to rely on external imagemagick tools to get this info since the gimp info is not providing this detail. It is also surprisingly difficult to find out the full file name of a currently open image. Unless I'm mistaken this appears neither in image properties nor file properties. This is drifting a bit OT so I should probably open a new bug about that. I've made some good improvements to both speed and sharpness of Lanczos but still working on integrating Yuu's suggestions to provide correct reduction. Some unacceptable anormalities keep poping up. thx for the help.
The image's colorspace is displayed in the Image properties dialogs as well as in the default image window title. It can also be verified by looking at the Image->Mode menu.
See bug #452782 for a comparison of the different "interpolation" methods used for downscaling an image. Looks like we should better try to get this sorted out for the 2.4 release.
Also see bug #464466 which is basically a duplicate of this one but contains some new ideas and code to address the problem.
Doesn't see to be much activity here. Let's see if someone can buckle down this for 2.8.
Created attachment 114699 [details] original kingfisher head shot for reference
With bug #464466 closed as FIXED I think we can close this as OBSOLETE.