What is the name of this algorithm, and how does it compare to other image resampling algorithms?

Question

This algorithm has been in my mind for a long time, but I cannot find it described anywhere. It's so simple though that I can't be the only one who has thought of it. Here's how it works:

You start with an image. Say, 7x7px:

You need to resample it say, to 5x5px:

So all you do is take the average color of each new square:

This isn't the nearest-neighbor, because that takes the color of just one pixel, not fractional pixels who happen to overlay the source pixel. It's also not bilinear, bicubic, lanczos or anything else interpolating.

So - what is it? It intuitively seems to me that this should be the "mathematically perfect" resampling algorithm, although since I don't have a definition of what "mathematically perfect" is, I cannot prove or disprove that.

Last but not least, "mathematically perfect" isn't always "best looking", so I wonder how it compares to other mainstream image resampling algorithms (bicubic, lanczos) in terms of "quality"? This is a subjective term, of course, so I'm really interested if there are significant differences between this algorithm and others, which most people would agree upon.

P.S. A few things I can already tell about it - it won't be "best looking" for pixel art, as demonstrated here; there are special algorithms for that (2xSAI etc); and also it won't be best for enlarging pictures - interpolation would win out there. But for shrinking pictures...?

Update 1: Hmm, just found out about supersampling. This seems like a variant of it, with a grid-type arrangement of samples, where the number of samples is optimized for the resolution of the source & target images.

Answer 1

I will start out by saying I don’t know an official name for your algorithm. I know that Paint Shop Pro called it “Bilinear” early on, but were forced to rename it to “Weighted Average” in version 8 when it was pointed out that the algorithm didn’t match the classic definition of Bilinear.

Most resizing algorithms can be applied in two independent passes, one in the X direction and one in the Y. This is not only more efficient, but it makes it a lot easier to describe and reason about the different algorithms. From this point forward I’m going to work in one dimension and assume you can extrapolate to 2D.

Your input consists of 7 pixels which we will give coordinates of 0, 1, 2, 3, 4, 5, 6. It’s useful to realize that a pixel is not a little square in this context, but is just a single point. To create the output you will want the interpolated values from the points 0.2, 1.6, 3.0, 4.4, 5.8. Why not 0.0, 1.5, 3.0, 4.5, 6.0? Suppose you doubled the size of the input and output to 14x14 and 10x10: the coordinates would now be 0.0, 1.44, 2.89, 4.33, 5.78, 7.22, 8.67, 10.11, 11.56, 13.0. Starting with the second pixel the results would be different, and that’s unacceptable. All the points should be 7/5 apart, giving the coordinates 0.2, 1.6, 3.0, 4.4, 5.8, 7.2, 8.6, 10.0, 11.4, 12.8.

Let’s compare the common resizing algorithms when expressed as a filter, and see how they compare to yours.

This first example in the generic form is called a Box or Averaging filter. But a magical thing happens when the width of the box filter is exactly 1.0: one pixel from the input is going to fall within the box and be given a weight of 1.0, and all the other pixels in the input will be given the weight 0.0. This makes it the equivalent of the Nearest Neighbor algorithm.

Our second example is generically called the Tent filter. Again it becomes something special when the width is exactly 2.0, it becomes a Linear interpolation; applied in 2D it’s called Bilinear.

The third example is a Cubic filter, which when applied in 2D is called Bicubic. There are different variations of this formula, this example uses the one suggested by Mitchell and Netravali.

While the Gaussian filter isn’t often used in resizing applications, I added it here for comparison.

Finally we reach your algorithm. It’s a combination of averaging and bilinear, a tent with a flat top.