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?
Reply by Oli Charlesworth●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 glen herrmannsfeldt●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 Jerry Avins●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.
> Thanks
Dew,
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 dew●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 dew●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 Ikaro●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 Nadav●March 12, 20072007-03-12
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