Page 1 of 1

5 new interpolation kernels

Posted: 2012-12-11T23:15:20-07:00
by henrywho
For whoever interested, *.mp4 has posted five interpolation kernels in Doom9:

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

Re: 5 new interpolation kernels

Posted: 2012-12-12T17:27:59-07:00
by 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

Re: 5 new interpolation kernels

Posted: 2012-12-13T16:25:44-07:00
by anthony
henrywho wrote: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.

Re: 5 new interpolation kernels

Posted: 2012-12-26T07:35:05-07:00
by 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.)

Re: 5 new interpolation kernels

Posted: 2013-01-01T21:52:52-07:00
by anthony
That still does not explain how the values are actually used as a filter.

Re: 5 new interpolation kernels

Posted: 2013-01-01T22:10:46-07:00
by fmw42
anthony wrote: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.

Binomial window... as I see it, anyways :)

Posted: 2013-01-02T19:50:12-07:00
by 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:

Image


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:

Image

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

Re: 5 new interpolation kernels

Posted: 2013-01-03T08:19:29-07:00
by 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.

Re: 5 new interpolation kernels

Posted: 2013-07-06T07:06:13-07:00
by 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.

Re: 5 new interpolation kernels

Posted: 2014-01-10T00:53:31-07:00
by 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.

Re: 5 new interpolation kernels

Posted: 2014-01-13T10:32:39-07:00
by Dane Vandeputte
NicolasRobidoux wrote: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. :)