# An Analytic Transform Kernel Derivation Method for Video Codecs
## 2 Proposed Common Sparse Unified Matrix
### Application of the Proposed Method to the DST-7/DCT-8 Fast Algorithm in VTM  
In Equation (23), a fast DST-7/DCT-8 algorithm with dual support was introduced and adopted in VTM-3.0. The fast algorithm is based on three different features for integer \(N\)-point DST-7/DCT-8 transform kernels shown in Figure 17, which can be defined as Figure 17.  
Where \(\{a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p\}\) are the \(N\)-point unique integer numbers for the 16-point DST-7 kernel. Assume that the output vector \(\mathbf{y}\ =\ [\mathbf{y}_{o},\ \mathbf{y}_{1},\dots,\mathbf{y}_{N-1}]^{T}\) is  
Figure 16: Removing the case not obtaining full kernel matrix by tuning values highlighted. (**a**) Method 1; (**b**) Method 2. Figure 17: Illustration of 16\(-\)point DST–7 kernel unique integer numbers [28]. obtained by multiplying the input vector \(\mathbf{x}=[x_{0},\ x_{1},\ldots,x_{N-1}]^{\mathbf{T}}\) with the transform kernel \(\mathbf{C}\), that is, (\(\mathbf{y}=\mathbf{x}\mathbf{C}\)). **Feature #1:** It is observed that the sum of several (2 or 3) numbers is equal to the sum of several (1 or 2) numbers. The elements \(l\), \(m\), \(n\), \(o\), and \(p\) are obtained by \((a+j)\), \((b+i)\), \((c+h)\), \((d+g)\), and \((e+f)\), respectively. To calculate \(y_{0}\), instead of performing vector-by-vector multiplication that requires 16 multiplications, the following alternative implementation is computed as shown in Equation (25):  
\[\mathbf{y}_{0}=a\cdot(\mathbf{x}_{0}+\mathbf{x}_{11})+b\cdot(\mathbf{x}_{1}+ \mathbf{x}_{12})+\ldots+j\cdot(\mathbf{x}_{9}+\mathbf{x}_{11})+k\cdot\mathbf{ x}_{10} \tag{25}\]  
which requires 10 multiplications. **Feature #2:** This is based on the feature that some elements in a row vector of DST-7 are symmetrically mirrored with each other. For example, the second vector \(\{c,f,i,l,o,o,l,i,f,c,o,-c,-f,-i,-l,-o\}\) in Figure 15(c) with only \(c,f\), \(i\), \(l\), and \(o\) elements. To calculate \(\mathbf{y}_{1}\), instead of performing vector-by-vector multiplication that requires 16 multiplications, the following alternative implementation is computed, as shown in Equation (26):  
\[\mathbf{y}_{1}=c\cdot(\mathbf{x}_{0}+\mathbf{x}_{9}-\mathbf{x}_{11})+f\cdot( \mathbf{x}_{1}+\mathbf{x}_{8}-\mathbf{x}_{12})+i\cdot(\mathbf{x}_{2}+\mathbf{ x}_{7}-\mathbf{x}_{13})+l\cdot(\mathbf{x}_{3}+\mathbf{x}_{6}-\mathbf{x}_{14})+o \cdot(\mathbf{x}_{4}+\mathbf{x}_{5}-\mathbf{x}_{15}) \tag{26}\]  
which requires five multiplications. **Feature #3:** This is based on the basic vectors that contain very few numbers (1 or 2) of distinct values without considering sign values \(\{\)k, k, 0, \(-\)k, \(-\)k, 0, k, k, 0, \(-\)k, \(-\)k, 0, k, k, 0, \(-\)k\(\}\). To calculate \(\mathbf{y}_{5}\), instead of performing vector-by-vector multiplication that requires 16 multiplications, the following alternative implementation is computed as shown in Equation (27):  
\[\mathbf{y}_{5}=k\cdot(\mathbf{x}_{0}+\mathbf{x}_{1}-\ldots-\mathbf{x}_{15}) \tag{27}\]  
which requires one multiplication. The major drawback of the fast algorithm [28] for DST-7 transform in VTM3.0 is that one feature out of the mentioned three features has to be applied in each row. However, once a feature is selected for the basic vector such as \([\mathbf{S}_{7,(0,0)}]_{16}\), \([\mathbf{S}_{7,(1,1)}]_{16}\), \([\mathbf{S}_{7,(2,2)}]_{16}\) and \([\mathbf{S}_{7,(5,5)}]_{16}\), the same feature is applied to vectors belonging to the same group. Hence, the proposed method follows \"one group one feature\" and removes the matching of a single feature among the three features in each row. For example, in the first row, a vector of DST-7, Feature #1 is applied, whereas in the second-row vector, Feature #2 is applied. Similarly, for the other rows, a single feature out of three features was applied. Initially, before applying the feature in each row vector, we were unaware of the feature to be applied in the respective row vector. Consequently, we need to check if the respective row vector follows Feature #1, #2, or #3 such that the single matched feature is applied.