AcademicFFT

Package

Class

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD

Class AcademicFFT

java.lang.Object
  AcademicFFT

public class AcademicFFT
extends java.lang.Object
extends java.lang.Object

The purpose of this class is to encapsulate operations related to the discrete Fourier transform of periodic sequences, images, and volumes. If x is a discrete sequence assumed to be periodic over K samples, then its discrete Fourier transform is X while the inverse discrete Fourier transform of X is x. The transforms are defined as the pair

∀n ∈ [0…K − 1]: X[n] = ℱ{x}[n] = ∑_{k ∈ [0…K − 1]} x[k] e^{−j n (2 π ∕ K) k}
∀k ∈ [0…K − 1]: x[k] = ℱ⁻¹{X}[k] = (1 ∕ K) ∑_{n ∈ [0…K − 1]} X[n] e^{j n (2 π ∕ K) k}

A few relevant relations are

j² = −1
∀k, n ∈ [0…K − 1], m ∈ ℤ: x[k] = x[k + m K], X[n] = X[n + m K]
∀λ ∈ ℂ: ℱ{λ x + y} = λ X + Y
ℱ{X}[0] = K x[0]; m ∈ [1…K − 1]: ℱ{X}[m] = K x[K − m]
k₀ ∈ [1…K − 1]: ((k ∈ [0…k₀ − 1]: y[k] = x[K + k − k₀]), (k ∈ [k₀…K − 1]: y[k] = x[k − k₀])); Y[n] = e^{−j k₀
(2 π ∕ K) n} X[n]
n ∈ [0…K − 1]: (k₀ ∈ [0…K − 2]: (x ∗ y)[k₀] = ∑_{k ∈ [0…k0]} x[k] y[k₀ − k] + ∑_{k ∈ [k0 + 1…K − 1]} x[k] y[K + k₀ − k]), ((x ∗ y)[K − 1] = ∑_{k ∈ [0…K − 1]} x[k] y[K − 1 − k]); ℱ{x ∗ y}[n] = X[n] Y[n]
〈x, y〉 = ∑_{k ∈ [0…K − 1]} x[k] (y[k])^* = (1 ∕ K) 〈X, Y〉 = (1 ∕ K) ∑_{n ∈ [0…K − 1]} X[n] (Y[n])^*
x[0] = 1, k ∈ [1…K − 1]: x[k] = 0; n ∈ [0…K − 1]: X[n] = 1
k ∈ [0…K − 1]: x[k] = 1; X[0] = K, n ∈ [1…K − 1]: X[n] = 0
x = ℜ(x); ℑ(X[0]) = 0, (2 ∣ K: ℑ(X[K ∕ 2]) = 0), n ∈ [1…K − 1]: X[n] = (X[K − n])^*
x = ℜ(x); y = ℜ(y); F = ℱ{x + j y}; X[0] = ℜ(F[0]); Y[0] = ℑ(F[0]); n ∈ [1…K − 1]: X[n] = (F[n] + (F[K − n])^*) ∕ 2, Y[n] = −j (F[n] − (F[K − n])^*) ∕ 2

In two dimensions

ℱ{x}[n₁, n₂] = ℱ_k2{ℱ_k1{x[k₁, k₂]}[n₁, k₂]}[n₁, n₂] = ℱ_k1{ℱ_k2{x[k₁, k₂]}[k₁, n₂]}[n₁, n₂]

In three dimensions

ℱ{x}[n₁, n₂, n₃] = ℱ_k3{ℱ_k2{ℱ_k1{x[k₁, k₂, k₃]}[n₁, k₂, k₃]}[n₁, n₂, k₃]}[n₁, n₂, n₃] = ℱ_k3{ℱ_k1{ℱ_k2{x[k₁, k₂, k₃]}[k₁, n₂, k₃]}[n₁, n₂, k₃]}[n₁, n₂, n₃] = ℱ_k2{ℱ_k3{ℱ_k1{x[k₁, k₂, k₃]}[n₁, k₂, k₃]}[n₁, k₂, n₃]}[n₁, n₂, n₃] = ℱ_k2{ℱ_k1{ℱ_k3{x[k₁, k₂, k₃]}[k₁, k₂, n₃]}[n₁, k₂, n₃]}[n₁, n₂, n₃] = ℱ_k1{ℱ_k3{ℱ_k2{x[k₁, k₂, k₃]}[k₁, n₂, k₃]}[k₁, n₂, n₃]}[n₁, n₂, n₃] = ℱ_k1{ℱ_k2{ℱ_k3{x[k₁, k₂, k₃]}[k₁, k₂, n₃]}[k₁, n₂, n₃]}[n₁, n₂, n₃]

Data are provided as the pair (real part, imaginary part). The real part is assumed to be provided as an array that contains raster data, with the convention that the indexing for the horizontal dimension is faster than the indexing for the vertical dimension, itself faster than the indexing for the depth dimension. The imaginary part follows the same organization.

The two buffers that are provided to some methods must have the same length as the data. They are used internally as temporary storage for the computations. They are there as a convenience to avoid repeated allocations.

Nested Class Summary
`static class`	`AcademicFFT.InputDataType` This enumeration provides the constants that describe the type of input (complex or real) of a Fourier transform.

Field Summary
`protected double[]`	`imBufferDouble`
`protected float[]`	`imBufferFloat`
`protected double[]`	`imDataDouble`
`protected float[]`	`imDataFloat`
`protected double[]`	`reBufferDouble`
`protected float[]`	`reBufferFloat`
`protected double[]`	`reDataDouble`
`protected float[]`	`reDataFloat`

Constructor Summary
`AcademicFFT(int width, int fourierOrigin1)` This constructor prepares a one-dimensional Fourier transform.
`AcademicFFT(int width, int height, int fourierOrigin1, int fourierOrigin2)` This constructor prepares a two-dimensional Fourier transform.
`AcademicFFT(int width, int height, int depth, int fourierOrigin1, int fourierOrigin2, int fourierOrigin3)` This constructor prepares a three-dimensional Fourier transform.

Method Summary
`static void`	`amplitudePhaseToRealImaginary(double[] amToRe, double[] phToIm)` This method converts complex data from an amplitude-phase representation to a real-imaginary representation.
`static void`	`amplitudePhaseToRealImaginary(float[] amToRe, float[] phToIm)` This method converts complex data from an amplitude-phase representation to a real-imaginary representation.
`void`	`circularConvolution(double[] reData1, double[] imData1, double[] reData2, double[] imData2, double[] reBuffer, double[] imBuffer)` This method computes the circular convolution of data provided in a real-imaginary representation.
`void`	`circularConvolution(float[] reData1, float[] imData1, float[] reData2, float[] imData2, float[] reBuffer, float[] imBuffer)` This method computes the circular convolution of data provided in a real-imaginary representation.
`void`	`circularFourierConvolution(double[] reData1, double[] imData1, double[] reFourierData2, double[] imFourierData2, double[] reBuffer, double[] imBuffer)` This method computes the circular convolution of data; the first operand is provided in a real-imaginary representation while the second operand is provided in a real-imaginary Fourier representation.
`void`	`circularFourierConvolution(float[] reData1, float[] imData1, float[] reFourierData2, float[] imFourierData2, float[] reBuffer, float[] imBuffer)` This method computes the circular convolution of data; the first operand is provided in a real-imaginary representation while the second operand is provided in a real-imaginary Fourier representation.
`void`	`directTransform(double[] reData, double[] imData, double[] reBuffer, double[] imBuffer, AcademicFFT.InputDataType inputDataType)` This method computes the Fourier transform of data provided in a real-imaginary representation.
`void`	`directTransform(float[] reData, float[] imData, float[] reBuffer, float[] imBuffer, AcademicFFT.InputDataType inputDataType)` This method computes the Fourier transform of data provided in a real-imaginary representation.
`void`	`inverseTransform(double[] reData, double[] imData, double[] reBuffer, double[] imBuffer)` This method computes the inverse Fourier transform of data provided in a real-imaginary representation.
`void`	`inverseTransform(float[] reData, float[] imData, float[] reBuffer, float[] imBuffer)` This method computes the inverse Fourier transform of data provided in a real-imaginary representation.
`void`	`makeHermitian(double[] reData, double[] imData, double[] reBuffer, double[] imBuffer)` This method enforces Hermitian symmetry to Fourier data provided in a real-imaginary representation.
`void`	`makeHermitian(float[] reData, float[] imData, float[] reBuffer, float[] imBuffer)` This method enforces Hermitian symmetry to Fourier data provided in a real-imaginary representation.
`static void`	`realImaginaryToAmplitudePhase(double[] reToAm, double[] imToPh)` This method converts complex data from a real-imaginary representation to an amplitude-phase representation.
`static void`	`realImaginaryToAmplitudePhase(float[] reToAm, float[] imToPh)` This method converts complex data from a real-imaginary representation to an amplitude-phase representation.
`static void`	`reset()` Several `static` auxiliary data are stored by this class, as needs arise, to be reused by subsequent instances of this class; this method frees the associated memory.

Methods inherited from class java.lang.Object
`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`

Field Detail

imBufferDouble

protected double[] imBufferDouble

imDataDouble

protected double[] imDataDouble

reBufferDouble

protected double[] reBufferDouble

reDataDouble

protected double[] reDataDouble

imBufferFloat

protected float[] imBufferFloat

imDataFloat

protected float[] imDataFloat

reBufferFloat

protected float[] reBufferFloat

reDataFloat

protected float[] reDataFloat

Constructor Detail

AcademicFFT

public AcademicFFT(int width,
                   int fourierOrigin1)

This constructor prepares a one-dimensional Fourier transform. It depends on the length of the sequence but not on the actual data being transformed, so that it can be reused for different data. It specifies the convention to adopt for locating the origin of the Fourier transform.

Parameters:: width - The length of the sequence.; fourierOrigin1 - The origin of the Fourier transform in the Fourier domain.

AcademicFFT

public AcademicFFT(int width,
                   int height,
                   int fourierOrigin1,
                   int fourierOrigin2)

This constructor prepares a two-dimensional Fourier transform. It depends on the width and height of the image but not on the actual data being transformed, so that it can be reused for different data. It specifies the convention to adopt for locating the origin of the Fourier transform.

Parameters:: width - The width of the image.; height - The height of the image.; fourierOrigin1 - The horizontal component of the origin of the Fourier transform in the Fourier domain.; fourierOrigin2 - The vertical component of the origin of the Fourier transform in the Fourier domain.

AcademicFFT

public AcademicFFT(int width,
                   int height,
                   int depth,
                   int fourierOrigin1,
                   int fourierOrigin2,
                   int fourierOrigin3)

This constructor prepares a three-dimensional Fourier transform. It depends on the width, height, and depth of the volume but not on the actual data being transformed, so that it can be reused for different data. It specifies the convention to adopt for locating the origin of the Fourier transform.

Parameters:: width - The width of the volume.; height - The height of the volume.; depth - The depth of the volume.; fourierOrigin1 - The horizontal component of the origin of the Fourier transform in the Fourier domain.; fourierOrigin2 - The vertical component of the origin of the Fourier transform in the Fourier domain.; fourierOrigin3 - The depth component of the origin of the Fourier transform in the Fourier domain.

Method Detail

amplitudePhaseToRealImaginary

public static void amplitudePhaseToRealImaginary(double[] amToRe,
                                                 double[] phToIm)

This method converts complex data from an amplitude-phase representation to a real-imaginary representation. The phase is assumed to be provided in radian units.

Parameters:: amToRe - At input, the amplitude of the data; at output, the real part of the data. The processing is in-place.; phToIm - At input, the phase of the data; at output, the imaginary part of the data. The processing is in-place.

amplitudePhaseToRealImaginary

public static void amplitudePhaseToRealImaginary(float[] amToRe,
                                                 float[] phToIm)

This method converts complex data from an amplitude-phase representation to a real-imaginary representation. The phase is assumed to be provided in radian units.

Parameters:: amToRe - At input, the amplitude of the data; at output, the real part of the data. The processing is in-place.; phToIm - At input, the phase of the data; at output, the imaginary part of the data. The processing is in-place.

realImaginaryToAmplitudePhase

public static void realImaginaryToAmplitudePhase(double[] reToAm,
                                                 double[] imToPh)

This method converts complex data from a real-imaginary representation to an amplitude-phase representation. The resulting phase is provided in radian units in the range [−π, π].

Parameters:: reToAm - At input, the real part of the data; at output, the amplitude of the data. The processing is in-place.; imToPh - At input, the imaginary part of the data; at output, the phase of the data. The processing is in-place.

realImaginaryToAmplitudePhase

public static void realImaginaryToAmplitudePhase(float[] reToAm,
                                                 float[] imToPh)

This method converts complex data from a real-imaginary representation to an amplitude-phase representation. The resulting phase is provided in radian units in the range [−π, π].

Parameters:: reToAm - At input, the real part of the data; at output, the amplitude of the data. The processing is in-place.; imToPh - At input, the imaginary part of the data; at output, the phase of the data. The processing is in-place.

reset

public static void reset()

Several static auxiliary data are stored by this class, as needs arise, to be reused by subsequent instances of this class; this method frees the associated memory.

circularConvolution

public void circularConvolution(double[] reData1,
                                double[] imData1,
                                double[] reData2,
                                double[] imData2,
                                double[] reBuffer,
                                double[] imBuffer)

This method computes the circular convolution of data provided in a real-imaginary representation. The number of dimensions of the data is determined by the constructor of this object. Likewise, the dimensions themselves must match those provided to the constructor of this object.

Parameters:: reData1 - At input, the real part of the first operand; at output, the real part of the convolution result. The processing is in-place.; imData1 - At input, the imaginary part of the first operand; at output, the imaginary part of the convolution result. The processing is in-place.; reData2 - At input, the real part of the second operand; at output, the real part of the Fourier transform of the second operand. The origin of the Fourier transform of the second operand follows the conventions for this object. The processing is in-place.; imData2 - At input, the imaginary part of the second operand; at output, the imaginary part of the Fourier transform of the second operand. The origin of the Fourier transform of the second operand follows the conventions for this object. The processing is in-place.; reBuffer - Garbage in, garbage out. A temporary buffer of length reData1.length is created internally if reBuffer is null.; imBuffer - Garbage in, garbage out. A temporary buffer of length imData1.length is created internally if imBuffer is null.

circularConvolution

public void circularConvolution(float[] reData1,
                                float[] imData1,
                                float[] reData2,
                                float[] imData2,
                                float[] reBuffer,
                                float[] imBuffer)

Parameters:: reData1 - At input, the real part of the first operand; at output, the real part of the convolution result. The processing is in-place.; imData1 - At input, the imaginary part of the first operand; at output, the imaginary part of the convolution result. The processing is in-place.; reData2 - At input, the real part of the second operand; at output, the real part of the Fourier transform of the second operand. The origin of the Fourier transform of the second operand follows the conventions for this object. The processing is in-place.; imData2 - At input, the imaginary part of the second operand; at output, the imaginary part of the Fourier transform of the second operand. The origin of the Fourier transform of the second operand follows the conventions for this object. The processing is in-place.; reBuffer - Garbage in, garbage out. A temporary buffer of length reData1.length is created internally if reBuffer is null.; imBuffer - Garbage in, garbage out. A temporary buffer of length imData1.length is created internally if imBuffer is null.

circularFourierConvolution

public void circularFourierConvolution(double[] reData1,
                                       double[] imData1,
                                       double[] reFourierData2,
                                       double[] imFourierData2,
                                       double[] reBuffer,
                                       double[] imBuffer)

This method computes the circular convolution of data; the first operand is provided in a real-imaginary representation while the second operand is provided in a real-imaginary Fourier representation. The number of dimensions of the data is determined by the constructor of this object. Likewise, the dimensions themselves must match those provided to the constructor of this object.

Parameters:: reData1 - At input, the real part of the first operand; at output, the real part of the convolution result. The processing is in-place.; imData1 - At input, the imaginary part of the first operand; at output, the imaginary part of the convolution result. The processing is in-place.; reFourierData2 - Real part of the Fourier transform of the second operand. The origin of the Fourier transform of the second operand follows the conventions for this object.; imFourierData2 - Imaginary part of the Fourier transform of the second operand. The origin of the Fourier transform of the second operand follows the conventions for this object.; reBuffer - Garbage in, garbage out. A temporary buffer of length reData1.length is created internally if reBuffer is null.; imBuffer - Garbage in, garbage out. A temporary buffer of length imData1.length is created internally if imBuffer is null.

circularFourierConvolution

public void circularFourierConvolution(float[] reData1,
                                       float[] imData1,
                                       float[] reFourierData2,
                                       float[] imFourierData2,
                                       float[] reBuffer,
                                       float[] imBuffer)

Parameters:: reData1 - At input, the real part of the first operand; at output, the real part of the convolution result. The processing is in-place.; imData1 - At input, the imaginary part of the first operand; at output, the imaginary part of the convolution result. The processing is in-place.; reFourierData2 - Real part of the Fourier transform of the second operand. The origin of the Fourier transform of the second operand follows the conventions for this object.; imFourierData2 - Imaginary part of the Fourier transform of the second operand. The origin of the Fourier transform of the second operand follows the conventions for this object.; reBuffer - Garbage in, garbage out. A temporary buffer of length reData1.length is created internally if reBuffer is null.; imBuffer - Garbage in, garbage out. A temporary buffer of length imData1.length is created internally if imBuffer is null.

directTransform

public void directTransform(double[] reData,
                            double[] imData,
                            double[] reBuffer,
                            double[] imBuffer,
                            AcademicFFT.InputDataType inputDataType)

This method computes the Fourier transform of data provided in a real-imaginary representation. The number of dimensions of the data is determined by the constructor of this object. Likewise, the dimensions themselves must match those provided to the constructor of this object.

Parameters:: reData - At input, the real part of the data; at output, the real part of the Fourier transform of the data. The processing is in-place.; imData - At input, the imaginary part of the data; at output, the imaginary part of the Fourier transform of the data. The processing is in-place.; reBuffer - Garbage in, garbage out. A temporary buffer of length reData.length is created internally if reBuffer is null.; imBuffer - Garbage in, garbage out. A temporary buffer of length imData.length is created internally if imBuffer is null.; inputDataType - When set to AcademicFFT.InputDataType.REALINPUT, disregards the values provided in imData and assumes that every element of imData is 0.0; when set to AcademicFFT.InputDataType.COMPLEXINPUT, honors the values provided in imData.

directTransform

public void directTransform(float[] reData,
                            float[] imData,
                            float[] reBuffer,
                            float[] imBuffer,
                            AcademicFFT.InputDataType inputDataType)

Parameters:: reData - At input, the real part of the data; at output, the real part of the Fourier transform of the data. The processing is in-place.; imData - At input, the imaginary part of the data; at output, the imaginary part of the Fourier transform of the data. The processing is in-place.; reBuffer - Garbage in, garbage out. A temporary buffer of length reData.length is created internally if reBuffer is null.; imBuffer - Garbage in, garbage out. A temporary buffer of length imData.length is created internally if imBuffer is null.; inputDataType - When set to AcademicFFT.InputDataType.REALINPUT, disregards the values provided in imData and assumes that every element of imData is 0.0; when set to AcademicFFT.InputDataType.COMPLEXINPUT, honors the values provided in imData.

inverseTransform

public void inverseTransform(double[] reData,
                             double[] imData,
                             double[] reBuffer,
                             double[] imBuffer)

This method computes the inverse Fourier transform of data provided in a real-imaginary representation. The number of dimensions of the data is determined by the constructor of this object. Likewise, the dimensions themselves must match those provided to the constructor of this object.

Parameters:: reData - At input, the real part of the data; at output, the real part of the Fourier transform of the data. The processing is in-place.; imData - At input, the imaginary part of the data; at output, the imaginary part of the Fourier transform of the data. The processing is in-place.; reBuffer - Garbage in, garbage out. A temporary buffer of length reData.length is created internally if reBuffer is null.; imBuffer - Garbage in, garbage out. A temporary buffer of length imData.length is created internally if imBuffer is null.

inverseTransform

public void inverseTransform(float[] reData,
                             float[] imData,
                             float[] reBuffer,
                             float[] imBuffer)

Parameters:: reData - At input, the real part of the data; at output, the real part of the Fourier transform of the data. The processing is in-place.; imData - At input, the imaginary part of the data; at output, the imaginary part of the Fourier transform of the data. The processing is in-place.; reBuffer - Garbage in, garbage out. A temporary buffer of length reData.length is created internally if reBuffer is null.; imBuffer - Garbage in, garbage out. A temporary buffer of length imData.length is created internally if imBuffer is null.

makeHermitian

public void makeHermitian(double[] reData,
                          double[] imData,
                          double[] reBuffer,
                          double[] imBuffer)

This method enforces Hermitian symmetry to Fourier data provided in a real-imaginary representation. The number of dimensions of the data is determined by the constructor of this object. Likewise, the dimensions themselves must match those provided to the constructor of this object. The output Fourier data Y satisfies ℜ(Y[0]) = ℜ(X[0]), ℑ(Y[0]) = 0, Y[n] = ℜ(X[n] + X[K − n]) ∕ 2 + j ℑ(X[n] − X[K − n]) ∕ 2 for n ∈ [1…K − 1], where X is the input Fourier data.

Parameters:: reData - At input, the real part of the data; at output, the real part is symmetric with respect to the origin. The processing is in-place.; imData - At input, the imaginary part of the data; at output, the imaginary part is antisymmetric with respect to the origin. The processing is in-place.; reBuffer - Garbage in, garbage out. A temporary buffer of length reData.length is created internally if reBuffer is null.; imBuffer - Garbage in, garbage out. A temporary buffer of length imData.length is created internally if imBuffer is null.

makeHermitian

public void makeHermitian(float[] reData,
                          float[] imData,
                          float[] reBuffer,
                          float[] imBuffer)

Parameters:: reData - At input, the real part of the data; at output, the real part is symmetric with respect to the origin. The processing is in-place.; imData - At input, the imaginary part of the data; at output, the imaginary part is antisymmetric with respect to the origin. The processing is in-place.; reBuffer - Garbage in, garbage out. A temporary buffer of length reData.length is created internally if reBuffer is null.; imBuffer - Garbage in, garbage out. A temporary buffer of length imData.length is created internally if imBuffer is null.

Package

Class

Tree

Deprecated

Index

Help

PREV CLASS NEXT CLASS

FRAMES NO FRAMES

SUMMARY: NESTED | FIELD | CONSTR | METHOD

DETAIL: FIELD | CONSTR | METHOD