image thumbnail

findSimilarity

version 1.0 (2.71 KB) by Matt Flax
A faster implementation of findsignal

6 Downloads

Updated 20 Oct 2021

From GitHub

View license on GitHub

findSimilarity

Finding a similar signal in a longer signal is a common problem in signal processing. Waveform Similarity Overlap Add (WSOLA) is an example of an algorithm which uses signal similarity to speed up and slow down audio without changing its pitch.

The brute force method to find a similar signal between a reference (s) and a longer waveform (y) is based on RMS value of the distance :

Ns=size(s,1);
res=buffer(y,Ns,Ns-1,'nodelay');
res=s-res;
errM=rms(res);
[err,nI]=min(errM);

This brute force method is slow because it uses a huge amount of memory in buffering the signal with one sample overlap and the computational complexity of the RMS function.

Methods based on the DFT (for example Mueen's implementation) break the nonlinear distance measure into a linear component which is convolved using the DFT :

(s-y)^2 = s^2 - 2s*y + y^2

The s*y convolution is performed in the DFT domain which is a speed up for large vectors. However for smaller s and y vectors the computation is still not efficient enough.

The solution proposed here reduces the order of the computation by breaking it into two steps. The first step computes the distance measure on a smaller signal space looking for the possible location of the global minimum. The second iteration does a complete search of the global minimum's region looking for the exact result.

Cite As

Matt Flax (2022). findSimilarity (https://github.com/flatmax/findSimilarity/releases/tag/v1.0), GitHub. Retrieved .

MATLAB Release Compatibility
Created with R2021b
Compatible with any release
Platform Compatibility
Windows macOS Linux
Tags Add Tags

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!
To view or report issues in this GitHub add-on, visit the GitHub Repository.
To view or report issues in this GitHub add-on, visit the GitHub Repository.