#pragma?pack（1）
#include
#include
#include“BMPStruct.h“
#define?Double_PI?6.283185307//2*PI
#define?NUM_ZERO?1e-10//浮點數0
using?namespace?std;
class?complex
{
public:
	complex（）{real=0;imag=0;}
	complex（double?rdouble?i）:real（r）imag（i）{}
	complex（double?x）{real=x;imag=0.0;}
	friend?complex?operator?+（complex?xcomplex?y）;
	friend?complex?operator?-（complex?xcomplex?y）;
	friend?complex?operator?*（complex?xcomplex?y）;
	friend?complex?operator?/（complex?xcomplex?y）;
	friend?ostream&?operator?<<（ostream?&outcomplex?&x）;
	void?operator=（complex?x）{real=x.real;imag=x.imag;}
	inline?double?length（）{return?sqrt（real*real+imag*imag）;}//復數的模長
	//friend?istream&?operator?>>（istream?&incomplex?x）;
public:
	double?real;//復數的實部
	double?imag;//復數的虛部
};
complex?operator+（complex?xcomplex?y）
{
	return?complex（x.real+y.realx.imag+y.imag）;
}
complex?operator-（complex?xcomplex?y）
{
	return?complex（x.real-y.realx.imag-y.imag）;
}
complex?operator*（complex?xcomplex?y）
{
	return?complex（x.real*y.real-x.imag*y.imagx.real*y.imag+x.imag*y.real）;
}
complex?operator/（complex?xcomplex?y）
{
	return?complex（（x.real*y.real+x.imag*y.imag）/（y.real*y.real+y.imag*y.imag）
		（x.imag*y.real-x.real*y.imag）/（y.real*y.real+y.imag*y.imag））;
}
ostream&?operator<<（ostream?&outcomplex?&x）
{
	out<	if（x.imag>0）
		out<<“+“<	else?if（abs（x.imag）<=NUM_ZERO）
	?????return?out;
	else
		out<	return?out;
}
void?bitReverse（complex?*aint?r）
{//碼位倒置函數，將輸入的序號直接按照二進制碼為倒置
	int?len=1<	int?ijkt;
	complex?b;//作為交換源數據的中間變量
	for（i=0;i	{
		k=i;//存放當前序號
		t=0;//存放當前序號的二進制逆序數
		for（j=0;j		{
			t<<=1;
			t|=（k&1）;
			k>>=1;
		}
		if（i		{
			b=a[i];
			a[i]=a[t];
			a[t]=b;
		}
	}
}
void?FFT（complex?*resultcomplex?*xint?r）
{
	//參數說明：result存放傅里葉變換后的結果，x是源數據，r是源數據的長度以2為底的對數
	int?N=1<	int?wLen=N>>1;//加權系數的長度
	complex?*w=new?complex[wLen];//w是加權系數
	int?ik;
	double?angle;
	for（i=0;i	{
		angle=-i*Double_PI/N;
		w[i].real=cos（angle）;
		w[i].imag=sin（angle）;
	}
	memcpy_s（resultN*sizeof（complex）xN*sizeof（complex））;//將時域信號復制到頻域信號里
	bitReverse（resultr）;//先進行碼位倒置，保證輸出按照順序輸出
	complex?x1x2;//取上一次的計算結果
	int?level;//蝶形算法當前的級數
	int?groups;//當前級上的蝶形組數
	int?count;//當前組上的相鄰蝶形數目
	int?p;//指示當前計算的組的首行
	for（level=0;level	{
		groups=1<<（r-level-1）;
		for（i=0;i		{
			count=1<			p=（i<<1）*（1<			for（k=0;k			{
				x1=result[p+k];
				x2=result[p+k+count];//count=1<				result[p+k]=x1+x2*w[k*（1<<（r-level-1））];
				result[p+k+count]=x1-x2*w[k*（1<<（r-level-1））];
			}
		}
	}
	delete?[]w;
}
void?AnalyzeBmpWithFFT（const?char?*bmpfilenamechar*resultfile）//用離散傅里葉變換分析一幅位圖
{
	FILE?*fin;
	if（fopen_s（&finbmpfilename“r“）!=0）
	{
		cout<<“Cannot?open?t

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----

?????文件????????789??2013-10-08?14:44??FFT\BMPStruct.h

?????文件??????66718??2013-10-08?19:48??FFT\效果圖.bmp

?????文件???????6182??2013-10-08?19:48??FFT\源.cpp

?????文件?????143478??2013-10-08?19:14??FFT\源圖像.bmp

?????目錄??????????0??2013-10-08?20:00??FFT

-----------?---------??----------?-----??----

???????????????217167????????????????????5