Hi there

I'm looking for a way for Pd to recognize recurring graphical data patterns within arrays, does anyone know of anything out there for this? Would my best bet be trying to make a patch for this myself?

Thanks

J

I haven't heard of anything like that before, but others probably know more. But this seems an interesting topic to work on, so could you please keep us informed about your progress?

Thanks a lot,

D.

This is just a wild guess, but thinking of "recurring patterns" as waves, maybe there's a way to use filters and FFT stuff at audio rate to do what you want?

Or you could probably program some basic filters at message rate, if none exist -- Google "digital filters." My understanding thereof is from the first 5 pages or so of Hamming's Digital Filters (before the math got scary), but there must be some stuff online.

Sounds good! Thanks for that, will post my progress...

J

Sometimes I feel like the calculus geek on the forums, but I'd like to throw out the idea of comparing the dy/dx of the tables to look for patterns as well. That would take into consideration transpositions. the ffts could be used in conjunction. For every table of data, constructing subtables, filtering the data. eg.

Just as a quick pointer...

This problem involves the subjects of correlation and autocorrelation (CC and AC).

To get a correlation you do something like convolution, it's expensive/forceful.
In its very simplest form, say you have a long signal of m samples M, and a shorter pattern n samples long called N that you are looking for. Starting at 0,0 you multiply M[0] x N[0], M[1] x N[1]... M[n] - N[n] and look for a minimum in the first derivative over n samples. That tells you that something close to your test signal N appears in M.

What AC gives you is a measure of the periodic similarity within a window. It's like a convolution of a signal with a time reversed version of itself. If a signal is periodic then the AC is high, if it noisy then the AC is low.

Do some searching on the words "cross correlation" and "auto correlation"

Like searching a piece of music for a motive or a theme?

I was thinking along the lines of comparing multiple patterns of x length, and then divining the most similar of the tables. Contrasting and comparing, not pattern recognition. I was OT, apologies.

But I think that comparison might be useful for automating pattern distillation.

No not OT, just a related but different take on the same ideas. Pattern recognition is usually meant as something that happens on a higher level Sunji. Correlation is a finer grain (samplewise) process that might be used as a smaller step in a bigger DSP process. Say for instance we do a DTFT/phase vocoder analysis to get a sequence of bins with spectral energy, or some other analysis that produces an array of data. Then 'pattern recognition' is any algorithm to search that data. What we're usually after is a start time for good matches, like grep for audio, or the x,y coords of the centre of a matching object in an image.

Often we aren't looking for an exact match, but a fuzzy "is it *like* this?" match. Some techniques to study are hidden Markov methods, distance/clustering approaches, predictive coding etc. These are things that neural networks and fuzzy logic are great for, applications are speech to text, keyword listening, automatic music transcription etc.

Exhaustive comparison of samples is a very expensive and very brittle (it breaks for any change in the data) way of doing things - first it's necessary to reduce the data down (feature extraction) to a more useful form.

There's several flavours of problem that lead to different algorithms.

identification - looking for one specific thing that appears somewhere in a lot of (potentially similar) data.

classification - finding new patterns in data and tagging them.

segregation - looking for changes that indicate boundaries of some kind.

recognition - finding the occurance of known, pre-classified features.

tracking/attending - following a known feature that changes dynamically (often while obscured by noise).

I know I've seen some fuzzy logic, classifier and NN objects in Pd in the past. These could be used with array data turned to message or signal domain flows.
Half the problem is defining exactly what you want. From Jareds OP I think it's more of a classification thing - does a pattern occur more than once?

a.

Am I correct in thinking autocorrelation is a n! function? It seems nearly impossible to perform on actual audio data. But, autocorrelating midi data seems much more reasonable. You can derive the motion of a melody, both chromatically and tonally, and also as solfege (0 do, 1 re, 2 mi). But then there's metric variation to account for as well... so much to code!

Am I correct in thinking autocorrelation is a n! function?

Not that bad. O(n^2) I think.

And there's "fast autocorrelation" that can do O(n log n). Don't know how those work.

Nice one guys! Thanks for all this!

"From Jareds OP I think it's more of a classification thing - does a pattern occur more than once?"

Yes, I had in mind initially the classification of recurring patterns. The info on cross correlation/autocorrelation seems as though it will be very helpful, and nice pointer on the use of 'fuzzy logic' as opposed to precise sample comparison!

sunji: "this gives you a multidimensional look at the table. You can visualize the fatness, and quickness, and shape of the data."

• This stuff will be really great to play with too!!

J

It would be great if you could post your finished product if it succeeds. I don't know much about what sunji and obiwannabe are talking about beyond the basic calculus stuff, so it would be fascinating to see a demonstration, especially in an aesthetic context.

Yes, I certainly will!

Was there ever any progress with this project? Sounds very interesting.

ok, some small progress has been made on this- check it out on my soundcloud page

It's a couple of things going on here. A live jam, I'm playing the egamelan, my amigo is bozioing some mididrums, and there is the synthonic support orchestra, which is jamming right along with us. The correlation is still baby steps, but I am happy with the prelim results.

Hi Sunji,

It it possible to share the patch?

Ricky

Ya sure, check it out. I do some spaghetti patching to get different effects.

Things I want this to do:

1. figure out what the hell [gestalt] does
2. incorporate Manzo's tonal library for better analysis and synthesis
3. finish integrating the auto correlators, you'll notice that there's some smoke waving and man behind the curtain code in there right now.

http://www.pdpatchrepo.info/hurleur/synthony.0.1.pd

the correlation patch is here, but it's so messy that I haven't moduled, to stick it in the synthony. It morphed into a hung up retread of Scrambled hackz

http://sourceforge.net/projects/scrambledhackz/

And as yet incomplete. This is extremely poor code right now! AAHYWEH.

but, the correlate functions could read the tables in the melody analysis subpatch in the synthony. motives will be successive strings of 0's in the correlate functions.

http://www.pdpatchrepo.info/hurleur/hambledscrakz.zip