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.

 Doom9's Forum on the theory of the Spline16/36/64 resizers
 Register FAQ Calendar Search Today's Posts Mark Forums Read

20th May 2009, 22:25   #41  |  Link
Registered Developer

Join Date: Sep 2006
Posts: 9,137
Quote:
 Originally Posted by tetsuo55 Are you using that one in MadVR?
Nope.

20th May 2009, 22:47   #42  |  Link
tetsuo55
MPC-HC Project Manager

Join Date: Mar 2007
Posts: 2,317
Quote:
too bad, i hope you will

 21st May 2009, 06:55 #43  |  Link IanB Avisynth Developer   Join Date: Jan 2003 Location: Melbourne, Australia Posts: 3,169 @Wilbert, From your post 7 you missed out on the polynomial for the [-4,-3]segment. Also some of the constraints were not present. I have marked these in Red. Also some of the constraints you have expressed in negated form, these I have adjusted these and marked them in Blue, the original expression is above in Light Gray. Code: Y_I(x) = h3*x3 + h2*x2 + h1*x + h0, for x in [-4,-3] Y_I(x) = g3*x3 + g2*x2 + g1*x + g0, for x in [-3,-2] Y_I(x) = f3*x3 + f2*x2 + f1*x + f0, for x in [-2,-1] Y_I(x) = e3*x3 + e2*x2 + e1*x + e0, for x in [-1,0] Y_I(x) = a3*x3 + a2*x2 + a1*x + a0, for x in [0,1] Y_I(x) = b3*x3 + b2*x2 + b1*x + b0, for x in [1,2] Y_I(x) = c3*x3 + c2*x2 + c1*x + c0, for x in [2,3] Y_I(x) = d3*x3 + d2*x2 + d1*x + d0, for x in [3,4] Analysing the set of constraints it appears that half are redundant, this make sense as the overall function is symmetrical about zero. Extracting the sets of constraint equations to do with each polynomial and pairing it with it's reflection about zero gives :- Equations for ai & ei Code: y2 = -e3 + e2 - e1 + e0 y4 = a3 + a2 + a1 + a0 y3 = e0 y3 = a0 3*f3 - 2*f2 + f1 = 3*e3 - 2*e2 + e1 -3*e3 + 2*e2 - e1 = -3*f3 + 2*f2 - f1 3*a3 + 2*a2 + a1 = 3*b3 + 2*b2 + b1 -6*f3 + 2*f2 = -6*e3 + 2*e2 6*a3 + 2*a2 = 6*b3 + 2*b2 e1 = a1 2*e2 = 2*a2 Equations for bi & fi Code: y1 = -8*f3 + 4*f2 - 2*f1 + f0 y5 = 8*b3 + 4*b2 + 2*b1 + b0 y2 = -f3 + f2 - f1 + f0 y4 = b3 + b2 + b1 + b0 12*g3 - 4*g2 + g1 = 12*f3 - 4*f2 + f1 -12*f3 + 4*f2 - f1 = -12*g3 + 4*g2 - g1 12*b3 + 4*b2 + b1 = 12*c3 + 4*c2 + c1 -12*g3 + 2*g2 = -12*f3 + 2*f2 12*b3 + 2*b2 = 12*c3 + 2*c2 3*f3 - 2*f2 + f1 = 3*e3 - 2*e2 + e1 -3*e3 + 2*e2 - e1 = -3*f3 + 2*f2 - f1 3*a3 + 2*a2 + a1 = 3*b3 + 2*b2 + b1 -6*f3 + 2*f2 = -6*e3 + 2*e2 6*a3 + 2*a2 = 6*b3 + 2*b2 Equations for ci & gi Code: y0 = -27*g3 + 9*g2 - 3*g1 + g0 y6 = 27*c3 + 9*c2 + 3*c1 + c0 y1 = -8*g3 + 4*g2 - 2*g1 + g0 y5 = 8*c3 + 4*c2 + 2*c1 + c0 -27*g3 + 6*g2 + g1 = -27*h3 + 6*h2 + h1 27*c3 + 6*c2 + c1 = 27*d3 + 6*d2 + d1 -18*g3 + 2*g2 = -18*h3 + 2*h2 18*c3 + 2*c2 = 18*d3 + 2*d2 -18*g3 + 2*g2 = 0 18*c3 + 2*c2 = 0 12*g3 - 4*g2 + g1 = 12*f3 - 4*f2 + f1 -12*f3 + 4*f2 - f1 = -12*g3 + 4*g2 - g1 12*b3 + 4*b2 + b1 = 12*c3 + 4*c2 + c1 -12*g3 + 2*g2 = -12*f3 + 2*f2 12*b3 + 2*b2 = 12*c3 + 2*c2 Equations for di & hi Code: y-1= -64*h3 + 16*h2 - 4*h1 + h0 y7 = 64*d3 + 16*d2 + 4*d1 + d0 y0 = -27*h3 + 9*h2 - 3*h1 + h0 y6 = 27*d3 + 9*d2 + 3*d1 + d0 -24*h3 + 2*h2 = 0 24*d3 + 2*d2 = 0 -27*g3 + 6*g2 + g1 = -27*h3 + 6*h2 + h1 27*c3 + 6*c2 + c1 = 27*d3 + 6*d2 + d1 -18*g3 + 2*g2 = -18*h3 + 2*h2 18*c3 + 2*c2 = 18*d3 + 2*d2 Thus the system should be solvable with just this half of the equations. Code: > eqn:={ > y3 = a0, > y4 = a3 + a2 + a1 + a0, > y4 = b3 + b2 + b1 + b0, > y5 = 8*b3 + 4*b2 + 2*b1 + b0, > y5 = 8*c3 + 4*c2 + 2*c1 + c0, > y6 = 27*c3 + 9*c2 + 3*c1 + c0, > y6 = 27*d3 + 9*d2 + 3*d1 + d0, > y7 = 64*d3 + 16*d2 + 4*d1 + d0, > 3*a3 + 2*a2 + a1 = 3*b3 + 2*b2 + b1, > 12*b3 + 4*b2 + b1 = 12*c3 + 4*c2 + c1, > 27*c3 + 6*c2 + c1 = 27*d3 + 6*d2 + d1, > 6*a3 + 2*a2 = 6*b3 + 2*b2, > 12*b3 + 2*b2 = 12*c3 + 2*c2, > 18*c3 + 2*c2 = 18*d3 + 2*d2, > 18*c3 + 2*c2 = 0, > 24*d3 + 2*d2 = 0}; Can you please confirm this with your Maple Wilbert. Also I think this constraint is also available 12*b3 + 2*b2 = 0, not sure about the 12 maybe it should be 9, my brain is quite rusty on this stuff. Also we know a0=1 and b0,c0,d0=0 so we may be able to reduce the equation clutter even more, making it feasible to deduce spline100, spline144, spline196 and spline256 coefficients
21st May 2009, 10:19   #44  |  Link
Wilbert
Moderator

Join Date: Nov 2001
Location: Netherlands
Posts: 6,332
Just a quick response,
Quote:
 From your post 7 you missed out on the polynomial for the [-4,-3]segment.
The author of Panorama Tools doesn't define a polynomial on [-4,-3]. If you do it correctly (using 8 splines, setting yj=0 except at the center), you will get this one: http://forums.virtualdub.org/index.p...&f=11&t=17212& (see post: May 20 2009, 02:44 AM). I don't see any difference with the existing Spline64 though.

Getting the spline100, spline144, spline196 and spline256 coefficients (using the correct number of splines) is trivial in Maple. I will post them tomorrow. It's also possible to calculate an arbitrary one. If i've time i will try to implement that. I will comment on your boundary conditions later.

21st May 2009, 10:30   #45  |  Link
Gavino
Avisynth language lover

Join Date: Dec 2007
Location: Spain
Posts: 3,380
Quote:
 Originally Posted by IanB @Wilbert, From your post 7 you missed out on the polynomial for the [-4,-3]segment.
No, Wilbert is correct.
There is no [-4,-3] segment. For Spline 64, we have eight points, hence seven intervals/polynomials.
Quote:
 Also I think this constraint is also available 12*b3 + 2*b2 = 0, not sure about the 12 maybe it should be 9, my brain is quite rusty on this stuff.
Can you say where this constraint comes from?
Quote:
 Also we know a0=1 and b0,c0,d0=0 so we may be able to reduce the equation clutter even more, making it feasible to deduce spline100, spline144, spline196 and spline256 coefficients
If you use a tool like Maple, does the equation clutter matter?
Unless the tool has a limit on the size of equations it can solve, isn't it just a matter of following Wilbert's method with the appropriate number of polynomials?

21st May 2009, 11:16   #46  |  Link
Gavino
Avisynth language lover

Join Date: Dec 2007
Location: Spain
Posts: 3,380
Quote:
 Originally Posted by Wilbert The author of Panorama Tools doesn't define a polynomial on [-4,-3]. If you do it correctly (using 8 splines, setting yj=0 except at the center), you will get this one: http://forums.virtualdub.org/index.p...&f=11&t=17212& (see post: May 20 2009, 02:44 AM). I don't see any difference with the existing Spline64 though.
After looking at the vdub forum thread, I think there is some confusion over the underlying process. Your method (from Panorama tools) fits a spline through the sample points and then derives the filter kernel from the resulting blending polynomials. The approach suggested by phaeron derives the kernel itself as a spline. It's not clear to me which is more 'correct', or if there is an equivalence between the two approaches at some level.

21st May 2009, 11:26   #47  |  Link
Wilbert
Moderator

Join Date: Nov 2001
Location: Netherlands
Posts: 6,332
Quote:
 After looking at the vdub forum thread, I think there is some confusion over the underlying process. Your method (from Panorama tools) fits a spline through the sample points and then derives the filter kernel from the resulting blending polynomials. The approach suggested by phaeron derives the kernel itself as a spline.
Yes, i know I should have made that more clear in my post above.

 22nd May 2009, 23:19 #48  |  Link Wilbert Moderator   Join Date: Nov 2001 Location: Netherlands Posts: 6,332 Spline100: Code: > w0:=coeff(w,y0); w1:=coeff(w,y1); w2:=coeff(w,y2); w3:=coeff(w,y3); w4:=coeff(w,y4); 3 209 2 362 w0 := 1/153 x - ----- x + ----- x 13515 40545 3 418 2 724 w1 := - 2/51 x + ---- x - ----- x 4505 13515 3 1672 2 2896 w2 := 8/51 x - ---- x + ----- x 4505 13515 10 3 1254 2 724 w3 := - -- x + ---- x - --- x 17 901 901 61 3 9893 2 w4 := -- x - ---- x - 1/13515 x + 1 51 4505 Spline144: Code: > w0:=coeff(w,y0); w1:=coeff(w,y1); w2:=coeff(w,y2); w3:=coeff(w,y3); w4:=coeff(w,y4); w5:=coeff(w,y5); 3 2340 2 1351 w0 := - 1/571 x + ------ x - ------ x 564719 564719 3 14040 2 8106 w1 := 6/571 x - ------ x + ------ x 564719 564719 24 3 56160 2 32424 w2 := - --- x + ------ x - ------ x 571 564719 564719 90 3 210600 2 121590 w3 := --- x - ------ x + ------ x 571 564719 564719 336 3 786240 2 453936 w4 := - --- x + ------ x - ------ x 571 564719 564719 683 3 1240203 2 w5 := --- x - ------- x - 3/564719 x + 1 571 564719 The weights sum up to one for both splines (including their symmetric counterparts), so i suspect that they are correct.
23rd May 2009, 00:08   #49  |  Link
Gavino
Avisynth language lover

Join Date: Dec 2007
Location: Spain
Posts: 3,380
Quote:
 Originally Posted by Wilbert Spline100: ... Spline144: ...
From the way these are expressed, I assume that they are calculated using the 'Panorama Tools' method (as for existing Spline16, etc), rather than the alternative method of fitting a spline through the kernel crossing points.

Any thoughts on the relative merits of the two approaches? It is clear that they give different coefficients and I suspect they are fundamentally different in nature, although they may both be equally valid as approximations to a sinc filter.

1st June 2009, 14:31   #50  |  Link
Wilbert
Moderator

Join Date: Nov 2001
Location: Netherlands
Posts: 6,332
Sorry for the late response.

Quote:
 From the way these are expressed, I assume that they are calculated using the 'Panorama Tools' method (as for existing Spline16, etc), rather than the alternative method of fitting a spline through the kernel crossing points.
Yes, indeed.

Quote:
 Any thoughts on the relative merits of the two approaches? It is clear that they give different coefficients and I suspect they are fundamentally different in nature, although they may both be equally valid as approximations to a sinc filter.
The coefficients seem to be close to each other (well i only looked at Spline64, dunno about the other ones). I implemented both resizers here: http://www.geocities.com/wilbertdijk...Resize_v01.zip

For the alternate method you can choose the number of "taps". I leave it up to you guys to find and report about the differences

 4th June 2009, 00:58 #51  |  Link mikenadia Registered User   Join Date: Nov 2007 Posts: 246 @ Gavino It is possible that the Panorama method is referred as the "cubic spline interpolator" and the alternate one as "the cubic convolution" (and different names in the following paper). If this is true , Maeland is favoring the Panorama method in ] E. Maeland: On the Comparison of Interpolation Methods. IEEE Trans. Medical Imag., vol. 7, no. 3, Sep. 1988. [MMMY97] T. Möller, R. Machiraju, K. Mueller, R. Yagel:. I do not have access to it (just the abstract). But it might not be that clear-cut for low radius ( Mitchell_Netravali might be close to a combination of the two). Panorama method: better usually but problem "at the edges" (p13 H) in the following paper). Alternate method: does not have a problem " at the edges" (p14 I) in the same paper) . A combination of the two looks to be the solution. http://ee.sharif.edu/~miap/Files/Sur...Processing.pdf @ all Last call on the subject, it would be interesting to see if the problem " at the edges " of the Panorama is not due to boundary conditions and avoid a combination of the two methods. Last edited by mikenadia; 4th June 2009 at 03:43.
 4th June 2009, 03:57 #52  |  Link MfA Registered User   Join Date: Mar 2002 Posts: 1,075 No, in "On the Comparison of Interpolation Methods" they are talking about cubic spline interpolation where control points are not recalculated for each segment but there is 1 control point per pixel. A true B-spline. You can take the pixel values directly as control points, but then the function is non interpolating. To compute a b-spline while keeping it interpolating you have to consider the entire "infinite" signal (basically the entire scanline) to compute the control points. At the time of that paper they didn't know how to do that efficiently (you basically had to solve a huge set of linear equations). Unser later discovered an efficient method though. Last edited by MfA; 4th June 2009 at 04:18.
 4th June 2009, 04:36 #53  |  Link mikenadia Registered User   Join Date: Nov 2007 Posts: 246 Thanks. but in that paper http://ee.sharif.edu/~miap/Files/Sur...Processing.pdf , is the alternate method ,the one in page 14 I) and the Panorama in page 13 H) ( I think they are taking care of that non-interpolating issue and the algorithm looks close to what has been described in this thread.).
 4th June 2009, 04:51 #54  |  Link MfA Registered User   Join Date: Mar 2002 Posts: 1,075 What exactly do you mean with Panorama method? Do you mean the interpolation with the Panorama convolution kernel as implemented in Avisynth? Because Method H in that paper is not that, as they say "the kernel is infinite" ... you can fundamentally not implement b-spline interpolation with a finite convolution kernel (which is what all the standard interpolators in Avisynth use). That is why in all the tables the support of for b-spline interpolation is given as "...", Spline16 has a support of 4x4 in 2D. As I said before, there might be some similarities in the math used to compute coefficients for the Panorama kernel and b-spline interpolation ... but in the end the coefficients are used in a convolution kernel, not for b-spline interpolation. You are attributing far more credit to it's methodology than it deservers. It works well despite of the math used, not thanks to it. The only kernel in the paper which could be Spline16 would be the Lagrange one (piecewise cubic, not C1 continuous, same as Spline16) but that one doesn't quite fit either. Last edited by MfA; 4th June 2009 at 05:51.
 4th June 2009, 12:08 #55  |  Link mikenadia Registered User   Join Date: Nov 2007 Posts: 246 Beginning to understand. Regarding Panorama convolution kernel as implemented in avisynth, are you saying that it should be discarded because you cannot implement b-spline interpolation with a finite convolution kernel or that if it looks better, let it be. Is the alternate method fundamentally correct, should it be renamed ( to Cubic64Resize...). Am I right in thinking that the difference between the b-spline (infinite support) and the Panorama method (finite support) is "those boundary conditions". MfA, if it makes sense to implement it , can you help to understand the Unser algo for a "true" spline interpolation? Is it this one? (p 7) bigwww.epfl.ch/publications/thevenaz0002.pdf May be , I will get more luck with http://www.cs.sunysb.edu/~mueller/pa...s98_Design.pdf In Appendix, coefficients with the optimal interpolation that is C2 and 4EF (6 filter weights). Last edited by mikenadia; 5th June 2009 at 16:28.
4th June 2009, 17:04   #56  |  Link
MfA
Registered User

Join Date: Mar 2002
Posts: 1,075
Quote:
 Originally Posted by mikenadia Am I right in thinking that the difference between the b-spline (infinite support) and the Panorama method (finite support) is "those boundary conditions".
Not really. Also poor performance of b-spline at the edges is probably partly caused by the choice of edge extension (mirroring doesn't work well on gradients for obvious reasons, doing say 8 pixels of point symmetric edge extension before doing the normal interpolation would probably help).
Quote:
 MfA, if it makes sense to implement it , can you help to understand the Unser algo for a "true" spline interpolation? Is it this one? (p 7) bigwww.epfl.ch/publications/thevenaz0002.pdf
Yes, that's the one ... they also have an implementation :
http://bigwww.epfl.ch/thevenaz/interpolation/

As for the math, meh ... too much work, I understand the implementation though They use 2 IIR filters, one right to left and one left to right ... after that you can use the resulting coefficients in plain b-spline interpolation.
Quote:
 May be , I will get more luck with http://www.cs.sunysb.edu/~mueller/pa...s98_Design.pdf In Appendix, coefficients with the optimal interpolation that is C2 and 4EF (6 filter weights).
Doubt it, but who knows.

Last edited by MfA; 4th June 2009 at 17:43.

 5th June 2009, 16:28 #57  |  Link mikenadia Registered User   Join Date: Nov 2007 Posts: 246 Thanks, MfA. Efficient Computation of the coefficients (weights) using " adapted" Horner's rule (13 % gain overall speed over standard Horner for r=2) in http://wscg.zcu.cz/wscg2004/Papers_2004_Short/J47.pdf. Described only for alternate method but can be adapted for the Panorama method. Last edited by mikenadia; 6th June 2009 at 15:53.
 5th June 2009, 16:41 #58  |  Link MfA Registered User   Join Date: Mar 2002 Posts: 1,075 Weight computation is not really an issue for resizing, at least not the way Avisynth does it ... it's amortized over all the scanlines, so it's only a very small part of the total runtime (this is not the same as the lookup method in that paper BTW). Last edited by MfA; 5th June 2009 at 16:43.
 20th June 2009, 06:41 #59  |  Link DeathTheSheep     Join Date: Dec 2004 Location: Deathly pasture of VFW Posts: 1,149 Regarding your SplineResize_v01.zip, increasing the number of taps for the splineResize function causes the frame to shift further and further to the left, duplicating the pixels of the final column. Source: 640x480. splineresize(320,240,32). __________________ Recommended all-in-one stop for x264/GCC needs on Windows: Komisar x264 builds!
 20th June 2009, 07:32 #60  |  Link DeathTheSheep     Join Date: Dec 2004 Location: Deathly pasture of VFW Posts: 1,149 Okay, I did some tests of the other spline filters via avisynth on the same clip. Methodology was to sequentially downscale and upscale the frame using the same filter for 5 repetitions, then look at the quality of the resulting image. I know this test isn't accurate or orthodox, but it has been done in the past and has really clued me on which of the splines were problematic in the past (as was the case with spline16w [wilbert] from an older thread). Also, sizes of compressed clips (x264) and png screenshots served as an even cruder means of comparing "sharpness." Conclusion: Is there a problem with spline100resize? The image it produces is far too sharp (and filesize too big) compared to the other (working?) filters. All of the others (except spline16) were similar in visual appearance, as is expected from spline36+ in terms of the law of diminishing returns to how 'accurately' the interpolator can resize an image (yes, I used the two words together). See the pics below. Remember, spline16w was verified to have a coefficient problem in the past, and it looks as if spline100 is following suit (though to a lesser extent). Of course, this anomalous problem could be reversed: if the splines are supposed to become increasingly sharp, then spline144 clearly isn't sharp enough! But I somehow doubt this to be the case. Top: spline100, Bottom: spline144 (looks very similar to 36 and 64 too). Here's the tar with all test pics. __________________ Recommended all-in-one stop for x264/GCC needs on Windows: Komisar x264 builds! Last edited by DeathTheSheep; 20th June 2009 at 07:54.