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, 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.