Image downscaling algorithm

Question

Could you help me find the right algorithm for image resizing? I have an image of a number. The maximum size is 200x200, I need to get an image with size 15x15 or even less. The image is monochrome (black and white) and the result should be the same. That's the info about my task.

I've already tried one algorithm, here it is

// xscale, yscale - decrease/increase rate
for (int f = 0; f<=49; f++)
            {
                    for (int g = 0; g<=49; g++)//49+1 - final size
                    {
                            xpos = (int)f * xscale;
                            ypos = (int)g * yscale;
                            picture3[f][g]=picture4[xpos][ypos];
                    }
            }

But it won't work with the decrease of an image, which is my prior target. Could you help me find an algorithm, which could solve that problem (quality mustn't be perfect, the speed doesn't even matter). Some information about it would be perfect too considering the fact I'm a newbie. Of course, a short piece of c/c++ code (or a library) will be perfect too.

Edit: I've found an algorithm. Will it be suitable for compressing from 200 to 20?

Answer 1

The general approach is to filter the input to generate a smaller size, and threshold to convert to monochrome. The easiest filter to implement is a simple average, and it often produces OK results. The Sinc filter is theoretically the best but it's impractical to implement and has ringing artifacts which are often undesirable. Many other filters are available, such as Lanczos or Tent (which is the generalized form of Bilinear).

Here's a version of an average filter combined with thresholding. Assuming picture4 is the input with pixel values of 0 or 1, and the output is picture3 in the same format. I also assumed that x is the least significant dimension which is opposite to the usual mathematical notation, and opposite to the coordinates in your question.

int thumbwidth = 15;
int thumbheight = 15;
double xscale = (thumbwidth+0.0) / width;
double yscale = (thumbheight+0.0) / height;
double threshold = 0.5 / (xscale * yscale);
double yend = 0.0;
for (int f = 0; f < thumbheight; f++) // y on output
{
    double ystart = yend;
    yend = (f + 1) / yscale;
    if (yend >= height) yend = height - 0.000001;
    double xend = 0.0;
    for (int g = 0; g < thumbwidth; g++) // x on output
    {
        double xstart = xend;
        xend = (g + 1) / xscale;
        if (xend >= width) xend = width - 0.000001;
        double sum = 0.0;
        for (int y = (int)ystart; y <= (int)yend; ++y)
        {
            double yportion = 1.0;
            if (y == (int)ystart) yportion -= ystart - y;
            if (y == (int)yend) yportion -= y+1 - yend;
            for (int x = (int)xstart; x <= (int)xend; ++x)
            {
                double xportion = 1.0;
                if (x == (int)xstart) xportion -= xstart - x;
                if (x == (int)xend) xportion -= x+1 - xend;
                sum += picture4[y][x] * yportion * xportion;
            }
        }
        picture3[f][g] = (sum > threshold) ? 1 : 0;
    }
}

I've now tested this code. Here's the input 200x200 image, followed by a nearest-neighbor reduction to 15x15 (done in Paint Shop Pro), followed by the results of this code. I'll leave you to decide which is more faithful to the original; the difference would be much more obvious if the original had some fine detail.

Answer 2

I've found an implementation of a bilinear interpolaton. C code.

Assuming that:

a - a primary array (which we need to stretch/compress) pointer.

oldw - primary width

oldh - primary height

b - a secondary array (which we get after compressing/stretching) pointer

neww - secondary width

newh - seconday height

---

#include <stdio.h>
#include <math.h>
#include <sys/types.h>

void resample(void *a, void *b, int oldw, int oldh, int neww,  int newh)
{
int i;
int j;
int l;
int c;
float t;
float u;
float tmp;
float d1, d2, d3, d4;
u_int p1, p2, p3, p4; /* nearby pixels */
u_char red, green, blue;

for (i = 0; i < newh; i++) {
    for (j = 0; j < neww; j++) {

        tmp = (float) (i) / (float) (newh - 1) * (oldh - 1);
        l = (int) floor(tmp);
        if (l < 0) {
            l = 0;
        } else {
            if (l >= oldh - 1) {
                l = oldh - 2;
            }
        }

        u = tmp - l;
        tmp = (float) (j) / (float) (neww - 1) * (oldw - 1);
        c = (int) floor(tmp);
        if (c < 0) {
            c = 0;
        } else {
            if (c >= oldw - 1) {
                c = oldw - 2;
            }
        }
        t = tmp - c;

        /* coefficients */
        d1 = (1 - t) * (1 - u);
        d2 = t * (1 - u);
        d3 = t * u;
        d4 = (1 - t) * u;

        /* nearby pixels: a[i][j] */
        p1 = *((u_int*)a + (l * oldw) + c);
        p2 = *((u_int*)a + (l * oldw) + c + 1);
        p3 = *((u_int*)a + ((l + 1)* oldw) + c + 1);
        p4 = *((u_int*)a + ((l + 1)* oldw) + c);

        /* color components */
        blue = (u_char)p1 * d1 + (u_char)p2 * d2 + (u_char)p3 * d3 + (u_char)p4 * d4;
        green = (u_char)(p1 >> 8) * d1 + (u_char)(p2 >> 8) * d2 + (u_char)(p3 >> 8) * d3 + (u_char)(p4 >> 8) * d4;
        red = (u_char)(p1 >> 16) * d1 + (u_char)(p2 >> 16) * d2 + (u_char)(p3 >> 16) * d3 + (u_char)(p4 >> 16) * d4;

        /* new pixel R G B  */
        *((u_int*)b + (i * neww) + j) = (red << 16) | (green << 8) | (blue);       
    }
}
}

Hope it will be useful for other users. But nevertheless I still doubth whether it will work in my situation (when not stratching, but compressing an array). Any ideas?

Answer 3

Since you're fine with using a library, you could look into the imagemagick C++ bindings.

You could also output the image in a simple format like a pbm, and then call the imagemagick command to resize it:

system("convert input.pbm -resize 10x10 -compress none output.pbm");

Sample output file (note: you don't need to use a new line for each row):

P1
20 20
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 0 0 0 0 0
0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 1 1 0 0 0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

The output file:

P1
10 10
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 1 0 1 1 0 
0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 1 1 0 1 1 0 0 0 0 0 0 1 1 1 1 
1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 

Answer 4

If you use Win32, then StretchBlt function possibly help.

The StretchBlt function copies a bitmap from a source rectangle into a destination rectangle, stretching or compressing the bitmap to fit the dimensions of the destination rectangle, if necessary. The system stretches or compresses the bitmap according to the stretching mode currently set in the destination device context.

Answer 5

To properly downscale an image, you should divide your image up into square blocks of pixels and then use something like Bilinear Interpolation in order to find the right color of the pixel that should replace the NxN block of pixels you're doing the interpolation on.

Since I'm not so good at the math involved, I'm not going to try give you an example of how the code would like. Sorry :(

Answer 6

I think, you need Interpolation. There are a lot of algorithms, for example you can use Bilinear interpolation

Answer 7

One approach to downsizing a 200x200 image to, say 100x100, would be to take every 2nd pixel along each row and column. I'll leave you to roll your own code for downsizing to a size which is not a divisor of the original size. And I provide no warranty as to the suitability of this approach for your problem.