Bug 111177 – feGaussianBlur shows banding under certain circumstances

• Status: NEW
• Component: SVG

Created attachment 190956 [details]
feGaussianBlur-banding.svg

See the attached SVG and screenshot. I've done this using Google Chrome since WebKit Nightly is no longer supported for 10.6.8. Looks like clipping or overflow (because of light, darker, light bands)

Google Chrome	25.0.1364.99 (Offizieller Build 183764) 
Betriebssystem	Mac OS X 
WebKit	537.22 (@143379)

Created attachment 190958 [details]
feGaussianBlur-banding.svg.screenshot.png

[Dirk Schulze]

Can you be a bit more precise about what you would expect? I can confirm that the filtered result looks the same in Chromium. Firefox fails and seems to run into circles, Opera displays it the same as WebKit.

Looking at the source, it does exactly what I would expect it to look like. You filter a text "text". Note that the "t" is larger than the "ex". This leads to the three bands that you mentioned.

(In reply to comment #2)
> Can you be a bit more precise about what you would expect? I can confirm that the filtered result looks the same in Chromium. Firefox fails and seems to run into circles, Opera displays it the same as WebKit.
> 
> Looking at the source, it does exactly what I would expect it to look like. You filter a text "text". Note that the "t" is larger than the "ex". This leads to the three bands that you mentioned.

If you look closely you see an alternation of darker and brighter bandings in the resulting gradient. I expect a smooth gradient without such alternations. I assume some byte swapping or overflow issues occurring here. Take a look at the screenshot using "Pixie.app" from the Mac OS X developer tools ( http://macapper.com/2007/04/16/the-gems-of-apples-development-tools/ ) or something similar.

Created attachment 191036 [details]
Screenshot using Pixie

This screenshot shows the banding (alternation of darker and brighter bands) using Pixie. If SVG is supposed to replace flash such details count.

Created attachment 191083 [details]
feGaussianBlur-banding-rect.svg

(In reply to comment #2)
> You filter a text "text". Note that the "t" is larger than the "ex". This leads to the three bands that you mentioned.

This happens also when I filter a rect. Have a look at the attachment "feGaussianBlur-banding-rect.svg"

[Florin Malita]

(In reply to comment #4)
> Created an attachment (id=191036) [details]
> Screenshot using Pixie
> 
> This screenshot shows the banding (alternation of darker and brighter bands) using Pixie. If SVG is supposed to replace flash such details count.

So the way I interpret this, the complaint in not strictly related to the presence of bands (they're unavoidable withing a discrete colorspace), but to their non-monotonic nature (lighter-darker-lighter instead of lighter-darker-darkerstill).

AFAICT the color component difference between adjacent bands is not larger than one (as expected), but the alternation is indeed non-monotonic: #565656 -> #575757 -> #565656 -> #555555 -> #545454 -> #555555.

> I expect a smooth gradient without such alternations.

That may be the root of the problem though: this is a Gaussian blur, not a gradient. I'm no feGaussianBlur expert, but your expectation may be unfounded.

I haven't tested IE and FF can't handle the samples, but Opera definitely implements feGaussianBlur similarly.

(In reply to comment #6)
> (In reply to comment #4)
> > Created an attachment (id=191036) [details] [details]
> > Screenshot using Pixie
> > 
> > This screenshot shows the banding (alternation of darker and brighter bands) using Pixie. If SVG is supposed to replace flash such details count.
> 
> So the way I interpret this, the complaint in not strictly related to the presence of bands (they're unavoidable withing a discrete colorspace), but to their non-monotonic nature (lighter-darker-lighter instead of lighter-darker-darkerstill).
> 
> AFAICT the color component difference between adjacent bands is not larger than one (as expected), but the alternation is indeed non-monotonic: #565656 -> #575757 -> #565656 -> #555555 -> #545454 -> #555555.
> 
> > I expect a smooth gradient without such alternations.
> 
> That may be the root of the problem though: this is a Gaussian blur, not a gradient. I'm no feGaussianBlur expert, but your expectation may be unfounded.

If you have a look at a Gaussian distribution curve it is indeed smooth and not jagged. So my expectation is not unfounded.

> 
> I haven't tested IE and FF can't handle the samples, but Opera definitely implements feGaussianBlur similarly.

Might be, but then Opera is also wrong. There might be a problem with the algorithm as such (I must confess I did not look at the algorithm used).

It boils down to the point that what is currently there is just not usable. It looks awkward. And please don't tell me to use a gradient instead. This is just a test case I provide here to show what is going on. I need to use feGaussianBlur (I use an animated version of this where I animate the parameter stdDeviation) and I know what I am doing.

[Florin Malita]

(In reply to comment #7)
> (In reply to comment #6)
> > > I expect a smooth gradient without such alternations.
> > 
> > That may be the root of the problem though: this is a Gaussian blur, not a gradient. I'm no feGaussianBlur expert, but your expectation may be unfounded.
> 
> If you have a look at a Gaussian distribution curve it is indeed smooth and not jagged. So my expectation is not unfounded.

If you insist on mathematically correct results, sure. But that may not be practical - see how FF handles the tests while presumably generating an exact blur :)

The current WK implementation uses various approximations for performance reasons:

1) feGausianBlur devolves into a 3-pass box blur for large stdDeviation values. This is explicitly allowed by the spec - see http://www.w3.org/TR/SVG/filters.html#feGaussianBlurElement

2) box blur itself is implemented in two one-dimensional passes (horizontal vs. vertical) to keep the runtime in O(n^2) bounds

Even considering the above, I couldn't immediately explain the non-monotonic banding. But after some digging, I found that #2 above is the problem.

It basically boils down to accumulated rounding errors: each box blur pass ends up rounding the components independently. Combine that with loss of precision from using a pre-multiplied format (again required by the spec), and you get enough color-vs-alpha rounding jitter to affect the the composited result.

Here's a trace for a scanline crossing a few of these bands (keep in mind that the blur values are pre-multiplied). Even though the individual components are monotonically increasing, relative red/alpha variations introduced by rounding errors can cause the composited result to be non-monotonic:

>> [153, 250] bg_red: 85, blur_red: 0, blur_alpha: 0, composited_red: 85
>> [154, 250] bg_red: 85, blur_red: 0, blur_alpha: 0, composited_red: 85
>> [155, 250] bg_red: 85, blur_red: 1, blur_alpha: 1, composited_red: 85
>> [156, 250] bg_red: 85, blur_red: 1, blur_alpha: 1, composited_red: 85
>> [157, 250] bg_red: 85, blur_red: 1, blur_alpha: 2, composited_red: 85
>> [158, 250] bg_red: 85, blur_red: 2, blur_alpha: 2, composited_red: 86
>> [159, 250] bg_red: 85, blur_red: 2, blur_alpha: 3, composited_red: 86
>> [160, 250] bg_red: 85, blur_red: 2, blur_alpha: 3, composited_red: 86
>> [161, 250] bg_red: 85, blur_red: 3, blur_alpha: 4, composited_red: 86
>> [162, 250] bg_red: 85, blur_red: 3, blur_alpha: 4, composited_red: 86
>> [163, 250] bg_red: 85, blur_red: 3, blur_alpha: 4, composited_red: 86
>> [164, 250] bg_red: 85, blur_red: 4, blur_alpha: 5, composited_red: 87
>> [165, 250] bg_red: 85, blur_red: 4, blur_alpha: 5, composited_red: 87
>> [166, 250] bg_red: 85, blur_red: 5, blur_alpha: 6, composited_red: 88
>> [167, 250] bg_red: 85, blur_red: 5, blur_alpha: 6, composited_red: 88
>> [168, 250] bg_red: 85, blur_red: 5, blur_alpha: 7, composited_red: 87   <- BZZZZZT!
>> [169, 250] bg_red: 85, blur_red: 6, blur_alpha: 7, composited_red: 88
>> [170, 250] bg_red: 85, blur_red: 6, blur_alpha: 8, composited_red: 88
>> [171, 250] bg_red: 85, blur_red: 6, blur_alpha: 8, composited_red: 88
>> [172, 250] bg_red: 85, blur_red: 7, blur_alpha: 9, composited_red: 89
>> [173, 250] bg_red: 85, blur_red: 7, blur_alpha: 9, composited_red: 89
>> [174, 250] bg_red: 85, blur_red: 8, blur_alpha: 10, composited_red: 89
>> [175, 250] bg_red: 85, blur_red: 8, blur_alpha: 10, composited_red: 89
>> [176, 250] bg_red: 85, blur_red: 8, blur_alpha: 11, composited_red: 89
>> [177, 250] bg_red: 85, blur_red: 9, blur_alpha: 11, composited_red: 90
>> [178, 250] bg_red: 85, blur_red: 9, blur_alpha: 11, composited_red: 90
>> [179, 250] bg_red: 85, blur_red: 9, blur_alpha: 12, composited_red: 90
>> [180, 250] bg_red: 85, blur_red: 10, blur_alpha: 12, composited_red: 91
>> [181, 250] bg_red: 85, blur_red: 10, blur_alpha: 13, composited_red: 90   <- BZZZZZT!
>> [182, 250] bg_red: 85, blur_red: 11, blur_alpha: 13, composited_red: 91
>> [183, 250] bg_red: 85, blur_red: 11, blur_alpha: 14, composited_red: 91
>> [184, 250] bg_red: 85, blur_red: 11, blur_alpha: 14, composited_red: 91
>> [185, 250] bg_red: 85, blur_red: 12, blur_alpha: 15, composited_red: 92
>> [186, 250] bg_red: 85, blur_red: 12, blur_alpha: 15, composited_red: 92
>> [187, 250] bg_red: 85, blur_red: 12, blur_alpha: 16, composited_red: 91   <- BZZZZZT!
>> [188, 250] bg_red: 85, blur_red: 13, blur_alpha: 16, composited_red: 92
...

I agree that this is undesirable, but I can't see a good solution that doesn't obliterate performance. Maybe keeping track of rounding errors across box blur passes and compensating would work?

[Dirk Schulze]

(In reply to comment #7)
> (In reply to comment #6)
> > (In reply to comment #4)
> > > Created an attachment (id=191036) [details] [details] [details]
> > > Screenshot using Pixie
> > > 
> > > This screenshot shows the banding (alternation of darker and brighter bands) using Pixie. If SVG is supposed to replace flash such details count.
> > 
> > So the way I interpret this, the complaint in not strictly related to the presence of bands (they're unavoidable withing a discrete colorspace), but to their non-monotonic nature (lighter-darker-lighter instead of lighter-darker-darkerstill).
> > 
> > AFAICT the color component difference between adjacent bands is not larger than one (as expected), but the alternation is indeed non-monotonic: #565656 -> #575757 -> #565656 -> #555555 -> #545454 -> #555555.
> > 
> > > I expect a smooth gradient without such alternations.
> > 
> > That may be the root of the problem though: this is a Gaussian blur, not a gradient. I'm no feGaussianBlur expert, but your expectation may be unfounded.
> 
> If you have a look at a Gaussian distribution curve it is indeed smooth and not jagged. So my expectation is not unfounded.
> 
> > 
> > I haven't tested IE and FF can't handle the samples, but Opera definitely implements feGaussianBlur similarly.
> 
> Might be, but then Opera is also wrong. There might be a problem with the algorithm as such (I must confess I did not look at the algorithm used).
> 
> It boils down to the point that what is currently there is just not usable. It looks awkward. And please don't tell me to use a gradient instead. This is just a test case I provide here to show what is going on. I need to use feGaussianBlur (I use an animated version of this where I animate the parameter stdDeviation) and I know what I am doing.

Did you try to use feConvolveMatrix? This allows you to use a kernel matrix. Maybe if you simulate it, it looks better? It will definitely slower though.

[Stephen White]

I'm pretty sure this is caused not by the gaussian blur per se, but by the lookup tables used to apply gamma conversion after filter application.

If you try applying color-interpolation-filters="sRGB" to the filters (both the morphology and the blur), it will skip the LUT step, which should reduce the banding.  The results may not be mathematically correct, but the visual result is a lot better in many cases.

(As to why WebKit's generic LUT application introduces banding while Safari's CoreGraphics implementation does not, I'm not sure.)

[Stephen White]

(In reply to comment #10)
> I'm pretty sure this is caused not by the gaussian blur per se, but by the lookup tables used to apply gamma conversion after filter application.

I take it back -- in this case, the LUT application accentuates the problem, but does not cause it:  the colors are still non-monotonically increasing, even with color-interpolation-filters="sRGB".

[Stephen White]

Interestingly, the problem still seems to occur if you use a stdDeviation of "50 0", which should eliminate the Y pass of each blur in the Skia implementation.  This suggest to me it's not the fact that it's a separable blur.

[Stephen White]

Created attachment 191138 [details]
Reduced test case -- X blur only, rounding errors only

[Stephen White]

Created attachment 191139 [details]
Reduced test case -- X blur only, w/color-interpolation-filters=sRGB

[Stephen White]

For posterity, I've attached my reduced test cases.  They show just the banding, without the "gradient" (blur) effect.  It's much reduced with color-interpolation-filters=sRGB:  it varies between 49-50 (vs 44-48 without it).

I'm still a little confused as to how we're getting alpha values introduced at all in this case, but that's probably just my lack of SVG-fu.

[Florin Malita]

(In reply to comment #11)
> (In reply to comment #10)
> > I'm pretty sure this is caused not by the gaussian blur per se, but by the lookup tables used to apply gamma conversion after filter application.
> 
> I take it back -- in this case, the LUT application accentuates the problem, but does not cause it:  the colors are still non-monotonically increasing, even with color-interpolation-filters="sRGB".

Yes, the trace above is a direct dump from the filter effect buffer.

> Interestingly, the problem still seems to occur if you use a stdDeviation of "50 0", which should eliminate the Y pass of each blur in the Skia implementation.  This suggest to me it's not the fact that it's a separable blur.

I'm not too surprised: in my testing I had changed the implementation to a single pass box blur in order to isolate the problem, and under those conditions a X-only or Y-only pass was not enough to trigger it. But if we're doing all three passes it's more likely for this to happen even with a one-dimensional stddev.

> I'm still a little confused as to how we're getting alpha values introduced at all in this case, but that's probably just my lack of SVG-fu.

Just from looking at the implementation, we're box-blurring all channels independently - including alpha.

I'm quite convinced now that this is just a precision issue. With the original test, the fill color is solid #cccccc. So we're blurring 0->0xcc edges for RGB, and 0->0xff edges for A => this yields a difference in rounding, and introduces enough variance in the (R,G,B)/A ratio to break the monotonicity of the composited values. I've plugged the numbers from that trace in a spreadsheet to better illustrate this: https://docs.google.com/spreadsheet/ccc?key=0AmPAhmQe58QjdHpMVjFkLXRXU3JFbG1kWXZ1Sjkzb0E

For example, consider a kernel of 20% coverage. Then for alpha we get 255 / 5 = 51, with 0 rounding error. For R/G/B we get 204 / 5 = 40, discarding 0.8 in flooring. Now suddenly our blur result is somewhat darker than it should be, and if the rounding stars also align when compositing, the composited result is also darker.

(In reply to comment #16)
> I'm not too surprised: in my testing I had changed the implementation to a single pass box blur in order to isolate the problem, and under those conditions a X-only or Y-only pass was not enough to trigger it. But if we're doing all three passes it's more likely for this to happen even with a one-dimensional stddev.
> 
> > I'm still a little confused as to how we're getting alpha values introduced at all in this case, but that's probably just my lack of SVG-fu.
> 
> Just from looking at the implementation, we're box-blurring all channels independently - including alpha.
> 
> I'm quite convinced now that this is just a precision issue. With the original test, the fill color is solid #cccccc. So we're blurring 0->0xcc edges for RGB, and 0->0xff edges for A => this yields a difference in rounding, and introduces enough variance in the (R,G,B)/A ratio to break the monotonicity of the composited values. I've plugged the numbers from that trace in a spreadsheet to better illustrate this: https://docs.google.com/spreadsheet/ccc?key=0AmPAhmQe58QjdHpMVjFkLXRXU3JFbG1kWXZ1Sjkzb0E
> 
> For example, consider a kernel of 20% coverage. Then for alpha we get 255 / 5 = 51, with 0 rounding error. For R/G/B we get 204 / 5 = 40, discarding 0.8 in flooring. Now suddenly our blur result is somewhat darker than it should be, and if the rounding stars also align when compositing, the composited result is also darker.

Just an idea to get some precision in such a case (if just must use integer in that case). Multiply by some amount, do your calculations and divide back through the same amount. Example: 

your calculation:

204 / 5 = 40,8 --cut off decimal--> 40

your calculation with more precision:

204 / 5 --multiply by 10--> 2040 / 50 = 408 --round by adding 5->  413 --divide back by 10 --> 41,3  --cut off decimal--> 41

For your computations you would off course not take decimal values to increase the precision but hex values:

0xCC / 0x05 * 0x10 = 0x0CC0 / 0x05 = 028C --round by adding 0x08--> 0x294 --cut of half a byte--> 0x29 = 41 decimal

I hope you're not doing your calculations using 8 bit integers

[Radar WebKit Bug Importer]

<rdar://problem/19160130>