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

对输入向量 做KL传换后,输出向量 之元素间( ,    之元素的index)的相关性为零,即: 

展开上式并做消去:

 

如果 ,因为KL变换式线性变换的关系, ,则可以达成以下式,所以这里得输入向量 之平均值 需为 ,所以KLT是专门用于随机程序的分析:

 

其中 ,即输出向量不同元素相关性为 

回到矩阵表示形式,令 为KL变换矩阵,使:

 

  表示 之covariance矩阵:

 

因为  直接等于covariance矩阵:

 

其中  之covariance矩阵。

如果要使 ,则 必须为对角线矩阵,即对角线上之值皆为 ,所以 必须将传换成对角线矩阵,即 的每一行皆为 之特征向量。

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

 

 

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

若输入讯号x为二维:

 

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

编辑

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

 

亦即

 

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

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

假设   之水平和垂直距离分别为 

 

以一3x2之输入   为例

此时  

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

 

可发现其值仅与   有关,取其闭合形式,其基底元素 

 

此处    之特征值

 

其中  

对于不同的输入影像,其 会有所不同,而若是令  ,则此变换不必与输入相关,同时继承了K-L变换去除相关性的优异性质。

此时  

代入上式,得 KLT|  

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

KLT与PCA的区别

编辑

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

 

PCA会根据 之covariance矩阵来选择特征向量做为变换矩阵之内容:

 

其中 为对角线矩阵且对角线值为特征值。

由上述可见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.