Rectangle spreading blur (not only for DoF)

Hi community,

I wonder if anyone of you read the 2009-2010 papers from Kosloff and Barsky on rectangle spreading. I'm having problems with some small details in "Depth of Field Postprocessing For Layered Scenes Using Constant-Time Rectangle Spreading" paper (http://www.cs.berkel...lur/kosloff.pdf). Concretely, Fig 3 bottom, which represents the normalisation table and then (therefore) with variable per-pixel blur radii (e.g. coming from CoC), and then in general with arbitrary PSFs (but that's another story).

I need to understand, why is the normalisation image a pixel wider (in each direction) than the original input image, how will this change if a smaller or larger kernel is used and ultimately what will happen with these extra pixels, which are in fact out of the input image, when variable blur will be used (Fig 3 has a constant PSF 3x3 "kernel").

I'm unable to find any implementation of any spreading (scattering) blur algorithm, including their DX10 implementation, which they mention (DX, GL, C++, Matlab, ... anything would be helpful).

Anyone feeling like reading the paper and helping me out by discussing it here?

Nice paper... looks like a solution to my DOF problems on a quick skim(maybe motion blur too). When I finish fixing/optimizing my engine due to the transition to dx11 I will definatly give it a look. Might be a while though:-(

[quote name='pcmaster' timestamp='1308144659' post='4823592']
Hi community,

I wonder if anyone of you read the 2009-2010 papers from Kosloff and Barsky on rectangle spreading. I'm having problems with some small details in "Depth of Field Postprocessing For Layered Scenes Using Constant-Time Rectangle Spreading" paper (http://www.cs.berkel...lur/kosloff.pdf). Concretely, Fig 3 bottom, which represents the normalisation table and then (therefore) with variable per-pixel blur radii (e.g. coming from CoC), and then in general with arbitrary PSFs (but that's another story).

I need to understand, why is the normalisation image a pixel wider (in each direction) than the original input image, how will this change if a smaller or larger kernel is used and ultimately what will happen with these extra pixels, which are in fact out of the input image, when variable blur will be used (Fig 3 has a constant PSF 3x3 "kernel").

I'm unable to find any implementation of any spreading (scattering) blur algorithm, including their DX10 implementation, which they mention (DX, GL, C++, Matlab, ... anything would be helpful).

Anyone feeling like reading the paper and helping me out by discussing it here?

Nice paper... looks like a solution to my DOF problems on a quick skim(maybe motion blur too). When I finish fixing/optimizing my engine due to the transition to dx11 I will definatly give it a look. Might be a while though:-(
[/quote]


Hmmm, that paper makes no sense... There is not really a proper description of the algorithm or why it works...

David

I need to understand, why is the normalisation image a pixel wider (in each direction) than the original input image, how will this change if a smaller or larger kernel is used and ultimately what will happen with these extra pixels, which are in fact out of the input image, when variable blur will be used (Fig 3 has a constant PSF 3x3 "kernel").

From what I can tell, the normalization buffer should extend beyond the border to the 'radius' of the kernel. e.g. With the 3x3 kernel, each pixel "gathers" (via scattering, of course) data from a radius of 1px. In order for the normalization to work, it has to gather a value of 1.0f from each neighbour in this radius - hence the larger normalization buffer.

The intermediate buffer shown in Fig3-c won't be generated correctly if the normalization buffer wasn't expanded like this.

Using a spreadsheet program, you can quickly implement the process shown in Fig3-b to demonstrate this visually -- I find it easier to understand some systems when I can tweak them visually and see the results.Note the valid & invalid results from the two inputs:
Here's my ODF format spreadsheet: [attachment=3282:normalization.zip] (Edit the values on sheet 2 only!)


[Edit #2]I added the process shown in Fig3-d, which produces Fig3-e to the spreadsheet too. Here's the updated version: [attachment=3283:normalization2.zip]

Thank you for the spreadsheet. I did this calculation myself and saw quite the same -- it won't work, if the normalisation image/table isn't bigger than the input image. My main concern, however, is how to implement variable per-pixel blur radii. Should I pad the normalisation image/table by the biggest possible filter size? Or what? The example is for 3x3 only :-( Also, what would be the smallest possible kernel/filter/psf? How would data spread if I wanted no blur (ie. 1 pixel)?

Do I understand correctly, that I do the same spreading for each pixel of the original input image AND for the normalisation image?

I edited my above post while you were replying btw

Should I pad the normalisation image/table by the biggest possible filter size?

I guess so

How would data spread if I wanted no blur (ie. 1 pixel)?[/quote]For a zero-radius blur, I guess the "corner-spreading" process would look like:18| 0 --> 18|-18
0| 0 -18| 18

Do I understand correctly, that I do the same spreading for each pixel of the original input image AND for the normalisation image?[/quote]That's how I've understood it.

N.B. I've only just read it quickly too (not implemented it), so take this confirmation with a pinch of salt

Now, how to handle "background" pixels? Imagine a single quad on a default, black (or coloured) background. Will this method spread the background pixels too?
And since we all think the same spreading operation applies to both the input image pixels and normalisation image pixels (which are 1.0 in the beginning), what operation applies to the normalisation pixels, which lie in the padding, outside of the input image pixels? I hope it's understandable

When using it for DOF, each pixel's blur radius comes from your depth information. If you've got some kind of background-mask, you could use that to determine the blur-radius (so that background pixels don't spread themselves).

Not sure I get what you mean regarding the padding pixels... but the answer might be "they're treated the same".


I had a go at implementing a 5x5 kernel, as well as the 3x3 kernel from earlier, and added a "colour" channel to go with the normalization channel.
The whole of Fig3 should be implemented in here now: [attachment=3286:normalization3.zip]


The logic behind the size of the padding areas hasn't quite clicked with me yet though...
unless I've done something wrong:
With the 3x3 kernel (radius 1), the normalization channel needs 1px of padding, and then the accumulation table needs 2px of padding.
With the 5x5 kernel (radius 2), the normalization channel needs 3px of padding, and then the accumulation table needs 5px of padding.

They don't explain this detail, and I feel like I'll have to implement some more kernel sizes before their logic reveals itself to me

[edit]Another detail that confuses me -- in their psuedo-code, they divide the 'corner' values by the area of the rectangle, which they don't do in the illustration. Performing this division seems unnecessary when the normalization buffer is doing the same thing!?
They also say that their table is the same size as the image, but then in the Fig3 description, they mention that the table requires padding. In the same description, they say that the normalization channel is the size of the image, yet they draw it with a border of padding pixels

That's exactly why I spawned this thread, it's confusing. I noticed the same discrepancies in the description, also that they divide by area in the pseudo-code but use normalisation elsewhere (which really seem to do the same work). I mailed Kosloff yesterday, asking whether any of the authors would try to help me out. No answer so far. I'll get back here right after I try treating a 11..11 normalisation image with the same size the same way as the input image.

Ok,

it works "somehow", giving slightly different results when I divide by the normalisation image and when I divide each spread corner by rectangle area. Each gives different artefacts.
I still don't quite understand how to treat background (if I spread background pixels too, they "eat" the other objects, if I don't, the edges are very weird). I also don't understand the layers they mention in the paper. And lastly, I don't get how they raised the PSF limitations.

I can imagine emulating arbitrary "constant-intesity" filters/kernels ("bokehs") by spreading several rectangles from each pixel. I can even imagine more difficult kernels but not completely arbitrary PSFs. I don't get it

Picture showing constant blurs, applied to all pixels (including black background). No normalisation, spread factors rather divided by area.
This should be equal to normal gather blur and according to photoshop, it seems pixel perfect (there is no SAT precision fix yet). It's fast as hell

Nice work on the results.

I also don't understand the layers they mention in the paper.

They're introduced in the referenced works, such as Elimination of artifacts due to occlusion and discretization problems in image space blurring techniques.
Short description seems to be -- they split the image based on depth, blur those images separately, and then re-composite them so that distant objects don't blur over the top of near objects.

I can imagine emulating arbitrary "constant-intesity" filters/kernels ("bokehs") by spreading several rectangles from each pixel. I can even imagine more difficult kernels but not completely arbitrary PSFs. I don't get it [/quote]Yeah to get arbitrarily shaped constant-intensity filters, you basically make one rectangle per row of pixels covered.
e.g. an oval shaped kernel - made up of a 3x1, a 7x1 and a 3x1 stacked on top of each other (think i drew it right...) 0 0 0 1 0 0 -1 0 0 0
0 1 0 -1 0 0 1 0 -1 0
0 -1 0 1 0 0 -1 0 1 0
0 0 0 -1 0 0 1 0 0 0
To make the density vary (i.e. non-constant-intensity), you'd have to also have more than one rectangle per row of pixels.
e.g. To spread a single pixel out into 3 columns of pixels - a 1px wide center column flanked by two brighter 3px wide columns with bright centers:
(i.e. [font="'Courier New"]000010000[/font] becomes the pattern [font="'Courier New"]232010232[/font]) 2 1 -1 -2 1 -1 2 1 -1 -2
-2 -1 1 2 -1 1 -2 -1 1 2(think i drew it right...)

Hi again, I've been busy with some other things too, so here's my late answer. I believe it will help someone.

I managed to get the spreading blur right, even with DoF. I got some answers from the paper authors and it turned out that we're supposed to do both normalisation and divide each fragment's colour by the spread rectangle area. They also say that the 1-pixel bigger normalisation table is an error in the paper :-) :-) Very helpful, isn't it? So, do exactly the same spreads to RGBA and normalisation, in the same resolution. Also, to support floating-point per-pixel sizes of blur (necessary for DoF), you need to spread 2 rectangles from each pixel, the first one with a "floor" size and the second one with a "ceil" size, weighed according to their ratios -- that is for CoC 4.73 spread a (4*2+1)^2 pixel rectangle with weight 0.27 and a (5*2+1)^2 rectangle weighed 0.73.

I also managed to implement "arbitrary" filters/kernels/bokehs of constant intensity, which, however, take much more time, since you don't spread rectangles but lines. The slowdown is proportional to the filter's perimeter (in final resolution depending on per-pixel CoC, for example). Not quite usable for games but usable for interactive and off-line rasterisers.

One interesting random thing to mention, which I almost overlooked, is that you don't need to do any precision hacks to the SAT itself, since we're spreading positive and negative deltas (corners), which will more-or-less cancel out and therefore the floating point numbers resolution doesn't suffer as if you summed just positive values (i.e. [0-1]).

Also, we've managed to implement motion blur by extending this technique but I'm not quite ready to disclose much info right now. Perhaps if someone's interested. It's definitely not usable for games (especially with the non-square filter shapes).