Wavelets for Computer graphics: A Primer Part 2 EricJ. StolInitz Tony D Derose David H salesin University of Washington 1 Introduction It is often convenient to put the different scaling functions d(x)for a given level j together into a single row matrix, Wavelets are a mathematical tool (x)]. verall shape plus detai ess of whether the func a curve or a where nr is the dimension of y. We can do the same for the surface, wavelets provid levels of detail present y,(x)I In Part I of this primer we discu simple case of Haar wavelets in one and two dimensions, and showed how they can be If is the dimension of w. Because wd is the orthogonal com- used for image compression. In Part 2, we present the mathematical theory of multiresolution analysis, then develop bounded-interval nt of in pr, the dimensions of these spaces satisfy m spline wavelets and describe their use in multiresolution curve and surface editing The condition that the subs ted is equivalent to requir ing that the scaling function That is, forall=1, 2 there must exist a matrix 2 Multiresolution analysis The Haar wavelets we discussed in Part I are just one of many bases that can be used to treat functions in a hierarchical fashion In this each scaling function at levelj-l must l ection, we develop a mathematical framework known as multires combination of“ finer” scaling function olution analysis for studying wavelets [2, 11]. Our examples will w and J-I have dimensions m and m- 学 continue to focus on the Haar basis, but the more general mathe- tively, P is an mr x m-matrix(taller than it is wide) matical notation used here will come in handy for discussing other wavelet bases in later sections ince the wavelet space w- is by definition also a subspace ofpd, we can write the wavelets w-(x)as linear combinations of the scal Multiresolution analysis relies on many results from linear algebra. ing functions (x). This means there is an m x natrix of con- Some readers may wish to consult the appendix in Part 1 for a brief stants g satisfying v(x)=()Q As discussed in Part l, the starting point for multiresolution analysis is a nested set of vector spaces In the Haar basis, at a particular level aling functions and n=2 wavelets I cvcv Asj increases, the resolution of functions in y increases. The basis the four scaling functions in I functions for the space V are known as scaling funct The next step in multiresolution analysis is to definewavelet space 10 For each j, we define Wa as the orthogonal complementof /o in //+ This means that wo includes all the functions in pi that are orthog- al to all those in w under some chosen inner product. The func tions we choose as a basis for wo are called wavelets of ne d In the case of wavelets constructed on the real line. the columns of p/ are shifted 2.1 A matrix formulation for refinement nother, as are the columns of @. One column The rest of our discussion of multiresolution analysis will focus on characterizes each matrix, so P and g wavelets defined on a bounded domain, although we will also refer pletely determined by se (,p-1,P0,p1,…)and wavelets on the unbounded real line wherever appropriate. In the (.. 9-1, 9o, 91, .. ) which also do not depend on j. Equa- bounded case, each space W has a finite basis, allowing us to use ma- pressions of the form trix notation in much of what follows, as did lounsbery et al.[101 and Quak and Weyrich [13] ox)=∑p2x-0 ter graphics: A primer, part 2, IEEE Computer Graphics and Applica- ions,15(4):75-85,July199Wavelets for Computer Graphics: A Primer Part 2y 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 surface, wavelets provide an elegant technique for representing the levels of detail present. In Part 1 of this primer we discussed the simple case of Haar wavelets in one and two dimensions, and showed how they can be used for image compression. In Part 2, we present the mathematical theory of multiresolution analysis, then develop bounded-interval spline wavelets and describe their use in multiresolution curve and surface editing. 2 Multiresolution analysis The Haar wavelets we discussed in Part 1 are just one of many bases that can be used to treat functions in a hierarchical fashion. In this section, we develop a mathematical framework known asmultires￾olution analysis for studying wavelets [2, 11]. Our examples will continue to focus on the Haar basis, but the more general mathe￾matical notation used here will come in handy for discussing other wavelet bases in later sections. Multiresolution analysis relies on many results from linear algebra. Some readers may wish to consult the appendix in Part 1 for a brief review. As discussed in Part 1, the starting point for multiresolution analysis is a nested set of vector spaces V0  V1  V2 


As j increases, the resolution of functions inVj increases. The basis functions for the space Vj are known as scaling functions. The next step in multiresolution analysis is to definewavelet spaces. For each j, we define Wj as the orthogonal complement of Vj in Vj+1. This means that Wj includes all the functions inVj+1 that are orthog￾onal to all those in Vj under some chosen inner product. The func￾tions we choose as a basis for Wj are called wavelets. 2.1 A matrix formulation for refinement The rest of our discussion of multiresolution analysis will focus on wavelets defined on a bounded domain, although we will also refer to wavelets on the unbounded real line wherever appropriate. In the bounded case, each spaceVj has a finite basis, allowing us to use ma￾trix notation in much of what follows, as did Lounsbery et al. [10] and Quak and Weyrich [13]. y Eric J. Stollnitz, Tony D. DeRose, and David H. Salesin. Wavelets for com￾puter graphics: A primer, part 2. IEEE Computer Graphics and Applica￾tions, 15(4):75–85, July 1995. It is often convenient to put the different scaling functions  j i (x) for a given level j together into a single row matrix, j (x) := [ j 0(x)


 j mj￾1 (x)], where mj is the dimension of Vj . We can do the same for the wavelets: j (x) := [ j 0(x)


j nj￾1(x)], where nj is the dimension of Wj . Because Wj is the orthogonal com￾plement of Vj in Vj+1, the dimensions of these spaces satisfy mj+1 = mj + nj . The condition that the subspacesVj be nested is equivalent to requir￾ing that the scaling functions berefinable. That is, for all j = 1, 2, : : : there must exist a matrix of constants Pj such that j￾1 (x) = j (x) Pj . (1) In other words, each scaling function at levelj ￾ 1 must be express￾ible as a linear combination of “finer” scaling functions at level j. Note that since Vj and Vj￾1 have dimensions mj and mj￾1 , respec￾tively, Pj is an mj mj￾1 matrix (taller than it is wide). Since the wavelet space Wj￾1 is by definition also a subspace ofVj , we can write the wavelets j￾1 (x) as linear combinations of the scal￾ing functions j (x). This means there is an mj nj￾1 matrix of con￾stants Qj satisfying j￾1 (x) = j (x) Qj . (2) Example: In the Haar basis, at a particular level j there are mj = 2j scaling functions and nj = 2j wavelets. Thus, there must be refinement matrices describing how the two scaling functions in V1 and the two wavelets in W1 can be made from the four scaling functions inV2 : P2 = 2 6 4 1 0 1 0 0 1 0 1 3 7 5 and Q2 = 2 6 4 1 0 ￾1 0 0 1 0 ￾1 3 7 5 Remark: In the case of wavelets constructed on the un￾bounded real line, the columns of Pj are shifted versions of one another, as are the columns of Qj . One column therefore characterizes each matrix, so Pj and Qj are com￾pletely determined by sequences (: : : , p￾1, p0, p1, : : :) and (: : : , q￾1, q0, q1, : : :), which also do not depend on j. Equa￾tions (1) and (2) therefore often appear in the literature as ex￾pressions of the form (x) = X i pi (2x ￾ i) (x) = X i qi (2x ￾ i).