// Catalano Imaging Learning Library
// The Catalano Framework
//
// Copyright © Diego Catalano, 2012-2016
// diego.catalano at live.com
//
// Copyright © Nayuki Minase, 2014
// nayuki at eigenstate.org
// http://nayuki.eigenstate.org/page/free-small-fft-in-multiple-languages
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
//
// Contains functions from the Free FFT and convolution:
// Copyright © Nayuki Minase, 2014
// Original work: http://nayuki.eigenstate.org/page/free-small-fft-in-multiple-languages
//
// Original license is listed below:
//
// Permission is hereby granted, free of charge, to any person obtaining a copy of
// this software and associated documentation files (the "Software"), to deal in
// the Software without restriction, including without limitation the rights to
// use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of
// the Software, and to permit persons to whom the Software is furnished to do so,
// subject to the following conditions:
//
// - The above copyright notice and this permission notice shall be included in
// all copies or substantial portions of the Software.
// - The Software is provided "as is", without warranty of any kind, express or
// implied, including but not limited to the warranties of merchantability,
// fitness for a particular purpose and noninfringement. In no event shall the
// authors or copyright holders be liable for any claim, damages or other
// liability, whether in an action of contract, tort or otherwise, arising from,
// out of or in connection with the Software or the use or other dealings in the
// Software.
package Catalano.Math.Transforms;
import Catalano.Math.ComplexNumber;
/**
* Fourier transformation.
*
The class implements one dimensional and two dimensional Discrete and Fast Fourier Transformation.
* @author Diego Catalano
*/
public class FourierTransform {
/**
* Transformation direction.
*/
public enum Direction {
/**
* Forward direction of Fourier transformation.
*/
Forward,
/**
* Backward direction of Fourier transformation.
*/
Backward
};
/**
* 1-D Discrete Fourier Transform.
* @param data Data to transform.
* @param direction Transformation direction.
*/
public static void DFT(ComplexNumber[] data, Direction direction){
int n = data.length;
ComplexNumber[] c = new ComplexNumber[n];
// for each destination element
for ( int i = 0; i < n; i++ ){
c[i] = new ComplexNumber(0, 0);
double sumRe = 0;
double sumIm = 0;
double phim = 2 * Math.PI * i / n;
// sum source elements
for ( int j = 0; j < n; j++ ){
double gRe = data[j].real;
double gIm = data[j].imaginary;
double cosw = Math.cos(phim * j);
double sinw = Math.sin(phim * j);
if(direction == Direction.Backward)
sinw = -sinw;
sumRe += ( gRe * cosw + data[j].imaginary * sinw );
sumIm += ( gIm * cosw - data[j].real * sinw );
}
c[i] = new ComplexNumber(sumRe, sumIm);
}
if(direction == Direction.Backward){
for (int i = 0; i < c.length; i++) {
data[i].real = c[i].real / n;
data[i].imaginary = c[i].imaginary / n;
}
}
else{
for (int i = 0; i < c.length; i++) {
data[i].real = c[i].real;
data[i].imaginary = c[i].imaginary;
}
}
}
/**
* 2-D Discrete Fourier Transform.
* @param data Data to transform.
* @param direction Transformation direction.
*/
public static void DFT2(ComplexNumber[][] data, Direction direction){
int n = data.length;
int m = data[0].length;
ComplexNumber[] row = new ComplexNumber[Math.max(m, n)];
for ( int i = 0; i < n; i++ ){
// copy row
for ( int j = 0; j < n; j++ )
row[j] = data[i][j];
// transform it
FourierTransform.DFT( row, direction );
// copy back
for ( int j = 0; j < n; j++ )
data[i][j] = row[j];
}
// process columns
ComplexNumber[] col = new ComplexNumber[n];
for ( int j = 0; j < n; j++ ){
// copy column
for ( int i = 0; i < n; i++ )
col[i] = data[i][j];
// transform it
FourierTransform.DFT( col, direction );
// copy back
for ( int i = 0; i < n; i++ )
data[i][j] = col[i];
}
}
/**
* 1-D Fast Fourier Transform.
* @param data Data to transform.
* @param direction Transformation direction.
*/
public static void FFT(ComplexNumber[] data, Direction direction){
double[] real = ComplexNumber.getReal(data);
double[] img = ComplexNumber.getImaginary(data);
if(direction == Direction.Forward)
FFT(real,img);
else
FFT(img, real);
if(direction == Direction.Forward){
for (int i = 0; i < real.length; i++) {
data[i] = new ComplexNumber(real[i], img[i]);
}
}
else{
int n = real.length;
for (int i = 0; i < n; i++) {
data[i] = new ComplexNumber(real[i] / n, img[i] / n);
}
}
}
/**
* 2-D Fast Fourier Transform.
* @param data Data to transform.
* @param direction Transformation direction.
*/
public static void FFT2(ComplexNumber[][] data, Direction direction){
int n = data.length;
int m = data[0].length;
//ComplexNumber[] row = new ComplexNumber[m];//Math.max(m, n)];
for ( int i = 0; i < n; i++ ){
// copy row
//for ( int j = 0; j < m; j++ )
//row[j] = data[i][j];
ComplexNumber[] row = data[i];
// transform it
FourierTransform.FFT( row, direction );
// copy back
for ( int j = 0; j < m; j++ )
data[i][j] = row[j];
}
// process columns
ComplexNumber[] col = new ComplexNumber[n];
for ( int j = 0; j < m; j++ ){
// copy column
for ( int i = 0; i < n; i++ )
col[i] = data[i][j];
// transform it
FourierTransform.FFT( col, direction );
// copy back
for ( int i = 0; i < n; i++ )
data[i][j] = col[i];
}
}
/*
* Computes the discrete Fourier transform (DFT) of the given complex vector, storing the result back into the vector.
* The vector can have any length. This is a wrapper function.
*/
private static void FFT(double[] real, double[] imag) {
int n = real.length;
if (n == 0) {
return;
} else if ((n & (n - 1)) == 0) // Is power of 2
transformRadix2(real, imag);
else // More complicated algorithm for arbitrary sizes
transformBluestein(real, imag);
}
/*
* Computes the inverse discrete Fourier transform (IDFT) of the given complex vector, storing the result back into the vector.
* The vector can have any length. This is a wrapper function. This transform does not perform scaling, so the inverse is not a true inverse.
*/
private static void inverseTransform(double[] real, double[] imag) {
FFT(imag, real);
}
/*
* Computes the discrete Fourier transform (DFT) of the given complex vector, storing the result back into the vector.
* The vector's length must be a power of 2. Uses the Cooley-Tukey decimation-in-time radix-2 algorithm.
*/
private static void transformRadix2(double[] real, double[] imag) {
int n = real.length;
int levels = 31 - Integer.numberOfLeadingZeros(n); // Equal to floor(log2(n))
// if (1 << levels != n)
// throw new IllegalArgumentException("Length is not a power of 2");
double[] cosTable = new double[n / 2];
double[] sinTable = new double[n / 2];
for (int i = 0; i < n / 2; i++) {
cosTable[i] = Math.cos(2 * Math.PI * i / n);
sinTable[i] = Math.sin(2 * Math.PI * i / n);
}
// Bit-reversed addressing permutation
for (int i = 0; i < n; i++) {
int j = Integer.reverse(i) >>> (32 - levels);
if (j > i) {
double temp = real[i];
real[i] = real[j];
real[j] = temp;
temp = imag[i];
imag[i] = imag[j];
imag[j] = temp;
}
}
// Cooley-Tukey decimation-in-time radix-2 FFT
for (int size = 2; size <= n; size *= 2) {
int halfsize = size / 2;
int tablestep = n / size;
for (int i = 0; i < n; i += size) {
for (int j = i, k = 0; j < i + halfsize; j++, k += tablestep) {
double tpre = real[j+halfsize] * cosTable[k] + imag[j+halfsize] * sinTable[k];
double tpim = -real[j+halfsize] * sinTable[k] + imag[j+halfsize] * cosTable[k];
real[j + halfsize] = real[j] - tpre;
imag[j + halfsize] = imag[j] - tpim;
real[j] += tpre;
imag[j] += tpim;
}
}
// Prevent overflow in 'size *= 2'
if (size == n)
break;
}
}
/*
* Computes the discrete Fourier transform (DFT) of the given complex vector, storing the result back into the vector.
* The vector can have any length. This requires the convolution function, which in turn requires the radix-2 FFT function.
* Uses Bluestein's chirp z-transform algorithm.
*/
private static void transformBluestein(double[] real, double[] imag) {
int n = real.length;
int m = Integer.highestOneBit(n * 2 + 1) << 1;
// Trignometric tables
double[] cosTable = new double[n];
double[] sinTable = new double[n];
for (int i = 0; i < n; i++) {
int j = (int)((long)i * i % (n * 2)); // This is more accurate than j = i * i
cosTable[i] = Math.cos(Math.PI * j / n);
sinTable[i] = Math.sin(Math.PI * j / n);
}
// Temporary vectors and preprocessing
double[] areal = new double[m];
double[] aimag = new double[m];
for (int i = 0; i < n; i++) {
areal[i] = real[i] * cosTable[i] + imag[i] * sinTable[i];
aimag[i] = -real[i] * sinTable[i] + imag[i] * cosTable[i];
}
double[] breal = new double[m];
double[] bimag = new double[m];
breal[0] = cosTable[0];
bimag[0] = sinTable[0];
for (int i = 1; i < n; i++) {
breal[i] = breal[m - i] = cosTable[i];
bimag[i] = bimag[m - i] = sinTable[i];
}
// Convolution
double[] creal = new double[m];
double[] cimag = new double[m];
convolve(areal, aimag, breal, bimag, creal, cimag);
// Postprocessing
for (int i = 0; i < n; i++) {
real[i] = creal[i] * cosTable[i] + cimag[i] * sinTable[i];
imag[i] = -creal[i] * sinTable[i] + cimag[i] * cosTable[i];
}
}
/*
* Computes the circular convolution of the given real vectors. Each vector's length must be the same.
*/
private static void convolve(double[] x, double[] y, double[] out) {
// if (x.length != y.length || x.length != out.length)
// throw new IllegalArgumentException("Mismatched lengths");
int n = x.length;
convolve(x, new double[n], y, new double[n], out, new double[n]);
}
/*
* Computes the circular convolution of the given complex vectors. Each vector's length must be the same.
*/
private static void convolve(double[] xreal, double[] ximag, double[] yreal, double[] yimag, double[] outreal, double[] outimag) {
// if (xreal.length != ximag.length || xreal.length != yreal.length || yreal.length != yimag.length || xreal.length != outreal.length || outreal.length != outimag.length)
// throw new IllegalArgumentException("Mismatched lengths");
int n = xreal.length;
FFT(xreal, ximag);
FFT(yreal, yimag);
for (int i = 0; i < n; i++) {
double temp = xreal[i] * yreal[i] - ximag[i] * yimag[i];
ximag[i] = ximag[i] * yreal[i] + xreal[i] * yimag[i];
xreal[i] = temp;
}
inverseTransform(xreal, ximag);
// Scaling (because this FFT implementation omits it)
for (int i = 0; i < n; i++) {
outreal[i] = xreal[i] / n;
outimag[i] = ximag[i] / n;
}
}
/**
* Shift zero-frequency component to center of spectrum.
* @param x Data.
* @param direction Transformation direction.
*/
public static void FFTShift1D(double[] x, Direction direction) {
if (x.length == 1)
return;
double[] temp = x.clone();
int move = x.length / 2;
if(direction == Direction.Forward){
int c = 0;
for (int i = x.length - move; i < x.length; i++)
x[c++] = temp[i];
for (int i = 0; i < x.length - move; i++)
x[c++] = temp[i];
}
else{
int c = 0;
for (int i = move; i < x.length; i++)
x[c++] = temp[i];
for (int i = 0; i < move; i++)
x[c++] = temp[i];
}
}
/**
* Shift zero-frequency component to center of spectrum.
* @param Object.
* @param x Data.
* @param direction Transformation direction.
*/
public static void FFTShift1D(E[] x, Direction direction) {
if (x.length == 1)
return;
E[] temp = x.clone();
int move = x.length / 2;
if(direction == Direction.Forward){
int c = 0;
for (int i = x.length - move; i < x.length; i++)
x[c++] = temp[i];
for (int i = 0; i < x.length - move; i++)
x[c++] = temp[i];
}
else{
int c = 0;
for (int i = move; i < x.length; i++)
x[c++] = temp[i];
for (int i = 0; i < move; i++)
x[c++] = temp[i];
}
}
/**
* Shift zero-frequency component to center of spectrum.
* @param x Data.
* @param direction Direction.
*/
public static void FFTShift2D(double[][] x, Direction direction){
FFTShift2D(x, direction, 1);
FFTShift2D(x, direction, 2);
}
/**
* Shift zero-frequency component to center of spectrum.
* @param x Data.
* @param direction Direction.
* @param dimension Dimension.
*/
public static void FFTShift2D(double[][] x, Direction direction, int dimension){
//Create a copy
double[][] temp = new double[x.length][x[0].length];
for (int i = 0; i < x.length; i++) {
for (int j = 0; j < x[0].length; j++) {
temp[i][j] = x[i][j];
}
}
if(direction == Direction.Forward){
//Perform fftshift in the first dimension
if(dimension == 1){
int move = temp.length / 2;
for (int i = 0; i < move; i++) {
for (int j = 0; j < x[0].length; j++) {
x[i][j] = temp[temp.length - move + i][j];
}
}
for (int i = move; i < x.length; i++) {
for (int j = 0; j < x[0].length; j++) {
x[i][j] = temp[i - move][j];
}
}
}
//Perform fftshift in the second dimension
if (dimension == 2){
for (int i = 0; i < x.length; i++) {
FFTShift1D(x[i], FourierTransform.Direction.Forward);
}
}
}
else{
if(dimension == 1){
int move = temp.length / 2;
for (int i = 0; i < x.length - move; i++) {
for (int j = 0; j < x[0].length; j++) {
x[i][j] = temp[move+i][j];
}
}
for (int i = 0; i < move; i++) {
for (int j = 0; j < x[0].length; j++) {
x[x.length-move+i][j] = temp[i][j];
}
}
}
if(dimension == 2){
for (int i = 0; i < x.length; i++) {
FFTShift1D(x[i], FourierTransform.Direction.Backward);
}
}
}
}
/**
* Shift zero-frequency component to center of spectrum.
* @param x Data.
* @param direction Direction.
*/
public static void FFTShift2D(E[][] x, Direction direction){
FFTShift2D(x, direction, 1);
FFTShift2D(x, direction, 2);
}
/**
* Shift zero-frequency component to center of spectrum.
* @param x Data.
* @param direction Direction.
* @param dimension Dimension.
*/
public static void FFTShift2D(E[][] x, Direction direction, int dimension){
//Create a copy
E[][] temp = (E[][])new Object[x.length][x[0].length];
for (int i = 0; i < x.length; i++) {
for (int j = 0; j < x[0].length; j++) {
temp[i][j] = x[i][j];
}
}
if(direction == Direction.Forward){
//Perform fftshift in the first dimension
if(dimension == 1){
int move = temp.length / 2;
for (int i = 0; i < move; i++) {
for (int j = 0; j < x[0].length; j++) {
x[i][j] = temp[temp.length - move + i][j];
}
}
for (int i = move; i < x.length; i++) {
for (int j = 0; j < x[0].length; j++) {
x[i][j] = temp[i - move][j];
}
}
}
//Perform fftshift in the second dimension
if (dimension == 2){
for (int i = 0; i < x.length; i++) {
FFTShift1D(x[i], FourierTransform.Direction.Forward);
}
}
}
else{
if(dimension == 1){
int move = temp.length / 2;
for (int i = 0; i < x.length - move; i++) {
for (int j = 0; j < x[0].length; j++) {
x[i][j] = temp[move+i][j];
}
}
for (int i = 0; i < move; i++) {
for (int j = 0; j < x[0].length; j++) {
x[x.length-move+i][j] = temp[i][j];
}
}
}
if(dimension == 2){
for (int i = 0; i < x.length; i++) {
FFTShift1D(x[i], FourierTransform.Direction.Backward);
}
}
}
}
}
Ads help maintain this website.