1D傅里叶变换:
1D傅里叶逆变换:
2D傅里叶变换:
2D傅里叶变换通过两次1D傅里叶变换实现:
由此我们只需要关注1D的傅里叶变换如何处理,又因为我们处理图片的时候都是离散的点信息,最终我们得到的傅里叶变换是:
逆变换:
上述的傅里叶变换公式很直观,图像进行傅里叶变换时,像素点是n,最终转换到频域的时候,结果纹理存储的是k点的集合。(比较重要的是,傅里叶变换和逆变换不同点只有两个:(1/N)和(-kn),这说明他们的算法实现可以共用)
快速傅里叶算法(FFT):
先看一下一个8个采样点的快速傅里叶变换,它是基2,基4,基8的快速傅里叶算法的基础:
1.看下面不起眼的stage单词没,它对整个过程划分了几个阶段,个人感觉这里的划分有问题,应该是3个阶段。每个阶段有几个过程:(n个输入:log2(n+1)个阶段:nlog2(n)次复数乘法和加法)
(1)排序过程:黄颜色的部分,执行排序功能,让需要计算的两个值排在一起进行计算。
k = BIT_REVERSE(n)
(2)加权过程:蓝颜色部分,相乘的两个位置为奇数位的需要乘一个W(n0),看上面好像只有第1个阶段是对的,其实第2个和第3个阶段如果排完序就是对的了。
(3)蝶形算法过程:
一次蝶形运算:两次复数加法 + 两次复数乘法 (复数加法:2次浮点加法 复数乘法:4次浮点乘法+2次浮点加法) 一次蝶形运算 = 8次浮点乘 + 8次浮点加
FFT算法实现:
1.FFT:
// data为输入和输出的数据,N为长度
bool CFFT::Forward(complex *const Data, const unsigned int N)
{
if (!Data || N < 1 || N & (N - 1))
return false;
// 排序
Rearrange(Data, N);
// FFT计算:const bool Inverse = false
Perform(Data, N);
return true;
}
2.IFFT:
// Scale 为是否缩放
bool CFFT::Inverse(complex *const Data, const unsigned int N,
const bool Scale /* = true */)
{
if (!Data || N < 1 || N & (N - 1))
return false;
// 排序
Rearrange(Data, N);
// FFT计算,ture表示是逆运算
Perform(Data, N, true);
// 对结果进行缩放
if (Scale)
CFFT::Scale(Data, N);
return true;
}
3.排序:
void CFFT::Rearrange(complex *const Data, const unsigned int N)
{
// Swap position
unsigned int Target = 0;
// Process all positions of input signal
for (unsigned int Position = 0; Position < N; ++Position)
{
// Only for not yet swapped entries
if (Target > Position)
{
// Swap entries
const complex Temp(Data[Target]);
Data[Target] = Data[Position];
Data[Position] = Temp;
}
// Bit mask
unsigned int Mask = N;
// While bit is set
while (Target & (Mask >>= 1))
// Drop bit
Target &= ~Mask;
// The current bit is 0 - set it
Target |= Mask;
}
}
4.FFT计算:
void CFFT::Perform(complex *const Data, const unsigned int N,
const bool Inverse /* = false */)
{
const double pi = Inverse ? 3.14159265358979323846 : -3.14159265358979323846;
// Iteration through dyads, quadruples, octads and so on...
for (unsigned int Step = 1; Step < N; Step <<= 1)
{
// Jump to the next entry of the same transform factor
const unsigned int Jump = Step << 1;
// Angle increment
const double delta = pi / double(Step);
// Auxiliary sin(delta / 2)
const double Sine = sin(delta * .5);
// Multiplier for trigonometric recurrence
const complex Multiplier(-2. * Sine * Sine, sin(delta));
// Start value for transform factor, fi = 0
complex Factor(1.);
// Iteration through groups of different transform factor
for (unsigned int Group = 0; Group < Step; ++Group)
{
// Iteration within group
for (unsigned int Pair = Group; Pair < N; Pair += Jump)
{
// Match position
const unsigned int Match = Pair + Step;
// Second term of two-point transform
const complex Product(Factor * Data[Match]);
// Transform for fi + pi
Data[Match] = Data[Pair] - Product;
// Transform for fi
Data[Pair] += Product;
}
// Successive transform factor via trigonometric recurrence
Factor = Multiplier * Factor + Factor;
}
}
}
5.缩放:
void CFFT::Scale(complex *const Data, const unsigned int N)
{
const double Factor = 1. / double(N);
// Scale all data entries
for (unsigned int Position = 0; Position < N; ++Position)
Data[Position] *= Factor;
}
2D傅里叶变换:
2D的就是做两次1D的FFT运算
FFT对图片的处理:
FFT对图片的处理主要需要注意的是参数怎么控制,对于灰度图来说,灰度值是实数位,0为虚数为。对于RGB则是对RGB分别进行FFT转换,其中R,G,B分别为实数,虚数位依旧是0。
参考:
http://www.librow.com/articles/article-10
分享到:
相关推荐
西安交通大学数字信号处理-快速傅里叶变换FFT实验报告
fft算例,采样频率和数据点数,对信号进行快速Fourier变换
DSP实验4 快速傅立叶变换(FFT)
1:蝶形运算实现FFT_1D,然后先对二维的y方向进行FFT_1D运算,后对x方向进行FFT_1D预算。 2:提供对数据预处理的函数,可以实现对非2的整数次幂的数组的处理。 3:数据预处理将调整数组长度,并生成与原始数据相...
FFT-C快速傅里叶变换超级详细的原代码
本文讲解了FFT算法的原理与实际应用,给欲往电子信息类专业进修和发展的同学一些课外参考。
verilog编写的1024点的fft快速傅立叶变换代码 verilog编写的1024点的fft快速傅立叶变换代码
fft快速傅立叶变换程序 是用C语言写的 有需要的可以参考一下
C语言实现基2蝶形算法的快速傅里叶变换程序,含测试程序
matlabFFT小波变换-基于Mallat算法和快速傅里叶变换的电能质量分析方法.pdf MATLAB 在小波变换,FFT方面的应用,希望对大家有用
傅立叶变换 傅立叶反变换 快速傅立叶变换 DFT IDFT FFT 公式及原理 非常清楚
FFT(快速傅立叶变换)图文并茂附FFT源码,快速傅里叶变换原理,详细,图文并茂FFT算法附源码
QT实现图像处理-傅立叶变换、傅立叶反变换。readImage() 从图像中读取数据 writeImage() 往图像中写入数据 fft() 快速傅立叶变换 ifft() 快速傅立叶反变换 adjustImageSize() 调整图像大小
基于快速傅里叶变换的蝶形公式,对于N元待转换信号,蝶形公式为logN层级的子运算,每层的子运算中,运算因子在同层中互不干扰,因此只要利用好CUDA的__syncthreads()函数,在此基础上便可进一步利用GPU的单个线程来...
Matlab中快速傅里叶变换FFT结果的物理意义-Matlab中快速傅里叶变换FFT结果的物理意义.doc Matlab中快速傅里叶变换FFT结果的物理意义。 小白级解说, 新手可以看看。:lol
快速傅立叶变换算法频域滤波,效果不错,可以试试。
快速傅立叶算法,采用时域抽取法FFT(Decimation-In-Time FFT, 简称 DIT - FFT),完全采用标准C++语言编写,算法上采用了蝶形运算原理,数据结构采用 STL 模板库存储动态数组,采用 complex 类处理复数运算。...
设计一个按照时间抽取的基2快速傅里叶变换(基2FFT-DIT)。输入倒位序,输出自然顺序
vb平台实现简单的FFT傅里叶变换算法,算法简单可行