Wave Comparison

finding a similarity percentage between two .wav files

Page 1 of 1

6 Replies - 11251 Views - Last Post: 12 March 2010 - 03:56 AM Rate Topic: -----

#1 fremgenc  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 119
  • Joined: 15-November 07

Wave Comparison

Post icon  Posted 21 December 2008 - 03:49 PM

Hey Guys. Let me explain the 'Big Idea'. I want to allow the user to whistle, or hum a song into a microphone, and my program find what song the user is thinking of.
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


Is This A Good Question/Topic? 0
  • +

Replies To: Wave Comparison

#2 scalt  Icon User is offline

  • D.I.C Regular
  • member icon

Reputation: 63
  • View blog
  • Posts: 342
  • Joined: 22-November 07

Re: Wave Comparison

Posted 21 December 2008 - 04:58 PM

I haven't tried to implement this before but maybe there is a way you could do a Fourier analysis on the input to try and find the main frequencies present and compare them? I remember using some software than essentially turned your soundcard into an oscilloscope that did basically the same thing and it seemed pretty quick. If you don't know what a Fourier series is look it up in Wikipedia, but it may be a little complicated particularly if you haven't used it before.

Edit:
Maybe you might also want try adding some kind of beat detection in if you get it going. People are probably more likely to get the beat right than the notes (I'm guessing here)

This post has been edited by scalt: 21 December 2008 - 05:02 PM

Was This Post Helpful? 1
  • +
  • -

#3 fremgenc  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 119
  • Joined: 15-November 07

Re: Wave Comparison

Posted 21 December 2008 - 05:19 PM

This is an incredibly rich topic to explore (Fourier Analysis)

I will look into this tonight and keep this thread updated. I think this is a very interesting project, and can be expanded greatly once a reliable method for wave comparison is achieved.

Cheers

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

Was This Post Helpful? 0
  • +
  • -

#4 HuaMin  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 10-June 09

Re: Wave Comparison

Posted 10 June 2009 - 10:02 PM

Hi,
I want to make sure if every sound will just become a series of numbers by this - 'BuildMarkovChains'?
Was This Post Helpful? 0
  • +
  • -

#5 fremgenc  Icon User is offline

  • D.I.C Head

Reputation: 3
  • View blog
  • Posts: 119
  • Joined: 15-November 07

Re: Wave Comparison

Posted 11 June 2009 - 07:59 AM

No, BuildMarkovChains() builds an array based on the relation of each sound compared with the previous sound level.

When you load in a .wav file, then it will become a series of numbers.
Was This Post Helpful? 0
  • +
  • -

#6 CrazedAzn  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 20
  • Joined: 26-September 07

Re: Wave Comparison

Posted 11 June 2009 - 11:13 AM

Maybe you can try some dynamic programming tactics and "memoize" the markov chains for each target.wav file that way you don't have to do the same calculation again. Perhaps even store the resulting data in a file and reading it in on startup.

Edit: Nvm, just realized that even comparing one song takes too long. Sorry.

This post has been edited by CrazedAzn: 11 June 2009 - 11:14 AM

Was This Post Helpful? 0
  • +
  • -

#7 Guest_Michael*


Reputation:

Re: Wave Comparison

Posted 12 March 2010 - 03:56 AM

Can u supply me with the full code?

Michael
Was This Post Helpful? 0

Page 1 of 1