Hi maintainers, this is my first time contributing to ImageMagick. I am not deeply familiar with signal processing but have taken a stab at implementing the Magic Kernel based on the paper https://johncostella.com/magic/mks.pdf and by looking at how other filters were implemented. Please let me know if I overlooked certain details or missed something in this PR.

As an aside, the paper mentions that this filter is essentially (box * box * box * sharp2013). I couldn't figure out a way to chain multiple filters in the resize operation. I wonder if having such an ability will make it easier to implement custom filters.

I am adding a mathematica workbook listing what I did in the hope that it will help with reviewing the implementation. It is identical to what the paper says.

Ah sorry, I didn't even see this work—I was only alerted to it through an email from someone grateful for both of our work today. I could have helped with this discussion, but it looks like it's all been sorted.

I also agree with the decision on 2013 v 2021 v both. 2013 remains popular, particularly for fast, low-level implementations, but 2021 is more accurate. The other high-level algorithms are more mathematically correct, but slower, and I think in many situations actually create unexpected artifacts.

[EDIT: I thought that this was wrong, but now I think it might not be; see below]

I've tried it out against my reference implementation and it looks good to me.

FWIW, according to ResampleScope, the 2013 variant appears to have been incorrectly implemented:
https://github.com/kleisauke/resize-comparison#imagemagick-magickernelsharp2013-vs-libvips-mks2013

FWIW, according to ResampleScope, the 2013 variant appears to have been incorrectly implemented: https://github.com/kleisauke/resize-comparison#imagemagick-magickernelsharp2013-vs-libvips-mks2013

Ah ok, I defer to this analysis and withdraw my comment. I will look into this shortly.

[Edit: see below; it's not clear to me now where the error is]

Uh … I'm actually concerned about both implementations now. It should look like this:

https://johncostella.com/magic/mks-2013-graph.png

I will try to debug this further. If applied as a single kernel (I have not checked if it was done that way either here or for libvips) then the formula should be:

https://johncostella.com/magic/mks-2013-formula.png

If, alternatively, it was done in the original (Facebook and Instagram) way, then the MK should look like this:

https://johncostella.com/magic/m-x-graph.png

with formula

https://johncostella.com/magic/m-x-formula.png

with the three-tap Sharp2013 filter applied in the appropriate space.

OK, now I'm confused again. resize.c has the code

which appears to differ from what I have (above) on my website

but expanding out the algebra shows that they're both equivalent. And (as with all variants of MK and MKS) they are all piecewise parabolic (and continuous and with continuous first derivative).

It's not clear from the graphs on your comparison whether those are piecewise parabolic—they're obviously wrong, but to the resolution shown they might be parabolas, just the wrong ones. (For libvips it's the flat top that is clearly wrong.)

I don't know whether the problem is with ImageMagick's use of its own resize.c (unlikely), with ResampleScope, or with your use of it.

Given that it would be remarkable if both ImageMagick and libvips were to each wrongly implement MKS 2013 in different ways, but both get MKS 2021 (and every other kernel) correct, I'm leaning towards one of the two latter explanations, but you'll have to test this yourself.

We corrected the algorithm. Let us know if you still think the algorithm has issues. If so, we can always revert the patch.

We corrected the algorithm. Let us know if you still think the algorithm has issues. If so, we can always revert the patch.

Ha, now I'm even more confused. :)

I noted that the output of both 2013 and 2021 appeared to match that of my reference implementation. I discounted small localized deviations, as there are implementation-dependent details that are not expected to match exactly.

@kleisauke found that 2021 was equal to libvips, but that 2013 was not. I then noted that the graphs he got for 2013 were wrong both here and for libvips. The graphs for 2021 look correct, visually.

@urban-warrior just noted that 2021 was just patched tonight. I haven't checked the formulas for 2021, and @kleisauke's test had shown it to be equivalent to libvips.

In all of these, we are being imprecise as to which version each of us is running. I was just using the current Homebrew version on Mac, since (until tonight) these were landed two months ago, and the options agreed with the current codebase.

Let me do some more digging.

Confirmed that I have been running 7.1.1-41 which is the current release, and that resize.c for it has what I showed above for 2013. It should be correct. 7.1.1-41 also matches what was in there for 2021 before @urban-warrior's patch tonight.

Let me check 2021 against the formulas on my page.

MKS 2013

OK, so I just noticed @urban-warrior's other patch tonight, for 2013. Since I had already established that what was previously there was correct (and I have just double-checked the algebra), this patch to 2013 is wrong and should be reverted.

MKS 2021

For 2021, the reference formulas on my page are

Tonight's patch is

In all cases I find that what was there before tonight's patch to be equivalent to my reference formula. The new patch is wrong for lines 451, 453, and 455, and is a no-op for line 457, and so also should be reverted.

I've spent some time researching this and didn't find any obvious issues in the original implementation. However, I can confirm that the recent patches are definitely broken.

I was able to resolve the "flat top"-issue for the Magic Kernel Sharp 2013 algorithm, it seems to be a minor issue in ResampleScope itself, see: jsummers/resamplescope#3.

I've spent some time researching this and didn't find any obvious issues in the original implementation. However, I can confirm that the recent patches are definitely broken.

I was able to resolve the "flat top"-issue for the Magic Kernel Sharp 2013 algorithm, it seems to be a minor issue in ResampleScope itself, see: jsummers/resamplescope#3.

So this run still remains anomalous and unexplained? There are both small discontinuities—at positions that are not the half-integer transition points of the parabolas—as well as the strange section around zero. Looking at your diff in that other thread, it seems that changing the colors causes significant changes to the apparent shape of the graph in a number of places of various graphs, not just the "flat top" issue.

I.e., it seems like the bug is in ResampleScope, not here. (Except for the incorrect diffs committed last night.)

Can you explain how you create these graphs by running Imagemagick -- what command as Imagemagick does 2D resampling not 1D?

Could the IM flat-top be a clipping issue?

Can you explain how you create these graphs by running Imagemagick -- what command as Imagemagick does 2D resampling not 1D?

Could the IM flat-top be a clipping issue?

I'll let @kleisauke answer that properly, and I haven't looked at how ResampleScope works, but I imagine that it wouldn't be too difficult to basically do an impulse response—say, an input image with a vertical line down the middle; blow it up using the program under test by a large enough factor to get horizontal resolution for the graphs; and then analyze the resulting image, which should show the impulse response in each row. There would be some interesting dynamic range and clipping issues to deal with, unless you had fully floating point images, which is what I think you're pointing to as a likely culprit.

For downscaling, ResampleScope generates two "dots" pattern test images (pd.png and pdr.png), which have dimensions of 557x275 and 275x557, respectively. These images are downscaled to 555x275 to test the horizontal direction and to 275x555 to test the vertical dimension.

pd.png	pdr.png

ResampleScope is extremely sensitive to cases where an application performs both horizontal and vertical shrinking, even when it should only shrink in one direction. This appears to be the issue with ImageMagick, for example, when resizing with:

$ magick pd.png -filter magickernelsharp2013 -resize '555x275!' pd_magick_magickernelsharp2013.png

^{(original source can be found here)}

It also appears to call VerticalFilter() despites that y_factor being equal to 1.0. I was able to resolve this using this patch.

With that, it generates the correct graphs (see e.g. commit kleisauke/resize-comparison@931cb55). I confirm that the "flat top"-issue persists in the generated graphs for ImageMagick when the previously linked PR is not applied. I still need to investigate why altering the special colors resolves this.

My apologies for the noise and wasted time. :(

Ah, interesting, and thanks for root-causing this. A very elegant way of testing the kernel, but also, as you note, somewhat sensitive to the assumption that the implementation will not resize in both directions when it only needs to do one.

After seeing this, I thought that it might be useful for me to implement the "kernel test" the way that I spitballed above, which is less elegant, but has the advantage of being directly inspectable. So I did. I include it on my page at https://johncostella.com/magic/#test.

Interestingly, I found that ImageMagick got the right results (in agreement with your revised findings) but does more quantizing than I thought it would be doing. It's probably just my misreading of the documentation, and missing out one or more required command-line options to prevent it, but anyway I include these observations in that section as well.

Suggestion: try using -distort resize rather than -resize. See if that is smoother

magick mks-2013-input.png -colorspace RGB -filter MagicKernelSharp2013 -distort resize 10000% -colorspace sRGB mks-2013-magick.png

magick mks-2013-input.png -colorspace RGB -filter MagicKernelSharp2013 -distort resize 10000% -colorspace sRGB mks-2013-magick.png

Not good.

OK. Thought it might help, but I guess not. Sorry.