Hi, Introduction: ******************** I have created an application that knows to match a collection wavelet patterns to sampled audio data ( hence, search ), This was achieved by extracting the features ( FFT, Mel-Scale & MFCC ) for the template and the searched/sampled content, and then, checking their correlation. The problem: ******************* The correlation algorithm I use correlates sampled data with a collection of templates and returns the best matching template ( with a similarity grade ). All this works fine and percice BUT when used with thousands of pattern templates it takes ALLOT of CPU, the main ( and only real ) CPU consumer is the correlation algorithm I use, that is: "Pearson's product-moment coefficient" ( as specified on http://en.wikipedia.org/wiki/Correlation ) I wonder is there any better algorithm ( in terms of CPU consumption ) for matching sampled data with a collection of templates ? I have thought of cross-correlating all of the patterns searched with each other, this cross-correlation can be calculated offline, and, can possibly be used to optimize the realtime 'search' for the best fit pattern ( in a tree structure or so ). I really have to dig deepr in to that and I really don't know how to pruff if the algorithm will converge. Any help would be appreciated Cheers, Nadav Rubinstein

# Audio pattern matching

Started by ●March 12, 2007

Reply by ●March 12, 20072007-03-12

> I have thought of cross-correlating all of the patterns searched with > each other, this cross-correlation can be calculated offline, and, can > possibly be used to optimize the realtime 'search' for the best fit > pattern ( in a tree structure or so ).This seems like a good idea. I would however, try to transform the feature space first into orthogonal sets using principal component analysis (PCA). You can then create clusters along each dimension (starting wit the biggest one first) to reduce your search. If you feature space is very big you can also reduce it by choosing the largest components of the PCA.

Reply by ●March 13, 20072007-03-13

On Mar 13, 2:43 am, "Ikaro" <ikarosi...@hotmail.com> wrote:> > I have thought of cross-correlating all of the patterns searched with > > each other, this cross-correlation can be calculated offline, and, can > > possibly be used to optimize the realtime 'search' for the best fit > > pattern ( in a tree structure or so ). > > This seems like a good idea. I would however, try to transform the > feature space first into orthogonal sets using principal component > analysis (PCA). You can then create clusters along each dimension > (starting wit the biggest one first) to reduce your search. If you > feature space is very big you can also reduce it by choosing the > largest components of the PCA.Can u tell me how u measured the CPU usage.And about the correlation algorithm, i actually need to do a password authentication of the sort on my DSP processor.I gathered that this can be done using correlation algorithm.(basically string matching).Can u tell me how u wrote the algorithm as in, a flow of the program. Thanks in advance

Reply by ●March 13, 20072007-03-13

On Mar 13, 2:43 am, "Ikaro" <ikarosi...@hotmail.com> wrote:> > I have thought of cross-correlating all of the patterns searched with > > each other, this cross-correlation can be calculated offline, and, can > > possibly be used to optimize the realtime 'search' for the best fit > > pattern ( in a tree structure or so ). > > This seems like a good idea. I would however, try to transform the > feature space first into orthogonal sets using principal component > analysis (PCA). You can then create clusters along each dimension > (starting wit the biggest one first) to reduce your search. If you > feature space is very big you can also reduce it by choosing the > largest components of the PCA.I would like to know how you have measured the CPU usage of the algorithm.and i want to do a password authentication on a DSP processot.i.e match the string with the ones stored in a database.I was told that correlation can be used.Can u outline the steps of the correlation algorithm u used. Thanks

Reply by ●March 13, 20072007-03-13

dew wrote:> On Mar 13, 2:43 am, "Ikaro" <ikarosi...@hotmail.com> wrote: >>> I have thought of cross-correlating all of the patterns searched with >>> each other, this cross-correlation can be calculated offline, and, can >>> possibly be used to optimize the realtime 'search' for the best fit >>> pattern ( in a tree structure or so ). >> This seems like a good idea. I would however, try to transform the >> feature space first into orthogonal sets using principal component >> analysis (PCA). You can then create clusters along each dimension >> (starting wit the biggest one first) to reduce your search. If you >> feature space is very big you can also reduce it by choosing the >> largest components of the PCA. > > I would like to know how you have measured the CPU usage of the > algorithm.and i want to do a password authentication on a DSP > processot.i.e match the string with the ones stored in a database.I > was told that correlation can be used.Can u outline the steps of the > correlation algorithm u used. > ThanksDew, While it's true that DSPs aren't well adapted to general string matching -- regular expressions, long texts, and all that -- verifying a password is a trivial character-by-character operation in strings of small maximum size. It doesn't matter if the task takes 200 microseconds instead of 50. You asked the wrong question at the outset. jerry -- Engineering is the art of making what you want from things you can get. ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯

Reply by ●March 13, 20072007-03-13

Jerry Avins wrote:> dew wrote:(snip)>> I would like to know how you have measured the CPU usage of the >> algorithm.and i want to do a password authentication on a DSP >> processot.i.e match the string with the ones stored in a database.I >> was told that correlation can be used.Can u outline the steps of the >> correlation algorithm u used.> While it's true that DSPs aren't well adapted to general string matching > -- regular expressions, long texts, and all that -- verifying a password > is a trivial character-by-character operation in strings of small > maximum size. It doesn't matter if the task takes 200 microseconds > instead of 50. You asked the wrong question at the outset.I wonder ... normally correlation wouldn't be used for password checking, but it might if one wanted to find a close match. Also, many systems use a one-way encryption function for passwords, where the actual password isn't stored, but an encrypted version instead. The entered password is then encrypted with the same algorithm and compared, though it is computationally difficult to compute the plain-text password from the encrypted password. It might be that Dew is interested in cracking passwords, or something else more than just an ordinary password look up. -- glen

Reply by ●March 13, 20072007-03-13

dew wrote on Tuesday 13 Mar 2007 11:23:> On Mar 13, 2:43 am, "Ikaro" <ikarosi...@hotmail.com> wrote: >> > I have thought of cross-correlating all of the patterns searched with >> > each other, this cross-correlation can be calculated offline, and, can >> > possibly be used to optimize the realtime 'search' for the best fit >> > pattern ( in a tree structure or so ). >> >> This seems like a good idea. I would however, try to transform the >> feature space first into orthogonal sets using principal component >> analysis (PCA). You can then create clusters along each dimension >> (starting wit the biggest one first) to reduce your search. If you >> feature space is very big you can also reduce it by choosing the >> largest components of the PCA. > > I would like to know how you have measured the CPU usage of the > algorithm.and i want to do a password authentication on a DSP > processot.i.e match the string with the ones stored in a database.I > was told that correlation can be used.Why would you want to do this on a DSP processor? Why not a normal processor? -- Oli

Reply by ●March 14, 20072007-03-14

On 13 Mrz., 23:01, Oli Charlesworth <c...@olifilth.co.uk> wrote:> dew wrote on Tuesday 13 Mar 2007 11:23: > > > > > > > On Mar 13, 2:43 am, "Ikaro" <ikarosi...@hotmail.com> wrote: > >> > I have thought of cross-correlating all of the patterns searched with > >> > each other, this cross-correlation can be calculated offline, and, can > >> > possibly be used to optimize the realtime 'search' for the best fit > >> > pattern ( in a tree structure or so ). > > >> This seems like a good idea. I would however, try to transform the > >> feature space first into orthogonal sets using principal component > >> analysis (PCA). You can then create clusters along each dimension > >> (starting wit the biggest one first) to reduce your search. If you > >> feature space is very big you can also reduce it by choosing the > >> largest components of the PCA. > > > I would like to know how you have measured the CPU usage of the > > algorithm.and i want to do a password authentication on a DSP > > processot.i.e match the string with the ones stored in a database.I > > was told that correlation can be used. > > Why would you want to do this on a DSP processor? Why not a normal > processor?Why would it matter?