dft.cpp

用C++实现的数字图像处理各个算法源代码 我精心整理的 很难的啊 希望可以给大家带来帮助

#include "stdafx.h"
#include "stdio.h"
#include "math.h"
#include "dft.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

#define PI 3.14159265

//////////////////////////////////////////////////

CComplex::CComplex()
{
	Re = 0.0;
	Im = 0.0;
}

CComplex::~CComplex()
{
}

CComplex::CComplex(double x,double y)
{
	Re = x;
	Im = y;
}

double CComplex::abs()
{
	return sqrt(Re * Re + Im * Im);
}

double CComplex::GetRe()
{
	return Re;
}

double CComplex::GetIm()
{
	return Im;
}

void CComplex::operator=(CComplex &cm)
{
	Re = cm.GetRe();
	Im = cm.GetIm();
}

void CComplex::operator+=(CComplex &cm)
{	
	Re += cm.GetRe();
	Im += cm.GetIm();
}

void CComplex::operator-=(CComplex &cm)
{
	Re -= cm.GetRe();
	Im -= cm.GetIm();
}

void CComplex::operator*=(CComplex &cm)
{
	double x = Re * cm.GetRe() - Im * cm.GetIm();
	double y = Re * cm.GetIm() + Im * cm.GetRe();
	Re=x;
	Im=y;
}

CComplex CComplex::operator*(CComplex &cm)
{
	CComplex temp;
	temp.Re = Re * cm.GetRe() - Im * cm.GetIm();
	temp.Im = Re * cm.GetIm() + Im * cm.GetRe();
	return temp;
}

void CComplex::operator*=(float var)
{
	Re *= var;
	Im *= var;
}

CComplex CComplex::operator+(CComplex &cm)
{
	double x = Re + cm.GetRe();
	double y = Im + cm.GetIm();
	return CComplex(x, y);
}

void CComplex::operator/=(double x)
{
	Re /= x;
	Im /= x;
}

CComplex CComplex::operator/(double x)
{
	CComplex temp;
	temp.Re = Re / x;
	temp.Im = Im / x;
	return temp;
}

CComplex CComplex::operator-(CComplex &cm)
{
	double x = Re - cm.GetRe();
	double y = Im - cm.GetIm();
	return CComplex(x, y);
}

////////////////////////////////////////////////////////////////////////
//离散傅立叶变换的实现
////////////////////////////////////////////////////////////////////////


////////////////////////////////////////////////////////////////////////
//CFourior()    
//----------------------------------------------------------------------
//基本功能：构造一个CFourior类的对象。
//----------------------------------------------------------------------
//参数说明：无
//----------------------------------------------------------------------
//返    回：无
//----------------------------------------------------------------------
//编	者：耿	楠
//最后编改：2001年12月11日
////////////////////////////////////////////////////////////////////////
CFourior::CFourior()
{
	bFlag = FALSE;
}

////////////////////////////////////////////////////////////////////////
//CFourior()    
//----------------------------------------------------------------------
//基本功能：构造一个CFourior类的对象。
//----------------------------------------------------------------------
//参数说明：int N	-离散傅立叶变换的点数
//----------------------------------------------------------------------
//返    回：无
//----------------------------------------------------------------------
//编	者：耿	楠
//最后编改：2001年12月11日
////////////////////////////////////////////////////////////////////////
CFourior::CFourior(int N)
{
	//标志置假
	bFlag = FALSE;
	
	//傅立叶变换的点数
	nByteNum = N;
}

////////////////////////////////////////////////////////////////////////
//void SetInverseDFT()    
//----------------------------------------------------------------------
//基本功能：离散傅立叶变换系数复数的共轭变换。
//----------------------------------------------------------------------
//参数说明：无
//----------------------------------------------------------------------
//返    回：无
//----------------------------------------------------------------------
//编	者：耿	楠
//最后编改：2001年12月11日
////////////////////////////////////////////////////////////////////////
void CFourior::SetInverseDFT()
{
	//标志为真才进行操作
	if(bFlag == TRUE)
	{
		for(int i = 0; i < nByteNum; i++)
		{
			//取出原复数的实部
			double x = (Wn+i)->GetRe();

			//取出原复数的虚部并进行符号求反
			double y = -(Wn+i)->GetIm();

			//重新写入复数数组
			*(Wn + i) = CComplex(x, y);
		}
	}
}

////////////////////////////////////////////////////////////////////////
//~CFourior()    
//----------------------------------------------------------------------
//基本功能：析构一个CFourior类的对象。
//----------------------------------------------------------------------
//参数说明：无
//----------------------------------------------------------------------
//返    回：无
//----------------------------------------------------------------------
//编	者：耿	楠
//最后编改：2001年12月11日
////////////////////////////////////////////////////////////////////////
CFourior::~CFourior()
{
	if(bFlag == TRUE) delete bWn;
}

////////////////////////////////////////////////////////////////////////
//void DFT()    
//----------------------------------------------------------------------
//基本功能：对CFourior类对象进行离散傅立叶变换。
//----------------------------------------------------------------------
//参数说明：CComplex *Input	-离散傅立叶变换的原数据
//----------------------------------------------------------------------
//返    回：无
//----------------------------------------------------------------------
//编	者：耿	楠
//最后编改：2001年12月11日
////////////////////////////////////////////////////////////////////////
void CFourior::DFT(CComplex *Input)
{
	//循环变量
	int i,j;

	//创建临时傅立叶数组（大小为nByteNum * sizeof(CComplex)）
	BYTE *btemp = new BYTE[nByteNum * sizeof(CComplex)];
	CComplex *temp = (CComplex *)btemp;

	//出错返回空值
	if(!temp)
	{
		AfxMessageBox("进行离散傅立叶变换数组分配出错！");
		return;
	}

	//定义一个临时复数变量
	CComplex var0((double)0,(double)0);

	//进行离散傅立叶变换（行循环）
	for(i = 0; i < nByteNum; i++)
	{
		//复数置零
		*(temp + i) = var0;

		//进行离散傅立叶变换（列循环）
		for(j = 0; j < nByteNum; j++)
		{
			//取得原数据
			CComplex temp1 = *(Input + j);
			
			//取得转换系数并与原数据相乘
			//用(j * i) % nByteNum计算转换系数（利用周期性）
			temp1 *= *(Wn + (j * i) % nByteNum);

			//累加求和进行离散傅立叶变换
			*(temp + i) += temp1;
		}
	}

	//用离散傅立叶变换结果替换原数据
	for(i = 0; i < nByteNum; i++)
	{
		*(Input + i) =* (temp + i);
	}
	delete btemp;
}

////////////////////////////////////////////////////////////////////////
//void FFT()    
//----------------------------------------------------------------------
//基本功能：对CFourior类对象进行快速离散傅立叶变换。
//----------------------------------------------------------------------
//参数说明：CComplex *Input	-离散傅立叶变换原数据
//----------------------------------------------------------------------
//返    回：无
//----------------------------------------------------------------------
//编	者：耿	楠
//最后编改：2001年12月11日
////////////////////////////////////////////////////////////////////////
void CFourior::FFT(CComplex *Input)
{
	//循环变量
	int i,j,k;

	//中间变量
	int M;
	int bfsize, p;
	
	//变换的点数
	int N = nByteNum;

	//不是2的整数幂次则无法进行快速傅立叶变换
	int temp = N;
	i = 0;
	while(1)
	{
		temp >>= 1; 
		i++;
		if(temp&1 == 1) break;
	}

	//迭代次数M=log2(N)，即为蝶形算法的级数
	M = i;

	nBitsNum = i;
	if(nByteNum != 1 << nBitsNum)
	{
		AfxMessageBox("FFT要求数据长度为2的n幂次方可!");
		return;
	}

	//定义FFT运算中用到的复数数组
	CComplex *X1, *X2, *X;
	
	//分配运算所需存储器
	X1 = (CComplex *) new BYTE[N * sizeof(CComplex)];
	X2 = (CComplex *) new BYTE[N * sizeof(CComplex)];
	
	//将时域点写入X1
	memcpy(X1, Input, N * sizeof(CComplex));
	
	// 采用蝶形算法进行快速付立叶变换
	for(k = 0; k < M; k++)
	{
		for(j = 0; j < 1 << k; j++)
		{
			bfsize = 1 << (M - k);
			for(i = 0; i < bfsize / 2; i++)
			{
				p = j * bfsize;
				X2[i + p] = X1[i + p] + X1[i + p + bfsize / 2];
				X2[i + p + bfsize / 2] = (X1[i + p] - X1[i + p + bfsize / 2]) * Wn[i * (1<<k)];
			}
		}
		X  = X1;
		X1 = X2;
		X2 = X;
	}
	
	// 重新排序
	for(j = 0; j < nByteNum; j++)
	{
		p = 0;
		for(i = 0; i < M; i++)
		{
			if (j & (1 << i))
			{
				p += 1 << (M - i - 1);
			}
		}
		Input[j]=X1[p];
	}
	
	// 释放内存
	delete X1;
	delete X2;

	return;
}


////////////////////////////////////////////////////////////////////////
//BOOL SetDftWn()    
//----------------------------------------------------------------------
//基本功能：设置离散傅立叶变换系数
//----------------------------------------------------------------------
//参数说明：无
//----------------------------------------------------------------------
//返    回：BOOL	-成功返回TRUE，失败返回FALSE
//----------------------------------------------------------------------
//编	者：耿	楠
//最后编改：2001年12月12日
////////////////////////////////////////////////////////////////////////
BOOL CFourior::SetDftWn()
{
	//标志置假
	bFlag = FALSE;
	
	//创建傅立叶数组（大小为nByteNum * sizeof(CComplex)）
	bWn = new BYTE[nByteNum * sizeof(CComplex)];
	Wn = (CComplex *)bWn;
	
	//创建失败返回空值
	if(!Wn)return FALSE;

	//创建变换加权系数
	//注意利用傅立叶变换的周期性，只需计算前nByteNum个变换系数便可。
	for(int i = 0; i < nByteNum; i++)
	{
		//W=e^(-j×2×π×i／nByteNum)
		double angle = -2.0 * PI * i / nByteNum;

		//利用欧拉公式将angle系数变为复数形式，并将其存入Wn数组中
		*(Wn + i) = CComplex(cos(angle), sin(angle));
	}

	//标志置真
	bFlag = TRUE;

	return TRUE;
}

////////////////////////////////////////////////////////////////////////
//BOOL SetFftWn()    
//----------------------------------------------------------------------
//基本功能：设置快速离散傅立叶变换系数
//----------------------------------------------------------------------
//参数说明：无
//----------------------------------------------------------------------
//返    回：BOOL	-成功返回TRUE，失败返回FALSE
//----------------------------------------------------------------------
//编	者：耿	楠
//最后编改：2001年12月12日
////////////////////////////////////////////////////////////////////////
BOOL CFourior::SetFftWn()
{
	//标志置假
	bFlag = FALSE;
	
	//创建傅立叶数组（大小为nByteNum * sizeof(CComplex)）
	bWn = new BYTE[nByteNum / 2 * sizeof(CComplex)];
	Wn = (CComplex *)bWn;
	
	//创建失败返回空值
	if(!Wn)return FALSE;

	//创建变换加权系数
	//注意利用傅立叶变换的周期性，只需计算前nByteNum个变换系数便可。
	for(int i = 0; i < nByteNum / 2; i++)
	{
		//W=e^(-j×2×π×i／nByteNum)
		double angle = -2.0 * PI * i / nByteNum;

		//利用欧拉公式将angle系数变为复数形式，并将其存入Wn数组中
		*(Wn + i) = CComplex(cos(angle), sin(angle));
	}

	//标志置真
	bFlag = TRUE;

	return TRUE;
}

////////////////////////////////////////////////////////////////////////
//BOOL SetCount()    
//----------------------------------------------------------------------
//基本功能：设置离散傅立叶变换系数
//----------------------------------------------------------------------
//参数说明：int N	-离散傅立叶变换时域数据点数
//----------------------------------------------------------------------
//返    回：无
//----------------------------------------------------------------------
//编	者：耿	楠
//最后编改：2001年12月12日
////////////////////////////////////////////////////////////////////////
void CFourior::SetCount(int N)
{
	nByteNum = N;
}

////////////////////////////////////////////////////////////////////////
//void SetInverseFFT()    
//----------------------------------------------------------------------
//基本功能：快速离散傅立叶变换系数复数的共轭变换。
//----------------------------------------------------------------------
//参数说明：无
//----------------------------------------------------------------------
//返    回：无
//----------------------------------------------------------------------
//编	者：耿	楠
//最后编改：2001年12月11日
////////////////////////////////////////////////////////////////////////
void CFourior::SetInverseFFT()
{
	//标志为真才进行操作
	if(bFlag == TRUE)
	{
		for(int i = 0; i < nByteNum / 2; i++)
		{
			//取出原复数的实部
			double x = (Wn+i)->GetRe();

			//取出原复数的虚部并进行符号求反
			double y = -(Wn+i)->GetIm();

			//重新写入复数数组
			*(Wn + i) = CComplex(x, y);
		}
	}
}