“Antialiasing through stochastic sampling” by Wold and Dippe

  • ©Erling Henry Wold and Mark Dippe




    Antialiasing through stochastic sampling



    Stochastic sampling techniques, in particular Poisson and fittered sampling, are developed and analyzed. These approaches allow the construction of alias-free approximations to continuous functions using discrete calculations. Stochastic sampling scatters high frequency information into broadband noise rather than generating the false patterne produced by regular sampling. The type of randomness used in the sampling process controls the spectral character of the noise. The average sampling rate and the function being sampled determine the amount of noise that is produced. Stochastic sampling is applied adaptively so that a greater number of samples are taken where the function varies most. An estimate is used to determine how many samples to take over a given region. Noise reducing filters are used to increase the efficacy of a given sampling rate. The filter width is adaptively controlled to further improve performance. Stochastic sampling can be applied spatiotemporally as well as to other aspects of scene simulation. Ray tracing is one example of an image synthesis approach that can be antialiased by stochastic sampling.


    1. Andreas Antoniou, Digital Filters: Anal$lsis and Design, McGraw-Hill Book Company, New York (1979).
    2. J.G. Ballard, Crash, Jonathan Cape Ltd., Great Britain (1973).
    3. J.M. Barstow and H. N. Christopher, “The Measurement of Random Monochrome Video Interference,” Transactions oi” the American Institute of Electrical Engineers 72 pp. 735- 74~. (195a1.
    4. Frederick J. Beutler, “Alias-Free Randomly Timed Sampling of Stochastic Processes,” IEEE Transactions on Information Theory ITolII(2)pp. 147-152. (March, 1970).
    5. F.C. Billingsley, Noise Considerations in Digital Image Processing Hardware, Springer-Verlag, New York (1975).
    6. Ronald N. Bracewell, The Fourier Transform and Its Application, MeGraw-ttill Book Company, New York (1965).
    7. William M. Brown, “Sampling with Random Jitter,” Journal Society Industrial Applied Mathematics (SIAM} 11{2} pp. 460-473. (June, 1963).
    8. Robert L. Cook, Thomas Porter, and Loren Carpenter, “Distributed Ray Tracing,” pp. 137-146 in SIGGRAPH ‘8~ Conference Proceedings, ACM {July, 1984).
    9. Franklin C. Crow, “A Comparison of Antialiasing Techniques,” IEEE Cvmputer Graphics and Applications 1(1) pp. 40-48. {January, 1981).
    10. Mark A. g. Dipp~ and Erling Henry Wold, Stochaetic Sampling: Theory and Application, Report, University of California, Berkeley, California {1985}. To appear.
    11. Mark E. Dipp~ and John A. Swensen, “An Adaptive Subdivision Algorithm and Parallel Architecture for Realistic Image Synthesis,” pp. 149-158 in SIGGRAPH ‘8~ Conference Proceedings, ACM, Minneapolis {July 23-27, 1984).
    12. Thomas S. Huang, “The Subjective Effect of Two-Dimensional Pictorial Noise,” IEEE Transactions on ln form~tion Theory ITolI(1) pp. 43-53. (January, 1965).
    13. H.B. Kekre, S. C. Sahasrabudhe, alrd N. C. Goyal, “Raised Cosine Function for Image Restoration,” Signal Processin9 S pp. 61-73. (1983),
    14. Donald E. Knuth, The Art of Computer Programming: Volume e, Seminumerical Algorithms, Addison-Wesley Publishing Company, Reading, Massachusetts (1969).
    15. Oscar A. Z. Leneman, Stationary Point Processes and Their Application to Random Sampling of Stochastic Processes, Ph.D. Thesis, University of Michigan, Ann Arbor (1964).
    16. Oscar A. Z. Leneman, “Random Sampling of Random Processes: Impulse Response,” Information and Control @ pp. 347-363. {1966).
    17. Elias Masry, “Alias-Free Sampling: An Alternative Conceptualization and Its Applications,” IEEE Transactions on information Theory ITo24(3) pp. 317-324. {May, 1978).
    18. Athanasios Papoul/s, Probability, Random Variables, and Stochaetic Processes, McGraw-Hill Book Company, Inc., New York (1965).
    19. Daniel P. Petersen and David Middleton, “Sampling and Reconstruction of Wave-Number-Limited Functions in N- Dimensional Eaclidean Spaces,” Information and Control 5~4)iDecember, 1962).
    20. Lawrence Gilman Roberts, “Picture Coding Using Pseudo- Random Noise,” IRE Transactions on Information Theory 1″I”-812) pp. 145-154. (February, 1962).
    21. P.F. Scott, Distortion and Estimation of the Autoeorrelation Function and Spectrum of a Randomly Sampled Signal, Ph.D. Thesis, Rennselaer Polytechnic Institute, Troy, New York (June, 1976}. Also published as General Electric Company technical report 76CRD180, Schenectady, N. Y., 1976.
    22. Harold S. Shapiro and Richard A. Silverman, “Alias-Free Sampling of Random Noise,” SIAM Journal 8{2)pp. 225-248. ( June, 1960).
    23. Yu. A. Shreider, The Monte Carlo Method, Pergamon Press, New York (1966).
    24. Robert Siegel and John R. Howell, Thermal Radiation Heat Transfer, McGraw-Hill Book Company, New York (1981). Second edition.
    25. H. Stark, “Diffraction Patterns of Nonoverlapping Circular Grains,” Journal of the Optical Society of America ~7(51 pp. 700-703. (May, 1977).
    26. Thomas G. Stockham, Jr., “Image Processing in the Context of a Visual Model,” Proceedings of the {EEE, Special Issue on Image Proceesing 00{7) pp. 828-842. (July, 1972).
    27. Ferrel G. Stremler, Introduction to Communication Systems, Addizon-Wesley , Reading, Mass. (1977).
    28. J. Turner Whitted, “An Improved Illumination Model for Shaded Display,” Communications of the ACM Z3{6)pp. 343-349. (June, 1980).
    29. N. Wiener, The Extrapolation, Interpolation and Smoothing of Stationary Time Series, John Wiley & Sons, Inc., New York (1949).
    30. John I. Yellott, “Spectral Analysis of Spatial Sampling by Photoreeeptors: Topological Disorder Prevents Alia.sing,” Vision Reoearch ~II pp. 1205-1210. (1982).
    31. John I. Yellott, “Nonhomogeneous Poisson Disks Model the Photoreceptor Mosaic (Abstract),” investigative Ophthalmology and Visual Science (Supplement)Z4(3)(March, 1083).

ACM Digital Library Publication:

Overview Page: