|
import java.lang.Math.*;
|
import java.awt.*;
|
|
/**
|
* The InverseFFT class contains a method to apply the 2D inverse FFT to a
|
* TwoDArray.
|
*
|
* @author Simon Horne
|
*/
|
public class InverseFFT
|
{
|
|
static public int progress;
|
|
/**
|
* Default no argument constructor.
|
*/
|
public InverseFFT()
|
{
|
}
|
|
static ComplexNumber cTwo = new ComplexNumber(2, 0);
|
|
/**
|
* Recursively applies the 1D inverse FFT algorithm.
|
*
|
* @param x ComplexNumber array containing the input to the 1D inverse FFT.
|
* @return ComplexNumber array containing the result of the 1D inverse FFT.
|
*/
|
static public ComplexNumber[] recursiveInverseFFT(ComplexNumber[] x)
|
{
|
ComplexNumber z1, z2, z3, z4, tmp;
|
int n = x.length;
|
int m = n / 2;
|
ComplexNumber[] result = new ComplexNumber[n];
|
ComplexNumber[] even = new ComplexNumber[m];
|
ComplexNumber[] odd = new ComplexNumber[m];
|
ComplexNumber[] sum = new ComplexNumber[m];
|
ComplexNumber[] diff = new ComplexNumber[m];
|
if (n == 1)
|
{
|
result[0] = x[0];
|
} else
|
{
|
z1 = new ComplexNumber(0.0, 2 * (Math.PI) / n);
|
tmp = ComplexNumber.cExp(z1);
|
z1 = new ComplexNumber(1.0, 0.0);
|
for (int i = 0; i < m; ++i)
|
{
|
z3 = ComplexNumber.cSum(x[i], x[i + m]);
|
sum[i] = ComplexNumber.cDiv(z3, cTwo);
|
|
z3 = ComplexNumber.cDif(x[i], x[i + m]);
|
z4 = ComplexNumber.cMult(z3, z1);
|
diff[i] = ComplexNumber.cDiv(z4, cTwo);
|
|
z2 = ComplexNumber.cMult(z1, tmp);
|
z1 = new ComplexNumber(z2);
|
}
|
even = recursiveInverseFFT(sum);
|
odd = recursiveInverseFFT(diff);
|
|
for (int i = 0; i < m; ++i)
|
{
|
result[i * 2] = new ComplexNumber(even[i]);
|
result[i * 2 + 1] = new ComplexNumber(odd[i]);
|
}
|
}
|
return result;
|
}
|
|
/**
|
* Takes a TwoDArray, applies the 2D inverse FFT to the input by applying
|
* the 1D inverse FFT to each column and then each row in turn.
|
*
|
* @param input TwoDArray containing the input image data.
|
* @return TwoDArray containing the new image data.
|
*/
|
static public TwoDArray transform(TwoDArray input)
|
{
|
progress = 0;
|
TwoDArray intermediate = new TwoDArray(input.width, input.height);
|
TwoDArray output = new TwoDArray(input.width, input.height);
|
|
for (int i = 0; i < input.size; ++i)
|
{
|
progress++;
|
intermediate.putColumn(i, recursiveInverseFFT(input.getColumn(i)));
|
}
|
|
for (int i = 0; i < intermediate.size; ++i)
|
{
|
progress++;
|
output.putRow(i, recursiveInverseFFT(intermediate.getRow(i)));
|
}
|
return output;
|
}
|
|
static public int[] getPixels(TwoDArray output)
|
{
|
double[] outputArrayDoubles =
|
new double[output.width * output.height];
|
outputArrayDoubles = output.getReal();
|
//outputArrayDoubles = fft.output.getMagnitude();
|
int[] outputArray; // = new int [outputArrayDoubles.length];
|
//outputArray = ImageMods.toPixels(outputArrayDoubles);
|
outputArray =
|
toPixels(allPositive(outputArrayDoubles));
|
|
return outputArray;
|
}
|
|
/**
|
* Method to slide and scale an array of doubles so that the minimum
|
* values is 0 (all positive).
|
*
|
* @param values An array of doubles.
|
* @return An array of positive doubles.
|
*/
|
static private double[] allPositive(double[] values)
|
{
|
double[] output = new double[values.length];
|
double m = minValue(values);
|
if (false) // m<0)
|
{
|
for (int i = 0; i < values.length; ++i)
|
{
|
output[i] = values[i] - m;
|
}
|
return output;
|
} else
|
{
|
return values;
|
}
|
}
|
|
static int[] toInts(double[] values)
|
{
|
int[] ints = new int[values.length];
|
|
double scale = 1; // 1024 * 16; // ???
|
|
for (int i = 0; i < values.length; ++i)
|
{
|
ints[i] = (int) (values[i]*scale);
|
}
|
|
return ints;
|
}
|
|
/**
|
* A method to convert an array of grey values to an array of pixel values.
|
*
|
* @param values An array of grey values (all positive).
|
* @return An array of pixel values.
|
*/
|
static int[] toPixels(double[] values)
|
{
|
int grey;
|
// double [] greys = new double [values.length];
|
int[] pixels = new int[values.length];
|
// for(int i=0;i<greys.length;++i){
|
// greys[i] = values[i];
|
// }
|
// double max = maxValue(greys);
|
// double max = maxValue(values);
|
double scale;
|
// if (max == 0)
|
scale = 1024 * 16;
|
// else scale = 255.0/max;
|
|
//System.out.println(max);
|
// for(int i=0;i<greys.length;++i){
|
for (int i = 0; i < values.length; ++i)
|
{
|
// greys[i] = greys[i] * 255/max;
|
// grey = (int) Math.round(greys[i]);
|
grey = (int) /*Math.round*/ (values[i] * scale);
|
if (grey < 0)
|
{
|
grey = 0;
|
}
|
pixels[i] = grey; // new Color(grey,grey,grey).getRGB(); //recombine greys
|
}
|
return pixels;
|
}
|
|
/**
|
* Method to find the maximum value from an array of doubles.
|
*
|
* @param values an array of doubles.
|
* @return The maximum value.
|
*/
|
static private double maxValue(double[] values)
|
{
|
double max = values[0];
|
for (int i = 1; i < values.length; ++i)
|
{
|
if (values[i] > max)
|
{
|
max = values[i];
|
}
|
}
|
return max;
|
}
|
|
/**
|
* Method to find the minimum value from an array of doubles.
|
*
|
* @param values an array of doubles.
|
* @return The minimum value.
|
*/
|
static private double minValue(double[] values)
|
{
|
double min = values[0];
|
for (int i = 1; i < values.length; ++i)
|
{
|
if (values[i] < min)
|
{
|
min = values[i];
|
}
|
}
|
return min;
|
}
|
|
static public int getProgress()
|
{
|
return progress;
|
}
|
}
|
