Sign in to follow this  
Tachikoma

Summed Area Tables - Handling Edges

Recommended Posts

I'm writing a software based image blurring function that uses SATs (summed area tables). I got the algorithm to work for the most part, but I'm finding the handling of image edges a bit messy. The image below is a SAT based blurred texture with an equivalent kernel size of 13 x 13 pixels. At the moment, I am trying to clip the kernel against the image border, and adjust the resulting averaging constant. It's not quite there yet, as evident by the dog's breakfast around the borders. Summed Area Table filtering In the example above, I have fair idea what the problem could be. Hence fixing that issue is not the real reason why I started in this thread. I'm more interested in finding neat a solution for handling borders - both for clamping and for repeating textures. I have been reading a bit of literature on this subject, including Crow's original paper, and I find it a bit surprising that there is not much coverage on the issue of borders. For example, Crow only wrote a vague paragraph about this, see the quote below (note, Crow assumes the image origin is at the bottom left corner):
Quote:
Where a texture is replicated many times over a surface, values lying to the right or above a boundary must be increased by the value at the boundary. In extreme cases, a pixel may contain several boundaries, implying that several whole texture images are mapped into one pixel. This case would require several additions to arrive at the proper values for the right and upper corners of the rectangle.
My interpretation of the excerpt above is that border cases need padding at the image edges with repeating pixel colours. The padding size will match the amount which kernel box overhangs. If your kernel box happens to be the size of the entire texture, then your total padded regions will make the SAT about twice as wide as the original image resolution. Quite hefty on the memory budget. Another option is to break up the overhanging kernel into smaller segment(s) and wrap each of them around the SAT table. This is quite fiddly, particularly handling cases at image corners. You end up implementing a lot of if-else statements that way. Are there alternative options for this?

Share this post


Link to post
Share on other sites
Sorry I didn't read all your post, but how about for clamping:
color=num=0;
for(vertical)
for(horizontal)
{ if(x>=0 and x<image_width and y>=0 and y<image_height)
{ color+=sample_color(x,y)
num++
}
}
color/=num
for repeating
for(vertical)
for(horizontal)
{ color+=sample_color((x+image_width)%image_width,(y+image_height)%image_height)
num++
}
color/=num

Share this post


Link to post
Share on other sites
You approach is a traditional box blur by the look of it, which defeats the purpose of using summed area tables in the first place. :P See here:

http://www.soe.ucsc.edu/classes/cmps160/Fall05/papers/p207-crow.pdf

The idea behind summed area tables is that you build a two dimensional running sum of the image, which allows you to perform arbitrary N x M kernel blurring with just four table accesses. This makes handling borders a bit problematic, as you can not apply the same wrapping and clamping techniques you normally use for conventional textures.



p.s. Magyar vagy talan?

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this