Project Overview |
Demonstration Video |
|
Languages: C++
Development Time: 12 Weeks
|
Gallery
Development and Strategy
This project implements an existing beat detection algorithm by Frédéric Patin, which can be found here.
Visualization
One of the goals of the project is to be able to visualize transformed audio data. This is achieved using a Fast Fourier Transform from the FMOD sound library to transform the audio data from time/waveform space to frequency space. The visualization code then flips the resulting data across a central axis to mirror the plot going the other way, which gives a neat effect.
Beat Detection
In order to achieve the actual beat detection, the process is split into several steps. The Fast Fourier Transform gives us a series of complex numbers. If we consider the real part of the data to be audio data from the left speaker, and the imaginary part being the right speaker, we can apply the algorithm to the data.
Steps to take for the algorithm:
Below is an image that shows how the transformed data is organized. The frequencies of the sound data are split into 32 sub-bands, as shown by the vertical white lines below. Each sub-band has it's own energy history buffer, which allows us to detect beats in different frequency ranges.
Steps to take for the algorithm:
- Calculate amplitude data from the transformed values (complex numbers).
- Use this data to calculate sound energy for each sub-band.
- Compare the current energy value to an energy history buffer to determine if there is a beat.
Below is an image that shows how the transformed data is organized. The frequencies of the sound data are split into 32 sub-bands, as shown by the vertical white lines below. Each sub-band has it's own energy history buffer, which allows us to detect beats in different frequency ranges.
Transformed frequency data split into 32 sub-bands.
Calculating Sound Energies for Beat Detection
|
Step One
Assuming 1024 samples…
|
Step one of sound energy calculation
|
|
Step Two
Next, we use B to find the instant energy values per sub-band
|
Step two of sound energy calculation
|
|
Step Three
For each sub-band, it corresponds to a sound energy history buffer H[ i ], which contains the last 43 samples for that sub-band
|
Step three of sound energy calculation
|
|
Step Four
For each sub-band, compare the instant energy to the average energy history multiplied by a beat threshold constant
|
If the current instant energy is higher than the sub-band's history, we have a beat.
|
The project currently monitors only sub-band zero, which is where the lower frequencies reside. The purpose of this is to detect bass hits, making the project useful for detecting beats in techno music.
Real-Time BPM Estimation
Beats-per-minute (BPM) estimation is based on a moving average of detected beat times. First, we store the time that a beat occurs in a beat history buffer H[ n ]. Then every frame, we flush out all values that are more than a second old, and recalculate. The current BPM is the one that is calculated the most often out of a history of calculated BPMs.
Use the beat times recorded in every second to calculate the average BPM for the song.
The Game
The game built on top of the beat detector is a simple 2D shooter. The player's ship is locked to a circle in the middle of the screen, and enemies spawn on the outer edges traveling inward whenever a beat occurs. The player must shoot the enemies before they reach the circle they are defending. The circle slowly expands as the player racks up more kills, and shrinks when enemies hit the circle.
Post Mortem
What Went Well
- The project allowed me to explore an area I am interested in, which is audio visualization and utilization.
- The integration of the FMOD library made accessing the audio data simpler, and allowed for the creation of an audio system for my engine.
- Once the beat detection portion was completed, integrating the beat detector into a game went smoothly, as the calculated beat data is exposed to external users. This also made it trivial to send beat data to corresponding graphics shaders for the game portion.
Challenges
- Understanding the math behind the beat detection algorithm was difficult, and required me to do some research regarding digital signal processing.
- Figuring out how to handle the audio data coming in took some work, as it was not entirely clear as to what the values coming in should be. Some numbers would be very high, while others would be extremely low, to tens of decimal places.
- The detection did not end up quite as accurate as I would have liked. There are many other avenues to explore in this problem space, which I did not have time to look into.
What Was Learned
- I have discovered that there are many different approaches to this problem, and the space is quite complex. For example, additional data can be found by finding reflections in the audio data from lower to higher frequencies, such as the patterns generated from square waves.
- Finding beats for songs without clear cut bass notes requires more analyzing of the audio data beyond monitoring the lower frequencies.