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

1. 傅里葉變換

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

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

DFT 盡管解決了頻域離散化的問(wèn)題，但運(yùn)算量太大。從公式中可以看到，有兩個(gè)嵌套的求和符號(hào)，顯然直接計(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。

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

算法步驟

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

算法步驟如下：

1. 檢查圖像的尺寸，如果不是 2 的整數(shù)冪則直接退出。
2. 對(duì)圖像的灰度值進(jìn)行歸一化。
3. 對(duì)圖像的每一行執(zhí)行一維 FFT，并保存為中間結(jié)果。
4. 對(duì)上一步結(jié)果中的每一列執(zhí)行一維 FFT，返回變換結(jié)果。
5. 將零頻分量移到頻譜中心，并求絕對(duì)值進(jìn)行可視化。
6. 對(duì)中心化后的結(jié)果進(jìn)行對(duì)數(shù)變換，以改善視覺(jué)效果。

主要代碼

一維 FFT

二維 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

零頻分量中心化

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

2. 余弦變換

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

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

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

式中

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

算法步驟

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

算法步驟如下：

1. 檢查圖像的尺寸，如果不是 2 的整數(shù)冪則直接退出。
2. 對(duì)圖像的灰度值進(jìn)行歸一化。
3. 對(duì)圖像的每一行進(jìn)行延拓，執(zhí)行一維 FFT 后取實(shí)部，乘以公式中的系數(shù)，并保存為中間結(jié)果。
4. 對(duì)上一步結(jié)果中的每一列進(jìn)行延拓，執(zhí)行一維 FFT 后取實(shí)部，乘以公式中的系數(shù)，返回變換結(jié)果。
5. 對(duì)結(jié)果求絕對(duì)值，并進(jìn)行對(duì)數(shù)變換，以改善視覺(jué)效果。

主要代碼

二維 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é)果

源碼請(qǐng)參考擴(kuò)展鏈接