Separable image warping with spatial lookup tables

ABSTRACT

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.

REFERENCES

• 1: Ed Catmull , Alvy Ray Smith, 3-D transformations of images in scanline order, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.279-285, July 14-18, 1980, Seattle, Washington, United States
• 2: Robert L. Cook, Stochastic sampling in computer graphics, ACM Transactions on Graphics (TOG), v.5 n.1, p.51-72, Jan. 1986 [doi>10.1145/7529.8927]
• 3: Mark A. Z. Dippé , Erling Henry Wold, Antialiasing through stochastic sampling, ACM SIGGRAPH Computer Graphics, v.19 n.3, p.69-78, Jul. 1985
• 4: Karl M Fant, A nonaliasing, real-time spatial transform technique, IEEE Computer Graphics and Applications, v.6 n.1, p.71-80, Jan.1986 [doi>10.1109/MCG.1986.276613]
• 5: Paul S Heckbert, Survey of texture mapping, IEEE Computer Graphics and Applications, v.6 n.11, p.56-67, November 1986 [doi>10.1109/MCG.1986.276672]
• 6: Don P. Mitchell, Generating antialiased images at low sampling densities, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.65-72, July 1987
• 7: A W Paeth, A fast algorithm for general raster rotation, Proceedings on Graphics Interface '86/Vision Interface '86, p.77-81, August 1986, Vancouver, British Columbia, Canada
• 8: Alvy Ray Smith, Planar 2-pass texture mapping and warping, ACM SIGGRAPH Computer Graphics, v.21 n.4, p.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: Carl F. R. Weiman, Continuous anti-aliased rotation and zoom of raster images, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.286-293, July 14-18, 1980, Seattle, Washington, United States
• 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.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.3 Enhancement
          Subjects: Geometric correction

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.3 Enhancement
          Subjects: Filtering

General Terms:
Algorithms