on the theory of the Spline16/36/64 resizers - Doom9's Forum

Welcome to Doom9's Forum, THE in-place to be for everyone interested in DVD conversion.

Before you start posting please read the forum rules. By posting to this forum you agree to abide by the rules.

Go Back Doom9's Forum > Capturing and Editing Video > Avisynth Development

Reload this Page on the theory of the Spline16/36/64 resizers

(追記) (追記ここまで)

Page 1 of 5 1 2 3 > Last »

Thread Tools Search this Thread Display Modes

Old 15th May 2009, 23:54 #1 | Link

Wilbert

Super Moderator

Join Date: Nov 2001

Location: Netherlands

Posts: 6,372

on the theory of the Spline16/36/64 resizers

I contacted the author of Panorama Tools (this is where the Spline16/36/64 appear to come from) and asked him about the coefficient of the Spline polynomials. He sent me a short reply which i have worked out in detail:

Let me first say that the polynomials are not the interpolating polynomials, but they are certain blending polynomials as will be explained below.

Let's consider Spline4 for simplicity. Consider one interpolating (cubic) spline for the interval [0,1]:

Code:

S(x) = a[3]*x^3 + a[2]*x^2 + a[1]*x + a[0] for x in [0,1]

Let's define: y0 = S(0), y1 = S(1), z0 = S''(0), z1 = S''(1). The coefficients (a[j])__j depend on (y0,y1,z0,z1). In fact, the values (a[j])_j are fixed by (y0,y1,z0,z1). Once you know (y0,y1,z0,z1), you can calculate the coefficients (a[j])_j, and thus the polynomial S.

Ok, let's set z0=z1=0. In other words, the second derivatives at the end points are zero. Under this condition (a[j])_j are fixed by (y0,y1).

What happens if you replace y0 by y1 and y1 by y0? In that case the polynomial S will be mirrored at x=1/2, since (1) S is fixed by (y0,y1) and (2) z0=z1. A consequence of this is that:

Code:

S[y0;y1](x) = S[y1;y0](1-x)

since the mapping x |-> 1-x results in the same mirroring of S at x=1/2.

It turns out that S can be expressed as a linear combination of the control points (y0,y1):

Code:

S(x) = w0(x) * y0 + w1(x) * y1

Since w0,w1 blend the points y0,y1 together, they are called blending polynomials (or basis functions). As a result of the boundary conditions we have:

Code:

y0 = S(0) = w0(0) * y0 + w1(0) * y1 => w0(0)=1, w1(0)=0
y1 = S(1) = w0(1) * y0 + w1(1) * y1 => w0(1)=0, w1(1)=1

It's also true that the sum of the blending polynomials is equal to one, that is

Code:

w0(x)+w1(x)=1

but i'm unable to prove that for the general case.

Because of the mirroring property we also have that

Code:

S(x) = w0(1-x) * y1 + w1(1-x) * y0

It follows that

Code:

w1(x) = w0(1-x)
w0(x) = w1(1-x)

Subtracting the segment bias results in

Code:

w1(x) = w0(1-x) -> w0[-x]

getting a symmetrical kernel.

Solving (w0,w1) using Maple:
The boundary conditions result in:

Code:

> eqn:={a0=y0, a3+a2+a1+a0=y1, 2*a2=0,6*a3+2*a2=0};

Solving for (a[j])_j:

Code:

> solve(eqn,{a0,a1,a2,a3});
{a0 = y0, a2 = 0, a3 = 0, a1 = -y0 + y1}

Calculating the coefficients of (y0,y1), that is (w0,w1):

Code:

> a0s:=y0; a1s:=-y0+y1; a2s:=0; a3s:=0;
> S:=a3s*x^3 + a2s*x^2 + a1s*x + a0s;
S:= (-y0 + y1) x + y0
> w0:=coeff(S,y0); w1:=coeff(S,y1);
w0 := -x + 1
w1 := x

Yes, that's the bilinear resizer (because a3=a2=0). I never realized that.

Two additional remarks:

1) In general for Spline k^2, we start with k-1 interpolating polynomials. They are located at (-k/2+1,-k/2+2), ..., (k/2-1,k/2). The bending polynomials are calculated from the polynomial located at [0,1], which is expressed as a linear combination of (y0, ..., y(k-1)). The boundary conditions are:

Code:

y[1](-k/2+1) = y0
y[1](-k/2+2) = y1
y[2](-k/2+2) = y1
...
y[k-2](k/2-1) = y(k-2)
y[k-2](k/2-1) = y(k-2)
y[k-1](k/2) = y(k-1)

and also continuity of first and second derivatives, where the second derivatives of the two endpoints are zero.

I have no idea how to derive a general formula. I can recalculate the known coefficients for Spline16 and Spline36. However for Spline64 I get slightly different ones. So, i assume that the known ones for Spline64 are simply wrong.

edit Wilbert: I made a mistake with Spline64. Its coefficients are correct now.

Last edited by Wilbert; 16th May 2009 at 22:52.

Wilbert is offline Reply With Quote

Wilbert