# An Analytic Transform Kernel Derivation Method for Video Codecs
## 2 Proposed Common Sparse Unified Matrix
### Unified DST-3 Matrix (**U**)  
The proposed unified DST-3 matrix (**U**) was used to derive DCT-2 transform kernels of different sizes. It stores only 1368 elements with 8-bit precision for deriving any block size of the DCT-2 transform kernel, whereas the current VVC allocates memory for 5460 elements with 8-bit precision for deriving different block sizes of the DCT-2 transform kernels. The proposed basic structure of the unified DST-3 matrix is shown in Figure 2.  
Figure 1: Common sparse unified matrix. The matrix \(\mathbf{U}\) comprises 32, 16, 8, 4, and 2-point DST-4 and a 2-point DST-3 matrix. The remaining elements of \(\mathbf{U}\) were set to zero. A relationship exists between DST-3 and DCT-2 [26], which can be expressed as Equation (6). \[\mathbf{C}_{2}=\mathbf{F}\times\mathbf{S}_{3}\times\mathbf{S} \tag{6}\]  
where \(\mathbf{C}_{2}\) is DCT-2, \(\mathbf{S}_{3}\) is DST-3, and \(\mathbf{F}\) and \(\mathbf{S}\) are flipping and sign change matrices, respectively. The elements in \(\mathbf{F}\) and \(\mathbf{S}\) are defined as  
\[F_{m,n}= \begin{cases}1,&\text{if }n=N-1-m,\\ 0,&\text{otherwise},\end{cases}  \tag{7}\]  
\[S_{m,n}= \begin{cases}(-1)^{m},&\text{if }n=m,\\ 0,&\text{otherwise}.\end{cases}  \tag{8}\]  
where \(m\) and \(n\) are matrix indices, and \(N\) is the size of the matrix. To retrieve any block size of the DCT-2 kernel, different block sizes of the DST-3 kernel are required, as in (6). As shown in Figure 2, a 2-point DST-3 transform kernel matrix exists at the right bottom part of \(\mathbf{U}\). Using (6) and the 2-point DST-3 transform kernel, a 2-point DCT-2 transform kernel can be derived. Similarly, different block sizes of DST-3 transform kernels are required to derive other sizes of DCT-2 transform kernels. To obtain different block sizes of DST-3 transform kernels from \(\mathbf{U}\), the predefined 64-point unit-element matrices, \(\mathbf{A}\), \(\mathbf{B}\), \(\mathbf{C}\), \(\mathbf{D}\), and \(\mathbf{E}\), are multiplied by \(\mathbf{U}\). Figure 3 shows the DST-3 derivation mechanism from unified DST-3 matrix (\(\mathbf{U}\)). The unit-element matrices \(\mathbf{A}\), \(\mathbf{B}\), \(\mathbf{C}\), \(\mathbf{D}\), and \(\mathbf{E}\) are the matrices with values of \(-1\), \(0\), or \(1\), and their elements are defined as Equations (9)-(13), respectively. \[A_{m,n}=\left\{ \begin{array}{cc}1\,,&if\ (m=n,\ \forall\ 0<(m,n)<60)\ ||\\ &(m=n,\ \forall\ 60<(m,n)<62)\ \ ||\\ &\left(\begin{array}{c}m+n=123\ \forall\ (61<m<64)\ and\\ (60<n<62)\end{array}\right)\ ||\\ &\left(\begin{array}{c}i-j=-2,\ \ \ \ \ \ \ \forall\ (60<m<62)\ and\\ (61<n<64)\end{array}\right)\\ -1\,,&if\ (m+n=125,\ \forall\ 61<(m,n)<64\\ 0\,,&elsewhere\end{array} \right. \tag{9}\]  
Figure 2: Structure of unified DST-3 matrix (\(\mathbf{U}\)). matrices, DST-3 transform kernels with different sizes can be obtained, which is explained using Equations (15)-(19)  
\[\mathbf{S}_{3,A}=\mathrm{T}[\mathbf{U}_{64}\times\mathbf{A}_{64}]_{4} \tag{15}\]  
\[\mathbf{S}_{3,8}=\mathrm{T}[\mathbf{U}_{64}\times\mathbf{M}_{64}]_{8} \tag{16}\]  
\[\mathbf{S}_{3,16}=\mathrm{T}[\mathbf{U}_{64}\times\mathbf{N}_{64}]_{16} \tag{17}\]  
\[\mathbf{S}_{3,32}=\mathrm{T}[\mathbf{U}_{64}\times\mathbf{O}_{64}]_{32} \tag{18}\]  
\[\mathbf{S}_{3,64}=\mathbf{U}_{64}\times\mathbf{P}_{64} \tag{19}\]  
where \(\mathbf{S}_{3,\,N}\) is an \(N\)-point DST-3 transform kernel, \(\mathrm{T}[]_{N}\) represents a function that takes an \(N\times N\) block of the right-bottom part of the matrix, and \(\mathbf{M,\,N,O,}\) and \(\mathbf{P}\) are defined using unit elements (\(-1,\,0,\) and \(1\)) as in Equation (20). \[ \begin{split}\mathbf{M}=\mathbf{A}\times\mathbf{B}\\ \mathbf{N}=\mathbf{A}\times\mathbf{B}\times\mathbf{C}\\ \mathbf{O}=\mathbf{A}\times\mathbf{B}\times\mathbf{C}\times \mathbf{D}\\ \mathbf{P}=\mathbf{A}\times\mathbf{B}\times\mathbf{C}\times \mathbf{D}\times\mathbf{E}\end{split}  \tag{20}\]  
For example, to derive the 16-point DCT-2 kernel, a 16-point DST-3 is required, as in Equation (6).