Graph-based Transforms for Video Coding

--In many state-of-the-art compression systems, signal transformation is an integral part of the encoding and decoding process, where transforms provide compact representations for the signals of interest. This paper introduces a class of transforms called graph-based transforms (GBTs) for video compression, and proposes two different techniques to design GBTs. In the first technique, we formulate an optimization problem to learn graphs from data and provide solutions for optimal separable and nonseparable GBT designs, called GL-GBTs. The optimality of the proposed GL-GBTs is also theoretically analyzed based on Gaussian-Markov random field (GMRF) models for intra and inter predicted block signals. The second technique develops edge-adaptive GBTs (EA-GBTs) in order to flexibly adapt transforms to block signals with image edges (discontinuities). The advantages of EA-GBTs are both theoretically and empirically demonstrated. Our experimental results demonstrate that the proposed transforms can significantly outperform the traditional Karhunen-Loeve transform (KL T). Index T erms --Transform coding, predictive coding, graph-based transforms, video coding, compression, optimization, statistical modeling. Predictive transform coding is a fundamental compression technique adopted in many block-based image and video compression systems, where block signals are initially predicted from a set of available (already coded) reference pixels, and then the resulting residual block signals are transformed (generally by a linear transformation) to decorrelate residual pixel values for effective compression. After prediction and transformation steps, a typical image/video compression system applies quantization and entropy coding to convert transform coefficients into a stream of bits. Figure 1 illustrates a representative encoder-decoder architecture comprising three basic components, (i) prediction, (ii) transformation, (iii) quantization and entropy coding, which are implemented in state-of-the-art compression standards such as JPEG [5], HEVC [6] and VP9 [7]. This paper focuses mainly on the transformation component of video coding and develops techniques to design orthogonal transforms, called graph-based transforms (GBTs), adapting diverse characteristics of video signals. In predictive transform coding of video, the prediction is typically carried out by choosing one among multiple intra and inter prediction modes in order to exploit spatial and temporal redundancies between block signals.