檢視 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 _ { 一 } \ neq u _ { 二 } $ , $ u _ { 一 } $ 和 $ u _ { 二 } $ 為 $ \ mathbf { X } $ 之元素的 index ) 的相關性做零，即：$ E [( X [ u _ { 一 }]-{ \ bar { X } } [u _ { 一 }] ) ( X [u _ { 二 }]-{ \ bar { X } } [u _ { 二 }] ) ]=零 $

展開上式並做消去：

$ $
E [X [ u _ { 一 }] X [u _ { 二 }] ]-{ \ bar { X } } [u _ { 一 }] { \ bar { X } } [u _ { 二 }]=零
$ $

若是 $ { \ bar { x } } [n]=零 $，因為乎 KL 轉換式線性轉換的關係，$ { \ bar { X } } [n]=零 $，會當達成以下式，所以遮有輸入向量 $ \ mathbf { x } $ 之平均值 $ { \ bar { x } } $ 需要為 $ 零 $，所以乎 KLT 是專門用佇隨機的程序的分析：

$ $
E [X [ u _ { 一 }] X [u _ { 二 }] ]=零
$ $

其中 $ u _ { 一 } \ neq u _ { 二 } $，就輸出向量無仝款元素相關性為 $ 零 $。

轉去到矩陣表示形式，令 $ \ 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]=零 $，$ 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 _ { 一 }] X [u _ { 二 }] ]=零 $，著 $ E [\ mathbf { X } \ mathbf { X } ^ { T }] $ 著愛為著對角線矩陣，隨對角線上之值攏為著 $ 零 $，所以乎 $ \ mathbf { K } $ 著愛將傳換做對角線矩陣，即 $ \ mathbf { K } $ 的每一行攏為 $ \ mathbf { C } $ 之特徵向量。

K-L 轉換的目的是將原始數據做轉換，予得轉換以後資料的相關性上細。若輸入數據做一維：

$ $
y [u]=\ sum _ { n=零 } ^ { N 影一 } K [u , n] x [n]
$ $

$ $
K [u , n]=e _ { n } [n]
$ $

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

若輸入訊號 x 為二維：

$ $
y [u , v]=\ sum _ { m=零 } ^ { M 影一 } \ sum _ { n=零 } ^ { N 影一 } 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 _ { 一 } , x _ { 一 }] & E [x _ { 一 } , x _ { 二 }] & E [x _ { 一 } , x _ { 三 }] & \ dots & E [x _ { 一 } , x _ { j }] & \ dots & E [x _ { 一 } , x _ { N }] \ \ E [x _ { 二 } , x _ { 一 }] & E [x _ { 二 } , x _ { 二 }] & E [x _ { 二 } , x _ { 三 }] & \ dots & E [x _ { 二 } , x _ { j }] & \ dots & E [x _ { 二 } , x _ { N }] \ \ \ vdots & \ vdots & \ vdots & \ ddots & \ vdots & \ ddots & \ vdots \ \ E [x _ { i } , x _ { 一 }] & E [x _ { i } , x _ { 二 }] & E [x _ { i } , x _ { 三 }] & \ dots & E [x _ { i } , x _ { j }] & \ dots & a _ { in } \ \ \ vdots & \ vdots & \ vdots & \ ddots & \ vdots & \ ddots & \ vdots \ \ E [x _ { M } , x _ { 一 }] & E [x _ { M } , x _ { 二 }] & E [x _ { M } , x _ { 三 }] & \ 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 } $

以一三 x 二之輸入 $ X={ \ begin { bmatrix } x 一 & x 二 & x 三 \ \ x 四 & x 五 & x 六 \ end { bmatrix } } $ 為例現此時 $ C _ { x _ { i } x _ { j } }={ \ begin { bmatrix } 一 & \ rho _ { H } & \ rho _ { H } ^ { 二 } & \ rho _ { V } & \ rho _ { H } \ rho _ { V } & \ rho _ { H } ^ { 二 } \ cdot \ rho _ { V } \ \ \ rho _ { H } & 一 & \ rho _ { H } & \ rho _ { H } \ rho _ { V } & \ rho _ { V } & \ rho _ { H } \ rho _ { V } \ \ \ rho _ { H } ^ { 二 } \ rho _ { V } & \ rho _ { H } & 一 & \ rho _ { H } ^ { 二 } \ rho _ { V } & \ rho _ { H } \ rho _ { V } & \ rho _ { V } \ \ \ rho _ { V } & \ rho _ { H } \ rho _ { V } & \ rho _ { H } ^ { 二 } \ rho _ { V } & 一 & \ rho _ { H } & \ rho _ { H } ^ { 二 } \ \ \ rho _ { H } \ rho _ { V } & \ rho _ { V } & \ rho _ { H } \ rho _ { V } & \ rho _ { H } & 一 & \ rho _ { H } \ \ \ rho _ { H } ^ { 二 } \ rho _ { V } & \ rho _ { H } \ rho _ { V } & \ rho _ { V } & \ rho _ { H } ^ { 二 } & \ rho _ { H } & 一 \ end { bmatrix } } $

毋過對任意 sài-sù 的水平抑是垂直方向之協方差矩陣會當表示成

$ $
C _ { xx }={ \ begin { bmatrix } \ rho & \ rho ^ { 二 } & \ dots & \ rho ^ { N 影一 } \ \ \ rho ^ { 二 } & \ rho & \ dots & \ rho ^ { N 鋪二 } \ \ \ vdots & \ vdots & \ ddots & \ vdots \ \ \ rho ^ { N 影一 } & \ rho ^ { N 鋪二 } & \ dots & \ rho \ end { bmatrix } }
$ $

會當發現其值干焦佮 $ | i-j | $ 有關，阮用其閉合形式，其基底元素 $ v _ { ij } $ 為

$ $
v _ { ij }={ \ sqrt { \ frac { 二 } { N + \ lambda _ { j } } } } \ sin { ( { \ frac { ( 二 i-N 影一 ) \ omega } { 二 } } + { \ frac { j \ pi } { 二 } } ) }
$ $

此處 $ \ lambda _ { j } $ 為 $ C _ { xx } $ 之特徵值

$ $
\ lambda _ { j }={ \ frac { 一-\ rho ^ { 二 } } { 一孵二 \ rho \ , \ cos { \ omega _ { j } } + \ rho ^ { 二 } } }
$ $

其中 $ \ tan ( N \ omega _ { j } )=-{ \ frac { ( 一-\ rho ^ { 二 } ) \ sin { \ omega _ { j } } } { \ cos { \ omega _ { j } } 鋪二 \ rho + \ rho ^ { 二 } \ cos { \ omega _ { j } } } } $

對無仝的輸入影像，其實 $ \ rho $ 會有無仝款，若是予 $ \ rho \ rightarrow 一 $，此轉換毋免佮輸入相關，同時繼承矣 K-L 轉換去除相關性的媠性質。

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

代入上式，得 KLT | $ \ rho \ rightarrow 一 $，$ v _ { ij }=\ left \ { { \ begin { matrix } { \ sqrt { \ frac { 一 } { N } } } \ cos { \ frac { ( 二 i 影一 ) ( j 影一 ) \ pi } { 二 N } } , & { \ mbox { if } } j=一 \ \ { \ sqrt { \ frac { 二 } { N } } } \ cos { \ frac { ( 二 i 影一 ) ( j 影一 ) \ pi } { 二 N } } , & { \ mbox { if } } j \ neq 一 \ 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 ) 的特性，所以也會當應用佇人面辨識頂懸。

==參考文獻==

一 . Ding , J . J . ( 二千空一十七 ) . Advanced Digital Signal Processing [Powerpoint slides] http : / / djj . ee . ntu . edu . tw / ADSP 八 . pdf

二 . Gerbrands , J . J . , On the relationships between SVD , KLT , and PCA , Pattern Recogn . , 十四 ( 一千九百八十一 ) , pp . 三百七十五拍三百八十一

[[分類: 待校正]]