Key Detection Algorithm - Krumhansl-Schmuckler Algorithm
The algorithm used to detect key is the Krumhansl-Schmuckler key finding algorithm [5]. The input to this algorithm is a vector of 12 pitches and their duration in a song. The input is then compared to an ideal “key profile”. The "key profile" is a vector of 12 values, experimentally determined by Krumhansl-Schmuckler. There is a "key profile" for each of the 24 major and minor keys. As an example, the key profile for C major and C minor are shown in Fig. 1. To determine the key, a correlation coefficient between the input and each key profile is calculated. The key profile with the largest correlation coefficient to the input is taken as the key of the song.
Figure 1: C Major and C Minor key profile determine experimentally by Krumhansl-Schmuchkler [5]
The Krumhansl-Schmuckler algorithm, described above, was implemented in MATLAB. The first test of the algorithm was with a song snippet from Yankee Doodle which is known to be in G major. The frequency of each pitch in the song was manually recorded from the sheet music and input into the algorithm. The frequency of each pitch can be seen in Fig. 2. Downloading and running the MATLAB code from the link below demonstrates that the Krumhansl-Schmuckler algorithm can successfully determine the key of Yankee Doodle from the given input.
Figure 2: Frequency of each pitch in the song snippet of Yankee Doodle. [5]
Finally the algorithm was tested with pitch frequencies output from the HPS pitch detection algorithm. A sample of songs the algorithm was tested on, their known key, and the key that the Krumhansl-Schmuckler algorithm determined are shown in the table below. In general the algorithm has about 80% accuracy. It has some misclassification between major and minor keys because they have similar key profiles. Often the correct key is the second highest correlation coefficient. Additionally the algorithm fails on songs where we don't have a key profile for the mode it is in. For example, We Are the Kids is in a key of G Lydian. However, we do not have a key profile for G Lydian, only major and minor keys, so the algorithm fails.
Table 1: Output of the Krumhansl-Schmuckler Algorithm compared to the Key determined by listening
DSP Used in Krumhansl-Schmuckler Algorithm
A key feature of the Krumhansl-Schmuckler Algorithm is the calculation of the correlation coefficient between a song's pitch frequency and each key profile. The correlation coefficient calculation shown in Eq. 1 is actually the covariance of two vectors divided by the standard deviation of each of those vectors.
Eq 1: Correlation Coefficient Calculation
It can be shown that the covariance is an inner product, a DSP topic discussed in EECS 351. Starting with two vectors of n values where the mean of the values in each vector is defined as:
Eq 2: Mean of the vector [7]
Two new vectors can be defined as containing their original vectors values with their respective means subtracted from each term (shown in Eq 4). The sample variance is defined as the squared sum of each term in this vector. The sample standard deviation, sx, is the square root of the sample variance.
Eq 3: Variance of the vector [7]
Now a standardized version of the original vectors can be defined as:
Eq 4: Standardize the vector [7]
The correlation coefficient defined above can be found by taking the dot product of these two vectors and normalizing by 1/n [7].
Eq 5: Dot Product [7]
The dot product is the inner product of Euclidean space. The value rxy is a scaled and shifted version of the dot product of x and y. The dot product is linear, therefore this calculation meets properties to be an inner product. Those properties are (1) the self-inner product is positive and zero only if x is zero (2) The inner product is distributive (3) The inner product is commutative with conjugation and (4) When we scale one of the vectors, the inner product scales as:
Eq 6: How Inner Product Scales