Hi I am trying to implement the Fast Fourier Transform. I have some code which I got online and slightly modified. I have a class GrabPixels which extracts a pixel array from an image, the class FFT implements the transform. My problem is I don't think the methods in the FFT class are being applies because the output I get back is what I would get when I run the GrabPixels class. The pixels are unchanged.
Could anyone help?
Thank you!
package FFTMain;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
//import java.awt.BorderLayout;
import java.awt.image.BufferedImage;
import java.awt.image.ImageObserver;
import java.awt.image.PixelGrabber;
import java.io.File;
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.imageio.*;
//import javax.swing.ImageIcon;
//import javax.swing.JFrame;
//import javax.swing.JLabel;
/**
*
*/
public class GrabPixels {
//http://www.java-tips.org/java-se-tips/javax.imageio/how-to-read-an-image-from-a-file-inputstream-o-2.html
public BufferedImage img;
public int[] pixels;
//int w, h;
private int width;
private int height;
// public GrabPixels(BufferedImage img) {
public GrabPixels() {
// this.img = img;
try {
img = ImageIO.read(new File("c:\\strawberry.jpg"));
} catch (IOException ex) {
Logger.getLogger(GrabPixels.class.getName()).log(Level.SEVERE, null, ex);
}
}
public GrabPixels(BufferedImage img) {
this.img = img;
try {
img = ImageIO.read(new File("c:\\strawberry.jpg"));
} catch (IOException ex) {
Logger.getLogger(GrabPixels.class.getName()).log(Level.SEVERE, null, ex);
}
}
public int[] getPixels() {
if(img!=null) {
width = img.getWidth();
System.out.println("Width = " + width);
height = img.getHeight();
System.out.println("Height = " + height);
pixels = new int[width * height];
}
PixelGrabber pg = new PixelGrabber(img, 0, 0, width, height, pixels, 0, width);
try {
pg.grabPixels();
for (int i = 0; i < pixels.length; i++) {
int pix = pixels[i];
pixels[i] = pix;
System.out.println(pix);
i++;
//pixels[i] = (new Color(pix)).getRed();
}
} catch (InterruptedException e) {
System.err.println("interrupted waiting for pixels!");
return null;
}
System.out.println("hi");
if ((pg.getStatus() & ImageObserver.ABORT) != 0) {
System.err.println("image fetch aborted or errored");
return null;
}
return pixels;
}
public int getWidth() {
return width;
}
public int getHeight() {
return height;
}
public void setWidth(int width) {
this.width = width;
}
public void setHeight(int height) {
this.height = height;
}
public int[][] get2DPixels() {
int[][] twoDPixels = null;
TwoDArray twoD = new TwoDArray(pixels, img.getWidth(), img.getHeight());
return twoDPixels;
}
}
package FFTMain;
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
//import java.awt.BorderLayout;
import java.awt.image.BufferedImage;
import java.awt.image.ImageObserver;
import java.awt.image.PixelGrabber;
import java.io.File;
import java.io.IOException;
import java.util.logging.Level;
import java.util.logging.Logger;
import javax.imageio.*;
//import javax.swing.ImageIcon;
//import javax.swing.JFrame;
//import javax.swing.JLabel;
/**
*
*/
public class GrabPixels {
//http://www.java-tips.org/java-se-tips/javax.imageio/how-to-read-an-image-from-a-file-inputstream-o-2.html
public BufferedImage img;
public int[] pixels;
//int w, h;
private int width;
private int height;
// public GrabPixels(BufferedImage img) {
public GrabPixels() {
// this.img = img;
try {
img = ImageIO.read(new File("c:\\strawberry.jpg"));
} catch (IOException ex) {
Logger.getLogger(GrabPixels.class.getName()).log(Level.SEVERE, null, ex);
}
}
public GrabPixels(BufferedImage img) {
this.img = img;
try {
img = ImageIO.read(new File("c:\\strawberry.jpg"));
} catch (IOException ex) {
Logger.getLogger(GrabPixels.class.getName()).log(Level.SEVERE, null, ex);
}
}
public int[] getPixels() {
if(img!=null) {
width = img.getWidth();
System.out.println("Width = " + width);
height = img.getHeight();
System.out.println("Height = " + height);
pixels = new int[width * height];
}
PixelGrabber pg = new PixelGrabber(img, 0, 0, width, height, pixels, 0, width);
try {
pg.grabPixels();
for (int i = 0; i < pixels.length; i++) {
int pix = pixels[i];
pixels[i] = pix;
System.out.println(pix);
i++;
//pixels[i] = (new Color(pix)).getRed();
}
} catch (InterruptedException e) {
System.err.println("interrupted waiting for pixels!");
return null;
}
System.out.println("hi");
if ((pg.getStatus() & ImageObserver.ABORT) != 0) {
System.err.println("image fetch aborted or errored");
return null;
}
return pixels;
}
public int getWidth() {
return width;
}
public int getHeight() {
return height;
}
public void setWidth(int width) {
this.width = width;
}
public void setHeight(int height) {
this.height = height;
}
public int[][] get2DPixels() {
int[][] twoDPixels = null;
TwoDArray twoD = new TwoDArray(pixels, img.getWidth(), img.getHeight());
return twoDPixels;
}
// public void main() {
//
// BufferedImage image = null;
// try {
// // Read from a file
// System.out.println("does it work");
// image = ImageIO.read(new File("c:\\strawberry.jpg"));
// //File sourceimage = new File("strawberry.jpg");
// //image = ImageIO.read(sourceimage);
// System.out.println("it works");
// GrabPixels bi = new GrabPixels(image);
// int[][] two;
// int[] array;
// array = bi.getPixels();
// two = bi.get2DPixels();
// //System.out.println(bi.getPixels(image, 2, 9, 8, 4));
// System.out.println(two);
// // Use a label to display the image
// JFrame frame = new JFrame();
// JLabel label = new JLabel(new ImageIcon(image));
// frame.getContentPane().add(label, BorderLayout.CENTER);
// frame.pack();
// frame.setVisible(true);
//
//
// } catch (IOException e) {
// }
// }
// public static void main(String[] args) {
// BufferedImage image = null;
// try {
// // Read from a file
// System.out.println("does it work");
// image = ImageIO.read(new File("c:\\strawberry.jpg"));
// //File sourceimage = new File("strawberry.jpg");
// //image = ImageIO.read(sourceimage);
// System.out.println("it works");
// GrabPixels bi = new GrabPixels();
// System.out.println(bi.getPixels(image, 2, 9, 8, 4));
// System.out.println(twoDPixels);
// // Use a label to display the image
// JFrame frame = new JFrame();
// JLabel label = new JLabel(new ImageIcon(image));
// frame.getContentPane().add(label, BorderLayout.CENTER);
// frame.pack();
// frame.setVisible(true);
//
//
// } catch (IOException e) {
// }
// }
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package FFTMain;
/**
*
*/
/*************************************************************************
* Compilation: javac Complex.java
* Execution: java Complex
*
* Data type for complex numbers.
*
* The data type is "immutable" so once you create and initialize
* a Complex object, you cannot change it. The "final" keyword
* when declaring re and im enforces this rule, making it a
* compile-time error to change the .re or .im fields after
* they've been initialized.
*
* % java Complex
* a = 5.0 + 6.0i
* b = -3.0 + 4.0i
* Re(a) = 5.0
* Im(a) = 6.0
* b + a = 2.0 + 10.0i
* a - b = 8.0 + 2.0i
* a * b = -39.0 + 2.0i
* b * a = -39.0 + 2.0i
* a / b = 0.36 - 1.52i
* (a / b) * b = 5.0 + 6.0i
* conj(a) = 5.0 - 6.0i
* |a| = 7.810249675906654
* tan(a) = -6.685231390246571E-6 + 1.0000103108981198i
*
*************************************************************************/
public class Complex {
private final double re; // the real part
private final double im; // the imaginary part
// create a new object with the given real and imaginary parts
public Complex(double real, double imag) {
re = real;
im = imag;
}
// return a string representation of the invoking Complex object
@Override
public String toString() {
if (im == 0) return re + "";
if (re == 0) return im + "i";
if (im < 0) return re + " - " + (-im) + "i";
return re + " + " + im + "i";
}
// return abs/modulus/magnitude and angle/phase/argument
public double abs() { return Math.hypot(re, im); } // Math.sqrt(re*re + im*im)
public double phase() { return Math.atan2(im, re); } // between -pi and pi
// return a new Complex object whose value is (this + b)
public Complex plus(Complex b) {
Complex a = this; // invoking object
double real = a.re + b.re;
double imag = a.im + b.im;
return new Complex(real, imag);
}
// return a new Complex object whose value is (this - b)
public Complex minus(Complex b) {
Complex a = this;
double real = a.re - b.re;
double imag = a.im - b.im;
return new Complex(real, imag);
}
// return a new Complex object whose value is (this * b)
public Complex times(Complex b) {
Complex a = this;
double real = a.re * b.re - a.im * b.im;
double imag = a.re * b.im + a.im * b.re;
return new Complex(real, imag);
}
// scalar multiplication
// return a new object whose value is (this * alpha)
public Complex times(double alpha) {
return new Complex(alpha * re, alpha * im);
}
// return a new Complex object whose value is the conjugate of this
public Complex conjugate() { return new Complex(re, -im); }
// return a new Complex object whose value is the reciprocal of this
public Complex reciprocal() {
double scale = re*re + im*im;
return new Complex(re / scale, -im / scale);
}
// return the real or imaginary part
public double re() { return re; }
public double im() { return im; }
// return a / b
public Complex divides(Complex b) {
Complex a = this;
return a.times(b.reciprocal());
}
// return a new Complex object whose value is the complex exponential of this
public Complex exp() {
return new Complex(Math.exp(re) * Math.cos(im), Math.exp(re) * Math.sin(im));
}
// return a new Complex object whose value is the complex sine of this
public Complex sin() {
return new Complex(Math.sin(re) * Math.cosh(im), Math.cos(re) * Math.sinh(im));
}
// return a new Complex object whose value is the complex cosine of this
public Complex cos() {
return new Complex(Math.cos(re) * Math.cosh(im), -Math.sin(re) * Math.sinh(im));
}
// return a new Complex object whose value is the complex tangent of this
public Complex tan() {
return sin().divides(cos());
}
// a static version of plus
public static Complex plus(Complex a, Complex b) {
double real = a.re + b.re;
double imag = a.im + b.im;
Complex sum = new Complex(real, imag);
return sum;
}
// sample client for testing
public static void main(String[] args) {
Complex a = new Complex(5.0, 6.0);
Complex b = new Complex(-3.0, 4.0);
System.out.println("a = " + a);
System.out.println("b = " + b);
System.out.println("Re(a) = " + a.re());
System.out.println("Im(a) = " + a.im());
System.out.println("b + a = " + b.plus(a));
System.out.println("a - b = " + a.minus(b));
System.out.println("a * b = " + a.times(b));
System.out.println("b * a = " + b.times(a));
System.out.println("a / b = " + a.divides(b));
System.out.println("(a / b) * b = " + a.divides(b).times(b));
System.out.println("conj(a) = " + a.conjugate());
System.out.println("|a| = " + a.abs());
System.out.println("tan(a) = " + a.tan());
}
}
/*
* To change this template, choose Tools | Templates
* and open the template in the editor.
*/
package FFTMain;
/**
*
*/
import java.lang.Math.*;
/**
* TwoDArray is a data structure to represent a two-dimensional array
* of complex numbers. ie The result of applying the 2D FFT to an image.
*
*/
public class TwoDArray{
/**
* The actual width of the image represented by the TwoDArray.
*/
public int width;
/**
* The actual height of the image represented by the TwoDArray.
*/
public int height;
/**
* Smallest value of 2^n such that the 2^n > width and 2^n > height.
* The dimensions of the square 2D array storing the image.
*/
public int size;
/**
* The 2D array of complex numbers padded out with (0,0)
* to 2^n width and height.
*/
public ComplexNumber [][] values;
/**
* Default no-arg constructor.
*/
public TwoDArray(){
}
/**
* Constructor that takes a TwoDArray and duplicates it exactly.
*
* @param a TwoDArray to be duplicated.
*/
public TwoDArray(TwoDArray a){
width = a.width;
height = a.height;
//System.out.println("NEW 2D 1 w: "+width+" height: "+height);
size = a.size;
values = new ComplexNumber[size][size];
for(int j=0;j<size;++j){
for(int i=0;i<size;++i){
ComplexNumber c = new ComplexNumber(a.values[i][j]);
values[i][j] = c;
}
}
}
/**
* Constructor that takes a width and a height, generates the appropriate
* size values and then sets up an array of (0,0) complex numbers.
*
* @param w Width of the new TwoDArray.
* @param h Height of the new TwoDArray.
*/
public TwoDArray(int w, int h){
width = w;
height = h;
//System.out.println("NEW 2D 2 w: "+width+" height: "+height);
int n=0;
while(Math.pow(2,n)<Math.max(w,h)){
++n;
}
size = (int) Math.pow(2,n);
values = new ComplexNumber [size][size];
for(int j=0;j<size;++j){
for(int i=0;i<size;++i){
values[i][j] = new ComplexNumber(0,0);
}
}
}
/**
* Constructor that takes a single dimension, generates an appropriate
* size and sets up a size x size array of (0,0) complex numbers.
*
* @param s Width or height of new TwoDArray.
*/
public TwoDArray(int s){
width = s;
height = s;
//System.out.println("NEW 2D 3 w: "+width+" height: "+height);
int n=0;
while(Math.pow(2,n)<s){
++n;
}
size = (int) Math.pow(2,n);
values = new ComplexNumber [size][size];
for(int j=0;j<size;++j){
for(int i=0;i<size;++i){
values[i][j] = new ComplexNumber(0,0);
}
}
}
/**
* Constructor taking int array of pixel values and width and height
* of the image represented by the array of pixels, sets values to
* (x,0) for each pixel x.
*
* @param p int array of pixel values.
* @param w Width of image.
* @param h Height of image.
*/
public TwoDArray(int [] p, int w, int h){
width = w;
height = h;
//System.out.println("NEW 2D 4 w: "+width+" height: "+height);
int n=0;
while(Math.pow(2,n)<Math.max(w,h)){
++n;
}
//System.out.println("n is "+n+" w is "+w+" h is "+h);
size = (int) Math.pow(2,n);
values = new ComplexNumber [size][size];
for(int j=0;j<size;++j){
for(int i=0;i<size;++i){
values[i][j] = new ComplexNumber(0,0);
}
}
/*System.err.println("Just about to add image to array");*/
/* DONALD NAIRN 2003 */
for(int j=0;j<h;++j){
for(int i=0;i<w;++i){
values[i][j] = new ComplexNumber(p[i+(j*w)], 0.0);
}
}
}
// public int [][] get2DArray(){
// values = (int [][])values;
// return (int [][])values;
// }
/**
* Constructor taking 2D int array of pixels values, width and height,
* sets values to (x,0) for each pixel x.
*
* @param v 2D array of pixel values.
* @param w Width of image.
* @param h Height of image.
*/
public TwoDArray(int [][] v, int w, int h){
width = w;
height = h;
//System.out.println("NEW 2D 5 w: "+width+" height: "+height);
int n=0;
while(Math.pow(2,n)<Math.max(w,h)){
++n;
}
size = (int) Math.pow(2,n);
values = new ComplexNumber [size][size];
for(int j=0;j<size;++j){
for(int i=0;i<size;++i){
values[i][j] = new ComplexNumber(0,0);
}
}
for(int j=0;j<h;++j){
for(int i=0;i<w;++i){
values[i][j] = new ComplexNumber(v[i][j], 0.0);
}
}
}
/**
* Constructor taking 2D array of complex numbers, width and height.
*
* @param v 2D array of complex numbers.
* @param w Width of image.
* @param h Height of image.
*/
public TwoDArray(ComplexNumber [][] v, int w, int h){
width = w;
height = h;
//System.out.println("NEW 2D 6 w: "+width+" height: "+height);
int n=0;
while(Math.pow(2,n)<Math.max(w,h)){
++n;
}
size = (int) Math.pow(2,n);
values = new ComplexNumber [size][size];
for(int j=0;j<size;++j){
for(int i=0;i<size;++i){
values[i][j] = new ComplexNumber(0,0);
}
}
for(int j=0;j<h;++j){
for(int i=0;i<w;++i){
values[i][j] = new ComplexNumber(v[i][j]);
}
}
}
/**
* Takes a column number and returns an array containing the
* complex numbers in that column.
*
* @param n int column number (0 is first column).
* @return ComplexNumber array containing column.
*/
public ComplexNumber [] getColumn(int n){
ComplexNumber [] c = new ComplexNumber [size];
for(int i=0;i<size;++i){
c[i] = new ComplexNumber(values[n][i]);
}
return c;
}
/**
* Takes a column number and an array of complex numbers and replaces
* that column with the new data.
*
* @param n int column number (0 is first column).
* @param Array of complex numbers representing the new data.
*/
public void putColumn(int n, ComplexNumber [] c){
for(int i=0;i<size;++i){
values[n][i] = new ComplexNumber(c[i]);
}
}
/**
* Takes a row number and an array of complex numbers and replaces
* that row with the new data.
*
* @param n int row number (0 is first row).
* @param c Array of complex numbers representing the new data.
*/
public void putRow(int n, ComplexNumber [] c){
for(int i=0;i<size;++i){
values[i][n] = new ComplexNumber(c[i]);
}
}
/**
* Takes a row number and returns an array containing the
* complex numbers in that row.
*
* @param n int row number (0 is first row).
* @return ComplexNumber array containing row.
*/
public ComplexNumber [] getRow(int n){
ComplexNumber [] r = new ComplexNumber [size];
for(int i=0;i<size;++i){
r[i] = new ComplexNumber(values[i][n]);
}
return r;
}
/**
* Takes a 2D array of doubles representing an image and translates
* and wraps the image to put (0,0) the DC value in the centre of the image.
* at (width/2,height/2) [because image runs -128..+127]
*
* @param input 2D array of doubles.
* @return 2D array of doubles representing the new image.
*/
public double [][] DCToCentre(double [][] input){
double [][] output = new double [width][height];
int x = width/2;
int y = height/2;
int i2,j2;
for(int j=0;j<height;++j){
for(int i=0;i<width;++i){
i2=i+x;
j2=j+y;
if(i2>=width)i2=i2%width;
if(j2>=height)j2=j2%height;
output[i][j] = input[i2][j2];
}
}
return output;
}
/**
* Takes a 2D array of doubles representing an image and translates
* and wraps the image to put the centre pixel at (0,0).
*
* @param input 2D array of doubles.
* @return 2D array of doubles representing the new image.
*/
public double [][] DCToTopLeft(double [][] input){
double [][] output = new double [width][height];
int i2,j2;
int x = width/2;
int y = height/2;
for(int j=0;j<height;++j){
for(int i=0;i<width;++i){
i2=i+x;
j2=j+x;
if(i2>=width)i2=i2%width;
if(j2>=height)j2=j2%height;
output[i][j] = input[i2][j2];
}
}
return output;
}
public ComplexNumber [][] DCToTopLeft(ComplexNumber [][] input){
ComplexNumber [][] output = new ComplexNumber [width][height];
int i2,j2;
int x = width/2;
int y = height/2;
for(int j=0;j<height;++j){
for(int i=0;i<width;++i){
i2=i+x;
j2=j+x;
if(i2>=width)i2=i2%width;
if(j2>=height)j2=j2%height;
output[i][j] = input[i2][j2];
}
}
return output;
}
/**
* Takes an array of doubles representing an image and translates
* and wraps the image to put (0,0) the DC value in the centre of the image.
* at (width/2,height/2) [because image runs -128..+127]
*
* @param input array of doubles.
* @return array of doubles representing the new image.
*/
public double [] DCToCentre(double [] input){
double [][] input2 = new double [width][height];
double [][] output2 = new double [width][height];
double [] output = new double [width*height];
for(int j=0;j<height;++j){
for(int i=0;i<width;++i){
input2[i][j] = input[j*width +i];
}
}
int x = width/2;
int y = height/2;
int i2,j2;
for(int j=0;j<height;++j){
for(int i=0;i<width;++i){
i2=i+x;
j2=j+y;
//if (input2[i][j] == 0){System.out.println("ZEROa at ("+i+","+j+") moved to ("+i2+","+j2+")");}
if(i2>=width)i2=i2%width;
if(j2>=height)j2=j2%height;
output2[i][j] = input2[i2][j2];
}
}
for(int j=0;j<height;++j){
for(int i=0;i<width;++i){
output[j*width +i] = output2[i][j];
}
}
return output;
}
/**
* Method to extract the real parts from a TwoDArray.
*
* @return An array of doubles representing the real parts of
* each element of the TwoDArray.
*/
public double [] getReal(){
double [] output = new double [width*height];
for(int j=0;j<height;++j){
for(int i=0;i<width;++i){
output[(j*width)+i] = values[i][j].real;
//if (values[i][j].real == 0){System.out.println("found ZERO at ("+i+","+j+")");}
}
}
return output;
}
/**
* Method to extract the imaginary parts from a TwoDArray.
*
* @return An array of doubles representing the imaginary parts of
* each element of the TwoDArray.
*/
public double [] getImaginary(){
double [] output = new double [width*height];
for(int j=0;j<height;++j){
for(int i=0;i<width;++i){
output[(j*width)+i] = values[i][j].imaginary;
}
}
return output;
}
/**
* Method to extract the magnitude of each element from a TwoDArray.
*
* @return An array of doubles representing the magnitude of
* each element of the TwoDArray.
*/
public double [] getMagnitude(){
double [] output = new double [width*height];
for(int j=0;j<height;++j){
for(int i=0;i<width;++i){
output[(j*width)+i] = values[i][j].magnitude();
}
}
return output;
}
/**
* Method to extract the phase angle of each element from a TwoDArray.
*
* @return An array of doubles representing the phase angle of
* each element of the TwoDArray.
*/
public double [] getPhase(){
double [] output = new double [width*height];
for(int j=0;j<height;++j){
for(int i=0;i<width;++i){
output[(j*width)+i] = values[i][j].phaseAngle();
}
}
return output;
}
}