Skip to content

Latest commit

 

History

History
280 lines (227 loc) · 13.9 KB

dft.md

File metadata and controls

280 lines (227 loc) · 13.9 KB
title date categories tags keywords mathjax description
傅里叶变换
2019-06-10 23:46
数学
数学
图像处理
FFT, 傅里叶变换, 图像处理
true
图像处理中, 为了方便处理，便于抽取特征，数据压缩等目的，常常要将图形进行变换,这篇文章介绍一下傅里叶变换

图像处理中, 为了方便处理，便于抽取特征，数据压缩等目的，常常要将图像进行变换。 一般有如下变换方法

  1. 傅立叶变换Fourier Transform
  2. 离散余弦变换Discrete Cosine Transform
  3. 沃尔希-哈德玛变换Walsh-Hadamard Transform
  4. 斜变换Slant Transform
  5. 哈尔变换Haar Transform
  6. 离散K-L变换Discrete Karhunen-Leave Transform
  7. 奇异值分解SVD变换Singular-Value Decomposition
  8. 离散小波变换Discrete Wavelet Transform

这篇文章介绍一下傅里叶变换

定义

连续

积分形式 如果一个函数的绝对值的积分存在，即 并且函数是连续的或者只有有限个不连续点，则对于 x 的任何值， 函数的傅里叶变换存在

  • 一维傅里叶变换
  • 一维傅里叶逆变换 同理多重积分

离散

实际应用中，多用离散傅里叶变换 DFT.

  • 一维傅里叶变换
  • 一维傅里叶逆变换 需要注意的是， 逆变换乘以 是为了归一化，这个系数可以随意改变， 即可以正变换乘以 , 逆变换就不乘，或者两者都乘以等系数。
  • 二维傅里叶变换
  • 二维傅里叶逆变换

幅度 相位 对于图像的幅度谱显示，由于 |F(u,v)| 变换范围太大，一般显示

用 <=> 表示傅里叶变换对

f,g,h 对应的傅里叶变换 F,G,H

表示 的共轭

性质

分离性

进行多维变换时，可以依次对每一维进行变换。 下面在代码中就是这样实现的。

位移定理

周期性

共轭对称性

a)偶分量函数在变换中产生偶分量函数; b)奇分量函数在变换中产生奇分量函数; c)奇分量函数在变换中引入系数-j; d)偶分量函数在变换中不引入系数.

旋转性

if then

加法定理

2.

平均值

相似性定理

尺度变换

卷积定理

卷积定义 1d 2d

卷积定理

离散卷积 用 即两个周期为 N 的抽样函数， 他们的卷积的离散傅里叶变换等于他们的离散傅里叶变换的卷积

卷积的应用： 去除噪声， 特征增强 两个不同周期的信号卷积需要周期扩展的原因：如果直接进行傅里叶变换和乘积，会产生折叠误差(卷绕)。

相关定理

下面用 表示相关。 相关函数描述了两个信号之间的相似性，其相关性大小有相关系数衡量

  • 相关函数的定义 离散 连续
  • 定理

Rayleigh 定理

能量变换 对于有限区间非零函数 f(t), 其能量为

其变换函数与原函数有相同的能量

快速傅里叶变换

由上面离散傅里叶变换的性质易知，直接计算 1维 dft 的时间复杂度维 。

利用到单位根的对称性，快速傅里叶变换可以达到 的时间复杂度。

复数中的单位根

我们知道， 在复平面，复数 k可以表示成 ， 可以对应一个向量。即为幅角。 在单位圆中 ，单位圆被分成 份， 由单位圆的对称性 现在记 ， 即被分成 n 份，幅度角为正且最小的向量称为 n 次单位向量， 记为， 其余的 n-1 个向量分别为 ，它们可以由复数之间的乘法得来 。 单位根的性质

  1. 这个可以用 e 表示出来证明
  2. 可以写成三角函数证明

容易看出 。

对于 , 它事实上就是 。

快速傅里叶变换的计算

下面的推导假设 ，以及代码实现 FFT 部分也是 如此。

利用上面的对称性， 将傅里叶计算进行奇偶分组 表示将 输入的次序中偶数点进行 Fourier 变换， 同理，这样就形成递推公式。 现在还没有减少计算量，下面通过将分别计算的 奇项，偶项利用起来，只计算 前 项，后面的一半可以利用此结果马上算出来。每一次可以减少一半的计算量。

对于 现在很清楚了，在每次计算 a[0..n-1] 的傅里叶变换F[0..n-1]，分别计算出奇 odd[0..n/2-1]，偶even[0..n/2-1]（可以递归地进行）， 那么傅里叶变换为：

代码

下面是 python 实现 一维用 FFT 实现， 不过 只实现了 2 的幂。/ 对于非 2 的幂，用 FFT 实现有点困难，还需要插值，所以我 用 直接实现。

二维的 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)

参考