MATLAB - Autocorrelation Project

[ElijahRockers]

I'm trying to design a program that can accurately detect the frequency of a real, periodic audio signal, such as several guitar notes in sequence.

I have the skeleton of the program working. It does, at times, accurately detect the frequency. However, it is very noisy, and I'm not too sure how to fix it. I believe it is an issue with how I'm finding the period of the auto-correlations.

Right now I (try to) search for the second peak of the auto correlation by ignoring the first, initial peak, then finding the next local max. (By definition, greater than the two values before and after it).

I'm not too concerned with the floor noise right now, as I don't think that's my problem.

If anyone has any suggestions on how to improve the quality/readability of the program, I would greatly appreciate it.

The image is a graph of me running up then back down the G Major scale on an acoustic guitar.

As you can see, it KINDA works. The first two and last three notes are correct, but the notes in between have issues.

Link to code:
https://gist.github.com/elijahrockers/1e9f1ece4fcc546d756b

 

[lewando]

Before diving into your code-- a couple of thoughts:

1) Multitones can cause havoc of you are trying to resolve a single tone.
2) May want to test with a frequency synthesizer instead of a guitar, at first--purer singular tones.
3) You may need to employ a volume threshold detector to eliminate the low-level results (0-0.1s, 2.25s - 2.6s).
4) Related to 3--what do you want to report when there is no signal?

 

[ElijahRockers]

First, thank you for replying!

I understand the idea of the volume threshold. That's kinda a secondary aspect, since I don't expect much trouble with that. Also, I tested the code with periodic signals of my own design when I was beginning the process, and it helped me develop the current code.

The real problem is that there is SO much data involved that it's difficult to manually analyze it and figure out where the problem is. I guess I was just hoping somebody with signal analysis experience would be able to tell me what I need to improve upon. Or at least tell me the best way to go about troubleshooting this much data. This is the first time I've ever worked with this much data.

As far as point 1) goes...the third and seventh note of the signal are the same note. And the third note is noisy, while the seventh note seems to be accurate. When you say multitones, I'm assuming you mean harmonics. Is that what's giving me problems?

Also, what I want to report when there is no signal is kinda secondary... I can cross that bridge when I come to it, and honestly I feel like that shouldn't be too much of a problem, using the energy of the signal.

 

[marcusl]

You might consider an alternate approach, maybe something like this:
1. Take the FFT of the autocorrelation. This is (with proper scaling) the power spectrum.
To be meaningful, you really need the power spectrum of each note separately, however. You could
2. First pass the data through an envelope detector (an absolute value rectifier or square-law followed by a low-pass filter).
3. Pass through a high pass filter or differentiator, and compare to a threshold to identify the beginning of each note.
3. Take the original data for a given time after the rising edge of the envelope of the first note (or you could take data, say, for 50% of the time before the next note).
4. Take the power spectrum (autocorrelation and FFT) of this sequence. Repeat #3-4 for each note.

A couple of notes:
A) An alternate method of finding the power spectrum is to take the FFT of the data, then its absolute value squared. This will run faster than finding autocorrelations.
B) Spectral analysis is actually surprisingly complex and subtle. I have given you fairly crude procedures that will get you started. There are many extensions--the use of windows for the FFT, or the use of models (since you know you have a vibrating string) to get more accurate spectra.
C) You will find that even a single note from guitar has a rich spectrum--there are harmonics, and with electric guitars, feedback and distortion. Harmonics die away with differing time scales so the spectrum at the beginning of a note is different than after the note has sounded a while. You can probably hear the difference with your ear if you're an experienced player.

 

[ElijahRockers]

Thanks. My teacher is the one who recommended the auto correlation approach, but I will bring up the FFT approach to see what he thinks about it. I might need a quick refresher on this stuff anyway.

 

[lewando]

1) You method is sound, I wouldn't abandon it quite yet.

2) I see you are trying to "roll your own" autocorrelator, which would be fine if everything else would only work! MATLAB provides a function, xcorr, which is well wrung-out. I suggest you try it, at least it would simplify your code.

3) I don't understand why you need both an x1 and an x2 (your window of data to process). Doing an autocorrelation on x1 should suffice. I think the problem is associated with how you are determining the maximum value of the autocorrelation output (excluding the central peak).

4) Use MATLAB to generate a synthetic scale-run waveform using pure tones--keeping things simple--to rule out any distortion/harmonic-based causes.

5) Some debugging thoughts:
--You literally need to pause the program (use the pause statement) to step through the results of each processed window to see what is going on. Insert plot statements and remove the ';' at the end of an assignment statement to get visibility of things before each pause.
--Try using the debugger, using breakpoints, etc.

I will continue to try to isolate the exact problem with your code, but I am convinced it could be made to work by considering points 2) and 3).

 

[marcusl]

1) You method is sound, I wouldn't abandon it quite yet.

I'm not convinced. Am I correct that you are computing the autocorrelation of the entire data sequence found in your first graph? If so, then you are summing the convolution of many tones at different frequencies against each other as one copy of the sequence slides along the other. When you do this with just two tones of different frequencies, you get sum and difference frequencies--and beats. Your frequency estimator will show a lot of structure. With a string of tones, you get lots of beats and a general mess. Add in harmonics and the picture gets worse. I believe that this is the cause of the "noisyness" that you mention--it is not noise at all, but rather chaotic output that I just described. It also helps explain why the end notes are better than the middle where you are, indeed, convolving multiple tones.

The solution is to analyze one tone at a time, either with your autocorrelation or with an FFT. This is what I proposed above.

 

[ElijahRockers]

2) I see you are trying to "roll your own" autocorrelator, which would be fine if everything else would only work! MATLAB provides a function, xcorr, which is well wrung-out. I suggest you try it, at least it would simplify your code.

3) I don't understand why you need both an x1 and an x2 (your window of data to process). Doing an autocorrelation on x1 should suffice. I think the problem is associated with how you are determining the maximum value of the autocorrelation output (excluding the central peak).

Yes. I have the intention of rolling this out to an Android based system if I can get it working correctly by the end of the summer. My prof had suggested I use the built in xcorr function, but by the time he mentioned it I had already written the auto-correlation code. I will try that to make sure it's not the way I'm doing the autocorrelation, though I'm fairly certain it's correct. That is one thing I have been able to check the data for and it seems to work in every case I've checked.

The reason I have x1 and x2 is just because I'm doing the autocorrelation manually. I correlate x1 against itself, then one of them gets shifted to the right by one sample, rinse and repeat until max_lag is reached. Then, x1 and x2 start again immediately at the end of the previous autocorrelation. It's kind of hard to explain in words, but it makes sense on a graph. Although it looks like x2 is the window that is shifting, mathematically it's actually x1 that is 'shifting'.

I'm not convinced. Am I correct that you are computing the autocorrelation of the entire data sequence found in your first graph? If so, then you are summing the convolution of many tones at different frequencies against each other as one copy of the sequence slides along the other. When you do this with just two tones of different frequencies, you get sum and difference frequencies--and beats. Your frequency estimator will show a lot of structure. With a string of tones, you get lots of beats and a general mess. Add in harmonics and the picture gets worse. I believe that this is the cause of the "noisyness" that you mention--it is not noise at all, but rather chaotic output that I just described. It also helps explain why the end notes are better than the middle where you are, indeed, convolving multiple tones.

The solution is to analyze one tone at a time, either with your autocorrelation or with an FFT. This is what I proposed above.

Negative. I am computing the autocorrelation of 2000 sample windows, a relatively small window, considering the data I'm analyzing has an enormous amount of samples (the audio shown has approximately 1.2 million). Then for each of these, I try to calculate the frequency, and that's what goes into the frequency graph.

'r' is a matrix of the various autocorrelation functions that are calculated in sequence.

 

[lewando]

Am I correct that you are computing the autocorrelation of the entire data sequence found in your first graph?

It looks like what he is trying to do is take a small, sliding time segment (where there are multiple segments available for processing for a given note duration), doing an autocorrelation on that segment, estimating the frequency of that segment, storing that frequency data point, then moving on to the next segment, repeating until the full time series has been processed.

The solution is to analyze one tone at a time, either with your autocorrelation or with an FFT. This is what I proposed above.

This is what it looks like he is doing, except he's getting multiple frequency estimates per tone. If a segment contains a transition from one tone to the next, that estimate will be not be the best. Agree that distortions/noise/harmonics of a real signal aren't helping the debug process. This should be made to work using pure tones. A single tone throughout the waveform, in fact, would be telling. Do a run with a "working tone" and another with one that results in a reported wrong frequency.

 

[ElijahRockers]

A single tone throughout the waveform, in fact, would be telling. Do a run with a "working tone" and another with one that results in a reported wrong frequency.

I agree... is there a function for this in matlab? If not I have a synthesizer, and I should be able to record a relatively clean sine wave... perhaps even the same notes I played on the guitar.

 

[lewando]

You should be able to do it with:

t=0:1/sample_rate:2; (2 seconds)
tone = sin(f_tone*2*pi*t);

If you get a chance, can you post a link to your .wav file?

 

[ElijahRockers]

G Major.wav is the one shown in the graphs previously.

low E.wav is one that, if I recall correctly, is a single note that is not working properly. For most of the analysis it detects the wrong frequency, though there is one point in the middle where it detects the correct frequency for a very brief moment. low E should be around 89Hz.

I will be working on material for another class for a good part of today, but I will definitely try to get the ideal tones to put through the system.

Thanks a million for your help, both of you!

 

[ElijahRockers]

You should be able to do it with:

t=0:1/sample_rate:2; (2 seconds)
tone = sin(f_tone*2*pi*t);

If you get a chance, can you post a link to your .wav file?

What is f_tone ? I am trying to get this to work, but I'm having trouble. Thanks.

EDIT: Derp, nvm I figured it out.

 

[ElijahRockers]

Alright... I was able to work on it a bit tonight. I made a variable energy_threshold that could sort of detect when there was a note being played, based on the total energy. I set the frequency to 1Hz whenever there was no note being played. (1Hz is not a meaningful frequency concerning guitars.)

It seemed to work ok at first. I started getting major problems with the tone generator and the built in xcorr function. I was trying to read the help page on xcorr but it was very confusing, as far as trying to get it to do what I did manually. I think my method will work anyway...

As for the tone generator, I could pretty accurately map the frequency of tones between 85hz and 150hz... anything outside of that range didn't seem to work so well. It seemed if I tweaked min_lag and max_lag I could expand the range of frequencies I could detect, but I don't think I should do that because those values are based off the highest and lowest (respectively) frequencies my guitar makes.

 

[lewando]

If you have 2 cases where one frequency works and a slightly different one does not, by taking a snapshot of your variables for both cases and comparing them, this will provide insight.

 

[lewando]

I had a chance to look at things in more detail and run your code. These are my notes:

Running with a pure tone of 155Hz works, 165, does not. What seems to be happening is that at 155Hz, r(i,:) your autocorrelation output, looks like 155Hz_R.bmp and at 155Hz, r(i,:) looks like 165Hz_R.bmp.

Your autocorrelation appears periodic with more or less constant amplitude peaks that compete for the maximum. Auto correlations normally trail off from the central peak (when your program stops, type "plot(xcorr(x1))" in your command window and you will see what I mean).

If you are spanning several octaves this will be a problem, and makes a case for using xcorr.

For now, if limit your octaves with min_lag and max_lag and you will see an improvement on your .wav file.

But not much. That signal is pretty far from pure tones. Try lowpass or bandpass filtering your x data before processing it.

 

[ElijahRockers]

Running with a pure tone of 155Hz works, 165, does not. What seems to be happening is that at 155Hz, r(i,:) your autocorrelation output, looks like 155Hz_R.bmp and at 155Hz, r(i,:) looks like 165Hz_R.bmp.

Are there supposed to be links to pictures there? Anyway, I noticed that I was able to detect the pure tone frequencies in a range from 80Hz to 160Hz. 70Hz shot up to a result of 1000Hz, whereas anything over 160Hz, tended to result in half the actual frequency. Ex: 170Hz pure tone resulted in frequency detection of 85Hz.

Your autocorrelation appears periodic with more or less constant amplitude peaks that compete for the maximum. Auto correlations normally trail off from the central peak (when your program stops, type "plot(xcorr(x1))" in your command window and you will see what I mean).

I typed that in but I'm not really sure what I'm looking at. I see what looks like the contour of a symmetric mountain. From what I understand, the autocorrelation should be a smoothed-out periodic waveform with the same period as the original. Since the first value in the AC is a max, then the distance to the next max should be the period, right? That's what my program is assuming.

If you are spanning several octaves this will be a problem, and makes a case for using xcorr.
For now, if limit your octaves with min_lag and max_lag and you will see an improvement on your .wav file.
But not much. That signal is pretty far from pure tones. Try lowpass or bandpass filtering your x data before processing it.

Well, I really just used that guitar sample because I needed something to process. It's clear now that I need to get this thing to operate correctly on a pure tone before moving on to guitar tones.
The values I chose for min/max_lag are based on the highest/lowest frequency notes my guitar can produce.

 

[lewando]

Yes, sorry, pictures were supposed to be included.
Here:
155Hz r(i,:)-- http://i1209.photobucket.com/albums/cc398/lewando/155Hz_R_zps971e0c06.png
165Hz r(i,:)-- http://i1209.photobucket.com/albums/cc398/lewando/165Hz_R_zps4a664ed4.png

xcorr(x1) of a 165Hz tone--
http://i1209.photobucket.com/albums/cc398/lewando/xcorrx1_zpsdb3611f2.png

xcorr(x1) same as above but "normalized" and truncated--
http://i1209.photobucket.com/albums/cc398/lewando/xcorrx1_norm_zpse5a447a1.png

So the above "normalized and truncated" image is the second half (descending part) of xcorr(x1) limited to 1:max_lag and as you can see, that problematic second peak is diminished. The central peak still stands and has not been clipped by min_lag yet.

 

[ElijahRockers]

Alright I have implented a new method for determining the frequency. This one is much more accurate. I attached the code. It seems to work pretty well for the most part. I applied a median filter to the output, to further clean it up..

Now, I need to figure out a way to distinguish between the same note on two different strings. The 6th fret on the 'Low E' string i the same frequency as the 1st fret on the 'A' string, but I need a way to differentiate.

Proposed methods are, slightly detuning each string, and measuring the distance between measured frequency and expected frequency. These differences could be used to determine which string is being plucked. He also mentioned something about harmonics, which I didn't fully understand.

I welcome anyone that has any ideas on how to clean up the code, or any tips on the above procedure!

Thanks :)

 

[lewando]

If this is a guitar-specific application, (as I suspect with "tab"-ber being the clue), you could use neighboring pitches to establish the string-fret that minimizes hand motion or somehow makes the most sense.