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}\neq u_{2}}$, ${\displaystyle u_{1}}$和${\displaystyle u_{2}}$为${\displaystyle \mathbf {X} }$之元素的index)的相关性为零，即：${\displaystyle E[(X[u_{1}]-{\bar {X}}[u_{1}])(X[u_{2}]-{\bar {X}}[u_{2}])]=0}$

展开上式并做消去：

${\displaystyle E[X[u_{1}]X[u_{2}]]-{\bar {X}}[u_{1}]{\bar {X}}[u_{2}]=0}$

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

${\displaystyle E[X[u_{1}]X[u_{2}]]=0}$

其中${\displaystyle u_{1}\neq u_{2}}$，即输出向量不同元素相关性为${\displaystyle 0}$。

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

${\displaystyle \mathbf {X} =\mathbf {Kx} }$

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

${\displaystyle E[\mathbf {X} \mathbf {X} ^{T}]=E[\mathbf {K} \mathbf {x} \mathbf {x} ^{T}\mathbf {K} ^{T}]=\mathbf {K} E[\mathbf {x} \mathbf {x} ^{T}]\mathbf {K} ^{T}}$

因为${\displaystyle {\bar {x}}[n]=0}$，${\displaystyle E[\mathbf {x} \mathbf {x} ^{T}]}$直接等于covariance矩阵：

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

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

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

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

${\displaystyle y[u]=\sum _{n=0}^{N-1}K[u,n]x[n]}$

${\displaystyle K[u,n]=e_{n}[n]}$

其中e_n为输入讯号x协方差矩阵(covariance matrix)C_x的特征向量(eigenvector)

若输入讯号x为二维：

${\displaystyle y[u,v]=\sum _{m=0}^{M-1}\sum _{n=0}^{N-1}K[u,m]K[v,m]x[m,n]}$

与离散余弦变换的关系 [1]

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

${\displaystyle C_{x_{i}x_{j}}=E[x_{i},x_{j}]}$

亦即

${\displaystyle C_{x_{i}x_{j}}={\begin{bmatrix}E[x_{1},x_{1}]&E[x_{1},x_{2}]&E[x_{1},x_{3}]&\dots &E[x_{1},x_{j}]&\dots &E[x_{1},x_{N}]\\E[x_{2},x_{1}]&E[x_{2},x_{2}]&E[x_{2},x_{3}]&\dots &E[x_{2},x_{j}]&\dots &E[x_{2},x_{N}]\\\vdots &\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\E[x_{i},x_{1}]&E[x_{i},x_{2}]&E[x_{i},x_{3}]&\dots &E[x_{i},x_{j}]&\dots &a_{in}\\\vdots &\vdots &\vdots &\ddots &\vdots &\ddots &\vdots \\E[x_{M},x_{1}]&E[x_{M},x_{2}]&E[x_{M},x_{3}]&\dots &E[x_{M},x_{j}]&\dots &E[x_{M},x_{N}]\end{bmatrix}}}$

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

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

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

则 ${\displaystyle E[x_{i},x_{j}]=\rho _{H}^{h}\cdot \rho _{V}^{v}}$

以一3x2之输入 ${\displaystyle X={\begin{bmatrix}x1&x2&x3\\x4&x5&x6\end{bmatrix}}}$ 为例

此时 ${\displaystyle C_{x_{i}x_{j}}={\begin{bmatrix}1&\rho _{H}&\rho _{H}^{2}&\rho _{V}&\rho _{H}\rho _{V}&\rho _{H}^{2}\cdot \rho _{V}\\\rho _{H}&1&\rho _{H}&\rho _{H}\rho _{V}&\rho _{V}&\rho _{H}\rho _{V}\\\rho _{H}^{2}\rho _{V}&\rho _{H}&1&\rho _{H}^{2}\rho _{V}&\rho _{H}\rho _{V}&\rho _{V}\\\rho _{V}&\rho _{H}\rho _{V}&\rho _{H}^{2}\rho _{V}&1&\rho _{H}&\rho _{H}^{2}\\\rho _{H}\rho _{V}&\rho _{V}&\rho _{H}\rho _{V}&\rho _{H}&1&\rho _{H}\\\rho _{H}^{2}\rho _{V}&\rho _{H}\rho _{V}&\rho _{V}&\rho _{H}^{2}&\rho _{H}&1\end{bmatrix}}}$

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

${\displaystyle C_{xx}={\begin{bmatrix}\rho &\rho ^{2}&\dots &\rho ^{N-1}\\\rho ^{2}&\rho &\dots &\rho ^{N-2}\\\vdots &\vdots &\ddots &\vdots \\\rho ^{N-1}&\rho ^{N-2}&\dots &\rho \end{bmatrix}}}$

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

${\displaystyle v_{ij}={\sqrt {\frac {2}{N+\lambda _{j}}}}\sin {({\frac {(2i-N-1)\omega }{2}}+{\frac {j\pi }{2}})}}$

此处 ${\displaystyle \lambda _{j}}$ 为 ${\displaystyle C_{xx}}$ 之特征值

${\displaystyle \lambda _{j}={\frac {1-\rho ^{2}}{1-2\rho \,\cos {\omega _{j}}+\rho ^{2}}}}$

其中 ${\displaystyle \tan(N\omega _{j})=-{\frac {(1-\rho ^{2})\sin {\omega _{j}}}{\cos {\omega _{j}}-2\rho +\rho ^{2}\cos {\omega _{j}}}}}$

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

此时 ${\displaystyle \lambda _{j}=\left\{{\begin{matrix}N,&{\mbox{if }}j=1\\0,&{\mbox{if }}j\neq 1\end{matrix}}\right.}$

代入上式，得 KLT|${\displaystyle \rho \rightarrow 1}$ ，${\displaystyle v_{ij}=\left\{{\begin{matrix}{\sqrt {\frac {1}{N}}}\cos {\frac {(2i-1)(j-1)\pi }{2N}},&{\mbox{if }}j=1\\{\sqrt {\frac {2}{N}}}\cos {\frac {(2i-1)(j-1)\pi }{2N}},&{\mbox{if }}j\neq 1\end{matrix}}\right.}$

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

KLT与PCA的区别

KLT和主成分分析(PCA, Principle component analysis) 有相似的特性，二者之间有很细微的差异，其中KLT专门处理随机性的讯号，但PCA则没有这个限制。对PCA而言，这里假设输入讯号为ㄧ向量，输入向量${\displaystyle \mathbf {x} }$在乘上变换矩阵${\displaystyle \mathbf {W} }$之前，会先将输入向量扣去平均值，即:

${\displaystyle \mathbf {X} =\mathbf {W} (\mathbf {x} -{\bar {x}})}$

PCA会根据${\displaystyle \mathbf {x} }$之covariance矩阵来选择特征向量做为变换矩阵之内容：

${\displaystyle E[(\mathbf {x} -{\bar {x}})(\mathbf {x} -{\bar {x}})^{T}]=\mathbf {W\Lambda W} ^{T}}$

其中${\displaystyle \mathbf {\Lambda } }$为对角线矩阵且对角线值为特征值。

由上述可见PCA和KLT之差异在于有没有减去平均值，这是由于输入资料分布的限制造成的，当输入向量支平均值为零时，二这者没有差异。

应用

在影像的压缩上，目的是要将原始的影像档用较少的资料量来表示，由于大部分的影像并不是随机的分布，相邻的像素(Pixal)间存在一些相关性，如果我们能找到一种可逆变换(reversible transformation)，它可以去除数据的相关性，如此一来就能更有效地储存资料，由于K-L变换是一种线性变换，并有去除资料相关性的特性，便可以将它应用在影像的压缩上。此外，由于K-L变换具有将讯号转到特征空间(eigenspace)的特性，因此也可以应用在人脸辨识上。