LOW-COMPLEXITY TRANSFORM ADJUSTMENTS FOR VIDEO CODING

Amir Said, Hilmi E. Egilmez, Yung-Hsuan Chao · 2025

Read LOW-COMPLEXITY TRANSFORM ADJUSTMENTS FOR VIDEO CODING by Amir Said, Hilmi E. Egilmez, Yung-Hsuan Chao (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-23618.txt.

Introduction

Amir Said, Hilmi Egilmez, and Yung-Hsuan Chao find a cheaper way, in a 2025 preprint, to run the math transforms inside modern video codecs. Codecs shrink video by restating blocks of leftover signal with wave-like patterns. Using several pattern types, including uneven ones, improves compression. But the uneven transforms cost far more to compute than the standard one, above all on large blocks. That cost hits both software and hardware designs.

The authors design near-copies of those transforms that start from the cheap standard transform. Small orthogonal tweaks then bend its most important patterns toward the target shapes. The result keeps the speed of the standard path while acting almost like the costly one. Tests in the Versatile Video Coding reference software showed large savings in computation. Coding quality stayed practically the same as with the full transforms.

Catalog record

CREATORAmir Said, Hilmi E. Egilmez, Yung-Hsuan Chao
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE18 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-23618

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

LOW-COMPLEXITY TRANSFORM ADJUSTMENTS FOR VIDEO CODING Amir Said, Hilmi E. Egilmez, Yung-Hsuan Chao Abstract Recent video codecs with multiple separable transforms can achieve significant coding gains using asymmetric trigonometric transforms (DCTs and DSTs), because they can exploit diverse statistics of residual block signals. However, they add excessive computational and memory complexity on large transforms (32-point and larger), since their practical software and hardware implementations are not as efficient as of the DCT-2. This article introduces a novel technique to design low-complexity approximations of trigonometric transforms. The proposed method uses DCT-2 computations, and applies orthogonal “adjustments” to approximate the most important basis vectors of the desired transform. Experimental results on the Versatile Video Coding (VVC) reference software show that the proposed approach significantly reduces the computational complexity, while providing practically identical coding efficiency. † † address: Qualcomm Technologies, Inc., San Diego, CA, USA 1 Introduction In hybrid video codecs, intra and inter predicted residuals may have diverse statistical properties, which are not fully exploited by symmetric transforms such as the traditional discrete cosine transform (i.e., DCT-2), yet some irregular features can be captured with fixed separable asymmetric transforms including discrete sine transform (DST-7) [ 1 , 2 , 3 ] , or with selections among several separable symmetric and asymmetric transforms by coding a transform index [ 4 ] . Although asymmetric trigonometric transforms can yield significant coding gains (larger than 1%), it is also necessary to consider the complexity aspects such as throughput (measured in transform coefficients per second) that can severely limit the maximum frame rate of encoding/decoding. Since throughput decreases with the transform dimension, it is essential to reduce the complexity of large transforms as worst-case measures typically define hardware costs. The DCT-2 has been extensively used for image/video coding, because it provides reasonable compression performance and has several low-complexity implementations. Symmetric and regular structure of the DCT-2 leads to efficient hardware implementations (parallel designs) and fast algorithms with low-level software optimizations (e.g., parallel SIMD instructions). Thus, the complexity of DCT-2 can be greatly reduced for critical transform dimensions with fewer arithmetic operations and parallel processing. On the other hand, existing implementations of asymmetric trigonometric transforms are more expensive than the DCT-2 due to their irregular structures [ 5 ] . The ITU/MPEG Versatile Video Coding Standard (VVC) at current development stage uses both symmetric and asymmetric transforms DCT-2, DCT-8 and DST-7, where the maximum dimension of DST-7 and DCT-8 is 32. Despite extensive research on efficient computations of trigonometric transforms, most methods do not truly match to the practical video coding requirements and potentially require distinct designs depending on the transform dimension [ 6 ] . Specifically, transforms for dimensions up to 16 can be effectively computed with direct matrix-vector products, but it can be prohibitively complex for larger dimensions. In this paper, we introduce a new approach to design low-complexity approximations of desired transforms by applying a family of efficient transforms closely related to DCT-2 (i.e., DCT-3, DST-2 and DST-3) and simple orthogonal transforms called adjustments. The proposed approach is fundamentally different than existing methods [ 5 ] , which directly seek fast implementations of a given transform. On the other hand, our approach uses one of DCT-2, DCT-3, DST-2 and DST-3 as the efficient building block for computation and applies optimized adjustment parameters to better approximate low-frequency basis vectors of a desired transform without degrading the coding performance. Two types of transform adjustment methods are discussed here: 1 1 1 Both approaches have been proposed for standardization [ 7 , 8 ] , and extensively tested. • Pre-adjustment with sparse band matrices (Fig. 2 a) first applies adjustment then uses one of DCT-2, DCT-3, DST-2 and DST-3 at the encoder side. • Post-adjustment with block sparse matrices (Fig. 2 b) first uses one of DCT-2, DCT-3, DST-2 and DST-3 and then applies adjustment at the encoder side. A non-convex constrained optimization framework is developed to estimate sparse and orthogonal adjustment matrices with a weighted least-squares criterion. Although the proposed method can be used to design any orthogonal transform of interest, here we focus on efficient designs for DST-7 and DCT-8 existing in the latest version of VVC. The proposed adjustment technique has the following main advantages: • It can greatly reduce the complexity in terms of throughput and memory, since it exploits highly efficient implementations of DCT-2 and sparsity patterns of adjustments (see Fig. 2 ). • It can achieve similar coding performance that of a desired transform, since the proposed optimization framework provides very good approximations of the truly important basis vectors. In the rest of this paper, Section 2 describes the proposed optimization framework and discusses the relations between DCT-2, DCT-3, DST-2, and DST-3 by showing that they share the same computational properties. In Section 3 , the experimental results are presented, and some concluding remarks are drawn in Section 4 . 2 Low-complexity transform adjustments Figure 1: Gray-coded representation of sparse adjustment matrices, where larger magnitudes are represented as darker pixels. Along vertical direction are transforms used for computation ( {\bf B} ), and along horizontal are the desired transforms ( {\bf D} ). Representing the group of orthogonal N\times N matrices [ 9 ] as {\rm O}(N,\mathbb{R}) , let {\bf D} be the desired transform and {\bf B} be the transform allowing efficient computations. The objective is to find orthogonal transform adjustment matrices {\bf A} and {\bf C} such that {\bf H}={\bf C}{\bf B}{\bf A}\stackrel{{\scriptstyle\rm cg}}{{\approx}}{\bf D},\quad{\bf A}\in{\cal A},{\bf C}\in{\cal C}, (1) where \stackrel{{\scriptstyle\rm cg}}{{\approx}} denotes a form of approximation meant to preserve coding gain, {\cal A}\subset{\rm O}(N,\mathbb{R}) and {\cal C}\subset{\rm O}(N,\mathbb{R}) are predefined subsets of sparse orthogonal matrices that have very low computational complexity. The following weighted least-squares criterion can be used to achieve similar coding gains that of {\bf D} by having a matrix approximation with larger weights for low-frequency components. \min_{{\bf A}\in{\cal A},{\bf C}\in{\cal C}}\left\{\sum_{i=0}^{N-1}\sum_{j=0}^{N-1}e^{-\alpha i}\left(H_{i,j}-D_{i,j}\right)^{2}\right\}, (2) where \alpha=\ln(10^{2})/N . The constraint to have matrices belonging to {\rm O}(N,\mathbb{R}) (making the optimization problem non-convex) can be satisfied by using a convenient matrix factorization, for example, with sequential sets of parallel Givens rotations [ 10 ] . 2.1 Trigonometric transforms related to the DCT-2 Figure 2: Sparsity patterns chosen for DST-7 adjustment matrices: all white-colored elements are equal to zero. The DCT-2, represented by matrix {\bf T}^{\mbox{\scriptsize(C2)}} , has several features that are useful for its efficient computation. The DCT-3, DST-2, and DST-3 also have those features because they are respectively related to the DCT-2 according to [ 5 ] {\bf T}^{\mbox{\scriptsize(C3)}}={\left[{\bf T}^{\mbox{\scriptsize(C2)}}\right]}^{\mbox{\sf\tiny T}},\;{\bf T}^{\mbox{\scriptsize(S2)}}={\bf R}{\bf T}^{\mbox{\scriptsize(C2)}}{\bf S},\;{\bf T}^{\mbox{\scriptsize(S3)}}={\bf S}{\left[{\bf T}^{\mbox{\scriptsize(C2)}}\right]}^{\mbox{\sf\tiny T}}{\bf R}, where the reversal (“flipping”) and interleaved sign changes matrices defined by R_{m,n}=\left\{\begin{array}[]{ll}\!\!1,&\!m=N-1-n,\\ \!\!0,&\!\mbox{otherwise,}\end{array}\right.\;S_{m,n}=\left\{\begin{array}[]{ll}\!\!(-1)^{m},&\!m=n,\\ \!\!0,&\!m\neq n,\end{array}\right. have negligible computational complexity. Figure 3: Example of how the adjustment via band matrix and DST-3 approximates the DST-7, on the transforms of dimension 16. Each subgraph combines the plots of basis functions in increasing frequency. While the process of choosing an adjustment transform that simplifies computations may be empiric, there are tools that can be employed for guidance, and only at the final stages it is necessary to use human expertise to select the most practical and effective choice. For example, if we set {\bf C}={\bf I} , we can

Read the complete text