transform rows transform rows Figure 5 Standard decomposition of an image Figure 6 Nonstandard decomposition of an image and columns. First, we perform one step of horizontal pairwise aver- by first defining a two-dimensional scaling function aging and differencing on the pixel values in each row of the image Next, we apply vertical pairwise averaging and differencing to each (x,y):=(x)y), column of the result. To complete the transformation, we repeat this process recursively only on the quadrant containing averages in both and three wavelet functions, directions. Figure 6 shows all the steps involved in the nonstandard decomposition procedure below dl l(x,y): =dx)w0) v(x,y)=以(x)y) procedure Nonstandard Decomposition(C: array [1.h, I.h]of reals) u(x,y):=(x)v() for roM← I to h do We now denote levels of scaling with a superscript (as we did in the DecompositionStep(arrow, I.) one-dimensional case)and horizontal and vertical translations with end for a pair of subscripts k and e. The nonstandard basis consists of a sin- for col← I to h do gle coarse scaling function ooo(r,y) =od(x, y) along with scales DecompositionStep(qll. h, col and translates of the three wavelet functions d, yc, and in ol (x, y): =2 o(2x-k, 2y-e end whi end procedure adh (x,y): =20 d(2x-k, 2y-e) a(x,y): =24/(2x-k, 2y-e 3.2 Two-dimensional Haar basis functions The constant 2 normalizes the wavelets to give an orthonormal ba- The two methods of decomposing a two-dimensional image yield is. The nonstandard construction results in the basis for shown coefficients that correspond to two different sets of basis functions 8 sis formed by the standard construction [2]of a two-dimensional We have presented both the standard and nonstandard approaches basis. Similarly, the nonstandard decomposition gives coefficients for the nonstandard construction of basis functions tages. The standard decomposition of an image is appealing be- The standard construction of a two-dimensional wavelet basis con- all rows and then on all columns. On the other hand, it is slightly ists of all possible tensor products of one-dimensional basis func- more efficient to compute the nonstandard decomposition. For an tions. For example, when we start with the one-dimensional Haar m x m image, the standard decomposition requires 4(m-m)as- basis for V, we get the two-dimensional basis for Shown in Fig- signment operations, while the nonstandard decomposition requires ure 7. Note that if we apply the standard construction to an orthonor only g(m-1)assignment operations mal basis in one dimension, we get an orthonormal basis in two di Another consideration is the support of each basis function, mean- ing the portion of each functions domain where that function is non- The nonstandard construction of a two-dimensional basis proceeds zero. All nonstandard Haar basis functions have square supports,


. . . - transform rows ? transform columns Figure 5 Standard decomposition of an image. and columns. First, we perform one step of horizontal pairwise aver￾aging and differencing on the pixel values in each row of the image. Next, we apply vertical pairwise averaging and differencing to each column of the result. To complete the transformation, we repeat this process recursively only on the quadrant containing averages in both directions. Figure 6 shows all the steps involved in the nonstandard decomposition procedure below. procedure NonstandardDecomposition(C: array [1. . h, 1. . h] of reals) C C=h (normalize input coefficients) while h > 1 do for row 1 to h do DecompositionStep(C[row, 1. . h]) end for for col 1 to h do DecompositionStep(C[1. . h, col]) end for h h=2 end while end procedure 3.2 Two-dimensional Haar basis functions The two methods of decomposing a two-dimensional image yield coefficients that correspond to two different sets of basis functions. The standard decomposition of an image gives coefficients for a ba￾sis formed by the standard construction [2] of a two-dimensional basis. Similarly, the nonstandard decomposition gives coefficients for the nonstandard construction of basis functions. The standard construction of a two-dimensional wavelet basis con￾sists of all possible tensor products of one-dimensional basis func￾tions. For example, when we start with the one-dimensional Haar basis for V2 , we get the two-dimensional basis forV2 shown in Fig￾ure 7. Note that if we apply the standard construction to an orthonor￾mal basis in one dimension, we get an orthonormal basis in two di￾mensions. The nonstandard construction of a two-dimensional basis proceeds ... - transform rows ? transform columns Figure 6 Nonstandard decomposition of an image. by first defining a two-dimensional scaling function, (x, y) := (x) (y), and three wavelet functions,  (x, y) := (x) (y) (x, y) := (x) (y) (x, y) := (x) (y). We now denote levels of scaling with a superscriptj (as we did in the one-dimensional case) and horizontal and vertical translations with a pair of subscripts k and `. The nonstandard basis consists of a sin￾gle coarse scaling function 0 0,0(x, y):=(x, y) along with scales and translates of the three wavelet functions  , , and :  j k` (x, y) := 2j (2j x ￾ k, 2j y ￾ `) j k` (x, y) := 2j (2j x ￾ k, 2j y ￾ `) j k` (x, y) := 2j (2j x ￾ k, 2j y ￾ `). The constant 2j normalizes the wavelets to give an orthonormal ba￾sis. The nonstandard construction results in the basis forV2 shown in Figure 8. We have presented both the standard and nonstandard approaches to wavelet transforms and basis functions because both have advan￾tages. The standard decomposition of an image is appealing be￾cause it simply requires performing one-dimensional transforms on all rows and then on all columns. On the other hand, it is slightly more efficient to compute the nonstandard decomposition. For an m m image, the standard decomposition requires 4(m2 ￾ m) as￾signment operations, while the nonstandard decomposition requires only 8 3 (m2 ￾ 1) assignment operations. Another consideration is the support of each basis function, mean￾ing the portion of each function’s domain where that function is non￾zero. All nonstandard Haar basis functions have square supports, 5