Bug 111177 - feGaussianBlur shows banding under certain circumstances
Summary: feGaussianBlur shows banding under certain circumstances
Status: NEW
Alias: None
Product: WebKit
Classification: Unclassified
Component: SVG (show other bugs)
Version: 528+ (Nightly build)
Hardware: Macintosh Intel OS X 10.6
: P2 Normal
Assignee: Nobody
URL:
Keywords: InRadar
Depends on:
Blocks: 68469
  Show dependency treegraph
 
Reported: 2013-03-01 06:46 PST by lars.sonchocky-helldorf
Modified: 2014-12-05 13:07 PST (History)
12 users (show)

See Also:


Attachments
feGaussianBlur-banding.svg (1.46 KB, image/svg+xml)
2013-03-01 06:46 PST, lars.sonchocky-helldorf
no flags Details
feGaussianBlur-banding.svg.screenshot.png (118.13 KB, image/png)
2013-03-01 06:47 PST, lars.sonchocky-helldorf
no flags Details
Screenshot using Pixie (99.81 KB, image/png)
2013-03-01 14:23 PST, lars.sonchocky-helldorf
no flags Details
feGaussianBlur-banding-rect.svg (1.37 KB, image/svg+xml)
2013-03-01 17:41 PST, lars.sonchocky-helldorf
no flags Details
Reduced test case -- X blur only, rounding errors only (617 bytes, image/svg+xml)
2013-03-03 12:24 PST, Stephen White
no flags Details
Reduced test case -- X blur only, w/color-interpolation-filters=sRGB (652 bytes, image/svg+xml)
2013-03-03 12:26 PST, Stephen White
no flags Details

Note You need to log in before you can comment on or make changes to this bug.
Description lars.sonchocky-helldorf 2013-03-01 06:46:50 PST
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)
Comment 1 lars.sonchocky-helldorf 2013-03-01 06:47:54 PST
Created attachment 190958 [details]
feGaussianBlur-banding.svg.screenshot.png
Comment 2 Dirk Schulze 2013-03-01 11:55:28 PST
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.
Comment 3 lars.sonchocky-helldorf 2013-03-01 14:13:28 PST
(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.
Comment 4 lars.sonchocky-helldorf 2013-03-01 14:23:24 PST
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.
Comment 5 lars.sonchocky-helldorf 2013-03-01 17:41:23 PST
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"
Comment 6 Florin Malita 2013-03-02 12:01:45 PST
(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.
Comment 7 lars.sonchocky-helldorf 2013-03-02 12:40:13 PST
(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.
Comment 8 Florin Malita 2013-03-02 18:34:23 PST
(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?
Comment 9 Dirk Schulze 2013-03-03 07:36:17 PST
(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.
Comment 10 Stephen White 2013-03-03 10:33:44 PST
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.)
Comment 11 Stephen White 2013-03-03 11:12:31 PST
(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".
Comment 12 Stephen White 2013-03-03 11:37:30 PST
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.
Comment 13 Stephen White 2013-03-03 12:24:59 PST
Created attachment 191138 [details]
Reduced test case -- X blur only, rounding errors only
Comment 14 Stephen White 2013-03-03 12:26:47 PST
Created attachment 191139 [details]
Reduced test case -- X blur only, w/color-interpolation-filters=sRGB
Comment 15 Stephen White 2013-03-03 12:43:16 PST
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.
Comment 16 Florin Malita 2013-03-04 07:20:26 PST
(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.
Comment 17 lars.sonchocky-helldorf 2013-03-08 09:35:22 PST
(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
Comment 18 Radar WebKit Bug Importer 2014-12-05 12:31:40 PST
<rdar://problem/19160130>