H.266 JEM7.0 变换之三（信号依赖的变换 SDT）

Signal dependent transform, SDT
考虑到帧内和帧之间存在许多类似的块，依赖于信号的变换探索这样的相关性发现可以通过KLT增强编码性能。这种训练的KLT扮演一种变换的角色，其目的是更有效地集中能量。

对当前编码块C而言，首先，获取包含重构左上模板tb和编码块的预测块p的参考块R。然后，参考块被用来在重构区域中找N个最相似块。最后，计算基于这些块的一维KLT（Karhunen-Loéve transform）和预测块。编码块在解码端的相似候选块中是未知的。预测块和重构模板被用来指导寻找相邻块的操作，而不是使用原始块。这个工具支持4×4, 8×8, 16×16以及32×32的块大小。
KLT为集中能量的最佳变换。通过在重构区域中进行搜索，得到N个与参考块最相相似的块xi,i=1,2,……N$x_i,i=1,2,\dots \dots N$。此处，xi=(xi1,xi2……xiD)T$x_i=(x_{i1},x_{i2}\dots \dots x_{iD}{)}^T$，D表示向量维度，是变化块大小。如，4x4的编码块，D为16(原提案中写的是N为16，个人觉得是D)。块的预测p$p$减去并获得残差块，为ui,i=1,2,……N$u_i,i=1,2,\dots \dots N$，ui=(xi−p)/N−−√$u_i=(x_i-p)/\sqrt{N}$。这些残差块被用为KLT求导零均值的训练样本。这些N个训练样本可以表示为：U=(u1,u2……uN)$U=(u_1,u_2\dots \dots u_N)$，是一个DxN的矩阵。考虑协方差矩阵Σ$\mathrm{\Sigma }$为：Σ=UUT$\mathrm{\Sigma }=U{U}^T$。协方差矩阵的维度为DxD。KLT的基是该协方差矩阵的特征向量。对于自然图像/视频内容，候选数N选为100就可获取足够好的性能。
这个特征值分解的计算复杂度为O(D3)$O(D^3)$。对于D=16的4x4的块而言，复杂度达到O(163)$O({16}^3)$，在可接受范围内。然而对于大块而言，复杂度很高。32x32的块D为1024，时间复杂度将达4x4块的262144倍。基于此，采用一个大块的快速算法。Σ$\mathrm{\Sigma }$的维度为DxD。然而UTU$U^{T}U$维度更低，为NxN。计算Σ′=UTU${\mathrm{\Sigma }}^{\prime }=U^{T}U$的特征向量，其满足：

UTUϕ=ϕΛ$U^{T}U\varphi =\varphi \mathrm{\Lambda }$

其中ϕ$\varphi$是特征矩阵，Λ$\mathrm{\Lambda }$表示特征值是对角线元素的对角阵。对上公示左右均乘U$U$：

(UUT)(Uϕ)=(Uϕ)Λ$(U{U}^T)(U\varphi )=(U\varphi )\mathrm{\Lambda }$

从上式可知，Uϕ$U\varphi$的列向量是UUT$U{U}^T$的特征向量，其对应特征值是矩阵Λ$\mathrm{\Lambda }$的对角元素。令φ=Uϕ$\phi =U\varphi$。表明高维度协方差矩阵UUT$U{U}^T$的特征向量可以通过乘有特征向量ϕ$\varphi$的U$U$获得，特征向量是通过低维度协方差矩阵UTU$U^{T}U$获得的。φ$\phi$和Λ$\mathrm{\Lambda }$的维度均为DxN。所有UUT$U{U}^T$其余(D−N)$(D-N)$特征值都是零特征向量。可采用施密特正交化来填补(D−N)$(D-N)$个特征向量来得到DxD的特征矩阵。
为了降低矩阵乘法的计算复杂度，可以用获取的N个特征向量进行KLT变化，将其余(D−N)$(D-N)$个变换系数视为零。此操作不会削弱性能，因为第一个N投影可以覆盖大部分信号能量，而基是从与编码块高度相关的样本训练的。
上述的KLT加入块级别的编码过程。为了对图像/视频内容有更高的适应性，支持4x4，8x8，16x16，32x32的编码块的所提KLT。JEM编码端，率失真优化被用来决定使用SDT和AMT中的变换模式。

代码实现

1. 帧内：帧内KLT主要通过函数xRecurIntraCodingLumaQT()调用的TEncSearch::xIntraCodingTUBlockTM()实现。该函数的主要步骤为：
   a. 通过函数getTargetTemplate()获取上方及左侧模板；
   b. 通过candidateSearchIntra()查找亮度块的最佳匹配块 ，主要通过函数searchCandidateFromOnePicIntra()实现，首先在块所在LCU内进行搜索，之后在LCU外搜索；
   c. 通过函数generateTMPrediction()获取模板匹配的预测块
   d. 通过函数calcKLTIntra()中调用的deriveKLT()完成协方差矩阵的计算，得到特征向量矩阵。
   e. 得到残差，进行变换量化及后续操作。变换中若useKLT = true，则会调用xKLTr()函数进行KLT变换。
2. 帧间：帧间KLT主要通过函数TEncSearch::xEstimateInterResidualQT()实现。函数中，若采用CrossComponent模式，选择该模式下的变换；否则，若使用KLT，通过函数getTargetPatch()``candidateSearch()``candidateTrain()进行KLT的相关操作。最后进行变换及量化。