A statistical approach to retrieval under user-dependent uncertainty in query-by-humming systems

Erdem Unal, Shrikanth S. Narayanan, Elaine ChewMultimedia Information Retrieval 2004 · DOI

TL;DR

This paper tackles the challenge of accurately retrieving songs from a database using hummed queries, which are inherently prone to user-dependent variations in pitch and rhythm. They propose a novel statistical approach that extracts "fingerprints" from characteristic local points of the hummed melody, rather than the entire sequence, to improve robustness against these uncertainties.

What Problem Does This Paper Address?

Content-based multimedia information retrieval (MIR) is a rapidly growing field, and one of its exciting frontiers is enabling natural human interactions with large music databases. Query-by-Humming (QBH) systems aim to allow users to search for songs by humming a melody. However, the primary hurdle for QBH systems is the significant uncertainty introduced by the user's performance. Unlike a perfectly played musical score, a hummed melody can vary considerably in pitch accuracy, timing, and even the presence of extraneous sounds. This user-dependent variability makes it difficult for systems to reliably match a hummed query to the original song in the database. Existing approaches often rely on coarse melodic contours or string matching, which can be brittle in the face of these uncertainties. This paper seeks to develop a more robust retrieval mechanism by statistically modeling and accounting for this inherent uncertainty.

Methods

The core of the proposed method involves several key steps:

  • Direct Transcription: The hummed audio is directly transcribed into pitch and duration symbols. This is achieved by first segmenting the humming into individual notes using energy, spectral, and pitch change features, followed by pitch extraction using Fourier transform techniques.
  • Relative Pitch and Duration Representation: Instead of absolute pitch values, the system focuses on relative pitch and duration changes between consecutive notes. This aligns with human perception, which often relies on intervals and relative timings rather than absolute values. Specifically, they calculate Relative Pitch Difference (RPD) and Relative Duration Difference (RDD).
  • Fingerprint Extraction: The novelty lies in extracting "fingerprints" from characteristic local points of the hummed melody. These points are identified based on musical composition aspects like fluctuating and monotonic note transitions, and repeated transition structures. Fingerprints are essentially small matrices capturing pitch and duration information around these salient local points. Different types of fingerprints are extracted, focusing on largest/smallest pitch transitions and largest/smallest duration changes.
  • Probabilistic Similarity Measures: The extracted fingerprints are then used to search a pre-processed music database. For each fingerprint, the system calculates the distance to corresponding segments in the database melodies. This distance is converted into probabilistic similarity measures.
  • Prediction Intervals for Search: To further handle uncertainty, Prediction Confidence Intervals (PCI) are built for pitch and duration transitions. These intervals help guide the search by defining acceptable ranges for transitions, preventing the system from being overly sensitive to minor deviations.
  • Overall Similarity Score: A final similarity measure for a candidate song is calculated as the product of the probabilities derived from each of its matching fingerprints. The songs with the highest similarity measures are returned as the most likely results.

Datasets

  • Humming Data: The system was tested using manually annotated humming samples. The paper mentions a dataset of 250 humming samples collected from subjects with varying musical backgrounds, building upon previous work that created a database of 100 humming samples from 100 individuals.
  • Music Database: A database of 200 pre-processed MIDI files was used for retrieval. This database included pieces used in their data collection experiments and songs from popular bands.

Key Insights and Ideas

  • Focusing on Local Salient Points: The idea of extracting "fingerprints" from characteristic local points (e.g., significant pitch changes, large duration shifts) rather than processing the entire hummed melody is a crucial insight. This approach is more robust to global timing errors or minor inaccuracies that might affect the entire sequence.
  • Embracing Uncertainty Statistically: The paper doesn't try to eliminate uncertainty but rather to model and account for it using probabilistic measures and prediction intervals. This data-driven approach acknowledges the inherent variability in human humming.
  • Relative Pitch and Duration are Key: The emphasis on relative pitch and duration changes aligns with human auditory perception and is a more effective representation for matching melodies across different keys and tempos.
  • Musical Training Matters: The results clearly demonstrate that musical training significantly impacts retrieval accuracy, highlighting the importance of understanding user expertise in system design.

Key Results

The proposed statistical approach demonstrated promising results:

  • Trained Subjects: Achieved a retrieval accuracy of 94 percent for subjects with musical training.
  • Untrained Subjects: Achieved 72 percent accuracy for subjects without musical training.
  • Fingerprint Effectiveness: The results suggest that extracting fingerprints with respect to characteristic local points is an effective and robust way for search and retrieval under uncertainty.
  • Effect of Fingerprint Length (k): Increasing the length of the information matrix (k) directly improved results for musically trained subjects, but this effect was non-monotonic for untrained subjects.

Limitations and Future Work

  • Database Size Impact: The paper notes that increasing the database size negatively affects retrieval accuracy, especially for non-trained subjects.
  • Automation of Preprocessing: The manual extraction of melodies from MIDI files for the database is a limitation. Future work aims to automate this preprocessing.
  • New Fingerprint Features: The authors plan to explore incorporating repeated pattern extraction as a new type of fingerprint.
  • Scaling and Query Formulation: Addressing scaling issues in terms of retrieval accuracy and improving query formulation are also identified as future research directions.

Summary updated

BibTeX
@inproceedings{unal2004statistical,
  author = {Erdem Unal and Shrikanth S. Narayanan and Elaine Chew},
  title = {{A statistical approach to retrieval under user-dependent uncertainty in query-by-humming systems}},
  booktitle = {Multimedia Information Retrieval},
  year = {2004},
  doi = {10.1145/1026711.1026731},
}
Figure