上一篇介紹了 Fourier Transform。

我們知道，它可以把圖片從空間域轉換到頻域，讓我們分析圖片中不同頻率的組成。

不過，既然 NumPy 一行程式就能完成傅立葉轉換。

為什麼還要多學一個 Fast Fourier Transform（FFT）？

它們不是同一個東西嗎？

FFT 和 Fourier Transform 有什麼關係？

FFT，其實就是一個 更快地計算傅立葉轉換的方法。

我們上一篇介紹的 Fourier Transform，真正要算的是 離散傅立葉轉換（DFT）。

而 FFT 的工作，就是利用一些數學技巧，讓 DFT 可以更快算完。

它們最後得到的結果其實是一樣的，只是花的時間差很多。

為什麼原本的方法會很慢？

假設今天有一張 1024 × 1024 的圖片。

代表總共有超過一百萬個 Pixel。

如果每一個頻率都要和所有 Pixel 做一次運算，計算量就會非常龐大。

這也是最直接的 DFT 最大的缺點：圖片越大，等待的時間就越久。

FFT 到底快在哪裡？

FFT 最厲害的地方，就是它發現了很多重複的計算。

有些結果其實不用重新算一次，只要利用前面已經算好的結果，就能推導出新的答案。

所以它把許多原本重複的運算省略掉，讓整體速度大幅提升。

如果用時間複雜度來表示，一般 DFT 的時間複雜度是：

O(n²)

FFT 可以降低成：

O(nlogn)

看到這兩個公式時，可能不會有什麼感覺。

但隨著資料量變大，兩者的差距會逐漸增加。

例如當有一百萬筆資料時，FFT 所需要的運算次數，可能只有原本方法的幾十分之一，甚至更少。

也因為如此，現在幾乎所有實際使用的傅立葉轉換，背後都是 FFT。

NumPy 其實已經幫我們用了 FFT

上一篇我們使用的是：

f = np.fft.fft2(img)

看到函式名稱相信大家已經猜到了，fft2() 裡面的 FFT，就是 Fast Fourier Transform。

也就是說我們上一篇其實已經在使用 FFT 了。

只是上一篇先把重點放在理解 Fourier Transform，所以沒有特別提到。

FFT 可以做哪些事情？

FFT 最重要的用途，就是快速取得圖片的頻率資訊。

有了這些資訊之後，很多影像處理工作都能在頻域完成。

例如：

• 去除雜訊
• 模糊圖片
• 強化細節
• 壓縮影像
• 分析週期性的紋理

可以發現 FFT 比較像是一個加速工具。

真正的重點，還是傅立葉轉換本身。

而因為 FFT 足夠快，才讓頻域分析能夠真正應用在各種影像處理問題中。

實作：使用 FFT

上一篇的程式，其實就是利用 FFT 完成傅立葉轉換。

完整程式如下：

import cv2
import numpy as np
import matplotlib.pyplot as plt

img = cv2.imread("dog.jpeg", cv2.IMREAD_GRAYSCALE)

# 使用 FFT 計算傅立葉轉換
f = np.fft.fft2(img)

# 將低頻移到中心
fshift = np.fft.fftshift(f)

# 計算頻譜
magnitude = np.log(np.abs(fshift) + 1)

plt.figure(figsize=(10, 4))

plt.subplot(1, 2, 1)
plt.imshow(img, cmap="gray")
plt.title("Original")
plt.axis("off")

plt.subplot(1, 2, 2)
plt.imshow(magnitude, cmap="gray")
plt.title("Magnitude Spectrum")
plt.axis("off")

plt.tight_layout()
plt.show()

執行後得到的結果，會和上一篇完全相同。

因為 FFT 改變的是計算方式。

並不是傅立葉轉換的結果。

今天總結

今天介紹了 Fast Fourier Transform（FFT）。

它不是新的傅立葉轉換，而是一種能夠快速計算 DFT 的方法。

也就是說：

FFT 幫助我們更有效率地完成 Fourier Transform。

不過，到目前為止，我們只是把圖片轉換到頻域。

既然到了頻域，我們終於可以開始修改不同的頻率資訊。

那麼，如果保留低頻、去掉高頻，圖片會變成什麼樣子？

下一篇，我們就來介紹 Low-pass Filter（低通濾波器），看看只保留低頻資訊後，圖片會發生哪些變化。