Block transform

Wavelet packet bases are designed by dividing the frequency axis in intervals of varying sizes. These bases are particularly well adapted to decomposing signals that have different behavior in different frequency intervals. If f has properties that vary in time, it is then more appropriate to decompose f in a block basis that segments the time axis in intervals with sizes that are adapted to the signal structures.

Block Bases

Block orthonormal bases are obtained by dividing the time axis in consecutive intervals [a_p,a_p + 1] with

lim_{p →  − ∞}a_p =  − ∞ and lim_{p → ∞}a_p = ∞.

The size l_p = a_p + 1 − a_p of each interval is arbitrary. Let g = 1_[0,1]. An interval is covered by the dilated rectangular window

$g_p(t)=1_{[a_p,a_{p+1}]}(t)=g({t-a_p \over l_p}).$

Theorem 1. constructs a block orthogonal basis of L²(ℝ) from a single orthonormal basis of L²[0,1].

Theorem 1.

if {e_k}_{k ∈ ℤ} is an orthonormal basis of L²[0,1], then

$\{g_{p,k}(t)=g_p(t)\frac{1}{\sqrt{l_p}}e_k(\frac{t-a_p}{l_p})\}_{(p,k)\in \mathbb{Z}}$

is a block orthonormal basis of L²(ℝ)

Proof

One can verify that the dilated and translated family

$\{\frac{1}{\sqrt{l_p}}e_k(\frac{t-a_p}{l_p})\}_{(p,k)\in \mathbb{Z}}$

is an orthonormal basis of L²[a_p,a_p + 1]. If p ≠ q, then ⟨g_p, k, g_q, k⟩ = 0 since their supports do not overlap. Thus, the family $\{g_{p,k}(t)=g_p(t)\frac{1}{\sqrt{l_p}}e_k(\frac{t-a_p}{l_p})\}_{(p,k)\in \mathbb{Z}}$ is orthonormal. To expand a signal f in this family, it is decomposed as a sum of separate blocks

$f(t)=\sum_{p=-\infty}^{+\infty}f(t)g_p(t),$

and each block f(t)g_p(t) is decomposed in the basis $\{\frac{1}{\sqrt{l_p}}e_k(\frac{t-a_p}{l_p})\}_{(p,k)\in \mathbb{Z}}$

Block Fourier Basis

A block basis is constructed with the Fourier basis of L²[0,1]:

{e_k(t) = exp(i2kπt)}_{k ∈ ℤ}

The time support of each block Fourier vector g_p, k is [a_p,a_p + 1] of size l_p. The Fourier transform of g = 1_[0,1] is

$\hat{g}(w)=\frac{\sin(w/2)}{w/2}exp(\frac{iw}{2})$

and

$\hat{g}_{p,k}(w)=\sqrt{l_p}\hat{g}(l_pw-2k\pi)exp(\frac{-i2\pi ka_p}{l_P}).$

It is centered at 2kπl_p⁻¹ and has a slow asymptotic decay proportional to l_p⁻1|w|⁻¹. Because of this poor frequency localization, even though a signal f is smooth, its decomposition in a block Fourier basis may include large high-frequency coefficients. This can also be interpreted as an effect of periodization.

Discrete Block Bases

For all p ∈ ℤ, suppose that a_p ∈ ℤ. Discrete block bases are built with discrete rectangular windows having supports on intervals [a_p,a_p − 1]:

g_p[n] = 1_{[ap,ap + 1−1]}(n).

Since dilations are not defined in a discrete framework, bases of intervals of varying sizes from a single basis cannot generally be derived. Thus, Theorem 2 supposes an orthonormal basis of ℂ^l for any l > 0 can be constructed. The proof is:

Theorem 2.

Suppose that {e_k, l}_{0 ≤ k < l} is an orthogonal basis of ℂ^l for any l > 0. The family

{g_p, k[n] = g_p[n]e_k, lp[n−a_p]}_{0 ≤ k < lp, p ∈ ℤ}

is a block orthonormal basis of l²(ℤ).

A discrete block basis is constructed with discrete Fourier bases

$\{e_{k,l[n]}=\frac{1}{\sqrt{l}}exp(\frac{i2\pi kn}{l})\}_{0\leqslant k<l}$

The resulting block Fourier vectors g_p, k have sharp transitions at the window border, and thus are not well localized in frequency. As in the continuous case, the decomposition of smooth signals f may produce large-amplitude, high-frequency coefficients because of border effects.

Block Bases of Images

General block bases of images are constructed by partitioning the plane ℝ² into rectangles {[a_p,b_p] × [c_p,d_p]}_{p ∈ ℤ} of arbitrary length l_p = b_p − a_p and width w_p = d_p − c_p. Let {e_k}_{k ∈ ℤ} be an orthonormal basis of L²[0,1] and g = 1_[0,1]. The following can be denoted:

$g_{p,k,j}(x,y)=g(\frac{x-a_p}{l_p})g(\frac{y-c_p}{w_p})\frac{1}{\sqrt{l_pw_p}}e_k(\frac{x-a_p}{l_p})e_j(\frac{y-c_p}{w_p})$.

The family {g_p, k, j}_{(p,k,j) ∈ ℤ³} is an orthonormal basis of L²(ℝ²).

For discrete images, discrete windows that cover each rectangle can be defined

g_p = 1_{[ap,bp−1] × [cp,dp−1]}.

If {e_k, l}_{0 ≤ k < l} is an orthogonal basis of ℂ^l for any l > 0, then

{g_p, k, j[n₁,n₂] = g_p[n₁,n₂]e_k, lp[n₁−a_p]e_j, wp[n₂−c_p]}_{(k,j,p) ∈ (Z)³}

is a block basis of l²(ℝ²)

References

1. St´ephane Mallat, A Wavelet Tour of Signal Processing, 3rd