“Filtering by repeated integration” by Heckbert

Many applications of digital filtering require a space variant filter – one whose shape or size varies with position. The usual algorithm for such filters, direct convolution, is very costly for wide kernels. Image prefiltering provides an efficient alternative. We explore one prefiltering technique, repeated integration, which is a generalization of Crow’s summed area table.We find that convolution of a signal with any piecewise polynomial kernel of degree n–1 can be computed by integrating the signal n times and point sampling it several times for each output sample. The use of second or higher order integration permits relatively high quality filtering. The advantage over direct convolution is that the cost of repeated integration filtering does not increase with filter width. Generalization to two-dimensional image filtering is straightforward. Implementations of the simple technique are presented in both preprocessing and stream processing styles.

1. Bracewell, Ronald N., The Fourier Transform and Its Applications, McGraw-Hill, New York, 1978.
2. Brigham, E. Oran, The Fast Fourier Transform, Prentice-Hall, Englewood Cliffs, N J, 1974. 
3. Catmull, Edwin E., and Raphael Rom, “A Class of Local Interpolating Splines”, Computer Aided Geometric Design, Robert Bamhill and Richard Riesenfeld, eels., Academic Press, New York, 1974, pp. 317-326.
4. Crow, Franklin C., “‘Summed-Area Tables for Texture Mapping”, Cornpuzer Graphics, (SIGGRAPH ’84 Proceedings), vol. 18, no. 3, July 1984, pp. 207-212. 
5. Dungan, William, Jr., Anthony Stenger, and George Sutty, “Texture Tile Considerations for Raster Graphics”, Computer Graphics, (SIGGRAPH ’78 Proceedings), vol. 12, no. 3, Aug. 1978, pp. 130-134. 
6. Feibush, Eliot A., Marc Levoy, and Robert L. Cook, “Synthetic Texturing Using Digital Filters”, Computer Graphics, (SIGGRAPH ’80 Proceedings), vol. 14, no. 3, July 1980, pp. 294-301. 
7. Goldman, Ronald N., “‘An Urnful of Blending Functions”, IEEE Computer Graphics and Applications, vol. 3, Oct. 1983, pp. 49-54.
8. Gordon, William J., and Richard F. Riesenfeld, “B-spline Curves and Surfaces”, Computer Aided Geometric Design, Robert Bamhitl and Richard Riesenfeld, eds., Academic Press, New York, 1974, pp. 95-126.
9. Greene, Ned, and Paul S. Heckbert, “Creating Raster Omnimax Images from Multiple Perspective Views Using The Elliptical Weighted Average Filter”, Compater Graphics and Appticalions, June 1986. 
10. Heckbert, Paul S., “Survey of Texture Mapping”, Graphics ,rnterface ’86, May 1986. 
11. Hou, Hsieh S., and Harry C. Andrews, “Cubic SpiNes for linage Interpolation and Digital Filtering”, IEEE Trans. Acoustics, Speech, and Signal Processing, vol. ASSP-26, no. 6, Dec. 1978, pp. 508-517.
12. Lavoie, J. L., Thomas I. Osler, and R. Tremblay, “Fractional Derivatives of Special Functions”, SIAM Review, vol. 18, pp. 240-268, 1976.
13. Papoulis, R., The Fourier Integral and its Applications, McGraw-Hill, New York, 1962.
14. Park, Stephen K., and Robert A. Schowengerdt, “Image Reconstruction by Parametxic Cubic ConvoIution”, Computer Vision, Graphics, and Image Processing. vo1.23, no. 3, Sept. 1983, pp. 258-272.
15. Perlin, Kenneth, personal communication, Jan. 1984.
16. Perlin, Kenneth, “Course Notes”, SIGGRAPH ’85 State of the Art in Image Synthesis seminar notes, July 1985.
17. Rosenfeld, A., Multiresolufion Image Processing and Analysis, Leesberg, VA, Springer, Berlin, 1984.
18. Schoenberg, I. J., “Contributions to the Problem of Approximation of Equidistant Data by Analytic Functions”, Quart. Applied Mazh, vol. 4, 1946, pp. 45-99, 112-14I.
19. Schowengerdt, Robert A., Techniques for Image Processing and Classification in Remote Sen.zing, Academic Press, New York/London, 1983.
20. Williams, Lance, “Pyramidal P~rametrics”, Computer Graphics, (SIG- GRAPH ’83 proceedings), vol. 17, no. 3, July 1983, pp. 1-11.