A few steps are involved, namely:

1) Read in the Wave Files

-This is done, I have the target file read in, target.wav and I have a directory of possible .wav's that could match

2) Comparing the waves

-My first idea was to create a markov chain (using Hidden Markov Model).

What this does is basically:

if the next data chunk is > the current data chunk, that position in the markov chain would be 1

0 for no change

-1 for a decrease change

ex: If this were the .wav's data

123 567 400 400 -125 -145 0 99

the markov chain would be

1 -1 0 -1 -1 1 1

My method of comparing involves comparing the markov chain of the target.wav to all of the possible files.

like this: (the target.wav must be smaller than a given possible file)

I compare the target markov to every position in the possible match file.

---- target -------- current possible ---- target -------- current possible ---- target -------- current possible ---- target -------- current possible

The problem is this takes way too long (a 10sec .wav file has 320,000 elements of data. Comparing 1 song to my 10sec clip took 6 hours)

and my question is: (drum roll please)

How can I do this better/faster? Maybe Markov model is not the way to go, or maybe I'm not implementing it correctly.

This is a very interesting problem and I'd like to hear your solutions!

Thanks

here's come code:

Note in the constructor:

The Waves are in an arraylist and they are type int[][] where int[channel][channel data]

class WaveCompare { ArrayList MarkovChains; public WaveCompare(ArrayList Waves, int IndexOfTargetWave) { //Build markov chain for each wave BuildMarkovChains(Waves); //now we need to compare the target markov chain to every sub-section of every other wav file CompareMarkovChains(IndexOfTargetWave); } private void CompareMarkovChains(int IndexOfTarget) { short[][] Target = (short[][])MarkovChains[IndexOfTarget]; for (int i = 0; i < MarkovChains.Count; i++) { if (i == IndexOfTarget)//dont compare to self! continue; short[][] Current = (short[][])MarkovChains[i]; for (int j = 0; j < Current.Length; j++) //for each channel in comparer { for (int z = 0; z < Target.Length; z++) //for each channel in target { //Will Only Continue if the Target is shorter than the Current! int TargChanLen = Target[z].Length; //compare at each starting position to find best alignment in the wav for (int k = FirstNonZero(Current[j]); k < Current[j].Length - TargChanLen; k++) { // Advances k to first non-zero position in the Current Wave int Matches = 0; for (int q = 0; q < TargChanLen; q++) {//compare each value of the target wave with the current subset of the Current wave if (Target[z][q] == Current[j][q + k]) {//is a match Matches++; } } //find percentage correct in that subset float Result = Matches / (float)TargChanLen; if (Result > .8) // if 80% match { } } } } } } private int FirstNonZero(short[] p) { for (int i = 0; i < p.Length; i++) if (p[i] != 0) return i; return 0; } private void BuildMarkovChains(ArrayList Waves) { MarkovChains = new ArrayList(); for (int k = 0; k < Waves.Count; k++) { int[][] Wave = (int[][])Waves[k]; short[][] CurrentMarkov = new short[Wave.Length][];//short int, 3 possible values //-1 for negative change, 0 for no change, 1 for positive change //Could expand to -2 for big down jump , -1 for small down jump, 0 no change, etc... //or even more! to -5, -4, -3, etc.. for (int i = 0; i < Wave.Length; i++) //frames { CurrentMarkov[i] = new short[Wave[0].Length - 1]; for (int j = 0; j < Wave[0].Length - 1; j++) //channels { if (Wave[i][j + 1] < Wave[i][j]) CurrentMarkov[i][j] = -1; else if (Wave[i][j + 1] == Wave[i][j]) CurrentMarkov[i][j] = 0; else CurrentMarkov[i][j] = 1; } } MarkovChains.Add(CurrentMarkov); } } }

This post has been edited by **fremgenc**: 21 December 2008 - 04:05 PM