The magic kernel | Hacker News Reader

The magic kernel

johncostella.com

207 pointswazoox32 comments

When seen as a [1 3 3 1] (the 4th row of Pascal's Triangle) kernel, it is more easily revealed as a discrete Gaussian kernel, which is for example used in scale-space representations in image processing.

Whoa. Your one sentence completely demystified this article for me.

The same applies to {0.05, 0.25, 0.4, 0.25, 0.05} mentioned later: it's proportional to 1 5 8 5 1, which is two rows down from 1 3 3 1.

The row is 1 4 6 4 1, but these are the closest 5-cent approximations to the 1/16th that add to 1.

Thanks for the correction, and additional information.

The rows after 1 3 3 1 are 1 4 6 4 1 and 1 5 10 10 5 1. Where does 1 5 8 5 1 come from?

From me being bad at arithmetic. Sorry.

Doing arithmetic in public is dangerous.

This makes heaps of sense, they say "wow it looks so much like a Gaussian kernel" and my first thought was "is Gaussian not the go-to kernel for image processing?"

no, gaussian is a bad reconstruction kernel.

The argument is that, in practice, it performs better for resampling images than the more correct sinc kernel from sampling and reconstruction theory.

Well, you can't actually use sinc in practice because it has an infinite support. But something like windowed sinc will work better than gaussian.

Right. And the advantages of the Gaussian kernel with respect to image processing:

1. It has no negative coefficients (hence the output will always be a valid color value.)

2. It is circular symmetric, yet separable (X and Y may be filtered independently) -- a property which simplifies the implementation considerably.

The Gaussian function is actually the distribution function of the normal distribution, and the normal distribution’s discrete equivalent is the binomial distribution whose coefficients (binomial coefficients) are the rows of Pascal's triangle.

Let me share my experience with chroma upsampling and smooth jpeg decoding.

At first, I optimized each channel, then upsampled the chroma channels using replication. This works terribly as you can see in the article.

So then I changed to linear interpolation. Briefly:

    +---+---+
    a x b y c
    +---+---+

We know the values in a and c but not b. The distance from x to a is half a pixel and the distance from x to c is one and a half pixel. Then linear interpolation gives x = a + (c - a) * (1/2 - 0) / (2 - 0) = 3/4 a + 1/4 c.

This worked decently, but it still showed fringes around sharper edges. I considered using more complicated upsampling methods like Lanczos or Mitchell, but instead went with optimizing a full size image with constraints on the downsampled image. By avoiding upsampling I got my optimized high resolution image for each channel.

But there were still fringes! As it turns out, just because each channel was optimized seperately doesn't mean that the image as a whole is optimized. So I switched to optimizing the three YCbCr channels together, not looking at the differences abs(x_{i+1} - x_i) but looking at the differences sqrt((Y_{i+1} - Y_i)^2 + (Cb_{i+1} - Cb_i)^2 + (Cr_{i+1} - Cr_i)^2). This actually eliminated the fringes.

The final result is https://github.com/victorvde/jpeg2png

Sorry guys, but no magic is involved here: http://cbloomrants.blogspot.com/2011/03/03-24-11-image-filte...

I mostly agree. But

> Costella shows that Lanczos and Bicubic create nasty grid artifacts. This is not true, he simply has a bug in his upsamplers.

The good and bad part of discussions about image processing is that it's easy to compare the results. This blog post would be better with the images using the correct implementation of the filters.

(One problem is that some times just getting the images, configuring the programs and tiding the results is more time consuming than expected. So "just add the images" may be a one week project.)

For reference I get the following result with my GIMPs "Cubic" scaler:

http://i.imgur.com/3LLNzv5.png

Notice the long-known bug, Gimp doesn't manage gamma properly, the scaled picture looks slightly darker.

I'll need to try this as an OpenGL (ES) shader in an app I work on regularly. I've been meaning to replace the default bilinear filtering with something a bit nicer-looking for ages, and this seems like it fits the bill nicely, as it avoids the usual ringing and moiré issues. (I don't need to worry about perspective correction as the app is 2D only)

My good friend Kyle posted his C++ port here: https://github.com/kylegranger/ImageScaling

This brings back high school memories of performing Gaussian blurring of 2-bit grayscale hand drawn sprites drawn on graphing paper. Yes, I got bored in class! I did use a calculator for assistance. :) I never knew there was such a remarkably simple kernel that provides good scaling!

The fact that you were studying Gaussian blurring in high school amazes me. Which kind of school, if I may ask? Is a standard program?

The "Yes, I got bored" part suggests that it wasn't in the program and he was studying it on his own.

Public school at Tippecanoe County (home of Purdue University), Indiana, USA. The math program was actually pretty good, along with the arts, and a few other areas. It definitely helped to be in a University City area. We got lab equipment from Purdue for a variety of science classes and some great teachers.

Very cool. I did something similar (but much less advanced) in math class where I generated something like a height map by "randomly" (I'd really just pick numbers that seemed good) assigning values to a grid and then subdividing the grid and linearly interpolating between points plus another "random" offset with a range that gets divided with each subdivision. It was a good way to pass time for someone who would rather have been playing dwarf fortress but only slightly understood the math behind perlin noise.

If you prefer blurry images such as the author seems to, you can use parameters to your cubic filter to add more blur than the (probably mitchell or catrom) parameters that gimp is using. I'd bet most people would find the result superior to this filter.

A good article on cubic filters: http://entropymine.com/imageworsener/bicubic/

I think you mean the "B-spline" filter.

Ya, B-spline, as the article defines it: Cubic(1, 0), is an example of a very blurry cubic filter.

What's the popular JPEG library that this is from? Why the refusal to mention it?

It's libjpeg. http://libjpeg.sourceforge.net/

Finally all those haters who think low-pixel images cannot be zoomed in on are proven wrong... https://www.youtube.com/watch?v=I_8ZH1Ggjk0

Now someone only has to find a way interpolate reflections in sunglasses, then I can die a happy man.

Reply on news.ycombinator.com