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 propieritary 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 garded 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?

Answer 1

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

Answer 2

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.

Answer 3

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

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.