Maximum call stack size exceeded (rec_FFT)

[izzy-md]

Hey there,

I've been working on a quality image detection js thing and came across this library. I've been wanting to use an FFT transform to be able to determine the quality of the image, however, when I pass in the grayscale image data, I get a maximum call stack size exceeded, is this due to the size of the array?

Example https://codepen.io/izzy-md/pen/JZbOWy?editors=0010

Error

RangeError: Maximum call stack size exceeded
    at rec_FFT (VM11697 fourier.js:37)

Note: I'm planning on making a JS implementation of this formula https://www.sciencedirect.com/science/article/pii/S1877705813016007

[izzy-md]

Any news on this?

[turbomaze]

I've been transitioning to a new job and unfortunately have not had time to look into this.

Does the library work as expected on the sample images? Due to the nature of the recursion (logarithmically many layers), I would be surprised if the algorithm exceeded the call stack size for reasons related to the input size. I suspect the issue is either an underlying bug or a confusing API. I would get your code working with the sample images and slowly change it to suit your use case. See where it breaks down. If you're able to pinpoint the cause of this issue then I can fix any underlying bugs in the library.

[izzy-md]

That's totally fine! Hope you've been settling in your new job fine :)

So it works on a single image (I used the grace one, but it's incredibly slow and render blocking too :/ (same link))

[OckhamRazor]

Probably because the size of the picture is not a power of 2.

  function rec_FFT(out, start, sig, offset, N, s) {
    if (N === 1) { // Note: if sig.length is not a power of 2, it won't end
      out[start] = new Complex(sig[offset], 0); // array
    } else {
      rec_FFT(out, start, sig, offset, N/2, 2*s);
      rec_FFT(out, start+N/2, sig, offset+s, N/2, 2*s);
      for (var k = 0; k < N/2; k++) {
        var twiddle = cisExp(-2*Math.PI*k/N);
        var t = out[start+k];
        out[start+k] = t.plus(twiddle.times(out[start+k+N/2]));
        out[start+k+N/2] = t.minus(
          twiddle.times(out[start+k+N/2])
        );
      }
    }
  }

[photopea]

In Fourier.transform(X,Y), the X should be an array of numbers (like [1,2,3,4,2...])

If you give any object as the first parameter, you will get "Maximum call stack size exceeded".

Too bad the author did not have time to write the specification for this library :(