5 new interpolation kernels
5 new interpolation kernels
For whoever interested, *.mp4 has posted five interpolation kernels in Doom9:
http://forum.doom9.org/showthread.php?t=166080
http://forum.doom9.org/showthread.php?t=166080
 fmw42
 Posts: 25752
 Joined: 20070702T17:14:5107:00
 Authentication code: 1152
 Location: Sunnyvale, California, USA
Re: 5 new interpolation kernels
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
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
 Posts: 8883
 Joined: 20040531T19:27:0307:00
 Authentication code: 8675308
 Location: Brisbane, Australia
Re: 5 new interpolation kernels
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.henrywho wrote:For whoever interested, *.mp4 has posted five interpolation kernels in Doom9:
http://forum.doom9.org/showthread.php?t=166080
Anthony Thyssen  Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/
https://imagemagick.org/Usage/

 Posts: 1944
 Joined: 20100828T11:16:0007:00
 Authentication code: 8675308
 Location: Montreal, Canada
Re: 5 new interpolation kernels
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 (Bspline) 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.)
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 (Bspline) 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
 Posts: 8883
 Joined: 20040531T19:27:0307:00
 Authentication code: 8675308
 Location: Brisbane, Australia
Re: 5 new interpolation kernels
That still does not explain how the values are actually used as a filter.
Anthony Thyssen  Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/
https://imagemagick.org/Usage/
 fmw42
 Posts: 25752
 Joined: 20070702T17:14:5107:00
 Authentication code: 1152
 Location: Sunnyvale, California, USA
Re: 5 new interpolation kernels
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 rollsoff 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
 Posts: 14
 Joined: 20120701T18:26:5307:00
 Authentication code: 13
 Location: Illinois, USA
Binomial window... as I see it, anyways :)
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 lopsided, 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].
binomial(n, x)*(1  p)^(n  x)*p^x.
In order that the distribution is not lopsided, 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].
Last edited by Dane Vandeputte on 20130103T10:51:0307:00, edited 2 times in total.
Digital image processing and photography enthusiast

 Posts: 1944
 Joined: 20100828T11:16:0007:00
 Authentication code: 8675308
 Location: Montreal, Canada
Re: 5 new interpolation kernels
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.

 Posts: 1944
 Joined: 20100828T11:16:0007:00
 Authentication code: 8675308
 Location: Montreal, Canada
Re: 5 new interpolation kernels
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.
Time to phone Mathematics Anonymous.

 Posts: 1944
 Joined: 20100828T11:16:0007:00
 Authentication code: 8675308
 Location: Montreal, Canada
Re: 5 new interpolation kernels
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.
It appears to me, however, that properly implementing it is more complicated, in particular matching coefficients to usage.
 Dane Vandeputte
 Posts: 14
 Joined: 20120701T18:26:5307:00
 Authentication code: 13
 Location: Illinois, USA
Re: 5 new interpolation kernels
I think it is also interesting to consider the Kaiser window, extended to include its first zero on either side of the yaxis. 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 windowedsinc 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.NicolasRobidoux wrote:I still think that good things could be obtained through a judicious use of Binomial as a replacement for Gaussian.
Digital image processing and photography enthusiast