Need to redo your image? Here's a nice algorithm to transform it as you like.
Introduction
Many, many moons ago (back in the days when 640x480 was considered high resolution), I needed an algorithm to place paintings and patterns (wall coverings like brick or wallpaper) in perspective on walls generated by an architectural rendering program. I developed a very simple technique to accomplish this — first in C under MS-DOS; then later on different platforms, including embedded graphics processors; and now this C++ implementation — one more new trick for this old dog.
For the programmers out there who do not have an interest in graphics, take a look at this article anyway. I have used many of these same “tricks” in non-graphical programs and as a foundation for other algorithms.
The Algorithm
In Figure 1, my source bitmap is a rectangle with four corner points: A through D. I select four corresponding points in the destination bitmap: A' through D'. There are no restraints on where the points of the new shape are in relationship to any other point. The major loop involves plotting the points along lines A'D' and B'C'. I then use each of the points on these lines as endpoints for another line between them. Each row of pixels from the source bitmap is then copied to the destination as this new line is plotted.
This technique is much simpler than the ones used in morphing programs where the destination is usually a series of curves rather than straight lines, and often pixels are blended together rather than just copied. It also may hit each destination pixel multiple times. While this may seem inefficient, the computational overhead to pick a specific source pixel for each point in the destination shape is much greater than that required to overwrite pixels multiple times.
In addition to the original goal (see Figure 2), users have found several other applications for this algorithm. Since there is no restriction placed on the orientation of the output “corner” points, images can be stretched, warped, mirrored, and rotated at will.
About the Code
This example was written using Microsoft Visual C++ v6.0. The code fragments presented here are very generic and should be portable with very little modification. Image modifications are made on memory bitmap images, not on the display. The code listings presented here are part of a sample application that loads images and provides a “rubber band” control to determine the destination. Full source code, project files, and notes that are too big to be included here, are available on the CUJ website at <www.cuj.com/code>. The sample application is far from complete; it is merely a small implementation to show the algorithm. It is limited to handle 24-bit uncompressed BMP files on full-color display hardware. Due to the large amount of MFC glue (we have other words for it in the shop), the application is compiler and platform specific.
The heart of the algorithm is class DeltaControl shown in Listing 1. This is a generic class that handles how often to increment a minor value while incrementing a major value. Common uses for DeltaControl include operations like fitting n pixels in a space m pixels wide, incrementing a progress bar one percent every n records, and, of course, since this is the same technique used in the inner loop of the Bressenham Line Algorithm (see sidebar), plotting lines. “Major” and “Minor” refer to the larger and the smaller value that will be handled. For instance, when plotting a line from (0, 0) to (25, 10), the X direction would be “major” and Y “minor.”
The member functions SetFrom and SetTo in Listing 2 set the starting and ending positions. After this initialization, the m_ErrorTerm value is set to half the major length. Next is used to calculate the next set of values and returns FALSE when there are no more values to calculate (i.e., the endpoint of a line has been plotted). Next adds the minor length to m_ErrorTerm. When m_ErrorTerm is greater than the major length, the minor value is incremented, and the major length is subtracted from m_ErrorTerm. If there is no change in the minor value, the major value is incremented. The notification member functions are provided each time that there is a change in major or minor values.
This is the primary class utilized in this example directly (and through its descendants) to not only plot the drawing of lines, but also the scaling of the images. It does this with integer math, which is still more efficient than floating-point operations in a wide variety of platforms in use today.
DeltaControl is one of the base classes for DeltaControlLine shown in Listing 3. This is the implementation of the actual line plotting, and each call to Next will compute new coordinates. The constructors call the Init member function, which is where a determination is made as to whether the change in the X direction is larger than the change in the Y direction, and then assigns the major and minor component accordingly.
The DeltaControlPair class in Listing 4 simultaneously increments two DeltaControl classes. As it is utilized in the major loop of this algorithm, as described above, it may need to have both lines being plotted incremented at the same time. This requires an override of the virtual Next function, as the default behavior changes either the major or minor value as required.
Listing 5 shows the definition of the CImageBitmap class that manages the image bitmaps. Note the m_Private member variable pointing to the undefined CIBHelper class. This is a technique that I adopted from a CUJ article by Dwayne Phillips [1] a few years back and has served my shop very well. One of the premises of object-oriented programming is hiding the implementation details from the higher levels. At our shop, the lower-level libraries are made available to junior programmers and customers, but only senior people can modify them and need access to the details involved. Only the “public” object interfaces are included in the header files, and the gory details are hidden in classes that are defined within the implementation source file and accessible only by the “public” object.
Listing 6 contains the definition for the private CIBHelper class. Note the virtual functions for reading and writing pixels. These functions allow you to provide overrides in derived classes to correctly manipulate pixels for any device. Also, more MFC glue is hidden in the implementation of these classes.
The member function of interest in CImageBitmap is Transform. Listing 7 shows where the drawing is controlled by utilizing all of the goodies I have been describing. The arguments to this function are an incoming bitmap object, the four destination points, and an offset point. The offset point is provided to handle the case where the destination bitmap is larger than the display and has been scrolled. The destination points would then be relative to the scrolled origin, not the bitmap origin. At reference point 1 in Listing 7, I define two DeltaControlLine objects named left and right that correspond to line A'D' and B'C' in Figure 1 and then a DeltaControlPair object (output_y) to control them. Note that “y” in this case is arbitrary — the movement need not be along the y axis in the output bitmap, but it is relative to the y direction in the source bitmap. At reference point 2 in Listing 7, I use a DeltaControl object (input_y) to control moving down the source bitmap in the y direction. I wrap the source and destination y controllers in another DeltaControlPair object, process_y. The major do loop is controlled by process_y.Next. This call is responsible for selecting which input row I am using via the input_y object and where the output line should be plotted by the left and right objects. Each time through the outer loop (reference point 3 in Listing 7), a CIBLine object (output_x) is defined to plot that line, and a DeltaControl object (input_x) is defined to track which column in the input row should be used. A DeltaControlPair object (process_x) is used to control the input_x and output_x objects and the inner loop.
The class CIBLine is derived from DeltaControlLine (see Listing 8). It is “private” to the CIBHelper class. When its ultimate parent, DeltaControl, notifies it of changes through the OnMajorChange and OnMinorChange functions, a pixel is transferred from the source to the destination bitmap.
Sample Operation
As an example, refer again to Figure 1. To keep this example simple, I will use a 5 x 5 pixel bitmap as the source [2]. I assign the destination points as:
A' (5, 5) B' (12, 7) C' (11, 10) D' (5, 11)The first time through the outer loop, left will be (5, 5) and right (12, 7). The starting point in the source bitmap will be (0, 0). The first invocation of the inner loop would then take the source pixels from the first row and plot them in a line from (5, 5) to (12, 7). The coordinates that the inner loop would generate would be:
SOURCE DESTINATION (0, 0) (5, 5) (0, 0) (6, 5) (1, 0) (6, 6) (2, 0) (7, 6) (2, 0) (8, 6) (3, 0) (9, 6) (3, 0) (10, 6) (4, 0) (10, 7) (4, 0) (11, 7) (4, 0) (12, 7)The second time through the outer loop, left will be (5, 6) and right (12, 8). The starting point in the source bitmap will be (0, 1). The inner loop would then take the source pixels from the second row and plot them in a line from (5, 6) to (12, 8). The third time through, left will be (5, 7), but right will not change from (12, 8). The source bitmap source would not change either. So, the inner loop would take the source pixels from the second row and plot them from (5, 7) to (12, 8).
Conclusion
This algorithm is not meant to provide a “morph” of an image, but rather is a quick way to handle a specific variety of image geometry alterations. The sample application is by no means complete — just a specific test platform for this article. It is missing several key features and is neither a complete image-processing or image-manipulation program. The graphic gurus in the audience will already be thinking of improvements. The mathematicians will already be finding “off by one” and other logic errors. And the assembler-at-heart guys will be screaming about inefficiency. I have also introduced a few basic techniques that can be applied in a wide array of applications and that you might consider adding to your toolbox.
Notes
[1] Dwayne Phillips. "Information Hiding in C via Modular Programming," C/C++ Users Journal, January 1998.
[2] The example grid coordinates assume the origin to be the “upper left” corner of the bitmaps with y increasing from top to bottom.
[3] J. E. Bressenham. "Algorithm for Computer Control of a Digital Plotter," IBM Systems Journal, Vol. 4, No. 1, 1965.
Bob Lorenzen has been involved in electronic imaging for over 30 years and has been programming for almost a quarter of a century. He is a principle in Lorenzen & Associates, a software firm in Tampa, Florida that specializes in raster graphics, and a former partner in Mathematica, Inc.