Separable image warping: implications and techniques
George Wolberg · 1991
Image warping is a geometric transformation that redefines the spatial relationship between points in an image. This facilitates the manipulation of an image's spatial layout, i.e., its size and shape. Image warping has benefited from dramatic developments in separable geometric transformation algorithms, methods which reduce a 2-D resampling problem into a sequence of 1-D (scanline) resampling operations. Despite the great contributions of separable algorithms, particularly the 2-pass approach, there are a number of problems that limit their usefulness. In particular, there exists the bottleneck and foldover problems. These difficulties, which can result in visual artifacts and costly memory requirements, are addressed in this thesis. A new 2-pass algorithm which properly handles the bottleneck and foldover problems is introduced. We demonstrate that all geometric transformations can be realized with the novel 2-pass warping algorithm derived herein. This extends the benefits of 2-pass transformations to efficiently process arbitrary spatial mappings--geometric transformations that, until now, required costly resampling operations. This thesis demonstrates that a simple shading algorithm coupled with low-order polynomial interpolation effectively reduces the cost of evaluating the spatial transformation for perspective mappings in real-time texture mapping applications. A novel algorithm is also introduced for realizing mappings among arbitrary planar shapes. This is useful for applications in which the correspondence between two images is known only along their boundaries. This method extends the method of polar coordinate transformations by using the symmetric axis, or skeleton, as a means of handling the difficulties presented by non star-shaped figures. This thesis also presents a new class of image models and reconstruction algorithms. We first show that current models of digital image reconstruction have a significant shortcoming for the problems of geometric transformations: they do not satisfy an important (and intuitive) imaging identity criterion. This is a product of appoximating the ideal low-pass filter prior to sampling. We describe functional image models which are symbolically integrated for image reconstruction. We then develop and analyze some new image models which, when integrated, do have the desired properties, and also give visually pleasing results.