K-L变换

K-L转换(Karhunen-Loève Transform)是建立在统计特性基础上的一种转换，它是均方差(MSE, Mean Square Error)意义下的最佳转换，因此在资料压缩技术中占有重要的地位。

K-L转换名称来自Kari Karhunen和Michel Loève。

K-L转换是对输入的向量x，做一个正交变换，使得输出的向量得以去除数据的相关性。

然而，K-L转换虽然具有均方差(MSE)意义下的最佳转换，但必须事先知道输入的讯号，并且需经过一些繁杂的数学运算，例如协方差(covariance)以及特征向量(eigenvector)的计算。因此在工程实践上K-L转换并没有被广泛的应用，不过K-L转换是理论上最佳的方法，所以在寻找一些不是最佳、但比较好实现的一些转换方法时，K-L转换能够提供这些转换性能的评价标准。

以处理图片为范例，在K-L转换途中，图片的能量会变得集中，有助于压缩图片，但是实际上，KL转算为input-dependent，即需要对每张输入图片存下一个转换机制，每张图都不一样，这在实务应用上是不实际的。

KL转换属于正交转换，其处输入讯号的原理如下：

对输入向量${\displaystyle \mathbf{x}}$做KL传换后，输出向量${\displaystyle \mathbf{X}}$之元素间(${\displaystyle u_1\ne <!--\; \ne \; -->u_2}$, ${\displaystyle u_1}$和${\displaystyle u_2}$为${\displaystyle \mathbf{X}}$之元素的index)的相关性为零，即：${\displaystyle E-<!--\; -\; -->\stackrel{¯<!--\; ¯\; -->}{X})(X-<!--\; -\; -->\stackrel{¯<!--\; ¯\; -->}{X})]=0}$

展开上式并做消去：

${\displaystyle EX]-<!--\; -\; -->\stackrel{¯<!--\; ¯\; -->}{X}\stackrel{¯<!--\; ¯\; -->}{X}=0}$

如果${\displaystyle \stackrel{¯<!--\; ¯\; -->}{x}=0}$，因为KL转换式线性转换的关系，${\displaystyle \stackrel{¯<!--\; ¯\; -->}{X}=0}$，则可以达成以下式，所以这里得输入向量${\displaystyle \mathbf{x}}$之平均值${\displaystyle \stackrel{¯<!--\; ¯\; -->}{x}}$需为${\displaystyle 0}$，所以KLT是专门用于随机程序的分析：

${\displaystyle EX]=0}$

其中${\displaystyle u_1\ne <!--\; \ne \; -->u_2}$，即输出向量不同元素相关性为${\displaystyle 0}$。

回到矩阵表示形式，令${\displaystyle \mathbf{K}}$为KL转换矩阵，使：

${\displaystyle \mathbf{X}=\mathbf{K}\mathbf{x}}$

以${\displaystyle \mathbf{K}}$和${\displaystyle \mathbf{x}}$表示${\displaystyle \mathbf{X}}$之covariance矩阵：

${\displaystyle E=E=\mathbf{K}E{\mathbf{K}}^T}$

因为${\displaystyle \stackrel{¯<!--\; ¯\; -->}{x}=0}$，${\displaystyle E}$直接等于covariance矩阵：

${\displaystyle E=\mathbf{K}\mathbf{C}{\mathbf{K}}^T}$

其中${\displaystyle \mathbf{C}}$为${\displaystyle \mathbf{x}}$之covariance矩阵。

如果要使${\displaystyle EX]=0}$，则${\displaystyle E}$必须为对角线矩阵，即对角线上之值皆为${\displaystyle 0}$，所以${\displaystyle \mathbf{K}}$必须将传换成对角线矩阵，即${\displaystyle \mathbf{K}}$的每一行皆为${\displaystyle \mathbf{C}}$之特征向量。

K-L转换的目的是将原始数据做转换，使得转换后资料的相关性最小。若输入数据为一维：

${\displaystyle y=\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}Kx}$

${\displaystyle K=e_n}$

其中e_n为输入讯号x共变异数矩阵(covariance matrix)C_x的特征向量(eigenvector)

若输入讯号x为二维：

${\displaystyle y=\underset{m=0}{\overset{M-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}\underset{n=0}{\overset{N-<!--\; -\; -->1}{\sum <!--\; \sum \; -->}}KKx}$

二维之K-L转换推导系自原先输入信号之自协方矩阵

${\displaystyle C_{x_i{x}_j}=E}$

亦即

而得，此处假设输入信号x已经先减去平均值。

而当输入彼此具高度相关性，如影像等，则可假设其在水平与垂直方向上得以被分离，并以水平与垂直之相关系数${\displaystyle {\mathrm{\rho <!--\; \rho \; -->}}_H,{\mathrm{\rho <!--\; \rho \; -->}}_V}$加以表示

假设${\displaystyle x_i}$ 与 ${\displaystyle x_j}$ 之水平和垂直距离分别为${\displaystyle h,v}$

则 ${\displaystyle E={\mathrm{\rho <!--\; \rho \; -->}}_H^h\cdot <!--\; \cdot \; -->{\mathrm{\rho <!--\; \rho \; -->}}_V^v}$

以一3x2之输入 为例

此时

而对于任意尺寸的水平或垂直方向之协方差矩阵可以表示成

可发现其值仅与 ${\displaystyle |i-<!--\; -\; -->j|}$ 有关，取其闭合形式，其基底元素${\displaystyle v_{ij}}$ 为

${\displaystyle v_{ij}=\sqrt{\frac{2}{N+{\mathrm{\lambda <!--\; \lambda \; -->}}_j}}\sin <!--\; \; -->(\frac{(2i-<!--\; -\; -->N-<!--\; -\; -->1)\mathrm{\omega <!--\; \omega \; -->}}{2}+\frac{j\mathrm{\pi <!--\; \pi \; -->}}{2})}$

此处 ${\displaystyle {\mathrm{\lambda <!--\; \lambda \; -->}}_j}$ 为 ${\displaystyle C_{xx}}$ 之特征值

${\displaystyle {\mathrm{\lambda <!--\; \lambda \; -->}}_j=\frac{1-<!--\; -\; -->{\mathrm{\rho <!--\; \rho \; -->}}^2}{1-<!--\; -\; -->2\mathrm{\rho <!--\; \rho \; -->}\cos <!--\; \; -->{\mathrm{\omega <!--\; \omega \; -->}}_j+{\mathrm{\rho <!--\; \rho \; -->}}^2}}$

其中 ${\displaystyle \tan <!--\; \; -->(N{\mathrm{\omega <!--\; \omega \; -->}}_j)=-<!--\; -\; -->\frac{(1-<!--\; -\; -->{\mathrm{\rho <!--\; \rho \; -->}}^2)\sin <!--\; \; -->{\mathrm{\omega <!--\; \omega \; -->}}_j}{\cos <!--\; \; -->{\mathrm{\omega <!--\; \omega \; -->}}_j-<!--\; -\; -->2\mathrm{\rho <!--\; \rho \; -->}+{\mathrm{\rho <!--\; \rho \; -->}}^2\cos <!--\; \; -->{\mathrm{\omega <!--\; \omega \; -->}}_j}}$

对于不同的输入影像，其${\displaystyle \mathrm{\rho <!--\; \rho \; -->}}$会有所不同，而若是令 ${\displaystyle \mathrm{\rho <!--\; \rho \; -->}\to <!--\; \to \; -->1}$，则此转换不必与输入相关，同时继承了K-L转换去除相关性的优异性质。

此时

代入上式，得 KLT|${\displaystyle \mathrm{\rho <!--\; \rho \; -->}\to <!--\; \to \; -->1}$ ，

离散余弦转换较K-L转换在实务上较为有利，因其毋须纪录会随输入而改变的转换矩阵