Find the most dominant frequency using FFT in Rust

on May 26, 2024

Introduction

In this post, we’ll explore how to determine the most dominant frequency present in an audio sample using Rust and FFT.

What is FFT?

FFT (Fast Fourier Transform) is an algorithm that computes the discrete Fourier transform (DFT) and its inverse. It transforms a signal from its original time domain to a representation in the frequency domain. This is crucial for analyzing the frequency components of audio signals.

Why Rust?

Rust is ideal for this task because of its performance and safety. Unlike Java, Rust has zero-cost abstractions and doesn’t rely on a garbage collector, making it faster and more efficient for real-time audio processing.

Setting Up the Test Bed

First, let’s set up the test bed to generate audio samples of a pure sine wave of amplitude 1. Add the following dependencies to your Cargo.toml file:

cargo.toml

[package]
name = "fft_to_note"
version = "0.1.0"
edition = "2021"
 
[dependencies]
lazy_static = "1.4.0"
atomic_float = "0.1"
rustfft = "6.1.0"

Test Case to Determine Frequency Using FFT

Let’s write an easy to understand generate_sine_wave function which creates a vector of f32 numbers representing a sine wave of specific length, frequency and amplitude.

lib.rs

use std::f32::consts::PI;
 
mod frequency;
 
fn generate_sine_wave(samples: usize, frequency: f32, sample_rate: f32) -> Vec<f32> {
    let mut wave = Vec::with_capacity(samples);
    for i in 0..samples {
        let sample = (i as f32 * frequency * 2.0 * PI / sample_rate).sin();
        wave.push(sample);
    }
    wave
}

Let’s now add a test case to lib.rs for calculating the most dominant frequency.

lib.rs

use std::f32::consts::PI;
 
mod frequency;
 
fn generate_sine_wave(samples: usize, frequency: f32, sample_rate: f32) -> Vec<f32> {
    let mut wave = Vec::with_capacity(samples);
    for i in 0..samples {
        let sample = (i as f32 * frequency * 2.0 * PI / sample_rate).sin();
        wave.push(sample);
    }
    wave
}
 
#[cfg(test)]
mod tests {
    use super::*;
    use frequency::{fft_to_frequency, fft_to_musical_note};
 
    #[test]
    fn test_generate_sine_wave() {
        let sample_rate = 44100.0;
        let frequency_440 = 440.0;
        let frequency_880 = 880.0;
        let samples = 4096;
 
        let sine_wave_440 = generate_sine_wave(samples, frequency_440, sample_rate);
        let sine_wave_880 = generate_sine_wave(samples, frequency_880, sample_rate);
 
        assert_eq!(fft_to_musical_note(sine_wave_440.as_ref(), 1.0).name, "A4");
        assert_eq!(fft_to_musical_note(sine_wave_880.as_ref(), 1.0).name, "A5");
    }
}

Introduction to `rustfft` Dependency

rustfft is a highly efficient FFT library in Rust that provides an easy-to-use API for performing Fast Fourier Transforms. The library is designed to handle both complex and real-valued inputs, making it ideal for audio signal processing. For our use case, we’ll use rustfft to analyze audio samples and determine the dominant frequency.

How `rustfft` Works

The rustfft library simplifies the process of performing FFT by providing a planner that generates FFT plans. These plans optimize the transformation process, ensuring that the FFT is performed as efficiently as possible. The main API we will use includes:

FftPlanner: Used to create FFT plans.
Fft::process: Executes the FFT on an array of complex numbers.

These components allow us to convert time-domain audio samples into the frequency domain, where we can then identify the most dominant frequency. By leveraging Rust’s performance, we can execute these transformations quickly and efficiently, outperforming languages like Java that rely on garbage collection and may have higher latency for real-time processing tasks.

Let’s see how to use these in frequency.rs below which we have defined as a module in our lib.rs. Let’s also speed up the calculation of western musical note name using binary search and precomputed list of frequencies of all notes within octaves.

frequency.rs

use std::{collections::HashMap, sync::Arc};
use lazy_static::lazy_static;
use rustfft::{num_complex::{Complex, ComplexFloat}, Fft, FftPlanner};
 
const SAMPLE_RATE: i32 = 44100;
const BUFFER_SIZE: i32 = 4096;
 
lazy_static! {
    pub static ref NOTES_FREQ: [f32; 132] = {
        let a4_freq = 440.0;
        let mut notes_freqs = [0.0; 132];
        let distance_c0_from_a4 = 57.0;
        notes_freqs[0] = a4_freq / 2.0f32.powf(distance_c0_from_a4 / 12.0);
 
        for i in 1..notes_freqs.len() {
            notes_freqs[i] = notes_freqs[i - 1] * 2.0f32.powf(1.0 / 12.0)
        }
 
        notes_freqs
    };
 
    static ref NOTE_OFFSETS: HashMap<i16, &'static str> = [
        (0, "C"),
        (1, "C#"),
        (2, "D"),
        (3, "D#"),
        (4, "E"),
        (5, "F"),
        (6, "F#"),
        (7, "G"),
        (8, "G#"),
        (9, "A"),
        (10, "A#"),
        (11, "B"),
    ]
    .iter()
    .cloned()
    .collect();
 
    static ref FFT_PLANNER: Arc<dyn Fft<f32>> = {
        FftPlanner::new().plan_fft(BUFFER_SIZE as usize, rustfft::FftDirection::Forward)
    };
}
 
pub fn fft_to_frequency(frames: &[f32], amplitude: f32) -> f32 {
    let fft = FFT_PLANNER.clone();
 
    let mut complex_output: Vec<Complex<f32>> = frames
        .iter()
        .map(|&x| Complex::new(x, 0.0))
        .collect();
    fft.process(&mut complex_output);
 
    let sample_rate = SAMPLE_RATE;
    let length = frames.len();
 
    let mut max_idx = 0;
    let mut magnitude = f32::MIN;
    for i in 0..length / 2 {
        let val = complex_output[i].abs();
        if val > magnitude {
            magnitude = val;
            max_idx = i;
        }
    }
 
    let frequency = max_idx as f32 * sample_rate as f32 / length as f32;
    frequency
}
 
pub fn fft_to_musical_note(frames: &[f32], amplitude: f32) -> Note {
    let freq = fft_to_frequency(frames, amplitude);
    calculate_note(freq, amplitude)
}
 
#[derive(Debug)]
pub struct Note {
    pub name: String,
    pub deviation_cents: f32,
    pub amplitude: f32,
}
 
fn get_deviation_cents(frequency: f32, target_frequency: f32) -> f32 {
    1200.0 * (frequency / target_frequency).log2()
}
 
fn find_closest(arr: &[f32], n: usize, target: f32) -> (f32, usize) {
    if target <= arr[0] {
        return (arr[0], 0);
    }
    if target >= arr[n - 1] {
        return (arr[n - 1], n - 1);
    }
 
    let mut i = 0;
    let mut j = n;
    let mut mid = 0;
    while i < j {
        mid = (i + j) / 2;
        if arr[mid] == target {
            return (arr[mid], mid);
        }
        if target < arr[mid] {
            if mid > 0 && target > arr[mid - 1] {
                return get_closest(arr, mid - 1, mid, target);
            }
            j = mid;
        } else {
            if mid < n - 1 && target < arr[mid + 1] {
                return get_closest(arr, mid, mid + 1, target);
            }
            i = mid + 1;
        }
    }
    (arr[mid], mid)
}
 
fn get_closest(arr: &[f32], i: usize, j: usize, target: f32) -> (f32, usize) {
    if target - arr[i] >= arr[j] - target {
        (arr[j], j)
    } else {
        (arr[i], i)
    }
}
 
fn calculate_note(frequency: f32, amplitude: f32) -> Note {
    let (closest, closest_idx) = find_closest(NOTES_FREQ.as_slice(), NOTES_FREQ.len(), frequency);
    let note = get_note(
        frequency,
        amplitude,
        closest,
        closest_idx as i16,
    );
 
    note
}
 
fn get_note(
    frequency: f32,
    amplitude: f32,
    closest: f32,
    closest_idx: i16,
) -> Note {
    
    let idx_offset = closest_idx % 12;
    let note_name = NOTE_OFFSETS.get(&idx_offset).unwrap();
 
    let octave_num: i16 = closest_idx / 12;
 
    Note {
        name: format!("{}{}", note_name, octave_num.to_string()),
        deviation_cents: get_deviation_cents(frequency, closest),
        amplitude,
    }
}
 
#[cfg(test)]
mod tests {
    use super::*;
 
    #[test]
    fn should_calculate_nearest_note_for_frequency() {
        let mut frequency = 440.0;
        let amplitude = 1.0;
        let mut note = calculate_note(frequency, amplitude);
        assert_eq!(note.name, "A4");
 
        frequency = 880.0;
        note = calculate_note(frequency, amplitude);
        assert_eq!(note.name, "A5");
 
        frequency = 16.0;
        note = calculate_note(frequency, amplitude);
        assert_eq!(note.name, "C0");
    }
}

The find_closest function is used to find the nearest known frequency to a target frequency from a sorted array of frequencies using binary search. Binary search is efficient, operating in O(log n) time complexity, which makes it ideal for quickly narrowing down the closest frequency.

The function compares the target frequency to the middle element of the array, recursively adjusting the search range based on whether the target is higher or lower, until the closest match is found. By doing this, find_closest efficiently identifies the nearest frequency, crucial for accurately mapping a detected frequency to a musical note.

Code Explanation

`lib.rs`

generate_sine_wave: Generates a sine wave of specified frequency, sample rate, and length.
Test case test_generate_sine_wave: Generates a sine wave and checks if the FFT correctly identifies the frequency.

`frequency.rs`

NOTES_FREQ: Array storing frequencies of musical notes. Helps in quickly converting frequency to note.
FFT_PLANNER: Planner for FFT computation.
Note: Struct representing a musical note.
get_deviation_cents: Calculates deviation in cents between two frequencies.
find_closest and get_closest: Find the closest frequency in an array using binary search.
calculate_note and get_note: Calculate the musical note from a frequency.
fft_to_frequency: Performs FFT on an audio sample to find the dominant frequency.
fft_to_musical_note: Converts the dominant frequency to a musical note.

Conclusion

We’ve seen how to generate a sine wave, apply FFT to find the dominant frequency, and convert that frequency to a musical note using Rust. Rust’s performance makes it ideal for real-time audio processing

More about me

LaWiz Android Oboe with Rust and React Native

Introduction

What is FFT?

Why Rust?

Setting Up the Test Bed

Test Case to Determine Frequency Using FFT

Introduction to `rustfft` Dependency

How `rustfft` Works

`FftPlanner`: Used to create FFT plans.

`Fft::process`: Executes the FFT on an array of complex numbers.

Code Explanation

`lib.rs`

`frequency.rs`

Conclusion

Introduction

What is FFT?

Why Rust?

Setting Up the Test Bed

Test Case to Determine Frequency Using FFT

Introduction to rustfft Dependency

How rustfft Works

FftPlanner: Used to create FFT plans.

Fft::process: Executes the FFT on an array of complex numbers.

Code Explanation

lib.rs

frequency.rs

Conclusion

Introduction to `rustfft` Dependency

How `rustfft` Works

`FftPlanner`: Used to create FFT plans.

`Fft::process`: Executes the FFT on an array of complex numbers.

`lib.rs`

`frequency.rs`