GNOME Bugzilla – Bug 464222
Lanczos3 Downsample Bug
Last modified: 2008-10-30 19:57:12 UTC
Please describe the problem: It appears that GIMP's Lanczos3 resampling algorithm does not incorporate any lowpass filtering, and, as a result, aliasing occurs in the downsampled image. The solution to this problem is fairly simple. Assuming that Lanczos3 resampling is applied using convolution, there are two options: 1) Perform resampling as you normally would, but first scale the Lanczos3 kernel width-wise by a factor inversely related to the scaling factor. For example, if scaling an image to 25%, the kernel should be scaled 4X width-wise. It is important to remember, though, that the entire width of the kernel must be used for convolution. In other words, when scaling to 25%, we have to consider 4x as many pixels as we normally would. Also, in addition to scaling the kernel width-wise, you must also scale the kernel height-wise by a factor directly proportional to the scaling factor (i.e. in the above example, we would scale the kernel height-wise by a factor of 0.25). 2. Do the resampling exactly as you have been doing, but first apply a lowpass filter to the image before resampling. Construct the scaled kernel exactly as described in the 1st option stated above. Apply this kernel to the source image with out changing the dimensions of the image. This can be done in the same manner as you would apply a Gaussian filter. If you have any questions, please ask. Steps to reproduce: 1. Downsize an image containing a lot of high-frequency detail using Lanczos3. You will notice aliasing artifacts (i.e false frequencies and superficially sharp details) Actual results: You get an image with aliasing artifacts. Everything proceeds smoothly from there. Expected results: I expect to get an image free from aliasing artifacts. Does this happen every time? Yes. Other information:
Yes, this is a known problem and it has been reported before (bug #448087 and bug #166130 for a more general discussion of the problem). However there is no one working on it currently and the people who have implemented the Lanczos filtering in the first place don't seem to be willing or able to fix it. We would appreciate some help.
*** Bug 448087 has been marked as a duplicate of this bug. ***
(In reply to comment #1) > Yes, this is a known problem and it has been reported before (bug #448087 and > bug #166130 for a more general discussion of the problem). However there is no > one working on it currently and the people who have implemented the Lanczos > filtering in the first place don't seem to be willing or able to fix it. We > would appreciate some help. > The easiest solution to this problem is probably the second option I listed in my first post because it does not involve modifying any of the Lanczos3 code that has already been written. All that is required to fix this problem is to lowpass filter the source image before we send it off to be downsampled. This is exactly like applying a Gaussian filter to the source image before downsampling it except that we use a Lanczos filter instead of a Gaussian filter. Here is some pseudo code to illustrate how to lowpass filter the source image using a Lanczos3 filter. The filter is applied in two passes, once along the x-axis and once along the y-axis: //if we are scaling an image down to 25%, 'scalingFactor' would be 0.25 void lowpassFilter(Image img_src, Image img_dest, float scalingFactor) { //first, determine the size (width) of the filter int windowWidth = 6 * (int) (1.0/scalingFactor + 0.5) + 1; float* filter = new float[windowWidth]; float xf; int index = 0; //now, calculate the values in the filter for(float x = -windowWidth / 2; x <= windowWidth / 2; x++) { xf *= scalingFactor; if (xf == 0) filter[index++] = scalingFactor; else filter[index++] = 3*scalingFactor*sin(PI*xf)*sin(PI*xf/3.0)/(PI*PI*xf*xf); } //make sure all the weights in 'filter' sum to 1 float sum = 0; for(int i=0; i<windowWidth; i++) sum += filter[i]; for(int i=0; i<windowWidth; i++) filter[i] /= sum; (1)//now, for every pixel 'p' in 'img_src' we consider the horizontal //neighborhood of pixels of size 'windowWidth' with 'p' located at the center (2)//convolve 'filter' with the just mentioned neighborhood of pixels (3)//the value of the pixel in 'img_dest' corresponding to the location of 'p' //in 'img_src' is simply the result of the above convolution (4)//after every pixel has been filled in 'img_dest' we copy all of 'img_dest' //back into 'img_src' (5)//repeat (1), (2), and (3) except that we consider vertical neighborhoods, //not horizontal neighborhoods //we're done! delete[] filter; } I hope the above code is of some use. If you would like, I can write a fully functional C++ lowpassFilter function (just like the one above) using generic getPxl() and setPxl() functions. I know that GIMP uses tiles, but this may still be of use to you. Let me know if you are interested. Lastly, you may already know this (as you may already know much of what I have said previously), but I thought I would mention it anyway. The following formula shows how to construct a Lanczos3 filter: sinc(x) = sin(PI*x)/(PI*x) Lanczos3(x) = sinc(x)*sinc(x/3) ( defined on the interval [-3,3] ) ( also be careful to note that Lanczos3(0) = 1 ) For a lowpass Lanczos3 filter, we have: (scalingFactor is the same as defined previously) Lanczos3lowpass(x, scalingFactor) = scalingFactor*Lanczos3(x*scalingFactor) (defined on the interval [-3/scalingFactor, 3/scalingFactor] ) (also be careful to note that Lanczos3lowpass(0, scalingFactor) = scalingFactor)
It seems to me that maybe steps 1-3 could be combined, giving a considerable performance improvement. Running a gaussian blur on a large image can be very time-consuming - certainly a matter of minutes. And it might be less work to do that refactoring from the start than trying to deal with performance afterwards.
(In reply to comment #4) > It seems to me that maybe steps 1-3 could be combined, giving a considerable > performance improvement. Running a gaussian blur on a large image can be very > time-consuming - certainly a matter of minutes. And it might be less work to > do that refactoring from the start than trying to deal with performance > afterwards. > As far as I know, a Lanczos3 lowpass filter cannot be applied to an image any faster than you can a Gaussian blur of similar size. Assuming we're working in the spatial domain, the only way I know of to accomplish the task is through convolution (there may be a recursive solution, but that's a bit beyond me at the moment). The fastest way I know to apply such convolution is by using a two-pass scheme like the one mentioned here: http://en.wikipedia.org/wiki/Gaussian_blur Applying a Gaussian blur using convolution and applying a Lanczos3 lowpass filter using convolution amount to exactly the same thing, except that we use different filter weights (my last post describes how to calculate the Lanczos3 lowpass filter weights). If you know of a fast way to implement a Gaussian blur using convolution, you can likely use the same code with only slight modification to implement the Lanczos3 lowpass filter. I apologize if I'm missing something here, but I don't see any other way around this downscaling problem if you don't want to change the existing Lanczos3 code. You simply have to apply a Lanczos3 lowpass filter to the source image before downscaling it with the existing Lanczos3 code. How you implement the Lanczos3 lowpass filter is up to you.
The other option we have is not to use Lanczos3 at all when scaling down. This is what we do for the other interpolation options as well. This also used to be the case for Lanczos, but it was changed because the implementation was buggy (see bug #443640).
In order to do any type of downsampling correctly, a lowpass filter must be incorporated one way or another. On closer inspection, I see that none of GIMP's interpolation methods do this. Aliasing is present regardless of the method chosen. The presence of a lowpass filter makes a significant difference in the overall quality of the final image, although much more so where fine, higher frequency details are present. I guess I just don't see any reason not to implement the lowpass filter for Lanczos3. It is no harder to implement than a Gaussian blur, and it will make quite a difference in terms of quality. If you are worried about the extra computing time it will take, perhaps you could give the user an option that let's them decide if they want to use the lowpass filter or not.
Well, what I suggested is not to use Lanczos at all for downsampling. We also don't do Cubic interpolation even if the user selected that. So while not correct, this would at least be consistent with the current behavior. We should however first improve the quality of the downscaling algorithm as is discussed in bug #464466. Of course in the long term it would be nice to implement proper downscaling variants of the various interpolation options that are offered in the UI.
I hope I already worked in that direction : http://bugzilla.gnome.org/show_bug.cgi?id=464466#c20 Current implementation : Scaling up : NONE => nearest point (copy pixel) LINEAR => bilinear interpolation CUBIC => bicubic interpolation LANCZOS => lanczos3 interpolation Scaling down : NONE => nearest point LINEAR => reduce by 2 average (similar to current gimp) + final cubic step CUBIC => reduce by 2 average (with gausian low-pass pre filter) LANCZOS => reduce by 2 average (with lanczos2 low-pass pre filter)
*** Bug 495515 has been marked as a duplicate of this bug. ***
As far as I know this is still not entirely fixed in 2.4. Changing the version field accordingly...
Let's close this as a duplicate of bug #464466. The patch attached there (which has been committed to trunk) deals with this problem. *** This bug has been marked as a duplicate of 464466 ***