A fast query by humming system based on notes

Jingzhou Yang, Jia Liu, Weiqiang ZhangInterspeech 2010 · DOI

Abstract

Query by Humming (QBH) systems allow users to search for music by singing or humming a melody. However, traditional frame-based methods often struggle with the computational overhead required for large-scale databases. This paper presents a high-speed QBH system developed by researchers at Tsinghua University that shifts from frame-by-frame analysis to a note-based approach. By utilizing two novel algorithms—Note-based Linear Scaling (NLS) and Note-based Recursive Align (NRA)—the system achieves a 96.1% Top-5 accuracy with a computation time of just 0.211 seconds, representing a 300-fold speedup over traditional Dynamic Time Warping (DTW) methods.

Introduction

The primary technical challenge in QBH is the "speed vs. accuracy" trade-off. High-accuracy systems typically rely on frame-based methods like DTW, which compare audio signals millisecond by millisecond. While precise, these methods are computationally expensive and difficult to scale. Conversely, note-based methods treat melodies as sequences of discrete notes, offering significant speed advantages but historically lower accuracy due to the difficulty of segmenting imperfect human humming. This research bridges that gap by introducing a robust note-based retrieval pipeline that models human singing errors.

Proposed System Architecture

The proposed system follows a structured pipeline designed to transform raw audio into a searchable note sequence. The process begins with humming input, which undergoes segmentation to extract pitch and duration data. This data is then compared against a melody database using a two-stage retrieval process.

System architecture of the proposed note-based QBH retrieval pipeline.

1. Pre-processing and Segmentation

To handle the inherent noise in human singing, such as consonants and pitch slides, the system uses time-domain autocorrelation for pitch tracking. A specialized weighting formula is applied during segmentation to de-emphasize the unstable beginning and end of notes, ensuring a cleaner representation of the intended melody.

2. Note-based Linear Scaling (NLS)

In the first retrieval stage, NLS performs a global search. It "stretches" or "compresses" the sequence of hummed notes to find the best fit against the MIDI database. By operating on notes rather than frames, the computational complexity is reduced from hundreds of operations to a handful of additions.

3. Note-based Recursive Align (NRA)

The second stage, NRA, provides a refined alignment. It uses a top-down recursive approach to divide the humming into segments and align them locally. This allows the system to account for non-linear tempo variations—such as a user speeding up or slowing down mid-melody—which global scaling might miss.

Alignment between a humming query and a target song melody using note-based segments.

Modeling Human Error

A key innovation of this system is its integration of "human-centric" heuristic enhancements. The researchers recognized that amateur humming contains predictable errors. To mitigate these, the system employs:

  • Pitch Regulation: Normalizing the starting pitch to accommodate different vocal ranges.
  • Temporal Weighting: Assigning lower weight to the start of a query, where users are statistically more likely to be out of tune.
  • Interval Weighting: De-emphasizing large pitch jumps, where human accuracy typically declines.

Experimental Results

The system was evaluated using the QBSH corpus, consisting of 2,797 audio clips and a 1,000-song MIDI database. Tests were conducted on a modest 1.6 GHz single-core CPU to highlight the algorithm's efficiency.

Algorithm Top-5 Accuracy Computation Time (s)
EMD (Earth Mover's Distance) 78.3% 4.980
NLS (Stage 1 only) 80.5% 0.044
DTW (Frame-based) 95.0% 69.432
NLS + NRA (Proposed) 96.1% 0.211

The combined NLS + NRA approach not only outperformed the frame-based DTW in accuracy but did so while being over 300 times faster.

Conclusion

By abstracting audio into notes and applying recursive alignment, this system demonstrates that note-based QBH can achieve state-of-the-art accuracy with minimal computational cost. While the system remains dependent on the initial quality of pitch tracking, its ability to model human error makes it a robust solution for real-time music retrieval. Future research will focus on refining segmentation for even noisier environments and testing the system against industrial-scale databases.

Summary updated

BibTeX
@inproceedings{yang2010fast,
  author = {Jingzhou Yang and Jia Liu and Weiqiang Zhang},
  title = {{A fast query by humming system based on notes}},
  booktitle = {Interspeech},
  year = {2010},
  doi = {10.21437/interspeech.2010-753},
}
Figure