Frame Synthesis

Let us consider the space of finite energy coefficients

The adjoint Φ* of Φ is defined over ²(Γ) and satisfies for any f ∈ H and a ∈ ²(Γ):

It is therefore the synthesis operator

(5.3)

The frame condition (5.2) can be rewritten as

(5.4)

with

It results that A and B are the infimum and supremum values of the spectrum of the symmetric operator Φ*Φ, which correspond to the smallest and largest eigenvalues in finite dimension. The eigenvalues are also called singular values of Φ or singular spectrum. Theorem 5.1 derives that the frame synthesis operator is also stable.

Redundancy

When the frame vectors are normalized ‖φ_n‖ = 1, Theorem 5.2 shows that the frame redundancy is measured by the frame bounds A and B.

Irregular Sampling

Let U_s be the space of L²() functions having a Fourier transform support included in [−π/s, π/s]. For a uniform sampling, t_n = ns, Theorem 3.5 proves that if φ_s(t) = s^1/2 sin(π/s⁻¹ t)/(πt), then {φ_s(t − ns)}_n∈ is an orthonormal basis of U_s. The reconstruction of f from its samples is then given by the sampling Theorem 3.2.

The irregular sampling conditions of Duffin and Schaeffer [235] for constructing a frame were later refined by several researchers [81, 102, 500]. Gröchenig proved [285] that if and , and if the maximum sampling distance δ satisfies

(5.8)

then

is a frame with frame bounds A ≥ (1 – δ/s)² and B ≤ (1 + δ/s)². The amplitude factor λ_n compensates for the increase of sample density relatively to s. The reconstruction of f requires inverting the frame operator Φf[n] = 〈f(u), λ_n, φ_s(u – t_n)〉.

Dual Frame

The pseudo inverse of a frame operator implements a reconstruction with a dual frame, which is specified by Theorem 5.5.

Biorthogonal Bases

A Riesz basis is a frame of vectors that are linearly independent, which implies that ImΦ = ²(Γ), so its dual frame is also linearly independent. Inserting f = φ_p in (5.12) yields

and the linear independence implies that

Thus, dual Riesz bases are biorthogonal families of vectors. If the basis is normalized (i.e., ‖φ_n‖ = 1), then

(5.19)

This is proved by inserting f = φ_p in the frame inequality (5.13):

Dual Synthesis

In a dual synthesis problem, the orthogonal projection is computed from the frame coefficients {Φf[n] = 〈f, φ_n〉}_n∈T with the dual-frame synthesis operator:

(5.22)

If the frame {φ_n}_n∈Γ does not depend on the signal f, then the dual-frame vectors are precomputed with (5.11):

(5.23)

and the dual synthesis is solved directly with (5.22). In many applications, the frame vectors {φ_n}_n∈Γ depend on the signal f, in which case the dual-frame vectors cannot be computed in advance, and it is highly inefficient to compute them. This is the case when coefficients {〈f, φ_n〉}_n∈Γ are selected in a redundant transform, to build a sparse signal representation. For example, the time-frequency ridge vectors in Sections 4.4.2 and 4.4.3 are selected from the local maxima of f in highly redundant windowed Fourier or wavelet transforms.

The transform coefficients Φf are known and we must compute

A dual-synthesis algorithm computes first

and then derives P_V f = L⁻¹ y = z by applying the inverse of the symmetric operator L = Φ*Φ_V to y, with

(5.24)

The eigenvalues of L are between A and B.

Dual Analysis

In a dual analysis, the orthogonal projection P_Vf is computed from the frame vectors {φ_n}_n∈Γ with the dual-frame analysis operator :

(5.25)

If {φ_n}_n∈Γ does not depend upon f then is precomputed with (5.23). The {φ_n}_n∈Γ may also be selected adaptively from a larger dictionary, to provide a sparse approximation of f. Computing the orthogonal projection P_Vf is called a backprojection. In Section 12.3, matching pursuits implement this backprojection.

When {φ_n}_n∈Γ depends on f, computing the dual frame is inefficient. The dual coefficient is calculated directly, as well as

(5.26)

Since ΦP_V f = Φf, we have Φ Φ*a = Φf. Let Φ*_ImΦ be the restriction of Φ* to ImΦ. Since Φ Φ*_ImΦ is invertible on ImΦ

Thus, the dual-analysis algorithm computes y = Φf = {〈f, φ_n〉}_n∈Γ and derives the dual coefficients a = L⁻¹ y = z by applying the inverse of the Gram operator L = Φ Φ*_ImΦ to y, with

(5.27)

The eigenvalues of L are also between A and B. The orthogonal projection of f is recovered with (5.26).

Richardson Inversion of Symmetric Operators

The key computational step of a dual-analysis or a dual-synthesis problem is to compute z = L⁻¹y, where L is a symmetric operator with eigenvalues that are between A and B. Theorems 5.7 and 5.8 describe two iterative algorithms with exponential convergence. The Richardson iteration procedure is simpler but requires knowing the frame bounds A and B. Conjugate gradient iterations converge more quickly when B/A is large, and do not require knowing the values of A and B.

Conjugate-Gradient Inversion

The conjugate-gradient algorithm computes z = L⁻¹ y with a gradient descent along orthogonal directions with respect to the norm induced by the symmetric operator L:

(5.36)

This L norm is used to estimate the error. Gröchenig’s [287] implementation of the conjugate-gradient algorithm is given by Theorem 5.8.

Noise Reduction

Suppose that each frame coefficient Φf[n] is contaminated by an additive noise W[n], which is a random variable. Applying the projector P gives

with

Since P is an orthogonal projector, ‖PW‖ ≤ ‖W‖. This projector removes the component of W that is in (ImΦ)^⊥. Increasing the redundancy of the frame reduces the size of ImΦ and thus increases (ImΦ)^⊥, so a larger portion of the noise is removed. If W is a white noise, its energy is uniformly distributed in the space ²(Γ). Theorem 5.10 proves that its energy is reduced by at least A if the frame vectors are normalized.

Oversampling

This noise-reduction strategy is used by high-precision analog-to-digital converters. After a low-pass filter, a band-limited analog signal f(t) is uniformly sampled and quantized. In hardware, it is often easier to increase the sampling rate rather than the quantization precision. Increasing the sampling rate introduces a redundancy between the sample values of the band-limited signal. Thus, these samples can be interpreted as frame coefficients. For a wide range of signals it has been shown that the quantization error is nearly a white noise [277]. Thus, it can be significantly reduced by a frame projector, which in this case is a low-pass convolution operator (Exercise 5.16).

The noise can be further reduced if it is not white and if its energy is better concentrated in (ImΦ)^⊥. This can be done by transforming the quantization noise into a noise that has energy mostly concentrated at high frequencies. Sigma-delta modulators produce such quantization noises by integrating the signal before its quantization [89]. To compensate for the integration, the quantized signal is differentiated. This differentiation increases the energy of the quantized noise at high frequencies and reduces its energy at low frequencies [456].

Discrete Translation-Invariant Frames

For finite-dimensional signals f[n] ∈ ^N a circular translation-invariant frame is obtained with a periodic shift modulo N of a finite number of generators

Such translation-invariant frames appear in Section 11.2.3 to define translation-invariant thresholding estimators for noise removal. Similar to Theorem 5.11, Theorem 5.12 gives a necessary and sufficient condition on the discrete Fourier transform of the generators φ_m[n] to obtain a frame.

Reconstructing Wavelets

Reconstructing wavelets that satisfy (5.49) are calculated with a pair of finite impulse response dual filters ĥ and ĝ. We suppose that the following Fourier transform has a finite energy:

(5.61)

Let us define

(5.62)

Theorem 5.13 gives a sufficient condition to guarantee that is the Fourier transform of a reconstruction wavelet.

Finite Impulse Response Solution

Let us shift h and g to obtain causal filters. The resulting transfer functions ĥ(ω) and ĝ(ω) are polynomials in e^{−i ω}. We suppose that these polynomials have no common zeros. The Bezout theorem (7.8) on polynomials proves that if P(z) and Q(z) are two polynomials of degree n and l, with no common zeros, then there exists a unique pair of polynomials and of degree l − 1 and n − 1 such that

(5.65)

This guarantees the existence of and , which are polynomials in e^{−i ω} and satisfy (5.63). These are the Fourier transforms of the finite impulse response filters and . However, one must be careful, because the resulting scaling function in (5.61) does not necessarily have a finite energy.

Spline Dyadic Wavelets

A box spline of degree m is a translation of m + 1 convolutions of 1_{[0, 1]} with itself. It is centered at t = 1/2 if m is even and at t = 0 if m is odd. Its Fourier transform is

(5.66)

so

(5.67)

We construct a wavelet that has one vanishing moment by choosing ĝ(ω) = O(ω) in the neighborhood of Ω = 0. For example,

(5.68)

The Fourier transform of the resulting wavelet is

(5.69)

It is the first derivative of a box spline of degree m + 1 centered at t = (1 + ε)/4. For m = 2, Figure 5.3 shows the resulting quadratic splines φ and ϕ. The dyadic admissibility condition (5.48) is verified numerically for A = 0.505 and B = 0.522.

To design dual-scaling functions and wavelets that are splines, we choose As a consequence, and the reconstruction condition (5.63) imply that

(5.70)

Table 5.1 gives the corresponding filters for m = 2.

Table 5.1 Coefficients of Filters Computed from the Transfer Functions (5.67, 5.68, 5.70) for m = 2

Fast Dyadic Transform

The samples a₀[n] of the input discrete signal are written as a low-pass filtering with φ of an analog signal f, in the neighborhood of t = n:

This is further justified in Section 7.3.1. For any j ≥ 0, we denote

The dyadic wavelet coefficients are computed for j > 0 over the integer grid

For any filter x[n], we denote by x_j[n] the filters obtained by inserting 2^f − 1 zeros between each sample of x[n]. Its Fourier transform is . Inserting zeros in the filters creates holes (trous in French). Let . Theorem 5.14 gives convolution formulas that are cascaded to compute a dyadic wavelet transform and its inverse.

Theorem 5.14.

For any j ≥ 0,

(5.71)

and

(5.72)

Proof of (5.71).

Since

we verify with (3.3) that their Fourier transforms are, respectively,

and

The properties (5.61) and (5.62) imply that

Since j ≥ 0, both ĥ(2^j ω) and ĝ(2^j ω) are 2π periodic, so

(5.73)

These two equations are the Fourier transforms of (5.71).

Proof of (5.72).

Equation (5.73) implies

Inserting the reconstruction condition (5.63) proves that

which is the Fourier transform of (5.72).

The dyadic wavelet representation of a₀ is defined as the set of wavelet coefficients up to a scale 2^J plus the remaining low-frequency information a_J:

(5.74)

It is computed from a₀ by cascading the convolutions (5.71) for 0 ≤ j < J, as illustrated in Figure 5.4(a). The dyadic wavelet transform of Figure 5.2 is calculated with the filter bank algorithm. The original signal a₀ is recovered from its wavelet representation (5.74) by iterating (5.72) for J > j ≥ 0, as illustrated in Figure 5.4(b).

FIGURE 5.4 (a) The dyadic wavelet coefficients are computed by cascading convolutions with dilated filters and . (b) The original signal is reconstructed through convolutions with and . A multiplication by 1/2 is necessary to recover the next finer scale signal a_j.

If the input signal a₀[n] has a finite size of N samples, the convolutions (5.71) are replaced by circular convolutions. The maximum scale 2^J is then limited to N, and for J = log₂ N, one can verify that a_J[n] is constant and equal to N^−1/2 Σ^{N − 1}_n=0a₀[n]. Suppose that h and g have, respectively, K_h and K_g nonzero samples. The “dilated” filters h_j and g_j have the same number of nonzero coefficients. Therefore, the number of multiplications needed to compute a_j+1 and d_j+1 from a_j or the reverse is equal to (K_h + K_g)N. Thus, for J = log₂ N, the dyadic wavelet representation (5.74) and its inverse are calculated with (K_h + K_g)N log₂ N multiplications and additions.

Necessary Conditions

We suppose that ψ is real, normalized, and satisfies the admissibility condition of Theorem 4.4:

(5.75)

Sufficient Conditions

Theorem 5.16 proved by Daubechies [19] provides a lower and upper bound for the frame bounds A and B, depending on ψ, u₀, and a.

Dual Frame

Theorem 5.5 gives a general formula for computing the dual-wavelet frame vectors

(5.81)

One could reasonably hope that the dual functions would be obtained by scaling and translating a dual wavelet . The unfortunate reality is that this is generally not true. In general, the operator Φ*Φ does not commute with dilations by a^j, so (Φ*Φ)⁻¹ does not commute with these dilations either. On the other hand, one can prove that (Φ*Φ)⁻¹ commutes with translations by na^ju₀, which means that

(5.82)

Thus, the dual frame is obtained by calculating each elementary function with (5.81), and translating them with (5.82). The situation is much simpler for tight frames, where the dual frame is equal to the original wavelet frame.

Mexican Hat Wavelet

The normalized second derivative of a Gaussian is

(5.83)

Its Fourier transform is

The graph of these functions is shown in Figure 4.6.

The dilation step a is generally set to be a = 2^1/v where v is the number of intermediate scales (voices) for each octave. Table 5.2 gives the estimated frame bounds A₀ and B₀ computed by Daubechies [19] with the formula of Theorem 5.16. For v ≥ 2 voices per octave, the frame is nearly tight when u₀ ≤ 0.5, in which case the dual frame can be approximated by the original wavelet frame. As expected from (5.76), when A ≈ B,

Table 5.2 Estimated Frame Bounds for the Mexican Hat Wavelet

The frame bounds increase proportionally to v/u₀. For a = 2, we see that A₀ decreases brutally from u₀ = 1 to u₀ = 1.5. For u₀ = 1.75, the wavelet family is not a frame anymore. For a = 2^1/2, the same transition appears for a larger u₀.

Window Scaling

Suppose that {g_n,k}_(n,k)∈² is a frame of L²() with frame bounds A and B. Let us dilate the window g_s(t) = s^−1/2g(t/s). It increases by s the time width of the Heisenberg box of g and reduces by s its frequency width. Thus, we obtain the same cover of the time-frequency plane by increasing u₀ by s and reducing ξ₀ by s. Let

(5.84)

We prove that {g_s,n,k}_(n,k)∈² satisfies the same frame inequalities as {g_n,k}_(n,k)∈², with the same frame bounds A and B, by a change of variable t′ = ts in the inner product integrals.

Discrete Window Fourier Tight Frames

To construct a windowed Fourier tight frame of ^N, the Fourier basis {e^ikξ₀t}_k∈ of L²[−π/ξ₀, π/ξ₀] is replaced by the discrete Fourier basis {e^i2πkn/K}_0≤k<K of ^K. Theorem 5.18 is a discrete equivalent of Theorem 5.17.

Theorem 5.18.

Let g[n] be an N periodic discrete window with a support and restricted to [−N/2, N/2] that is included in [−K/2, K/2 − 1]. If M divides N and

(5.86)

then {g_m,k[n] = g[n − mM]e^i2πkn/K}_{0≤k<K, 0≥m<N/M} is a tight frame N with a frame bound equal to A.

The proof of this theorem follows the same steps as the proof of Theorem 5.17. It is left in Exercise 5.10. There are N/M translated windows and thus NK/M windowed Fourier coefficients. For a fixed window position indexed by m, the discrete windowed Fourier coefficients are the discrete Fourier coefficients of the windowed signal

They are computed with O(K log₂ K) operations with an FFT Overall windows, this requires a total of O(NK/M log₂ K) operations. We generally choose 1 < K/M ≤ 2 so that only consecutive windows overlap. The square root of a Hanning window g[n] = √2/K cos(πn/K) satisfies (5.86) for M = K/2 and a redundancy factor A = 2. Figure 5.7 shows the log spectrogram log |Sf[m, k]|² of the windowed Fourier frame coefficients computed with a square root Hanning window for a musical recording.

FIGURE 5.7 (a) Musical recording. (b) Log spectrogram log |S f[m, k]|² computed with a square root Hanning window.

Sufficient Conditions

Theorem 5.21 proved by Daubechies [195] gives sufficient conditions on u₀ξ₀, and g for constructing a windowed Fourier frame.

Dual Frame

Theorem 5.5 proves that the dual-windowed frame vectors are

(5.96)

Theorem 5.22 shows that this dual frame is also a windowed Fourier frame, which means that its vectors are time and frequency translations of a new window ĝ.

Gaussian Window

The Gaussian window

(5.98)

has a Fourier transform ĝ that is a Gaussian with the same variance. The time and frequency spreads of this window are identical. Therefore, let us choose equal sampling intervals in time and frequency: u₀ = ξ₀. For the same product u₀ξ₀ other choices would degrade the frame bounds. If g is dilated by s then the time and frequency sampling intervals must become su₀ and ξ₀/s.

If the time-frequency sampling density is above the critical value of 2π/(u₀ξ₀) > 1, then Daubechies [195] proves that {g_n,k}_(n,k)∈² is a frame. When u₀ξ₀ tends to 2π, the frame bound A tends to 0. For u₀ξ₀ = 2π, the family {g_n,k}_(n,k)∈² is complete in L²(), which means that any f ∈ L²() is entirely characterized by the inner products {〈f, g_n,k〉}_(n,k)∈². However, the Balian-Low theorem (5.20) proves that it cannot be a frame and one can indeed verify that A = 0 [195]. This means that the reconstruction of f from these inner products is unstable.

Table 5.3 gives the estimated frame bounds A₀ and B₀ calculated with Theorem 5.21, for different values of u₀ = ξ₀. For u₀ξ₀ = π/2, which corresponds to time and frequency sampling intervals that are half the critical sampling rate, the frame is nearly tight. As expected, A ≈ B ≈ 4, which verifies that the redundancy factor is 4 (2 in time and 2 in frequency). Since the frame is almost tight, the dual frame is approximately equal to the original frame, which means that When u₀ξ₀ increases we see that A decreases to zero and deviates more and more from a Gaussian. In the limit u₀ξ₀ = 2π, the dual window is a discontinuous function that does not belong to L²(). These results can be extended to discrete windowed Fourier transforms computed with a discretized Gaussian window [501].

Table 5.3 Frame Bounds for the Gaussian Window (5.98) and u₀ = ξ₀

Gabor Wavelets

In the cat’s visual cortex, Hubel and Wiesel [306] discovered a class of cells, called simple cells, having a response that depends on the frequency and direction of the visual stimuli. Numerous physiological experiments [401] have shown that these cells can be modeled as linear filters with impulse responses that have been measured at different locations of the visual cortex. Daugmann [200] showed that these impulse responses can be approximated by Gabor wavelets, obtained with a Gaussian window multiplied by a sinusoidal wave:

(5.104)

These findings suggest the existence of some sort of wavelet transform in the visual cortex, combined with subsequent nonlinearities [403]. The “physiological” wavelets have a frequency resolution on the order of 1 to 1.5 octaves, and are thus similar to dyadic wavelets.

The Fourier transform of g(x₁, x₂) is . It results from (5.104) that

In the Fourier plane, the energy of this Gabor wavelet is mostly concentrated around (−2^−j η sin α, 2^−j η cos α), in a neighborhood proportional to 2^−j.

The direction is chosen to be uniform a = lπ/K for −K < l ≤ K. Figure 5.8 shows a cover of the frequency plane by dyadic Gabor wavelets 5.105 with K = 6. If K ≥ 4 and η is of the order of 1 then 5.101 is satisfied with stable bounds. Since images f(x) are real, and f can be reconstructed by covering only half of the frequency plane, with −K < l ≤ 0. This is a two-dimensional equivalent of the one-dimensional analytic wavelet transform, studied in Section 4.3.2, with wavelets having a Fourier transform support restricted to positive frequencies. For texture analysis, Gabor wavelets provide information on the local image frequencies.

FIGURE 5.8 Each circle represents the frequency domain in a direction α + π/2 where the amplitude of a Gabor wavelet Fourier transform is large. It is proportional to 2^−j and its position rotates with α.

Texture Discrimination

Despite many attempts, there are no appropriate mathematical models for “homogeneous image textures.” The notion of texture homogeneity is still defined with respect to our visual perception. A texture is said to be homogeneous if it is preattentively perceived as being homogeneous by a human observer.

The texton theory of Julesz [322] was a first important step in understanding the different parameters that influence the perception of textures. The direction of texture elements and their frequency content seem to be important clues for discrimination. This motivated early researchers to study the repartition of texture energy in the Fourier domain [92]. For segmentation purposes it is necessary to localize texture measurements over neighborhoods of varying sizes. Thus, the Fourier transform was replaced by localized energy measurements at the output of filter banks that compute a wavelet transform [315, 338, 402, 467]. Besides the algorithmic efficiency of this approach, this model is partly supported by physiological studies of the visual cortex.

Since , Gabor wavelet coefficients measure the energy of f in a spatial neighborhood of u of size 2^j, and in a frequency neighborhood of (−2^−j η sin α, 2^−j η cos α) of size 2^−j, where the support of is located, illustrated in Figure 5.8. Varying the scale 2^j and the angle α modifies the frequency channel [119]. The wavelet transform energy |W f(u, 2^j, α)|² is large when the angle α and scale 2^j match the direction and scale of high-energy texture components in the neighborhood of u. Thus, the amplitude of |W f(u, 2^j, α)|² can be used to discriminate textures. Figure 5.9 shows the dyadic wavelet transform of two textures, computed along horizontal and vertical directions, at the scales 2⁻⁴ and 2⁻⁵ (the image support is normalized to [0, 1]²). The central texture is regular vertically and has more energy along horizontal high frequencies than the peripheric texture. These two textures are therefore discriminated by the wavelet of angle α = π/2, whereas the other wavelet with α = 0 produces similar responses for both textures.

FIGURE 5.9 Directional Gabor wavelet transform |W f(u, 2^j, α)|² of a texture patch, at the scales 2^j = 2⁻⁴, 2⁻⁵, along two directions α = 0, π/2. The darker the pixel, the larger the wavelet coefficient amplitude.

For segmentation, one must design an algorithm that aggregates the wavelet responses at all scales and directions in order to find the boundaries of homogeneous textured regions. Both clustering procedures and detection of sharp transitions over wavelet energy measurements have been used to segment the image [315, 402, 467]. These algorithms work well experimentally but rely on ad hoc parameter settings.

Steerable Wavelets

Steerable directional wavelets along any angle α can be written as a linear expansion of few mother wavelets [441]. For example, a steerable wavelet in the direction α can be defined as the partial derivative of order p of a window p(x) in the direction of the vector = (− sin α, cos α):

(5.105)

Let R_α be the planar rotation by an angle α. If the window is invariant under rotations θ(x) = θ(R_αx), then these wavelets are generated by the rotation of a single mother wavelet: ψ^α(x) = ψ(R_αx) with ψ = ∂^pθ/∂x^p₂.

Furthermore, the expansion of the derivatives in (5.105) proves that each ψ^α can be expressed as a linear combination of p + 1 partial derivatives

(5.106)

with

The waveforms ρⁱ (x) can also be considered as wavelets functions with vanishing moments. It results from 5.106 that the directional wavelet transform at any angle α can be calculated from p + 1 convolutions of f with the ρⁱ dilated:

Exercise 5.22 gives conditions on θ so that for a set θ of p + 1 angles α = kπ/(p + 1) with 0 ≤ k < p the resulting oriented wavelets ψ^α define a family of dyadic wavelets that satisfy 5.101. Section 6.3 uses such directional wavelets, with p = 1, to detect multiscale edges in images.

Discretization of the Translation

A translation-invariant wavelet transforms W f(u, 2^j, α) for all scales 2^j, and angle α requires a large amount of memory. To reduce computation and memory storage, the translation parameter is discretized. In the one-dimensional case a frame is obtained by uniformly sampling the translation parameter u with intervals u₀2^j n with n = (n₁, n₂) ∈ ², proportional to the scale 2^j. The discretized wavelet derived from the translation-invariant wavelet family (5.100) is

(5.107)

Necessary and sufficient conditions similar to Theorems 5.15 and 5.16 can be established to guarantee that such a wavelet family defines a frame of L²(²).

To decompose images in such wavelet frames with a fast filter filter bank, directional wavelets can be synthesized as a product of discrete filters. The steerable pyramid of Simoncelli et al. [441] decomposes images in such a directional wavelet frame, with a cascade of convolutions with low-pass filters and directional band-pass filters. The filter coefficients are optimized to yield wavelets that satisfy approximately the steerability condition 5.106 and produce a tight frame. The sampling interval is u₀ = 1/2.

Figure 5.10 shows an example of decomposition on such a steerable pyramid with K = 4 directions. For discrete images of N pixels, the finest scale is 2^j = 2N⁻¹. Since u₀ = 1/2, wavelet coefficients at the finest scale define an image of N pixels for each direction. The wavelet image size then decreases as the scale 2^j increases. The total number of wavelet coefficients is 4KN/3 and the tight frame factor is 4K/3 [441]. Steerable wavelet frames are used to remove noise with wavelet thresholding estimators [404] and for texture analysis and synthesis [438].

FIGURE 5.10 Decomposition of an image in a frame of steerable directional wavelets [441] along four directions: α = 0, π/4, π/2, 3π/4, at two consecutive scales, 2^j and 2^j + 1. Black, gray, and white pixels correspond respectively to wavelet coefficients of negative, zero, and positive values.

Chapter 9 explains that sparse image representation can be obtained by keeping large-amplitude coefficients above a threshold. Large-amplitude wavelet coefficients appear where the image has a sharp transition, when the wavelet oscillates in a direction approximately perpendicular to the direction of the edge. However, even when directions are not perfectly aligned, wavelet coefficients remain nonnegligible in the neighborhood of edges. Thus, the number of large-amplitude wavelet coefficients is typically proportional to the length of edges in images. Reducing the number of large coefficients requires using waveforms that are more sensitive to direction properties, as shown in the next section.

Dyadic Curvelet Transform

A curvelet is function c(x) having vanishing moments along the horizontal direction like a wavelet. However, as opposed to wavelets, dilated curvelets are obtained with a parabolic scaling law that produces highly elongated waveforms at fine scales:

(5.108)

They have a width proportional to their length². Dilated curvelets are then rotated c^α_2^j = c_2^j (R_αx), where R_α is the planar rotation of angle α, and translated like wavelets: c^α_{2^j, u} = c^α_2^j (x − u). The resulting translation-invariant dyadic curvelet transform of f ∈ L²(²) is defined by

To obtain a tight frame, the Fourier transform of a curvelet at a scale 2^j is defined by

(5.109)

where is the Fourier transform of a one-dimensional wavelet and is a one-dimensional angular window that localizes the frequency support of ĉ_2^j in a polar parabolic wedge, illustrated in Figure 5.11. The wavelet is chosen to have a compact support in [1/2, 2] and satisfies the dyadic frequency covering:

FIGURE 5.11 (a) Example of curvelet c^α_{2^j, u} (x). (b) The frequency support of ĉ^α_{2^j, u} (ω) is a wedge obtained as a product of a radial window with an angular window.

(5.110)

One may, for example, choose a Meyer wavelet as defined in (7.82). The angular window is chosen to be supported in [−1, 1] and satisfies

(5.111)

As a result of these two properties, one can verify that for uniformly distributed angles,

curvelets cover the frequency plane

(5.112)

Real valued curvelets are obtained with a symmetric version of 5.109: ĉ_2^j (ω) + ĉ_2^j (−ω). Applying Theorem 5.11 proves that a translation-invariant dyadic curvelet dictionary {c^α_{2^j, u}}_{α∈θj, j∈, u∈²} is a dyadic translation-invariant tight frame that defines a complete and stable signal representation [142].

Curvelet Properties

Since ĉ_2^j(ω) is a smooth function with a support included in a rectangle of size proportional to 2^−j/2 × 2^−j, the spatial curvelet c_2^j (x) is a regular function with a fast decay outside a rectangle of size 2^−j/2 × 2^j. The rotated and translated curvelet c^α_{2^j, u} is supported around the point u in an elongated rectangle along the direction α; its shape has a parabolic ratio width = length², as shown in Figure 5.11.

Since the Fourier transform ĉ_2^j (Ω₁, Ω₂) is zero in the neighborhood of the vertical axis Ω₁ = 0, c_2^j(x₁, x₂) has an infinite number of vanishing moments in the horizontal direction

A rotated curvelet c^α_{2^j, u} has vanishing moments in the direction α + π/2, and therefore oscillates in the direction α + π/2, whereas its support is elongated in the direction α.

Discretization of Translation

Curvelet tight frames are constructed by sampling the translation parameter u [134]. These tight frames provide sparse representations of signals including regular geometric structures.

The curvelet sampling grid depends on the scale 2^j and on the angle α. Sampling intervals are proportional to the curvelet width 2^j in the direction α + π/2 and to its length 2^j/2 in the direction α:

(5.113)

Figure 5.12 illustrates this sampling grid. The resulting dictionary of translated curvelets is

FIGURE 5.12 (a) Curvelet polar tiling of the frequency plane with parabolic wedges. (b) Curvelet spatial sampling grid u^(j,α)_m at a scale 2^j and direction α.

Theorem 5.24 proves that this curvelet family is a tight frame of L²(²). The proof is not given here, but can be found in [142].

Wavelet versus Curvelet Coefficients

In the neighborhood of an edge having a tangent in a direction θ, large-amplitude coefficients are created by curvelets and wavelets of direction α = θ, which have their vanishing moment in the direction θ + π/2. These curvelets have a support elongated in the edge direction θ, as illustrated in Figure 5.13. In this direction, the sampling grid of a curvelet frame has an interval 2^j/2, which is much larger than the sampling interval 2^j of a wavelet frame. Thus, an edge is covered by fewer curvelets than wavelets having a direction equal to the edge direction. If the angle α of the curvelet deviates from 0, then curvelet coefficients decay quickly because of the narrow frequency localizaton of curvelets. This gives a high-directional selectivity to curvelets.

FIGURE 5.13 (a) Directional wavelets: a regular edge creates more large-amplitude wavelet coefficients than curvelet coefficients. (b) Curvelet coefficients have a large amplitude when their support is aligned with the edge direction, but there are few such curvelets.

Even though wavelet coefficients vanish when α = θ + π/2, they have a smaller directional selectivity than curvelets, and wavelet coefficients’ amplitudes decay more slowly as α deviates from θ. Indeed, the frequency support of wavelets is much wider and their spatial support is nearly isotropic. As a consequence, an edge produces large-amplitude wavelet coefficients in several directions. This is illustrated by Figure 5.10, where Lena’s shoulder edge creates large coefficients in three directions, and small coefficients only when the wavelet and the edge directions are aligned.

As a result, edges and image structures with some directional regularity create fewer large-amplitude curvelet coefficients than wavelet coefficients. The theorem derived from Section 933 proves that for images having regular edges, curvelet tight frames are asymptotically more efficient than wavelet bases when building sparse representations.

Fast Curvelet Decomposition Algorithm

To compute the curvelet transform of a discrete image f[n₁, n₂] uniformly sampled over N pixels, one must take into account the discretization grid, which imposes constraints on curvelet angles. The fast curvelet transform [140] replaces the polar tiling of the Fourier domain by a recto-polar tiling, illustrated in Figure 5.14(b). The directions α are uniformly discretized so that the slopes of the wedges containing the support of the curvelets are uniformly distributed in each of the north, south, west, and east Fourier quadrants. Each wedge is the support of the two-dimensional DFT ĉ^α_j[k₁, k₂] of a discrete curvelet c^α_j [n₁, n₂]. The curvelet translation parameters are not chosen according to 5.113, but remain on a subgrid of the original image sampling grid. At a scale 2^j, there is one sampling grid (2^⌋j/2⌊m₁, 2^j m₂) for curvelets in the east and west quadrants. In these directions, curvelet coefficients are

FIGURE 5.14 (a) Curvelet frequency plane tiling. The dark gray area is a wedge obtained as the product of a radial window and an angular window. (b) Discrete curvelet frequency tiling. The radial and angular windows define trapezoidal wedges as shown in dark gray.

(5.115)

with . For curvelets in the north and south quadrants the translation grid is (2^j m₁, 2^⌋j/2⌊ m₂), which corresponds to curvelet coefficients

(5.116)

The discrete curvelet transform computes the curvelet filtering and sampling with a two-dimensional FFT. The two-dimensional discrete Fourier transforms of f[n] and are and [k]. The algorithm proceeds as:

The critical step is the last inverse Fourier transform. A computationally more expensive one would compute for all n = (n₁, n₂) and then subsample this convolution along the grids (5.115) and (5.116).

Instead, the subsampled curvelet coefficients are calculated directly by restricting the FFT to a bounding box that contains the support of ĉ^α_j [−k]. A horizontal or vertical warping maps this bounding box to an elongated rectangular frequency box on which the inverse FFT is calculated. One can verify that the resulting coefficients correspond to the subsampled curvelet coefficients. The overall complexity of the algorithm is then O(N log₂ (N)), as detailed in [140]. The tight frame redundancy bound obtained with this discrete algorithm is A ≈ 5.

An orthogonal curvelet type transform has been developed by Do and Vetterli [212]. The resulting contourlets are not redundant but do not have the appropriate time and frequency localization needed to obtain asymptotic approximation results similar to curvelets.