從序列到網格
數碼影像或矩形網格上的數值解是二維陣列,而不是單一序列。振盪可以沿任一座標發生,也可以同時沿兩個方向發生。二維離散傅立葉(Fourier)變換(DFT)用網格上的波來描述同一個有限陣列。精確算術下,反變換能恢復每個數值;但僅靠變換本身,我們無法知道網格點之間或觀測矩形之外發生了甚麼。
設 為正整數,複數數據 的索引滿足 、。第一個索引表示行,第二個表示列。以下固定採用這個慣例。
定義 2.6.1
( 陣列的二維 DFT)
的變換是陣列
兩個頻率索引分別按模 和模 理解。
零頻值 ,因此樣本平均數是 。有些軟件在正變換或兩個方向都加入歸一化;比較數值振幅前須先比較其定義。
反變換與正交性
定理 2.6.2
(反變換)
對上述任意陣列,
證明
(分開兩個等比和)
代入正變換,交換有限求和次序。 的係數為
由有限等比級數公式,每個括號在對應差值可被其長度整除時等於該長度,否則為零。由於索引均在各自範圍內,兩個整除條件同時成立恰好意味著 且 。因此只剩下該項。即使其中一個維度為一,論證仍然成立。
索引 的基底波是 ,其反變換係數為 。指定範圍內不同索引對的網格波互相正交,每個波的範數平方為 ;這 個波構成 維複數陣列空間的一組基底。
可分離計算
指數可分解成行座標與列座標的因子。先沿列方向變換每一行:
第二步變換 的每一列。交換有限和可見,反過來先變換各列也得到相同結果。寫成矩陣形式,這就是兩邊各乘一個一維 DFT 矩陣,詳見下文。這個張量積結構是計算方法,並非假設數據可分解成兩個一維陣列的乘積。
直接從所有 個輸入計算所有 個輸出,需要 次算術運算。分離後直接計算的成本為 。若兩個方向採用合適的一維 FFT,對非平凡維度,其合計成本通常為 ;確切成本和儲存需求視長度及實作而定。FFT 重新排列的是同一個有限變換,但浮點結果未必精確。
例題 2.6.3
(二乘二陣列)
取 。二點 DFT 把 映為 。逐行變換得 ,再逐列變換得
例如, 是帶符號的行對比,而 是列對比。 處的反變換為 ;完整反變換恢復原來四個數值。若交換軸的標籤,兩個非對角係數也會交換。
例題 2.6.4
(平移二乘二陣列)
把同一陣列的行循環平移 、:。逐行變換得 和 ,再逐列變換得
由於 ,平移應把 的第 行乘以 ;確實只有 變號。所有模都不變:循環平移在 中看不見,完全由相位承載。下面最後一題證明一般規則。
反例模式
幅值相同並不迫使兩者相差一個平移
聲稱:若每個頻率格都有 ,則 是 的循環平移。在 網格上,令 的第一行為 , 的第一行為 ,兩者第二行皆為零。於是
所以兩個頻譜每一行的幅值都是 。然而 的四個列方向平移是 、、、,而行方向平移會把非零的行移走; 不是其中任何一個。幅值相同只表示 ;平移恰好對應於對 為線性的相位 。
能量、對稱性與頻率格
定理 2.6.5
(離散 Parseval 等式)
在上述慣例下,。
證明
(展開模平方)
把反變換展開式代入左邊並展開模平方。兩個座標的正交性消去不同頻率對之間的交叉項。每個留下的基底波範數平方為 ,故係數模平方和乘上 ,得到結論。採用其他歸一化時,因子也會改變。
概念視角代數
把變換看成矩陣夾乘
令 為 矩陣,其元素為 , 同理。兩者都是對稱矩陣,而一維等比和恆等式說明 。定義於是寫成 ;此處轉置不取複共軛。反變換成為矩陣恆等式 ;又因 和 是酉矩陣,Frobenius 範數滿足 ,這正是 Parseval 等式。若把 的各列疊成一個向量,同一映射就是乘以 Kronecker 積 ,所以可分離計算是精確的,而非近似。
若 為實數,對正變換取複共軛可得頻譜的一種對稱性。
定理 2.6.6
(實數據的共軛對稱性)
若每個 都是實數,則對所有
證明
(對正變換取共軛)
由於 ,對定義取共軛就把每個指數 換成 。指數只按模 依賴 ,所以結果正是在 的變換值。
若一個頻率格在兩個座標都與自身配對,它的值必為實數。例如零索引與偶數長度的中點索引都是自配對的。其餘頻率格成複共軛對。
常見錯誤
(只把一個頻率變號)
兩個座標須同時變號;只改一個未必得到複共軛。對在 處為 、其餘為零的實 陣列,。 的配對是 ,而 。但 ,並不等於 。
常見錯誤
(實數輸入不代表每個係數都是實數)
只有自配對的頻率格才必定是實數。 陣列 的 。
例題 2.6.7
(二乘四網格上的自配對頻率格)
令 的第一行為 ,第二行為零。則對 有 。由於 ,兩個行索引都是自配對的; 時列索引 和 也是,所以 的四個頻率格必為實數:它們等於 和 。其餘頻率格按 配對,而確實 。數實參數:四個實頻率格加兩組共軛對,共 ,與 的八個實數元素吻合。
較大的索引如 可代表頻率 ,因為兩者在網格上取值相同。若行間距為 ,代表元 對應該座標的物理頻率 ,單位為每單位長度的週期數;列方向類似。偶數長度的中點頻率,其正負代表元在網格上重合,解讀時須選定慣例。有些圖把零頻移到中央,這只是頻譜的排列,並非另一種變換。影像顯示也可能轉置軸;須記錄每個索引對應的物理方向。
網格無法提供甚麼
對整數 ,把波的頻率 換成 ,網格樣本和 DFT 都不變。因此不同連續波可以產生相同數據;沒有額外假設,任何變換都無法區分它們。矩形截取會被視為週期陣列的一個週期。邊界不匹配可令能量散佈至多個頻率格;乘上窗函數會改變洩漏,也會改變振幅。補零增加的是零而非新的測量,並會改變陣列及頻率網格。用頻譜相乘計算卷積時,除非按預期線性操作選擇補零和邊界慣例,否則會出現週期性折返。
練習與解答
快速檢查
(求常數陣列 的變換。)
每個座標的和都是等比和。
解答 · 答案
兩個座標的和在非零剩餘類均為零,所以 ,其餘頻率格全為零。反變換在每點給出 。
快速檢查
(在 網格上令 。求其非零頻率格。)
陣列是一個行因子與一個列因子的乘積。
解答 · 答案
行方向的和 在 時為 ,在 時為零。列方向的和在 時為 ,其他時為零。因此 ,其餘全為零;其反變換係數為 。
快速檢查
(驗證二乘二例子的 Parseval 等式,並解釋此處為何不能直接把頻譜模平方相加。)
把兩個和與因子 比較。
解答 · 答案
樣本能量為 ,頻譜模平方和為 ;除以 後得 。所選慣例的正變換並非酉變換。
快速檢查
(對整數 ,設 。求其變換 與 的關係。)
代入平移後的求和索引。
解答 · 答案
分別以模數代換 、;這只重新排列求和索引,而指數可以分離,因此 。相位改變,模不變。故僅憑模不能定位陣列:任何非平凡的循環位移都有相同的頻譜模。