Summed Area Table

Definition

Summed Area Table is both an algorithm and data structure used in reference with the concept of Integral images. SAT is a name used to refer to both the method and the result of conversion of an image to an integral image.

SAT – The Algorithm

Summed Area Table (or Integral Image) is an algorithm applied on a 2-dimensional array of elements. It’s a simple, single pass algorithm to obtain the integral image values from the given pixel values of image.

SAT – The Data Structure

SAT also refers to the table of values generated after applying the conversion to Integral Image. This table of values is then used as input for improving the speed of more complicated operations.


Procedure
The algorithm takes as input, a table of order nxn and returns a table of order (n+1)x(n+1). The fundamental operation done here is to apply the following formula;


I(x,y) = i(x,y) + I(x-1,y) + I(x,y-1) - I(x-1,y-1)
Where, 
  i(x,y) = Element of image array i[x][y]
  I(x,y) =  Element of integral image array I[x][y]


The procedure can be better explained by the following code snippet