Filtering by repeated integration

ABSTRACT

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.

REFERENCES

• 1: Bracewell, Ronald N., The Fourier Transform and Its Applications, McGraw-Hill, New York, 1978.
• 2: E. Oran Brigham, The fast Fourier transform and its applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1988
• 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: Franklin C. Crow, Summed-area tables for texture mapping, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.207-212, January 1984
• 5: William Dungan, Jr. , Anthony Stenger , George Sutty, Texture tile considerations for raster graphics, Proceedings of the 5th annual conference on Computer graphics and interactive techniques, p.130-134, August 23-25, 1978
• 6: Eliot A. Feibush , Marc Levoy , Robert L. Cook, Synthetic texturing using digital filters, Proceedings of the 7th annual conference on Computer graphics and interactive techniques, p.294-301, July 14-18, 1980, Seattle, Washington, United States
• 7: Goldman, Ronald N., "'An Umful 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: Ned Greene , Paul S. Heckbert, Creating raster Omnimax images from multiple perspective views using the elliptical weighted average filter, IEEE Computer Graphics and Applications, v.6 n.6, p.21-27, June 1986 [doi>10.1109/MCG.1986.276738]
• 10: P S Heckbert, Survey of texture mapping, Proceedings on Graphics Interface '86/Vision Interface '86, p.207-212, August 1986, Vancouver, British Columbia, Canada
• 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: Lance Williams, Pyramidal parametrics, Proceedings of the 10th annual conference on Computer graphics and interactive techniques, p.1-11, July 25-29, 1983, Detroit, Michigan, United States

INDEX TERMS

Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation
          Subjects: Display algorithms
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.3 Enhancement
          Subjects: Filtering

General Terms:
Algorithms, Theory