Seislet transform and seislet frame

Lifting scheme for wavelet transforms

In order to define the new transform, we follow the general recipe for digital wavelet transforms provided by Sweldens and Schröder (1996). In the most general terms, the lifting scheme (Sweldens, 1995) can be defined as follows:

1. Organize the input data as a sequence of records.
2. Break the data into even and odd components $\mathbf{e}$ and $\mathbf{o}$.
3. Find a residual difference $\mathbf{r}$ between the odd component and its prediction from the even component:
   

   $$\mathbf{r} = \mathbf{o} - \mathbf{P[e]}\;,$$ (1)

   
   
   where $\mathbf{P}$ is a prediction operator.
4. Find a coarse approximation $\mathbf{c}$ of the data by updating the even component
   

   $$\mathbf{c} = \mathbf{e} + \mathbf{U[r]}\;,$$ (2)

   
   
   where $\mathbf{U}$ is an update operator.
5. The coarse approximation $\mathbf{c}$ becomes the new data, and the sequence of steps is repeated at the next scale level.

A digital wavelet transform consists of data approximation at the coarsest level and residuals from all the levels. The key in designing an effective transform is making sure that the prediction operator $\mathbf{P}$ leaves small residuals while the update operator $\mathbf{U}$ preserves essential features of the original data while promoting them to the next scale level. For example, one can obtain the classic Haar wavelet by defining the prediction operator as a simple shift from the nearest sample:

$$\mathbf{P[e]}_k = \mathbf{e}_{k}\;,$$ (3)

with the update operator designed to preserve the DC (zero frequency) component of the signal. Alternatively, the $(2,2)$ Cohen-Daubechies-Feauveau biorthogonal wavelets (Cohen et al., 1992) are constructed by making the prediction operator a linear interpolation between two neighboring samples,

$$\mathbf{P[e]}_k = \left(\mathbf{e}_{k-1} + \mathbf{e}_{k}\right)/2\;,$$ (4)

and by constructing the update operator to preserve the running average of the signal (Sweldens and Schröder, 1996), as follows:

$$\mathbf{U[r]}_k = \left(\mathbf{r}_{k-1} + \mathbf{r}_{k}\right)/4\;.$$ (5)

The digital wavelet transform is an efficient operation. Assuming that the prediction and update operation take a constant cost per record, the number of operations at the finest scale is proportional to the total number of records $N$, the next scale computation takes $O(N/2)$, etc. so that the total number of operations is proportional to $N+N/2+N/4+\ldots + 2 =2\,(N-1)$, which is smaller than the $O(N\,\log{N})$ cost of the Fast Fourier Transform.

The digital wavelet transform is also easily invertible. Reversing the lifting scheme operations provides the inverse transform algorithm, as follows:

1. Start with the coarsest scale data representation $\mathbf{c}$ and the coarsest scale residual $\mathbf{r}$.
2. Reconstruct the even component $\mathbf{e}$ by reversing the operation in equation 2, as follows:
   

   $$\mathbf{e} = \mathbf{c} - \mathbf{U[r]}\;,$$ (6)

   
   

3. Reconstruct the odd component $\mathbf{o}$ by reversing the operation in equation 1, as follows:
   

   $$\mathbf{o} = \mathbf{r} + \mathbf{P[e]}\;,$$ (7)

   
   

4. Combine the odd and even components to generate the data at the previous scale level and repeat the sequence of steps.

Figure 1 shows a classic benchmark image from the image analysis literature and its digital wavelet transform using 2-D biorthogonal wavelets. Thanks to the general smoothness of the ``Lena'' image, the residual differences from equation 2 (stored as wavelet coefficients at different scales) have a small dynamic range, which enables an effective compression of the image in the transform domain. Wavelet compression algorithms are widely used in practice for compression of natural images. As for compression of seismic data, the classic DWT may not be optimal, because it does not take into account the specific nature of seismic data patterns. In the next section, we turn the wavelet transform into the seislet transform, which is tailored for representing seismic data.

lena,linear2
Figure 1. Benchmark ``Lena'' image from image analysis literature (a) and its 2-D digital wavelet transform using bi-orthogonal wavelets (b).

Seislet transform and seislet frame