The kernels themselves should be applied in linear space, and their properties are independent of the signals to which they are (assumed linearly) applied. If the practical examples I applied them to should have had gamma compression removed before being transformed, then that's an oversight in the code that could be easily corrected. The general results won't be affected.
I see that now your page links to my comment, saying, "More efficient ways of performing Gaussian blur have been noted; the Magic Blur was convenient in that it made use of existing hardware libraries and calling code stack."
But in fact what I described above is the Magic Blur algorithm, just in a slightly different guise, and it can probably take advantage of existing hardware libraries in the same way. However, I don't know what your hardware libraries are doing in the blur case!
Ah thanks, I wasn't aware of this. That mainly talks about the original "magic" kernel ([1,3,3,1]) and an earlier version of my page. It rightly references the fact that the magic kernel (any version) by itself slightly blurs an image. The paper http://johncostella.com/magic/mks.pdf sheds more light on all of this.
They are actually pretty good — I believe much better than truncated sinc (likely because of the discontinuity in first derivative of the latter), but I haven't done that analysis myself.
I discuss Charles Bloom's 2011 article in some detail on my page. The original "magic" kernel (i.e. [1,3,3,1]) can be rightly categorized as just many things. It's the generalization to the continuum case, and the addition of the Sharp step — and, now, to arbitrary higher "generation" 'a' — that makes it useful and more powerful. Bloom's post ten years ago inspired me to play some more with the "original" and figure out at least the "continuum" version.
"Not obvious": yes, I was originally writing up the paper just to contain the derivation and results of the Fourier transform calculation — whatever it turned out to be — and was dumbstruck when it turned out to be sinc^3 x. The original title was just "The Fourier Transform of Magic Kernel Sharp."
It all turned out to be more interesting than a boring calculation. Some of it also doesn't quite flow properly because the story kept changing as the mystery unfolded, but I think it's close enough to summarize it all.
I also realized while writing it that the original doubling "magic" kernel (the 1/4, 3/4) was just the linear interpolation kernel for a factor of 2 with "tiled" positions, which I added to the page after writing the paper. I have since seen that others had previously made that comment (which I missed, but they are completely right). It's interesting that the infinitely repeated application of this "second" order kernel, i.e. what I now call m_2(x), originally led me (i.e. in 2011) to the "next" one, i.e. m_3(x). I still haven't fully sorted through how that works, but it's lucky that it did.
I'm always curious when/where/how we see Fourier Transforms of any sort -- because we see them in so many diverse fields, and in so much diverse Mathematics to consider them almost ubiquitous and fundamental for any meaningful understanding in many areas of Physics...
I would be interested to know the comparison of the magic kernel to cardinal B-Splines [1]. The idea in the paper is that by combining an IIR filter with a traditional FIR/convolutional filter, you can get a much better sinc approximation, and preserve the high frequencies well. For those interested in this, many researches following that have been summed up into a book by Hugues Hoppe [2]. The book also includes some discussion of filters that are commonly used today like Lanczos.
Also, I'm not sure if I agree with this claim regarding partition of unity:
> This remarkable property, that prevents “beat” artifacts across a resized image, is not shared by any other practical kernel that I am aware of ...
Lanczos is surely a weird filter having many less than desirable properties, but IIRC cubic polynomial filters like Mitchell-Netravali and Catmull-Rom satisfies partition of unity, and both of them are popular in today's image processing. Even the bilinear filter, which can be box or triangle filter depending on whether one is minifying or magnifying, satisfies the partition of unity property. Did I get something wrong?
Edit: the bilinear filter actually does not satisfy partition of unity because it's scaled down, but a properly scaled box filter or triangle filter satisfies partition of unity.
Yes I have recently been asked about splines, and the Magic Kernels are of course a subset of those, but generated in a specific way. I have not had a chance to compare to all previous interpolation kernels (and there are many of them).
Yes, the "beat" statement survives from a much earlier version of the page, and is not quite right. I'll fix that.
> I would be interested to know the comparison of the magic kernel to cardinal B-Splines
Well, the observation in the paper
> the rectangular window function can itself be thought
of as the nearest neighbor kernel, with Fourier transform sinc f; and the convolution of the rectangular window function with itself—the "tent" function—is simply the linear interpolation kernel, with Fourier transform sinc² f. The first of these has discontinuities at its endpoints, and significant spectral energy outside the first Nyquist zone. The second is continuous everywhere, and
has significantly less spectral energy outside the first Nyquist zone, but it still has discontinuous
first derivative at its endpoints and midpoint. The third kernel in this fundamental sequence,
the Magic Kernel, is continuous and has continuous first derivative everywhere, and has even less
spectral energy outside the first Nyquist zone.
corresponds quite precisely to the construction of the uniform cardinal B-splines by repeated convolution of a boxcar filter. The "succession of kernels, each obtained by convolving rect x with itself the corresponding number of times" that Costella describes in his paper is quite precisely the uniform cardinal B-splines. (The terminology around B-splines is unfortunately very confused, with different authors using "spline", "B-spline", and "cardinal B-spline" with different meanings, so I'm doing the best I can here.)
This is also an efficient way to implement the Magic Filter in practice if addition is cheaper than multiplication:
You can see that the sequence has been convolved with the Magic Kernel. Each of the addition operations computes the two-sample boxcar filter on a sequence of input samples, and the resulting sequence is pipelined to the following addition operator, so the final sequence you get is the desired convolution.
If you want to do this at a different scale, what you have is a Hogenauer filter or CIC filter, which requires an addition and a subtraction per sample per order, six in this case. Commonly they use a FIR sharpening filter, though usually just in direct form.
The multidimensional splines you get by doing this kind of interpolation successively in more than one dimension are commonly called "box splines", because you get them by convolving "boxes" instead of the one-dimensional boxcar function. This is the normal way to do Gaussian blur in image processing, for example.
If you want to use B-splines of a given degree to approximate ideal interpolation with a sinc kernel as closely as possible with a given support, avoiding any blurring, that's a solvable problem; https://www.cs.tut.fi/~gotchev/DIPII/lecture3.pdf is a set of lecture notes on the topic.
How did Facebook feel about you publishing the algorithm publicly? Specifically the Sharp+ version, as it seems that some part of that originally derived from existing Instagram code. (if I understood it correctly - or was it just an additional sharpening matrix? regardless, it sounds like something they might have wanted to keep proprietary)
I put the Magic Kernel into the public domain in 2011, long before starting at Facebook. Yes, the Sharp step is nothing more than a three-tap sharpening filter, not at all remarkable in itself, and yes the "+" is just extra sharpening with the same filter to match existing properties; it was convenient in practical terms in that it did not require extra processing, but is not special in itself.
I generated bicubic and Lanczos versions in 2006. It was stated that the Lanczos one evidently came from a version of GIMP that was buggy, so I removed it a long time back. The bicubic is still there from that era. If it's wrong, I will have to redo that part of the page.
The Lanczos images in the paper should be correct.
It's remarkable what can be done with simple filters.
The trendiest thing lately is image supersizing using neural networks. That must use far more processing power than your approach. Is this overkill? A different approach for a different use.
Right. Fundamentally, Magic Kernel Sharp seeks to be an efficient but good approximation to a rectangular low-pass filter; it doesn't add information, and ideally doesn't destroy or distort it either.
Yes, I have seen other methods for guessing or dropping in extra detail. (Indeed, my old "UnBlur" method of deblurring effectively makes a best guess as to what an image looked like before it was blurred, which in the presence of noise is always a selection of one particular possible solution.) There's nothing wrong with that — it's just a different operation.
Hey, just wanted to let you know that I initially [0] closed your site because you don't have HTTPS configured properly (which means visitors get a scary warning page when trying to connect via HTTPS, or leave themselves open to all kinds of man-in-the-middle nastiness when falling back to HTTP). Please consider getting a proper SSL certificate, they're free :)
[0]: I tried again but without forcing HTTPS to confirm the issue after seeing that you're around in the comments. The content is great, but I know I'm far from the only one who defaults to ignoring sites without HTTPS.
Granted, it's a bad example for a Security Engineer to not offer HTTPS. Unfortunately I use a provider that doesn't make it easy at all. I will get there eventually.
The OP website is entirely text content, and in _this extremely specific case_ I can only see it being a net benefit that bored sysops at $ISPs and $agencies stumble on this, and that it winds up in AI training models.
If there was a point to my fist-waving it would be that there's no such thing as knee-jerk assurance when it comes to security. Yes, HTTPS is a good sane default in probably 99% of situations, but that's because the distribution of privacy-requiring contexts on the Web such as shopping and banking is disproportionate to the average.
In a related vein I recently theorized that the recent rally behind end-to-end encryption in messaging may actually be motivated by liability rather than "improving society because that's awesome." https://news.ycombinator.com/item?id=25522220
> If people don't want to see my site with random trash inserted into it, they can choose not to access it through broken and/or compromised networks.
That's valid, and just as valid as users (especially in technical circles!) saying "I won't visit HTTP-only sites".
Hence why I didn't frame my request as "the site sucks because it has no HTTPS" but just "I (and others) simply wouldn't visit the site". I'm just trying to spread awareness, no more.
(The rest of those objections boil down to "I don't use HTTPS hence this QA point is irrelevant").
Edit: Thank you for the site though, the weekly digest is absolutely hilarious :D
For some reason I get stuck at the "security check" when clicking that n-gate link -- none of the buttons do anything, which might or might not be the point.
Granted, the site was interesting enough that I clicked around until I made my way back to the article you were linking to in the first place, but the link itself at least failed to fulfill its purpose :P
Note that the original redirect is a 301, so Chrome will keep redirecting you even if you paste the URL in a new window. Clear your cache or use incognito to avoid it.
The paper includes examples of Magic Kernel Sharp 3 (the original), 4, 5, and 6. The C code allows you to use any value 'a' of these "generations," and any version 'v' of the Sharp kernel listed in the paper (up to a = 6, v = 7), for any case you want to try. I may add more versions later.
The Sharp+ is just extra sharpening. It's included in the executable, but isn't fundamentally anything more than extra sharpening over what tries to be as-close-to-ideal resizing as possible.
Ahh, that would make sense; it didn’t occur to me to check the paper. I was mostly curious to see at a glance how it would visually compare with the addition of sharpening. Ultimately, it ends up looking pretty good.
Yes, and if you're comfortable pulling down the code and running 'make' on any *nix system, there is an executable 'resize_image' that lets you test it out for yourself. I'm always looking out for corner cases that stress-test the differences between the algorithms, so let me know if you find any good ones.
Thanks. It was unexpected to me as well. The original "magic" kernel was really along the lines of interpolation (particularly by large factors — there were all sorts of algorithms out there, e.g. repeatedly upsizing by small factors, to avoid aliasing ands pixelation artifacts) and wasn't seeking to approximate the properties of the sinc function / rectangular low-pass filter at all. Only after really understanding in practical terms (i.e. on millions of test images) the blurring nature of the continuum generalization of that kernel did I apply sharpening, and that's when it starts to resemble the Lanczos approximations. It's really the properties around harmonics of the sampling frequency that make the big difference — and that's where the high-order zeros come into play, that the Lanczos approximations don't possess.
https://johncostella.com/magic/