Christopher Dean has been a computer programmer for Teacher Support Software for 6 years and has almost completed his Bachelor of Science in Computer Engineering from the University of Florida. He is interested in computer graphics, object-oriented programming, and artificial intelligence. He may be reached via e-mail at cjd@reef.cis.uf].edu or via phone (904) 332-8655.
Introduction
Manipulation of bitmap images is important when performing tasks such as computer art and animation. Many paint programs allow images to be scaled, sheared, and rotated. When I wanted to mimic the actual turning of book pages to increase the realism of a reading program, I ran into problems because the user could alter the contents of the page. Standard animation techniques would not work because the animation would have to vary for every page and the content of each page was not known ahead of time. As a result I decided to simulate the page turning by successive shears and reductions of the page. Figure 1 shows how this appears on the screen. The only problem was that I could not find any algorithms to perform these transformations, so I decided to write my own.Image processing normally requires some sort of filtering and convolutions to accurately transform images. Unfortunately, for most practical uses this is too time consuming and in some cases very complex. The algorithms developed here are relatively quick and simple considering the task involved. The one drawback is that the transformations cause some aliasing, caused by the fixed resolution of the image. As a result, some lines and curves appear jagged. This is the case with shearing. In the case of scaling some lines may disappear and others may be duplicated too many times (edges, for example). For most animation purposes this is of no consequence. In any case, the effect can be reduced by using higher resolution graphics modes, digitizing images (which tend to blur the edges), or incorporating antialiasing techniques (see modifications).
Scaling Images
Expansion of images in integral multiples is fairly standard — just duplicate every pixel column or row N times. Shrinking of an image by a factor of 1/N is achieved by removing every Nth column or row. However, when you want to scale an image by a non-?? scalar, the procedure becomes more complex. You have to d?? cate or remove pixel rows or columns according to some spe?? pattern.The basis for determining this pattern is the Rothstein code, binary sequence representing a line with slope p/q. In the case o?? expanding an image horizontally, it tells you how to distribute q columns of the source image among p columns of the target, duplicating each appropriate column to fill in the gaps. For example, if you are expanding an image with q columns to a width of p columns, the Rothstein code will be a set of p bits with q of them set, each set bit evenly distributed among the p bits. Each set bit indicates that this column is to be copied, and each unset bit indicates that the column is to be a duplicate of the copied columns.
In the case of shearing, each set bit in the Rothstein code tells you which columns to move up. For shrinking an image, you use the inverse of the expansion slope, the factor q/p. The Rothstein code then tells you which columns to remove. Again each column with a set bit in the Rothstein code is copied and each column with an unset bit is removed. For scaling and shearing in other directions you use the code in the same way just for the rows instead of the columns.
The generation of the Rothstein code can be described graphically. First, plot a line with the desired slope on a grid. Every column in which the line crosses a horizontal grid line receives a one, all others a zero. If the slope of the line is greater than 45 degrees some adjustments must be made as described later. Listing 2 shows the routine to calculate the Rothstein code. At every column you increment psum by p. When psum overtakes qsum the line crosses a horizontal grid mark — the Rothstein code for the current column is set to one and qsum is incremented by q. This process continues until the number of columns has been reached.
For an expansion of 9/5 horizontally (Figure 2) we traverse the image column by column copying every column with a one in the Rothstein code and duplicating the previous column if the code has a zero (which itself may be a duplicate). For reduction of an image, every column whose Rothstein code is a zero is removed. Scaling vertically requires calculating the Rothstein code based upon the height instead of the width. This time the image is traversed row by row, removing every row with a code of zero for reduction, or duplicating the previous row if the code has a zero for enlargement.
Shearing images
Shearing vertically is similar to horizontal scaling in that the Rothstein code is computed using the width of the image. A one in the Rothstein code means the corresponding column and all columns following it are raised up one from the height of the previous column. The image can be traversed left to right or right to left to shear in different directions. Shearing horizontally is the same except the height is used for the Rothstein code and the image is traversed row by row. Figure 2 shows the Rothstein code for a vertical right shear of 5/9.The routines for the scaling horizontally and shearing vertically are presented in Listing 2. They work with any noncompressed image whether it be text or graphics and are fast and simple enough for use in animation applications. The transformations can be done on compressed images but only as they are decompressed. PCX images, for example, can be transformed as each pixel line is decompressed.
Rotations can be performed using vertical and horizontal shears by the same amount. To rotate clockwise you shear the image horizontally right and then vertically left by the same amount. Rotation in the counter-clockwise direction is just the opposite; you shear horizontally left and then vertically right by the same amount. The demo code in Listing 1 does just this in increments of five pixels. This illustrates some of the interesting transformations you can achieve by shearing a previously sheared image in a different direction and by altering the image dimensions between successive shears.
VGA-256 routines
Listing 1 and Listing 2 are the code for a demo in the VGA-256 mode (320 x 200 256 colors) written using Borland C and the Borland Graphic Interface (BGI). I chose this mode initially because it has one pixel per byte addressing, which makes transformations on individual columns easier than other modes. The demo presents a 3-D line drawing of a house that you can manipulate. You can only do one type of transformation at a time: scaling, right vertical shearing, left vertical shearing, right horizontal shearing, left horizontal shearing, or rotations. These transformations can be combined in any way necessary for your purposes (remembering that scaling an already scaled image increases aliasing) as in the turning of a page in a book.After selecting your transform choice you may use the arrow keys (up, down, left, and right for scaling; up and down for vertical shearing; left and right for horizontal shearing and rotations) to manipulate the image. The current width and height of the image are displayed at the bottom of the screen. The routines will not let the image become larger than the screen. When you are finished with your selected transformation press the END key.
Listing 2 contains the transform code for the VGA-256 mode. The first function calculates the Rothstein code based upon the fraction p/q (p = new dimension, q = old dimension). The max parameter may be one of four values depending on the transform desired, the bitmap's width, new width, height, or new height. TransXY combines scaling in both the horizontal and vertical directions for efficiency. It takes as arguments the source image, its dimensions, and its new dimensions.
First, the function determines if it is expanding or shrinking in either direction, allocates the memory needed to hold the new bitmap and computes the Rothstein codes for both directions. Next, it loops through the rows of the image, manipulating each based upon the Rothstein code for that row. If the Rothstein code for the current row is a one then the routine copies this row. If the Rothstein code is a zero then the routine does one of two things: it copies the previous row if the image is being expanded (horizontally) or it skips the row if the image is being reduced. When the row is copied, it must be traversed one column at a time. Each pixel in each column of the current row will be manipulated based upon the Rothstein code for that column. The pixel is copied if the Rothstein code for the column is a one. If the Rothstein code is a zero and the image is to be expanded (vertically) then the previous pixel is duplicated. Otherwise, the pixel is skipped. Thus, through two nested traversal loops, one for the row and one for the column, the image can be simultaneously scaled in both the x and y directions.
The shear routines are broken up into two functions, one for horizontal shearing and one for vertical. The vertical shear routine uses the difference between the new height and the original height as p and the width as q to calculate the Rothstein code for the shear. To perform what I call a right shift the routine starts at the left side of the image shearing the columns up so that the right side is the apex of the shear. The left shear is just the opposite, starting at the right side and moving toward the left shifting up. (The routine could also start at the same side only shifting down instead of up.)
To perform the shearing the routine traverses each column of the image, moving the column up one row for each one in the Rothstein code. The shifting is cumulative so that the next column is moved up as much as the previous column and moved up one more if the code is a one. If the shear is greater than 45 degrees the routine shifts each column up one for each multiple the new height is of the width. This is a quick and simple way to make this adjustment but not as precise as some other methods. Unless you require the shear to be exact, this is not a problem. The horizontal shear function works in the same manner as the vertical except the routine traverses the rows instead of the columns and shifts the rows horizontally.
Figure 3 shows a house in the VGA-256 mode. Figure 4, Figure 5, Figure 6, Figure 7, Figure 8, Figure 9, Figure 10, and Figure 11 show this house after being transformed through each of the transformations in the demo.
The Problem with Shearing
The biggest problem with shearing an image is that you no longer have a rectangular bitmap; you have empty areas at the corners. If you want to preserve the background underneath the sheared image there are two alternatives: using a mask or a special method for putting the sheared image to the screen. Listing 1 uses a modified version of Borland's putimage function. Because there are 256 colors to work with and only one pixel per byte in this mode, you can fill the destination buffer with a color that is not being used in the background. Thus, when you shear the image, the empty areas have this special color. When you put the image onto the screen you check for this color when copying the image. If the current pixel is this color then you don't copy it, thus the background is preserved.The xputimage function in Listing 1 accomplishes this. In other graphics modes this cannot be done because there are either not enough colors or there are multiple pixels per byte in more than one bit plane (usually) which complicates the writing of each byte to the screen. More than one pixel per byte causes each pixel to be more difficult to isolate and move. A mask can be used that is sheared along with the original image and ORed to the screen with the sheared image being ANDed on top.
Enhancements and Modifications
The VGA-256 routines can be modified for other graphics modes. The routines must handle multiple bit planes and multiple pixels per byte. Offsets within the source and destination bytes for each pixel must be maintained since they will become out of sync. As you duplicate or remove columns and rows, the source and destination pixel offsets within their respective bytes move apart from each other. The bit(s) that make up each pixel column must be shifted into the appropriate destination bit position before copying. To copy the bit(s), a mask is used so only the corresponding bit(s) are changed in the destination byte. If your application only requires vertical scaling then the bit shifting is unnecessary. For shearing, however, it is still needed.The shear routines must also be modified to shear a mask that is the same size as the image. A modified putimage routine is also necessary to use this mask. As mentioned previously, this mask is ORed to the screen and the image is ANDed on top of the mask, preserving the background. Unfortunately, these modifications will slow the transformations drastically. For example, routines for the sixteen-color VGA modes must read and write each byte of an image eight times more than VGA-256, not to mention traversing all four bit planes.
Some speed enhancements can be implemented especially if you know ahead of time the exact transforms that will be performed. Each transform routine allocates a new buffer for the transformed image. If you know the size of the biggest resulting image you will need then you can allocate this buffer ahead of time and pass it to the transformation routines so the time acquiring and freeing memory will be removed. Also, if you do write routines for other graphics modes you can make your images start and change width on byte boundaries. Then the excess code necessary to manage the trailing and preceding pixel columns not starting on byte boundaries can be removed. The putimage routine then becomes almost as simple as that of VGA-256. Other speed enhancements include using inline assembly where necessary to speed up reading and writing the image.
To increase the quality of the images after transformation, some antialiasing techniques can be used. However, these will slow down the transformations considerably so only use them if necessary. For my animation purposes the quality was not an issue. A typical antialiasing procedure is to make every pixel the average color (RGB values) of its neighbors. This will blur the edges so they appear smoother. This will only work satisfactorily when you have many colors to choose from. Many other techniques for edge detection and smoothing can be found in image processing books.
Conclusion
Whether it be for painting, animation, font manipulation, or even text manipulation, the algorithms presented above can help. They offer easy methods for scaling, shearing, and rotating bitmaps in your own programs much like those used in commercial paint programs and some graphics packages.
References
Foley, James D.; van Dam, Andries; Feiner, Steven K.; Hughes, John F. Computer Graphics Principles and Practice. Addison-Wesley Publishing Company, 1990.Wilton, Richard. Programmer's Guide to PC & PS/2 Video Systems. Microsoft Press, 1987.