BC-splines with 2C+B=1 are optimal for EWA resampling

[NicolasRobidoux]

Anthony:

I have tested RobidouxSharp (EWA, of course) with a number of images, and I think that if one wants a sharp result, this is hard to beat (at least in the EWA world).

It's arguably better than the sharp Jinc-windowed Jinc ones.

And, amazingly, it gives, in some cases, nearly identical results to the sharp Jinc-windowed Jinc 4, which I like so much, but with less haloing.

I have not done enough testing to be really sure, but it's really promising.

Yes, it is somewhat jaggy. But so are the sharp Jinc-windowed Jinc ones.

[anthony]

The question then becomes, is it worth implementing?

[NicolasRobidoux]

The question then becomes, is it worth implementing?

My current honest opinion is this:

RobidouxSharp is worth implementing. As of now, it is the sharpest EWA that does not fail spectacularly when it fails.

What should go are LanczosSharp and Lanczos2Sharp.

Rationale:

The "maximally sharpened" ones discussed in this thread do well when they do well, but they give worse results than RobidouxSharp when enlarging a natural image which is the result of downsampling with a sharpening scheme (with orthogonal Lanczos 3 or 4 followed by USM?).

There are examples of enlargements of such pictures: http://web.cs.laurentian.ca/nrobidoux/misc/halodemo. Most of the originals (pre-enlargement by 400%) already have haloing, and some of them have noticeable moire. The "maximally sharp" Jinc-windowed Jinc schemes don't do well at all with those. They're not flat out awful, they simply are not worth the expense.

In addition, with 4 lobes or more, you get very annoying ringing with "text like" images (the bullseye test in the above group).

So, the "maximally sharpened" Jinc-windowed Jinc should not be recommended. (I think: I really have not done enough testing across the board to be sure. For one thing, they may be good for slightly blurry images.)

What this means is that the LanczosSharp family should either be based on preserving vertical lines as best one can (like the current Lanczos2Sharp and LanczosSharp) or some other principle, like using blur = r_n/n where n is the number of lobes and r_n is the n'th root of the Jinc function. The latter choice seems reasonable, but it appears to me to be somewhat arbitrary sharpening, possibly too strong.

Which leaves optimization based on vertical/horizontal line preservation.

Depending on the particular way that one decides to preserve vertical/horizontal lines, one generally gets blur values between .97 and .99. This holds for Jinc-windowed Jinc 3 and 4, and I would assume it holds for the higher ones as well. The one exception to this is Jinc-windowed Jinc 2. However, this scheme is almost perfectly emulated by the current Robidoux filter, which by several measures could be argued to be a better scheme. (It certainly is simpler and cheaper.) So, Lanczos2Sharp is not worth keeping.

Now, blur values around .98 have almost no visual impact. So, they are not worth keeping either. Basically, Jinc-windowed Jinc (with at least 3 lobes) is almost "perfect" as it is. Yes, it's on the blurry side, but it's almost as good as can be with vertical/horizontal lines.

My conclusion:

Remove Lanczos2Sharp and LanczosSharp. (And then you don't have side effects with regular orthogonal Lanczos.)

Keep Robidoux.

Add RobidouxSharp. For certain types of images it gives results close to the maximally sharpened Jinc-windowed Jinc 4, but it rings once instead of three times.

Unless: You decide that since Mitchell-Netravali sits pretty much exactly halfway between them, you may as well just use that (as you used to) and get rid of Robidoux* altogether, even though they provide a way of making things sligthly smoother or sharper while staying within the Keys family (you can't do that with blur) which, as discussed earlier in this thread, is special because it minimizes the reconstruction error for affine gradients in EWA, just like it does in orthogonal resampling.

Then, Mitchell-Netravali could be characterized as "just right", and the two Robidoux's hopefully would satisfy mama and papa bear.

In addition, Robidoux and RobidouxSharp are perfectly useable in orthogonal resampling, unlike Lanczos2Sharp and LanczosSharp.

[NicolasRobidoux]

This being said, what the maximally sharpened Jinc-windowed Jinc 4 does well, it does really really well: straighten sharp oblique lines.

[NicolasRobidoux]

Then, maybe it would be wise to wait for the dust to settle. (Although I am quite convinced that RobidouxSharp does what it does quite well and is most likely a better EWA default than Robidoux.)

[anthony]

Okay sounds reasonable. I'll do this when I next get back into programming (day or so).

[NicolasRobidoux]

Anthony:

Actually, just let the dust settle for now. I'll get back to you when, literally, I have a better picture.

I may have a slightly better RobidouxSharp coming up.

And I'd like to figure out whether the poor results of the maximally sharpened Jinc-windowed Jinc with the test picture some Avisynth people like (sharpened downsamples, with pre-existing halos and sometimes moire, hence pushing the Nyquist limit) are truly representative of their strengths and weaknesses. However, this last thing will take a while.

[NicolasRobidoux]

Anthony:

Actually, as far as RobidouxSharp is concerned, the dust has settled.

I wanted to triple check that the above RobidouxSharp C value is also the one that minimizes maximum deviation for an arbitrary (not extreme) value. The Axiom code that checks this is here:

Code: Select all

)cl a

inner x == _
eval( ( (12 - 9 * B - 6 * C) * x * x * x _
        + (-18 + 12 * B + 6 * C) * x * x _
        + (6 - 2 * B) ) / 6, B = 1-2*C )

outer x == _
eval( ( (-B - 6 * C) * x * x * x _
      + (6 * B + 30 * C) * x * x _
      + (-12 * B - 48 * C) * x _
      + (8 * B + 24 * C) ) / 6, B = 1-2*C )

z := inner 0

cr := inner 1

di := outer sqrt 2

denom := z + 4 * ( cr + di )

-- I factored out a factor of 4

l1 := ( sqrt(( cr + di )^2) + sqrt(cr*cr) + sqrt(di*di) ) / denom

draw(l1,C=0...55)

D(l1^2,C)

limit(%,C=(42*sqrt(2)-7)/142)

[ %.leftHandLimit :: EXPR Float, %.rightHandLimit :: EXPR Float ]

Here is a quick explanation of what Robidoux and RobidouxSharp are about in the EWA context:

Somewhat surprisingly, the Keys cubics are the BC-cubics which minimize the error when upsampling linear (a.k.a. affine) gradients aligned with the axes with Clamped EWA. In the orthogonal context, Keys cubics are precisely the ones which reconstruct such gradients exactly. The surprise lies in that they also minimize (without making it zero) the reconstruction error of linear gradients when used radially. (There is a back of the envelope argument that makes this plausible, having to do with the dominant part of the error along grid lines. The surprise is that this very rough argument actually captures the truth.)

Among the Keys cubics, which are defined by either the B value or the C value since Keys cubics satisfy B+2C=1, two pairs of B,C values are special when performing Elliptical Weighted Averaging (and no downsampling is taking place in any direction):

• The Robidoux pair B = (228 - 108 sqrt(2))/199 = 0.37821575509399866, C = (108 sqrt(2) - 29)/398 = 0.31089212245300067
• The RobidouxSharp pair B = (78 - 42 sqrt(2))/71 = 0.2620145123990142, C = (42 sqrt(2) - 7)/142 = 0.3689927438004929

Informally, the Robidoux Keys cubic is the one that best preserves vertical and horizontal features under no-op when resampling with EWA, and the RobidouxSharp Keys cubic is the one which is closest to being interpolatory in the same situation. Being interpolatory is roughly correlated with being "optimally sharp." Overall, EWA Robidoux turns out to be roughly equivalent to (orthogonal) Mitchell, and EWA RobidouxSharp roughly equivalent to (orthogonal) Catmull-Rom. (If you know how EWA works, it should not surprise you to find out that using a BC-cubic as radial function actually gives a scheme which is somewhat sharper than when used orthogonally.)

Specifically, the Robidoux pair gives the unique Keys cubic such that, under no-op, a vertical (resp. horizontal) line with constant colour value will not affect nearby pixel values when resampling with EWA. Consequently, putting a black frame (say) around an image will not change the content of the image except at its four corner pixels when no-op "resampling" (filtering, really) with EWA. There is another characterization of the Robidoux pair: If an image is constant along vertical (resp. horizontal) lines, no-op EWA will not modify it. Mathematically, the Robidoux pair is defined by the property that under no-op the coefficients of the pixels immediately left, right, up and down are twice as large as the coefficients of the nearest pixels in the four diagonal directions. (They have opposite signs.)

The RobidouxSharp pair gives the unique Keys cubic which minimizes the maximum possible deviation under no-op, under the assumption that pixel values are bound to a fixed range (like 0-255). (In the terminology of applied linear algebra, the RobidouxSharp no-op EWA filter is the one that is closest to the identity in the l1-norm, which ensures that as a linear operator it is as close as possible to the identity in l-infinity a.k.a. max operator norm.) It turns out that the RobidouxSharp pair is also the one that minimizes the maximum possible change in a pixel value which is at one of the extremes (e.g., 0 or 255) under no-op. Mathematically, the RobidouxSharp pair is defined by the property that under no-op the coefficients of the pixels immediately left, right, up and down are exactly as large as the coefficients of the nearest pixels in the four diagonal directions. (Again, they have opposite signs.)

The above properties are not only relevant to no-op: When using Clamped EWA, they describe what happens to the values at the original pixel locations whenever there is no downsampling in any direction (that is, when the EWA ellipse is a circle with the minimal radius, minimal radius equal to 2 when using a BC-cubic as radial filter).

That the Mitchell-Netravali pair B=1/3, C=1/3 is pretty close to being halfway between the Robidoux and RobidouxSharp pairs is an example of the strange coincidences surrounding the use of Keys cubics for Elliptical Weighted Averaging, an application for which they would appear to be ill-suited.

(This coincidence could be taken as justification for reverting to Mitchell-Netravali as the default. Then, users know where to go to get something sharper (RobidouxSharp) or smoother (Robidoux). Alternatively, RobidouxSharp could be made the default, and users could then be instructed to "back down" the sharpness by trying Mitchell, Robidoux and Cubic in order, keeping the first one which they considered sufficiently un-aliased. Or else, switch to Jinc Lanczos.)

[NicolasRobidoux]

I'm not going to work on the sharpened Jinc-windowed Jinc for a while. Other things to do.

I do think it is a good idea to remove LanczosSharp and Lanczos2Sharp.

But I'm not 100% sure that they will never come back (with different parameters, of course). Although I suspect they probably should be gone for good.

[anthony]

Thank you for the great description, make the meanings of the various filters quite clear.

I may re-order the RobiduxSharp descriptions slightly so as to put the more 'practical' user-friendly meaning first and the more rigorous mathematical explanation second. But otherwise I'll use them as they stand.

Soon I hope. I really have to get back to the CLI interface (backed off a bit to think about settings).

[NicolasRobidoux]

I rewrote the explanation based on your comments.

But you are totally welcome to edit as you see fit.

[NicolasRobidoux]

...(This coincidence could be taken as justification for reverting to Mitchell-Netravali as the default. Then, users know where to go to get something sharper (RobidouxSharp) or smoother (Robidoux). Alternatively, RobidouxSharp could be made the default, and users could then be instructed to "back down" the sharpness by trying Mitchell, Robidoux and Cubic in order, keeping the first one which they considered sufficiently un-aliased. Or else, switch to Jinc Lanczos.)

A better recommendation, I think:

Keep Robidoux as the default EWA filter.

Recommend the use of Quadratic if one wants more smoothness/no halo, RobidouxSharp if one wants more sharpness. Or a switch to Lanczos (Jinc-windowed Jinc 3).

Rationale:

Not much difference between Mitchell-Netravali and Robidoux. (RobidouxSharp is noticeably sharper.)

IMHO, EWA Cubic smooths too much for almost all uses. Quadratic is a better "one step down." EWA Cubic is "two steps down."

[imaggie]

I would suggest finding another name than "lanczos" for jinc-jinc.

firstly it's confusing because it is not a lanczos filter (sinc-sinc) and secondly out of respect for Lanczos who was a thorough and brilliant mathematician and does not deserve to have his name recycled and given to something he did not do. AFAIK, Lanczos did not propose jinc windowed jinc.

[NicolasRobidoux]

Dear imaggie:

"Lanczos" is an established name for Jinc-windowed Jinc when used as an EWA filter. We did not make it up. It dates back at least to 1993 (Gustafsson's masters thesis).

Although indeed Cornelius Lanczos most likely did not suggest anything else than Sinc-windowed Sinc, the naming of Jinc-windowed Jinc is not random:

In the plane, which is the ("clamped") EWA context, the "ideal" low-pass filter is the Jinc function, just like the "ideal" low-pass filter on the real line is the Sinc function.

C. Lanczos' idea, TTBOMK, was to window the "ideal" low-pass filter with its own first lobe ("self-windowing"). To some extent, the fact that the low pass filter under consideration was the Sinc function is besides the point. Jinc-windowed Jinc is the obvious extension of this idea to the planar (EWA) situation. Hence the name.

P.S. In addition, as mentioned in another thread, Sinc-windowed Sinc is no good for EWA filtering, and Jinc-windowed Jinc barely better for orthogonal filtering. Consequently, users don't lose anything by overloading the name so it automatically picks the appropriate self-windowed "ideal" low-pass filter. Esp. since they actually can do EWA with Sinc-windowed Sinc, and orthogonal filtering with Jinc-windowed Jinc by direct manipulation of the expert settings.

I completely stand by Anthony's decision to substitute Jinc for Sinc in the EWA context and overload the Lanczos filter accordingly. Not only is it practical, TTBOMK it also respects the meaning and history of the term "Lanczos filter."

I of course stand to be corrected. (The above is from memory.)

[anthony]

That is exactly right.

It falls in like with other 'windowed' filters.

If you select a 'Blackman' windowed filter for Orthogonal Resize your get a Blackman-Sinc
But in a EWA (distort) resize you will automatically get a Blackman-Jinc.

The Filter naming for Windowed filters thus automatically translate from Sinc Orthogonal to Jinc EWA filtering.
Lanczos just follows that same scheme but with Sinc-Sinc for Orthogonal, translating to Jinc-Jinc for EWA
as per Gustafsson's thesis.

A PDF of the Thesis is at.... http://www.gson.org/thesis/warping-thesis.pdf

However weather EWA Lanczos should actually be Sinc-Jinc I had no other guide but that thesis. From the brevity of that section of his thesis I don't think even Gustafsson did a lot of thinking on this topic, as he was more concerned with distortion techniques rather than the filter.

If Sinc-Jinc does prove to be better than Jinc-Jinc for EWA filtering (which does not appear to be the case) I would gladly modify that definition.


Also at the time EWA filtering was implemented (and for 3 years following) had a MAJOR BUG, (selection of HQEWA rather than 'Clamped-EWA' that cause No-Op distortions to be extremely Fuzzy. Paul Heckbert's papers was the source of this rather horrible choice, but as he was the one to publish the source for the now almost universally accepted code for orthogonal resizing of images (and few others explained well), I took this a gospel. Nicholas was able to provide me with the code (and mathematics) to switch to a Clamped-EWA algorithm (HQEWA is still in source but undefined) and with that improvement allowed me to locate another bug (a sign error) in the code.

In summery: When the decision was made for EWA Lanczos to be a jinc-jinc, a logical (published) definition was taken. But 'eyeball' testing was not practical for three more years following that decision due to the use of a slightly different EWA algorithm, that was very very fuzzy at near unity scales, though worked well for extreme downsampling required for perspective distortions.

Thanks to Nicholas, distortions in IM are now one of the best available, which can and does produce better resize results that traditional orthogonal resizing.