In VVC, in comparison with HEVC, a new stage of transform called low-frequency non-separable transform(LFNST) was added. The main condition is that LFNST applies only for intra blocks for both luma/chroma components (separate chroma is enabled).

The main goal of LFNST is to further compress the redundancy between low-frequency primary transform coefficients, which are transform coefficients from the conventional direction intra prediction. We can also add that for elongated rectangles LFNST helps to concentrate coefficients exactly in the top right corner.

So how does it work? LFNST is applied between forward primary transform and quantization (on the encoder side) and between de-quantization and inverse primary transform (on the decoder side). LFNST consists of 2 modes: 4x4 LFNST (for blocks with width/height < 8) and 8x8 LFNST (for blocks with width/height >= 8).

As a way of example, let’s consider 4x4 LFNST for block X:

First of all, we need to represent X as a one-dimensional vector:

After that, the non-separable transform can be calculated as: F = T⋅ X (F and X are vectors), where T is 16x16 transform matrix and F is the 16x1 vector with transform coefficients which can be reorganized into a 4x4 block using a raster scan order.

In LFNST, amatrix multiplication approach is used, so to save memory space to store matrix coefficients and to decrease computational complexity it will be good if the matrix dimension can be minimized. In this way. the main idea is to map N dimensional vector to R dimensional vector, where N > R and N/R is the reduction factor. For 8x8 LFNST the reduction factor is 4, so the transform matrix is 16x64. But in later stages of VVC it was further reduced to 16x48. So due to matrix dimensional reduction the memory usage for storing them decreased from 10Kb to 8Kb without much performance degradation.

For inverse process on the decoder side the inverse LFNST matrix is the transposed matrix of the forward transform matrix.

LFNST has some restrictions and it cannot be used in the following cases:

block size is more than 64x64 or width/height CU are more than max transform_block_size;
if ISP is applied TU width or height is less than 4;
block has INTER mode;
transform skip is used;
blocks 4x4 and 8x8 have more than 8 first significant coefficients;
there are some coefficients out of the 1st subblock;
if there is only 1 non-zeroed coefficient (DC only); It is important to note that LFNST and MTS are connected: if LFNST is enabled, only DCT-II mode (MTS index = 0) can be applied.

LFNST transform matrices T can be represented as follows:

8 different 16x16 matrices for 4x4 LFNST (Cartesian product of 4 lfnstTrSetIdx & 2 lfnst_idx);
8 different 16x48 matrices for 8x8 LFNST; All these matrices are precalculated and stored on the encoder/decoder side.

The choice of the best suitable LFNST matrix depends on lfnstTrSetIdx, which depends on IntraPredMode and lfnst_idxwhich is transmitted in bitstream. Below you can see the table of dependence of lfnstTrSetIdx on IntraPredMode:

And here you can see, how LFNST works on decoder side:

This is all for today. In our next article we will continue telling you about VVC transform innovations. Also you can check our previous article about MTS here.

References

Algorithm description for Versatile Video Coding and Test Model 12 (VTM 12)
Low Frequency Non-Separable Transform (LFNST)

#H.266:

Low-Frequency Non-Separable Transform (LFNST) in VVC

Affine Motion Compensated Prediction in VVC

VVC Transform: Multi Transform Selection (MTS)

Subblock-based Temporal Motion Vector Prediction (SbTMVP) in VVC