title: 傅里葉變換
date: 2019-06-10 23:46
categories: 數(shù)學
tags: [數(shù)學, 圖像處理]
keywords: FFT, 傅里葉變換, 圖像處理
mathjax: true
description:
圖像處理中, 為了方便處理速址，便于抽取特征，數(shù)據(jù)壓縮等目的碗暗，常常要將圖形進行變換,這篇文章介紹一下傅里葉變換
圖像處理中, 為了方便處理临扮，便于抽取特征积蜻，數(shù)據(jù)壓縮等目的试伙，常常要將圖像進行變換劈狐。
一般有如下變換方法
- 傅立葉變換Fourier Transform
- 離散余弦變換Discrete Cosine Transform
- 沃爾希-哈德瑪變換Walsh-Hadamard Transform
- 斜變換Slant Transform
- 哈爾變換Haar Transform
- 離散K-L變換Discrete Karhunen-Leave Transform
- 奇異值分解SVD變換Singular-Value Decomposition
- 離散小波變換Discrete Wavelet Transform
這篇文章介紹一下傅里葉變換
定義
連續(xù)
積分形式
如果一個函數(shù)的絕對值的積分存在，即
并且函數(shù)是連續(xù)的或者只有有限個不連續(xù)點县匠，則對于 x 的任何值， 函數(shù)的傅里葉變換存在
- 一維傅里葉變換
- 一維傅里葉逆變換
同理多重積分
離散
實際應用中撒轮，多用離散傅里葉變換 DFT.
- 一維傅里葉變換
- 一維傅里葉逆變換
需要注意的是乞旦， 逆變換乘以是為了歸一化，這個系數(shù)可以隨意改變题山， 即可以正變換乘以
等系數(shù)。
- 二維傅里葉變換
- 二維傅里葉逆變換
幅度
相位
對于圖像的幅度譜顯示顶瞳，由于 |F(u,v)| 變換范圍太大玖姑，一般顯示
用 <=> 表示傅里葉變換對
f,g,h 對應的傅里葉變換 F,G,H
表示
的共軛
性質
分離性
進行多維變換時，可以依次對每一維進行變換慨菱。 下面在代碼中就是這樣實現(xiàn)的焰络。
位移定理
周期性
共軛對稱性
a)偶分量函數(shù)在變換中產生偶分量函數(shù);
b)奇分量函數(shù)在變換中產生奇分量函數(shù);
c)奇分量函數(shù)在變換中引入系數(shù)-j;
d)偶分量函數(shù)在變換中不引入系數(shù).
旋轉性
if
then
加法定理
平均值
相似性定理
尺度變換
卷積定理
卷積定義
1d
2d
卷積定理
離散卷積
用
即兩個周期為 N 的抽樣函數(shù)符喝， 他們的卷積的離散傅里葉變換等于他們的離散傅里葉變換的卷積
卷積的應用：
去除噪聲闪彼， 特征增強
兩個不同周期的信號卷積需要周期擴展的原因：如果直接進行傅里葉變換和乘積，會產生折疊誤差(卷繞)协饲。
相關定理
下面用 表示相關畏腕。
相關函數(shù)描述了兩個信號之間的相似性，其相關性大小有相關系數(shù)衡量
- 相關函數(shù)的定義
離散
連續(xù)
- 定理
Rayleigh 定理
能量變換
對于有限區(qū)間非零函數(shù) f(t), 其能量為
其變換函數(shù)與原函數(shù)有相同的能量
快速傅里葉變換
由上面離散傅里葉變換的性質易知茉稠，直接計算 1維 dft 的時間復雜度維 郊尝。
利用到單位根的對稱性，快速傅里葉變換可以達到 的時間復雜度战惊。
復數(shù)中的單位根
我們知道流昏， 在復平面，復數(shù) k可以表示成
吞获， 可以對應一個向量况凉。
即為幅角。
在單位圓中 各拷，單位圓被分成 份刁绒， 由單位圓的對稱性
現(xiàn)在記 ， 即被分成 n 份烤黍，幅度角為正且最小的向量稱為 n 次單位向量知市， 記為
傻盟，
其余的 n-1 個向量分別為 ，它們可以由復數(shù)之間的乘法得來
嫂丙。
單位根的性質
- 這個可以用 e 表示出來證明
- 可以寫成三角函數(shù)證明
容易看出 娘赴。
對于 , 它事實上就是
。
快速傅里葉變換的計算
下面的推導假設 跟啤，以及代碼實現(xiàn) FFT 部分也是 如此诽表。
利用上面的對稱性，
將傅里葉計算進行奇偶分組
表示將 輸入的次序中偶數(shù)點進行 Fourier 變換隅肥，
同理竿奏，這樣就形成遞推公式。
現(xiàn)在還沒有減少計算量腥放，下面通過將分別計算的 奇項泛啸，偶項利用起來，只計算 前 項秃症，后面的一半可以利用此結果馬上算出來候址。每一次可以減少一半的計算量。
對于
現(xiàn)在很清楚了伍纫，在每次計算 a[0..n-1] 的傅里葉變換F[0..n-1]宗雇，分別計算出奇 odd[0..n/2-1]，偶even[0..n/2-1]（可以遞歸地進行）莹规，
那么傅里葉變換為：
代碼
下面是 python 實現(xiàn)
一維用 FFT 實現(xiàn)赔蒲， 不過 只實現(xiàn)了 2 的冪。/ 對于非 2 的冪良漱，用 FFT 實現(xiàn)有點困難舞虱，還需要插值，所以我 用 直接實現(xiàn)母市。
二維的 DFT利用 分離性矾兜，直接調用 一維 FFT。
GitHub
import numpy as np
def _fft(a, invert=False):
N = len(a)
if N == 1:
return [a[0]]
elif N & (N - 1) == 0: # O(nlogn), 2^k
even = _fft(a[::2], invert)
odd = _fft(a[1::2], invert)
i = 2j if invert else -2j
factor = np.exp(i * np.pi * np.arange(N // 2) / N)
prod = factor * odd
return np.concatenate([even + prod, even - prod])
else: # O(n^2)
w = np.arange(N)
i = 2j if invert else -2j
m = w.reshape((N, 1)) * w
W = np.exp(m * i * np.pi / N)
return np.concatenate(np.dot(W, a.reshape(
(N, 1)))) # important, cannot use *
def fft(a):
'''fourier[a]'''
n = len(a)
if n == 0:
raise Exception("[Error]: Invalid length: 0")
return _fft(a)
def ifft(a):
'''invert fourier[a]'''
n = len(a)
if n == 0:
raise Exception("[Error]: Invalid length: 0")
return _fft(a, True) / n
def fft2(arr):
return np.apply_along_axis(fft, 0,
np.apply_along_axis(fft, 1, np.asarray(arr)))
def ifft2(arr):
return np.apply_along_axis(ifft, 0,
np.apply_along_axis(ifft, 1, np.asarray(arr)))
def test(n=128):
print('\nsequence length:', n)
print('fft')
li = np.random.random(n)
print(np.allclose(fft(li), np.fft.fft(li)))
print('ifft')
li = np.random.random(n)
print(np.allclose(ifft(li), np.fft.ifft(li)))
print('fft2')
li = np.random.random(n * n).reshape((n, n))
print(np.allclose(fft2(li), np.fft.fft2(li)))
print('ifft2')
li = np.random.random(n * n).reshape((n, n))
print(np.allclose(ifft2(li), np.fft.ifft2(li)))
if __name__ == '__main__':
for i in range(1, 3):
test(i * 16)
