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 轉換屬於正交轉換，其處輸入訊號的原理如下：

對輸入向量 $\mathbf {x} $ 做 KL 傳換後，輸出向量 $\mathbf {X} $ 之元素間 ( $u_{1}\neq u_{2}$ , $u_{1}$ 和 $u_{2}$ 為 $\mathbf {X} $ 之元素的 index) 的相關性為零，即： $E[(X[u_{1}]-{\bar {X}}[u_{1}])(X[u_{2}]-{\bar {X}}[u_{2}])]=0$

展開上式並做消去：

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

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

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

其中 $u_{1}\neq u_{2}$ ，即輸出向量不同元素相關性為 $0$ 。

回到矩陣表示形式，令 $\mathbf {K} $ 為 KL 轉換矩陣，使：

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

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

$$
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}
$$

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

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

其中 $\mathbf {C} $ 為 $\mathbf {x} $ 之 covariance 矩陣。

如果要使 $E[X[u_{1}]X[u_{2}]]=0$ ，則 $E[\mathbf {X} \mathbf {X} ^{T}]$ 必須為對角線矩陣，即對角線上之值皆為 $0$ ，所以 $\mathbf {K} $ 必須將傳換成對角線矩陣，即 $\mathbf {K} $ 的每一行皆為 $\mathbf {C} $ 之特徵向量。

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

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

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

其中 en 為輸入訊號 x 共變異數矩陣 (covariance matrix) Cx 的特徵向量 (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}}={\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 已經先減去平均值。

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

假設 $x_{i}$ 與 $x_{j}$ 之水平和垂直距離分別為 $h,v$

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

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

此時 $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}}$

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

$$
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}}
$$

可發現其值僅與 $|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 \rightarrow 1$ ，則此轉換不必與輸入相關，同時繼承了 K-L 轉換去除相關性的優異性質。

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

代入上式，得 KLT| $\rho \rightarrow 1$ ， $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 而言，這裡假設輸入訊號為ㄧ向量，輸入向量 $\mathbf {x} $ 在乘上轉換矩陣 $\mathbf {W} $ 之前，會先將輸入向量扣去平均值，即:

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

PCA 會根據 $\mathbf {x} $ 之 covariance 矩陣來選擇特徵向量做為轉換矩陣之內容：

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

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

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