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变换属于正交变换，其处输入讯号的原理如下：

对输入向量<math>\mathbf{x}</math>做KL传换后，输出向量<math>\mathbf{X}</math>之元素间(<math>u_1\neq u_2</math>, <math>u_1</math>和<math>u_2</math>为<math>\mathbf{X}</math>之元素的index)的相关性为零，即：<math>E[(X[u_1]-\bar{X}[u_1])(X[u_2]-\bar{X}[u_2])]=0</math>

展开上式并做消去：

<math>E[X[u_1]X[u_2]]-\bar{X}[u_1]\bar{X}[u_2]=0</math>

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

<math>E[X[u_1]X[u_2]]=0</math>

其中<math>u_1\neq u_2</math>，即输出向量不同元素相关性为<math>0</math>。

回到矩阵表示形式，令<math>\mathbf{K}</math>为KL变换矩阵，使：

<math>\mathbf{X}=\mathbf{Kx}</math>

以<math>\mathbf{K}</math>和<math>\mathbf{x}</math>表示<math>\mathbf{X}</math>之covariance矩阵：

<math>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</math>

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

<math>E[\mathbf{X}\mathbf{X}^T]=\mathbf{K}\mathbf{C}\mathbf{K}^T</math>

其中<math>\mathbf{C}</math>为<math>\mathbf{x}</math>之covariance矩阵。

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

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

<math>y[u]=\sum_{n=0}^{N-1}K[u,n]x[n]</math>

<math>K[u,n]=e_{n}[n]</math>

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

若输入讯号x为二维：

<math>y[u,v]=\sum_{m=0}^{M-1}\sum_{n=0}^{N-1}K[u,m]K[v,m]x[m,n]</math>

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

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

<math>C_{x_ix_j}=E[x_i,x_j]</math>

亦即

<math>C_{x_ix_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_{i n}\\ \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}</math>

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

而当输入彼此具高度相关性，如影像等，则可假设其在水平与垂直方向上得以被分离，并以水平与垂直之相关系数<math>\rho_H, \rho_V</math>加以表示

假设<math>x_i</math> 与 <math>x_j</math> 之水平和垂直距离分别为<math>h,v</math>

则 <math> E[x_i,x_j]=\rho_H^{h} \cdot \rho_V^{v} </math>

以一3x2之输入 <math>X=\begin{bmatrix} x1 & x2 & x3 \\ x4 & x5 & x6\end{bmatrix}</math> 为例

此时 <math>C_{x_ix_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}</math>

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

<math>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}</math>

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

<math> v_{ij}= \sqrt{\frac{2}Template:N+\lambda j}\sin{(\frac{(2i-N-1)\omega}{2}+\frac{j\pi}{2})}</math>

此处 <math> \lambda_j</math> 为 <math> C_{xx} </math> 之特征值

<math> \lambda_j=\frac{1-\rho^2}{1-2\rho \, \cos{\omega_j} + \rho^2} </math>

其中 <math> \tan(N\omega_j)=-\frac{(1-\rho^2)\sin{\omega_j}}{\cos{\omega_j}-2\rho+\rho^2\cos{\omega_j}}</math>

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

此时 <math> \lambda_j=\left\{\begin{matrix} N, & \mbox{if }j=1 \\ 0, & \mbox{if }j \neq 1 \end{matrix}\right.</math>

代入上式，得 KLT|<math>\rho\rightarrow1</math> ，<math> 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.</math>

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

KLT与PCA的区别[编辑]

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

<math>\mathbf{X}=\mathbf{W}(\mathbf{x}-\bar{x})</math>

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

<math>E[(\mathbf{x}-\bar{x})(\mathbf{x}-\bar{x})^T]=\mathbf{W\Lambda W}^T</math>

其中<math>\mathbf{\Lambda}</math>为对角线矩阵且对角线值为特征值。

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

应用[编辑]

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

 参考文献[编辑]

1. Ding, J. J. (2017). Advanced Digital Signal Processing [Powerpoint slides] http://djj.ee.ntu.edu.tw/ADSP8.pdf （页面存档备份，存于互联网档案馆）

2. Gerbrands, J.J., On the relationships between SVD, KLT, and PCA, Pattern Recogn., 14 (1981), pp. 375–381

  1. ^ 酒井善则，吉田俊之原著，原岛博监修，白执善编译，“影像压缩术＂，全华印行, 2004.
检索自“https://arolstar52-zhtest.hf.space/index.php?title=K-L变换&oldid=2152805”