圖像的正交變換在數(shù)字圖像的處理與分析中起著很重要的作用，被廣泛應(yīng)用于圖像增強(qiáng)、去噪、壓縮編碼等眾多領(lǐng)域。本文手工實(shí)現(xiàn)了二維離散傅里葉變換和二維離散余弦變換算法，并在多個(gè)圖像樣本上進(jìn)行測試，以探究二者的變換效果。

1. 傅里葉變換

實(shí)驗(yàn)原理

對一幅圖像進(jìn)行離散傅里葉變換(DFT)，可以得到圖像信號的傅里葉頻譜。二維 DFT 的變換及逆變換公式如下：

DFT 盡管解決了頻域離散化的問題，但運(yùn)算量太大。從公式中可以看到，有兩個(gè)嵌套的求和符號，顯然直接計(jì)算的復(fù)雜度為 \(O(n^2)\) 。為了加快傅里葉變換的運(yùn)算速度，后人提出快速傅里葉變換(FFT)，即蝶形算法，將計(jì)算 DFT 的復(fù)雜度降低到了 \(O(n\log n)\)。

FFT 利用傅里葉變換的數(shù)學(xué)性質(zhì)，采用分治的思想，將一個(gè) \(N\) 點(diǎn)的 FFT，變成兩個(gè) \(N/2\) 點(diǎn)的 FFT。以一維 FFT 為例，可以表示如下：

其中，\(G(k)\) 是 \(x(k)\) 的偶數(shù)點(diǎn)的 \(N/2\) 點(diǎn)的 FFT，\(H(k)\) 是 \(x(k)\) 的奇數(shù)點(diǎn)的 \(N/2\) 點(diǎn)的 FFT。

這樣，通過將原問題不斷分解為兩個(gè)一半規(guī)模的子問題，然后計(jì)算相應(yīng)的蝶形運(yùn)算單元，最終得以完成整個(gè) FFT。

算法步驟

本次實(shí)驗(yàn)中，一維 FFT 采用遞歸實(shí)現(xiàn)，且僅支持長度為 2 的整數(shù)冪的情況。

算法步驟如下：

檢查圖像的尺寸，如果不是 2 的整數(shù)冪則直接退出。

對圖像的灰度值進(jìn)行歸一化。

對圖像的每一行執(zhí)行一維 FFT，并保存為中間結(jié)果。

對上一步結(jié)果中的每一列執(zhí)行一維 FFT，返回變換結(jié)果。

將零頻分量移到頻譜中心，并求絕對值進(jìn)行可視化。

對中心化后的結(jié)果進(jìn)行對數(shù)變換，以改善視覺效果。

主要代碼

一維 FFT

def fft(x):

n = len(x)

if n == 2:

return [x[0] + x[1], x[0] - x[1]]

G = fft(x[::2])

H = fft(x[1::2])

W = np.exp(-2j * np.pi * np.arange(n//2) / n)

WH = W * H

X = np.concatenate([G + WH, G - WH])

return X

二維 FFT

def fft2(img):

h, w = img.shape

if ((h-1) & h) or ((w-1) & w):

print('Image size not a power of 2')

return img

img = normalize(img)

res = np.zeros([h, w], 'complex128')

for i in range(h):

res[i, :] = fft(img[i, :])

for j in range(w):

res[:, j] = fft(res[:, j])

return res

零頻分量中心化

def fftshift(img):

# swap the first and third quadrants, and the second and fourth quadrants

h, w = img.shape

h_mid, w_mid = h//2, w//2

res = np.zeros([h, w], 'complex128')

res[:h_mid, :w_mid] = img[h_mid:, w_mid:]

res[:h_mid, w_mid:] = img[h_mid:, :w_mid]

res[h_mid:, :w_mid] = img[:h_mid, w_mid:]

res[h_mid:, w_mid:] = img[:h_mid, :w_mid]

return res

運(yùn)行結(jié)果

2. 余弦變換

實(shí)驗(yàn)原理

當(dāng)一個(gè)函數(shù)為偶函數(shù)時(shí)，其傅立葉變換的虛部為零，因而不需要計(jì)算，只計(jì)算余弦項(xiàng)變換，這就是余弦變換。離散余弦變換(DCT)的變換核為實(shí)數(shù)的余弦函數(shù)，因而計(jì)算速度比變換核為指數(shù)的 DFT 要快得多。

一維離散余弦變換與離散傅里葉變換具有相似性，對離散傅里葉變換進(jìn)行下式的修改：

式中

由上式可見，\(\sum\limits_{x=0}^{2M-1}f_e(x)e^{\frac{-j2ux\pi}{2M}}\) 是 \(2M\) 個(gè)點(diǎn)的傅里葉變換，因此在做離散余弦變換時(shí)，可將其拓展為 \(2M\) 個(gè)點(diǎn)，然后對其做離散傅里葉變換，取傅里葉變換的實(shí)部就是所要的離散余弦變換。

算法步驟

基于上述原理，二維 DCT 的實(shí)現(xiàn)重用了上文中的一維 FFT 函數(shù)，并根據(jù)公式做了一些修改。

算法步驟如下：

檢查圖像的尺寸，如果不是 2 的整數(shù)冪則直接退出。

對圖像的灰度值進(jìn)行歸一化。

對圖像的每一行進(jìn)行延拓，執(zhí)行一維 FFT 后取實(shí)部，乘以公式中的系數(shù)，并保存為中間結(jié)果。

對上一步結(jié)果中的每一列進(jìn)行延拓，執(zhí)行一維 FFT 后取實(shí)部，乘以公式中的系數(shù)，返回變換結(jié)果。

對結(jié)果求絕對值，并進(jìn)行對數(shù)變換，以改善視覺效果。

主要代碼

二維 DCT

def dct2(img):

h, w = img.shape

if ((h-1) & h) or ((w-1) & w):

print('Image size not a power of 2')

return img

img = normalize(img)

res = np.zeros([h, w], 'complex128')

for i in range(h):

res[i, :] = fft(np.concatenate([img[i, :], np.zeros(w)]))[:w]

res[i, :] = np.real(res[i, :]) * np.sqrt(2 / w)

res[i, 0] /= np.sqrt(2)

for j in range(w):

res[:, j] = fft(np.concatenate([res[:, j], np.zeros(h)]))[:h]

res[:, j] = np.real(res[:, j]) * np.sqrt(2 / h)

res[0, j] /= np.sqrt(2)

return res

運(yùn)行結(jié)果

文章來源: www.cnblogs.com，作者：TimDyh，版權(quán)歸原作者所有，如需轉(zhuǎn)載，請聯(lián)系作者。

原文鏈接：https://www.cnblogs.com/timdyh/p/13338975.html

總結(jié)

以上是生活随笔為你收集整理的python实现傅里叶变换求幅值和相位_Python 实现图像快速傅里叶变换和离散余弦变换...的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。