Motion-Adaptive Transforms (MAT) based on Graphs

  • Videos

    Image
  • Image

  • Compression

    Image
  • Image

  • Motion

    Image
  • Image

  • Graph-based
    Transfrorms

    Image
  • Image

  • Graphs

    Image

Transforms are widely used in today's data compression techniques such as High Efficiency Video Coding (HEVC) as an important tool for signal decorrelation. For videos with both spatial and temporal correlation, the transforms, especially the discrete cosine transform (DCT), are commonly applied to the spatial domain to reduce the spatial redundancy. For temporal correlation, the standard approach is to use motion-compensated prediction. Instead of using closed-loop prediction, we focus on temporal transforms that operate in an open-loop fashion.

The purpose of the work is to produce jointly coded frames for efficient video coding. We use graph-based motion-adaptive transforms (MATs) in the temporal domain to generate the temporal subbands.

MATs are orthonormal

Motion-adaptive transforms (MATs) are constructed to be orthonormal matrices for energy conservation. They allow energy compaction for efficient compression.

MATs adapt to the motion information

The motion information in the image sequences is captured by motion estimation. MATs are performed on the motion-connected signals.

MATs are based on graphs

The graph-based MATs are constructed using graph information, such as the graph structure and the graph Laplacian matrix.

The work of graph-based MAT extends the class of Motion-Compensated Orthogonal Transform (MCOT) to a more general class. Not restricted to Euler rotations of two dimensions, MATs can be constructed in an n-dimensional space.

In our work, we consider a subspace constraint as the first step to construct the transform. The purpose of the subspace constraint is to achieve good energy compaction [1].

  1. D. Liu and M. Flierl
    Motion-Adaptive Transforms based on Vertex-Weighted Graphs
    Proc. Data Compression Conference, Snowbird, UT, Mar. 2013. [pdf] [slides]

Based on the subspace constraint, we propose multiple methods to construct a full MAT matrix [2-4]. In [4], the transform is constructed using a vertex-weighted graph Laplacian matrix, which incorporates the graph structure into the transform.

  1. D. Liu and M. Flierl
    Graph-Based Rotation of the DCT Basis for Motion-Adaptive Transforms
    Proc. IEEE International Conference on Image Processing, Melbourne, Sept. 2013. [pdf]

  2. D. Liu and M. Flierl
    Graph-Based Construction and Assessment of Motion-Adaptive Transforms
    Proc. Picture Coding Symposium, San Jose, CA, Dec. 2013. [pdf]

  3. D. Liu and M. Flierl
    Motion-Adaptive Transforms based on the Laplacian of Vertex-Weighted Graphs
    Proc. Data Compression Conference, Snowbird, UT, Mar. 2014. [pdf]

We further analyze the optimality between using the covariance-based transform and the graph-based transform. We consider a covariance model based on a graph and show that the Laplacian eigenbasis approximates the covariance eigenbasis for large correlation.

  1. D. Liu and M. Flierl
    Energy Compaction on Graphs for Motion-Adaptive Transforms
    Proc. Data Compression Conference, Snowbird, UT, Apr. 2015. [pdf]

  2. D. Liu and M. Flierl
    Temporal Signal Basis for Hierarchical Block Motion in Image Sequences
    IEEE Signal Processing Letters, 2018. [link]

In [7], we consider transforms for multiple steps in energy compaction and redistribution, i.e., the transforms can be applied to bidirectional or multihypothesis motion estimation for better compaction.

  1. D. Liu and M. Flierl
    Video Coding using Multi-Reference Motion-Adaptive Transforms based on Graphs
    Proc. IEEE Image Video and Multidimensional Signal Processing Workshop, Bordeaux, July 2016. [pdf]

Contact

Du Liu
dul@kth.se
Osquldas väg 10, floor 3
KTH School of Electrical Engineering
10044 Stockholm