# Detect song changes in audio stream

I have a stream of music that I'm reading(from a microphone, from an online streaming source or whatever). And I want to have a system that will detect when a song changes.

The question is, is this possible with any kind of accuracy?(even something 75% rate of detection would be helpful).

Alternatively, would it be possible to detect large enough changes in the music(so it might be a song change but it could just be a switch from a verse to chorus or chorus to bridge, etc...).

I am not asking for an exact algorithm -- though obviously if you know one then I obviously wouldn't mind -- but even a general approach on how to tackle such a problem would be helpful.

All pointers welcome, scientific papers, open source projects, some random guy's blog, whatever.

-
You could detect the key, tempo, etc. The problem is that all of these things sometimes change within songs. –  Jim Clay Feb 26 '13 at 19:55
That's true, which is why I said that I would settle for detecting large changes within a single song. –  entropy Feb 26 '13 at 20:07

The very first thing to try would be to implement a rough speech/music classifier to detect a radio host/DJ; and to extract the amplitude envelope to detect fade outs and fade ins.

Once you have implemented that and/or if this doesn't solve your problem because your stream is continuous (DJ-style mix), you'll certainly run into the song boundary / song section boundary ambiguity - but if this is not a problem to you then there are solutions. What you are looking for is known in the academic community as unsupervised audio stream segmentation" - with a variety of techniques proposed over the years. You have to decide on two ingredients: which audio features to extract from the audio stream; and which statistical analysis method to use to detect changes/structure.

Regarding the features, the consensus is on a combinations of the following:

• MFCC (which carry timbre/instrumentation information)
• Chroma (which carry key/chord information)
• Loudness
• Tempo or other measures of rhythm (beat histogram, Pampalk's fluctuation patterns, etc.)

Very frequently, an algorithm can be repurposed just by a change of features... For example, there are papers on musicological analysis of piano music which will not use MFCC (same timbre throughout the piece), or papers on pop song structure analysis which will not use tempo (assumed to be constant throughout the piece, so not informative) - but the methods they describe could very well work for you if you decide to include other features - so don't be narrow when looking for literature.

Regarding the statistical analysis methods, the usual suspects are:

1. Computation of a self-similarity matrix, and "checkerboard" filter to detect blocks. The classic paper is by Foote, "Automatic Audio Segmentation Using A Measure of Audio Novelty". Foote's novelty detection function can be computed online and incrementally - over a buffer of past audio frames.

2. Hidden Markov models, used in an unsupervised way. You hope that the HMM states will map well into segments (Peeters and Rodet, "Music Structure Discovering Using Dynamic Audio Features for Audio Summary Generation: Sequence and State Approach"), or you overestimate the number of HMM states and look for changes in the HMM state distribution within small windows (Levy and Sandler, "Structural Segmentation of Musical Audio by Constrained Clustering"). These methods are more geared towards offline processing, and situations in which you have an idea in advance of how many segments you want to identify.

3. "Streaming" change detection methods. The principle is to split the past $N$ frames of audio into two $N/2$ frames blocks $S_1$ and $S_2$, and to perform a statistical test to decide which of the hypotheses "Frames from $S_1$ and $S_2$ are drawn from the same distribution $P$" and "Frames from $S_1$ and $S_2$ are drawn from a different distribution $P_1$ and $P_2$" is the most likely. Big peaks or dips in the test outcome indicate that the middle of the block is a segment change. There are a number of information criteria used to weigh the two hypotheses, such as the BIC (Classic paper: "Unsupervised Audio Stream Segmentation And Clustering Via The Bayesian Information Criterion" by Zhou). The limitation here is that you usually have little data to perform the test, and the data has weird-looking distributions. See the section 2.2 of Gillet et al's "Comparing audio and video segmentations for music videos indexing" for a few pointers on kernel methods that overcome these limitations.

For a real-life application (indexing of radio streams), see for example Ramona's "Combined supervised and unsupervised approaches for automatic segmentation of radiophonic audio streams" - this work combined the kind of unsupervised section detectors discussed here to a supervised speech/music classifier (to tackle the most obvious part of the problem).

-
this is why I love stack exchange :) Thank you for the information. I'll be looking into it over the next few days. This provides a very good starting point. –  entropy Feb 26 '13 at 22:21
PS: What I'm looking at is mainly DJ-style mixes. I'm trying to build something that dances to music. I've already got the beat-tracking/prediction part down(which is why I specifically said that papers are good because that's where most of the practical info for that part was found). For that I ended up going with a system based on spectral flux detection for onsets and a heuristic that maps onsets to beats online. –  entropy Feb 26 '13 at 22:25

I think your best bet is some combination of key and tempo detection. There are a number of threads that discuss how to determine a note's pitch (see here), so I won't get into that. Key detection should simply be an expansion of pitch detection. You determine the pitch of the notes and find the key that matches. You could also use information like that the primary, third, and fifth notes will tend to be more common than the others.

If you started seeing notes that didn't fit the key, there might have been a key change. You could see if the new set of notes match a different key. You could also use the fact that some key changes are more likely than others.

The other characteristic to use is tempo. This is simply how quickly the notes come. Some notes, of course, will be held longer than others (eighth notes, quarter notes, half notes, full notes, etc.), but they should have a primary period. A change in that primary period could indicate a song change.

-