Implement fast floating-point(?) Gaussian blur using SIMD

[libass]

Implement fast floating-point(?) Gaussian blur using SIMD

[astiob]

Huhh, this is rightfully closed because the thing in the issue title has been done, but the comments went off a tangent and are a goldmine.

I should probably repost those pictures I apparently posted. I do have them, but there’s a lot and I don’t remember how I organized them when I uploaded them.

Anyway, libass’s and xy-VSFilter’s blur parameters are actually different? I sure didn’t remember that, and I do remember making it a point to preserve libass’s parameters when merging MrSmile’s blur. So the output looks different… yet oddly similar at the same time, because we also clip the kernels differently 🤯

[rcombs]

Scratch that, because fuck intrinsics. Will be writing my own implementations, based on xy and Intel's, in pure ASM.

[grigorig]

Why do you want to use ASM? Intrinsics are supported by all major compilers and won't complicate the build process. I'd definitely be in favor of intrinsics.

[MrSmile]

xy-vsfilter's algorithm is far from optimal for large blur radius, its asymptotic is O(w_h_r^2), where (w, h) are resulting bitmap sizes and r is radius. There is much better algorithm with asymptotic O(w*h). I posted in https://code.google.com/p/libass/issues/detail?id=71#c4 patch with implementation (though far from ready for commiting). General idea is to shrink source image first, then apply filter with small radius, and finally expand back to initial size. Filters at all stages have fixed kernel size and must be SSE/AVX frendly.

[rcombs]

I'll be looking into a few algorithms as soon as I've merged noucome-proof; I'm looking primarily at Intel's IIR algorithm right now. Could you stop by #libass on Freenode to discuss all this in more detail?

[grigorig]

MrSmile, instead of shrinking images and whatnot, it might be easier and faster to approximate gaussian blur with box blur (applied multiple times). That isn't very accurate but neither is your solution.

[rcombs]

That's pretty much what \be does; \blur is meant to be higher-quality at the expense of speed. We're not going to move to something with similar quality to the [[1 2 1][2 4 2][1 2 1]] blur.

[MrSmile]

My algorithm has error about 0.5% of maximum value. For integer fields in range [0-255] it's practically indistinguishable from exact result. Box blur is much worse. Main point is that inner filter compensate for shrink/enlarge filter errors.

[rcombs]

Heh, not bad at all. Will definitely look into using yours, then. Got any profiling numbers?

[grigorig]

Approximating gaussian with box blur isn't the same as \be. FIrst, \be isn't box blur. Second, that approximation uses varying kernel sizes. Applying a box blur three or more times with suitable kernel size is an acceptable gaussian approximation (in many cases). It is only good for bigger blur sizes, though.

[rcombs]

Could possibly determine which algorithm to use for C blur depending on the size, choosing a method that maximizes speed and quality for that size?
Also, I'm unfamiliar with what \blur's argument actually means, seeing as a true Gaussian has no "radius". Is it meant to be the standard deviation of the Gaussian, or some multiple of it?

[MrSmile]

Applying a box blur three or more times with suitable kernel size is an acceptable gaussian approximation

3% error is too much for quality approximation. More like dozen or two.

Is it meant to be the standard deviation of the Gaussian, or some multiple of it?

Formula for calculating dispersion (standard deviation squared):
double r2 = blur_radius * blur_radius / log(256) + 0.5 * be;

[astiob]

\blur

xy-VSFilter

Standard deviation = \blur argument. If it is ≤ ⅓, no blur is applied. The Gaussian kernel is cut off after the sample at ±(int) ceil(3*r) / 2 and normalized to have an area of 1.

VSFilter

Standard deviation = \blur argument. Blur is applied for all values > 0. The Gaussian kernel is cut off after the sample at ±max(1, (int) round(3*r) / 2) and normalized to have an area of 1… but no attempt is made to mitigate rounding error, allowing it to considerably affect the output. I could easily model xy-VSFilter mathematically; for modelling VSFilter, I had to actually implement the rounding.

libass

Standard deviation = 2 (\blur argument) / sqrt(log(256)). (@MrSmile, did you perhaps miss the first line of outline_to_bitmap3?) Blur is applied for all values > 0. The Gaussian kernel is cut off after the sample at ± ceil(2 r) and normalized to have an area of 1. The output is considerably different from xy-VSFilter’s and from VSFilter’s. I’d say it’s probably closer to xy-VSFilter’s, but I’ve only looked at output with large radii so far.

I’ll upload some pictures later.

\be

The [[1,2,1], [2,4,2], [1,2,1]] kernel is applied to the whole bitmap (modulo some bad boundary conditions, which I’ll overlook). There is no intermediate rounding during this step, but the output values are then rounded down (truncated). (@11rcombs, take note. I missed this bit last time. They’re specifically truncated, not properly rounded. You’re probably already doing this, but I figured I’d point this out just in case.) This whole procedure is repeated (\be argument) times.

The rounding errors do accumulate; see http://code.google.com/p/xy-vsfilter/issues/detail?id=97#c13.

The kernel produces new values just outside the edges of the original bitmap, so the bitmap must be expanded to accommodate them. The different renderers do this differently: VSFilter adds a constant 1 pixel if I’m reading the code right; xy-VSFilter adds round(sqrt(\be argument * 0.25)), which is still not enough; libass adds floor(sqrt(2 \be argument)), which is better but still is not enough.

If the rounding errors didn’t accumulate and we had infinite (or just correctly expanded) bitmaps, the total effect of \beN would tend to a Gaussian kernel with standard deviation sqrt(0.5 N), just like @MrSmile said. But, of course, reality is harsh:

• For small \be arguments, the �effect of \be does not match a Gaussian kernel even mathematically.
• \be does have rounding errors, and they do accumulate.
• \blur uses a clipped Gaussian kernel.
• I am still unsure what practical effect this has if any (other than the obvious clipping), but bitmaps are not infinite and are not expanded enough.

[MrSmile]

For small \be arguments, the effect of \be does not match a Gaussian kernel even mathematically

That difference is quite small and not easily noticeable by eye. Also discrete Gaussian kernel is not well defined for small radii so it's quite possible to define it to behave exactly the same.

\be does have rounding errors, and they do accumulate.

That's the real problem. But given that even VSFilter and xy-VSFilter do it differently maybe libass can get away with unified blur approach. (Is many-pass \be filters even used? Maybe no one cares about this at all?)

\blur uses a clipped Gaussian kernel.

I consider any visible clipping as a bug. It's eye tearing and clearly any sub writer don't want that at all. It's don't matter for libass though, as it uses sufficient border size (at least in outline_to_bitmap3, dunno about next stages).

There is another rationale for unified blur approach: libass is required to render subs not only in native video resolution, but also with arbitrary scaling applied. I think, the only good way to render scaled \be is to replace it with effective gaussian blur.

[x-xy-y]

xy-vsfilter's algorithm is far from optimal for large blur radius, its asymptotic is O(w_h_r^2), where (w, h) are resulting bitmap sizes and r is radius.

It is O(w_h_r), not O(w_h_r^2).
I had read some O(w_h) algorithms using IIR filter to *simulate_ Gaussian blur. But ...

@astiob
I'll re-check some differences between xy-VSFilter and VSFilter you pointed out. But I have some confidence that xy-VSFilter's blur/be (especially \be) routines have really little difference from VSFilters, because I've checked those lines several times and cyber also has done quite a lot of test on that. E.g.

xy-VSFilter ... If it is ≤ 1/3, no blur is applied

VS

VSFilter ... Blur is applied for all values > 0

When \blur<=1/3, it has no effect because the Gaussian kernel used by VSFilter is 1x1. So it can be skipped.
And mind you, \be blur in xy-VSFilter is majorly done with the function be_blur in Rasterizer.cpp, not xy_be_blur in xy_filter.cpp. The rounding error of the later is too different from VSFilter and hard to tune that we decided not to use it at the moment.

[astiob]

When \blur<=1/3, it has no effect because the Gaussian kernel used by VSFilter is 1x1. So it can be skipped.

Oh, that’s a good point.

I’m a bit busy right now, but I still hope to post some pictures illustrating the differences within the next day or two.

[astiob]

Wait, no, but VSFilter’s kernel always has at least three samples (hence the max in my formula):

        width = (int)(sigma * 3.0 + 0.5) | 1; // binary-or with 1 to make sure the number is odd
        if (width < 3) {
            width = 3;
        }

Note also that your rounding of the kernel size is a bit different: you do ceil, while VSFilter does round (by adding 0.5 and truncating).

Nice to see you here, by the way!

[x-xy-y]

Wait, no, but VSFilter’s kernel always has at least three samples (hence the max in my formula):

Right. I just saw that too...facepalm...maybe I've always compare with some wrong version code.

I’m a bit busy right now, but I still hope to post some pictures illustrating the differences within the next day or two.

Nice.
To be honest, I'm a bit tired and afraid of those \blur & \be compatibity issues. We had implemented some floating point \be code, but in order to be compatible with VSFilter, some insane code was added to produce rounding error. That is really none sense.

[x-xy-y]

VSFilter adds a constant 1 pixel if I’m reading the code right; xy-VSFilter adds round(sqrt(\be argument * 0.25)), which is still not enough; libass adds floor(sqrt(2 \be argument)), which is better but still is not enough.

VSFilter pads the image with 1 pixel to ease the filter process. And it does NOT write to those lines in the \be code. So VSFilter's \be along does not enlarge the image's size. (However the case is different when \be comes with \blur).
With that said, xy-VSFilter does not seem to do it right and I forgot why it is done this way.

[astiob]

Didn’t I promise pictures? http://minus.com/mbeWsD2GT2AA1C
Sorry for the very massive delay.

The “ideal” versions use Gaussian CDF formulæ derived mathematically for blurring a square.

[astiob]

Added screenshots of MrSmile’s blur (patch applied on top of the commit just before combined bitmaps). I’d like it to be tested on some rescaler-killer images… except that’s not exactly possible in ASS due to layering. But perhaps one can be converted into some very fancy font or vector drawing.

[Cyberbeing]

Didn’t I promise pictures? http://minus.com/mbeWsD2GT2AA1C

For these screenshots, did you use a discrete implementation of each \blur algorithm variation with Libass, or did you use the respective original filters themselves? It's noteworthy that without the following change, xy-VSFilter blur is applied to a 6-bit pixel coverage image instead of 8-bit like Libass: Cyberbeing/xy-VSFilter@def6de6

This behavior is a legacy VSFilter thing, not something specific to xy-VSFilter or desired. We never merged it, since while 8-bit \blur was fine, 8-bit \be broke compatibility with VSFilter 2.39 rather badly because of the aforementioned rounding error mess. Compare something like \be100 on an vector 80x80 block with VSFilter 2.39 vs Libass and you'll see what I mean. On smaller objects even low \be strength can cause a very significant differences in visual energy like this. At some point it would be good to come to some sort of consensus about how scripts utilizing \be should be handled, so users can have expected output in both xy-VSFilter and Libass.

[astiob]

For these screenshots, did you use a discrete implementation of each \blur algorithm variation with Libass, or did you use the respective original filters themselves?

I used the actual filters, and this is why there is banding on the VSFilter blur screenshots. I completely forgot that the 6-bit thing also affects \be though!

Cyberbeing/xy-VSFilter@def6de6

Oh, so that has actually been done! Nice. Maybe one day we will come up with something good for \be and enable that to be merged in.

I have now added \be screenshots to the folder. I guess the visual difference between MPC-HC and xy-VSFilter must be due to the different image padding/extension as mentioned before.

[Cyberbeing]

xy-VSFilter must be due to the different image padding/extension as mentioned before.

Probably. Last month, x-xy-y made the branch blur_be_fixes to attempt to fix those issues you mentioned. Not yet included in XySubFilter Beta2 because it still requires an additional bugfix of some kind, since now it seems 1px at the tallest point of a border sometimes wouldn't have have \be applied to it at all after those changes.

Oh, so that has actually been done! Nice. Maybe one day we will come up with something good for \be and enable that to be merged in.

I hope so, since there is definitely a nice quality improvement after that 8-bit change for \blur & \be. Those woes combined with hacking together a solution for \be scaling using legacy 6-bit was the context for the earlier comment by x-xy-y:

To be honest, I'm a bit tired and afraid of those \blur & \be compatibility issues. We had implemented some floating point \be code, but in order to be compatible with VSFilter, some insane code was added to produce rounding error. That is really none sense.

If no sane solution can be found for 8-bit \be, it would certainly make life easier to just break compatibility and eliminate the \be rounding error completely going forward. The question is how many people actually used \be intentionally instead of \blur in order to achieve that rounding-error "faded-out effect' over the years, or at least care about maintaining the original VSFilter appearance or interaction between \be and \blur on the same lines?

You may remember that neither variable strength \be nor \blur existed in the original ASS spec, and were third-party patches added by jfs@Aegisub into VSFilter 2.39. xy-VSFilter has taken the safe route for the sake of compatibility, but only since we don't have a good sense of the impact or acceptance of making a change in this regard. As mentioned above:

At some point it would be good to come to some sort of consensus about how scripts utilizing \be should be handled, so users can have expected output in both xy-VSFilter and Libass.

[Cyberbeing]

I have now added \be screenshots to the folder. I completely forgot that the 6-bit thing also affects \be though!

Here are a couple quick comparisons with that 8-bit precision Cyberbeing/xy-VSFilter@def6de6 commit merged into xy-VSFilter Master without any additional tweaks for reference:

xy-VSFilter 6-bit \be VS. xy-VSFilter 8-bit \be

xy-VSFilter 8-bit \be VS. Libass 8-bit \be

xy-VSFilter 6-bit \blur VS. xy-VSFilter 8-bit \blur

xy-VSFilter 8-bit \blur VS. Libass 8-bit \blur

[astiob]

Oh, that made me realize that maybe I should’ve posted the scripts that I used for my screenshots. I’ve put them in a gist now. Sorry about that.

I didn’t have enough time for much experimentation today, but I’ve found that converting, with correct rounding, all pixel values from [0‥255] to [0‥64] at the beginning and back at the end of each \be iteration seems to work almost perfectly. (Edit: oh, but this is just the same as converting to [0‥64], then applying all \be iterations and then converting back to [0‥255].) Of course, this means the picture quality is lowered to 6 bits whenever \be is used, but it still allows everything that doesn’t have \be to be 8-bit.

If we then make sure to apply \blur after \be, we can even get \blur to be 8-bit regardless of the presence of \be… Oh wait, but VSFilter applies \be after \blur. And whenever \be has enough error for us to care, the order does matter (I presume). Oh well.

And of course, this doesn’t help with rescaling.

[astiob]

@x-xy-y
In Cyberbeing/xy-VSFilter@7ffcf12:

2. enlarge the image with the same bluradjust as VSFilter. The value is generally larger then the current value. The difference is important when combining \blur with \be

The VSFilter value, which is rounded, is smaller than the current/old xy-VSFilter value, which is ceiled. And does it actually affect \be output? To me it seems like the only difference in \be is ugly visual clipping, which we may want to either remove for quality or intentionally keep for compatibility with VSFilter. \blur itself is more complicated because its clipping affects the Gaussian kernel it uses.

[Cyberbeing]

When watching something today, I noticed that the current \blur implementation in Libass has the potential to cause strong discolored banding when layered.

https://www.mediafire.com/?4yq1e8r0qy3kc95

With VSFilter, there is no discoloring. Should this be moved to a separate issue?

[x-xy-y]

@astiob

The VSFilter value, which is rounded, is smaller than the current/old xy-VSFilter value, which is ceiled. And does it actually affect \be output?

No.