Во многих задачах обработки изображений требуется рассчитывать яркость прямоугольного участка изображения. Например, в вейвлет-преобразованиях, фильтрах Хаара, SURF и многих других алгоритмах. Интегральное представление позволяет быстро рассчитывать суммарную яркость произвольного прямоугольника, причем время рассчета не зависит от площади прямоугольника.

Интегральное представление

Интегральное представление изображения представляет собой матрицу, размерность которой совпадает с размерностью исходного изображения. Элементы матрицы рассчитываются по следующей формуле:



Где I(i,j) — яркость пиксела исходного изображения.

Каждый элемент матрицы II[x,y] представляет собой сумму пикселов в прямоугольнике от (0,0) до (x,y). Рассчет матрицы занимает линейное время, пропорциональное числу пикселов в изображении.

Рассчет матрицы можно производить по рекуррентной формуле:

II(x,y) = I(x,y) — II(x-1,y-1) + II(x,y-1) + II(x-1,y)

(код на C# приведен ниже)

Интегральное представление имеет интересную особенность. По интегральной матрице можно очень быстро вычислить сумму пикселов произвольного прямоугольника, произвольной площади.

Пусть ABCD — интересующий нас прямоугольник:


Из рисунка понятно, что сумму внутри прямоугольника можно выразить через суммы и разности смежных прямоугольников по следующей формуле:

SumOfRect(ABCD) = II(A) + II(С) — II(B) — II(D)

Простая и замечательная формула. Все компоненты для вычисления уже хранятся в интегральной матрице, вычисление занимает четыре обращения к массиву и три арифметических действия.

Аппроксимация круга

Применяя интегральную матрицу, можно вычислять яркости и более сложных фигур. Для примера возьмем круг. Яркость круга бывает очень полезна для вычисления дискрипторов, инвариантных относительно вращения.

Аппроксимируем круг фигурой, показанной на картинке:



Данное приближение является достаточно грубым, однако для многих практических целей вполне приемлемым.
Для вычисления суммы пикселов внутри фигуры, применим дискретную теорему Грина, и получим следующую формулу:

SumOfFigure(ABCDEFGHIJKL)=II(A)-II(B)+II(С)-II(D)+II(E)-II(F)+II(G)-II(H)+II(I)-II(J)+II(K)-II(L)

где
A=(X-r, Y-R) B=(X+r, Y-R)
C=(X+r, Y-r) D=(X+R, Y-r)
E=(X+R, Y+r) F=(X+r, Y+r)
G=(X+r, Y+R) H=(X-r, Y+R)
I=(X-r, Y+r) J=(X-R, Y+r)
K=(X-R, Y-r) L=(X-r, Y-r)
r=R/√2
R — радиус круга
(X,Y) — центр круга

Как видим, формула требует 12 обращений к интегральной матрице и 11 арифметических операций (не считая рассчета координат самих точек фигуры).

Реализация C#

Первый метод производит вычисление интегральной матрицы. Второй — рассчитывает суммарную яркость произвольного прямоугольника:

    //вычисление интегрального представления изображения
    public static int[,] IntegralImage(int[,] sourceImage)
    {
      int width = sourceImage.GetLength(0);
      int height = sourceImage.GetLength(1);

      int[,] result = new int[width, height];

      result[0, 0] = sourceImage[0, 0];
      for (int x = 1; x < width; x++)
        result[x, 0] = sourceImage[x, 0] + result[x - 1, 0];
      for (int y = 1; y < height; y++)
        result[0, y] = sourceImage[0, y] + result[0, y - 1];

      for (int y = 1; y < height; y++)
        for (int x = 1; x < width; x++)
          result[x, y] = sourceImage[x, y] + result[x - 1, y] + result[x, y - 1] - result[x - 1, y - 1];

      return result;
    }

    //рассчет суммы яркости пикселов в произвольном прямоугольнике
    public static int SumOfRectangle(int[,] integralImage, Rectangle rect)
    {
      int A = 0, B = 0, C = 0, D = 0;
      if (rect.Top > 0 || rect.Left > 0)
        if (rect.Top <= 0)
          D = integralImage[rect.Left - 1, rect.Bottom];
        else
        if (rect.Left <= 0)
          B = integralImage[rect.Right, rect.Top - 1];
        else
        {
          A = integralImage[rect.Left - 1, rect.Top - 1];
          B = integralImage[rect.Right, rect.Top - 1];
          D = integralImage[rect.Left - 1, rect.Bottom];
        }

      C = integralImage[rect.Right, rect.Bottom];
      return A + C - B - D;
    }

Ссылки:
Wiki. Summed area table
YouTube. Semi-discrete Calculus.
Применение в SURF (eng)
Модификация для прямоугольников, повернутых на 45 градусов (eng)
Дискретная теорема Грина (eng)