Sigmoidized Ginseng (pronounced "Jinc-Sinc") resampling

[NicolasRobidoux]

Nice to see the idea of "deblurring" kernels instead of using them "straight up" (which of course was in IM way before I got involved, but was not used much I think) exploited to good effect.
As some of you know, I've been pushing the idea that there are "special" deblurs that should be used. I have been wondering, however, whether these special deblurs don't "overfit" the property they are designed for, and whether, actually, deblurs that are close but not equal to the "rigidly optimized" values may be better.
Hyllian's "perceptual blur tweaking" is aligned with this musing. Note however that, if I understand correctly (I've not looked carefully at the code https://github.com/libretro/common-shaders) but if you enlarge by fixed ratios, the game changes a lot. Method tweaking needs to be done way more carefully when you allow arbitrary enlargement ratios (not only, say, 4x, but 1.87928 or 7.31428x). The reason is that if you keep the alignment consistent you only ever use a few values of the function that defines the weights (you use a small LUT without interpolation).

[NicolasRobidoux]

Sergio (Hyllian): One last thing: Your choice to limit yourself to diameter 2.5 is reasonable, the other components of your approach also reasonable (at least in what I understand your context is) and the results you showed look good. I won't be offended if you ignore my advice. Good luck!

[NicolasRobidoux]

P.S. An example of "rigid optimization" concerns the fact that, when used in an EWA (Elliptical Weighted Averaging) resampler, the Keys splines are the BC-splines that most accurately interpolate linear gradients (just like they do when used in a tensor, that is, "orthogonal", way). This has motivated my advice of using Keys splines for EWA resampling. (The Robidoux, RobidouxSharp and RobidouxSoft splines are Keys cubics which are further "rigidly optimized".)
However, this property ("reproduce linear gradients accurately") may make more sense in the world of solving partial differential equations than in resampling, which basically caters to the HVS (Human Visual System). I've seen examples of knowledgeable people using different BC-splines than the Keys ones for image resampling. Mathias Rauen (madshi), the creator of the fantastic madVR video renderer, uses a family of BC-splines that are quite far from the Keys ones; and in the source code of common-shaders I see that Sergio Barbosa (Hyllian) empirically chose a non-Keys BC-spline which is nonetheless close to the Robidoux one.
All this points to a theme: Top notch image resampling cannot be blindly assembled from pieces that are individually optimized or come from isolated "rules of thumb" that concern only one stage of the toolchain, no matter how well tested in a test tube.
I still believe that a killer general purpose image resampler can be put together without relying on neural networks or similar approaches (a la NNEDI3, for example). However, a killer upsampler, downsampler or "warper" needs to be assembled as a complete system: as much attention needs to be paid to how the pieces fit together than to the individual components. In other words, this is an engineering, not a math, problem. (A mathematician myself, I certainly don't relish this last statement.)
-----
Let me put this another way:
Mathematical theorems and back of the envelope computations and heuristics can guide the construction of a great image resampler, and certainly help in staying away from horrible ones. But in and by themselves, they are not enough. So, cut the "Sinc is the ideal image interpolation kernel" nonsense.

[Hyllian]

Nice to see the idea of "deblurring" kernels instead of using them "straight up" (which of course was in IM way before I got involved, but was not used much I think) exploited to good effect.
As some of you know, I've been pushing the idea that there are "special" deblurs that should be used. I have been wondering, however, whether these special deblurs don't "overfit" the property they are designed for, and whether, actually, deblurs that are close but not equal to the "rigidly optimized" values may be better.
Hyllian's "perceptual blur tweaking" is aligned with this musing. Note however that, if I understand correctly (I've not looked carefully at the code https://github.com/libretro/common-shaders) but if you enlarge by fixed ratios, the game changes a lot. Method tweaking needs to be done way more carefully when you allow arbitrary enlargement ratios (not only, say, 4x, but 1.87928 or 7.31428x). The reason is that if you keep the alignment consistent you only ever use a few values of the function that defines the weights (you use a small LUT without interpolation).

Hi, Nicolas, which specific "deblurring" shader are you talking about?

Sergio (Hyllian): One last thing: Your choice to limit yourself to diameter 2.5 is reasonable, the other components of your approach also reasonable (at least in what I understand your context is) and the results you showed look good. I won't be offended if you ignore my advice. Good luck!

The advice about EWA with Keys cubic? I have an implementation of BC cubic family in shader format, so I intend to integrate it with cyindrical coordinates to see what is the output. I don't understand very well EWA to implement it someway.

P.S. An example of "rigid optimization" concerns the fact that, when used in an EWA (Elliptical Weighted Averaging) resampler, the Keys splines are the BC-splines that most accurately interpolate linear gradients (just like they do when used in a tensor, that is, "orthogonal", way). This has motivated my advice of using Keys splines for EWA resampling. (The Robidoux, RobidouxSharp and RobidouxSoft splines are Keys cubics which are further "rigidly optimized".)
However, this property ("reproduce linear gradients accurately") may make more sense in the world of solving partial differential equations than in resampling, which basically caters to the HVS (Human Visual System). I've seen examples of knowledgeable people using different BC-splines than the Keys ones for image resampling. Mathias Rauen (madshi), the creator of the fantastic madVR video renderer, uses a family of BC-splines that are quite far from the Keys ones; and in the source code of common-shaders I see that Sergio Barbosa (Hyllian) empirically chose a non-Keys BC-spline which is nonetheless close to the Robidoux one.
All this points to a theme: Top notch image resampling cannot be blindly assembled from pieces that are individually optimized or come from isolated "rules of thumb" that concern only one stage of the toolchain, no matter how well tested in a test tube.
I still believe that a killer general purpose image resampler can be put together without relying on neural networks or similar approaches (a la NNEDI3, for example). However, a killer upsampler, downsampler or "warper" needs to be assembled as a complete system: as much attention needs to be paid to how the pieces fit together than to the individual components. In other words, this is an engineering, not a math, problem. (A mathematician myself, I certainly don't relish this last statement.)
-----
Let me put this another way:
Mathematical theorems and back of the envelope computations and heuristics can guide the construction of a great image resampler, and certainly help in staying away from horrible ones. But in and by themselves, they are not enough. So, cut the "Sinc is the ideal image interpolation kernel" nonsense.

I have the intention to combine a pure pixel art algorithm (xBR) with a pure linear one (a good one with cylindrical coordinates), so that it keeps good textures at nature scenes and a high edge care. I have already tried it before and released a shader called xBR-hybrid, which combine xBR with a very simple reverse anti-aliasing filter. The problem with this combination is that the transition between algorithms isn't seamless, there's too many discontinuities.

[NicolasRobidoux]

Nice to see the idea of "deblurring" kernels instead of using them "straight up" (which of course was in IM way before I got involved, but was not used much I think) exploited to good effect.
As some of you know, I've been pushing the idea that there are "special" deblurs that should be used. I have been wondering, however, whether these special deblurs don't "overfit" the property they are designed for, and whether, actually, deblurs that are close but not equal to the "rigidly optimized" values may be better.
Hyllian's "perceptual blur tweaking" is aligned with this musing. Note however that, if I understand correctly (I've not looked carefully at the code https://github.com/libretro/common-shaders) but if you enlarge by fixed ratios, the game changes a lot. Method tweaking needs to be done way more carefully when you allow arbitrary enlargement ratios (not only, say, 4x, but 1.87928 or 7.31428x). The reason is that if you keep the alignment consistent you only ever use a few values of the function that defines the weights (you use a small LUT without interpolation).

Hi, Nicolas, which specific "deblurring" shader are you talking about?

You using

Code: Select all

weights[4*(j+1)+k+1] = sinc(WA*dist(j-0.25, k-0.25))*sinc(WB*dist(j-0.25, k-0.25));

with WA non-integer is an example of "deblurring". My own EWA LanczosSharp is an example of "deblurring" as well. In general, it means not sticking to the scaling of the filter kernel suggested by a literal reading of sampling (or interpolation, as in using BC-spline weights over a region of with extent different from 4) theory. When the filter kernel's extent is "shrunk". This is what I (and others) have found the most useful "change of scaling". (Widening the extent of the kernel by "stretching" it generally "blurs" the result.)
Makes sense?

[NicolasRobidoux]

EWA (when doing pure enlargement) in a nutshell:
Let the 1D kernel function be

Code: Select all

f(r)

This is a univariate function: 1 input, 1 output, both real numbers.
The unnormalized weight of the input pixel (i,j) at location (x,y) is

Code: Select all

v_{i,j} = f(r_{i,j})

where

Code: Select all

r_{i,j} = sqrt((x-i)^2+(y-j)^2)

In other words, the weight associated with an input pixel depends only on the distance to the sampling point.
The normalized weight is

Code: Select all

w_{i,j} = v_{i,j}/sum_{i,j}v_{i,j}

This normalization ensures that patches with constant color values are enlarged into like patches. You know about this already.
Conceptually, EWA is actually simpler than tensor (orthogonal) methods. However, they generally cannot be performed by doing two independent passes. This is what makes them more expensive.

P.S. If you are downsampling (resizing down, keeping the aspect ratio), you do the same except that the radius of the disc is enlarged by the ratio between the pixel dimensions in the original and the downsampled image. You then stretch the weighting function so it fills this disc, which is the same as using the above function with r equal to the distance divided by the ratio (so that if you are resizing by half, you use r = distance / 2.

If you are changing the aspect ratio, it is a bit more complicated because you are using an ellipse with axes aligned with the vertical and horizontal, and using a distance function appropriate for this ellipse. Basically you scale (x-i) and (y-j) independently instead of with the same scaling, so that your weight is stretched over the ellipse instead like it is over the larger disc when you downsample keeping the aspect ratio.

[NicolasRobidoux]

The advice about EWA with Keys cubic? I have an implementation of BC cubic family in shader format, so I intend to integrate it with cyindrical coordinates to see what is the output.

I think you may get good mileage out of EWA with Keys cubics, and playing with the one parameter that's left (because B+2C=1, setting either B or C automatically sets the other). You may also use the full range of BC-splines, instead of sticking to Keys. But if I was to choose one blindly, I'd pick a Keys one for the reason I gave above.
I however am not certain that this is the best choice. Same with, say, EWA Quadratic or Quadratic-Jinc. All this advice is off the top of my head.
Given that I now know that you are OK with a disc of diameter 5, there may be a better choice than EWA Keys or Quadratic. However, these are simple and solid performers.
What I'd suggest depends on how much you loathe haloing, and I'd need to spend a bit of time thinking and looking through my notes.
-----
I also think that you may find Nohalo-LBB to your liking. The first incarnation of Nohalo ("Nohalo-bilinear") was actually programmed in HLSL. But it's a tricky scheme to program cheaply. And again this is off the top of my head.

[NicolasRobidoux]

I have the intention to combine a pure pixel art algorithm (xBR) with a pure linear one (a good one with cylindrical coordinates), so that it keeps good textures at nature scenes and a high edge care. I have already tried it before and released a shader called xBR-hybrid, which combine xBR with a very simple reverse anti-aliasing filter. The problem with this combination is that the transition between algorithms isn't seamless, there's too many discontinuities.

General strategy: Instead of trying to "switch", compute a weighting function that is smooth (both as a function of position and function of the local image content, meaning the image data in a patch centered at the sampling point), and lerp the results of the two schemes in such a way that when you can detect that one of the two is definitely the one that's appropriate, the weight of the other result is 0, or at least close to zero.
P.S. Please take no offense if I tell you something you already know. I'm just trying to cover the bases.

[NicolasRobidoux]

Sergio:
With a disc of radius 2.5 and enlargement ratios that are not too large (so you can't see the discontinuities introduced by chopping at radius 2.5), I think you should simply use Jinc3 and play with the deblur. Unless this messes up the anti-ring you use, in which case I'd stick to EWA Keys (or BC-splines). Or simply deblur the real JInc2.
Also, my first pass at a weighting function that detects whether you're dealing with pixel art would count different colors in a neighbourhood and weight the pixel art component by a constant plus something proportional to the reciprocal of the number of colors, locally smoothing out the resulting weights so things don't jump too much. (Really really quick and dirty advice.)
P.S.... or use EWA Quadratic Jinc, for which the "outer weights" are really small, so chopping should not hurt too much. I've not tried deblurring it, but it should work just fine deblurred. It's not an "optimized" method; just one that is assembled from reasonable pieces and that turned out to work well. Deblurring it so it's diameter is 6 like the 3-lobe LanczosRadius (and then chopping at diameter 5) may work well?

[Hyllian]

You using

Code: Select all

weights[4*(j+1)+k+1] = sinc(WA*dist(j-0.25, k-0.25))*sinc(WB*dist(j-0.25, k-0.25));

with WA non-integer is an example of "deblurring". My own EWA LanczosSharp is an example of "deblurring" as well. In general, it means not sticking to the scaling of the filter kernel suggested by a literal reading of sampling (or interpolation, as in using BC-spline weights over a region of with extent different from 4) theory. When the filter kernel's extent is "shrunk". This is what I (and others) have found the most useful "change of scaling". (Widening the extent of the kernel by "stretching" it generally "blurs" the result.)
Makes sense?

Oh, yes, makes sense. It's good to get the jargon used in this field. (I'm not of this field, as you already have noticed.)

EWA (when doing pure enlargement) in a nutshell:
Let the 1D kernel function be

Code: Select all

f(r)

This is a univariate function: 1 input, 1 output, both real numbers.
The unnormalized weight of the input pixel (i,j) at location (x,y) is

Code: Select all

v_{i,j} = f(r_{i,j})

where

Code: Select all

r_{i,j} = sqrt((x-i)^2+(y-j)^2)

In other words, the weight associated with an input pixel depends only on the distance to the sampling point.
The normalized weight is

Code: Select all

w_{i,j} = v_{i,j}/sum_{i,j}v_{i,j}

This normalization ensures that patches with constant color values are enlarged into like patches. You know about this already.
Conceptually, EWA is actually simpler than tensor (orthogonal) methods. However, they generally cannot be performed by doing two independent passes. This is what makes them more expensive.

OH, so this is EWA. This is exactly what I'm doing when I said about "cylindrical coordinates". I calculate the "r" and apply the filter kernel, and then normalize at the final step. So, if any filter is applied to "r", it should be called EWA, is that right? And if I use BC-cubic resampler over the distance "r" from the sampling point, can I call this filter as EWA-BC-cubic?

The advice about EWA with Keys cubic? I have an implementation of BC cubic family in shader format, so I intend to integrate it with cyindrical coordinates to see what is the output.

I think you may get good mileage out of EWA with Keys cubics, and playing with the one parameter that's left (because B+2C=1, setting either B or C automatically sets the other). You may also use the full range of BC-splines, instead of sticking to Keys. But if I was to choose one blindly, I'd pick a Keys one for the reason I gave above.
I however am not certain that this is the best choice. Same with, say, EWA Quadratic or Quadratic-Jinc. All this advice is off the top of my head.
Given that I now know that you are OK with a disc of diameter 5, there may be a better choice than EWA Keys or Quadratic. However, these are simple and solid performers.
What I'd suggest depends on how much you loathe haloing, and I'd need to spend a bit of time thinking and looking through my notes.
-----
I also think that you may find Nohalo-LBB to your liking. The first incarnation of Nohalo ("Nohalo-bilinear") was actually programmed in HLSL. But it's a tricky scheme to program cheaply. And again this is off the top of my head.

For now, I'm restricted to diameter 2.5, because it already demand at least 16 texture lookups (a shader jargon for picking samples from input) per pixel. For many systems, this is a big number yet. So, I'm a stuck at 2-lobe filters as a general rule. Is there a description of the Nohalo scheme? Is this some kind of more complex anti-ringing scheme?

General strategy: Instead of trying to "switch", compute a weighting function that is smooth (both as a function of position and function of the local image content, meaning the image data in a patch centered at the sampling point), and lerp the results of the two schemes in such a way that when you can detect that one of the two is definitely the one that's appropriate, the weight of the other result is 0, or at least close to zero.
P.S. Please take no offense if I tell you something you already know. I'm just trying to cover the bases.

This a very useful advice. I didn't think much about it, though I remember that it's a bit hard to decide which one is better to apply in an specific position. But, I think I could develop an approach where I can define a function where I could weight each algorithm. It is in my todo list for now.

And, Nicolas, don't be concerned on giving your thoughts. You are a very knowleageable person in this field, and have many things to contribute. I'm very grateful I could receive these tips, as I'm just a curious guy about image processing. I like it very much, but I don't have a background in this field.

[NicolasRobidoux]

https://github.com/jcupitt/libvips/blob ... nohalo.cpp
https://github.com/GNOME/gegl/blob/mast ... r-nohalo.c
P.S. LBB-Nohalo has not built a huge following (that I know). Maybe it's because it's only found in a library that only recently started picking up steam (libvips) and in the work in progress (fully GEGLized) GIMP. Maybe it's because people actually like artificial acutance ("tasteful" haloing). Or maybe it's because it's not as good than I think.
With images that don't have much Nyquist (checkerboard mode) content and are not too noisy, it's very clean although slightly aliased. To compute one output value, it only uses a 5x5 minus the four corners (that's 21 values, from five rows). The LBB (Locally Bounded Bicubic) component of it is a useful thing on its own. In another life, I may modify it so it creates a pair of smooth surfaces that tightly bracket the data and which never "cross", to be used to build an AR filter.
P.S. 2 Blending LBB-Nohalo with a decent EWA scheme like LanczosSharp or LanczosSharpest may give good results. If I had more time...

[NicolasRobidoux]

There is only more to EWA than "computing weights using polar (or cylindrical) coordinates and ignoring the angle" when you are not preserving the aspect ratio, for example when warping or doing texture mapping.
EWA BC-spline is fairly self-explanatory IMHO.

[Hyllian]

I finished implementing an EWA-cubic shader: http://pastebin.com/Csfi4nmr

I need to tweak its parameters to see how the output change. I only can test it with games, as it's in a format only Retroarch emulator recognizes. I'll take a rest now and when I have some good params, I'll post here some screenshots.

[NicolasRobidoux]

Suggestion: The min of four values is better computed as min(min(a,b),min(c,d)). (This of course depends on the compiler etc.) The reason is that the two mins can be computed "concurrently".
Same with max.
And if you really want to save flops, you may be better off combining the computation of the min and max into one single "sorting network": You can recycle comparisons.

[NicolasRobidoux]

Suggestion: Compute the weights using the formulas used in ImageMagick's resize.c

Code: Select all

if (x < 1.0)
  return(resize_filter->coefficient[0]+x*(x*(resize_filter->coefficient[1]+x*resize_filter->coefficient[2])));
if (x < 2.0)
  return(resize_filter->coefficient[3]+x*(resize_filter->coefficient[4]+x*(resize_filter->coefficient[5]+x*resize_filter->coefficient[6])));
return(0.0);

and save one flop.