Multiresolutions

Biorthogonal wavelet bases are related to multiresolution approximations. The family {ϕ(t – n)}_n∈ is a Riesz basis of the space V₀ it generates, whereas is a Riesz basis of another space ₀. Let V_j and _j be the spaces defined by

One can verify that {V_j}_j∈ and {_j}_j∈ are two multiresolution approximations of L²(). For any j ∈ , {ϕ_{j, n}}_n∈ and are Riesz bases of V_j and _j. The dilated wavelets {ψ_{j, n}}_n∈ and are bases of two detail spaces W_j and _j such that

The biorthogonality of the decomposition and reconstruction wavelets implies that W_j is not orthogonal to V_j but is to _j, whereas _j is not orthogonal to _j but is to V_j.

Fast Biorthogonal Wavelet Transform

The perfect reconstruction filter bank discussed in Section 7.3.2 implements a fast biorthogonal wavelet transform. For any discrete signal input b[n] sampled at intervals N⁻¹ = 2^L, there exists f ∈ V_L such that a_L[n] = 〈f, ϕ_{L, n}〉 = N^−1/2 b[n]. The wavelet coefficients are computed by successive convolutions with and .

Let a_j[n] = 〈f, ϕ_{j, n}〉 and d_j[n] = 〈f, ψ_{j, n}〉. As in Theorem 7.10, one can prove that

(7.157)

The reconstruction is performed with the dual filters and :

(7.158)

If a_L includes N nonzero samples, the biorthogonal wavelet representation [{d_j}_{L < j ≤ J}, a_J] is calculated with O(N) operations by iterating (7.157) for L ≤ j < J. The reconstruction of a_L by applying (7.158) for J > j ≥ L requires the same number of operations.

Support

If the perfect reconstruction filters h and have a finite impulse response, then the corresponding scaling functions and wavelets also have a compact support. As in Section 7.2.1, one can show that if h[n] and [n] are nonzero, respectively, for N₁ ≤ n ≤ N₂ and ₁ ≤ n ≤ ₂, then ϕ and have a support equal to [N₁, N₂] and [₁, ₂], respectively. Since

the supports of ψ and defined in (7.145) are, respectively,

(7.159)

Thus, both wavelets have a support of the same size and equal to

(7.160)

Vanishing Moments

The number of vanishing moments of ψ and depends on the number of zeroes at ω = π of ĥ(ω) and . Theorem 7.4 proves that ψ has vanishing moments if the derivatives of its Fourier transform satisfy for k ≤ . Since , (7.41) implies that it is equivalent to impose that has a zero of order at ω = 0. Since , this means that (ω) has a zero of order at ω = π. Similarly, the number of vanishing moments of is equal to the number p of zeroes of ĥ(ω) at π.

Regularity

Although the regularity of a function is a priori independent of the number of vanishing moments, the smoothness of biorthogonal wavelets is related to their vanishing moments. The regularity of ϕ and ψ is the same because (7.145) shows that ψ is a finite linear expansion of ϕ translated. Tchamitchian’s theorem (7.6) gives a sufficient condition for estimating this regularity. If ĥ(ω) has a zero of order p at π, we can perform the factorization

(7.161)

Let . Theorem 7.6 proves that ϕ is uniformly Lipschitz α for

Generally, log₂ B increases more slowly than p. This implies that the regularity of ϕ and ψ increases with p, which is equal to the number of vanishing moments of . Similarly, one can show that the regularity of and increases with , which is the number of vanishing moments of ψ. If ĥ and have different numbers of zeroes at π, the properties of ψ and can be very different.

Ordering of Wavelets

Since ψ and might not have the same regularity and number of vanishing moments, the two reconstruction formulas

(7.162)

(7.163)

are not equivalent. The decomposition (7.162) is obtained with the filters (h, g), and the reconstruction with (, ). The inverse formula (7.163) corresponds to (, ) at the decomposition and (h, g) at the reconstruction.

To produce small wavelet coefficients in regular regions we must compute the inner products using the wavelet with the maximum number of vanishing moments. The reconstruction is then performed with the other wavelet, which is generally the smoothest one. If errors are added to the wavelet coefficients, for example with a quantization, a smooth wavelet at the reconstruction introduces a smooth error. The number of vanishing moments of ψ is equal to the number of zeroes at π of . Increasing also increases the regularity of . Thus, it is better to use h at the decomposition and at the reconstruction if ĥ has fewer zeroes at π than .

Symmetry

It is possible to construct smooth biorthogonal wavelets of compact support that are either symmetric or antisymmetric. This is impossible for orthogonal wavelets, besides the particular case of the Haar basis. Symmetric or antisymmetric wavelets are synthesized with perfect reconstruction filters having a linear phase. If h and have an odd number of nonzero samples and are symmetric about n = 0, the reader can verify that ϕ and are symmetric about t = 0, while ψ and are symmetric with respect to a shifted center. If h and have an even number of nonzero samples and are symmetric about n = 1/2, then ϕ(t) and are symmetric about t = 1/2, while ψ and are antisymmetric with respect to a shifted center. When the wavelets are symmetric or antisymmetric, wavelet bases over finite intervals are constructed with the folding procedure of Section 7.5.2.

Spline Biorthogonal Wavelets

Let us choose

(7.169)

with ε = 0 for p even and ε = 1 for p odd. The scaling function computed with (7.148) is then a box spline of degree p − 1:

Since ψ is a linear combination of box splines ϕ (2t – n), it is a compactly supported polynomial spline of the same degree.

The number of vanishing moments of ψ is a free parameter, which must have the same parity as p. Let q = (p + p)/2. The biorthogonal filter of minimum length is obtained by observing that L(cos ω) = 1 in (7.164). Thus, the factorization (7.166) and (7.168) imply that

(7.170)

These filters satisfy the conditions of Theorem 7.14 and therefore generate biorthogonal wavelet bases. Table 7.3 gives the filter coefficients for (p = 2, = 4) and (p = 3, = 7); see Figure 7.14 for the resulting dual wavelet and scaling functions.

Table 7.3 Perfect Reconstruction Filters h and for Compactly Supported Spline Wavelets

FIGURE 7.14 Spline biorthogonal wavelets and scaling functions of compact support corresponding to Table 7.3 filters.

Closer Filter Length

Biorthogonal filters h and of more similar length are obtained by factoring the polynomial in (7.166) with two polynomial L(cos ω) and (cos ω) of similar degree. There is a limited number of possible factorizations. For q = (p + )/2 < 4, the only solution is L(cos ω) = 1. For q = 4 there is one nontrivial factorization, and for q = 5 there are two. Table 7.4 gives the resulting coefficients of the filters h and of most similar length, computed by Cohen, Daubechies, and Feauveau [172]. These filters also satisfy the conditions of Theorem 7.14 and therefore define biorthogonal wavelet bases.

Table 7.4 Perfect Reconstruction Filters of Most Similar Length

Figure 7.15 gives the scaling functions and wavelets for p = = 2 and p = = 4, which correspond to filter sizes 5/3 and 9/7, respectively. For p = p = 4, ϕ, ψ are similar to , which indicates that this basis is nearly orthogonal. This particular set of filters is often used in image compression and recommended for JPEG-2000. The quasi-orthogonality guarantees a good numerical stability and the symmetry allows one to use the folding procedure of Section 7.5.2 at the boundaries. There are also enough vanishing moments to create small wavelet coefficients in regular image domains. Section 7.8.5 describes their lifting implementation, which is simple and efficient. Filter sizes 5/3 are also recommended for lossless compression with JPEG-2000, because they use integer operations with a lifting algorithm. The design of other compactly supported biorthogonal filters is discussed extensively in [172, 473].

FIGURE 7.15 Biorthogonal wavelets and scaling functions calculated with the filters of Table 7.4, with p = 2 and = 2 (top row) and p = 4 and p = 4 (bottom row).

Discrete Basis of ^N

The decomposition of a signal in a wavelet basis over an interval is computed by modifying the fast wavelet transform algorithm of Section 7.3.1. A discrete signal b[n] of N samples is associated to the approximation of a signal f ∈ L²[0, 1] at a scale N⁻¹ = 2^L with (7.111):

Its wavelet coefficients can be calculated at scales 1 ≥ 2^j > 2^L. We set

(7.172)

The wavelets and scaling functions with support inside [0, 1] are identical to the wavelets and scaling functions of a basis of L²(). Thus, the corresponding coefficients a_j[n] and d_j[n] can be calculated with the decomposition and reconstruction equations given by Theorem 7.10. However, these convolution formulas must be modified near the boundary where the wavelets and scaling functions are modified. Boundary calculations depend on the specific design of the boundary wavelets, as explained in the next three sections. The resulting filter bank algorithm still computes the N coefficients of the wavelet representation [a_J, {d_j}_L<j≤J] of a_L with O(N) operations.

Wavelet coefficients can also be written as discrete inner products of a_L with discrete wavelets:

(7.173)

As in Section 7.3.3, we verify that

is an orthonormal basis of ^N.

Periodic Discrete Transform

For f ∈ L²[0, 1] let us consider

We verify as in (7.178) that these inner products are equal to the coefficients of a periodic signal decomposed in a nonperiodic wavelet basis:

Thus, the convolution formulas of Theorem 7.10 apply if we take into account the periodicity of f^pér. This means that a_j[n] and d_j[n] are considered as discrete signals of period 2^−j, and all convolutions in (7.102-7.104) must therefore be replaced by circular convolutions. Despite the poor behavior of periodic wavelets near the boundaries, they are often used because the numerical implementation is particularly simple.

Folded Discrete Transform

For f ∈ L²[0, 1], we consider

We verify as in (7.180) that these inner products are equal to the coefficients of a folded signal decomposed in a nonfolded wavelet basis:

The convolution formulas of Theorem 7.10 apply if we take into account the symmetry and periodicity of f^repl. The symmetry properties of ϕ and ψ imply that a_j[n] and d_j[n] also have symmetry and periodicity properties, which must be taken into account in the calculations of (7.102-7.104).

Symmetric biorthogonal wavelets are constructed with perfect reconstruction filters h and ĥ of odd size that are symmetric about n = 0. Then ϕ is symmetric about 0, whereas ψ is symmetric about 1/2. As a result, one can verify that a_j[n] is 2^−j+1 periodic and symmetric about n = 0 and n = 2^−j. Thus, it is characterized by 2^−j+1 samples for 0 ≤ n ≤ 2^−j. The situation is different for d_j[n], which is 2^−j+1 periodic but symmetric with respect to −1/2 and 2^−j − 1/2. It is characterized by 2^−j samples for 0 ≤ n < 2^−j.

To initialize this algorithm, the original signal a_L[n] defined over 0 ≤ n < N − 1 must be extended by one sample at n = N, and considered to be symmetric with respect to n = 0 and n = N. The extension is done by setting a_L[N] = a_L[N − 1]. For any J < L, the resulting discrete wavelet representation [{dj}_L<j≤J, a_J] is characterized by N + 1 coefficients. To avoid adding one more coefficient, one can modify symmetry at the right boundary of a_L by considering that it is symmetric with respect to N − 1/2 instead of N. The symmetry of the resulting a_j and d_j at the right boundary is modified accordingly by studying the properties of the convolution formula (7.157). As a result, these signals are characterized by 2^−j samples and the wavelet representation has N coefficients. A simpler implementation of this folding technique is given with a lifting in Section 7.8.5. This folding approach is used in most applications because it leads to simpler data structures that keep the number of coefficients constant. However, the discrete coefficients near the right boundary cannot be written as inner products of some function f(t) with dilated boundary wavelets.

Antisymmetric biorthogonal wavelets are obtained with perfect reconstruction filters h and ĥ of even size that are symmetric about n = 1/2. In this case, ϕ is symmetric about 1/2 and ψ is antisymmetric about 1/2. As a result, a_j and d_j are 2^−j+1 periodic and, respectively, symmetric and antisymmetric about −1/2 and 2^−j − 1/2. They are both characterized by 2^−j samples for 0 ≤ n < 2^−j. The algorithm is initialized by considering that a_L[n] is symmetric with respect to −1/2 and N − 1/2. There is no need to add another sample. The resulting discrete wavelet representation [{d_j}_L<j≤J, a_J] is characterized by N coefficients.

Multiresolution of L²[0, 1]

A wavelet basis of L²[0, 1] is constructed with a multiresolution approximation {V_j^int}_–∞<j≤0. A wavelet has p vanishing moments if it is orthogonal to all polynomials of degree p − 1 or smaller. Since wavelets at a scale 2^j are orthogonal to functions in V_j^int, to guarantee that they have p vanishing moments we make sure that polynomials of degree p − 1 are inside V_j^int.

We define an approximation space V_j ^int ⊂ L²[0, 1] with a compactly supported Daubechies scaling function ϕ associated to a wavelet with p vanishing moments. Theorem 7.7 proves that the support of ϕ has size 2p − 1. We translate ϕ so that its support is [–p + 1, p]. At a scale 2^j ≤ (2p)⁻¹, there are 2^−j − 2p scaling functions with a support inside [0, 1]:

To construct an approximation space V_j^int of dimension 2^−j we add p scaling functions with a support on the left boundary near t = 0:

and p scaling functions on the right boundary near t = 1:

Theorem 7.17 constructs appropriate boundary scaling functions {ϕ^left_n}_0≤n<p and {ϕ^right_n}_0≤n<p.

Theorem 7.17:

Cohen, Daubechies, Vial. One can construct boundary scaling functions ϕ^left_n and ϕ^right_n so that if 2^−j ≥ 2p, then is an orthonormal basis of a space V_j^int satisfying

and the restrictions to [0, 1] of polynomials of degree p − 1 are in V_j^int.

Proof.

A sketch of the proof is given. All details are in [174]. Since the wavelet ψ corresponding to ϕ has p vanishing moments, the Fix-Strang condition (7.70) implies that

(7.183)

is a polynomial of degree k. At any scale 2^j, q_k(2^−jt) is still a polynomial of degree k, and for 0 ≤ k < p this family defines a basis of polynomials of degree p − 1. To guarantee that polynomials of degree p − 1 are in V_j^int we impose that the restriction of q_k(2^−jt) to [0, 1] can be decomposed in the basis of V_j^int:

(7.184)

Since the support of ϕ is [–p + 1, p], the condition (7.184) together with (7.183) can be separated into two nonoverlapping left and right conditions. With a change of variable, we verify that (7.184) is equivalent to

(7.185)

and

(7.186)

The embedding property V_j^int⊂V_{j − 1}^int is obtained by imposing that the boundary scaling functions satisfy scaling equations. We suppose that ϕ^left_n has a support [0, p + n] and satisfies a scaling equation of the form

(7.187)

whereas φ^right_n has a support [–p –n, 0] and satisfies a similar scaling equation on the right. The constants H^left_{n, l}, h^left_{n, m}, H^right_{n, l}, and h^right_{n, m} are adjusted to verify the polynomial reproduction equations (7.185) and (7.186), while producing orthogonal scaling functions. The resulting family is an orthonormal basis of a space V_j^int.

The convergence of the spaces V_j^int to L²[0, 1] when 2^j goes to 0 is a consequence of the fact that the multiresolution spaces V_j generated by the Daubechies scaling function {ϕ_{j, n}}_n∈ converge to L²().

The proof constructs the scaling functions through scaling equations specified by discrete filters. At the boundaries, the filter coefficients are adjusted to construct orthogonal scaling functions with a support in [0, 1], and to guarantee that polynomials of degree p − 1 are reproduced by these scaling functions. Table 7.5 gives the filter coefficients for p = 2.

Table 7.5 Left and Right Border Coefficients for a Daubechies Wavelet with p=2 Vanishing Moments

Wavelet Basis of L²[0, 1]

Let W_j^int be the orthogonal complement of V_j^int in V_{j − 1}^int. The support of the Daubechies wavelet ψ with p vanishing moments is [–p + 1, p]. Since ϕ_{j, n} is orthogonal to any ϕ_{j, l}, we verify that an orthogonal basis of W_j^int can be constructed with the 2^−j − 2p inside wavelets with support in [0, 1]:

to which are added 2p left and right boundary wavelets

Since W^int_j ⊂ V^int_j–1 the left and right boundary wavelets at any scale 2^j can be expanded into scaling functions at the scale 2^j–1. For j=1 we impose that the left boundary wavelets satisfy equations of the form

(7.188)

The right boundary wavelets satisfy similar equations. The coefficients G^left_n,l, g^left_n,m, G^right_n,l, and g^right_n,m are computed so that {ψ^int_j,n}_{0 ≤n<2^−j} is an orthonormal basis of W^int_j. Table 7.5 gives the values of these coefficients for p = 2.

For any 2^J ≤ (2p)⁻¹ the multiresolution properties prove that

which implies that

(7.189)

is an orthonormal wavelet basis of L²[0, 1]. The boundary wavelets, like the inside wavelets, have p vanishing moments because polynomials of degree p − 1 are included in the space V^int_j. Figure 7.18 displays the 2p = 4 boundary scaling functions and wavelets.

FIGURE 7.18 Boundary scaling functions and wavelets with p = 2 vanishing moments.

Fast Discrete Algorithm

For any f ∈ L²[0, 1] we denote

Wavelet coefficients are computed with a cascade of convolutions identical to Theorem 7.10 as long as filters do not overlap signal boundaries. A Daubechies filter h is considered here to have a support located at [– p + 1, p]. At the boundary, the usual Daubechies filters are replaced by boundary filters that relate boundary wavelets and scaling functions to the finer-scale scaling functions in (7.187) and (7.188).

Scaling Autocorrelation

We denote by ϕ_o an orthogonal scaling function, defined by the fact that {ϕ_o (t – n)}_{n ε} is an orthonormal basis of a space V₀ of a multiresolution approximation. Theorem 7.2 proves that this scaling function is characterized by a conjugate mirror filter h_o. Theorem 7.20 defines an interpolation function from the autocorrelation of ϕ_o [423].

Theorem 7.20.

Let . If , then

(7.193)

is an interpolation function. Moreover,

(7.194)

with

(7.195)

Proof.

The main steps of the proof are given without technical detail. Let us set s = 2^j. One can verify that the spaces {V_j = U_2j}_{j ∈} define a multiresolution approximation of L²(). The Riesz basis of V₀ required by Definition 7.1 is obtained with θ = ϕ. This basis is orthogonalized by Theorem 7.1 to obtain an orthogonal basis of scaling functions. Theorem 7.3 derives a wavelet orthonormal basis {ψ_j,n}_{(j,n) ∈²} of L² ().

Using Theorem 7.4, one can verify that ψ has p vanishing moments if and only if has p zeros at π. Although ϕ is not the orthogonal scaling function, the Fix-Strang condition (7.70) remains valid. It is also equivalent that for k < p,

is a polynomial of degree k. The interpolation property (7.191) implies that qk(n) = n^k for all n ∈ , so qk(t) = t^k. Since {t^k}_0⩽k<p is a basis for polynomials of degree p −1, any polynomial q(t) of degree p − 1 can be decomposed over {ϕ(t – n)}_{n ∈} if and only if has p zeros at π.

We indicate how to prove (7.199) for s = 2^j. The truncated family of wavelets {ψ_l,n}_{l⩽j,n ∈} is an orthogonal basis of the orthogonal complement of U_2^j = V_j in L²(). Thus,

If f is uniformly Lipschitz α, since ψ has p vanishing moments, Theorem 6.3 proves that there exists A > 0 such that

To simplify the argument we suppose that ψ has a compact support, although this is not required. Since f also has a compact support, one can verify that the number of nonzero 〈f, ψ_l,n〉 is bounded by K 2^−l for some K > 0. Thus,

which proves (7.199) for s = 2^j.

As long as α ≤ p, the larger the Lipschitz exponent α, the faster the error ‖ f – P_Us f ‖ decays to zero when the sampling interval s decreases. If a signal f is C^k with a compact support, then it is uniformly Lipschitz k, so Theorem 7.21 proves that ‖ f – P_Us f ‖ ≤ Cs^k.

EXAMPLE 7.11

A cubic spline-interpolation function is obtained from the linear spline-scaling function ϕ_o. The Fourier transform expression (7.5) yields

(7.200)

Figure 7.19(a) gives the graph of ϕ, which has an infinite support but exponential decay. With Theorem 7.21, one can verify that this interpolation function recovers polynomials of degree 3 from a uniform sampling. The performance of spline interpolation functions for generalized sampling theorems is studied in [162, 468].

FIGURE 7.19 (a) Cubic spline–interpolation function. (b) Deslauriers-Dubuc interpolation function of degree 3.

EXAMPLE 7.12

Deslauriers-Dubuc[206] interpolation functions of degree 2p − 1 are compactly supported interpolation functions of minimal size that decompose polynomials of degree 2p − 1. One can verify that such an interpolation function is the autocorrelation of a scaling function ϕ_o. To reproduce polynomials of degree 2p − 1, Theorem 7.21 proves that must have a zero of order 2p at π. Since it follows that and thus has a zero of order p at π. The Daubechies theorem (7.7) designs minimum-size conjugate mirror filters h_o that satisfy this condition. Daubechies filters h_o have 2p nonzero coefficients and the resulting scaling function ϕ_o has a support of size 2p − 1. The autocorrelation ϕ is the Deslauriers-Dubuc interpolation function, which support [− 2p + 1, 2p − 1].

For p = 1, ϕ_o = 1_[0,1] and ϕ are the piecewise linear tent functions with a support that [– 1, 1]. For p = 2, the Deslauriers-Dubuc interpolation function ϕ is the autocorrelation of the Daubechies 2 scaling function, shown in Figure 7.10. The graph of this interpolation function is in Figure 7.19(b). Polynomials of degree 2p − 1 = 3 are interpolated by this function.

The scaling equation (7.194) implies that any autocorrelation filter verifies h[2n] =0 for n ≠ 0. For any p ≤0, the nonzero values of the resulting filter are calculated from the coefficients of the polynomial (7.168) that is factored to synthesize Daubechies filters. The support of h is[− 2p + 1, 2p − 1] and

(7.201)

Dual Basis

If f ∉ U_s, then it is approximated by its orthogonal projection P_Us f on U_s before the samples at intervals s are recorded. This orthogonal projection is computed with a biorthogonal basis [82]. Theorem 3.4 proves that where the Fourier transform of ϕ is

(7.202)

Figure 7.20 gives the graph of the cubic spline associated to the cubic spline-interpolation function. The orthogonal projection of f over U_s is computed by decomposing f in the biorthogonal bases

FIGURE 7.20 The dual cubic spline (t) associated to the cubic spline-interpolation function ϕ(t) shown in Figure 7.19(a).

(7.203)

Let The interpolation property (7.190) implies that

(7.204)

Therefore, this discretization of f through a projection onto U_s is obtained by a filtering with followed by a uniform sampling at intervals s. The best linear approximation of f is recovered with the interpolation formula (7.203).

Subdivision Scheme

Let ϕ be an interpolation function that is the autocorrelation of an orthogonal scaling function ϕ_o. Let ϕ_j,n(t) = ϕ(2^−j t – n). The constant 2^−j/2 that normalizes the energy of ϕ_j,n is not added because we shall use a supremum norm ‖ f ‖∞ = sup_{t ε} |f (t)| instead of the L² () norm, and

We define the interpolation space V_j of functions

where a[n] has at most a polynomial growth in n. Since ϕ is an interpolation function, a [n] =g(2^j n). This space Vj is not included in L²() since a[n] may not have a finite energy. The scaling equation (7.194) implies that Vj+1 ⊂ V_j for any j ∈. If the autocorrelation filter h has a Fourier transform that has a zero of order p at ω = π, then Theorem 7.21 proves that polynomials of a degree smaller than p − 1 are included in V_j.

For f ∉ V_j, we define a simple projector on V_j that interpolates the dyadic samples f (2^j n):

(7.205)

This projector has no orthogonality property but satisfies P_Vj f (2^j n) = f (2^j n). Let C₀ be the space of functions that are uniformly continuous over . Theorem 7.22 proves that any f ε C₀ can be approximated with an arbitrary precision by P_Vj f when 2^j goes to zero.

Interpolation Wavelets

The projection P_Vj f (t) interpolates the values f (2^j n). When reducing the scale by 2, we obtain a finer interpolation P_Vj–1 f (t) that also goes through the intermediate samples f (2^j(n + 1/2)). This refinement can be obtained by adding “details” that compensate for the difference between P_Vjf (2^j(n + 1/2)) and f (2^j (n + 1/2)). To do this, we create a “detail” space W_j that provides the values f (t) at intermediate dyadic points t = 2^j (n + 1/2). This space is constructed from interpolation functions centered at these locations, namely ϕ_j–1,2n+1. We call interpolation wavelets

Observe that ψ_j,n(t) = ψ(2^−j t – n) with

The function ψ is not truly a wavelet since it has no vanishing moment. However, we shall see that it plays the same role as a wavelet in this decomposition. We define W_j to be the space of all sums . Theorem 7.23 proves that it is a (nonorthogonal) complement of V_j in V_j–1.

Fast Calculations

The interpolating wavelet transform of f is calculated at scale 1 ≥ 2^j > N⁻¹ = 2^L from its sample values {f(N⁻¹n)}_{n ε}. At each scale 2^j, the values of f in between samples {2^j n}_{n ε} are calculated with the interpolation (7.205):

(7.213)

where the interpolation filter h_i is a subsampling of the autocorrelation filter h in (7.195):

(7.214)

The wavelet coefficients are computed with (7.210):

The reconstruction of f (N⁻¹ n) from the wavelet coefficients is performed recursively by recovering the samples f (2^j–1 n) from the coarser sampling f (2^j n) with the interpolation (7.213) to which is added d_j[n]. If h_i[n] is a finite filter of size K and if f has a support in [0, 1], then the decomposition and reconstruction algorithms require KN multiplications and additions.

A Deslauriers-Dubuc interpolation function ϕ has the shortest support while including polynomials of degree 2p − 1 in the spaces V_j. The corresponding interpolation filter h_i[n] defined by (7.214) has 2p nonzero coefficients for –p ≤n < p, which are calculated in (7.201). If p = 2, then h_i[1] = h_i[–2] = −1/16 and h_i[0] = h_i[– 1] = 9/16. Suppose that q(t) is apolynomial of degree smaller or equal to 2p − 1. Since q = P_Vjq, (7.213) implies a Lagrange interpolation formula

The Lagrange filter h_i of size 2p is the shortest filter that recovers intermediate values of polynomials of degree 2p − 1 from a uniform sampling.

To restrict the wavelet interpolation bases to a finite interval [0, 1] while reproducing polynomials of degree 2p − 1, the filter h_i is modified at the boundaries. Suppose that f (N⁻¹ n) is defined for 0 ≤ n < N. When computing the interpolation

if n is too close to 0 or to 2^−j − 1, then h_i must be modified to ensure that the support of h_i [n – k] remains inside [0, 2^−j − 1]. The interpolation P_Vjf (2^j (n + 1/2)) is then calculated from the closest 2p samples f (2^j k) for 2^j k ε [0, 1]. The new interpolation coefficients are computed in order to recover exactly all polynomials of degree 2p − 1 [450]. For p = 2, the problem occurs only at n = 0 and the appropriate boundary coefficients are

The symmetric boundary filter h_i[–n] is used on the other side at n = 2^−j − 1.

Multiresolution Vision

An image of 512 × 512 pixels often includes too much information for real-time vision processing. Multiresolution algorithms process less image data by selecting the relevant details that are necessary to perform a particular recognition task [58]. The human visual system uses a similar strategy. The distribution of photoreceptors on the retina is not uniform. The visual acuity is greatest at the center of the retina where the density of receptors is maximum. When moving apart from the center, the resolution decreases proportionally to the distance from the retina center [428].

The high-resolution visual center is called the fovea. It is responsible for high-acuity tasks such as reading or recognition. A retina with a uniform resolution equal to the highest fovea resolution would require about 10,000 times more photoreceptors. Such a uniform resolution retina would increase considerably the size of the optic nerve that transmits the retina information to the visual cortex and the size of the visual cortex that processes these data.

Active vision strategies [83] compensate the nonuniformity of visual resolution with eye saccades, which move successively the fovea over regions of a scene with a high information content. These saccades are partly guided by the lower-resolution information gathered at the periphery of the retina. This multiresolution sensor has the advantage of providing high-resolution information at selected locations and a large field of view with relatively little data.

Multiresolution algorithms implement in software [125] the search for important high-resolution data. A uniform high-resolution image is measured by a camera but only a small part of this information is processed. Figure 7.21 displays a pyramid of progressively lower-resolution images calculated with a filter bank presented in Section 7.7.3. Coarse to fine algorithms analyze first the lower-resolution image and selectively increase the resolution in regions where more details are needed. Such algorithms have been developed for object recognition and stereo calculations [284].

FIGURE 7.21 Multiresolution approximations a_j [n₁, n₂] of an image at scales 2^j for −5≥ j≥ − 8.

Separable Biorthogonal Bases

One-dimensional biorthogonal wavelet bases are extended to separable biorthogonal bases of L² (²) with the same approach as in Theorem 7.25. Let ϕ, ψ and be two dual pairs of scaling functions and wavelets that generate biorthogonal wavelet bases of L² (). The dual wavelets of ψ¹, ψ², and ψ³ defined by (7.218) are

(7.224)

One can verify that

(7.225)

and

(7.226)

are biorthogonal Riesz bases of L² (²).

Finite Image and Complexity

When a_L is a finite image of N =N₁ N₂ pixels, we face boundary problems when computing the convolutions (7.227-7.231). Since the decomposition algorithm is separable along rows and columns, we use one of the three one-dimensional boundary techniques described in Section 7.5. The resulting values are decomposition coefficients in a wavelet basis of L²[0, 1]². Depending on the boundary treatment, this wavelet basis is a periodic basis, a folded basis, or a boundary adapted basis.

For square images with N₁ = N₂, the resulting images a_j and d^k_j have 2^−2j samples. Thus, the images of the wavelet representation (7.233) include a total of N samples. If h and g have size K, the reader can verify that 2K2^−2(j–1) multiplications and additions are needed to compute the four convolutions (7.227-7.230) with the factorization of Figure 7.25(a). Thus, the wavelet representation (7.233) is calculated with fewer than 8/3 KN operations. The reconstruction of a_L by factoring the reconstruction equation (7.231) requires the same number of operations.

Fast Biorthogonal Wavelet Transform

The decomposition of an image in a biorthogonal wavelet basis is performed with the same fast wavelet transform algorithm. Let (, ) be the perfect reconstruction filters associated to (h, g). The inverse wavelet transform is computed by replacing the filters (h, g) that appear in (7.231) by (, ).

Fast Wavelet Transform

Let b[n] be an input p-dimensional discrete signal sampled at intervals 2^L. We associate b[n] to an approximation f at the scale 2^L with scaling coefficients a_L [n] = 〈f, ψ⁰_L,n〉 that satisfy

The wavelet coefficients of f at scales 2^j > 2^L are computed with separable convolutions and subsamplings along the p signal dimensions. We denote

The fast wavelet transform is computed with filters that are separable products of the one-dimensional filters h and g. The separable p-dimensional low-pass filter is

Let us denote u⁰ [m] = h[m] and u¹ [m] =g[m]. To any integer ε = ε₁,…, ε_p written in a binary form, we associate a separable p-dimensional band-pass filter

Let . One can verify that

(7.235)

(7.236)

We denote by the signal obtained by adding a zero between any two samples of y[n] that are adjacent in the p-dimensional lattice n= (n₁, …, n_p). It doubles the size of y[n] along each direction. If y[n] has M^p samples, then y[n] has (2M)^p samples. The reconstruction is performed with

(7.237)

The 2^p separable convolutions needed to compute a_j and {d^ε_j}_{1≤ε ≤2p} as well as the reconstruction (7.237) can be factored in 2^p+1 − 2 groups of one-dimensional convolutions along the rows of p-dimensional signals. This is a generalization of the two-dimensional case, illustrated in Figure 7.25. The wavelet representation of a_L is

(7.238)

It is computed by iterating (7.235) and (7.236) for L ≤ j < J. The reconstruction of a_L is performed with the partial reconstruction (7.237) for J >j ≥ L.

If a_L is a finite signal of size N₁, …, N_p, the one-dimensional convolutions are modified with one of the three boundary techniques described in Section 7.5. The resulting algorithm computes decomposition coefficients in a separable wavelet basis of L²[0, 1]^p. If N₁ = … = N_p, the signals a_j and d^ε_j have 2^−pj samples. Like a_L, the wavelet representation (7.238) is composed of N samples. If the filter h has K nonzero samples, then the separable factorization of (7.235) and (7.236) requires pK2^−p(j–1) multiplications and additions. Thus, the wavelet representation (7.238) is computed with fewer than p (1 − 2^−p) ⁻¹KN multiplications and additions. The reconstruction is performed with the same number of operations.

Embedded Grids

Biorthogonal multiresolutions, defined in Section 7.4, are generalized by considering nested spaces

which are defined over embedded approximation grids G_j ⊂ G_J–1. Each index n ε G_j is associated to a sampling point x_n ε Ω. Since the sampling grids are embedded, this position does not change when the index is moved to finer grids n ε G_k for k ≤ j. Each space V_j is equipped with a Riesz basis {ϕ_j,n}_{n εGj} parameterized by the approximation grid G_j.

Embedded grids are decomposed with complementary grids C_j:

For example, over the interval [0, 1], the grid G_j–1 is the set of 2^j–1 n ∈ [0, 1] for 0 ≤ n < 2^−j. It is decomposed into the even grid points of 2^j–1 2n of G_j and the odd grid points 2^j–1(2n + 1) of C_j. A corresponding vector space decomposition is defined V_j–1 = V_j ⊕ W_j, where the detail space W_j has a Riesz basis of wavelets {ψ_j,m}_{m εCj} indexed on the complementary grid C_j.

A dual-biorthogonal wavelet family and a dual basis of scaling functions satisfy the biorthogonality conditions

(7.239)

The resulting wavelet families {ψ_j,m}_{m εGj,j ε} and are biorthogonal wavelet bases of L²(Ω), which implies that for any f ε L²(Ω),

where 2^J is an arbitrary coarsest scale. The difference with the biorthogonal wavelets of Section 7.4 is that scaling functions and wavelets are typically not translations and dilations of mother scaling functions and wavelets to be adapted to Ω. As a result, the decomposition filters are not convolution filters.

Spatially Varying Filters

The spatially varying filters associated to this biorthogonal multiresolution satisfy

(7.240)

Over a translation-invariant domain, h_j[n, l]= h[n − 2l] are the perfect reconstruction filters of Section 7.3.2. Dual filters and are defined similarly by

(7.241)

The biorthogonality relations (7.239) between wavelets and scaling functions imply equivalent biorthogonality filter relations for all n, n’ ε G_j and m, m’ ε C_j:

(7.242)

(7.243)

Wavelets and scaling functions can be written as an infinite product of these filters. If these products converge in L²(Ω) and the filters that satisfy (7.242) and (7.243), then the resulting wavelets and scaling functions define biorthogonal bases of L²(Ω), which satisfy (7.239) [452].

To simplify notations, the filters h_j and g_j are also written as matrices that transform discrete vector

and similarly for the dual matrices and .

The biorthogonality conditions (7.242) are rewritten as

(7.244)

where A* is the complex transpose of a matrix A.

Vanishing Moments

Wavelets with p₁ vanishing moments are orthogonal to polynomials of a degree strictly smaller than p₁. Let d₁ be the dimension of the space of polynomials of degree q − 1 in dimension d. If d = 1, then d₁ =p₁, and if d= 2, then d₁ = p₁(p₁ + 1) / 2. Such wavelets are orthogonal to a basis {q^(k)}_0≤k<d1 of this polynomial space, defined over Ω ⊂ ^d:

(7.245)

and similarly for dual wavelets with p₂ vanishing moments,

Lifting steps are used to increase the number of vanishing moments.

Lazy Wavelets

A lifting begins from lazy wavelets, which are Diracs on grid points. The lazy discrete orthogonal wavelet transform just splits the coefficients of a grid G_j–1 into the two subgrids G_j and C_j. It corresponds to filters that are Diracs on these grids:

For a ε ^|G_j–1|, the vector H^o_j a ε ^|G_j| is the restriction of a to G_j, and G^o_j a ε ^|C_j| is the restriction of a to C_j.

Since each index n ε G_j is associated to a sampling point x_n ε Ω that does not depend on the scale index j, one can verify that and , meaning that for any continuous function f (x):

This lazy wavelet basis is improved with a succession of liftings.

Increasing Vanishing Moments, Stability, and Regularity

A lifting modifies biorthogonal filters in order to increase the number of vanishing moments of the resulting biorthogonal wavelets, and hopefully their stability and regularity.

Increasing the number of vanishing moments decreases the amplitude of wavelet coefficients in regions where the signal is regular, which produces a more sparse representation. However, increasing the number of vanishing moments with a lifting also increases the wavelet support, which is an adverse effect that increases the number of large coefficients produced by isolated singularities.

Each lifting step maintains the filter biorthogonality but provides no control on the Riesz bounds and thus on the stability of the resulting wavelet biorthogonal basis. When a basis is orthogonal then the dual basis is equal to the original basis. Having a dual basis that is similar to the original basis is therefore an indication of stability. As a result, stability is generally improved when dual wavelets have as much vanishing moments as original wavelets and a support of similar size. This is why a lifting procedure also increases the number of vanishing moments of dual wavelets. It can also improve the regularity of the dual wavelet.

A lifting design is computed by adjusting the number of vanishing moments. The stability and regularity of the resulting biorthogonal wavelets are measured a posteriori, hoping for the best. This is the main weakness of this wavelet design procedure.

Prediction

Starting from an initial set of biorthogonal filters , a prediction step modifies each filter g^o_j to increase the number of vanishing moments of ψ_j,n. This is done with an operator P_j that predicts the values in the grid C_j from samples in the grid G_j:

The number of vanishing moments of ψ_j,n is increased by modifying the filter g^o_j with this predictor

(7.246)

Biorthogonality is maintained by also modifying the dual filter :

The filter lifting (7.246) implies a retransformation of the scaling and wavelet coefficients computed with the original filters h^o_j and g^o_j. The lifted scaling coefficients {a_j[n]= 〈 f, ϕ_j,n 〉}_{n εGj} and detail coefficients {d_j[m] = 〈 f, ψ_j,m}_{m εCj} are computed from the coefficients {d^o_j[m], a^o_j[n]}_{n εGj,m εCj} corresponding to h^o_j and g^o_j by applying the predict operator

while the scaling coefficients are not modified: a_j [n] = a^o_j [n]. If P_j is a good predictor of d^o_j [m] from a^o_j [n] on the coarse grid G_j, then the resulting coefficients d_j [m] are smaller, which is an indication that the wavelet has more vanishing moments.

The prediction (7.246) of the filters is rewritten with matrix notations

(7.247)

Since Hj = H^o_j is not modified, the scaling functions ϕ_j,n = ϕ^o_j,n are not modified. In contrast, since is modified, both the dual-scaling and wavelet functions are modified:

(7.248)

(7.249)

Theorem 7.27 proves that this lifting step maintains the biorthogonality conditions [451].

Update

The prediction (7.248) modifies ψ_j,n but does not change The roles of ψ_j,m and ψ_j,m are reversed by applying a lifting step to increase the number of vanishing moments of ψ_j,m as well. The goal is to obtain dual wavelets ψ_j,n that are as similar as possible to ψ_j,n in order to improve the stability of the basis. It requires the use of an update operator U_j defined by

The update step is then

(7.251)

Since predict and update steps are equivalent operations on dual filters, Theorem 7.27 shows that this update operation defines new filters that remain biorthogonal.

Let {d^o_j[m], a^o_j[n]}_{n εGj,m εCj} be the wavelet and scaling coefficients corresponding to the filters h^o_j and g^o_j The wavelet coefficients are not modified d_j [n] = d^o_j [n], and {a_j[n]}_{n εGj} is computed by applying the update operator

The updated scaling functions and wavelets are:

(7.252)

(7.253)

Theorem 7.28 proves that this update does not modify the number of vanishing moments of the analyzing wavelet.

Predict plus Update Design and Algorithm

Wavelets synthesized with a lifting are constructed with one predict step followed by one update step, because there is no technique that controls the wavelet stability and regularity over more lifting steps. Beginning from Dirac lazy wavelets with no vanishing moment, a prediction (7.247) obtains biorthogonal wavelets with, respectively, p₁ and zero vanishing moments. An update (7.251) then yields biorthogonal wavelets having, respectively, p₁ and p₂ vanishing moments.

A fast wavelet transform computes the coefficients

by replacing convolution with conjugate mirror filters by a succession of lifting and update steps. The algorithm takes in input a discrete signal a_L ε ^|G_L| of length N = |G_L|, and applies the lazy decomposition, a predict, and an update operator, as illustrated in Figure 7.26. For j = L + 1, …, J, it computes

FIGURE 7.26 Predict and update decomposition of a_j–1 into a_j and d_j, followed by the reconstruction of a_j–1 with the same update and predict operators.

This fast biorthogonal wavelet transform (7.157) requires O(N) operations.

The reconstruction of a_L from {d_j}_J≤j<L and a_J inverts these predict and update steps. For j = J, …, L + 1, it computes

Vanishing Moments

The predict and update filters are computed to create vanishing moments on the resulting wavelets. After the prediction applied to the lazy Diracs ψ^o_j,m (x) = δ(x – x_m), ϕ^o_j,n(x) = δ(x – x_n), the resulting wavelets and scaling functions derived from (7.248) and (7.249) are:

(7.256)

(7.257)

According to (7.250), the wavelet ψ¹_j,m has p₁ vanishing moments if for each m, the p₁ coefficients of {p_j[m, n]}_n solve the d₁ × d₁ linear system:

(7.258)

Following (7.253), after the update of the dual wavelet and the scaling functions, are

(7.259)

(7.260)

Theorem 7.28 proves that the vanishing moments of ψ^o_j,m are transferred to ψ²_j,m after the dual lifting step. According to (7.258), the dual wavelet has p₂ vanishing moments if for each m the d₂ coefficients of {u_j[m, n]}_n solve the d₂ × d₂ linear system:

(7.261)

The inner products I^k_j (n) are computed iteratively with (7.259):

(7.262)

The recurrence is initialized at the finest scale j = L by setting I^k_L (n) = q^(k) (x_n), where x_n ε Ω is the point associated to the index n ε G_L. More elaborated initializations using quadrature formula can also be used [427].

Linear Splines 5/3 Biorthogonal Wavelets

Linear spline wavelets are obtained with a two-step lifting construction beginning from lazy wavelets. The one-dimensional grid G_j–1 is a uniform sampling at intervals 2^j–1 and the two subgrids G_j and C_j correspond to even and odd subsampling. Figure 7.27 illustrates these embedded one-dimensional grids.

FIGURE 7.27 Predict and update steps for the construction of linear spline wavelets.

The lazy wavelet transform splits the coefficients a_j–1 into two groups

The value of d^o_j in C_j is predicted with a linear interpolation of neighbor values in G_j

(7.263)

This lifting step creates wavelets with two vanishing moments because this linear interpolation predicts exactly the values of polynomials of degree 0 and 1.

A symmetric update step computes

(7.264)

To obtain two vanishing moments, the inner products are computed iteratively with (7.262), using two nonzero update coefficients u_j [n, m − 2^j–1] and u_j [n, m + 2^j–1] for each m. For k = 0 we get . Since t is antisymmetric, if this equation is valid for k = 0 and if u_j[n, m − 2^j–1] = u_j[n, m + 2^j–1], then it is valid for k = 1. Solving (7.261) for k = 0 gives u_j[n, m − 2^j–1] = u_j[n, m + 2^j–1] = 1/4 and thus,

(7.265)

Figure 7.27 illustrates the succession of predict and update. One can verify (Exercise 7.20) that the resulting biorthogonal wavelets correspond to the spline biorthogonal wavelets computed with p₁ = p₂ = 2 vanishing moments (shown in Figure 7.15). The dual-scaling functions and wavelets are compactly supported linear splines. Higher-order biorthogonal spline wavelets are constructed with a prediction (7.263) and an update (7.264) providing more vanishing moments.

Semiregular Triangulation

A triangulation is a data structure frequently used to index points x_n ε Ω on a surface. Embedded indexes n ε G_j with a triangulation topology are defined by recursively subdividing a coarse triangulated mesh.

For each scale j, a triangulation (E_j, T_j) is composed of edges E_j ⊂ G_j × G_j that link pairs of points on the grid, and triangles T_j ⊂ G_j × G_j × G_j. Each triangle of T_j is composed of three edges in E_j. These triangulations are supposed to be embedded using the 1:4 subdivision rule of each triangle, illustrated in Figure 7.31, as follows.

For each edge e ε E_j, a midpoint γ(e) ε G_j–1 is added to the vertices

FIGURE 7.31 (a) Iterated regular subdivision 1:4 of one triangle in four equal subtriangles. (b) Planar triangulation (G₀, E₀, T₀) of a domain Ω in ², successively refined with a 1:4 subdivision.

Each edge is subdivided into two finer edges

The subdivided set of edges is then

Each triangle face f = (n₀, n₁, n₂) ε F_j is subdivided into four faces

The subdivided set of faces is then

Figure 7.31 shows an example of coarse planar triangulation with points x_n in a domain Ω of ².

The semiregular mesh {E_j, T_j}_j and the corresponding sample locations x_n are usually computed from an input surface S, represented either with a parametric continuous function or with an unstructured set of polygons. This requires using a hierarchical remeshing process to compute the embedded triangulation [354]. Figure 7.32 shows an example of semiregular triangulation of a three-dimensional surface S, and in this case the points x_n belong to a domain Ω that is the surface S in .

FIGURE 7.32 Examples of semiregular mesh {G_j, E_j, T_j}_j of a domain Ω that is a surface S in ³.

Wavelets to Process Functions on Surfaces

Let us consider a domain Ω ε ³ that is a three-dimensional surface, and each n ε G_j indexes a point x_n ε Ω of the surface. Figure 7.33 shows the local labeling convention for the neighboring vertices in G_j of a given index m ε C_j in a butterfly neighborhood.

FIGURE 7.33 Labeling of points in the butterfly neighborhood of a vertex m ε C_j.

A predictor P_j is computed in this local neighborhood

(7.268)

where the parameters Λ_i, μ_i, v_i,j are calculated by solving (7.258) to obtain vanishing moments for a collection of low-degree polynomials {q^(k)}_0≤k<d1 [427].

The update operator ensures that the dual wavelets have one vanishing moment. It is calculated on the direct neighbors in C_j of each point n ε G_j:

The update operator is parameterized as follows:

(7.269)

where each Λ_n is computed to solve the system (7.261) to obtain vanishing moments. This requires the iterative computation of the moments I^k_j (n), as explained in (7.262), with an initialization I^k_L (n) = 1 at the finest scale L of the mesh. In a perfectly regular triangulation, where all the points have six neighbors, a constant weight Λ_n = Λ can be used, and one can check that Λ_n = 1/24 guarantees one vanishing moment.

Processing signals on a sphere is an important application of these wavelets on surfaces [427]. The triangulated mesh is obtained by a 1:4 subdivision of a regular polyhedron, for instance a tetrahedron. The positions of the points x_n for n ε G_j are defined recursively by projecting midpoints of the edges on the sphere:

The signal is defined on the finest mesh G_L.

A nonlinear approximation is obtained by setting to zero wavelet coefficients that satisfy |〈f, ψ_j,m〉 | ≤ T ‖ψ_j,m ‖ where T is a given threshold. The value of ‖ψ_j,m‖ can be approximated from the size of its support [427]. Figure 7.34 shows an example of such a nonlinear approximation with an image of Earth defined as a function on the sphere.

FIGURE 7.34 Nonlinear approximation of a function defined on a sphere using a decreasing number of large wavelet coefficients.

Wavelets to Process Surfaces

A three-dimensional surface S ⊂ ³ is represented as a mapping from a two-dimensional parameter domain Ω to ³. This surface is discretized with a semiregular mesh {G_j, E_j, T_j}_L≤j≤0, and thus Ω can be chosen as the finest grid G_L viewed as an abstract domain. The surface is a discrete mapping from Ω = G_L to ³ that assigns to each n ε Ω three values (f₁ [n], f₂ [n], f₃ [n]) ε S, which is a position in the three-dimensional space.

Processing the discrete surface is equivalent to processing the three signals (f₁, f₂, f₃) where each is defined on the finest grid G_L. Since points in the parametric domain Ω do not have positions in Euclidean space, the notion of vanishing moments is not well defined, and the predict operator is computed using weights that are calculated as if the faces of the mesh were equilateral triangles. One can verify that the resulting parameters of the predict operator (7.268) are Λ_i = 1/2, μ_i = 1/4, and v_i,j = − 1/16 [427]. Figure 7.35 shows the corresponding wavelets on a subdivided equilateral triangle.

FIGURE 7.35 Example of dual wavelets for x on a subdivided equilateral triangle. The height over the triangle indicates the value of the wavelet.

These wavelets are used to compress each of the three signals by uniformly quantizing the normalized coefficients 〈f_i, ψ_j,m〉 / ‖ ψ_j,m ‖. The resulting set of quantized coefficients are within strings with an entropy coder algorithm, described in Section 10.2.1. The quantization and coding of sparse signal representation is described in Section 10.4.

Figure 7.36 shows an example of three-dimensional surface approximation using biorthogonal wavelets on triangulated meshes. Wavelet coders based on lifting offer state-of-the-art results in surface compression [327]. There is no control on the Riesz bounds of the lifted wavelet basis, because the lifted basis depends on the surface properties, but good approximation results are obtained.

FIGURE 7.36 Nonlinear surface approximation using a decreasing proportion of large wavelet coefficients.

Symmetric Lifting on the Interval

The lifting implementation is described in more detail for symmetric wavelets on an interval, corresponding to symmetric biorthogonal filters . Predict and update convolutions are modified at the boundaries to implement folding boundary conditions.

The input sampling grid G_L has N = 2^−L samples at integer positions 0 ≤ n < N. The embedded subgrids at scales 0 ≥ 2^j > 2^L are

(7.272)

The resulting lifting operators {P^(k), U^(k)}_1≤k≤K are two-tap symmetric convolution operators. A prediction of parameter Λ is defined by

(7.273)

An update of parameter μ is defined as

(7.274)

At the interval boundaries, the predict and update operators must be modified for m = N – N 2^j–1 in (7.273) and n = 0 in (7.274), because one of the two neighbors falls outside the grids G_j and C_j.

Symmetric boundary conditions, described in Section 7.5.2, are implemented with a folding, which leads to the following definition of boundary predict and update operators:

This ensures that the lifting operators have one vanishing moment, and that the resulting boundary wavelets also have one vanishing moment.

Factorization of 5/3 and 9/7 Biorthogonal Wavelets

The 9/7 biorthogonal and 5/3 wavelets in Figure 7.15 are recommended for image compression in JPEG-2000 and are often used in wavelet image-processing applications. The 5/3 biorthogonal wavelet has p₁ = p₂ = 2 vanishing moments, while the 9/7 wavelet has p₁ = p₂ = 4 vanishing moments.

The 5/3 wavelet transform is implemented with K = 1 pair of predict and update steps, presented in Section 7.8.2. They correspond to

The 9/7 wavelet transform is implemented with K = 2 pairs of predict and update steps defined as

and the scaling constant is ζ = 1.1496043988602.