Video compression types

[zakray]

Hi everyone, first time post, sorry for the super basic question. Trying to get a deeper understanding of video compression.

Basically, I'm trying to figure out:
-The basic difference between DCT and wavelet
-Do both of them support both lossless and lossy encoding?
-Are there other algorithms in use for video compression? I've read that HEVC for example uses something different.


Thank you!
Zak

[Jyrki Alakuijala]

Hi everyone, first time post, sorry for the super basic question. Trying to get a deeper understanding of video compression.

Basically, I'm trying to figure out:
-The basic difference between DCT and wavelet

DCT compresses in a way that humans like it. Wavelet compresses in a way that mathematicians like it. Wavelets can be more compatible with variable resolution, but no practical implementation exists.

-Do both of them support both lossless and lossy encoding?

With lossless encoding fine quality of prediction, entropy coding and context modeling are more critical. Integral transform doesn't help much.

-Are there other algorithms in use for video compression? I've read that HEVC for example uses something different.

Variable size and combination of Identity, DST, and DCT are the algorithms used by AV1, and PIK uses currently only 8x8 DCT.

In theory Gabor functions should be better than DCT, but it seems to be near impossible to actually get that working competitively at a high quality (high BPP rates).

[Shelwien]

> The basic difference between DCT and wavelet

https://en.wikipedia.org/wiki/Discrete_cosine_transform
https://en.wikipedia.org/wiki/Discre...elet_transform

Actually they are simply different orthonormal bases.

Just as well you can use Taylor series or any other
parametric approximation, and there'd be some cases
where it would perform better than anything else.

> Do both of them support both lossless and lossy encoding?

Yes, but it might be hard to find lossless implementations.
I have one for DCT of 16-bit values, but I had to make it from scratch.

Also lossless spectral transformations normally hurt compression -
they're only necessary to spread quantization errors around,
to make them less noticeable.

> Are there other algorithms in use for video compression?
> I've read that HEVC for example uses something different.

Seems to be a tuned DCT:

The elements of the core transform matrices were
derived by approximating scaled DCT basis functions, under
considerations such as limiting the necessary dynamic range
for transform computation and maximizing the precision and
closeness to orthogonality when the matrix entries are specified
as integer values.

There's also block matching and motion compensation,
but spectral transform seems to be the same as usual.

[thorfdbg]

-The basic difference between DCT and wavelet

Oh well. A DCT essentially extracts frequencies from the source image. The DWT is a scale-space transformation. In frequency space, the DCT creates multiple equally-sized slots. The DWT creates slots that form a geometric series, i.e. finer resolution at low and coarser resolution at higher frequencies.

-Do both of them support both lossless and lossy encoding?

Yes, but. It is relatively simple to find lossless wavelet transformations, it is a cascaded polyphase matrix with only two entries which can be lifted easily - the "lifting scheme" provides a relatively simple access to lossless approximations. For DCT, this is considerably harder as the transformation is a 8x8 (or NxN) matrix, and it is more complex to "lift" it. Yet, it is possible. For example, JPEG XT part-8 has a lossless DCT as one option.

-Are there other algorithms in use for video compression? I've read that HEVC for example uses something different.

HEVC also has a DST as one option, a discrete sine transformation. This works better for intra-frame predicted blocks where the prediction comes only from one edge of the block. It is a close cousin of the DCT, though. You miss, however, one important point: DCT and DST are block-based transformations, the DWT is not. This has advantages but also drawbacks. The advantage is that it fits well to block-based motion-prediction schemes of the hybrid video codecs we have today. Block-based motion prediction does not mix well with the DWT as the DWT does not like "block edges", i.e. creates artefacts there. The drawback is that the DCT itself creates artefacts as the transformation does not go across edges, i.e. cannot pick up correlations across the edges of its transform domain. You see typical DCT blocking artefacts at low bitrates in JPEG compression, for example. There are also hybrid transformations like the JPEG XR transformation which uses a first-level DCT, and a block-overlap transformation on the second level to avoid the blocking defects of the first level. This is related to the MDCT in audio compression.

[thorfdbg]

DCT compresses in a way that humans like it. Wavelet compresses in a way that mathematicians like it. Wavelets can be more compatible with variable resolution, but no practical implementation exists.

In this generality: Certainly no. A DCT can be seen to be the ideal transformation (the KLT) for certain number of sources. There is nothing like that for the DWT. So, in a sense, the DCT is ideal. Second, the "visual bands" of the human visual system can be better described as a cascaded set of frequency filters where the frequency slot grows geometrically, not arithmetically. So in that sense, the DWT actually fits better to the human visual system than the DCT. There is of course a practical implementation that makes use of the "variable resolution" or resolution scalability of wavelets. It is called JPEG 2000.

With lossless encoding fine quality of prediction, entropy coding and context modeling are more critical. Integral transform doesn't help much.

Yes, indeed. Unless you want a lossless to lossy scalability.

In theory Gabor functions should be better than DCT, but it seems to be near impossible to actually get that working competitively at a high quality (high BPP rates).

The problem is to invert them without loss, and to allow an efficient implementation of them. They are good for image analysis, also quality analysis, but not for image coding (so far).