Directional Transforms for Video Coding Based on Lifting on Graphs

In this paper, we describe and optimize a general scheme based on lifting transforms on graphs for video coding. A graph is constructed to represent the video signal. Each pixel becomes a node in the graph and links between nodes represent similarity between them. Therefore, spatial neighbors and temporal motion-related pixels can be linked, while nonsimilar pixels (e.g., pixels across an edge) may not be. Then, a lifting-based transform, in which filtering operations are performed using linked nodes, is applied to this graph, leading to a 3D (spatio-temporal) directional transform, which can be viewed as an extension of wavelet transforms for video. The design of the proposed scheme requires four main steps: 1) graph construction; 2) graph splitting; 3) filter design; and 4) extension of the transform to different levels of decomposition. We focus on the optimization of these steps in order to obtain an effective transform for video coding. Furthermore, based on this scheme, we propose a coefficient reordering method and an entropy coder leading to a complete video encoder that achieves better coding performance than a motion-compensated temporal filtering wavelet-based encoder, and a simple encoder derived from H.264/AVC that makes use of similar tools as our proposed encoder (reference software JM15.1 configured to use one reference frame, no subpixel motion estimation, and 16 x 16 inter and 4 x 4 intra modes).