on the theory of the Spline16/36/64 resizers

[mikenadia]

@ 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/Survey-%20Interpolation%20Methods%20in%20Medical%20Image%20Processing.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.

[MfA]

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.

[mikenadia]

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.).

[MfA]

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.

[mikenadia]

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 www.cs.sunysb.edu/~mueller/papers/volvis98_Design.pdf
In Appendix, coefficients with the optimal interpolation that is C2 and 4EF (6 filter weights).

[MfA]

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).
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.
May be , I will get more luck with www.cs.sunysb.edu/~mueller/papers/volvis98_Design.pdf
In Appendix, coefficients with the optimal interpolation that is C2 and 4EF (6 filter weights).
Doubt it, but who knows.

[mikenadia]

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.

[MfA]

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).

[DeathTheSheep]

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.
http://img13.imageshack.us/img13/9569/duplicateedge.png
Source: 640x480. splineresize(320,240,32).

[DeathTheSheep]

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.
http://img191.imageshack.us/img191/5451/1005.png
http://img221.imageshack.us/img221/3729/1445.png
Top: spline100, Bottom: spline144 (looks very similar to 36 and 64 too).
[edit]Here's the tar with all test pics (http://gabe.ej.am/tests.tar).

[Gavino]

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).
The documentation is wrong. The 3rd paramater is src_left.
Use taps=32.

[Wilbert]

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.
When i made Spline16W i didn't know what i was doing, so therefor it was faulty. Spline100/Spline144 should be correct though. Looking at your pics I see that Spline100 is sharper than Spline64/Spline144. Strange. I will look at it next week after my exams.

Could you do this test for SplineResize(x,y,taps=xx) too and post the results?

[DeathTheSheep]

@Gavino: Thanks. I should have also looked at the example scripts first. Haste makes waste, indeed.
@Wilbert: Okay, done. I modified the test so it was more extreme: 32 cycles. I also made it a perfect '2xScale' and included the original picture. Updated tests for the cubic spline filters were included as well. In this file (http://gabe.ej.am/test2.zip), all pictures are provided. Those named tX are the natural splines of taps X.

Conclusions: For low even numbers of taps, the behavior of the natural spline (SplineResize) is aberrant much like spline16w. This 'oversharp' problem also does occur with spline100, and surprisingly to some small extent with spline36, which was only revealed after this more excessive repetition size.

[Wilbert]

@DeathTheSheep,

Thanks! I goofed up Spline100Resize. There was a minus sign in the leading coefficients in one of the polynomials that shouldn't be there. Could you try this version:
http://www.geocities.com/wilbertdijkhof/SplineResize_v02.zip
and post a screenshot? I will look at your other pics later.

Could you tell me how you made your pics? Just downsize with a factor of 2 (using Spline) and upsize with a factor of 2 (using Pointresize), and do that 5 resp. 32 times?

[DeathTheSheep]

Image removed, since it was replaced by imageshack with some italian-looking illegal screenshot thing. Suffice it to say, spline100 is back on track.

It appears in-line with the other results from spline64 and up.

As to how I made these pics, yes, I at first did it exactly the way you described 5 times, but then decided to change my strategy: it's more interesting to instead test how accurately the interpolator can then scale up what it just scaled down, essentially a 2-way test. So I ended up doing:
spline100resize(320,240)
spline100resize(640,480)
32 times to produce these exact results.
Now it's even more interesting that spline36 produces such a 'sharp' image, sharper than the rest. Surely the coefficients for spline36 were determined via some other method or source?

Also, the natural spline produces oversharp images at low even tap numbers (2 and 4 most noticeably). When taps is increased too far (beyond the bounds of human reason, I'd say) as was the case with 64 taps, it produces strange artifacts on the bottom of the image.

[Wilbert]

Good!

32 times to produce these exact results.
Now it's even more interesting that spline36 produces such a 'sharp' image, sharper than the rest. Surely the coefficients for spline36 were determined via some other method or source?
No, it is derived in the same way as Spline16/64/100/144 (i've double checked its coefficients). Sorry, i have no explanation for its sharpness.

Also, the natural spline produces oversharp images at low even tap numbers (2 and 4 most noticeably). When taps is increased too far (beyond the bounds of human reason, I'd say) as was the case with 64 taps, it produces strange artifacts on the bottom of the image.
Yes, i noticed that in your pics. The coefficients are calculated on the fly (two times per frame; yes one time for the whole clip should be enough but i don't know how to do that). I will check the calculated coefficients with the exact ones (which can be easily calculated with Maple). Perhaps something goes wrong somewhere.

[mikenadia]

For SplineResize, I think that the use of natural cubic spline is flawed:).
For taps=2 , the natural cubic spline model does not take into account that for abs(x)>=2, h(x)=0, so the natural cubic spline is not C1 continuous at x=2. It should be at least the clamped cubic spline with first derivatives at endpoints=0 (that will lead to a=-0.75). It seems that a=-0.5 is preferred (we should get rid of the C2 continuous condition at abs(x)=1 and replace it with another one (Keys 1981 paper).

[Gavino]

On the other hand, the existing SplineNNResize kernels are not C1 continuous at the joins (x=integer), not even at x=0, yet they seem to give 'reasonable' results.

I think MfA got it right in saying that there is no perfect mathematical solution. It helps to start with a mathematical model that approximates 'reality', but ultimately the results can only be judged by experiment with real images.

[Wilbert]

For taps=2 , the natural cubic spline model does not take into account that for abs(x)>=2, h(x)=0
Yes, it does. That is, it should do that when implemented correctly, but perhaps i did something wrong somewhere. I don't think the artifacts are caused by this. I will check it after my exams.

natural cubic spline is not C1 continuous at x=2
Yes, it's not C1 continuous at the end-points (only C2 continuous): x=+/-support.

[MfA]

Anyone know any blender? It would be nice to have a couple of losslessly encoded short scenes from Elephant's Dream rendered at a couple of resolutions (preferably with a large GCD) and subpixel offsets for objective testing of scalers/interpolators.

Though the default renderer might have too many resolution dependent effects to really work well for benchmarking. Some of the more physically correct pathtracing engines such as Luxrender would be better, but don't know how feasible it would be to use that with the ED animation.

[EpheMeroN]

Just glancing over this thread, are you guys saying Spline16Resize is heavily flawed?

But Spline144Resize is the better choice?

IIRC just going from Spline16 to Spline36 took a HUGE hit on encoding speed. So Spline144Resize must be incredibly slow?

[DeathTheSheep]

No, spline16 as implemented in avisynth seems to work just fine. We were just discussing a[n oddly unbounded] development filter. Unless there's something really meticulous you need to do, spline16 should be fine. Yes, 36 is slower, and 144 much slower still.

In other news, what the hell happened to my image (above)? What the heck is that thing? That's not what I posted at all.

[thewebchat]

I think the real question is regarding the rule 6 violation apparent in the picture from the last page of this thread.

[DeathTheSheep]

I fully agree. Also rules 3, 5, and 7 are being broken in addition to 6.

Trust me, I did not put that picture there. Imageshack must have erased the original, 100b, which was a picture of the fixed spline100 interpolator showing the correct behavior.

I will edit the post to remove all image tags. Are my other pictures still intact, or have they been changed as well? Anybody notice anything?

[DeathTheSheep]

@Wilbert:

Your link is dead-- could you re-upload sometime? I reinstalled my system so my old package is gone...

[Wilbert]

http://www.wilbertdijkhof.com/SplineResize_v02.zip

[bxyhxyh]

It is still in development? Or stopped?

[Wilbert]

It is still in development? Or stopped?
What do you like to see? A while ago i got the following bug report from someone:

I did some testing of various resizers and found that SplineResize() was shown with a left shift.
I've attached a picture and the data I used for testing.

But i haven't looked at that yet.

[turbojet]

I see a noticeable improvement of spline144 over spline100. Would spline196 or even spline256 bring further improvement?

[Katie Boundary]

A rewrite of the OP in plain English would be extremely valuable.

The funny thing about the Catmull-Rom spline is the amount of different methods which lead to it.

Yeah, I've suspected for a while that Catrom is the "true" cubic, as it's the one cubic that (a) always goes through all of the original sample points, and (b) preserves linear gradients

[Wilbert]

Here http://avisynth.nl/index.php/Resampling#Spline_resampler

[Katie Boundary]

Here http://avisynth.nl/index.php/Resampling#Spline_resampler

Unfortunately, that's not noticeably more legible.

[Groucho2004]

Unfortunately, that's not noticeably more legible.
Increase the font size in your browser settings.

[TheFluff]

A friend once said in relation to an algorithm he was trying to explain, "I can say it again with more words, but I can't make it easier to understand".

[FranceBB]

I see a noticeable improvement of spline144 over spline100. Would spline196 or even spline256 bring further improvement?

Not necessarily in terms of visual quality; Spline64Resize is fine for almost any sources quality wise. Having more sample points doesn't necessarily mean more visual quality even 'cause, depending on the sources, it may be really barely noticeable.


Unfortunately, that's not noticeably more legible.


Maybe you could try to tell us what you don't get of that explanation. :)


Increase the font size in your browser settings.


Rotfl.


A friend once said in relation to an algorithm he was trying to explain, "I can say it again with more words, but I can't make it easier to understand".


True.

[luquinhas0021]

Neither spline resize neither Avisynth Bicubic resize are accurate, mathematically, like Bicubic interpolation explained in https://en.wikipedia.org/wiki/Bicubic_interpolation, if I am not wrong, due to, in Bicubic interpolation, to be computed the first and second image derivatives.

[feisty2]

sinc is the most mathematically accurate resampling filter

[madshi]

This all depends a bit on which task we're talking about. But if it's image upscaling, then let me say:

The problem with linear filters is that they don't treat high-contrast edges any differently than smooth areas. If you downscale a "groundtruth" image, then upscale it again, using linear filters, and if you then use PSSR or SSIM to compare the down+upscaled image to the original image, all linear filters produce *very* bad results. So no offense, but IMHO no linear filter is even remotely mathematically accurate, at least when talking about upscaling. If you want accurate results, you need an algorithm which adapts to high contrast edges.

[luquinhas0021]

sinc is the most mathematically accurate resampling filter

Is the most accurate when the sample satisfies the Nyquist-Shannon sampling condition.

This all depends a bit on which task we're talking about. But if it's image upscaling, then let me say:
The problem with linear filters is that they don't treat high-contrast edges any differently than smooth areas. If you downscale a "groundtruth" image, then upscale it again, using linear filters, and if you then use PSSR or SSIM to compare the down+upscaled image to the original image, all linear filters produce *very* bad results. So no offense, but IMHO no linear filter is even remotely mathematically accurate, at least when talking about upscaling. If you want accurate results, you need an algorithm which adapts to high contrast edges.

The comparative, by P.S.N.R and S.S.I.M, between an original H.R image and an upscaled downscaled original H.R image only makes sense if the downscaler that was used be good, near perfect. Whatever be the upscaling, the goodest it be, it can not recover an image that was destroyed by a bad quality downscaler.

Madshi, "high contrast edges" and "smooth regions" can means the local contrast that a pixel has with it m x n neighborhood, means the high and low frequencies that an image has when is applied to it a frequency domain operator or can it means the pixel derivatives (Central operator)?

[madshi]

What I mean is that when you apply linear resampling "across" a strong edge, linear filtering will either blur & bloat (make fatter) the edge or add ringing artifacts, or both, depending on which linear resampling filter you're using. sinc helps avoiding blur and bloating, but adds an atrocious amount of ringing. Resamplers like spline add much less ringing artifacts, but still some, and add blur & bloat.

My explanation is probably less scientific than you may be looking for. I prefer looking at the practical output of algos, instead of theorizing over frequency domain stuff.

[luquinhas0021]

Your explanation helped me.

By "linear upscaling operator", do you want mean those operators that are derived from the solving of a set of p x q linear equations (Or it derived discrete form)?

[Katie Boundary]

A friend once said in relation to an algorithm he was trying to explain, "I can say it again with more words, but I can't make it easier to understand".

I don't need more words, I just need less math... unless those words are an explanation of what the variables mean in the math. For example, "s(x) = sum_n s(n*T) * sinc((x-n*T)/T" might make more sense if someone explained what s, sum_n, n, and T were supposed to mean.

Not necessarily in terms of visual quality; Spline64Resize is fine for almost any sources quality wise. Having more sample points doesn't necessarily mean more visual quality even 'cause, depending on the sources, it may be really barely noticeable.

It's not always even a matter of "barely noticeable". Some algorithms start to look WORSE when the number of taps goes above a certain number. High-tap windowed sinc filters, for example, just add more/worse ringing without increasing sharpness. In the synthetic benchmarks that I ran a few weeks ago, 4-tap Lanczos outperformed both 3-tap and 5-tap, and 3-tap outperformed 5-tap.

Maybe you could try to tell us what you don't get of that explanation. :)

If I had to pick one thing to start with, I'd start with an explanation of how a function can be cubic when it uses more than four control points. I read somewhere that any function going through N control points can see X raised to an exponent as high as N-1...

Is the most accurate when the sample satisfies the Nyquist-Shannon sampling condition.

...which, when dealing with images, is never :)

[TheFluff]

I don't need more words, I just need less math... unless those words are an explanation of what the variables mean in the math. For example, "s(x) = sum_n s(n*T) * sinc((x-n*T)/T" might make more sense if someone explained what s, sum_n, n, and T were supposed to mean.

Did you click and read the wikipedia link that says where the maths come from?

The symbol T = 1/fs is customarily used to represent the interval between samples and is called the sample period or sampling interval. And the samples of function x(t) are commonly denoted by x[n] = x(nT) (alternatively "xn" in older signal processing literature), for all integer values of n. A mathematically ideal way to interpolate the sequence involves the use of sinc functions. Each sample in the sequence is replaced by a sinc function, centered on the time axis at the original location of the sample, nT, with the amplitude of the sinc function scaled to the sample value, x[n]

If I had to pick one thing to start with, I'd start with an explanation of how a function can be cubic when it uses more than four control points. I read somewhere that any function going through N control points can see X raised to an exponent as high as N-1...
You probably misunderstood what you read then, because the order of the polynomials and the number of control points have nothing to do with each other. The cubic spline is called cubic because each piece (the curve between one control point and the next) is expressed as a third order polynomial. http://mathworld.wolfram.com/CubicSpline.html

[Katie Boundary]

Did you click and read the wikipedia link that says where the maths come from?

What wikipedia link?

You probably misunderstood what you read then, because the order of the polynomials and the number of control points have nothing to do with each other.

No, what I read was very explicit and unambiguous about that fact.

The cubic spline is called cubic because each piece (the curve between one control point and the next) is expressed as a third order polynomial. http://mathworld.wolfram.com/CubicSpline.html

Yes, I knew that already. And cubic splines are derived from four control points, which is why they don't need to raise x to any power higher than 3.

[StainlessS]

What wikipedia link?
Presumably post #86.

[Katie Boundary]

Presumably post #86.

Hmmm. I can't find the quoted passage in that article.


EDIT:

I've been able to compare different filter shapes using Desmos graphing calculator, and I'm convinced that 2-tap Lanczos approximates Catrom more closely than any other 2-tap windowed sinc filter (Blackman, Hann, Hamming etc). I'd like to put it up against Spline16 and 2-tap Lagrange, but I have no idea what formulae they use.

[Katie Boundary]

I'm running some side-by-size PSNR tests. There's DEFINITELY something wrong with Spline100. It's performing much worse than literally everything except Linear.

EDIT: something is also wrong with Spline144, though it's not as bad as Spline100. Someone needs to triple-check that the code and coefficients are correct.

EDIT 2: I did a visual check. Spline100 is much blurrier than Spline64 or Spline144.

[Katie Boundary]

In retrospect, the fact that Spline36 is sharper than Spline64 should have warned us that something was very wrong with the entire Spline theory/methodology to begin with. Spline100 and Spline144 just made that fact more obvious. I don't think it's a problem with the code being written incorrectly or the coefficients being calculated incorrectly. It's a Spline problem.