Dwayne Phillips works as a computer and electronics engineer with the U.S. Department of Defense. He has a PhD in Electrical and Computer Engineering from Louisiana State University. His interests include computer vision, artificial intelligence, software engineering, and programming languages.
Introduction to the Series of Articles
This is the 14th in a series of articles on the C Image Processing System (CIPS) that performs image-processing operations on grayscale images. Previous articles in the series discussed reading, writing, displaying, and printing images (TIFF format), histograms, edge detection, spatial frequency filtering, sundry image operations, image segmentation, working with shapes, and geometric operations (see sidebar for an index). This article extends the discussion of geometric operations and delves into warping and morphing (Hollywood — here we come).Image warping is a technique that Hollywood discovered in the 1980's. The result is the magic we see every day in commercials, music videos, and movies. Warping (and its cousin morphing) "melts" old cars into new ones and can turn a car into a tiger.
Image Warping
Image warping is a technique that bends and distorts objects in images. Remember when we used to press a flat piece of silly putty on a newspaper to copy the image to the silly putty? Grabbing and pulling the silly putty distorted the appearance of the image. We could bend and stretch the silly putty until the objects in the image took on weird and wonderful shapes. Image warping does the same for digitized images.Image warping actually began as early as the 1960's with early space probes. Pictures of the moon produced by the "cameras" on the probes were distorted — straight lines appeared bent and the objects were out of proportion. Image processors at the Jet Propulsion Laboratory [1] transformed these square images into pie shapes, which had straight lines where straight lines belonged.
The basic idea behind warping is to transform a quadrilateral to a rectangle [2]. A quadrilateral is a four-cornered region bounded by straight lines (a rectangle is a special case of a quadrilateral). Transforming a quadrilateral to a rectangle warps the objects inside the quadrilateral.
Figure 1 shows a quadrilateral with a point P inside. Transforming a quadrilateral to a rectangle requires finding the coordinates of any point P inside the quadrilateral. This is possible given the coordinates of the four corners P1, P2, P3, and P4 and the fractions a and b along the edges. The key to finding P is a technique called bi-linear interpolation. In the previous installment to this series [3] a form of this technique, called gray level bi-linear interpolation, determined the gray level of a pixel between other pixels. Spatial bi-linear interpolation works in a similar fashion to find the location of a pixel between other pixels.
(Note: This article deals with shapes divided into four parts. As a convention, I number the parts 1, 2, 3, and 4, where part 1 is in the upper left-hand corner, and 2 through 4 are found by proceeding clockwise.)
Equations (1) through (7) (see box, "Spatial Bi-linear Interpolation") show how bi-linear interpolation determines the coordinates of point P. If mathematical derivation is not for you, skip down to the results in equations (6) and (7). The source code shown later will implement these equations. These equations interpolate along the top and bottom of the quadrilateral and then along the sides. In the equations, a and b are fractions (0 < a < 1, 0 < b < 1).
Equation (1) finds point Q by interpolating between points P1 and P2 using a. Equation (2) finds point R by interpolating between points P3 and P4 using a. Equation (3) finds point P by interpolating between Q and R using b. Equation (4) is the result of substituting the values of Q and R from equations (1) and (2) into equation (3). Equation (5) gathers all the terms from (4).
Equations (6) and (7) are the final answers. Equation (6) shows how to find the x-coordinate of any point P given the x-coordinates of the quadrilateral's four corners and the fractions a and b. Equation (7) does the same for the y-coordinate. The subroutines described below implement equations (6) and (7). Notice the ab term in the equations. This term introduces non-linearities (curves) into the results.
Two Ways to Warp
In this article I implement two kinds of warping. The first is control point warping illustrated in Figure 2. Take a square section of an image (such as a ROWSxCOLS array) and divide it into four smaller squares 1, 2, 3, and 4. Pick a control point anywhere inside the square section. This control point divides the square section into four quadrilaterals as shown in the top part of Figure 2. Equations (6) and (7) will transform these four quadrilaterals back into the four squares as shown in the bottom part of Figure 2. This will warp the objects in the image. The control point effectively dictates the kind of warping that is done.Listing 1 shows how CIPS implements control point warping. Function warp controls the process and calls functions warp_loop and bi_warp_loop. Inputs to warp include the usual file names, image arrays, and line and element coordinates. Inputs specific to warp are the x and y control points and the bilinear parameter. The control points control the warping, and bilinear specifies whether to call function warp_loop, or bi_warp_loop. Both functions perform spatial bi-linear interpolation, but bi_warp_loop throws in an extra gray level bi-linear interpolation step to produce a higher quality image. If bilinear == 0, warp calls warp_loop, otherwise it calls bi_warp_loop.
warp operates on the four quarters of the ROWSxCOLS image section, one quarter at a time. At each quarter, warp sets (x1, y1) through (x4, y4) to the corner coordinates of the quadrilateral formed by the control point, then sets the extra_x and extra_y variables to the upper left-hand corner of the small square associated with that quadrilateral. Setting these variables provides all the information needed to implement equations (6) and (7). warp calls warp_loop for quick warping or bi_warp_loop to use gray-level bi-linear interpolation for a better (albeit slower to complete) image.
Function warp_loop
warp_loop implements equations (6) and (7) to transform a small quadrilateral to a small square. To do so, it sets up the coefficients for the equations — the variables xa, xb, and xab correspond to a, b, and ab from equation (6), and ya, yb, yab correspond to a, b, ab from equation (7). The loops that iterate over i and j calculate the coordinates of the pixels in the input image that will be copied to the output image (x_out and y_out). If x_out or y_out lie outside the ROWSxCOLS array, output_image is set to a FILL value. Otherwise, the output_image pixel is set to the proper pixel from the_image.
bi_warp_loop and Friends
bi_warp_loop performs the same operations as warp_loop; however, bi_warp_loop uses floating-point math and calls the bilinear_interpolate subroutine to set the final output pixel value. Thus, bi_warp_loop produces better results than warp_loop. It also takes more time. I recommend using warp_loop for quick experiments and bi_warp_loop for presentation results.bilinear_interpolate appears as the final routine in Listing 1. I presented this routine in "Geometric Operations" [3] and I repeat the code here for those who may have missed that article.
The top image in Photograph 1 shows some results of control point warping. The
upper left quarter is the input image (a ROWSxCOLS array). The other three quarters show the result of picking a control point inside the ROWSxCOLS array. Repetitive warping can give an object almost any shape you want (windows the shape of circles, triangles, etc.).
Object Warping
A second form of warping is what I call object warping. Instead of picking a control point inside the ROWSxCOLS array, the user picks the four corners of a quadrilateral as shown in Figure 3. Object warping transforms this quadrilateral to a ROWSxCOLS square. The four corners of the quadrilateral can be almost anywhere inside or outside the square. In some ways, object warping is more versatile than control point warping, because control point warping did not support quadrilaterals whose corners were outside the square.Listing 2 shows how CIPS implements object warping. Function object_warp is very similiar to warp; it controls the process and calls either full_warp_loop or bi_full_warp_loop. object_warp's inputs are nearly the same as warp's except object_warp receives the four corners of the quadrilateral (x1, y1 through x4, y4) instead of the control points. The bilinear parameter controls whether object_warp calls full_warp_loop (no gray level bilinear interpolation) or bi_full_warp_loop (gray level bilinear interpolation and floating-point math).
full_warp_loop and bi_full_warp_loop perform the same function as their cousins warp_loop and bi_warp_loop, but the full_warp_loop routines loop over an entire ROWSxCOLS array; the warp_loop routines only go through one quarter of the ROWSxCOLS array.
Again, I recommend full_warp_loop for experiments and bi_full_warp_loop for presentation results.
The bottom image in Photograph 1 shows some results of object warping. The upper left quarter shows the input image with the three other quarters showing results. The results are quite similar to those for control point warping. Note, however, that each result in the bottom image contains FILL values shifted in from outside the ROWSxCOLS square when the starting quadrilateral had corners outside the square.
Photograph 2 shows what you can get by applying warping to a complete image. This image results from control point warping over several ROWSxCOLS arrays in the house's image file.
This photo ought to spark your imagination. I'd say this was a house in the middle of a very bad earthquake. If we made a series of house images, with the control points moving from right to left, we could produce a motion picture that made the house ripple, like it was made of Jell-O. All we would need was a computer fast enough to generate 10,000 images and a motion picture camera. That's how they do it in Hollywood.
Morphing
Morphing is the term most people use today to describe the melting of one object into another. Michael Jackson "morphed" to a panther; A car "morphed" to a tiger. The Mighty Morphin' Power Rangers . . . well that's another story.Morphing occurs as a sequence of images — not a single image. A car becomes a tiger by showing a sequence of intermediate images. The transition appears magical when there are dozens of images shown every second in a film sequence.
Morphing can be done as an extension to warping. Suppose we wanted to morph a dark circle to a bright triangle. The first step is to produce two sequences of images. One sequence warps the dark circle to a dark triangle. The second sequence warps the light triangle to a light circle (Figure 4a) .
The second step is to blend these two sequences into a third sequence. The third sequence is a weighted average of the first two; however, before blending to produce the third sequence we must first reverse one of the previous sequences (Figure 4b) . The third, blended sequence handles the transition from one gray level to the next. If we placed one image of the third sequence in each frame of a motion picture film, we would have a smooth morphing.
Photograph 3 illustrates the process. The objective here is to morph a window to a door. The far left frame of the middle row shows the original window. The far right of the middle row shows the final door.
The top row of Photograph 3 shows how the window warps up to the size and shape of the door, in two steps. I use object warping and with each step pick a quadrilateral smaller than the ROWSxCOLS array. The output of each step is an enlarged window.
The bottom row of photograph 3 shows how the door warps down to the size and shape of the window. Just as I expand the window in two steps, I shrink the door in two corresponding steps, by picking a quadrilateral larger than the ROWSxCOLS array. The output of each step is a smaller door. (However, you must read this bottom sequence from right to left, as I've reversed it here in preparation for blending.)
The three frames in the center of the middle row show the result of a weighted average. (An average is the result of adding two images together and dividing by two. A weighted average is the result of adding an image to itself several times, adding this result to another image, and dividing by <number of additions> + 1.)
The frame closest to the original window results from averaging two shots of the leftmost window from the top row and one shot of the the leftmost door from the bottom row. The frame at dead center is the average of one shot of the middle window and one shot of the middle door. The frame closest to the final door results from averaging two shots of the rightmost door and one shot of the rightmost window.
The sequence of frames in the middle row morph the window to the door. Of course, it would look much nicer had I used a sequence of 3,000 warps and averages instead of three. The procedure is the same, but the more steps between the start and the end, the better the effect.
Applying Warping and Morphing
One application of warping is simple "shearing" of images. Shearing is what you get when push on one side of a flimsy rectangular frame, such as an unbraced scaffold. The top and bottom remain parallel to the ground, while the sides (as well as all verticals) become slanted. In a more severe form of shearing, all four sides become slanted, turning a rectangle into a diamond-like shape (in geometry-speak, a parallelogram). A related article [4] showed how to shear images to make them appear as pages of a turning book. Object warping and bi-linear interpolation can do the same thing without producing jagged lines.I make extensive use of MS-DOS batch files with CIPS. Since CIPS includes a number of stand-alone programs, it's easy to write batch programs to produce shearing, as well as the morphing sequence shown in Photograph 3. This month's code disk includes the batch file that produced Photograph 3. After studying how it works you should be able to produce neat effects of your own.
This month's code disk also contains source code for a stand-alone warp utility. This utility collects command-line arguments and calls the routines described in the preceding article. You can also use it in a batch program.
The professional morphing seen in the movies is hand-tuned by artists, and the sequences are not as straightforward as discussed above. For one thing, artists will take the sequences and manipulate individual pixels so they look just right. They also adjust the weighted averages using more complicated algorithms. In short, the principle is the same, but the professional images reflect the tender loving care put into them. This is a field that calls for tinkering and experimentation.
Summary
This article discussed image warping and morphing. Warping bends or objects in images. Morphing is an extension of warping that melts one object into another, by simultaenously altering shapes and gray levels. Warping is an old technique with its roots in the space program of the 1960's. The ever-increasing power and decreasing price of computers brought these techniques to Hollywood. They are fun. Experiment with them and you can turn brick houses into Jell-O.
References
[1] Kenneth R. Castleman. Digital Image Processing (Prentice-Hall, 1979).[2] Christopher Watkins, Alberto Sadun, Stephen Marenka. Modern Image Processing (Academic Press, 1993).
[3] Dwayne Phillips. "Image Processing, Part 13: Geometric Operations," C/C++ Users Journal, August: 1995, p. 23.
[4] Christopher Dean. "Bitmap Image Transformations," The C Users Journal, December: 1993, pp. 49-70.