“Separable image warping with spatial lookup tables” by Wolberg and Boult

Image warping refers to the 2-D resampling of a source image onto a target image. In the general case, this requires costly 2-D filtering operations. Simplifications are possible when the warp can be expressed as a cascade of orthogonal 1-D transformations. In these cases, separable transformations have been introduced to realize large performance gains. The central ideas in this area were formulated in the 2-pass algorithm by Catmull and Smith. Although that method applies over an important class of transformations, there are intrinsic problems which limit its usefulness.The goal of this work is to extend the 2-pass approach to handle arbitrary spatial mapping functions. We address the difficulties intrinsic to 2-pass scanline algorithms: bottlenecking, foldovers, and the lack of closed-form inverse solutions. These problems are shown to be resolved in a general, efficient, separable technique, with graceful degradation for transformations of increasing complexity.

1. CatmuU, E. and A.R. Smith, “3-D Transformations of Images in Scanline Order,” Computer Graphics, (SIGGRAPH ’80 Proceedings), vol. 14, no. 3, pp. 279-285, July 1980.
2. Cook,’ R.L., “Stochastic Sampling in Computer Graphics,” ACM Trans. on Graphics, vol. 5, no. 1, pp. 51-72, January 1986.
3. Dippe, M.A.Z and E.H. Wold, “Antialiasing Through Stochastic Sampling,” Computer Graphics, (SIGGRAPH ’85 Proceedings), vol. 19, no. 3, pp. 69-78, July 1985.
4. Fant, K.M., “A Nonaliasing, Real-Time Spatial Transform Technique,” IEEE Computer Graphics and Applications, vol. 6, no. 1, pp. 71-80, January 1986.
5. Heckbert, P., “Survey of Texture Mapping,” IEEE Computer Graphics and Applications, vol. 6, no. 11, pp. 56-67, November 1986.
6. Mitchell, D., “Generating Antialiased Images at Low Sampling Densities,” Computer Graphics, (SIGGRAPH ’87 Proceedings), vol. 21, no. 4, pp. 65-72, July 1987.
7. Paeth, A.W., “A Fast Algorithm for General Raster Rotation,” Graphics Interface ’86, pp. 77-81, May 1986.
8. Smith, A.R., “Planar 2-Pass Texture Mapping and Warping,” Computer Graphics, (SIGGRAPH ’87 Proceedings), vol. 21, no. 4, pp. 263-272, July 1987.
9. Tanaka, A., M. Kameyama, S. Kazama, and O. Watanabe, “A Rotation Method for Raster image Using Skew Transformation,” Proc. IEEE Conference on Computer Vision and Pattern Recognition, pp. 272-277, June 1986.
10. Weiman, C.F.R., “Continuous Anti-Aliased Rotation and Zoom of Raster Images,” Computer Graphics, (SIGGRAPH ’80 Proceedings), vol. 14, no. 3, pp. 286-293, July 1980.
11. Wolberg, G., “Geometric Transformation Teehniques for Digital Images: A Survey,” Columbia University Computer Science Tech. Report CUCS-390-88, December 1988. To appear as a monograph by IEEE Computer Society Press.