GNOME Bugzilla – Bug 358481
Numerical accuracy in Lanczos routines
Last modified: 2006-11-07 21:24:57 UTC
Please describe the problem: Re-evaluation of data type and number off elements to ensure image data is not degraded. Current settings typically produce an error of 1 bit in each colour of each pixel. While not likely to shock they eye over a single operation, it would seem preferable to ensure the data is not gradually degraded, esp. where Lanczos is chosen as the interpolation method for all transforms there could be more significant accumulated errors. Since the possible error in the value of sinc() due to using a lookup table is of the order 1e-3, using gdouble seems unnecessary. To ensure integrity of the image I suggest LANCZOS_SPP=4000 . Using gfloat will double array mem to 80kB. Setting up the array does not seem to a significant part of execution time. I'll wait for any comments on gimp-devel then post a patch to scale-funcs.* Steps to reproduce: 1. 2. 3. Actual results: Expected results: Does this happen every time? Other information:
Created attachment 73729 [details] [review] patch to set 4000 and gfloat I did not expect to see it but I can confirm small but visibly detectable improvement in quality with spp=4000.
Another factor which contributed to this improvement and would be of equal magnitude to the SPP change - x_shift = (gint) ((dsrc_x - src_x) * LANCZOS_SPP); - y_shift = (gint) ((dsrc_y - src_y) * LANCZOS_SPP); + x_offset = (gint) ((dsrc_x - src_x) * LANCZOS_SPP +0.5); + y_offset = (gint) ((dsrc_y - src_y) * LANCZOS_SPP +0.5); I'll wait until some of these patches get committed because it is becoming pretty unmanagable from this end trying to triage hundreds of lines of diff in order to post single issue patches. In the meantime I'll post those trivial changes and CC geert on this.
gg, can you perhaps join forces with Geert so that you two review your patches to the Lanczos code? If you could feed us with patches that you two agreed on should be committed, we will make sure that they get into CVS as soon as possible.
gg, I must say I alsog got a bit lost in what patches are applied. Currently I think (pretty sure) the gimpdrawable-transform.c contains a correct implementation. It also handles the borders better by copying duplicating the border pixels if the kernel goes over the border. Could you explain why adding the 0.5 x/y_offset? Currently I think it is better to have a seperate implementation in gimpdrawable-transform.c and scale-funcs.c. Basicly I ported your suggestions for scale-funcs.c to the gimp-drawable-transform.c. I may find some time saterday or sunday to work on or review a patch.
geert, using int() on the calculation of x/y_offset will truncate not round. The +0.5 is that classic solution to that situation. At first I thought adding this extra precission was a waste of time in inner loop of all this but doing some calculations of the error induced in the result when we are off by one array element gave a 1 bit error in every plane of every pixel. Small but not negligable. Fixing this and increasing the array size produces worthwhile improvements. This patch was made against current cvs when it was posted , and addresses soley this issue so there should be no confusion there. But there are too many non committed patches here, that is the cause of some confusion and makes it difficult for us to syncronise efforts. (which is what cvs is for!) Yes, I agree your transform code deals better with borders, I already added a FIXME to scale_funcs.c to that this needs attention. @sven. I CC'd Geert to this bug and asked him for comments which he has done but syncronising efforts is hard since a lot of these patches are not getting committed. I had to stop following his efforts on the offset bug because I could not work out what patches were needed from different threads. It seems he is having similar probs here. I understand if there is not enough time to review all this in a short time scale but that seems to be the cause of cvs failing to help us work concurrently. You said you would like this fixed for inclusion in 2.4, Geert has limitted time , I may be able share some of the load if we can syncronise our efforts. If cvs is not able to keep up with more than one person making changes can you suggest another method? thx
gg, Geert: the problem is not that CVS is not capable of handling commits by two people, or that we don't have enough time to commit some small patches. The problem is that you two seem to be the authorities wrt the lanczos code and that none other the other developers understands it well enough or don't have the time to read up on all the stuff. So, what Sven is asking for is that you two mutually review your patches, and we will commit them when you both said they are fine.
mitch, thanks for clarifying. I'll try to get some mutual reviewing OKed with geert and get some of this committed although I know he has limitted time and cant always come straight back on questions. geert , does this accuracy tweek make sense to you? If you want to discuss details email me directly or on gimp-devel. Also if you can post a new patch against current cvs for the offset bug this w'e I'll have a look and see if I can spot anything. It must be some annoying glitch , this is so close.
For the moment I do not have any patches open so if the patch GG has is against the current CVS it is fine by me. So if gg could adress the boreder handling in scale-funcs.c there won't be any collision.
thanks , just to clarify, if I build current cvs that represents where you are with the offset issue. If so could you make the patches in that thread as obselete? That is what was confusing me. IIRC you drawables code does not use LANCZOS_SPP from scale-funcs.h so if your agree with my comments here you may want to look at the accuracy issue there. I'll try to find time during the week to add some more rigourous border modes to scale-funcs.c Thx.
Since Geert has said (on IRC) that he approves of it, I have committed the patch from comment #1 to HEAD: 2006-10-11 Bill Skaggs <weskaggs@primate.ucdavis.edu> * app/paint-funcs/scale-funcs.[ch]: apply patch from GG to improve accuracy of Lanczos, from bug #358481. Leaving open until the issue raised in comment #2 is resolved.
Created attachment 74520 [details] [review] address changes mentioned in comment #2 additional to prev patch , adds accuracy tweek from #2 and cleans up +2, -2 , -0.5 paradigm with some clearer explainations about why it's there. No functional chnages, just rationalisation and comments.
Attachment from comment #11 committed. 2006-10-12 Bill Skaggs <weskaggs@primate.ucdavis.edu> * app/paint-funcs/scale-funcs.c: apply modified patch from GG to improve accuracy of Lanczos, probably fixes bug #358481. Is this bug fixed now?
thx, marking as fixed.
sorry for the formatting errors, I'll pay more attention to detail next time. However, in looking over your changes I saw one that got away: - const gdouble dx = LANCZOS_WIDTH / (gdouble) (LANCZOS_SAMPLES - 1); + const gdouble dx = LANCZOS_WIDTH / (gdouble) (LANCZOS_SAMPLES); Could you add that to cvs. It'sa detail but no sense in leaving wrong. This is partly due to having so many uncommitted changes. I have to keep backing out to separte different bugs and fixes and I sometimes end up undoing something I have already fixed. I'll ping you on irc and see if we can tidy up some loose ends. thx.
Created attachment 76007 [details] [review] patch remove duplicate coding of lanczos lookup table reopening and adding this patch to ensure only one version of the lanczos lookup table code. It is currently coded differently in gimp-transform-region that missed out on the accuracy improvements and uses 160MB for the table instead of 80MB. It's pretty trivial so let's get this commited a.s.a.p. gg
2006-11-05 Sven Neumann <sven@gimp.org> * app/core/gimp-transform-region.c: applied patch from gg that removes duplicated code (bug #358481).
thanks for the quick commital. I see the following comment got edited. Not sure what was wrong with it but it is certainly less clear now what "window" refers to. In the context of gimp the immediate reading of someone new to the code will be some reference to a gimp window. They will not realise it is the lanczos windowing of the sinc function. If a comment is there it should help not confuse, something more explicit would be better than something more vague. <<<<<<< gimp-transform-region.c gfloat *lanczos = NULL; /* Lanczos lookup table */ gdouble x_kernel[LANCZOS_WIDTH2]; /* 1-D kernels of Lanczos window coeffs */ ======= gfloat *lanczos; /* Lanczos lookup table */ gdouble x_kernel[LANCZOS_WIDTH2]; /* 1-D kernels of window coeffs */ >>>>>>> 1.124 suggests: 1-D kernels of Lanczos coeffs 1-D kernels of windowed sinc function coeffs 1-D kernels of coeffs again, the "window" here refers to the way Lanczos clips the infinite sinc function and is what is meant by lanczos in this context. Window is very misleading out of context here. The original comment was probably not explicit enough or else you probably would not have made this change. /* 1-D kernels of Lanczos coeffs */ would seem clearest. Request you commit that.
The comment was simply too long. Either you make it fit into 80 columns by shortening it or by breaking it up into 2 lines. So that's what I did. IMO you are overdoing it here. Feel free to change the comment with one of your next patches. If you followed the coding style, I wouldn't have to go over your patches and could commit them unchanged.
I seem to recall being told looking at the existing code _was_ coding style guide. I know I wont need to look far to find lines >80 chars. I'll bear that rule in mind in the future though. My final suggestion above should fit your requirements. Is there a written guide to gimp coding style? That may save you some editorial work if you have some rigid rules to apply. gg
Please don't tell me that you haven't read the file HACKING yet.