5 new interpolation kernels

Discuss digital image processing techniques and algorithms. We encourage its application to ImageMagick but you can discuss any software solutions here.
Post Reply
henrywho
Posts: 188
Joined: 2011-08-17T06:46:40-07:00
Authentication code: 8675308

5 new interpolation kernels

Post by henrywho »

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

http://forum.doom9.org/showthread.php?t=166080
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: 5 new interpolation kernels

Post 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
User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: 5 new interpolation kernels

Post 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.
Anthony Thyssen -- Webmaster for ImageMagick Example Pages
https://imagemagick.org/Usage/
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: 5 new interpolation kernels

Post 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.)
User avatar
anthony
Posts: 8883
Joined: 2004-05-31T19:27:03-07:00
Authentication code: 8675308
Location: Brisbane, Australia

Re: 5 new interpolation kernels

Post by anthony »

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/
User avatar
fmw42
Posts: 25562
Joined: 2007-07-02T17:14:51-07:00
Authentication code: 1152
Location: Sunnyvale, California, USA

Re: 5 new interpolation kernels

Post 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.
User avatar
Dane Vandeputte
Posts: 14
Joined: 2012-07-01T18:26:53-07:00
Authentication code: 13
Location: Illinois, USA

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

Post 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].
Last edited by Dane Vandeputte on 2013-01-03T10:51:03-07:00, edited 2 times in total.
Digital image processing and photography enthusiast :)
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: 5 new interpolation kernels

Post 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.
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: 5 new interpolation kernels

Post 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.
NicolasRobidoux
Posts: 1944
Joined: 2010-08-28T11:16:00-07:00
Authentication code: 8675308
Location: Montreal, Canada

Re: 5 new interpolation kernels

Post 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.
User avatar
Dane Vandeputte
Posts: 14
Joined: 2012-07-01T18:26:53-07:00
Authentication code: 13
Location: Illinois, USA

Re: 5 new interpolation kernels

Post 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. :)
Digital image processing and photography enthusiast :)
Post Reply