What is the best image downscaling algorithm (quality-wise)?

Question

I want to find out which algorithm is the best that can be used for downsizing a raster picture. With best I mean the one that gives the nicest-looking results. I know of bicubic, but is there something better yet? For example, I've heard from some people that Adobe Lightroom has some kind of proprietary algorithm which produces better results than standard bicubic that I was using. Unfortunately I would like to use this algorithm myself in my software, so Adobe's carefully guarded trade secrets won't do.

Added:

I checked out Paint.NET and to my surprise it seems that Super Sampling is better than bicubic when downsizing a picture. That makes me wonder if interpolation algorithms are the way to go at all.

It also reminded me of an algorithm I had "invented" myself, but never implemented. I suppose it also has a name (as something this trivial cannot be the idea of me alone), but I couldn't find it among the popular ones. Super Sampling was the closest one.

The idea is this - for every pixel in target picture, calculate where it would be in the source picture. It would probably overlay one or more other pixels. It would then be possible to calculate the areas and colors of these pixels. Then, to get the color of the target pixel, one would simply calculate the average of these colors, adding their areas as "weights". So, if a target pixel would cover 1/3 of a yellow source pixel, and 1/4 of a green source pixel, I'd get (1/3*yellow + 1/4*green)/(1/3+1/4).

This would naturally be computationally intensive, but it should be as close to the ideal as possible, no?

Is there a name for this algorithm?

Tympanist

You describe how supersampling exactly works. It is not better than bicubic, because bicubic takes more pixels from source image in account. – Chafer

I'm voting to reopen this very old question, since it's a good one. "Looks best" sounds subjective, but people who study this quantify it sufficiently to have good, non-subjective and consensus answers. – Arluene

@Arluene - Well, frankly, I think that the Lanczos option is already good enough for most purposes. – Tympanist

Answer 1

"The magic kernel" is likely the best image resizing algorithm, with superior results and performance when compared to Lanczos. It is used by both Facebook and Instagram.

More information is available at https://johncostella.com/magic/

Irremovable

The article is over my head, but I guess it really is better than Lanczos. Up you go! – Tympanist

Answer 2

Unfortunately, I cannot find a link to the original survey, but as Hollywood cinematographers moved from film to digital images, this question came up a lot, so someone (maybe SMPTE, maybe the ASC) gathered a bunch of professional cinematographers and showed them footage that had been rescaled using a bunch of different algorithms. The results were that for these pros looking at huge motion pictures, the consensus was that Mitchell (also known as a high-quality Catmull-Rom) is the best for scaling up and sinc is the best for scaling down. But sinc is a theoretical filter that goes off to infinity and thus cannot be completely implemented, so I don't know what they actually meant by 'sinc'. It probably refers to a truncated version of sinc. Lanczos is one of several practical variants of sinc that tries to improve on just truncating it and is probably the best default choice for scaling down still images. But as usual, it depends on the image and what you want: shrinking a line drawing to preserve lines is, for example, a case where you might prefer an emphasis on preserving edges that would be unwelcome when shrinking a photo of flowers.

There is a good example of the results of various algorithms at Cambridge in Color.

The folks at fxguide put together a lot of information on scaling algorithms (along with a lot of other stuff about compositing and other image processing) which is worth taking a look at. They also include test images that may be useful in doing your own tests.

Now ImageMagick has an extensive guide on resampling filters if you really want to get into it.

It is kind of ironic that there is more controversy about scaling down an image, which is theoretically something that can be done perfectly since you are only throwing away information, than there is about scaling up, where you are trying to add information that doesn't exist. But start with Lanczos.

Datha

I'd like to point out that the sinc filter is implementable without truncation on signals with finite extent. If we assume that outside of the region we know, all the samples are zero, the extra terms in the Whittaker–Shannon interpolation formula disappear and we get a finite sum. That is a valid interpretation of the original data, even though it is likely incorrect (the world isn't black outside of our field of view). This filter still couldn't be used on live audio and video because it isn't causal, but for use in images that doesn't matter. – Striated

I'm late to the party, but here's my take on this. There is only one proper way to scale an image down, and it's a combination of two methods. 1) scale down by x2, keep scaling down until the next scale down would be smaller than the target size. At each scaling every new pixel = average of 4 old pixels, so this is the maximum amount of information kept. 2) from that last scaled-down-by-2 step, scale down to the target size using BILINEAR interpolation. This is important as bilinear doesn't cause any ringing at all. 3) (a bonus) do the scaling in linear space (degamma->scale down->regamma). – Festoon

@Festoon there is no universally "proper" way to scale down an image because there is no universal definition of what is "important" in an image and should be preserved versus what is "unimportant" and can be discarded. Your algorithm might be great for some images, but it would turn a black and white line drawing into a light gray blur. – Datha

Well yeah, I was talking about photos, but I think it will handle line drawings better as well. For sure you know there will be no ringing. Like, zero. No filter can match this. But yeah, for certain images it's better to do nearest neighbor or something else that's more appropriate than a universal algorithm. – Festoon

@Alex: further more, you are not considering the filtering effects that an algorithm such as "sinc" has. Many pictures you take with a digital camera will have noise (fairly evenly distributed), especially when you take pictures at high iso. This can be filtered when downscaling an image. – Deca

Answer 3

There is Lanczos sampling which is slower than bicubic, but produces higher quality images.

Ming

Is there an implementation in .NET for this already? Would save me the time. :) – Tympanist

@Tympanist github.com/dlemstra/Magick.NET i have used it and it wroks perfectly fine for lanczos using (MagickImage image = new MagickImage(path)) { image.FilterType = ImageMagick.FilterType.Lanczos; image.Resize(145,145); // Save image as tiff image.Write("c:/workbackup/jay_Lanczos.png"); } – Sessler

Lanczos is by far the best for UPscaling. Every other filter looks blurry but Lanczos fills in detail in a very realistic way. PhotoFiltre 7 is free for personal use, is very easy to use and includes a Lanczos filter. – Ajmer

Answer 4

(Bi-)linear and (bi-)cubic resampling are not just ugly but horribly incorrect when downscaling by a factor smaller than 1/2. They will result in very bad aliasing akin to what you'd get if you downscampled by a factor of 1/2 then used nearest-neighbor downsampling.

Personally I would recommend (area-)averaging samples for most downsampling tasks. It's very simple and fast and near-optimal. Gaussian resampling (with radius chosen proportional to the reciprocal of the factor, e.g. radius 5 for downsampling by 1/5) may give better results with a bit more computational overhead, and it's more mathematically sound.

One possible reason to use gaussian resampling is that, unlike most other algorithms, it works correctly (does not introduce artifacts/aliasing) for both upsampling and downsampling, as long as you choose a radius appropriate to the resampling factor. Otherwise to support both directions you need two separate algorithms - area averaging for downsampling (which would degrade to nearest-neighbor for upsampling), and something like (bi-)cubic for upsampling (which would degrade to nearest-neighbor for downsampling). One way of seeing this nice property of gaussian resampling mathematically is that gaussian with very large radius approximates area-averaging, and gaussian with very small radius approximates (bi-)linear interpolation.

Fults

When I try to look up Gaussian resampling, all I find is stuff about Gaussian blur. As a person not versed in image processing algorithms, where might one find a Gaussian resampling implementation? – Importance

libswscale from ffmpeg/libav (originally from MPlayer) has one. The basic concept is simple though: your filter taps are just a gaussian function centered at the point you want to produce an output sample for. – Fults

The radius is all important. The reason bicubic fails so often in downscaling is that the radius isn't adjusted and the same radius that works for upsizing is used for downsizing. This simply doesn't work, and in the extreme devolves to worse than nearest neighbor. If the radius is adjusted properly it should deliver better results than area averaging. – Accounting

@MarkRansom: Radius is irrelevant. A cubic filter only uses 4 input sample points (and fundamentally cannot use more or it would not be cubic). If the input it's covering had more than 4 samples, bam, you've got aliasing, and there's nothing you can do about it. – Fults

There's absolutely nothing inherent to a cubic filter that restricts it to 4 samples, the formula works just fine if you widen it and divide by the sum of the weights. In fact Catmull-Rom is similar to Lanczos-2 and can be adjusted to be almost identical. – Accounting

@MarkRansom: The definition of a cubic filter is an approximation of the curve by a cubic polynomial defined uniquely by any 4 points on the curve. – Fults

That may be so, but the math doesn't care. Try it sometime and see. – Accounting

@MarkRansom: What you're talking about is potentially valid solution to the problem, but you're using the wrong name for it -- it's not "cubic". The reason I say potentially valid is that any linear filter with negative coefficients inherently introduces ringing-type artifacts. While others may find lack of perceived (even if fake) "sharpness" more offensive than ringing, I don't; my subjective position is that any good scaling filter should have all non-negative coefficients, followed by a nonlinear sharpening step if needed. – Fults

Wikipedia uses a much more general definition of "cubic" which definitely applies in this case. If you like filters with no ringing you should check out B-Spline, which can be performed with the same cubic filter: cs.utexas.edu/~fussell/courses/cs384g/lectures/mitchell/… – Accounting

@MarkRansom: Not sure what you mean by the wp citation. Can you explain what particular section/paragraph you wanted me to look at? That article is on cubic functions, whereas the topic at hand is "[bi]cubic scaling/filtering". – Fults

@R.. just pointing out that the term "cubic" has another definition so my usage isn't incorrect. And I'll reiterate my suggestion to check out the cubic B-Spline, it's very similar to the Gaussian 0.6737 * exp(-x**2 / 0.7161) – Accounting

Having investigated best looking downscaling methods I also found area method to produce the best results. The one situation where the result is not satisfying is when downscaling an image by a small factor. In that particular case area method generally blurs the image, but nearest neighbor can preform surprisingly well. The funny thing about using gaussian downscaling is that it's more or less equivalent of first blurring the image and then downscaling it using nearest neighbor. – Mudd

@jahu: Unless the source image is seriously band-limited (roughly speaking, blurred) to begin with, nearest-neighbor is guaranteed to give very bad aliasing, even for very "small" (just below 1.0) factors. For these cases, area-averaging, if implemented correctly (using weights based on the coverage of a source pixel) will only yield noticeable blurring at points where you're roughly halfway between source pixels. At least one of blurring, ringing, or aliasing is inevitable with linear-transformation-based scaling. To do better you need highly nonlinear warp-based algorithms. – Fults

@R.. What I meant is, that when you reduce the size of an image by a just a few pixels in both dimension, it becomes relatively blurred. To be honest this is only a problem if the image was small to begin with. The results of nearest neighbor can be ok in those cases, but will depend on the contents of the image. If the image was blurred from the start it will look like the result of area or gaussian downscaling anyway. – Mudd

Something can go wrong when applying Gaussian blur to color images because RGB values are the square-root of the actual brightness intensities. Hence if one naively/linearly blurs RGB colors, the mixed colors will not correspond to what our eyes natively perceive as a mixed color. A solution is to apply the blur like this: sqrt(gauss(image^2)). – Cabrales

Answer 5

I saw an article on Slashdot about Seam Carving a while ago, it might be worth looking into.

Seam carving is an image resizing algorithm developed by Shai Avidan and Ariel Shamir. This algorithm alters the dimensions of an image not by scaling or cropping, but rather by intelligently removing pixels from (or adding pixels to) the image that carry little importance.

Exhilarate

I've seen this. Wasn't exactly what I had in mind, but it's certainly a good idea to look into! Thanks! Is this algorithm publicly available somewhere? – Tympanist

Actually, seam carving is retargeting, not scaling. They produce different results. @Vilx: yes, there's a GIMP plugin here: liquidrescale.wikidot.com – Deceit

Here's a dotNET implementation: blogs.msdn.com/mswanson/archive/2007/10/23/… – Exhilarate

Note that the seam carving retargetting algorithm made its way into Photoshop 4, I wouldn't be surprised if there are heavy patent burdens on this algorithm. – Supereminent

Seamcarving is the same idea as the Gimp's liquid rescaling and Photoshop CS4's Content aware scaling. It is not for scaling, it is for changing the aspect ratio of an image without making it appear stretched. – Offal

Answer 6

The algorithm you describe is called linear interpolation, and is one of the fastest algorithms, but isn't the best on images.

Dine

Except OP is taking into account the spatial location of subpixels the way subpixel font rendering does. This could be a really cool way to gain a little resolution, but could also result in odd image effects, and is also dependent on a given sub-pixel architecture. – Creolized

No, linear interpolation is kind of convolution algorithms. Described in true supersampling. – Chafer

@AdamTolley I severely doubt subpixel AA for normal images would look even acceptable. It works with text because there are only two colors and even there having any other color than white is a problem – Buckjumper

@itzJanuary i think it would be just fine when the boundary colors matched the subpixel scheme, but that would only happen sometimes, resulting at best inconsistent usefulness and at worst disruption of the fundamental frequency of pixel sampling creating odd perceptual artifacts – Creolized

Answer 7

Is there a name for this algorithm?

It might be referred as "box" or "window" resampling in literature. It is actually less computational expensive as you think.

It can also be used to create a intermediate bitmap that is subsequently used by bi-cubic interpolation to avoid aliasing when downsampled by more than 1/2.

Deidradeidre

Answer 8

If anyone's interested, here is my C++ implementation of area averaging scaling algorithm:

void area_averaging_image_scale(uint32_t *dst, int dst_width, int dst_height, const uint32_t *src, int src_width, int src_height)
{
    // 1. Scale horizontally (src -> mid)
    int mid_width  = dst_width,
        mid_height = src_height;
    float src_width_div_by_mid_width = float(src_width) / mid_width;
    float mid_width_div_by_src_width = 1.f / src_width_div_by_mid_width;
    std::vector<uint32_t> mid(mid_width * mid_height);
    for (int y=0; y<mid_height; y++)
        for (int x=0; x<mid_width; x++)
            for (int c=0; c<4; c++) {
                float f = x * src_width_div_by_mid_width;
                int i = int(f);
                float d = ((uint8_t*)&src[i + y*src_width])[c] * (float(i) + 1 - f);
                float end = f + src_width_div_by_mid_width;
                int endi = int(end);
                if (end - float(endi) > 1e-4f) {
                    assert(endi < src_width);
                    d += ((uint8_t*)&src[endi + y*src_width])[c] * (end - float(endi));
                }
                for (i++; i < endi; i++)
                    d += ((uint8_t*)&src[i + y*src_width])[c];
                int r = int(d * mid_width_div_by_src_width + 0.5f);
                assert(r <= 255);
                ((uint8_t*)&mid[x + y*mid_width])[c] = r;
            }

    // 2. Scale vertically (mid -> dst)
    float mid_height_div_by_dst_height = float(mid_height) / dst_height;
    float dst_height_div_by_mid_height = 1.f / mid_height_div_by_dst_height;
    for (int y=0; y<dst_height; y++)
        for (int x=0; x<dst_width; x++)
            for (int c=0; c<4; c++) {
                float f = y * mid_height_div_by_dst_height;
                int i = int(f);
                float d = ((uint8_t*)&mid[x + i*mid_width])[c] * (float(i) + 1 - f);
                float end = f + mid_height_div_by_dst_height;
                int endi = int(end);
                if (end - float(endi) > 1e-4f) {
                    assert(endi < mid_height);
                    d += ((uint8_t*)&mid[x + endi*mid_width])[c] * (end - float(endi));
                }
                for (i++; i < endi; i++)
                    d += ((uint8_t*)&mid[x + i*mid_width])[c];
                int r = int(d * dst_height_div_by_mid_height + 0.5f);
                assert(r <= 255);
                ((uint8_t*)&dst[x + y*dst_width])[c] = r;
            }
}

Antonantone

Please add some explanation to your answer such that others can learn from it – Superannuation

Nice with code, so we can try it. But I'm missing clarification on the choice of uint32_t. Is this becuse 4 color channels, each of 8 bits, have been packed together? In such case this would not work with all image types, such as greyscale and RGB.. I would also like to see you correct the answer by adding in some documentation. Proper explanation is always better than brevity, imo. – Tellus

Answer 9

There isn't any one best algorithm for downscaling. It depends a lot on the image content and even what you're doing with the image. For example, if you're doing image processing involving gradients, it often works best to fit it to a differentiable spline (e.g. B-splines) and take the derivatives of those. If the spatial frequency of the image is relatively low, almost anything will work reasonably well (the area-proportional approach you're describing is popular; it's called INTER_AREA in OpenCV though it's really more of an antialiaser than an interpolator), but it gets complicated with high frequency content (sharp edges, high contrast). In those cases, you usually have to do some kind of antialiasing, either built into the resampler or as a separate step.

The one rule that really holds in almost every case is that nearest neighbor has the worst quality, followed by bilinear. If you can possibly afford the processing time to do something better than bilinear, don't use bilinear. The only merits of bilinear are that it's really fast, easy to code, and often supported in GPU hardware.

There are a multitude of higher-order resampling schemes. I've seen dozens in the literature and I'd say about 10 of them are worth looking at depending on what you're doing. IMO, the best approach is to take a set of typical images for what you're doing, run them through a list of the usual suspects (Keys convolutional bicubic, Catmull-Rom, Lanczos2/4, Lanczos3/6, O-MOMS, B-spline...) and see what usually works best for your application. Chances are, once you go up to a 4x4 resampler, there won't be a single really consistent winner unless your images are all very similar. Sometimes you'll see some consistent improvement with a 6x6 like Lanczos3, but most of the time, the step up from the 2x2 bilinear to any 4x4 is the big win. This is, of course, why most image processing software supports different choices. If one thing worked best all the time, everybody'd be using it.

Vivianviviana