Bitmap Image Rotation: Staircasing & Interpolation

London Wall in Rain, 1981
London Wall in Rain, 1981

When you perform a rotation operation on a bitmap image, such as a digital photograph that you’re trying to straighten, you may sometimes create an undesirable effect called staircasing, where what were apparently straight and smooth edges in the original image become noticeably “stepped” in the rotated result. I noticed this problem recently when I tried to correct a shooting error in the image above (the version above shows the corrected image).

This article explains:

Staircasing: the Problem

Generally, whenever someone takes a photograph of a natural scene, they attempt to align the camera so that the ground line will appear exactly horizontal, and so that vertical edges in the scene will be truly vertical in the image.

However, the photographer doesn’t always achieve this, and that is becoming a more frequent problem in these days of smaller cameras. When you’re holding up your phone camera, it can be very difficult to ensure that it is exactly perpendicular to the horizon.

There are apps that you can install on your phone that display a “torpedo level” widget, so that you can determine when your device is exactly horizontal, but most people don’t use such apps. In any case, once a photo has been taken, you usually can’t go back and take it again.

Below is an example of an image where what should be vertical edges are not quite vertical, due to the angle at which the camera was held when the photograph was taken. I took this photo in London in 1981, and since then many of the buildings in the picture have been demolished, so there’s zero chance of being able to retake the photo!

Uncorrected Image
Uncorrected Image

If you look closely at the image above, you can see that what should be a vertical edge nearest to the centerline of the picture is not quite vertical. It’s tilted about 1° counter-clockwise. In theory, it’s easy to fix this by rotating the entire image 1° clockwise. However, if this is not done carefully, staircasing effects can result.

Below is an example of visible staircasing in a portion of the rotated image, resulting from an attempt to straighten the verticals in the original. (This is an enlargement to show the effect.) Notice the jagged transitions where the bright lamps contrast with the dark background.

Staircasing Effect in Bitmap Image
Staircasing Effect in Bitmap Image

How can you avoid this undesirable effect? Below, I offer a couple of solutions, but it’s important to bear in mind these overriding principles:

  • Except for rotations in multiples of 90°, you should avoid rotating images unless absolutely necessary, because most rotations result in loss of detail.
  • If you must rotate an image, perform only one rotation to achieve the final result, because each individual rotation introduces errors. For example, if you want to rotate your image by 3°, do that as one 3° operation rather than three consecutive 1° operations.

Staircasing: the Cause

As I explained in an earlier post, when you take a digital photograph, your camera creates a rectangular bitmap matrix of colored “dots” or pixels. The color value of each pixel is determined by the color of light shining on that particular detector in the sensor.

If you subsequently want to change the mapping of the color values to the bitmap matrix, as happens if you want to resize or rotate the image, then there has to be a way to determine the new color value of each pixel in the modified image.

The simplest way to determine the new color value of each pixel is simply to pick the value of the nearest corresponding pixel in the original image. (This is called Nearest-Neighbor Interpolation.) However, in areas of the image where there are sharp transitions of color, this method can lead to jagged edges and the effect called Staircasing.

(If you rotate a bitmap through some exact multiple of 90°, then this effect does not appear, because the original rectangular matrix maps exactly to a new rectangular matrix. The discussion here relates to rotations that are not a multiple of 90°.)

The following example shows a simple case of this problem. In these images, I’ve deliberately enlarged everything to the point that you can see the individual pixel boundaries; you would rarely see these at normal viewing magnifications. I’ve also tilted an edge that was originally vertical into a non-vertical position, rather than vice versa, because this shows the effect more plainly.

In the first image, on the left is the original unrotated image, which consists only of a dark rectangle abutting a light-colored rectangle. The transition between the two colors is a vertical edge, which maps neatly to the vertical alignment of the pixels.

Rotation of Bitmap without Interpolation
Rotation of Bitmap without Interpolation

On the right above is the result of rotating this image by 1 degree counter-clockwise, without any interpolation. Each new pixel takes the color value of the nearest pixel in the original image. Since the transition between the colors no longer maps neatly into vertically-aligned pixels, a jagged edge transition has now been created.

To reduce the quantization effects, a more sophisticated way of determining the new pixel values is by interpolation. Interpolation is basically a sophisticated form of averaging, whereby the color value of each interpolated pixel is determined by averaging the values of the nearest few pixels in the original image.

Here’s the same rotation operation, but with interpolation applied:

Rotated Bitmap with Interpolation
Rotated Bitmap with Interpolation

As you can see, the jaggedness is reduced, although there are still visible discontinuities, due to the small number of pixels involved.

Staircasing: the Solution

As demonstrated above, the staircasing effect is caused by inadequate interpolation of color values between adjacent pixels in a bitmap. If the interpolation could somehow be made perfect, the problem would not occur.

Typically, when we rotate an image, we’re using third-party software, and we’re stuck with whatever interpolation algorithm has been provided by the software manufacturer (which may consist of no interpolation at all). Thus, we can’t improve the interpolation, so all we can do is to take steps to disguise the problem.

  1. Use Interpolation
  2. Increase Resolution

Solution #1: Make Sure to Use Interpolation

Whenever you notice staircasing in a rotated image, the first thing to check is whether interpolation was applied during the rotation operation. Depending on the software you used to perform the rotation, interpolation may not have been applied by default, or, in the case of some low-end software, it may not even be available.

Look for an “interpolation” setting in your software. In some cases, this is referred to as “anti-aliasing”, even though there isn’t really any “aliasing” in this case. Make sure that “interpolation” or “anti-aliasing” are switched on.

Solution #2: Increase Image Resolution

If using interpolation doesn’t work, then the second approach is to try to reduce the quantization artefacts by temporarily increasing the Image Resolution. Most modern bitmap processing (“Paint”) software allows you to do this quite easily.

The procedure is as follows:

  1. Use your paint software to increase the image DPI. To minimize the amount of unnecessary interpolation required, it’s usually best to set the new DPI value to be an exact multiple of the current value. For example, if the image currently has 72 DPI, try increasing to four times that (288 DPI), or another higher multiple. (In general, the higher the DPI, the better, but of course increasing the resolution increases the total image size, so processing takes longer and requires more memory.)
  2. Perform the rotation operation.
  3. Reduce the image DPI back to the original value.
  4. Evaluate the results. If staircasing is still visible, repeat from Step 1, but this time increase the image DPI to an even higher multiple of the original.

Use Your Own Judgment

Ultimately, fixing this problem is a matter of aesthetic judgment; you have to view the results and decide when they’re good enough. What’s good enough in one situation may not be good enough in another.

I hope that my explanation has been helpful, but, if you need more detail, here is a very good post describing these concepts.

Definition: Image Size, Dimensions and Resolution

It may be helpful to remind ourselves of the differences between bitmap image size, dimensions and resolution. In my experience, these important distinctions can cause immense confusion to people working with bitmap images. That is not helped by the fact that some of these terms are used loosely and interchangeably in existing documentation, which merely adds to the confusion.

Each pixel in a bitmap image has a constant color value. The illusion that the colors in the image vary continuously occurs because the image typically consists of a very large number of pixels.

It’s intuitively obvious that each bitmap has a particular “size”, but what exactly does that term mean in this context? There’s more to it than just the number of pixels in the matrix, because that does not specify the size at which the bitmap is supposed to be viewed.

Note that these are my definitions of the terms, and you may find varying definitions in other documentation. The important point is to understand what is meant by each term, rather than which term is used for which concept.

Definitions
Definitions

Image Size: The width and height of the image (W x H) in pixels

Image Dimensions: The width and height of the image (W x H) in measurement units

Image Resolution: Dots Per Inch. It is possible for an image to have different horizontal and vertical DPI values, but this is rarely done in practice. The horizontal and vertical resolutions are usually the same.

Definition: Interpolation

Interpolation is a mathematical concept, which involves creating new data points between the data points of an existing set.

When applied to images, interpolation usually involves creating a new pixel color value by averaging the values of nearby pixels, according to some algorithm.

The Two Types of Computer Graphics: Bitmaps and Vector Drawings

I received some feedback from my previous posts on computer graphics asking for a basic explanation of the differences between the two main ways of representing images in digital computer files, which are:

  • Bitmap “paintings”
  • Vector “drawings”

Most people probably view images on their computers (or phones, tablets or any other digital device with a pictorial interface) without giving any thought to how the image is stored and displayed in the computer. That’s fine if you’re just a user of images, but for those of us who want to create or manipulate computer graphic images, it’s important to understand the internal format of the files.

Bitmap Images

If you’ve ever taken or downloaded a digital photo, you’re already familiar with bitmap images, even if you weren’t aware that that’s what digital photos are.

A bitmap represents an image by treating the image area as a rectangle, and dividing up the rectangle into a two-dimensional array of tiny pixels. For example, an image produced by a high-resolution phone camera may have dimensions of 4128 pixels horizontally and 3096 pixels vertically, requiring 4128×3096 = 12,780,288 pixels for the entire image. (Bitmap images usually involve large numbers of pixels, but computers are really good at handling large numbers of items!) Each pixel specifies a single color value for the image at that point. The resulting image is displayed simply by copying (“blitting”) the array of pixels to the screen, with each pixel showing its defined color.

Some of the smallest bitmap images you’ll see are the icons used for programs and other items in computer user interfaces. The size of these bitmaps can be as small as 16×16 pixels, which provides very little detail, but is sufficient for images that will always be viewed in tiny sizes. Here’s one that I created for a user interface some time ago:

icon16x16_versions2

Enlarging this image enables you to see each individual pixel:

icon16x16_versions_enlarged

You can see the pixel boundaries here, and count them to confirm that (including the white pixels at the edges) the image is indeed 16×16 pixels.

Obviously, the enlarged image looks unacceptably crude, but, since the image would normally never be viewed at this level of magnification, it’s good enough for use as an icon. In most cases, such as digital photographs, there are so many pixels in the bitmap that your eye can’t distinguish them at normal viewing sizes, so you see the image as a continuous set of tones.

Bitmap images have a “resolution”, which limits the size to which you can magnify the image without visible degradation. Images with higher numbers of pixels have higher resolution.

Given that bitmap image files are usually large, it’s helpful to be able to be able to compress the pixel map in some way, and there are many well-known methods for doing this. The tradeoff is that, the more compression you apply, the worse the image tends to look. One of the best-known is JPEG (a standard created by the Joint Photographic Experts’ Group), which is intended to allow you to apply variable amounts of compression to digital photographs. However, it’s important to realize that bitmap image files are not necessarily compressed.

Programs that are designed to process bitmap images are referred to as “paint” programs. Well-known examples are: Adobe Photoshop and Corel PhotoPaint.

Vector Images

The alternative way of producing a computer image is to create a list of instructions describing how to draw the image, then store that list as the image file. When the file is opened, the computer interprets each instruction and redraws the complete image, usually as a bitmap for display purposes. This process is called rasterization.

This may seem to be an unnecessarily complex way to create a computer image. Wouldn’t it just be simpler to stick to bitmap images for everything? Well, it probably wouldn’t be a good idea to try to store a photo of your dog as a vector image, but it turns out that there are some cases where vector images are preferable to bitmap images. Part of the skill set of a digital artist is knowing which cases are best suited to vector images, and which to bitmaps.

There are many vector drawing standards, and many of those are proprietary (e.g., AI, CDR). One open vector drawing standard that’s becoming increasingly popular is SVG (Scalable Vector Graphics). You can view the contents of an SVG file by opening it with a text editor program (such as Notepad).

Here’s a very simple example of an SVG image file, consisting of a white cross on a red circle:

icon_err_gen

(Not all browsers can interpret SVG files, so I rendered the image above as a bitmap to ensure that you can see it!)

If you open the SVG file with a text editor, you can see the instructions that create the image shown above. In this case, the important instructions look like this:

<g id=”Layer_x0020_1″>

<circle class=”fil0″ cx=”2448″ cy=”6098″ r=”83″/>

<path class=”fil1″ d=”M2398 6053l5 -5c4,-4 13,-1 20,5l26 26 26 -26c7,-7 16,-9 20,-5l5 5c4,4 1,13 -5,20l-26 26 26 26c7,7 9,16 5,20l-5 5c-4,4 -13,1 -20,-5l-26 -26 -26 26c-7,7 -16,9 -20,5l-5 -5c-4,-4 -1,-13 5,-20l26 -26 -26 -26c-7,-7 -9,-16 -5,-20z”/>

</g>

As you’d expect, the instructions tell the computer to draw a “circle”, and then create the cross item by following the coordinates specified for the “path” item.

Of course, if you were to try to represent a photograph of your dog as a vector image, the resulting file would contain a huge number of instructions. That’s why bitmap images are usually preferable for digital photographs and other very complex scenes.

A major advantage of vector image formats is that the picture can be rendered at any size without degradation. Bitmap images have inherent resolutions, which vector images do not have.

Programs that are designed to process vector images are referred to as “drawing” programs. Well-known examples are: Adobe Illustrator and Corel Draw.

Converting Between Bitmap and Vector Images

It’s often necessary to convert a vector image into a bitmap image, and, less frequently, to convert a bitmap image into a vector image.

Conversion of vector images to bitmaps occurs all the time, every time you want to view the content of a vector image. When you open a vector image, the computer reads the instructions in the file, and draws the shapes into a temporary bitmap that it displays for you.

Converting bitmaps to vector images requires special software. The process is usually called “Tracing”. Years ago, you had to buy tracing software separately, but now most vector drawing software includes built-in tracing capabilities. As the name suggests, tracing software works by “drawing around” the edges of the bitmap, so that it creates shapes and lines representing the image. The result of the operation is that the software generates a set of mathematical curves that define the vector image.

Summary of the Pros and Cons

There are situations where bitmap images are preferable to vector images, and vice versa. Here’s a summary of the pros and cons of each type.

Bitmap

Advantages:

  • Complex scenes can be depicted as easily as simple scenes.
  • Significant compression is usually possible, at the expense of loss of quality.
  • Rendering is computationally easy; requires minimal computing power.

Disadvantages:

  • Size: Files tend to be large.
  • Not scalable: attempting to magnify an image causes degradation.

Vector

Advantages:

  • Compact: Files tend to be small.
  • Scalable: images can be displayed at any resolution without degradation.

Disadvantages:

  • Complex scenes are difficult to encode, which tends to create very large files.
  • Rendering is computationally intensive; requires significant computing power.