跳转到内容

圖論傅立葉轉換

本页使用了标题或全文手工转换
维基百科,自由的百科全书


圖論傅立葉轉換(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. 圖位移選定拉普拉斯矩陣

參考

[编辑]