Highly Efficient Non-Separable Transforms for Next Generation Video Coding
Amir Said, Xin Zhao, Marta Karczewicz, Hilmi E. Egilmez, Vadim Seregin, Jianle Chen · 2025
Read Highly Efficient Non-Separable Transforms for Next Generation Video Coding by Amir Said, Xin Zhao, Marta Karczewicz, Hilmi E. Egilmez, Vadim Seregin, Jianle Chen (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-21728.txt.
Introduction
Amir Said, Xin Zhao, Marta Karczewicz, Hilmi Egilmez, Vadim Seregin, and Jianle Chen wrote this paper in two thousand twenty-five. It seeks cheaper transforms for squeezing video, where matrix-based transforms tuned to the signal have long been too costly to run.
Rather than hunt for full matrices that squeeze best, the team hunts for a few parameters that define a new class of transforms, called HyGTs. These have cheap forms that run well in parallel. Built as an add-on to the HEVC standard, they cut bit rate by a clear margin in tests. They also use far less memory than the classic optimal matrices. The gain points a way for next-round video standards.
Catalog record
| CREATOR | Amir Said, Xin Zhao, Marta Karczewicz, Hilmi E. Egilmez, Vadim Seregin, Jianle Chen |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 23 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-21728
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Highly Efficient Non-Separable Transforms for Next Generation Video Coding Amir Said, Xin Zhao, Marta Karczewicz, Hilmi E. Egilmez, Vadim Seregin, Jianle Chen Abstract For the last few decades, the application of signal-adaptive transform coding to video compression has been stymied by the large computational complexity of matrix-based solutions. In this paper, we propose a novel parametric approach to greatly reduce the complexity without degrading the compression performance. In our approach, instead of following the conventional technique of identifying full transform matrices that yield best compression efficiency, we look for the best transform parameters defining a new class of transforms, called HyGTs, which have low complexity implementations that are easy to parallelize. The proposed HyGTs are implemented as an extension of High Efficiency Video Coding (HEVC), and our comprehensive experimental results demonstrate that proposed HyGTs improve average coding gain by 6% bit rate reduction, while using 6.8 times less memory than KLT matrices. I Introduction Transform coding is a fundamental part in all the widely used video compression standards [ 1 , 2 , 3 ] , which typically adopt a fixed, separable transform in order to maintain low complexity. For this purpose, the discrete cosine transform (DCT) is by far the most popular transform in such standards, since it can achieve good compression rates especially when inter-sample correlations between pixels are large, and it has fast implementations. However, the DCT is optimal under very restrictive assumptions, which do not practically hold for the most image and video data. On the other hand, it has been long known that the signal-adaptive Karhunen-Loève Transform 1 1 1 What is discussed here applies to all forms of adaptive transform coding, but to avoid confusion we only refer to the KLT. (KLT) is optimal for transform coding [ 4 , 5 , 6 , 7 ] . There is a good number of studies showing that, when combined with proper classification and adaptation methods, KLTs can very effectively improve compression efficiency. Nevertheless, since they used the inefficient matrix-based implementations, those contributions have not been adopted, nor further developed. In this work, we propose a novel method that allows us to design more practical signal-adaptive transforms by taking simultaneously into account signal statistics, compression efficiency, and computational complexity. We consider the following basic premises about transform coding applied to media compression in our approach. • The mathematical tools to compute the optimal data-defined transform provide a unique type of solution. However, in practice transform coding gains are defined nearly exclusively by a few principal components (i.e., data within certain subspaces), and we commonly have large sets of transforms that produce coding results that are very close to the optimal. • There are certain orthogonal transform structures that enable computation with very low complexity (both memory and operations). Individually they cover a very limited range of all possible orthogonal transforms, but if they are properly combined, the range can be greatly extended, without significant increase in complexity. The novelty of our approach is that, instead of identifying the full transform matrices (e.g., KLTs) that yield best compression, we search for a set of parameters, which implicitly defines a low-complexity transform , to derive a low-complexity transform that achieves the best coding performance. As illustrated in Fig. 1 , we search for the intersection of two transform sets. The resulting transform should produce compression sufficiently close to the KLT’s, but at much lower computational complexity. The low-complexity transforms are defined by a set of parameters which defines a special multi-pass decomposition of transform matrices, and they are computationally efficient and easily parallelizable by construction. In the rest of the paper, Section II present some preliminaries about signal-adaptive transforms and computational complexity. In Section III , we introduce the general class of parametric multi-pass transforms (PMPT), and Hypercube-Givens transforms (HyGT) is proposed as a special case of PMPT in Section IV . The HyGT parameter optimization is discussed in Section V . The experimental results and concluding remarks are presented in Sections VI and VII , respectively. Fig. 1: The new design method exploits the fact that for media coding there is commonly a large set of nearly optimal transforms, and looks for those that that can also be computed with low complexity. II Preliminaries Signal-adaptive transform coding: An essential aspect of advanced transform coding is that it should be highly adaptive, to exploit the non-stationary features of complex data. We assume that a vector {\bf x} with values of pixels in a video block is first subtracted from its prediction {\bf p} to create the zero-mean residual vector {\bf r}={\bf x}-{\bf p} , and that the decoder, using rate-distortion estimation, decides on a classification index c\in\{1,2,\ldots,C\} for the current block, applies the transform corresponding to c to obtain {\bf y}_{c} , and encodes c as side information. To find the optimal transform for class c , we first compute (e.g., using training) the matrix with the conditional correlation of the residual vector \mathbf{\Phi}_{c}=\mathrm{E}_{{\bf r}|c}\left\{{\bf r}\,{\bf r}^{\mbox{\sf\tiny T}}\right\}, (1) which is symmetric and positive semi-definite, and we can always find one orthogonal matrix {\bf K}_{c} such that [ 8 , 9 ] {\bf K}_{c}\,\mathbf{\Phi}_{c}\,{\bf K}^{\mbox{\sf\tiny T}}_{c}=\mathbf{\Lambda}_{c}, (2) where \mathbf{\Lambda}_{c} is a diagonal matrix with the eigenvalues of \mathbf{\Phi}_{c} . This transform matrix {\bf K}_{c} defines the KLT for \mathbf{\Phi}_{c} , and produces the transformed vector {\bf y}_{c}={\bf K}_{c}\,{\bf r}, (3) which has uncorrelated elements. Analysis of Computational Complexity : To analyze the computational complexity of transform coding, applied to images and video, we have to consider the following implementation choices: (a) Separable or non-separable; and (b) “fast” or matrix-based. While any linear transformation can be implemented using a matrix multiplication as in eq. ( 3 ), low-complexity computation has been available only for a few special “fast” transforms, like the DCT, which have very specific mathematical properties [ 10 ] . Table I shows the complexity (memory and operations) of transforms applied to blocks of 2^{B}\times 2^{B} residuals, considering that we use C different transforms, according to their classification (the last row is explained in Section IV ). We can observe that the complexity of non-separable, matrix-based transforms—the ones that yield best compression—grows very fast, which is the reason they have been impractical except for very small blocks. On the practical side, it is important to observe that while in the past arithmetic operations could have been much more expensive than memory, now we have to consider that the number of operations per pixel is not as critical, and instead we commonly need to limit the memory requirements, because best compression is obtained when the number of transforms C is relatively large. TABLE I: Memory and arithmetic operations complexity of different types 2-D block transforms, applied to 2^{B}\times 2^{B} residual blocks, and considering C different classifications. Transform Memory Operations Ops./pixel Fast, sep. O \left(2^{B}CB\right) O \left(2^{2B}B\right) O \left(B\right) Matrix, sep. O \left(2^{2B}C\right) O \left(2^{3B}\right) O \left(2^{B}\right) Matrix, non-sep. O \left(2^{4B}C\right) O \left(2^{4B}\right) O \left(2^{2B}\right) PMPT, non-sep. O \left(2^{2B}CP\right) O \left(2^{2B}P\right) O \left(P\right) III Parametric Multi-pass Transform (PMPT) In this section we discuss the basic approach for reducing the transform complexity, with technical details in the following sections. We start by considering that N\times N orthogonal matrices form the