Need pointers on adding feature to search pattern

[audio-enthusiast]

Hello,

I needed a feature in Audacity but it's currently not present. Therefore I'd like to code it myself, but need some initial pointers/comments.

Feature is to be able to select small section from an audio waveform and locate all occurrences of that section in the complete audio file.

This could be achieved in various way, simplest being the use of cross-correlation, which I intend to implement. I have downloaded Audacity source code (I'm not familiar with the code structure yet).

I think the task can be divided into following steps -

1. Store the selected waveform amplitude an an array pattern[]. Some sort of averaging approximation can be used as we don't need to store one number for each sample .

2. Store amplitude numbers for complete audio using similar logic as in step 1 completeAudio[].

3. Perform sliding cross-correlation and store results in another array crossCorr[].

4. Search for maximas in crossCorr[]

Do you think this approach will work? Where should I look in the code base for this task (may be some of these are already taken care of in some function)?

Thanks!

[steve]

Feature is to be able to select small section from an audio waveform and locate all occurrences of that section in the complete audio file.

The general case of selecting an arbitrary sound, then searching for that sound, is very difficult to implement.

There are specific cases that are much more simple. For example, to look for "all occurrences of sound that have a peak level above a specified threshold" is relatively simple to achieve. This is essentially what the "Sound Finder" effect does: http://manual.audacityteam.org/o/man/si ... html#sound

Moving one step up in complexity; looking for a "beep" that is at a specific frequency is not too complicated, The audio can be filtered to pass only narrow frequency bands that correspond to the frequencies contained in the "beep", then the filtered audio searched for where each of those frequency bands has a signal that lies within a specified amplitude range.

Moving further up in terms of complexity; The "needle" sound could be analysed for its frequency content using FFT analysis, then searching for a similar spectrum profile within the "haystack" audio.

For the general case you need to be searching for a sequence of spectrum profiles. A little about this has been written here: http://wiki.audacityteam.org/wiki/Proposal_Audio_Diff

[Robert J. H.]

Cross correlation is a reasonable starting point, it has it's draw backs though.
Let's take a simple example:

audacity.wav

(333.91 KiB) Downloaded 244 times

The search pattern is roughly in the first 18000 samples -- nearly a second at 22.05 kHz.
We will now try to search for it with convolution.
This is nothing but correlation, if the pattern is reversed.
That's the snippet to do it:

Code: Select all

;; Store pattern as array
(setf pattern (snd-samples s 18000))
;; reverse array
(do* ((i 0 (1+ i)) (j (1- (length pattern)) (1- j)) temp) 
     ((or (= j (1- i)) (= i j))) 
      (setf temp (aref pattern i))
      (setf (aref pattern i) (aref pattern j))
      (setf (aref pattern j) temp))
;; Back to a sound
(setf pattern (snd-from-array 0 *sound-srate* pattern))
;; cross correlation by convolution
(setf result  (convolve s pattern))
;; peak is way to high (thousands of times)
(setf result (scale (/ 1.0  (peak result  36000)) result)) 
;; The mask will last for 18000 samples,
;; after a threshold of 0.3 is detected
;; Since the peak is at the end of the pattern,
;; all is shifted back by this amount
(setf mask (extract-abs (/ 18000 *sound-srate*) 3600 
      (snd-oneshot result 0.3 (/ 18000 *sound-srate*))))
;; mask original
(mult s mask)

Copy the code into the nyquist prompt and press ok.
(Of course, you have to import the sample file above first.)
There should now only the occurrances of "Audacity" be audible in the returned sound.
The threshold of 0.3 is somewhat arbitrary.
That's perhaps something that had to be set by a plug-in control.

Also, the marked places do not exclusively hold "Audacity" because the word is sometimes longer and sometimes shorter.
Thus a perfect pattern matching algorithm has to work in two dimensions.

The code above is admittedly slow because I've not averaged the samples.
The result is getting worse, the more we do that. However, you can try to down sample, take the rms values or whatever you want.

[steve]

That's the snippet to do it:

Very nice Robert.

[Robert J. H.]

Thank you Steve,
It is after all only an example under "clinical" conditions.
I've just tried the snippet with the audio book extract from "Manipulating Decibels" at 16 kHz.
It is interesting that the code marks all places with the same intonation--which is actually more difficult for humans than finding a single word.
For practical applications, the convolution had to be implemented with FFT.

[audio-enthusiast]

Brilliant stuff Robert. It works! (within reasonable limits).

I will try to come up with something more sophisticated. Btw is it possible to bring the Nyquist prompt with a keyboard shortcut? I don't see an option for that under kbd shortcut preferences.

[steve]

The Nyquist Prompt is an "Effect" so you can set a keyboard shortcut in the same way as other effects.
http://manual.audacityteam.org/o/man/ke ... ences.html
but probably better would be to make the code as a plug-in
http://wiki.audacityteam.org/wiki/Nyqui ... -in_Header

You can update a plug-in without needing to restart Audacity, but to add a new plug-in Audacity must be restarted before it will appear in the menu.

[audio-enthusiast]

Thanks Steve, but under Effect in kbd preferences where is only key binding available called "Repeat Last Effect".

[steve]

Which version of Audacity are you using? (look in "Help > About Audacity"). The current version is 2.0.5 which is available here: http://audacityteam.org/download/

[Robert J. H.]

Have you entered any character in the filter field?
Just choose "All Commands", change to the list and press "N" until Nyquist Prompt gets focus.

I wouldn't program at all without a shortcut to the Nyquist prompt.
Another Tip: Use Control-Enter in the NP if you don't want to always click on Ok. But you'll probably need the Alt-G shortcut even more...