hi Olli (and others)...
i was reviewing this thread because i wanted to read what Stefan
Stenzel had said and realized that you had posted this response, and i
don't think i or anyone had responded to it. i don't remember reading
it (it must be the cannabis). i hope you're listening Olli - i have a
lot of respect for what i have read from you (the pink elephant paper).
since this comes from last December, i reposted (with more
corrections) the original "theory" at the bottom.
On Dec 7, 2010, at 5:27 AM, Olli Niemitalo wrote:
RBJ,
I had a look at your theory, and compared it to my approach (dare not
call it a theory, as it was not as rigorously derived). The following
is how I imagine we thought things out.
Both of us wanted to preserve some aspect(s) of the known-to-be-good
constant-voltage crossfade envelopes, and to generalize from those the
envelope functions for arbitrary values of the correlation
coefficient.
You saw that the odd component o(t) determined the shape of the
constant-voltage envelopes. For those, the even component had to be
e(t) = 1/2 to satisfy the symmetry a(t) + a(-t) = 1 required in
constant-voltage crossfades.
it need not be the case that e(t) = 1/2 in the non-constant-voltage
crossfades.
So apparently o(t) was capturing the
essential aspects of the crossfade envelope. You showed how to
recalculate e(t) for different values of the correlation coefficient
in such a way that o(t) was preserved.
i wasn't trying to preserve o(t). it's just that it was easier to get
a handle on a(t) (and a(-t)) if i split it into e(t) and o(t). and
then in the final solution, a square root was involved in solving for
either o(t) or e(t). since o(t) *has* to be bipolar, solving for o(t)
in terms of e(t) is a little more problematic than vise versa because
you *know* that o(t) is necessarily bipolar and you have to deal with
the +/- sqrt() issue. but if you specify o(t) and solve for e(t),
there is no problem with defining e(t) to be always non-negative.
I, on the other hand, chose that the ratio a(t)/a(-t) (using your
notation) should be preserved for each value of t.
now, i do not understand why you would do that. by "preserved", do
you mean constant over all t? even for simple, linear crossfades,
you cannot satisfy that.
To accomplish this,
one could first do the crossfade using constant-voltage envelopes and
then apply to the resulting signal a volume envelope to adjust for any
deviation from perfect positive correlation. Or equivalently, the
compensation could be incorporated into a(t), which I showed how to do
in the case of a linear constant-voltage crossfade. Other
constant-voltage crossfade envelopes than linear could be handled by a
time deformation function u(t) which gives the time at which the
linear constant-voltage envelope function reaches the value of the
desired constant-voltage envelope function at time t. u(t) would then
used instead of t in the formula for a(t) derived for generalization
of the linear crossfade for arbitrary r.
so if a(t)/a(-t) is not "preserved" over different values of t but is
preserved over different values of r, i am not sure you want to do that.
what is the fundamental reason for preserving a(t)/a(-t) ?
I believe your requirement for r >= 0 could be relaxed. For example,
if one is creating a drum-loop, then it would probably make most sense
to put the loop points in the more quiet areas between the transients.
And there you might only have noise that is independent between the
two loop points, thus giving values of the correlation coefficient
slightly positive or slightly negative. Because the length of a drum
loop is fixed, there might not be so much choice in placement of the
loop points, and a spot giving a slightly negative r might actually be
the most natural choice. I do not think your formulas will fall apart
just as long as -1 < r <= 1.
but i don't think it is necessary to deal with lags where Rxx(tau) <
0. why splice a waveform to another part of the same waveform that
has opposite polarity? that would create an even a bigger glitch.
you want to find a value of the lag, tau, so that Rxx(tau) is maximum
(not including tau around 0) and then your splice is as seamless as it
can be. then, if the splice is real good (r=1), you use a constant-
voltage crossfade. when your splice is poor (r=0 and it need not be
poorer than that), you use a constant-power crossfade.
but i agree that the crossfade theory i presented does not require r >
1. i just wanted to show that it degenerates to a constant-voltage
crossfade when r=1 and a constant-power crossfade when r=0.
--
r b-j r...@audioimagination.com
"Imagination is more important than knowledge."
This is a continuation of the thread started by Element Green titled:
Algorithms for finding seamless loops in audio
As far as I know, it is not published anywhere. A few years ago, I
was thinking of writing this up and publishing it (or submitting it
for publication, probably to JAES), and had let it fall by the
wayside. I'm "publishing" the main ideas here on music-dsp because of
some possible interest here (and the hope it might be helpful to
somebody), and so that "prior art" is established in case of anyone
like IVL is thinking of claiming it as their own. I really do not
know how useful it will be in practice. It might not make any
difference. It's just a theory.
______________________________________________________________________
Section 0:
This is about the generalization of the different ways we can splice
and crossfade audio that has these two extremes:
(1) Splicing perfectly coherent and correlated signals
(2) Splicing completely uncorrelated signals
I sometimes call the first case the "constant-voltage crossfade"
because the crossfade envelopes of the two signals being spliced add
up to one. The two envelopes meet when both have a value of 1/2. In
the second case, we use a "constant-power crossfade", the square of
the two envelopes add to one and they meet when both have a value of
sqrt(1/2) = 0.707 .
The questions I wanted to answer are: What does one do for cases in
between, and how does one know from the audio, which crossfade
function to use? How does one quantify the answers to these
questions? How much can we generalize the answer?
______________________________________________________________________
Section 1: Set up the problem.
We have two continuous-time audio signals, x(t) and y(t), and we want
to splice from one to the other at time t=0. In pitch-shifting or
time-scaling or any other looping, y(t) can be some delayed or
advanced version of x(t).
e.g. y(t) = x(t+P)
where P is a period length or some other "good" splice
displacement. We get that value, P, from an algorithm
we call a "pitch detector".
Also, it doesn't matter whether x(t) is getting spliced to y(t) or the
other way around, it should work just as well for the audio played in
reverse. And it should be no loss of generality that the splice
happens at t=0, we define our coordinate system any damn way we damn
well please.
The signal resulting from the splice is
v(t) = a(t)*y(t) + a(-t)*x(t)
By restricting our result to be equivalent if run either forward or
backward in time, we can conclude that "fade-in" function (say that's
a(t)) is the time-reversed copy of the "fade-out" function, a(-t).
For the correlated case (1): a(t) + a(-t) = 1 for all t
For the uncorrelated case (2): (a(t))^2 + (a(-t))^2 = 1 for all t
This crossfade function, a(t), has well-defined even and odd symmetry
components:
a(t) = e(t) + o(t)
where
even part: e(t) = e(-t) = ( a(t) + a(-t) )/2
odd part: o(t) = -o(-t) = ( a(t) - a(-t) )/2
And it's clear that
a(-t) = e(t) - o(t) .
For example, if it's a simple linear crossfade (equivalent to splicing
analog tape with a diagonally-oriented razor blade):
{ 0 for t <= -1
{
a(t) = { 1/2 + t/2 for -1 < t < 1
{
{ 1 for t >= 1
This is represented simply, in the even and odd components, as:
e(t) = 1/2
{ t/2 for |t| < 1
o(t) = {
{ sgn(t)/2 for |t| >= 1
where sgn(t) is the "sign function":
{ -1 for t < 0
{
sgn(t) = { 0 for t = 0
{
{ +1 for t > 0
a shorthand: sgn(t) = t/|t| .
This is a constant voltage-crossfade, appropriate for perfectly
correlated signals; x(t) and y(t). There is no loss of generality by
defining the crossfade to take place around t=0 and have two time
units in length. Both are simply a matter of offset and scaling of
time.
Another constant-voltage crossfade would be what I might call a "Hann
crossfade" (after the Hann window):
e(t) = 1/2
{ (1/2)*sin(pi/2 * t) for |t| < 1
o(t) = {
{ sgn(t)/2 for |t| >= 1
Some might like that better because the derivative is continuous
everywhere. Extending this idea, one more constant-voltage crossfade
is what I might call a "Flattened Hann crossfade":
e(t) = 1/2
{ (9/16)*sin(pi/2 * t) + (1/16)*sin(3*pi/2 * t) for |t| < 1
o(t) = {
{ sgn(t)/2 for |t| >= 1
This splice is everywhere continuous in the zeroth, first, and second
derivative. A very smooth crossfade.
As another example, a constant-power crossfade would be the same as
any of the above, but where the above a(t) is square rooted:
{ 0 for t <= -1
{
a(t) = { sqrt(1/2 + t/2) for -1 < t < 1
{
{ 1 for t >= 1
This is what we might use to splice to completely uncorrelated signals
together. We can separate this into even and odd parts as:
{ (1/2)*(sqrt(1/2 + t/2) + sqrt(1/2 - t/2)) for |t| < 1
e(t) = {
{ 1/2 for |t| >= 1
{ (1/2)*(sqrt(1/2 + t/2) - sqrt(1/2 - t/2)) for |t| < 1
o(t) = {
{ sgn(t)/2 for |t| >= 1
______________________________________________________________________
Section 2: Which crossfade function to use?
Now we shall make a definition and an assumption. We shall define an
inner product of two general signals as:
+inf
<x,y> = <x(t), y(t)> = integral{ x(t)*y(t) * w(t) dt}
-inf
w(t) is a window function that is symmetrical about t=0 and is
probably wider than the crossfade. Strictly speaking, if you were
coming at this from out of a graduate course in metric spaces or
functional analysis, one of the components (probably y(t)) should be
complex conjugated, but since x(t) and y(t) are always real, in this
whole theory, I will not bother with that notation.
This inner product is an degenerate case of the more general cross-
correlation evaluated with a lag of zero:
+inf
Rxy(tau) = <x(t), y(t+tau)> = integral{ x(t)*y(t+tau) * w(t) dt}
-inf
If y(t) is a time-offset copy of x(t), then Rxy(tau) is the
autocorrelation of x(t), Rxx(tau), but also accounting for the time
offset in the lag, tau.
So <x,y> = Rxy(0)
A measure of signal energy or average power is:
+inf
Rxx(0) = <x,x> = integral{ (x(t))^2 * w(t) dt}
-inf
Now, the assumption that we are going to toss in here is that the mean
power of the two signals that we are crossfading, x(t) and y(t), are
equal.
<x,x> = <y,y>
We are assuming that we're not crossfading this very quiet tone or
sound to a very loud sound that is 60 dB louder. Similarly, the
resulting spliced sound, v(t), has the same mean power of the two
signals being spliced:
<v,v> = <x,x> = <y,y>
So, assuming we lined up x(t) and y(t) so that we want to splice from
one to the other at t=0, and scaled x(t) and y(t) so that they have
the same mean power in the neighborhood of t=0, then the inner product
is a measure of how well they are correlated. We shall define this
normalized measure of correlation as:
r = <x,y>/<x,x> = <x,y>/<y,y>
If r = 1, they are perfectly correlated and if r = 0, they are
completely uncorrelated.
We will make the additional assumption that our pitch detection
algorithm will find *some* lag, P, where the correlation is at least
zero correlated. We should not have to deal with splicing
*negatively* correlated audio (that would have quite a "glitch" or a
bad splice). If the two signals, x(t) and y(t), have no DC component,
then their autocorrelations and their cross-correlations to each other
must have no DC component. That means there will be values of tau
such that Rxy(tau) are either negative or positive. If it was
theoretical white noise, Rxx(tau) would be zero for |tau| > 0 and
Rxx(0) would be the noise variance or power. But Rxx(tau) cannot be
negative for *all* values of tau, even excluding tau=0.
For the splicing done in a time-domain pitch shifting or time scaling
algorithm, we can find a value of tau so that Rxx(tau) is non-negative
and we want to choose tau = P so that has the highest value of
Rxx(tau). Then define
y(t) = x(t+P)
and then
<x,y> = Rxy(0) = Rxx(P)
Now we shall also assume that the crossfade function, a(t), is
completely uncorrelated and even statistically independent from the
two signals being spliced. a(t) is a volume control that varies in
time, but is unaffected by anything in x(t) or y(t).
We shall also assume something called "ergodicity". This means that
*time* averages of x(t) and y(t) (or combinations of x(t) and y(t))
are equal to *statistical* averages. If this window, w(t) is scaled
(or normalized) so that its integral is 1,
+inf
integral{ w(t) dt} = 1
-inf
then all these inner products (which are time averages) can be related
to "expectation values" (which are statistical averages):
<x,y> = E{ x(t)*y(t) }
If x(t) and y(t) are thought of as sorta "random" processes (rather
than well defined deterministic functions), the expectation value is
unmoved no matter what t is. But if the envelope a(t) is considered
deterministic, then it simply scales x(t) or y(t) and is treated as a
constant in the expectation. So at some particular time t0,
<a(t0)*x,y> = E{ (a(t0)*x(t)) * y(t) }
= a(t0) * E{ x(t) * y(t) }
= a(t0) * <x,y>
This is a little sloppy, mathematically, because I am "fixing" t for
a(t) to be t0, but not fixing t for x(t) or y(t) (so that "time
averages" for x(t) and y(t) can be meaningful and equated to
statistical averages).
Recall that
v(t) = a(t)*y(t) + a(-t)*x(t)
Then:
<v,v> = <(a(t)*y(t) + a(-t)*x(t)), (a(t)*y(t) + a(-t)*x(t))>
Using identities that we can apply to expectation values
<v,v> = (a(t))^2*<y,y> + 2*a(t)*a(-t)*<x,y> + (a(-t))^2*<x,x>
Since <v,v> = <x,x> = <y,y>, we can divide by <v,v> and get to the key
equation of this whole theory:
1 = (a(t))^2 + 2*r*a(t)*a(-t) + (a(-t))^2
Given the normalized correlation measure, we want the above equation
to be true all of the time. If r=0 (completely uncorrelated), one can
see we get a constant-power crossfade:
(a(t))^2 + (a(-t))^2 = 1
If r=1 (completely correlated), one can see that we get a constant-
voltage crossfade:
(a(t))^2 + (a(-t))^2 + 2*a(t)*a(-t) = ( a(t) + a(-t) )^2 = 1
or, assuming a(t) is non-negative,
a(t) + a(-t) = 1 .
______________________________________________________________________
Section 3: Generalizing the crossfade function
Recall that
a(t) = e(t) + o(t)
a(-t) = e(t) - o(t)
and substituting into
(a(t))^2 + (a(-t))^2 + 2*r*a(t)*a(-t) = 1
results in
(e(t) + o(t))^2 + (e(t) - o(t))^2
+ 2*r*(e(t) + o(t))*(e(t) - o(t)) = 1
Blasting through that gets:
(1+r)*(e(t))^2 + (1-r)*(o(t))^2 = 1/2
This means that, if r is measured and known (from the correlation
function) we have the freedom to define either one of e(t) or o(t)
arbitrarily (as long as the even or odd symmetry is kept) and solve
for the other. We can see that square rooting is involved in solving
for either e(t) or o(t) and there is an ambiguity for which sign to
pick. We shall resolve that ambiguity by adding the additional
assumption that the even-symmetry component, e(t), is non-negative.
e(t) = e(-t) >= 0
Given a general and bipolar odd-symmetry component function,
o(t) = -o(-t)
then we solve for the even component (picking the non-negative square
root):
e(t) = sqrt( (1/2)/(1+r) - (1-r)/(1+r)*(o(t))^2 )
The overall crossfade envelope would be
a(t) = e(t) + o(t)
= sqrt( (1/2)/(1+r) - (1-r)/(1+r)*(o(t))^2 ) + o(t)
______________________________________________________________________
Section 4: Implementation:
Given a particular form for the odd part, o(t) (linear or Hann or
Flattened Hann or whatever is your heart's desire), and for a variety
of values of r, ranging from r=0 to r=1, a collection of envelope
functions, a(t), are pre-calculated and stored in memory. Then, when
pitch detection or loop matching is done, a splice displacement that
is optimal is determined, and if autocorrelation of some form is used
in determining a measure of goodness (or seamlessness, using Element's
language) of that loop splice, that autocorrelation is normalized (by
dividing by Rxx(0)) to get r and that value of r is used to choose
which pre-calculated a(t) from the above collection is used for the
crossfade in the splice.
______________________________________________________________________
--
dupswapdrop -- the music-dsp mailing list and website:
subscription info, FAQ, source code archive, list archive, book reviews, dsp
links
http://music.columbia.edu/cmc/music-dsp
http://music.columbia.edu/mailman/listinfo/music-dsp
