图像的逆FFT [英] Inverse-FFT of an image
问题描述
我使用以下代码进行图像的快速傅里叶逆变换(I-FFT)。
I am using the following code to do the Inverse Fast Fourier Transform (I-FFT) of an Image.
public static Complex[,] InverseFourierTransform2d(Complex[,] image)
{
int Width = image.GetLength(0);
int Height = image.GetLength(1);
FourierTransform.FastFourierTransform2d(image, Direction.Backward);
for (int y = 0; y < Height; y++)
{
for (int x = 0; x < Width; x++)
{
if (((x + y) & 0x1) != 0)
{
image[x, y] *= -1;
}
}
}
return image;
}
(完整源代码的DotNetFiddle链接) [ ^ ]
输出:
http://i.stack.imgur.com/AmSCT.png [ ^ ]
在此处输入图片说明
正如你所看到的,FFT工作正常,但I-FFT不是?
可能是什么问题?
我的尝试:
(The DotNetFiddle link of the complete source code)[^]
Output:
http://i.stack.imgur.com/AmSCT.png[^]
enter image description here
As you can see, FFT is working correctly, but, I-FFT isn't?
What could be the problem?
What I have tried:
using System;
using System.Numerics;
using System.Drawing;
using System.Drawing.Imaging;
using System.IO;
using System.Windows.Forms;
namespace Fourier_Transform__Test
{
public enum Direction
{
Forward = 1,
Backward = -1
}
;
public class Tools
{
public static int Pow2(int power)
{
return ((power >= 0) && (power <= 30)) ? (1 << power) : 0;
}
public static int Log2(int x)
{
if (x <= 65536)
{
if (x <= 256)
{
if (x <= 16)
{
if (x <= 4)
{
if (x <= 2)
{
if (x <= 1)
return 0;
return 1;
}
return 2;
}
if (x <= 8)
return 3;
return 4;
}
if (x <= 64)
{
if (x <= 32)
return 5;
return 6;
}
if (x <= 128)
return 7;
return 8;
}
if (x <= 4096)
{
if (x <= 1024)
{
if (x <= 512)
return 9;
return 10;
}
if (x <= 2048)
return 11;
return 12;
}
if (x <= 16384)
{
if (x <= 8192)
return 13;
return 14;
}
if (x <= 32768)
return 15;
return 16;
}
if (x <= 16777216)
{
if (x <= 1048576)
{
if (x <= 262144)
{
if (x <= 131072)
return 17;
return 18;
}
if (x <= 524288)
return 19;
return 20;
}
if (x <= 4194304)
{
if (x <= 2097152)
return 21;
return 22;
}
if (x <= 8388608)
return 23;
return 24;
}
if (x <= 268435456)
{
if (x <= 67108864)
{
if (x <= 33554432)
return 25;
return 26;
}
if (x <= 134217728)
return 27;
return 28;
}
if (x <= 1073741824)
{
if (x <= 536870912)
return 29;
return 30;
}
return 31;
}
public static bool IsPowerOf2(int x)
{
return (x > 0) ? ((x & (x - 1)) == 0) : false;
}
}
public static class FourierTransform
{
private static void FastFourierTransform1d(Complex[] data, Direction direction)
{
int n = data.Length;
int m = Tools.Log2(n);
// reorder data first
ReorderData(data);
// compute FFT
int tn = 1, tm;
for (int k = 1; k <= m; k++)
{
Complex[] rotation = FourierTransform.GetComplexRotation(k, direction);
tm = tn;
tn <<= 1;
for (int i = 0; i < tm; i++)
{
Complex t = rotation[i];
for (int even = i; even < n; even += tn)
{
int odd = even + tm;
Complex ce = data[even];
Complex co = data[odd];
double tr = co.Real * t.Real - co.Imaginary * t.Imaginary;
double ti = co.Real * t.Imaginary + co.Imaginary * t.Real;
data[even] += new Complex(tr, ti);
data[odd] = new Complex(ce.Real - tr, ce.Imaginary - ti);
}
}
}
if (direction == Direction.Forward)
{
for (int i = 0; i < data.Length; i++)
data[i] /= (double)n;
}
}
public static void FastFourierTransform2d(Complex[, ] data, Direction direction)
{
int k = data.GetLength(0);
int n = data.GetLength(1);
// check data size
if (!Tools.IsPowerOf2(k) || !Tools.IsPowerOf2(n))
throw new ArgumentException("The matrix rows and columns must be a power of 2.");
if (k < minLength || k > maxLength || n < minLength || n > maxLength)
throw new ArgumentException("Incorrect cInputFft length.");
// process rows
var row = new Complex[n];
for (int i = 0; i < k; i++)
{
// copy row
for (int j = 0; j < row.Length; j++)
row[j] = data[i, j];
// transform it
FourierTransform.FastFourierTransform1d(row, direction);
// copy back
for (int j = 0; j < row.Length; j++)
data[i, j] = row[j];
}
// process columns
var col = new Complex[k];
for (int j = 0; j < n; j++)
{
// copy column
for (int i = 0; i < k; i++)
col[i] = data[i, j];
// transform it
FourierTransform.FastFourierTransform1d(col, direction);
// copy back
for (int i = 0; i < k; i++)
data[i, j] = col[i];
}
}
#region Private Region
private const int minLength = 2;
private const int maxLength = 16384;
private const int minBits = 1;
private const int maxBits = 14;
private static int[][] reversedBits = new int[maxBits][];
private static Complex[, ][] complexRotation = new Complex[maxBits, 2][];
// Get array, indicating which data members should be swapped before FFT
private static int[] GetReversedBits(int numberOfBits)
{
if ((numberOfBits < minBits) || (numberOfBits > maxBits))
throw new ArgumentOutOfRangeException();
// check if the array is already calculated
if (reversedBits[numberOfBits - 1] == null)
{
int n = Tools.Pow2(numberOfBits);
int[] rBits = new int[n];
// calculate the array
for (int i = 0; i < n; i++)
{
int oldBits = i;
int newBits = 0;
for (int j = 0; j < numberOfBits; j++)
{
newBits = (newBits << 1) | (oldBits & 1);
oldBits = (oldBits >> 1);
}
rBits[i] = newBits;
}
reversedBits[numberOfBits - 1] = rBits;
}
return reversedBits[numberOfBits - 1];
}
// Get rotation of complex number
private static Complex[] GetComplexRotation(int numberOfBits, Direction direction)
{
int directionIndex = (direction == Direction.Forward) ? 0 : 1;
// check if the array is already calculated
if (complexRotation[numberOfBits - 1, directionIndex] == null)
{
int n = 1 << (numberOfBits - 1);
double uR = 1.0;
double uI = 0.0;
double angle = System.Math.PI / n * (int)direction;
double wR = System.Math.Cos(angle);
double wI = System.Math.Sin(angle);
double t;
Complex[] rotation = new Complex[n];
for (int i = 0; i < n; i++)
{
rotation[i] = new Complex(uR, uI);
t = uR * wI + uI * wR;
uR = uR * wR - uI * wI;
uI = t;
}
complexRotation[numberOfBits - 1, directionIndex] = rotation;
}
return complexRotation[numberOfBits - 1, directionIndex];
}
// Reorder data for FFT using
private static void ReorderData(Complex[] data)
{
int len = data.Length;
// check data length
if ((len < minLength) || (len > maxLength) || (!Tools.IsPowerOf2(len)))
throw new ArgumentException("Incorrect cInputFft length.");
int[] rBits = GetReversedBits(Tools.Log2(len));
for (int i = 0; i < len; i++)
{
int s = rBits[i];
if (s > i)
{
Complex t = data[i];
data[i] = data[s];
data[s] = t;
}
}
}
#endregion
}
public class FourierImageOperation
{
public static Complex[, ] FastFourierTransform2d(Complex[, ] image)
{
Complex[, ] comp = (Complex[, ])image.Clone();
int Width = comp.GetLength(0);
int Height = comp.GetLength(1);
for (int y = 0; y < Height; y++)
{
for (int x = 0; x < Width; x++)
{
if (((x + y) & 0x1) != 0)
{
comp[x, y] *= -1;
}
}
}
FourierTransform.FastFourierTransform2d(comp, Direction.Forward);
return comp;
}
public static Complex[, ] InverseFourierTransform2d(Complex[, ] image)
{
int Width = image.GetLength(0);
int Height = image.GetLength(1);
FourierTransform.FastFourierTransform2d(image, Direction.Backward);
for (int y = 0; y < Height; y++)
{
for (int x = 0; x < Width; x++)
{
if (((x + y) & 0x1) != 0)
{
image[x, y] *= -1;
}
}
}
return image;
}
}
public partial class MainForm : Form
{
string path = @"lena.png";
public MainForm()
{
InitializeComponent();
}
private void loadImageButton_Click(object sender, EventArgs e)
{
Bitmap bitmap = Bitmap.FromFile(path) as Bitmap;
originalImagePictureBox.Image = bitmap as Image;
}
private void grayscaleButton_Click(object sender, EventArgs e)
{
Bitmap originalImage = originalImagePictureBox.Image as Bitmap;
Bitmap grayscale = Grayscale.ToGrayscale(originalImage);
grayscaleImagePictureBox.Image = grayscale as Image;
}
private void fftButton_Click(object sender, EventArgs e)
{
Bitmap grayscale = grayscaleImagePictureBox.Image as Bitmap;
Complex[, ] cGrayscale = ImageDataConverter.ToComplex(grayscale);
Complex[, ] cFFt = FourierImageOperation.FastFourierTransform2d(cGrayscale);
fftPictureBox.Image = ImageDataConverter.ToBitmap(cFFt, true);
}
private void ifftButton_Click(object sender, EventArgs e)
{
Bitmap fftImage = fftPictureBox.Image as Bitmap;
Complex[, ] image = ImageDataConverter.ToComplex(fftImage);
Complex[, ] cGrayscale = FourierImageOperation.InverseFourierTransform2d(image);
ifftPictureBox.Image = ImageDataConverter.ToBitmap(image, false);
}
}
}
推荐答案
您的Log2
功能看起来很奇怪。
上次检查时,Log2(9)
不是4。
YourLog2
function look weird.
Last time I checked,Log2(9)
was not 4.
我不想分析整个FFT代码。但是当在函数FastFourierTransform1d
中看到代码部分时,代码的作者似乎还不理解前向,后向和反向术语:
I don't want to analyse the whole FFT code. But it seems that the author of the code has not understand the forward, backward, and inverse terms when seeing this code part in the functionFastFourierTransform1d
:
if (direction == Direction.Forward)
{
for (int i = 0; i < data.Length; i++)
data[i] /= (double)n;
}
将矢量除以 n
是执行前向后的逆FFT运算FFT。所以这个实现似乎在传递 Direction.Forward
时执行逆FFT。
要执行逆FFT,进行正向FFT并将向量除以 n
。
反向FFT是反向的非标度版本FFT。它可以在比例不关心时使用,因为它更快(不需要分割矢量)。
这个链接提供了很好的差异解释:< a href =https://planet.racket-lang.org/package-source/williams/science.plt/4/1/planet-docs/science/fft.html> 12& nbsp; Fast Fourier Transforms [ ^ ]
所以你有两个选择:
- 让FFT代码保持不变,传递
Direction.Forward
,你应该得到反向FTT。 - 从上面删除上面的代码FFT代码,传递
Direction.Forward
,并按n
执行除法以获得逆FFT。 - Let the FFT code unchanged, pass
Direction.Forward
and you should get the inverse FTT. - Remove the above code from the FFT code, pass
Direction.Forward
, and perform the division byn
to get the inverse FFT.
Dividing the vector by n
is the operation for an inverse FFT after having performed a forward FFT. So this implementatione seems to perform an inverse FFT when passing Direction.Forward
.
To perform an inverse FFT, do a forward FFT and divide the vector by n
.
A backward FFT is the unscaled version of an inverse FFT. It can be used when the scale does not care because it is faster (dividing the vector is not necessary).
This link provides a good explantion of the differences: 12 Fast Fourier Transforms[^]
So you have two options:
这篇关于图像的逆FFT的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!