William Vennes
William Vennes
  • Home
  • Individual Projects
    • Beat Detection
    • Tile-based Level Editor
    • Viola
  • Team Projects
    • Scrapped
    • Robbin' Robin
  • Resume
  • About
  • Home
  • Individual Projects
    • Beat Detection
    • Tile-based Level Editor
    • Viola
  • Team Projects
    • Scrapped
    • Robbin' Robin
  • Resume
  • About

Picture
Build Download
Github Repo

Project Overview

Demonstration Video

Languages: C++
Development Time: 12 Weeks
  • Made using custom C++ engine and utilizes the FMOD library for handling audio.
  • The goal of the project was to detect "beats" in a given audio file and estimate beats-per-minute (BPM) in real time, then to apply this functionality to a simple game.
  • Implemented an existing algorithm that utilizes a Fast Fourier Transform on the audio data to calculate "sound energy" for each sub-band of audio data, then compare this energy value to a history of energy values to determine if there is a beat on that sub-band.

Beat Detection Program (With Commentary) from William Vennes on Vimeo.


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:
  1. Calculate  amplitude data from the transformed values (complex numbers).
  2. Use this data to calculate sound energy for each sub-band.
  3. 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​.
Picture
Transformed frequency data split into 32 sub-bands.

Calculating Sound Energies for Beat Detection

Step One
​Assuming 1024 samples…
  • B = Sound amplitude buffer
  • L = left speaker data
  • R = right speaker data
Picture
Step one of sound energy calculation
Step Two
​Next, we use B to find the instant energy values per sub-band
  • 1024 sample size
  • 32 sub-bands
  • E = instant energy buffer
Picture
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
  • 43 energy samples corresponds to roughly one second of music
  • A[ H[ i ] ] = Average sound energy history for sub-band i
Picture
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
  • C = threshold constant ~= 1.5 (varies per song)
Picture
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.
Picture
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.

Code Samples

  • BeatDetector.hpp
  • BeatDetector.cpp
  • Visualizer.hpp
  • Visualizer.cpp
  • TheGame.hpp
  • TheGame.cpp
  • Audio.hpp
  • Audio.cpp
<
>

Home

Individual Projects

Team Projects

Resume

About

Last Updated - 9/24/2019