C#: the integral image (summed-area table)

Precompute running sums so that the total of any rectangle takes four lookups.

using System;

class Program {
  static void Main() {
    int[,] image = new int[4, 4];
    int value = 1;
    for (int r = 0; r < 4; r++) {
      for (int c = 0; c < 4; c++) {
        image[r, c] = value++;
      }
    }

    int[,] integral = new int[5, 5];
    for (int r = 1; r <= 4; r++) {
      for (int c = 1; c <= 4; c++) {
        integral[r, c] = image[r - 1, c - 1] + integral[r - 1, c] + integral[r, c - 1] - integral[r - 1, c - 1];
      }
    }
    Console.WriteLine("total of the whole image: " + integral[4, 4]);

    int top = 1, left = 1, bottom = 2, right = 2;
    int box = integral[bottom + 1, right + 1] - integral[top, right + 1] - integral[bottom + 1, left] + integral[top, left];
    Console.WriteLine("sum of rows 1-2, columns 1-2: " + box);
  }
}

Output

total of the whole image: 136
sum of rows 1-2, columns 1-2: 34

Explanation

An integral image stores at each position (r, c) the sum of all pixels above and to the left of it, inclusive. It is built in one pass using I[r,c] = pixel + I[r−1,c] + I[r,c−1] − I[r−1,c−1], where the last term removes the area that would be counted twice.

Once built, the sum of any rectangle needs only four table values: the bottom-right corner, minus the strip above, minus the strip to the left, plus the corner that was removed twice. The cost is independent of the rectangle size, which is why box filters and the Viola–Jones face detector use integral images.

Explore the dry run

Guided walkthroughReady

1using System;

3class Program {

4 static void Main() {

5 int[,] image = new int[4, 4];

6 int value = 1;

7 for (int r = 0; r < 4; r++) {

8 for (int c = 0; c < 4; c++) {

9 image[r, c] = value++;

10 }

11 }

13 int[,] integral = new int[5, 5];

14 for (int r = 1; r <= 4; r++) {

15 for (int c = 1; c <= 4; c++) {

16 integral[r, c] = image[r - 1, c - 1] + integral[r - 1, c] + integral[r, c - 1] - integral[r - 1, c - 1];

17 }

18 }

19 Console.WriteLine("total of the whole image: " + integral[4, 4]);

21 int top = 1, left = 1, bottom = 2, right = 2;

    int box = integral[bottom + 1, right + 1] - integral[top, right + 1] - integral[bottom + 1, left] + integral[top, left];

23 Console.WriteLine("sum of rows 1-2, columns 1-2: " + box);

24 }

25}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
One extra row and column of zeros, so no special cases are needed at the border.	`first row and column are 0`	—
Add the pixel and the sums above and to the left, then subtract the overlap counted twice.	`first row and column are 0`	—
The bottom-right entry is the sum of all 16 pixels: 1 + 2 + ... + 16.	`integral[4,4] = 136`	total of the whole image: 136
Four lookups give the sum of 6 + 7 + 10 + 11 for the central 2×2 block.	`box = 34`	total of the whole image: 136
The cost does not depend on the rectangle size.	`box = 34`	total of the whole image: 136 sum of rows 1-2, columns 1-2: 34

Cost and common mistakes

Building takes O(R·C) time and space. Each rectangle sum is then O(1).

Off-by-one mistakes are the usual bug. The padded border row and column keep the indices simple.
Large images can overflow int in the table. Use long for big or 16-bit images.

Try it yourself

What is the sum of the top-left 2×2 block?

Reveal answer and reasoning

1 + 2 + 5 + 6 = 14, which is integral[2, 2].

C#: the integral image (summed-area table)

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading