"Morphing/Warping" of two lists

[Akiraaah]

Hi everyone

I'm an almost total newbie to lisp, so please be indulgent...

I'd like to write a code to make a kind of supervised morphing between 2 lists.
Something that's not too far from image morphing, but in one-dimension.

For instance :
-from a list A...
(0.0 0.1 0.1 0.0 1.0 1.0 1.0 0.4 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0)
-> labelling it with any number of points or groups of points as key-features / leaving some datas "neutral"
((0.0) (0.1 x) (0.1 x) (0.0) (1.0 y) (1.0 y) (1.0 y) (0.4 y) (0.0) (0.0) (0.0) (0.0) (0.0) (0.0) (0.0) (0.0) (0.0) (0.0) (0.0) (0.0))



-...to a list B
(0.0 0.0 0.0 0.0 0.5 0.5 0.5 0.1 0.0 0.0 0.0 1.0 1.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0)
-> same as before, with key features equivalent to the ones of list A
((0.0) (0.0) (0.0) (0.0) (0.5 x) (0.5 x) (0.5 x) (0.1 x) (0.0) (0.0) (0.0) (1.0 y) (1.0 y) (1.0 y) (0.0) (0.0) (0.0) (0.0) (0.0) (0.0))


-> my goal would be to obtain an arbitrary number of intermediate lists, progressively turning list A
into list B, according to the key-features determined. The "neutral" parts would be transformed like
in a standard linear interpolation.


Here's a example source I found online about morphing :
http://www.hammerhead.com/thad/morph.html

I would probably manage to program the different parts of the code, mostly
using iterate I think, but I really need help to decipher the formulas.
I'm a musician, not a programmer and my math knowledge is worst than everything.
I came to lisp more through the logical part than the mathematical part, so
I have big difficulties to understand the procedures and, above all, to reformulate
them in one dimension...

Anybody has an idea?
Thank you very much in advance

J.

[ramarren]

I doubt that trying to change a two-dimensional algorithm to one dimension would be useful in this case. And I don't think it is necessary, since the one-dimensional case for pre-tagged features appears trivial, at least conceptually, unless I misunderstand your requirements.

The way I would do it is to separate each feature, normalize the endpoints to common size by interpolation, do a linear interpolation between those endpoints, and then apply a morphed feature with an interpolated shift and rescaling to the background.

Scaling and blending might be tricky, but I don't think the exact values matter that much for this application. What do you need this for, anyway?

[edgar-rft]

I'm a musician, not a programmer and my math knowledge is worst than everything. I came to lisp more through the logical part than the mathematical part...

Hello and welcome, that's exactly how I myself started Common Lisp programming some years ago. I'm not a real professional math artist either, but the math on the hammerhead page doesn't look really complicated. But the real problem may be a completely different thing:

What do you need this for, anyway?

I think this is the key question. The hammerhead page is about computer graphics, the pictures above to me look more like control curves for audio equalizers or resonance filter effects. In computer graphics you use linear interpolation, in audio DSP you use linear as well as logarithmic interpolation (deciBels), depending on the particular use-case. That's one of the reasons why computer graphics math in most cases cannot directly transformed into audio processing math, even if the curves look similar.

Maybe interesting to know in this context: 'rft' = 'radio/television technichian', I'm something like a audio/video electronics hardware repair-man. Maybe you can explain what you intend to do in 'musician language', I think I can help to translate it to 'Lisp language' if necessary.

[Akiraaah]

Thank you very much for your answers.
You're both right in a way, what do I need this for... ^^

To be more precise for Edgar, I am equally into the sound things (Cubase, MaxMSP)
and to the composition things, scores and so on...
A few years ago I began lisp using a kind of graphical common-lisp environment
for musicians (a "lisp for dummies" so to speak) called PWGL.
http://www2.siba.fi/PWGL/
(BTW, lisp is used by composers almost since the 70th, because its set theory aspect is
very similar to the way musicians think)

It is a bit elitist, maybe too much oriented to experimental/contemporary music,
but it's enough open (like lisp) to do what anybody wants.
In my case, I use arbitrary (sometime improvized) forms, like the ones posted above,
as schemes for any parts of my music and I need this morphing thing for instance
to turn a musical idea into another.
Actually, a lot of people I know do similar things (in sound and
scores, sometimes for really beautiful results, you couldn't expect...) but nobody
achieved a supervised metamorphosis tool, that could help us to morph bigger and
more precise morphologies...

...Until that night. I achieved a kind a process that's not too far from what Ramarren suggested.
Here is a capture of my graphical code, we usually call a "patch" :
http://i.imagehost.org/0992/patch.png (sorry the image is too big)
That's just to give you an idea, I think it won't be so easy to read :
graphical programming, even very close to lisp, implies some different strategies than text lisp.
And I use a lot a abstractions of uncommon functions to gain so time.


The problem of my approach is local-resampling, necessary to keep successive equivalent parts with same length,
that is keeping their relative scale to the whole form.
At the end, some parts of the signal are altered by linear down-sampling, as shown here :
http://img830.imageshack.us/img830/645/morph.png

You can see the difference between the last element and the penultimate. Maybe if I oversample the
shorter sequence first, morph the two, then downsample it, I can bypass this problem. What do you think?

(Last thing to Edgar, you're perfectly right about the linear/logarithmic problem, even for my problem in a way.
Perception of time, as perception of dynamics, is not linear at all, so I must integrate some non-linear logic
somewhere...)

[edgar-rft]

Thanks for the information., I'm semi-familiar with Pure Data (poor man's version of MaxMSP), so reading 'patches' is not very new to me, so far the good news. The bad news is, that in graphical interfaces a myriad of implementation details is hidden to the user, so the 'patch.png' only shows the basic principle, but trying to re-program the patch in Common Lisp (text version) is a lot of work.

Attempt of a summary in possibly simple terms:

• You want to morph one waveform into another waveform.

Questions:

• Are the waveforms audible signals (sounds) or control waveforms (usually very low frequencies, below the audible range, which control filters or volume levels) or maybe both, depending on the situation?
  
  Do the initial and the final waveform of the morph both have the same length (same number of samples or same time in seconds) or does this depend on the particular situation?

Possible solutions:

• Time-related manipulations can be solved via up- and downsampling, linear interpolation or most often both together. This not really complicated, but in the case of audible signals we have to care about aliasing. This happens if during downsampling the input signal contains frequencies above half of the new (lower) sample frequency. In this case additional filtering before downsampling is needed.
  
  In the case of audible waveforms (sounds), volume changes are logarithmic.
  
  Pitch-shifting is logarithmic, too, but different from changing volumes.

As far as I have understood only time-stretching is involved (or better 'morphing', what is not exactly the same as time-stretching but very similar), but no any other pitch-shifting is involved than caused by resampling. Is that right or do also you need effects like 'time-stretching without pitch-shifting' or similar things?

Common audio stretching and morphing techniques are:

• psola, wsola, phase-vocoder
  
  see: http://en.wikipedia.org/wiki/Audio_timescale-pitch_modification

Is there any useful information for your question on this page?

- edgar

[edgar-rft]

One hour later: Sorry, maybe I'm more stupid than intended.

Are these piece-wise envelope waveforms stored in lists and you want the envelope in list A:

Code: Select all

(0.0 0.1 0.1 0.0 1.0 1.0 1.0 0.4 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0 0.0)

being morphed into the envelope stored in list B:

Code: Select all

(0.0 0.0 0.0 0.0 0.5 0.5 0.5 0.1 0.0 0.0 0.0 1.0 1.0 1.0 0.0 0.0 0.0 0.0 0.0 0.0)

in a user-definable number of steps (morphs), where PWGL handles the antialiasing and we do not need to care about?
Only the number of elements in the list is relevant and nothing else? Is this true?

Unfortunately there is no time scale in 'morph.png', so I can't answer this question to myself.

[Akiraaah]

Hi again Edgar, thanks for your replies.

Cool that you know PD, this is an excellent program.
Cheap but as much serious (maybe more) as MaxMSP.

Unfortunately, I think i wasn't enough explicit in my previous post.
PWGL is not at all a program to compute audio, which is clearly the job
of Max or PD. PWGL is (kind of) equivalent to them, but in the field of
musical structures, i.e. computing pitches, rhythms, orchestrations, etc.
rendered as standard musical scores like this :


These kind of musical datas as really more abstract than sound, and LISP
is really appropriate to compute them. That's why what you call "waveforms",
I call "morphologies", that is abstract schemes that I can use arbitrarily at any
time scales, for any musical purpose I need and want for a composition.

That is the reason I need a supervised geometrical morphing that can be enoughprecise (rigorously geometrical) to be neutral, to generate hybrids, for instance, between two melodies or two rhythmical sequences. Usual interpolations precisely don't work well with rhythms, for various reasons. I think that supervising the process, by defining some equivalent features (like in image morphing) can be a way to resolve this problem.

I found where my errors come from, I used locally (for extracted features) a basic interpolator to morph lists of different length.
I just need to find a way to fix this, and my morphing patch will be finished, I hope.
I will try to translate it to pure lisp and post it here if i got some time.
Thank you again for your help.

[s-imp]

Wouldn't you just find the difference between A and B for each point, divide by how many intermediate steps to get a transform list (T) and then mapcar adding T to A, and using each result list as the new A until A becomes B?

[Akiraaah]

Hi s-imp

I don't think this will work, as it will map together, without any consideration, features into plane parts and inverse.
This would be the basic interpolation I use, locally, to turn a feature of A into a feature of B, or a plane part of A into
a plane part of B.
But in order for that method to work, I found out it was necessary to classify (with k-means or another clustering algorithm)
the two lists before, to extract their basic structure (features or saliences and plane parts or background).

My patch works perfectly now : a fully supervised feature-oriented list morpher.
But it's still hard to turn into pure lisp.
If anyone is interested, he/she can contact me in order to get the patch for PWGL.
Then you could maybe deduce the code from the system I built.
Cheers
J.