Lifting transforms on graphs and their application to video coding
Eduardo Martínez Enríquez · 2013
Compact representations of data are very useful in many applications such as coding, denoising or feature extraction. “Classical” transforms such as Discrete Cosine Transforms (DCT) or Discrete Wavelets Transforms (DWT) provide sparse approximations of smooth signals, but lose efficiency when they are applied to signals with large discontinuities. In such cases, directional transforms, which are able to adapt their basis functions to the underlying signal structure, improve the performance of “classical” transforms. In this PhD Thesis we describe a general class of lifting transforms on graphs that can be seen as N-dimensional directional transforms. Graphs are constructed so that every node corresponds to a specific sample point of a discrete N-dimensional signal and links between nodes represent correlation between samples. Therefore, non-correlated samples (e.g., samples across a large discontinuity in the signal) should not be linked. We propose a lifting-based directional transform that can be applied to any undirected graph. In this transform, filtering operations are performed following highcorrelation directions (indicated by the links between nodes), thus avoiding filtering across large discontinuities that give rise to large high-pass coefficients in those locations. In this way, the transform efficiently exploits the correlation that exists between data on the graph, leading to a more compact representation. We mainly focus on the design and optimization of these lifting transforms on graphs, studying and discussing the three main steps required to obtain an invertible and critically sampled transform: (i) graph construction, (ii) design of “good” graph bipartitions, and (iii) filter design. We also explain how to extend the transform to J levels of decomposition, obtaining a multiresolution analysis of the original N-dimensional signal. The proposed transform has many desirable properties, such as perfect reconstruction, critically-sampled, easy generalization to N-dimensional domains, non-separable and one-dimensional filtering operations, localization in frequency and in the original domain, and the ability to choose any filtering direction. As an application, we develop a graph-based video encoder where the goal is to obtain a compact representation of the original video sequence. To this end, we first propose a graph-representation of the video sequence and then design a 3-dimensional (spatio-temporal) non-separable directional transform. This can be viewed as an extension of wavelet transform-based video encoders that operate in the spatial and in the temporal domains independently. Our transform yields better compaction ability (in terms of non-linear approximation) than a state of the art motion-compensated temporal filtering transform (which can be interpreted as a temporal wavelet transform) and a comparable hybrid Discrete Cosine Transform (DCT)-based video encoder (which is the basis of the latest video coding standards). In order to obtain a complete video encoder, the transform coefficients and the side information (needed to obtain an invertible scheme) should be entropy coded and sent to the decoder. Therefore, we also propose a coefficient-reordering method based on the information of the graph which allows to improve the compression ability of the entropy encoder. Furthermore, we design two different low-cost approaches which aim to reduce the extensive computational complexity of the proposed system without causing significant losses of compression performance. The proposed complete system leads to an efficient encoder which significantly outperforms a comparable hybrid DCT-based encoder in rate-distortion terms. Finally, we investigate how rate-distortion optimization can be applied to the proposed coding scheme.