Summed Area Table (SAT) box filtering - GreycLab/gmic-community GitHub Wiki

The goal of this page is to explore in more detail some problems with Summed Area Table (SAT) based box filtering. Contributions to this are of course welcome. Image locations are assumed as (0,0) = top left.

Boundary Handling

It is not obvious how to simulate Neumann boundary conditions when using a 2D SAT box filter. Without this, the edges of a blurred image will not appear correct - although that can also be achieved with reduced windows at the edges. A desirable solution would leave the standard box sum computation as intact as possible: S(x1,y1) - S(x1,y0) - S(x0,y1) + S(x0,y0), while also keeping boundary comparisons to a minimum.

If the windows are centred this is achievable, while still allowing per-pixel window dimensions. The starting point is to define two functions T(x,y) and B(x,y) which can extrapolate the summed area past the top and bottom boundaries respectively (but not left and right edges). Then we use knowledge of which boundaries each of the four sums can pass, to define and extrapolate each of those (to minimise number of comparisons per function). Using the ternary operator:

T(x,y) = y > 1 ? S(x,y-1) : y * S(x,0)

B(x,y) = y < H ? S(x,y) : (1+y-H) * S(x,H) - (y-H) * S(x,H-1)

Here S(x,y) refers to a value in the summed area table at location (x,y), H is the table height minus one. Note this implies the extrapolated sum beyond the top is negative. Now we can create four new functions based on those to handle the left and right edges. Each sum location for a centred window can only cross two of the four boundaries: {top or bottom} and {left or right}. This means they can be defined using the relevant top T() or bottom B() functions:

D(x,y) = x > 1 ? T(x-1,y) : x * T(0,y)

E(x,y) = x < W ? T(x,y) : (1+x-W) * T(W,y) - (x-W) * T(W-1,y)

F(x,y) = x > 1 ? B(x-1,y) : x * B(0,y)

G(x,y) = x < W ? B(x,y) : (1+x-W) * B(W,y) - (x-W) * B(W-1,y)

Those are the D() = top left, E() = top right, F() = bottom left, G() = bottom right sums. W is the table width minus one. Again this implies the left extrapolated side is negative, but also that beyond the the top left corner for (-x,-y) is in fact positive. Finally the new computed window sum is:

G(x1,y1) - E(x1,y0) - F(x0,y1) + D(x0,y0)

Assumptions

The SAT will have the same dimensions as the input image (i.e. no extra rows). The sum at S(0,0) will be the value of the input image pixel I(0,0). There is no need to subtract 1 from x0 or y0, because the functions above include it.

Precision

It can easily be observed that for an origin at the top left, the accuracy of the sum will diminish with increasing x+y if the data type has limited precision. A simple way to improve that is to first subtract the image average, then add it back after blurring.