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为二维:
二维之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
- ^ 酒井善则,吉田俊之原著,原岛博监修,白执善编译,“影像压缩术",全华印行, 2004.