Wavelets for Computer graphics: A Primer Part 1t Eric J. Stollnitz Tony D. De rose David H Salesin University of Washington 1 Introduction We can represent this image in the Haar basis by com wavelet transform. To do this, we first average the pixels together Wavelets are a mathematical tool for hierarchically decomposing pairwise, to get the new lower resolution image with pixel values functions. They allow a function to be described in terms of a coarse overall shape plus details that range from broad to narrow. Regard 84 ess of whether the function of interest is an image, a curve, or sur face, wavelets offer an elegant technique for representing the levels of detail present. This primer is intended to provide people work Clearly some information ha lost in this averaging process n computer graphics with some intuition for what wavelets are, as To recover the original four ues from the two averaged val well as to present the mathematical foundations necessary for study ues. we need to store some coefficients, which capture the ing and using them. In Part 1, we discuss the simple case of Haar missing information. In our we will choose i for the fi wavelets in one and two dimensions, and show how they can be used detail coefficient, since the average we computed is I less than 9 for image compression. In Part 2, we will present the mathematical nd I more than 7. This single number allows us to recover the first theory of multiresolution analysis, then develop spline wavelets and two pixels of our original four-pixel image. Similarly, the second describe their use in multiresolution curve and surface editing detail coefficient is-1, since 4+(1)=3 and 4-(1)=5 Although wavelets have their roots in approximation theory [5]and Thus, we have decomposed the original image into a lower resolu- signal processing [13], they have recently been applied to many tion( two-pixel) version and a pair of detail coefficients. Repeating clude image editing [1], image compression [6, and image query tion: ing [10] automatic level-of-detail control for editing and render ing curves and surfaces [7, 8, 12]; surface reconstruction from con- Resolution A Detail coefficients tours[14]; and fast methods for solving simulation problems in ani- mation [11]and global illumination 3, 4, 9, 15]. For a discussion of wavelets that goes beyond the scope of this primer, we refer readers he stage here by first presenting the simplest form of imensional wavelet trans basis functions, and show how these tools can be used to Finally, we will define the wavelet transform(also called the wavelet the representation of a piecewise-constant function. Then decomposition)of the original four-pixel image to be the single ss two-dimensional generalizations of the Haar basis, and efficient representing the overall average of the original image, fol- demonstrate how to apply these wavelets to image compression lowed by the detail coefficients in order of increasing resolution Because linear algebra is central to the mathematics of wavelets, we Thus. for the one-dimensional Haar basis, the wavelet transform of briefly review important concepts in Appendix A our original four-pixel image is given by 「62 2 Wavelets in one dimension The haar the simplest wavelet basis. We will first discuss The way we computed the wavelet transform, by recursively aver- ow a on describe the actual basis functions. Finally, we we will generalize to other types of wavelets in Part 2 of show how using the Haar wavelet decomposition leads to a straight- rial. Note that no information has been gained or lost by this forward technique for compressing a one-dimensional function. The original image had four coefficients, and so does the transform. Also note that, given the transform, we can reconstruct the image to any resolution by recursively adding and subtracting the detail 2.1 One-dimensional Haar wavelet transform efficients from the lower resolution versions To get a sense for how wavelets work, let s start with a simple exam- Storing the image' s wavelet transform, rather than the image itself, ple. Suppose we are given a one-dimensional "image"with a reso- has a number of advantages. One advantage of the wavelet trans lution of four pixels, having values form is that often a large number of the detail coefficients turn out to be very small in magnitude, as in the example of Figure 1. Trun- 9735 cating, or removing, these small coefficients from the representa- tion introduces only small errors in the reconstructed iter graphics: A primer, part 1. IEEE Computer Grap avelets for com- a form of"lossy"image compression. We will discuss this particu- ics and Applica- lar application of wavelets in Section 2.3, after we present the one- lIonS,,15(3):76-84,May1995 dimensional haar basis functionsWavelets for Computer Graphics: A Primer Part 1y Eric J. Stollnitz Tony D. DeRose David H. Salesin University of Washington 1 Introduction Wavelets are a mathematical tool for hierarchically decomposing functions. They allow a function to be described in terms of a coarse overall shape, plus details that range from broad to narrow. Regard￾less of whether the function of interest is an image, a curve, or a sur￾face, wavelets offer an elegant technique for representing the levels of detail present. This primer is intended to provide people working in computer graphics with some intuition for what wavelets are, as well as to present the mathematical foundations necessary for study￾ing and using them. In Part 1, we discuss the simple case of Haar wavelets in one and two dimensions, and show how they can be used for image compression. In Part 2, we will present the mathematical theory of multiresolution analysis, then develop spline wavelets and describe their use in multiresolution curve and surface editing. Although wavelets have their roots in approximation theory [5] and signal processing [13], they have recently been applied to many problems in computer graphics. These graphics applications in￾clude image editing [1], image compression [6], and image query￾ing [10]; automatic level-of-detail control for editing and render￾ing curves and surfaces [7, 8, 12]; surface reconstruction from con￾tours [14]; and fast methods for solving simulation problems in ani￾mation [11] and global illumination [3, 4, 9, 15]. For a discussion of wavelets that goes beyond the scope of this primer, we refer readers to our forthcoming monograph [16]. We set the stage here by first presenting the simplest form of wavelets, the Haar basis. We cover one-dimensional wavelet trans￾forms and basis functions, and show how these tools can be used to compress the representation of a piecewise-constant function. Then we discuss two-dimensional generalizations of the Haar basis, and demonstrate how to apply these wavelets to image compression. Because linear algebra is central to the mathematics of wavelets, we briefly review important concepts in Appendix A. 2 Wavelets in one dimension The Haar basis is the simplest wavelet basis. We will first discuss how a one-dimensional function can be decomposed using Haar wavelets, and then describe the actual basis functions. Finally, we show how using the Haar wavelet decomposition leads to a straight￾forward technique for compressing a one-dimensional function. 2.1 One-dimensional Haar wavelet transform To get a sense for how wavelets work, let’s start with a simple exam￾ple. Suppose we are given a one-dimensional “image” with a reso￾lution of four pixels, having values 9 7 3 5 y Eric J. Stollnitz, Tony D. DeRose, and David H. Salesin. Wavelets for com￾puter graphics: A primer, part 1. IEEE Computer Graphics and Applica￾tions, 15(3):76–84, May 1995. We can represent this image in the Haar basis by computing a wavelet transform. To do this, we first average the pixels together, pairwise, to get the new lower resolution image with pixel values 8 4 Clearly, some information has been lost in this averaging process. To recover the original four pixel values from the two averaged val￾ues, we need to store some detail coefficients, which capture the missing information. In our example, we will choose 1 for the first detail coefficient, since the average we computed is 1 less than 9 and 1 more than 7. This single number allows us to recover the first two pixels of our original four-pixel image. Similarly, the second detail coefficient is ￾1, since 4 + (￾1) = 3 and 4 ￾ (￾1) = 5. Thus, we have decomposed the original image into a lower resolu￾tion (two-pixel) version and a pair of detail coefficients. Repeating this process recursively on the averages gives the full decomposi￾tion: Resolution Averages Detail coefficients 4 9 7 3 5 2 8 4 1 ￾1 1 6 2 Finally, we will define thewavelet transform (also called thewavelet decomposition) of the original four-pixel image to be the single co￾efficient representing the overall average of the original image, fol￾lowed by the detail coefficients in order of increasing resolution. Thus, for the one-dimensional Haar basis, the wavelet transform of our original four-pixel image is given by 6 2 1 ￾1 The way we computed the wavelet transform, by recursively aver￾aging and differencing coefficients, is called afilter bank—a process we will generalize to other types of wavelets in Part 2 of our tuto￾rial. Note that no information has been gained or lost by this process. The original image had four coefficients, and so does the transform. Also note that, given the transform, we can reconstruct the image to any resolution by recursively adding and subtracting the detail co￾efficients from the lower resolution versions. Storing the image’s wavelet transform, rather than the image itself, has a number of advantages. One advantage of the wavelet trans￾form is that often a large number of the detail coefficients turn out to be very small in magnitude, as in the example of Figure 1. Trun￾cating, or removing, these small coefficients from the representa￾tion introduces only small errors in the reconstructed image, giving a form of “lossy” image compression. We will discuss this particu￾lar application of wavelets in Section 2.3, after we present the one￾dimensional Haar basis functions.