Rotate GIF by shear

Introduction

Rotating an image is a common requirement, especially GIFs with transparency. However a rotation matrix cannt be used because it requires interpolation of pixels, which is not possible in a colour indexed image. However rotation is possible using the shearing method.

Background

To rotate a point we must apply sine and cosine to the x and y components. Specifically

x' = x cos(theta) - y sin(theta)

y' = x sin(theta) + y cos(theta)

And so it is possible to rotate an image by iterating over the destination pixels, applying the reverse of this equation (theta = -theta), and finding the right point in the source image. However  the sample point is vanishingly unlikely to hit a pixel exactly. And so we must interpolate the four closet pixels to obtain the output pixel. If we don't do this, and choose the nearest, we will get strange artifacts as source pixels are doubled and dropped, technically termed "aliasing".

With a true colour image, interpolation is relatively simple (as long as we don't demand mathematically perfect results), But with a colour-indexed image, such as a GIF file, it is impossible, as we only have a restricted set of pixels to choose from. So using the rotation matrix method, we have to accept aliasing.

However it is possible to avoid this. by using another algorithm for rotation. A rotation is equivalent to three shear transforms. To rotate an image by 180 degrees, we can shear the entire width, shear the entire height, and then shear the entire width again. This should be easy to visualise, and gives you an intuitive understanding of the algorithm. It also works for other values.

There are some provisios. I's only possible to rotate by whole pixels. So for a finite image, small rotations are disallowed. And the image rows and columns are broken up into runs of source pixels, which is itself  source of aliasing. However results are relatively good, and the method is established. 

The code is packaged as a working program. GIF images are rectagular, and is only possible to rotate geometry in the incircle without changing the dimensions of the image. So the program is suitable for GIFs with transparency. The alternative of expanding the dimensions would quickly lead to runaway inflation of image size.

Using the code

The code is all pure ANSI C. Just type

gcc *.c

to obtain the executable.

/**
  Rotate an image, using the shearing method.

Params:
  binary - the binary or colour-indexed image
  width - image width
  height - image height
  cx - centre x, y co-ordinates (pass in 1.5, 1.5 for the centre of a 3x3 image)
  cy - centre x, y co-ordinates (pass in 1.5, 1.5 for the centre of a 3x3 image)
  theta - angle to rotate by
  out[out] - buffer for output (can't be the same as input)
  
Returns: 0 for success

  Conventional image rotation by the matrix method causes destination pixels to be
    sub-samples of source pixels. This isn't a problem with continous tone images where
    the new pixel values can be obtained by interpolation. However with binary or
    colour-index images, interpolation isn't possible. The shearing method preserves the
    pixels, at some cost in rotational accuracy.

  */
int rotatebyshear(unsigned char *binary, int width, int height, double cx, double cy, double theta, unsigned char *out)
{
    double alpha;
    double beta;
    int dpx;
    int tx, ty;
    int x, y;

    assert(binary != out);
    theta = fmod(theta, 2 * PI);

    if(theta >= -PI/2 && theta <= PI/2)
    {
      alpha = -tan(theta/2);
      beta = sin(theta);

      for(y=0;y<height;y++)
      {
         dpx = (int) floor(alpha * (y - cy) + 0.5);
         for(x=0;x<width;x++)
         {
           ty = y + (int) floor(beta * (x + dpx - cx) + 0.5);
           tx = x + dpx + (int) floor(alpha * (ty - cy) + 0.5);
           if(tx >= 0 && tx < width && ty >= 0 && ty < height)
             out[y*width+x] = binary[ty*width+tx];
           else
             out[y*width+x] = 0;
         }
      }
    }
    else
    {
        alpha = -tan( (theta + PI) / 2);
        beta = sin(theta + PI);
        for(y=0;y<height;y++)
        {
         dpx = (int) floor(alpha * (y - cy) + 0.5);
         for(x=0;x<width;x++)
         {
           ty = y + (int) floor(beta * (x + dpx - cx) + 0.5);
           tx = x + dpx + (int) floor(alpha * (ty - cy) + 0.5);
           tx = (int) (cx-(tx - cx));
           ty = (int) (cy-(ty - cy));
           if(tx >= 0 && tx < width && ty >= 0 && ty < height)
             out[y*width+x] = binary[ty*width+tx];
           else
             out[y*width+x] = 0;
         }
      }
    }

    return 0;
}

This is the function you want.

The shear transformation is given by the matrix

And is one of the basic simple transforms.

Results

Lena 256 GIF	Lena rotated

The results are not perfect. You see severe "jaggies" on Lena's hat and left cheek, and of course the image edges themselves are aliased. But all the pixels are retained. There is no banding or diminution of quality In the continuous tone areas.

Points of Interest

You might wonder where we obtained such a high quality 256 colour Lena, with no mach banding at all on the shoulder. Of course we used the Principal Component Analysis algorithm.

History

The code is part of the binary image library, on github

https://github.com/MalcolmMcLean/binaryimagelibrary