nested set of spaces /3. We will consider this topic more thoroughly y approximation Now we need to define a basis for each vector space V!. The basis ally denoted by the symbol c. A simple basis for W is given by the set of scaled and translated"box functions. d(r) 0,,2-1, ws detail coefficients (x) I for 0<x< I As an example, Figure 2 shows the four box functions forming a ba- The next step is to choose an inner product defined on the vector l-detail coefficients spaces V!. The"standard"inner product, vle f(r)g(x)dx, or two elements g E k will do quite well for our running ex- mple. We can now define a new vector space H as the orthogonal of all functions in w that are orthogonal to all functions in chosen inner product. Informally, we can think of in W as a means for representing the parts of a function in l A collection of linearly independent functions/(x)spanning wo called wavelets. These basis functions have two important proper approximation detail coefficient I.The basis functions w/ of wa, together with the basis functions d Figure 1 A ce of decreasing. resoluti of y form a basis for yf+ function(left), along with the detail coefficient 2. Every basis function y of w is orthogonal to every basis func- the finest approximation(right ). Note that in tion d of wd under the chosen inner product. works wel he corresponding detail coef smal Thus, the"detail coefficients" of Section 2. 1 are really coefficients of the wavelet basis functions quences of coefficients. Alternatively, we can think of images se- wavelets, given y sponding to the box basis are known as the Haar 2.2 One-dimensional haar wavelet basis functions v(x)=v(2x-),i=0,,2-1 so, we will use the concept of a vector space from linear algebra ixel image is just a function that interval We'll let Io be the vector all these 1for0≤x<1/2 tions. A two-pixel image has two constant over the w(x) 1/2<x<1 vals [0, 1/2)and [1/2, 1). We ll call the space containing all these 0 otherwise unctions V. If we continue in this manner, the space po will in- ons defined on the interval [o, 1) Figure 3 shows the two Haar wavelet with constant pieces over each of 2 equal subintervals Before going on, let's run through our example from Section 2.1 w think of every one-dimensional with 2 pixels a an element, or vector, in I. Note that because these vectors are all again, but now applying these more sophisticated ideas. functions defined on the unit interval vector inkd is also con- We begin by expressing our original image I(x)as a linear combi tained in /. For example, we can always describe a piecewise- nation of the box basis functions in I constant function with two intervals as a piecewise-constant func tion with four intervals. with each interval in the first function ce (x)=(x)+(x)+x)+c3的(x) responding to a pair of intervals in the second. Thus, the spaces v Some authors refer to functions with these properties aspre-wavelets, reserving the term"wavelet"for functions, that are also orthogonal to eachV4 approximation V3 approximation W3 detail coefficients V2 approximation W2 detail coefficients V1 approximation W1 detail coefficients V0 approximation W0 detail coefficient Figure 1 A sequence of decreasing-resolution approximations to a function (left), along with the detail coefficients required to recapture the finest approximation (right). Note that in regions where the true function is close to being flat, a piecewise-constant approximation works well, so the corresponding detail coefficients are relatively small. 2.2 One-dimensional Haar wavelet basis functions We have shown how one-dimensional images can be treated as sequences of coefficients. Alternatively, we can think of images as piecewise-constant functions on the half-open interval [0, 1). To do so, we will use the concept of a vector space from linear algebra. A one-pixel image is just a function that is constant over the entire interval [0, 1). We’ll let V0 be the vector space of all these functions. A two-pixel image has two constant pieces over the intervals [0, 1=2) and [1=2, 1). We’ll call the space containing all these functions V1 . If we continue in this manner, the space Vj will include all piecewise-constant functions defined on the interval [0, 1) with constant pieces over each of 2j equal subintervals. We can now think of every one-dimensional image with 2j pixels as an element, or vector, in Vj . Note that because these vectors are all functions defined on the unit interval, every vector inVj is also contained in Vj+1. For example, we can always describe a piecewiseconstant function with two intervals as a piecewise-constant function with four intervals, with each interval in the first function corresponding to a pair of intervals in the second. Thus, the spacesVj are nested; that is, V0 V1 V2 The mathematical theory of multiresolution analysis requires this nested set of spaces Vj . We will consider this topic more thoroughly in Part 2. Now we need to define a basis for each vector spaceVj . The basis functions for the spaces Vj are called scaling functions, and are usually denoted by the symbol . A simple basis for Vj is given by the set of scaled and translated “box” functions: j i (x) := (2j x i), i = 0, : : : , 2j 1, where (x) := 1 for 0 x < 1 0 otherwise. As an example, Figure 2 shows the four box functions forming a basis for V2 . The next step is to choose an inner product defined on the vector spaces Vj . The “standard” inner product, hf j gi := Z 1 0 f(x) g(x) dx, for two elements f, g 2 Vj will do quite well for our running example. We can now define a new vector spaceWj as the orthogonal complement of Vj in Vj+1. In other words, we will let Wj be the space of all functions inVj+1 that are orthogonal to all functions inVj under the chosen inner product. Informally, we can think of the wavelets in Wj as a means for representing the parts of a function inVj+1 that cannot be represented in Vj . A collection of linearly independent functions j i (x) spanning Wj are called wavelets. These basis functions have two important properties: 1. The basis functions j i of Wj , together with the basis functions j i of Vj , form a basis for Vj+1. 2. Every basis function j i of Wj is orthogonal to every basis function j i of Vj under the chosen inner product.1 Thus, the “detail coefficients” of Section 2.1 are really coefficients of the wavelet basis functions. The wavelets corresponding to the box basis are known as theHaar wavelets, given by j i(x) := (2j x i), i = 0, : : : , 2j 1, where (x) := ( 1 for 0 x < 1=2 1 for 1=2 x < 1 0 otherwise. Figure 3 shows the two Haar wavelets spanning W1 . Before going on, let’s run through our example from Section 2.1 again, but now applying these more sophisticated ideas. We begin by expressing our original image I(x) as a linear combination of the box basis functions inV2 : I(x) = c 2 0 2 0(x) + c 2 1 2 1(x) + c 2 2 2 2(x) + c 2 3 2 3(x). 1Some authors refer to functions with these properties aspre-wavelets, reserving the term “wavelet” for functions j i that are also orthogonal to each other. 2