Welcome to Doom9's Forum, THE inplace 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. 
21st May 2009, 06:55  #43  Link 
Avisynth Developer
Join Date: Jan 2003
Location: Melbourne, Australia
Posts: 3,168

@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] 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 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 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 Code:
y1= 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 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}; 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  
Moderator
Join Date: Nov 2001
Location: Netherlands
Posts: 6,301

Just a quick response,
Quote:
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  
Avisynth language lover
Join Date: Dec 2007
Location: Spain
Posts: 3,380

Quote:
There is no [4,3] segment. For Spline 64, we have eight points, hence seven intervals/polynomials. Quote:
Quote:
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  
Avisynth language lover
Join Date: Dec 2007
Location: Spain
Posts: 3,380

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. 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  
Moderator
Join Date: Nov 2001
Location: Netherlands
Posts: 6,301

Quote:


22nd May 2009, 23:19  #48  Link 
Moderator
Join Date: Nov 2001
Location: Netherlands
Posts: 6,301

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 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 
23rd May 2009, 00:08  #49  Link 
Avisynth language lover
Join Date: Dec 2007
Location: Spain
Posts: 3,380

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  
Moderator
Join Date: Nov 2001
Location: Netherlands
Posts: 6,301

Sorry for the late response.
Quote:
Quote:
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 
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 clearcut 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 
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 Bspline. You can take the pixel values directly as control points, but then the function is non interpolating. To compute a bspline 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 
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 noninterpolating issue and the algorithm looks close to what has been described in this thread.).

4th June 2009, 04:51  #54  Link 
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 bspline 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 bspline 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 bspline interpolation ... but in the end the coefficients are used in a convolution kernel, not for bspline 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 
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 bspline 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 bspline (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  
Registered User
Join Date: Mar 2002
Posts: 1,075

Quote:
Quote:
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 bspline interpolation. Quote:
Last edited by MfA; 4th June 2009 at 17:43. 

5th June 2009, 16:28  #57  Link 
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 
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 
<The VFW Sheep of Death>
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 allinone stop for x264/GCC needs on Windows: Komisar x264 builds! 
20th June 2009, 07:32  #60  Link 
<The VFW Sheep of Death>
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). [edit]Here's the tar with all test pics.
__________________
Recommended allinone stop for x264/GCC needs on Windows: Komisar x264 builds! Last edited by DeathTheSheep; 20th June 2009 at 07:54. 
Thread Tools  Search this Thread 
Display Modes  

