“Constant-time filtering with space-variant kernels” by Fournier and Fiume

Filtering is an essential but costly step in many computer graphics applications, most notably in texture mapping. Several techniques have been previously developed which allow prefiltering of a texture (or in general an image) in time that is independent of the number of texture elements under the filter kernel. These are limited, however, to space-invariant kernels whose shape in texture space is the same independently of their positions, and usually are also limited to a small range of filters.We present here a technique that permits constant-time filtering for space-variant kernels. The essential step is to approximate a filter surface in texture space by a sum of suitably-chosen basis functions. The convolution of a filter with a texture is replaced by the weighted sum of the convolution of the basis functions with the texture, which can be precomputed. To achieve constant time, convolutions with the basis functions are computed and stored in a pyramidal fashion, and the right level of the pyramid is selected so that only a constant number of points on the filter kernel need be evaluated.The technique allows the use of arbitrary filters, and as such is useful to explore interesting mappings and special filtering techniques. We give examples of applications to perspective and conformal mappings, and to the use of filters such as gaussians and sinc functions.

1. F.C. Crow, “Summed-Area Tables for Texture Mapping,” Computer Graphics, vol, 18(3), pp. 207-212, July 1984.
2. E. Flume, A. Foumier, and V. Canale, “Conformal Texture Mapping,” Proceedings of Eurographics ’87, pp. 53-64, August 1987. Elsevier Science Publishers (North Holland) (August 24-28, 1987, Amsterdam, The Netherlands).
3. N. Greene and P. S. Heckbert, “Creating Raster Omnimax Images from Multiple Perspective Views Using the Elliptical Weighted Average Filter,” IEEE Computer Graphics and Applications, vol. 6, no. 6, pp. 21-27, June 1986.
4. N. Greene, “Environment Mapping and Other Applications of World Projections,” IEEE Computer Graphics and Applications, vol. 6(11), pp. 21-29, November 1986.
5. P.S. Heckbert, “Filtering By Repeated Integration,” Computer Graphics, vol. 20(4), pp. 315-321, August 1986.
6. P.S. Heckbert, “Survey of Texture Mapping,” IEEE Computer Graphics and Applications, vol. 6(11), pp. 56-67, November 1986.
7. J. Kajiya and M. Ullner, “Filtering High Quality Text for Display on Raster Scan Devices,” Computer Graphics, vol. 15, no. 3, pp. 7-15, 1981. (ACM SIG- GRAPH’81 Conference Proceedings, July 1981, Dallas, Texas)
8. K. Kishimoto, K. Onaga, and E. Nakamae, “Theoretical Assessments of Mean Square Errors of Antialiasing Filters,” Computer Vision, Graphics and Image Processing, vol. 37, pp. 428-437, 1987.
9. A. Naiman and A. Fournier, “Rectangular Convolution for Fast Filtering of Characters,” Computer Graphics, vol. 21, no. 4, pp. 233-242, 1987. (ACM SIG- GRAPH’87 Conference Proceedings, July 27-31, 1987, Anaheim, California).
10. W.K. Pratt, Digital linage Processing, Wiley- Interscience, 1978.
11. L. Williams, “Pyramidal Parametrics,” Computer Graphics, vol. 17(3), pp. 1-11, July 1983.
12. W. Dungan, A. Stenger, and G. Sutty, “Texture Tiles Consideration for Raster Graphics,” Computer Graphics, vol. 12, no. 3, pp. 130-134, 1978. (ACM SIG- GRAPH’78 Conference Proceedings, July 1978, Atlanta, Georgia)
13. E. Catmull and R. Rom, “A Class of Local Interpolating Splines,” in Computer-Aided Geometric Design, ed. R. F. Riesenfeld, pp. 317-326, Academic Press, 1974.
14. A. Rosenfeld and A. C. Kak, Digital Picture Processing, Academic Press, 1976.