Pretty cool stuff.

For people know who the capabilities of Arduino, is it possible to do real time image processing using opencv or similar library on it?

There’s an alternate way to save space: the discrete Hartley transform.

https://news.ycombinator.com/item?id=27386319

https://twitter.com/theshawwn/status/1400383554673065984

  dht(x) = fft( (1 + 1j)*x ).real / area(x)**0.5

  area(x) = np.prod(np.shape(x))

The dht is its own inverse, which is a neat trick. No need for an inverse fft. In other words, dht(dht(x)) == x.

Notice that the output is the real component of the fft. That means the storage required is exactly identical to the input signal. And since the input signal is copied to the real and imaginary components (1 + 1j)*x, the intermediate representation size is also equal to the input signal size. (Just take sin and cos of the input signal.)

The dht has almost all the same properties of the fft. You can blur an image by taking a hamming window and multiplying. You can resize an image by fftshift + pad with zeros + fftshift. Etc.

In practice the dht seems to have all the benefits of fft with very few downsides. I’m amazed it isn’t more popular.

One tidbit I got out of this that is not directly related to the content of the post is that there are apparently some high-quality instructables out there, and that people spend time writing them!

99% of the instructables I’ve come across in the last 10 or so years have been low-effort junk that aren’t even worth reading. The few the author linked are quite great.

Think about using the Despain algorithm, derived by recursively decomposing an N-point FFT into FFTs of size sqrt(N). You end up with a bunch of 4-point FFTs where the twiddle factors are rotations by multiples of pi/2, which can be implemented with swapping of real/imaginary parts and a change of sign. Non-degenerate twiddle factors still occur between those 4-point FFTs In this way the number of maths operations can be reduced. The cost is that the input and output are both in a weird order.

This is super cool—but why use a micro with no fp unit and only 2048 bytes of ram? Something much more capable likely wouldn't be more expensive.

It would be interesting to know what the side project that required FFT on the Arduino was. I'd also be interested in which other applications of the FFT algorithm has on Arduino given the performance shown. Could you create a real time guitar tuner for example?

Really this should be titled for AVR - Arduino covers a broad range of microcontrollers with very different capabilities. As much as some people deliberately try suggest Arduino is a microcontroller, it isn't.

Little known fact: FFT is an O(nlgn) algorithm, but incremental FFT is O(n), meaning that if you want to compute FFT on the past n points of a stream of samples, it only takes O(n) to compute it for every new incoming sample.

where would be the use cases for FFT ? I'm a newbie.

The author links to another blog post called "A nice approximation of the norm of a 2D vector" [1], Recently I learnt from Youtube about the Alpha max plus beta min algorithm [2] which is a better approximation, it uses 1 max and linear combination to achieve 3.96% largest error compared to the approximation in the blog post which uses 2 max and has 5.3% error. I also wrote a comment on his blog so hopefully he will see it.

[1]: https://klafyvel.me/blog/articles/approximate-euclidian-norm... [2]: https://en.wikipedia.org/wiki/Alpha_max_plus_beta_min_algori...

> abhilash_patel's instructable is a Great instructable

Christ, I hate Instructables. A site with such shitty presentation that should be so much better.

Years ago I tried using an FFT library for the Arduino to convert audio to frequency domain in order to "bucket" the audio spectrum and (hint: music visualizer) light up some LEDs.

The Arduino+FFT were not however up to the task and I ended up going with a dedicated IC to do the audio frequency bucketing.

I suspect these days a better FFT or hardware like the Teensy could likely handle the job.

This AVR FFT is potentially faster.

http://wiki.openmusiclabs.com/wiki/ArduinoFFT

There's also a Hartley available there.

Some good links too. Like http://www.elektronika.kvalitne.cz/ATMEL/necoteorie/transfor...