Abstract

The edge-avoiding wavelets are a family of second-generation wavelets constructed using a data-prediction lifting scheme.
The support of these wavelets is formed based on the edge content of the image and avoids having pixels from both sides of an edge.
The scheme achieves nonlinear multi-scale edge-preserving image processing at computation times which are linear in the number of image pixels.
The wavelets encode, in their shape, the smoothness information of the image at every scale.

Lifting Scheme

The lifting scheme is an efficient implementation of the fast wavelet transform. It provides a methodology for constructing biorthogonal wavelets through a spatial domain. This makes it a well-suited framework for constructing wavelets that adapt to the spatial particularities of the data. For example, one can start with some given simple basis and performs a sequence of modifications that adapt and improve the wavelets. The scheme can be divided into three steps: split, predict, and update.

The input signal data at the finest level, $a^0[n]$ (the superscripts denote the level), is divided into two disjoint sets $C$ and $F$. These sets define coarse and fine data points, respectively. The signal values restricted to these sets are denoted by $a^0_C[n]$ and $a^0_F[n]$. Next, the coarse data points $a^0_C$ are used to predict the fine $a^0_F$. This prediction operator is denoted by $\mathcal{P} : C \mapsto F$. The prediction errors are the wavelet or detail coefficients of the wavelet transform of the next level. The coarse variables are usually not taken as the next-level approximation coefficients. The lifting scheme makes sure that the overall sum of the approximation coefficients is preserved at all levels. This is achieved by an additional update operator $\mathcal{U} : F \mapsto C$ that introduces averaging with the fine variables. These new variables are the approximation coefficients of the next level of the wavelet transform. The following levels are computed recursively by repeating these three steps over the approximation coefficients. The inverse transformation is obtained by applying these steps in the reverse order.

To make this construction more concrete, a particular example is described. Consider a 1-D image signal $a_0[n]$ and the splitting step that takes the odd-indexed pixels as the coarse variables and the even-indexed as the fine. Every even-indexed pixel is predicted by its two odd-indexed neighbors using a simple linear interpolation formula $$ \mathcal{P}\left(a^0_C\right)[n] = \left( a^0_C[n-1] + a^0_C[n+1] \right) / 2 \text{.} $$ Next, by choosing the following update operator $$ \mathcal{U}\left(d^1\right)[n] = \left( d^1[n-1] + d^1[n+1] \right) / 4 \text{,} $$ the approximation average is preserved throughout the different levels. This construction corresponds to the well-known CDF 5/3 biorthogonal wavelets.

Weighted Wavelets

The scaling and wavelet functions are constructed based on the content of the input data.
Instead of using data-independent regression formulae, posteriori influence functions are used based on the similarity between the predicted pixel and its neighboring coarse variables.
More specifically, the edge-stopping function is used to define the following prediction weights
$$ w^j_n[m] = \left( \left| a^j[n] - a^j[n] \right|^\alpha + \epsilon \right)^{-1} \text{,} $$
where $\alpha$ is between 0.8 and 1.2 and $\epsilon = 10^{-5}$, for images with pixels values ranging from zero to one.
A two-dimensional weighted prediction based on the CDF 5/3 wavelet transform, applied along each axis separately, is described here.
Instead of using an even average of the two coarse variables, the following robust average is defined
$$ \mathcal{P}\left(a^j_C\right)[x,y] = \frac{ w^j_{x,y}[x-1,y] a^j_C[x-1,y] + w^j_{x,y}[x+1,y] a^j_C[x+1,y] }{ w^j_{x,y}[x-1,y] + w^j_{x,y}[x+1,y] } \text{.} $$
The update operator $\mathcal{U}$ is designed to smooth the next level approximation variables $a^{j+1}_C$ when possible and a robust smoothing is used to define
$$ \mathcal{U}\left(d^{j+1}\right)[x,y] = \frac{ w^j_{x,y}[x-1,y] d^{j+1}[x-1,y] + w^j_{x,y}[x+1,y] d^{j+1}[x+1,y] }{ 2\left( w^j_{x,y}[x-1,y] + w^j_{x,y}[x+1,y] \right) } \text{.} $$
The analog steps are repeated along the y-image axis.
Note that uniform weights, obtained by $\alpha = 0$, produce a separable two-dimensional CDF 5/3 wavelet transform.

References

- R. Fattal. Edge-Avoiding Wavelets and their Applications (2009)