Digital Image Warping / Edition 1 available in Paperback
- ISBN-10:
- 0818689447
- ISBN-13:
- 9780818689444
- Pub. Date:
- 08/10/1990
- Publisher:
- Wiley
Paperback
Buy New
$136.95Buy Used
$82.10-
-
SHIP THIS ITEM
Temporarily Out of Stock Online
Please check back later for updated availability.
-
Overview
About the Author
Read an Excerpt
Digital Image Warping
By George Wolberg
John Wiley & Sons
ISBN: 0-8186-8944-7Chapter One
INTRODUCTION
1.1. BACKGROUND
Digital image warping is a growing branch of image processing that deals with the geometric transformation of digital images. A geometric transformation is an operation that redefines the spatial relationship between points in an image. Although image warping often tends to conjure up notions of highly distorted imagery, a warp may range from something as simple as a translation, scale, or rotation, to something as elaborate as a convoluted transformation. Since all warps do, in fact, apply geometric transformations to images, the terms "warp" and "geometric transformation" are used interchangeably throughout this book.
It is helpful to interpret image warping in terms of the following physical analogy. Imagine printing an image onto a sheet of rubber. Depending on what forces are applied to that sheet, the image may simply appear rotated or scaled, or it may appear wildly distorted, corresponding to the popular notion of a warp. While this example might seem to portray image warping as a playful exercise, image warping does serve an important role in many applied sciences. Over the past twenty years, for instance, image warping has been the subject of considerable attention in remote sensing, medical imaging, computer vision, and computer graphics. It has made its way into many applications, including distortion compensation of imaging sensors, decalibration for image registration, geometrical normalization for image analysis and display, map projection, and texture mapping for image synthesis.
Historically, geometric transformations were first performed on continuous (analog) images using optical systems. Early work in this area is described in [Cutrona 60], a landmark paper on the use of optics to perform transformations. Since then, numerous advances have been made in this field [Horner 87]. Although optical systems offer the distinct advantage of operating at the speed of light, they are limited in control and flexibility. Digital computer systems, on the other hand, resolve these problems and potentially offer more accuracy. Consequently, the algorithms presented in this book deal exclusively with digital (discrete) images.
The earliest work in geometric transformations for digital images stems from the remote sensing field. This area gained attention in the mid-1960s, when the U.S. National Aeronautics and Space Administration (NASA) embarked upon aggressive earth observation programs. Its objective was the acquisition of data for environmental research applicable to earth resource inventory and management. As a result of this initiative, programs such as Landsat and Skylab emerged. In addition, other government agencies were supporting work requiring aerial photographs for terrain mapping and surveillance.
These projects all involved acquiring multi-image sets (i.e., multiple images of the same area taken either at different times or with different sensors). Immediately, the task arises to align each image with every other image in the set so that all corresponding points match. This process is known as image registration. Misalignment can occur due to any of the following reasons. First, images may be taken at the same time but acquired from several sensors, each having different distortion properties, e.g., lens aberration. Second, images may be taken from one sensor at different times and at various viewing geometries. Furthermore, sensor motion will give rise to distortion as well.
Geometric transformations were originally introduced to invert (correct) these distortions and to allow the accurate determination of spatial relationships and scale. This requires us to first estimate the distortion model, usually by means of reference points which may be accurately marked or readily identified (e.g., road intersections and landwater interface). In the vast majority of cases, the coordinate transformation representing the distortion is modeled as a bivariate polynomial whose coefficients are obtained by minimizing an error function over the reference points. Usually, a second-order polynomial suffices, accounting for translation, scale, rotation, skew, and pincushion effects. For more local control, affine transformations and piecewise polynomial mapping functions are widely used, with transformation parameters varying from one region to another. See [Haralick 76] for a historical review of early work in remote sensing.
An example of the use of image warping for geometric correction is given in Figs. 1.1 and 1.2. Figure 1.1 shows an example of an image distorted due to viewing geometry. It was recorded after the Viking Lander 2 spacecraft landed on Mars in September 1976. A cylindrical scanner was used to acquire the image. Since the spacecraft landed with an 8° downward tilt, the level horizon appears curved. This problem is corrected in Fig. 1.2, which shows the same image after it was rectified by a transformation designed to remove the tilt distortion.
The methods derived from remote sensing have direct application in other related fields, including medical imaging and computer vision. In medical imaging, for instance, geometric transformations play an important role in image registration and rotation for digital radiology. In this field, images obtained after injection of contrast dye are enhanced by subtracting a mask image taken before the injection. This technique, known as digital subtraction angiography, is subject to distortions due to patient motion. Since motion causes misalignment of the image and its subtraction mask, the resulting produced images are degraded. The quality of these images is improved with transformation algorithms that increase the accuracy of the registration.
Image warping is a problem that arises in computer graphics as well. However, in this field the goal is not geometric correction, but rather inducing geometric distortion. Graphics research has developed a distinct repertoire of techniques to deal with this problem. The primary application is texture mapping, a technique to map 2-D images onto 3-D surfaces, and then project them back onto a 2-D viewing screen. Texture mapping has been used with much success in achieving visually rich and complicated imagery. Furthermore, additional sophisticated filtering techniques have been promoted to combat artifacts arising from the severe spatial distortions possible in this application. The thrust of this effort has been directed to the study and design of efficient spatially-varying lowpass filters. Since the remote sensing and medical imaging fields have generally attempted to correct only mild distortions, they have neglected this important area. The design of fast algorithms for filtering fairly general areas remains a great challenge.
Image warping is commonly used in graphics design to create interesting visual effects. For instance, Fig. 1.3 shows a fascinating sequence of warps that depicts a transformation between two faces, a horse and rider, two frogs, and two dancers. Other examples of such applications include the image sequence shown on the front cover, as well as other effects described in [Holzmann 88].
The continuing development of efficient algorithms for digital image warping has gained impetus from the growing availability of fast and cost-effective digital hardware. The ability to process high resolution imagery has become more feasible with the advent of fast computational elements, high-capacity digital data storage devices, and improved display technology. Consequently, the trend in algorithm design has been towards a more effective match with the implementation technology. This is reflected in the recent surge of warping products that exploit scanline algorithms.
It is instructive at this point to illustrate the relationship between the remote sensing, medical imaging, computer vision, and computer graphics fields since they all have ties to image warping. As stated earlier, image warping is a subset of image processing. These fields are all connected to image warping insofar as they share a common usage for image processing. Figure 1.4 illustrates these links as they relate to images and mathematical scene descriptions, the two forms of data used by the aforementioned fields.
Consider the transition from a scene description to an image, as shown in Fig. 1.4. This is a function of a Tenderer in computer graphics. Although image processing is often applied after rendering, as a postprocess, those rendering operations requiring proper filtering actually embed image processing concepts directly. This is true for warping applications in graphics, which manifests itself in the form of texture mapping. As a result, texture mapping is best understood as an image processing problem.
The transition from an input image to an output image is characteristic of image processing. Image warping is thereby considered an image processing task because it takes an input image and applies a geometric transformation to yield an output image. Computer vision and remote sensing, on the other hand, attempt to extract a scene description from an image. They use image registration and geometric correction as preliminary components to pattern recognition. Therefore, image warping is common to these fields insofar as they share images which are subject to geometric transformations.
1.2. OVERVIEW
The purpose of this book is to describe the algorithms developed in this field within a consistent and coherent framework. It centers on the three components that comprise all geometric transformations in image warping: spatial transformations, resampling, and antialiasing. Due to the central importance of sampling theory, a review is provided as a preface to the resampling and antialiasing chapters. In addition, a discussion of efficient scanline implementations is given as well. This is of particular importance to practicing scientists and engineers.
In this section, we briefly review the various stages in a geometric transformation. Each stage has received a great deal of attention from a wide community of people in many diverse fields. As a result, the literature is replete with varied terminologies, motivations, and assumptions. A review of geometric transformation techniques, particularly in the context of their numerous applications, is useful for highlighting the common thread that underlies their many forms. Since each stage is the subject of a separate chapter, this review should serve to outline the contents of this book. We begin with some basic concepts in spatial transformations.
1.2.1. Spatial Transformations
The basis of geometric transformations is the mapping of one coordinate system onto another. This is defined by means of a spatial transformation - a mapping function that establishes a spatial correspondence between all points in the input and output images. Given a spatial transformation, each point in the output assumes the value of its corresponding point in the input image. The correspondence is found by using the spatial transformation mapping function to project the output point onto the input image.
Depending on the application, spatial transformation mapping functions may take on many different forms. Simple transformations may be specified by analytic expressions including affine, projective, bilinear, and polynomial transformations. More sophisticated mapping functions that are not conveniently expressed in analytic terms can be determined from a sparse lattice of control points for which spatial correspondence is known. This yields a spatial representation in which undefined points are evaluated through interpolation. Indeed, taking this approach to the limit yields a dense grid of control points resembling a 2-D spatial lookup table that may define any arbitrary mapping function.
In computer graphics, for example, the spatial transformation is completely specified by the parameterization of the 3-D object, its position with respect to the 2-D projection plane (i.e., the viewing screen), viewpoint, and center of interest. The objects are usually defined as planar polygons or bicubic patches. Consequently, three coordinate systems are used: 2-D texture space, 3-D object space, and 2-D screen space. The various formulations for spatial transformations, as well as methods to infer them, are discussed in Chapter 3.
1.2.2. Sampling Theory
In the continuous domain, a geometric transformation is fully specified by the spatial transformation. This is due to the fact that an analytic mapping is bijective - one-to-one and onto. However, in our domain of interest, complications are introduced due to the discrete nature of digital images. Undesirable artifacts can arise if we are not careful. Consequently, we turn to sampling theory for a deeper understanding of the problem at hand.
Sampling theory is central to the study of sampled-data systems, e.g., digital image transformations. It lays a firm mathematical foundation for the analysis of sampled signals, offering invaluable insight into the problems and solutions of sampling. It does so by providing an elegant mathematical formulation describing the relationship between a continuous signal and its samples. We use it to resolve the problems of image reconstruction and aliasing. Note that reconstruction is an interpolation procedure applied to the sampled data and that aliasing simply refers to the presence of unreproducibly high frequencies and the resulting artifacts.
Together with defining theoretical limits on the continuous reconstruction of discrete input, sampling theory yields the guidelines for numerically measuring the quality of various proposed filtering techniques. This proves most useful in formally describing reconstruction, aliasing, and the filtering necessary to combat the artifacts that may appear at the output. The fundamentals of sampling theory are reviewed in Chapter 4.
1.2.3. Resampling
Once a spatial transformation is established, and once we accommodate the subtleties of digital filtering, we can proceed to resample the image. First, however, some additional background is in order.
In digital images, the discrete picture elements, or pixels, are restricted to lie on a sampling grid, taken to be the integer lattice. The output pixels, now defined to lie on the output sampling grid, are passed through the mapping function generating a new grid used to resample the input. This new resampling grid, unlike the input sampling grid, does not generally coincide with the integer lattice. Rather, the positions of the grid points may take on any of the continuous values assigned by the mapping function.
Since the discrete input is defined only at integer positions, an interpolation stage is introduced to fit a continuous surface through the data samples. The continuous surface may then be sampled at arbitrary positions. This interpolation stage is known as image reconstruction. In the literature, the terms "reconstruction" and "interpolation" are used interchangeably. Collectively, image reconstruction followed by sampling is known as image resampling.
Image resampling consists of passing the regularly spaced output grid through the spatial transformation, yielding a resampling grid that maps into the input image. Since the input is discrete, image reconstruction is performed to interpolate the continuous input signal from its samples. Sampling the reconstructed signal gives us the values that are assigned to the output pixels.
The accuracy of interpolation has significant impact on the quality of the output image. As a result, many interpolation functions have been studied from the viewpoints of both computational efficiency and approximation quality. Popular interpolation functions include cubic convolution, bilinear, and nearest neighbor. They can exactly reconstruct second-, first-, and zero-degree polynomials, respectively. More expensive and accurate methods include cubic spline interpolation and convolution with a sine function. Using sampling theory, this last choice can be shown to be the ideal filter. However, it cannot be realized using a finite number of neighboring elements. Consequently, the alternate proposals have been given to offer reasonable approximations. Image resampling and reconstruction are described in Chapter 5.
(Continues...)
Excerpted from Digital Image Warping by George Wolberg Excerpted by permission.
All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.
Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site.