5 new interpolation kernels

[henrywho]

For whoever interested, *.mp4 has posted five interpolation kernels in Doom9:

http://forum.doom9.org/showthread.php?t=166080

[fmw42]

henrywho,

I had been thinking for quite some time now about the binomial filter for use as a window or -filter shape in IM (for -distort resize and -resize). I have also suggested that to Anthony and Nicolas.

Thanks for pointing that link out.

Fred

[anthony]

For whoever interested, *.mp4 has posted five interpolation kernels in Doom9:

http://forum.doom9.org/showthread.php?t=166080

I am not quite certain how these interpolations methods are being applied. The code just defines 'weights' then calls some other function to apply them.

[NicolasRobidoux]

I've looked into the math behind the binomial window functions, and it looks like it may add something valuable.
As is often the case, the top level motivation goes through a limit when the window has infinite width, so it's hard to tell what whether they'll add much with small numbers of lobes.
I would guess the results would be pretty close to using Parzen or Quadratic (B-spline) windowing. But I've not looked into this enough to know. And I've not tried the existing versions.
As a stand alone filter, I think this could be noticeably better than the usual truncated Gaussian blur.
Thank you Henry! (And Fred.)
(No time for this now.)

[anthony]

That still does not explain how the values are actually used as a filter.

[fmw42]

That still does not explain how the values are actually used as a filter.

I suspect one would compute the binomial values for some N, scale them to range 0 to 1 (first "lobe" zero) in x and (linearly) interpolate to some desired lut length as needed for accuracy. Note y is automatically in range 0 to 1. Thus it would be an looked up interpolation method or a window, rather than computed from a formula. It's shape is like a simplistic bell shaped (Gaussian approx.) that always rolls-off exactly to zero. I suspect the issue is to compute the lut length to some reasonable accuracy and store that for use. I am not sure if the shape actually changes for different binomial orders N, since it is being scale. One could easily compare a few orders and see. The accuracy would likely be better for higher orders, since that involves more values to scale to range x=0 to 1.

[Dane Vandeputte]

The probability mass function of the binomial distribution is:

binomial(n, x)*(1 - p)^(n - x)*p^x.

In order that the distribution is not lop-sided, we use p = 1/2. This simplifies to:

binomial(n, x)/2^n.

Of interest is n >= 0 and 0 <= x <= n. Scaling and shifting the distribution so that x is mapped to [-1, 1] gives:

binomial(n, n*(x + 1)/2)/2^n.

To make the window continuous, we use the gamma function:

gamma(n + 1)/(2^n*gamma((n*(1 - x))/2 + 1)*gamma((n*(1 + x))/2 + 1)).

For n = 0, this gives a rectangular window. As n increases, the window becomes bell shaped. From a few quick experiments, it seems this window behaves similarly to the Kaiser window.

The image below shows the evolution of the window as n varies from 0 to 10:




Update:

If we desire that the window be continuous (C0 only), then we can modify the window to have roots at +/- 1:

gamma(n + 1)/(2^n*gamma(((n + 2)*(1 - x))/2)*gamma(((n + 2)*(x + 1))/2)).

For the same range of n as before:



It is interesting to note that, for n = 0, if we do not truncate the domain to [-1, 1], we get sinc(x) = sin(pi*x)/(pi*x). In fact, for all n >= 0, the window is oscillatory outside of [-1, 1].

[NicolasRobidoux]

Too bad I'm so busy: binomial does sound like a superior alternative to the Gaussian kernel, because no truncation of the support is needed to get continuity.

[NicolasRobidoux]

Woke up this morning (a gorgeous Saturday in Copenhagen) going "Man, I wish I had time to look carefully into binomial filtering".

Time to phone Mathematics Anonymous.

[NicolasRobidoux]

I still think that good things could be obtained through a judicious use of Binomial as a replacement for Gaussian.

It appears to me, however, that properly implementing it is more complicated, in particular matching coefficients to usage.

[Dane Vandeputte]

I still think that good things could be obtained through a judicious use of Binomial as a replacement for Gaussian.

I think it is also interesting to consider the Kaiser window, extended to include its first zero on either side of the y-axis. As the alpha parameter is varied, the extended Kaiser window displays an evolution in shape that is very similar to the C0 binomial window. Some time ago, I did some experiments comparing the binomial window (the first flavor I mentioned in my previous post) to the Kaiser window, and I came to the conclusion that, while the two windows give very similar results for windowed-sinc resampling, I preferred the Kaiser window overall. I suspect, then, that I would prefer the extended Kaiser window to the C0 binomial window as a potential replacement for the Gaussian filter. Of course, though, that's just me.