C#: the integral image (summed-area table)
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.
C#
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);
}
}