Abstract

The red-black wavelets are a kind of second generation wavelets on a rectangular grid.
They are constructed using a 2-D lifting scheme which is based on a quincunx lattice.
Compared to classical tensor product wavelets on the same grid, the non-separable red-black wavelets show less anisotropy.

Lifting Scheme

Classical one-dimensional wavelet transforms can be extended to more dimensions using tensor products, yielding a separable multi-dimensional transform. A disadvantage of this technique is the introduction of an anisotropy in the wavelet decomposition. Non-separable wavelets can provide a solution to this.

At each resolution level of a wavelet transform, the signal is split into a high pass and a low pass part. The lifting scheme is an efficient implementation of these filtering operations. Suppose that the low-resolution part of a signal at level $j+1$ consists of a data set $\lambda_{j+1}$. This set is divided into two subsets at level $j$: the low-resolution part $\lambda_j$ and the high-resolution part $\gamma_j$. Then, a dual lifting step can be seen as a prediction: the data $\gamma_j$ are predicted from the data in the subset $\lambda_j$. The $\gamma_j$ is replaced by $\gamma_j - \mathcal{P}\left(\lambda_j\right)$, where $\mathcal{P}$ represents the prediction operator. Furthermore, a primal lifting step updates set $\lambda_j$ with data computed from the new subset $\gamma_j$. The $\lambda_j$ is replaced by $\lambda_j - \mathcal{U}\left(\gamma_j\right)$ with $\mathcal{U}$ some updating operator.

The famous family of classical biorthogonal CDF wavelets fits in the above scheme. Especially its member with two vanishing moments, the CDF 5/3 wavelet. In this case, the prediction operator predicts the odd samples using linear interpolation $$ d_i \leftarrow d_i - \frac{1}{2} \left( s_i + s_{i+1} \right). $$ The update operator updates the even samples to preserve the mean value of the samples $$ s_i \leftarrow s_i + \frac{1}{4} \left( d_{i-1} + d_{i} \right). $$ For two-dimensional data, it can be applied row and columnwise, resulting in a tensor product wavelet transform. This is a separable transform.

Red-Black Transform

The red-black wavelets are defined on a two-dimensional quincunx lattice. First, the data are split into two subsets. The even/odd splitting from the one-dimensional case is replaced by a checkerboard splitting, with red and black squares. Thus, one has a red subset $\lambda_j$ and a black subset $\gamma_j$. Then, the values of the black subset are predicted from its immediate neighbors in the red set. In accordance with the CDF 5/3 lifting scheme, an average of the four neighbors is taken for this prediction. Next, an updating step for the data in the red subset is performed, based on the new black values. For the subsequent resolution level, the same operation cannot be repeated on a horizontal/vertical basis as on the previous resolution level. However, it can be done on the diagonals instead. The red set is divided into two subsets: the blue subset $\lambda_{j-1}$ and the yellow subset $\gamma_{j-1}$. The same kind of averaging and updating steps are then computed for the blue-yellow squares. For the next resolution level, one has to decompose the blue subset further. Since this subset is again arranged in a horizontal/vertical manner, a red-black update can be performed again. It is seen that a red-black and a blue-yellow splitting is alternated to pass through the subsequent resolution levels.

The Red-Black wavelet transform is a non-separable two-dimensional transform. It is less anisotropic than tensor-product wavelets on the same rectangular grid. The splitting in red and black or blue and yellow pixels creates trivial biorthogonal basis functions.

References

- G. Uytterhoeven, A. Bultheel. The Red-Black Wavelet Transform (1998)
- G. Uytterhoeven, A. Bultheel. The Red-Black Wavelet Transform and the Lifting Scheme (2000)