A 2-D DDA Algorithm for Fast Image Scaling

Dean is a programmer/analyst developing graphics and imaging applications. He can be contacted at [email protected].

Graphic images are almost never exactly the right size -- they're either too small for a wallpaper background or too big for an icon. Consequently, changing image size is among the most-common kinds of image manipulation. Of course, a digital image doesn't really have a "size" like a photograph does; it's just a collection of discrete units of color information called pixels. The color information might be direct, so that the pixels themselves contain color information (24-bit RGB images). More often, however, the image pixels contain indirect color information in the form of color-table look-up values (8-bit color-table images). Pixels are organized as a grid of rows or scan lines (vertically), each of which contains some number of individual pixels (horizontally).

The most meaningful way to talk about a digital image's size is by referring to the number of pixels it contains, expressed in rows×columns. Thus, resizing an image means mapping the original pixels to another grid that has a different number of pixels.

It's easy to imagine changing an image's size in integer units. To enlarge an image by two, just copy each pixel twice; to reduce an image to one third of the original, display every third pixel. Scaling an image by noninteger amounts is more problematic. Intuitively, it would seem that, to scale an image by one and a half times, you'd need to work with half a pixel at some point. But what does "half a pixel" mean?

One way to approach this problem is to interpolate existing image pixels. Interpolation combines the color values of a group of pixels in some way in order to predict the value of a pixel between them. Interpolation gives good results, but is slow because each output pixel requires several floating-point calculations. For palette-table images, time is also spent searching the table for a color closely matching the interpolated color.

The scaling technique I'll present here doesn't require floating-point math and is, therefore, considerably faster than those that do. In particular, it is well suited to common, 8-bit color-table images because no table searching is involved. The algorithm is based on the differential techniques used to display lines and curves on raster devices. This classic technique (thanks to Bresenham, among others) is referred to as the Digital Differential Analyzer (DDA). DDAs have been examined before in DDJ, most recently in the article "Rendering Circles and Ellipses," by Tim Kientzle ("Algorithm Alley," DDJ, July 1994). Likewise, Michael Abrash discussed the topic in his "Graphics Programming" column (DDJ, September 1992). Finally, Tim Paterson covered DDA in his article "Circles and the Digital Differential Analyzer" (DDJ, July 1990). The algorithm I present here uses a similar approach, but works on 2D images rather then 1-D lines; consequently, I'll refer to it as 2-D DDA.

The 2-D DDA

Usually, the scaling factor for an image is specified as either a percentage of the original (200 percent, 45 percent, and so on), or as a multiplication factor (2×, 3×). Either can also be viewed as a ratio of image elements in the resized image to the elements in the original image. So "200 percent" means there are two pixels in the resized image for each pixel in the original image.

Most people intuitively visualize image resizing in terms of stretching or shrinking the original image to fit in a different space. Instead, think of the resized image as a grid of points that must fit into the same space as the original image. Figure 1 illustrates this. The red boxes are the original pixels, while the green dots are the pixels in the resized image, in this case an enlarged image.

Conceptually, whichever box a green pixel falls in is the pixel value copied to the resized image. Note that although it appears that a green pixel can straddle more than one box, in truth, a pixel is always in only one box.

In Figure 2, the ratio of output pixels to original pixels is 11/4, an enlargement of 275 percent. Therefore, the distance between adjacent output pixels, when viewed from the original image, is 4/11, or 0.364. This is the pixel differential. If the image is resized by the same amount in x and y, then the differential is the same in both directions.

Looking in the x direction, the first green pixel is in the corner of the original pixel, so its differential is 0. The second green pixel is Dx (the pixel differential) away, the third is 2Dx, and all three fall inside the first original pixel. The fourth green pixel is in the second original pixel; its accumulated differential, 3Dx or 1.092, is greater than 1. In fact, the fourth pixel is 0.092 inside the second original pixel. Each whole-number change signals a boundary crossing in the original pixel grid. You now have the basis for a general differential algorithm in one dimension; see Example 1. All that remains is to get rid of the floating-point numbers, expand to 2-D, and look for optimizations.

To get rid of the floating-point numbers, simply scale up the differential. Let's use a scaling constant of 1000 and cast the differential to an int using Dx=(int)(1.0/scale*1000);. There's no real magic to the number 1000, and changing it has little effect. Scaling up the differential also affects the accumulated differential by the same amount; that is, a crossing occurs at accumulations of 1000, 2000, and so on. To expand to 2-D, simply add a second differential for the y direction and add an outer loop to process the rows, while the inner loop does each pixel in the rows.

The Code

Listing One (beginning on page 78) is a C function that scales an image using the 2-D DDA approach. It takes a pointer to a file containing the original image, the size of the original, and a scale factor. The image is scaled by the same amount horizontally and vertically. The scale factor is multiplicative so that 1.0 is full size, 2.0 is a double-sized enlargement, and 0.5 is a half-sized reduction. ResizeDDA assumes an external function called getline() that returns a single raster from an image, and SetPixel(), a function that stores a pixel value at a particular (x,y) location -- an output buffer or the screen. getmem() simply wraps the C library function malloc() to provide error checking.

The accumulated differentials in variables ddax and dday are initialized to -1000, and the test for crossing to a new original pixel is for the accumulated differential to go nonnegative.

The inner loop processes pixels in a scan line from the original image into a resized scan line. The outer loop then repeatedly outputs that scan line based on the y differential. For the y direction, crossing the threshold for the accumulated differential triggers reading of a new scan line from the original image, which is then processed by the inner loop.

Figure 3(a) is an image displayed at 100 percent, Figure 3(b) is scaled by 164 percent, and Figure 3(c), by 61 percent using the code in Listing One.

Conclusion

If speed is what you need, then the 2-D DDA technique should be just what the doctor ordered. Enlarging and reducing (or same-size) are handled equally well. The output results and speed are similar to the simple technique of copying or skipping blocks of pixels, but with the significant advantage that they are not limited to integer scaling factors.

DDJ

Listing One

/**************************************************************************
** ResizeDDA -- Reads an image from file 'f' one scan line at a time, 
** outputs the image resized by the 'zoom' factor.
*/
void ResizeDDA(FILE *f, int rows, int cols, double zoom)
{
    unsigned char   *aspline, *line;
    int             x, y;
    int             ddax, dday, izoom, i, k;
    extern int      getline(FILE *, int, unsigned char *);


</p>
    /* Calculate the differential amount */
    izoom = (int)(1.0/zoom * 1000);
    /* Allocate a buffer for a scan line from original image, and a
    ** resized scan line */
    aspline = (unsigned char *)getmem((t_size)cols);
    line    = (unsigned char *)getmem((t_size)(zoom * cols + 1));
    /* Initialize the output Y value and vertial differential */
    y = 0;
    dday = 0;
    /* Loop over rows in the original image */
    for (i = 0; i < rows; i++) {
        /* Get a scan line from the original image (8-bit values expected) */
        getline(f,cols,aspline);
        /* Adjust the vertical accumulated differential, initialize the
        ** output X pixel and horizontal accumulated differential */
        dday -= 1000;
        x    = 0;
        ddax = 0;
        /* Loop over pixels in the original image */
        for (j = 0; j < cols; j++) {
            /* Adjust the horizontal accumulated differential */
            ddax -= 1000;
            while (ddax < 0) {
                /* Store values from original image scanline into the scaled
                ** buffer until accumulated differential crosses threshold */
                line[x] = aspline[j];
                x++;
                ddax += izoom;
            }
        }
        while (dday < 0) {
            /* The 'outer loop' -- output resized scan lines until the
            ** vertical threshold is crossed */
            dday += izoom;
            for (k = 0; k < x; k++) {
                SetPixel(k, y, line[k]);
            }
            y++;
        }
    }
    free(aspline);
    free(line);
}
/**************************************************************************
** getmem - memory allocator
*/
void * getmen(size_t size)
{
    void * p;
    if (p = malloc(size)) {
        return p;
    }
    printf("Allocation of %old bytes failed \n size);
    exit(1);
}

Back to Article