Fastest Algorithm to scale down 32Bit RGB IMAGE.

Question

which algorithm to use to scale down 32Bit RGB IMAGE to custom resolution? Algorithm should average pixels.

for example If I have 100x100 image and I want new Image of size 20x50. Avg of first five pixels of first source row will give first pixel of dest, And avg of first two pixels of first source column will give first dest column pixel.

Currently what I do is first scale down in X resolution, and after that I scale down in Y resolution. I need one temp buffer in this method.

Is there any optimized method that you know?

Answer 1

If you're looking for a wordy explanation, I've found this article to be helpful. If on the other hand you deal more in mathematical formulae, there is a method of fast image downscaling explained here.

Answer 2

You forget to mention the most important aspect of the question: how much you care about quality. If you dont care exactly how the values of the sources pixels are smashed together to create the destination pixel the fastest is (at least in almost all cases) the one that produces the worst quality.

If youre tempted to respond with "the fastest algorithm that still yields very good quality" you have essentially covered the entire algorithm field that deals with just imagesampling/resizing.

And you already outlined your initial idea of the algorithm:

Avg of first five pixels of first source row will give first pixel of dest,

Calculating the average value for each channel on the source pixels could be seen as trivial, are you looking for example code that does that?

Or are you looking for someone to challenge your initial draft of the algorithm with something even faster?

Answer 3

What you're doing is the optimized method. The only faster one is called nearest neighbor, where you simply grab the middle pixel of the range without trying to average any of them. The quality is significantly worse if there is any detail in the original image, although it might be acceptable if the original is simple.

Answer 4

This averages the appropriate pixels.

 w_ratio = src.w / dest.w
 h_ratio = src.h / dest.h

 dest[x,y] = 
    AVG( src[x * w_ratio + xi, y * h_ratio + yi] ) 
      where
           xi in range (0, w_ratio - 1), inc by 1
           yi in range (0, h_ratio - 1), inc by 1

For boundary conditions do a separate loop (no if's in loop).

Here's a more C like code:

src and dest are bitmaps that:
* property src[x,y] for pixel
* property src.w for width
* property src.h for height

pixel has been defined so that

adding

p1 = p1 + p2   
is same as
p1.r = p1.r + p2.r
p1.g = p1.g + p2.g
...

division

p1 = p1 / c
p1.r = p1.r / c
p1.g = p1.g / c

evaluation with a constant 0

p1 = 0
p1.r = 0
p1.g = 0
...

for simplicity sake I won't consider the problem when pixel component integer overflows...

float w_ratio = src.w / dest.w;
float h_ratio = src.h / dest.h;
int w_ratio_i = floor(w_ratio);
int h_ratio_i = floor(h_ratio);

wxh = w_ratio*h_ratio;

for (y = 0; y < dest.w; y++)
for (x = 0; x < dest.h; x++){
 pixel temp = 0;  

 int srcx, srcy;
 // we have to use here the floating point value w_ratio, h_ratio
 // otherwise towards the end it can get a little wrong
 // this multiplication can be optimized similarly to Bresenham's line
 srcx = floor(x * w_ratio);
 srcy = floor(y * h_ratio);

 // here we use floored value otherwise it might overflow src bitmap
 for(yi = 0; yi < h_ratio_i; yi++)
 for(xi = 0; xi < w_ratio_i; xi++)
   temp += src[srcx + xi, srcy + yi];
 dest[x,y] = temp / wxh;
}

Bresenham's line optimization

Answer 5

The term you are looking for is "Resampling." In your case you want image resampling. You seem to already be doing linear interpolation, which should be the fastest. Here are ~6 base algorithms. If you really want to delve into the subject look into "resampling kernels."

• Lanczos resampling
• Bicubic interpolation
• Bilinear interpolation
• Nearest-neighbor interpolation
• Spline interpolation
• Linear interpolation

Answer 6

After you do the standard C optimizations (pointer arithmetic, fixed point math, etc...) There are also some more clever optimizations to be had. A (very) long time ago, I saw an scaler implementation that scaled the X direction first. In the process of writing out the horizontally scaled image, it rotated the image 90degrees in memory. This was so that when it came time to do the reads for the Y direction scale, the data in memory would be better cache aligned.

This technique depends heavily on the processor that it will run on.

Answer 7

It really is a speed/quality trade-off.

First of all, you're correct that doing one dimension then the other is slower than it has to be. Way too many memory reads and writes.

Your big choice is whether to support fractional pixels or not. Your example is 100x100 to 20x50. So 10 pixels map to 1. What if you're going from 100x100 to 21x49? Are you willing to operate at source pixel boundaries, or do you want to pull fractional pixels in? What would you do for 100x100 to 99x99?

You have to tell us what you're willing to accept before we can say what's fastest.

And also tell us the possible extremes of the shrinkage. How many orders of magnitude might the difference between the source and destination be? At some point, sampling representative pixels inside the source are won't be much worse than averaging all the pixels. But you'll have to be careful in choosing representative pixels or you'll get aliasing with many common patterns.