0

I'm trying to downscale an image from a large size (as large as 960x960) to possibly as small as 32x32. I have the following code I use to get the raw pixels:

    Image* img = new Image();
    img->initWithImageFile(fileNameWithPath);
    int x=3;
    if(img->hasAlpha()){
        x=4;
    }

    unsigned char *data = new unsigned char[img->getDataLen()*x];
    data = img->getData();
    // [0][0] => Left-Top Pixel !
    // But cocos2d Location Y-axis is Bottom(0) to Top(max)

    //This is for changing pixels in the original image
    //Skip this loop if there are no changes to be made (converting to grayscale etc).
    for(int i=0;i<img->getWidth();i++)
    {
        for(int j=0;j<img->getHeight();j++)
        {
            unsigned char *pixel = data + (i + j * img->getWidth()) * x;

            // You can see/change pixels' RGBA value(0-255) here !
            unsigned char r = *pixel;
            unsigned char g = *(pixel + 1);
            unsigned char b = *(pixel + 2) ;
            unsigned char a = *(pixel + 3);

            //pixel[2] = 255; //Example: Setting the blue component to 255
        }
    }

I can create an output image by doing:

        int width = scale*img->getWidth();
        int height = scale*img->getHeight();
        Image* scaledImage = new Image();
        auto dataLen = width * height * x * sizeof(unsigned char);
        auto data2 = static_cast<unsigned char*>(malloc(dataLen));
        scaledImage->initWithRawData(data2, dataLen, width, height, 8);

And I can set the individual pixels of the output image by doing:

            unsigned char *pixel2 = data2 + (i + j * width) * x;

The question is how to average / interpolate the pixels from the original image efficiently (using minimum cpu and memory, with the preference to use more cpu if necessary and less memory).

Challenges:

  1. The downscaled image and the original image may not be perfect multiples.
  2. The downscaled image can be as small as 0.1 of the original image size.
  3. most images will be downscaled to 0.4 to 0.1 of the original image, so these are the most important ranges.

EDIT: If you think some other interpolation algorithm would be better suited (instead of bilinear) then I am open to it. The challenge is writing an efficient algorithm to average / interpolate the individual pixels..

How do I interpolate the individual pixels of the original image ?

Rahul Iyer
  • 19,924
  • 21
  • 96
  • 190

1 Answers1

2

Memory isn't an issue, you need an input buffer with the original image and an output buffer with the rescaled image, you don't need any more.

Bilinear interpolation isn't very suitable for downsampling by a large factor as it doesn't really differ from nearest sampling. You only interpolate four neighbouring pixels and so are vulnerable to aliasing effects, particularly on computer-generated images.

This function uses the averaging method.

 /*
  resize an image using the averaging method.
  Note that dwidth and dheight must be smaller than or equal to swidth, sheight.

 */
void sprshrink(unsigned char *dest, int dwidth, int dheight, unsigned char *src, int swidth, int sheight)
{
  int x, y;
  int i, ii;
  float red, green, blue, alpha;
  float xfrag, yfrag, xfrag2, yfrag2;
  float xt, yt, dx, dy;
  int xi, yi;


  dx = ((float)swidth)/dwidth;
  dy = ((float)sheight)/dheight;

  for(yt= 0, y=0;y<dheight;y++, yt += dy)
  {
    yfrag = ceil(yt) - yt;
    if(yfrag == 0)
      yfrag = 1;
    yfrag2 = yt+dy - (float) floor(yt + dy);
    if(yfrag2 == 0 && dy != 1.0f)
      yfrag2 = 1;

    for(xt = 0, x=0;x<dwidth;x++, xt+= dx)
    {
      xi = (int) xt;
      yi = (int) yt;
      xfrag = (float) ceil(xt) - xt;
     if(xfrag == 0)
       xfrag = 1;
      xfrag2 = xt+dx - (float) floor(xt+dx);
     if(xfrag2 == 0 && dx != 1.0f)
        xfrag2 = 1;
      red = xfrag * yfrag * src[(yi*swidth+xi)*4];
      green =  xfrag * yfrag * src[(yi*swidth+xi)*4+1];
      blue =   xfrag * yfrag * src[(yi*swidth+xi)*4+2];
      alpha =  xfrag * yfrag * src[(yi*swidth+xi)*4+3];

      for(i=0; xi + i + 1 < xt+dx-1; i++)
      {
        red += yfrag * src[(yi*swidth+xi+i+1)*4];
        green += yfrag * src[(yi*swidth+xi+i+1)*4+1];
        blue += yfrag * src[(yi*swidth+xi+i+1)*4+2];
        alpha += yfrag * src[(yi*swidth+xi+i+1)*4+3];
      } 

      red += xfrag2 * yfrag * src[(yi*swidth+xi+i+1)*4];
      green += xfrag2 * yfrag * src[(yi*swidth+xi+i+1)*4+1];
      blue += xfrag2 * yfrag * src[(yi*swidth+xi+i+1)*4+2];
      alpha += xfrag2 * yfrag * src[(yi*swidth+xi+i+1)*4+3];


      for(i=0; yi+i+1 < yt +dy-1 && yi + i+1 < sheight;i++)
      {
        red += xfrag * src[((yi+i+1)*swidth+xi)*4];
        green += xfrag * src[((yi+i+1)*swidth+xi)*4+1];
        blue += xfrag * src[((yi+i+1)*swidth+xi)*4+2];
        alpha += xfrag * src[((yi+i+1)*swidth+xi)*4+3];

        for (ii = 0; xi + ii + 1 < xt + dx - 1 && xi + ii + 1 < swidth; ii++)
        {
          red += src[((yi+i+1)*swidth+xi+ii+1)*4];
          green += src[((yi+i+1)*swidth+xi+ii+1)*4+1];
          blue += src[((yi+i+1)*swidth+xi+ii+1)*4+2];
          alpha += src[((yi+i+1)*swidth+xi+ii+1)*4+3];
        }

          if (yi + i + 1 < sheight && xi + ii + 1 < swidth)
          {
              red += xfrag2 * src[((yi+i+1)*swidth+xi+ii+1)*4];
              green += xfrag2 * src[((yi+i+1)*swidth+xi+ii+1)*4+1];
              blue += xfrag2 * src[((yi+i+1)*swidth+xi+ii+1)*4+2];
              alpha += xfrag2 * src[((yi+i+1)*swidth+xi+ii+1)*4+3];
          }
      }

      if (yi + i + 1 < sheight)
      {
          red += xfrag * yfrag2 * src[((yi + i + 1)*swidth + xi) * 4];
          green += xfrag * yfrag2 * src[((yi + i + 1)*swidth + xi) * 4 + 1];
          blue += xfrag * yfrag2 * src[((yi + i + 1)*swidth + xi) * 4 + 2];
          alpha += xfrag * yfrag2 * src[((yi + i + 1)*swidth + xi) * 4 + 3];

          for (ii = 0; xi + ii + 1 < xt + dx - 1 && xi + ii + 1 < swidth; ii++)
          {
              red += yfrag2 * src[((yi + i + 1)*swidth + xi + ii + 1) * 4];
              green += yfrag2 * src[((yi + i + 1)*swidth + xi + ii + 1) * 4 + 1];
              blue += yfrag2 * src[((yi + i + 1)*swidth + xi + ii + 1) * 4 + 2];
              alpha += yfrag2 * src[((yi + i + 1)*swidth + xi + ii + 1) * 4 + 3];
          }
      }

      if (yi + i + 1 < sheight && xi + ii + 1 < swidth)
      {
          red += xfrag2 * yfrag2 * src[((yi + i + 1)*swidth + xi + ii + 1) * 4];
          green += xfrag2 * yfrag2 * src[((yi + i + 1)*swidth + xi + ii + 1) * 4 + 1];
          blue += xfrag2 * yfrag2 * src[((yi + i + 1)*swidth + xi + ii + 1) * 4 + 2];
          alpha += xfrag2 * yfrag2 * src[((yi + i + 1)*swidth + xi + ii + 1) * 4 + 3];
      }


     red /= dx * dy;
     green /= dx * dy;
     blue /= dx * dy;
     alpha /= dx * dy;

     red = clamp(red, 0, 255);
     green = clamp(green, 0, 255);
     blue = clamp(blue, 0, 255);
     alpha = clamp(alpha, 0, 255);

     dest[(y*dwidth+x)*4] = (unsigned char) red;
     dest[(y*dwidth+x)*4+1] = (unsigned char) green;
     dest[(y*dwidth+x)*4+2] = (unsigned char) blue;
     dest[(y*dwidth+x)*4+3] = (unsigned char) alpha;
    }
  }


}

It is maintained in the Baby X resource compiler on github.

https://github.com/MalcolmMcLean/babyxrc

Malcolm McLean
  • 6,258
  • 1
  • 17
  • 18
  • Can you include a license file in your github repo so it is clear what the permissible use cases are ? I couldn't find one.... It seems like your project could be very useful to a lot of people... – Rahul Iyer Oct 07 '16 at 04:08
  • What is the name of this algorithm ? – Rahul Iyer Oct 07 '16 at 06:39
  • That code was devised by me and is available on the web "as is". Where code has been written by or based on other authors' work, I retain the licence terms and of course ask other people to abide by them. The algorithm was invented by me but is highly unlikely to be original, I call it the "averaging" method. – Malcolm McLean Oct 07 '16 at 07:58
  • What I mean is, normally a license like "MIT" or something is embedded which clearly state the terms - otherwise it is risky to use anything like this except in personal non-commercial projects.. – Rahul Iyer Oct 08 '16 at 02:57
  • Does you algorithm result in artificats being produced on the right half of all images ? – Rahul Iyer Oct 11 '16 at 12:44
  • Shouldn't do. If so a bugged version has been checked in. – Malcolm McLean Oct 11 '16 at 13:42
  • https://www.dropbox.com/s/myme1z1mkxjwyjf/artifact.zip?dl=0 If you have Xcode 8, you can open the Xcodeproj file in proj.ios_mac. The file where I used your function is HelloScene.cpp. You can set a breakpoint in your code and work backwards if necessary, but unless I'm making a blunder with pointers (very possible, I don't have much xp with pointers), using your function creates a pattern in the right third of the image... – Rahul Iyer Oct 12 '16 at 11:32
  • http://stackoverflow.com/questions/40002797/why-does-this-downscaling-algorithm-produce-artifacts?noredirect=1#comment67284941_40002797 Some think the floating point math is Br0k3n ... totes amaze balls! :D – Rahul Iyer Oct 12 '16 at 16:25
  • I've tried to fix it. See if the fixed version works. – Malcolm McLean Oct 12 '16 at 16:59
  • totes amaze balls on that blazing response big mac! Right now it looks totes amaze balls, but I have to test it more and look over the changes you made.... by the way... wouldn't it be just better to use integer arithmetic and just non-totes amaze balls the floating point arithmetic.... just to be sure... like Aliens 2. – Rahul Iyer Oct 12 '16 at 17:04
  • It can certainly be optimised. The resource compiler generates C dumps of images, so speed isn't a real priority. If you want to use it online using fixed point would maybe be faster. – Malcolm McLean Oct 13 '16 at 07:24
  • jajaja thats not what I mean - in the other conversation t'was suggested that due to the "perils" of floating point arithmetic / imprecision, it is better to use integer arithmetic, so that we don't generate artefacts... fp imprecision makes everyone cray-cray... by the way no artefacts so far..incred.. – Rahul Iyer Oct 13 '16 at 09:01
  • Sometimes png data doesn't include an alpha channel, and other times an entirely opaque png image has an alpha channel too. As a result your algorithm works well if there is an alpha channel but has problems otherwise..- Since you're mostly doing the same calculation for each channel, if you take the number of channels as input, and only perform the data manipulations for those channels, then your algorithm becomes more flexible.... – Rahul Iyer Oct 21 '16 at 05:49