8(x)v(y)8(x))th(x)动()h(x)v() /,(,y) L(x,y) wl,(x,y) wv(x,y) co(x)wo() v0(x)w00) v0(x)w/o0) vi(r)vo0) pwo, o(r,y) wio(x, y) wno,o(x,y) wvio(x, y) c8(x)v8(y)v8(x)v8()t2(x)v8(y)vh(x)8(y) cloo(x, y) woo(, y) vo0(x,y) voi.(x,y) 0(x)00) v0(x)000) vd(x)000) ai(x)o0 coo(x, y) 1/goo(x, y) uplo(x,y) iolo(x,y) Figure 7 Standard construction of a two-dimensional Haar wavelet Figure 8 Nonstandard construction of a two-dimensional haar basis for V. In the unnormalized case, functions are +l where plus wavelet basis for k- signs appear, -l where minus signs appear, and 0 in gray regions while some standard basis functions have nonsquare supports. De- to be discarded no longer changes pending upon the application, one of these choices may be prefer- able to the othel procedure ss(C: array [1.. m] of reals, E: real) Tmin← 可} 3.3 Application Il: Image compression T← We defined compression in Section 2.3 as the representation of a function using fewer basis function coefficients than were origi- fori← I to m do ally given. The method we discussed for one-dimensional func if|< T then s←s+()2 ons applies equally well to images, which we treat as the end for cients corresponding to a two-dimensional piecewise-cons ifs<e then in t else T complete treatment of wavelet image compression, see the if|q< T then C←0 end for summarize wavelet image compression using the l-norm nd procedure ch algorithm was used to produce the images in 1. Compute coefficients Cl, ... Cm representing an image in a nor- Figure 9. These images demonstrate the high compression ratios wavelets offer, as well as some of the artifacts they introduce 2. Sort the coefficients in order of decreasing magnitude to produce De Vore et al. [6] suggest that the L' norm is best suited to the the sequence ca(D),., co(m) task of image compression. Here is a pseudocode fragment for a 3. Starting with i m, find the smallest m for which"greedy"L compression scheme The first step is accomplished by applying either of the two- dimensional Haar wavelet transforms described in Section 3. 1. be ing sure to use normalized basis functions. Any standard sorting o Chnique will work for the second step. However, for large images 8<5+error from discarding Ci ∑|{[,y|<then isard coefficient C The pseudocode below outlines a more efficient method that uses a binary search strategy to find a threshold below which coefficient zes are deemed negligible. The procedure takes as input a one- end for dimensional array of coefficients C(with each coefficient corre- sponding to a two-dimensional basis function) and an error toler- Note that this algorithms results depend on the order in which coef- ance e. For each guess at a threshold T, the algorithm computes the ficients are visited. Different images(and degrees of compression) square of the L2 error that would result from discarding coefficients may be obtained from varying this order-for example, by start- smaller in magnitude thanT. This squared error s is compared to ing with the finest scale coefficients, rather than the smallest coef- at each iteration to decide whether the binary search should continue ficients. You could also run a more sophisticated constrained op- in the upper or lower half of the current interval. The algorithm halts timization procedure to select the minimum number of coefficients when the current interval is so narrow that the number of coefficients subject to the error bound1 1(x) 0 0 (y) 1 0 (x) 0 0 (y) 0 0 (x) 0 0  (y) 0 0(x) 0 0(y) 1 1 (x) 0 0 (y) 1 0 (x) 0 0 (y) 0 0 (x) 0 0  (y) 0 0(x) 0 0 (y) 1 1 (x) 1 0 (y) 1 0 (x) 1 0 (y) 0 0 (x) 1 0  (y) 0 0(x) 1 0 (y) 1 1 (x) 1 1 (y) 1 0 (x) 1 1 (y) 0 0 (x) 1 1  (y) 0 0(x) 1 1 (y) Figure 7 Standard construction of a two-dimensional Haar wavelet basis for V2. In the unnormalized case, functions are +1 where plus signs appear, ￾1 where minus signs appear, and 0 in gray regions. while some standard basis functions have nonsquare supports. De￾pending upon the application, one of these choices may be prefer￾able to the other. 3.3 Application II: Image compression We defined compression in Section 2.3 as the representation of a function using fewer basis function coefficients than were origi￾nally given. The method we discussed for one-dimensional func￾tions applies equally well to images, which we treat as the coeffi- cients corresponding to a two-dimensional piecewise-constant ba￾sis. The approach presented here is only introductory; for a more complete treatment of wavelet image compression, see the article by DeVore et al. [6]. We can summarize wavelet image compression using the L2 norm in three steps: 1. Compute coefficients c1, : : : , cm representing an image in a nor￾malized two-dimensional Haar basis. 2. Sort the coefficients in order of decreasing magnitude to produce the sequence c(1), : : : , c(m). 3. Starting with ˜ P m = m, find the smallest ˜m for which m i= ˜m+1(c(i)) 2   2 , where  is the allowable L2 error. The first step is accomplished by applying either of the two￾dimensional Haar wavelet transforms described in Section 3.1, be￾ing sure to use normalized basis functions. Any standard sorting technique will work for the second step. However, for large images sorting becomes exceedingly slow. The pseudocode below outlines a more efficient method that uses a binary search strategy to find a threshold below which coefficient sizes are deemed negligible. The procedure takes as input a one￾dimensional array of coefficients C (with each coefficient corre￾sponding to a two-dimensional basis function) and an error toler￾ance . For each guess at a threshold  , the algorithm computes the square of the L2 error that would result from discarding coefficients smaller in magnitude than  . This squared errors is compared to  2 at each iteration to decide whether the binary search should continue in the upper or lower half of the current interval. The algorithm halts when the current interval is so narrow that the number of coefficients 1 1,1 (x, y) 1 0,1(x, y) 1 1,0 (x, y) 1 0,0(x, y)  1 1,1  (x, y) 1 0,1(x, y)  1 1,0  (x, y) 1 0,0(x, y) 1 1,1  (x, y) 1 0,1(x, y) 1 1,0  (x, y) 1 0,0(x, y) 0 0,0  (x, y) 0 0,0(x, y) 0 0,0  (x, y) 0 0,0(x, y) Figure 8 Nonstandard construction of a two-dimensional Haar wavelet basis for V2. to be discarded no longer changes. procedure Compress(C: array [1. . m] of reals; : real) min min f jC[i]j g max max f jC[i]j g do  (min + max)=2 s 0 for i 1 to m do if jC[i]j <  then s s + (C[i])2 end for if s < 2 then min  else max  until min  max for i 1 to m do if jC[i]j <  then C[i] 0 end for end procedure This binary search algorithm was used to produce the images in Figure 9. These images demonstrate the high compression ratios wavelets offer, as well as some of the artifacts they introduce. DeVore et al. [6] suggest that the L1 norm is best suited to the task of image compression. Here is a pseudocode fragment for a “greedy” L1 compression scheme: for each pixel (x, y) do [x, y] 0 end for for i 1 to m do  0  + error from discarding C[i] if P x,y j0 [x, y]j <  then discard coefficient C[i]   0 end if end for Note that this algorithm’s results depend on the order in which coef- ficients are visited. Different images (and degrees of compression) may be obtained from varying this order—for example, by start￾ing with the finest scale coefficients, rather than the smallest coef- ficients. You could also run a more sophisticated constrained op￾timization procedure to select the minimum number of coefficients subject to the error bound. 6