0
$\begingroup$

I have two audio files that have mostly identical* content, most of which is just people talking. A typical example would be two files, each approximately an hour long, in which ~55 minutes of the total ~60 minutes are the same content (2-4 people talking), with the other 5 minutes of different content interspersed throughout.

I'm trying to pinpoint all the relevant offsets of the two files where the identical content lines up. So it should output something like this:

File 1 Start File 2 Start Duration
00:11 03:27 12:11
14:02 17:55 39:03
56:43 58:21 0:49

I started with effectively zero knowledge of how digital audio works and have spent the past week or more reading just about every DSP post, blog post, etc. I could find on this topic.

Now I know how to do a Fast Fourier Transform and wrote a Ruby script (after a bit of trial and error, I'm currently using audio sample rates of 11025 Hz and window sizes of 1024 samples each) to compare the two files' FFT output arrays (using the peak frequency from each bin as the array elements to compare) to try to find the offsets where the two audio files' contents match each other.

So far, the script works just well enough to indicate I'm on the right track, but nowhere near production-level performance. For example, it will find something like 30 seconds in common between the two one-hour files in total, even though in reality it should be more like 55 minutes. (It also will find 1-2 dozen other portions in common, but they're all about 1 second in duration or less, so I suspect it's just pauses between people speaking.) When I check the offsets for that 30 seconds, they do line up. The problem is just that it's not finding the vast majority of the content that's identical.

So I'm feeling a bit stuck. It feels like I must be missing something obvious, as my problem is significantly less complicated than, say, the Shazam use case. I can't figure out why my peak frequencies aren't lining up better.

  • Should I be using overlaps between my sample windows?
  • Do I need to use some kind of windowing function and, if so, which one?
  • Is there some additional calculation I should be applying to the FFT output (other than / in addition to sqrt(real**2 + imaginary**2) that's better optimized for human voices?
  • Should I be capturing (and then comparing) the top, say, 2 or 3 peak frequencies per window rather than just the top 1?

Any pointers at all would be helpful. Thank you!

* I'm using "identical" in layman's terms here, as I don't know if the files necessarily match up perfectly, e.g. individual bytes of the files being exactly the same. The point is any differences in the audio are completely imperceptible to humans: there's no background noise in one vs. the other, etc. In other words, this is not a Shazam type use case where a fuzzy recording from a bar is being matched against a real music file.

$\endgroup$
6
  • $\begingroup$ Hello jayp and welcome to DSP SE. The problem you are trying to tackle seems quite more involved that what you present it to me. IMO, without having done any experiments though, one frequency peak is way to little information to base your "matching". I believe you should at least use more peaks or even try to use some kind of error/deviation criterion on top of that (or alone) like the well used (vector) $L_{2}$ on the spectrum differences. Most often than not, using a window is beneficial to the STFT (which you seem to be using), the choice of which depends on many factors (cont.) $\endgroup$
    – ZaellixA
    Apr 25 at 9:06
  • $\begingroup$ I am not sure overlap is very important here but I may be wrong... You should do some testing. I don't think that any transformation to the spectrum could yield more information but I may be wrong on this one too... You can (and should) also try this out too. Finally, using some kind of "correlation" metric could prove to be beneficial. A simple one you could try would be the coherence between the two signals and see if you get any high values, which should correspond to "similar" signals. Please note that these are simple speculations on an empirical approach that should be tested first. $\endgroup$
    – ZaellixA
    Apr 25 at 9:10
  • $\begingroup$ Thank you @ZaellixA. Is the 𝐿2 approach different than the calculation I indicated above (sqrt(real**2 + imaginary**2))? From basic googling it looks the same but I may be missing something. Also, if one peak per bin is too few, is there a best practice for determining how many frequencies to match against per bin? 3? 10? etc. It seems likely that matching will get even worse if I keep adding more frequency bins. $\endgroup$
    – jayp
    Apr 25 at 14:23
  • $\begingroup$ It is not the same. In general, $L_{2}$ norm is the sum of squares, so it would be the same if you would drop the sqrt() function and use a single peak, otherwise you should sum the squared magnitudes of the peaks. You could also use an $L_{1}$ vector norm which is considered to be more robust against outliers. $\endgroup$
    – ZaellixA
    Apr 26 at 20:03
  • $\begingroup$ Thanks @ZaellixA. For the 𝐿2 norm, what exactly is being squared + summed? i.e. if I have an FFT size of 512 bins, am I summing + squaring the indices of the bins? Because if I sum + square the magnitudes only, there would be no difference between, say, A) 0s in all the bins but a 1 in the 100th bin and B) 0s in all the bins but a 1 in the 50th bin, right? $\endgroup$
    – jayp
    Apr 27 at 9:45

1 Answer 1

0
$\begingroup$

I wanted to provide my (partial) solution after doing a lot more experimentation.

After trying and failing to get better results by tweaking window sizes, sample rates, etc., I finally decided to export the individual windows' peak frequency bin indices from each audio file to a combined CSV, so I could investigate in more detail.

I did this by manually lining up the window frame rows based on A) listening to the audio files and estimating the window offset and then B) shifting up/down one file's window frames in the CSV so I could compare peak frequency bins side by side.

The output looked something like this:

File 1 Window # Audio 1 Peak Freq Bin Index Audio 2 Peak Freq Bin Index File 2 Window #
1 84 84 312
2 17 17 313
3 20 21 314
4 18 18 315
5 29 32 316
6 18 18 317
... ... ... ...

What I found was that, during audio sections that should have matched up between the two files, most of the windows' peak frequency bins did match exactly -- but not all of them did. (See above table for an artificial example.) My script was only accepting an audio section as a match if all peak frequency bins within the section matched identically, so it was far too strict.

Although I still haven't managed to tweak all the settings to perfection just yet (meaning where there are no false positive or negative matching sections), here are the main config changes that have gotten me closer:

  1. Pick a minimum total of windows that defines a "section" (e.g. an 100-window minimum, with a window size of 1,024 and sample rate of 8,192, would mean the minimum "section" is about 12.5 seconds). Then consider the section a match if X% or more of the peak frequency bins within it match identically. This allows for some amount of weird encoding issues or other anomalies in otherwise identical audio sections.

  2. Consider windows to be matching if their peak frequency bins are within X bins of each other. (For example, in the above table, you may consider file 1 window #3 / file 2 window #314's bins to be close enough to consider them a match, but perhaps not those in #5 / #316).

  3. Haven't tried this yet, but also considering taking the top, say, 2 or 3 peak frequency bin indices (rather than just a single max) and considering two windows as matching if any of one file's top indices match any of the other file's, for that window.

Hope this helps!

$\endgroup$
2
  • $\begingroup$ Glad you found something that (at least kinda) works for you. In general it could prove to be a quite good idea to drop the "identical" part and define a tolerance when comparing two numbers, except if they are integer values. This has to do more with numerical issues and not something with your approach. Also, allowing for some (the amount depends on your needs and may need experimentation) tolerance in most (if not all) parameters could potentially account for real-life noise $\endgroup$
    – ZaellixA
    Apr 26 at 20:07
  • 1
    $\begingroup$ Yup, agreed. That's what the config change #2 above is mainly about: defining an "error tolerance" for bin matching across audio files. $\endgroup$
    – jayp
    Apr 27 at 9:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.