iPhone Accelerate Framework FFT to convert a two-dimensional array

Question

I'm working on a project that requires a Fourier transform of a 2D array.

However, I'm far from being an expert with both FFT's or particularly vDSP.

I've seen some examples here, here or here but they are either for 1D arrays or I can't quite understand them.

What I wish to trasform is this array that I build as follows:

 if (!_double2DArray) {
  _double2DArray = (double**) malloc([traces count]*sizeof(double*));
}

for (NSInteger i=0; i<[traces count]; i++) {
  Trace *trace = [traces objectAtIndex:i];
  _double2DArray[i] = (double*) malloc(length*sizeof(double));

  NSMutableArray *traceAxis = [trace getTraceAxis:axis];
  for (NSInteger j=0; j<[[trace traceLength] integerValue]; j++) {
    _double2DArray[i][j] = [[traceAxis objectAtIndex:j] doubleValue];
  }
}

score 3 · Accepted Answer · answered May 08 '13 at 19:05

To use vDSP, you will need to use actual two-dimensional arrays. The code you show creates an array of pointers to arrays, which is not a two-dimensional array. (It is composed of pieces from separate allocations and may have irregular spacing. vDSP requires that the columns of arrays be regularly spaced.)

It is likely you want to perform a real-to-complex FFT. For various reasons, this requires reformatting the real input data into two arrays, one for the elements with even column indices and one for the elements with odd column indices. This is what the vDSP_ctoz call does in the demonstration code you linked to, but you would use vDSP_ctozD for double precision. (If you do not need double precision, use float. It will be greatly faster in the FFT routines and other high-volume work.)

Before you perform an FFT with vDSP, you must obtain a setup object by calling vDSP_create_fftsetupD, as shown in the demonstration code. To perform the FFT, you call vDSP_fft2d_zripD. The setup object is released by calling vDPS_destroy_fftsetupD.

The create and destroy calls are expensive and should be performed rarely. They should be used by creating a setup early in your program and using it repeatedly with FFT calls.

The data returned by vDSP_fft2d_zripD is packed in an unusual format, and you will need to refer to this documentation for information about it.

@dwbrito: Objective-C does not have the same formal specification as C, but it is said to be a superset of C, and C has supported variable-length arrays for some time. For example, the following code compiles without error with Apple clang 4.0: `void foo(int a, int b) { float x[a][b]; float (*y)[a][b] = malloc(sizeof *y); float (*z)[b] = malloc(a * sizeof *z); }`. You may find the third alternative to be the most convenient, since it is better for large arrays than the automatic object is (due to stack size limits) and is usable with the simple syntax `z[i][j]`. — Eric Postpischil, May 10 '13 at 14:02
Actually, my problem is that, at least in the vDSP samples, the way they use the 2d array is not an usual array[x][y], but instead it appears to be a 1d array: https://developer.apple.com/library/mac/#samplecode/vDSPExamples/Listings/DemonstrateFFT2D_c.html#//apple_ref/doc/uid/DTS10004300-DemonstrateFFT2D_c-DontLinkElementID_7 (check the " Signal[(r*C + c) * Stride] =" part) — dwbrito, May 10 '13 at 15:49
@dwbrito: You can use a stride of one and ignore it in this case. Then the indexing is `Signal[r*C + c]`. That is equivalent to `S[r][c]` where `S` is the one-dimensional array converted to two-dimensional, as with the cast `(float (*)[C]) Signal`. This conversion is safe on Apple systems using Apple compilers. Or you can use the index arithmetic explicitly as shown, keeping a one-dimensional array. (Strides have purposes for traversing columns of matrices or down-sampling singles by using only some of their elements. Mostly, you should use a stride of one for real arrays.) — Eric Postpischil, May 10 '13 at 16:23

iPhone Accelerate Framework FFT to convert a two-dimensional array

1 Answers1