We present a program to rotate a GIF file using the shearing method, which is suitable for colour-indeced images as it does not require interpolation of pixel values.
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.
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