BPM detectors work by finding the strongest period in the onset detection function - a function of time indicating how likely it is that there is an onset at time t. Which brings the topic of onset detection...
Tracking energy/envelope in the time domain is a weak strategy for detecting rhythm/notes, because:
- For some instruments, there are playing techniques which create new notes without a significant change of energy (for example moving the finger on a string of a cello with no change in bowing, or changing the fingering on a flute with continuous blowing). This has the effect of creating changes in fundamental frequency without a noticeable change in the time-domain envelope.
- A lot of commercial music is so heavily compressed that the signal is almost "pumped" to maximum amplitude all the time.
- While this is yet another corner case, it is worth reminding that some instruments or playing techniques have very slow attacks.
So naively looking for peaks in the time-domain (via energy) will not be very robust. You have to look for better "clues", and the frequency domain is the answer. The simplest thing that can be done in the frequency domain is to compute the difference of energy between adjacent STFT frames (a measure known as the "spectral energy flux").
A more elaborate metric, which is actually as cheap in terms of computing costs, consists in checking the deviation between the actual and expected value of the complex amplitude in a STFT bin (reference here) - this deviation would be null in the stable segment of a note (as the amplitudes are just sustaining or slowly decaying; and the phases are just keeping on rolling), and high at an onset.
All these techniques have very modest computational costs and can be implemented in realtime even on relatively cheap microcontrollers - a complete beat-tracker (onset detection + BPM detection + beat tracking) is in the 10 MIPS range.