K-L变换

K-L轉換（Template:Lang-en）是建立在統計特性基礎上的一種轉換，它是均方差（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傳換後，輸出向量$𝐗$之元素間($u_1\ne u_2$, $u_1$和$u_2$為$𝐗$之元素的index)的相關性為零，即：$E[(X[u_1]-\overline{X}[u_1])(X[u_2]-\overline{X}[u_2])]=0$

展開上式並做消去：

$E[X[u_1]X[u_2]]-\overline{X}[u_1]\overline{X}[u_2]=0$

如果$\overline{x}[n]=0$，因為KL轉換式線性轉換的關係，$\overline{X}[n]=0$，則可以達成以下式，所以這裡得輸入向量$𝐱$之平均值$\overline{x}$需為$0$，所以KLT是專門用於隨機程序的分析：

$E[X[u_1]X[u_2]]=0$

其中$u_1\ne u_2$，即輸出向量不同元素相關性為$0$。

回到矩陣表示形式，令$𝐊$為KL轉換矩陣，使：

$𝐗=𝐊𝐱$

以$𝐊$和$𝐱$表示$𝐗$之covariance矩陣：

$E[𝐗{𝐗}^T]=E[𝐊𝐱{𝐱}^T{𝐊}^T]=𝐊E[𝐱{𝐱}^T]{𝐊}^T$

因為$\overline{x}[n]=0$，$E[𝐱{𝐱}^T]$直接等於covariance矩陣：

$E[𝐗{𝐗}^T]=𝐊𝐂{𝐊}^T$

其中$𝐂$為$𝐱$之covariance矩陣。

如果要使$E[X[u_1]X[u_2]]=0$，則$E[𝐗{𝐗}^T]$必須為對角線矩陣，即對角線上之值皆為$0$，所以$𝐊$必須將傳換成對角線矩陣，即$𝐊$的每一行皆為$𝐂$之特徵向量。

K-L轉換的目的是將原始數據做轉換，使得轉換後資料的相關性最小。若輸入數據為一維：

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

$K[u,n]=e_n[n]$

其中e_n為輸入訊號x共變異數矩陣(covariance matrix)C_x的特徵向量(eigenvector)

若輸入訊號x為二維：

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

與離散餘弦轉換的關係

二維之K-L轉換推導係自原先輸入信號之自協方矩陣

$C_{x_i{x}_j}=E[x_i,x_j]$

亦即

$C_{x_i{x}_j}=\left[\begin{array}{ccccccc}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]\\ ⋮& ⋮& ⋮& \ddots & ⋮& \ddots & ⋮\\ E[x_i,x_1]& E[x_i,x_2]& E[x_i,x_3]& \dots & E[x_i,x_j]& \dots & a_{in}\\ ⋮& ⋮& ⋮& \ddots & ⋮& \ddots & ⋮\\ 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{array}\right]$

而得，此處假設輸入信號x已經先減去平均值。

而當輸入彼此具高度相關性，如影像等，則可假設其在水平與垂直方向上得以被分離，並以水平與垂直之相關係數${\rho }_H,{\rho }_V$加以表示

假設$x_i$ 與 $x_j$ 之水平和垂直距離分別為$h,v$

則 $E[x_i,x_j]={\rho }_H^h\cdot {\rho }_V^v$

以一3x2之輸入 $X=\left[\begin{array}{ccc}x1& x2& x3\\ x4& x5& x6\end{array}\right]$ 為例

此時 $C_{x_i{x}_j}=\left[\begin{array}{cccccc}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{array}\right]$

而對於任意尺寸的水平或垂直方向之協方差矩陣可以表示成

$C_{xx}=\left[\begin{array}{cccc}\rho & {\rho }^2& \dots & {\rho }^{N-1}\\ {\rho }^2& \rho & \dots & {\rho }^{N-2}\\ ⋮& ⋮& \ddots & ⋮\\ {\rho }^{N-1}& {\rho }^{N-2}& \dots & \rho \end{array}\right]$

可發現其值僅與 $|i-j|$ 有關，取其閉合形式，其基底元素$v_{ij}$ 為

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

此處 ${\lambda }_j$ 為 $C_{xx}$ 之特徵值

${\lambda }_j=\frac{1-{\rho }^2}{1-2\rho \cos {\omega }_j+{\rho }^2}$

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

對於不同的輸入影像，其$\rho$會有所不同，而若是令 $\rho \to 1$，則此轉換不必與輸入相關，同時繼承了K-L轉換去除相關性的優異性質。

此時 ${\lambda }_j=\{\begin{array}{cc}N,& \text{if }j=1\\ 0,& \text{if }j\ne 1\end{array}$

代入上式，得 KLT|$\rho \to 1$ ，$v_{ij}=\{\begin{array}{cc}\sqrt{\frac{1}{N}}\cos \frac{(2i-1)(j-1)\pi }{2N},& \text{if }j=1\\ \sqrt{\frac{2}{N}}\cos \frac{(2i-1)(j-1)\pi }{2N},& \text{if }j\ne 1\end{array}$

離散餘弦轉換較K-L轉換在實務上較為有利，因其毋須紀錄會隨輸入而改變的轉換矩陣。

KLT與PCA的區別

KLT和主成分分析(PCA, Principle component analysis) 有相似的特性，二者之間有很細微的差異，其中KLT專門處理隨機性的訊號，但PCA則沒有這個限制。對PCA而言，這裡假設輸入訊號為ㄧ向量，輸入向量$𝐱$在乘上轉換矩陣$𝐖$之前，會先將輸入向量扣去平均值，即:

$𝐗=𝐖(𝐱-\overline{x})$

PCA會根據$𝐱$之covariance矩陣來選擇特徵向量做為轉換矩陣之內容：

$E[(𝐱-\overline{x})(𝐱-\overline{x}{)}^T]={𝐖\mathrm{\Lambda }𝐖}^T$

其中$\mathrm{\Lambda }$為對角線矩陣且對角線值為特徵值。

由上述可見PCA和KLT之差異在於有沒有減去平均值，這是由於輸入資料分布的限制造成的，當輸入向量支平均值為零時，二這者沒有差異。

應用

在影像的壓縮上，目的是要將原始的影像檔用較少的資料量來表示，由於大部分的影像並不是隨機的分布，相鄰的像素(Pixal)間存在一些相關性，如果我們能找到一種可逆轉換(reversible transformation)，它可以去除數據的相關性，如此一來就能更有效地儲存資料，由於K-L轉換是一種線性轉換，並有去除資料相關性的特性，便可以將它應用在影像的壓縮上。此外，由於K-L轉換具有將訊號轉到特徵空間(eigenspace)的特性，因此也可以應用在人臉辨識上。

 参考文献

1. Ding, J. J. (2017). Advanced Digital Signal Processing [Powerpoint slides] -{R|http://djj.ee.ntu.edu.tw/ADSP8.pdf}- Template:Wayback

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