2D 影像進行 Discrete Fourier Transform－Lung-Yu,Tsai 的部落格

傅立葉轉換主要是將時域空間的資訊轉換為頻域空間的資訊。

傅立葉轉換圖解可參照下圖(引用維基百科)。

undefined

而由於數位訊號都是屬於離散的數列，因此採用離散傅立葉轉換將其進行轉換。

由於數學式與程式實作上會有些許落差，因此先對公式進行簡單的轉換。

由於傅立葉為負數運算，因此須考量是否有該資料結構，若無複數資料結構可自行定義含有實部與虛部的資料格式。

此專案定義 Complex 物件專門負責處理複數形式的數值。

class Complex
{
	double _real;
	double _image;
	public Complex()
	{
		_real = 0.0;
		_image = 0.0;
	}
	public Complex(double real)
	{
		_real = real;
		_image = 0.0;
	}
	public Complex(double real, double image)
	{
		_real = real;
		_image = image;
	}
	public double Image
	{
		get { return _image; }
		set { _image = value; }
	}
	public double Real
	{
		get { return _real; }
		set { _real = value; }
	}
	public double Magnitude()
	{
		return ((float)Math.Sqrt(_real * _real + _image * _image));
	}
	public double Phase()
	{
		return ((float)Math.Atan(_image / _real));
	}
	public double spectralDensity()
	{
		return _real * _real + _image * _image;
	}
	public void Add(Complex complex)
	{
		_image += complex.Image;
		_real += complex.Real;
	}
}

離散傅立葉轉換(Discrete Fourier Transform, DTF)程式如下所示。

已知輸入數列長度為size(相當於數學式的M)。

i 為公式中的u，表示目前的轉換目標。

j為公式中的x，表示原始數列的位置。

而傅立葉轉換與反傅立葉轉換僅差異一個「負號」因此DFTdir即表示目前是傅立葉亦或是反複利葉。

public List<Complex> transform()
{
	int size = inputs.Count;
	int DFTdir = (_IsInverse) ? -1 : 1;
	double Theta, cosineA, sineA;
	for (int i = 0; i < size; i++)
	{
		outputs.Add(new Complex());
		for (int j = 0; j < size; j++)
		{
			Theta = (Math.PI * 2 * i * j * DFTdir) / size;
			cosineA = Math.Cos(Theta);
			sineA = Math.Sin(Theta);

			outputs[i].Real += inputs[j].Real * cosineA - inputs[j].Image * sineA;
			outputs[i].Image += inputs[j].Real * sineA + inputs[j].Image * cosineA;
		}
	}
	return outputs;
}

離散傅立葉轉換僅處理1維資訊，因此對於影像屬於2維資訊需進行兩次的離散傅立葉轉換。

針對row進行DFT，後針對column進行DFT方能得到目標影像。