圖論傅立葉轉換


圖論傅立葉轉換(Graph Fourier Transform,GFT),是將離散傅立葉轉換延伸至處理圖訊號時的推廣型態。其轉換函數由其預設的決定,沒有既定的方程式表示法。

在形式上,變換兩端(時域和頻域)的資料維度皆為有限長。

常見定義

一個已編號的N點一般圖(有限不重邊無向圖)G,考慮它的拉普拉斯矩陣(Laplacian matrix)L:

 

其中D為此圖的度數矩陣,W為邻接矩陣。

因L為實對稱矩陣,L會有特徵分解

 

且其中 為正交基底矩陣, 特徵值對角矩陣。

此時定義  即為在此圖上的圖論傅立葉轉換矩陣

現有一圖訊號依相同編號表示為向量形式

 , 其中 表示編號為k的頂點上的訊號值

則它的圖論傅立葉轉換為

 

其中 的第k項之頻率值為 

相反地,逆圖論傅立葉轉換即是將過程逆進行:

 

廣義定義

對於一個N點的圖 (可為有向,但通常有限、不重邊),圖論傅立葉轉換的其中一種定義過程為:

  • 基本算子:圖位移(Graph Shift):
    • 圖位移 線性映射,可表為一N階方陣 。
    • 圖位移是一個抽象定義,並沒有特別指對G使用哪種特定方法構造出來的為圖位移。
    • 比較被使用的圖位移有:連接矩陣A拉普拉斯矩陣L正規化拉普拉斯矩陣LN
  • 圖論傅立葉轉換與頻域分解:
    • 考慮圖位移 的廣義特徵分解(Jordon decomposition) 
    • 定義 為頻域基底矩陣, 為圖論傅立葉轉換矩陣,也就是說對於圖信號   為其圖論傅立葉轉換。

廣義定義之範例

  • N點離散傅立葉轉換(DFT)可由圖論傅立葉轉換的廣義定義,經由以下選擇得到:
    1.  選定為N點的有向
    2. 圖位移 選定 連接矩陣
  • N點的第二型離散餘弦轉換(DCT-II)可由圖論傅立葉轉換的廣義定義,經由以下選擇得到:
    1.  選定為N點的無向道路
    2. 圖位移 選定 拉普拉斯矩陣
  • NxM點的二維DCT-II可由圖論傅立葉轉換的廣義定義,經由以下選擇得到:
    1.  選定為NxM點的柵格。
    2. 圖位移 選定 拉普拉斯矩陣

參考