Дискретная теорема Грина

Пусть ${\displaystyle f}$ — локально интегрируемая функция на плоскости ${\displaystyle \mathbb {R} ^{2}}$; тогда существует её первообразная (в смысле двойного интеграла с фиксированным нижним пределом)

${\displaystyle F(x,y)\equiv \int _{-\infty }^{y}\!\!\int _{-\infty }^{x}f(u,v)\,du\,dv}$

(или от произвольной точки ${\displaystyle (x_{0},y_{0})}$, если функция имеет компактный носитель). Функция ${\displaystyle F}$ определена при любом локально интегрируемом ${\displaystyle f}$ (существование гарантировано теоремой Фубини; для непрерывной ${\displaystyle f}$ функция ${\displaystyle F}$ удовлетворяет ${\displaystyle {\frac {\partial ^{2}F}{\partial x\,\partial y}}=f}$)^[2].

Пусть ${\displaystyle D\subset \mathbb {R} ^{2}}$ — обобщённая прямоугольная область, то есть объединение конечного числа прямоугольников со сторонами, параллельными осям координат. Её граница ${\displaystyle \partial D}$ состоит из горизонтальных и вертикальных отрезков и может состоять из нескольких контуров (например, при наличии «дырок»). Обозначим через ${\displaystyle V(D)}$ множество углов (вершин) границы области ${\displaystyle D}$. Каждому углу ${\displaystyle {\vec {x}}\in V(D)}$ приписывается целый коэффициент ${\displaystyle \alpha _{D}({\vec {x}})\in \{0,\pm 1,\pm 2\}}$, определяемый по типу угла: в точке ${\displaystyle {\vec {x}}}$ координатные прямые делят плоскость на четыре четверти, и ${\displaystyle \alpha _{D}({\vec {x}})}$ равен сумме знаков ${\displaystyle +1}$ (для четвертей северо-востока и юго-запада) и ${\displaystyle -1}$ (для юго-востока и северо-запада), взятых по тем четвертям, которые вблизи ${\displaystyle {\vec {x}}}$ покрываются областью ${\displaystyle D}$ (формально — через односторонние пределы индикаторной функции области)^[1][2]. Тогда дискретная теорема Грина утверждает:

${\displaystyle \iint _{D}f(x,y)\,dx\,dy=\sum _{{\vec {x}}\,\in \,V(D)}\alpha _{D}({\vec {x}})\,F({\vec {x}}).}$

Для одного прямоугольника ${\displaystyle [x_{1},x_{2}]\times [y_{1},y_{2}]}$ теорема обращается в стандартное тождество алгоритма интегрированной картинки:

${\displaystyle \iint _{D}f=F(x_{2},y_{2})-F(x_{1},y_{2})-F(x_{2},y_{1})+F(x_{1},y_{1}).}$

Для любой точки ${\displaystyle {\vec {x}}}$ определим четыре четверти ${\displaystyle Q_{NE}({\vec {x}}),Q_{NW}({\vec {x}}),Q_{SE}({\vec {x}}),Q_{SW}({\vec {x}})}$. Индикаторная функция прямоугольника ${\displaystyle R=[x_{1},x_{2}]\times [y_{1},y_{2}]}$ почти всюду представима как линейная комбинация индикаторов четвертей:

${\displaystyle \mathbf {1} _{R}(x,y)=\mathbf {1} _{Q_{SW}(x_{2},y_{2})}-\mathbf {1} _{Q_{SW}(x_{1},y_{2})}-\mathbf {1} _{Q_{SW}(x_{2},y_{1})}+\mathbf {1} _{Q_{SW}(x_{1},y_{1})}.}$

Интегрируя это тождество с весом ${\displaystyle f(x,y)}$ и используя определение ${\displaystyle F}$, получаем стандартную формулу для прямоугольника со знаками ${\displaystyle +1,-1,-1,+1}$. Для объединения прямоугольников формула следует из аддитивности интеграла и взаимного сокращения слагаемых на общих внутренних границах.

Строгое доказательство опирается на тот факт, что индикаторная функция ${\displaystyle \mathbf {1} _{D}}$ почти всюду совпадает с линейной комбинацией индикаторов четвертей с вершинами в углах ${\displaystyle D}$ и коэффициентами ${\displaystyle \alpha _{D}({\vec {x}})}$. Умножая это равенство на ${\displaystyle f}$ и интегрируя по теореме Фубини, получаем искомое тождество. Абстрактно это можно рассматривать как формулу обращения Мёбиуса на булевой алгебре прямоугольников или как дискретный аналог меры на границе.

На практике алгоритм реализуется в два этапа:

1. Подготовка (Preprocessing): таблица первообразных ${\displaystyle F(x,y)}$ для дискретной сетки вычисляется за ${\displaystyle O(W\cdot H)}$ операций с помощью двумерного префиксного суммирования (операция scan).
2. Запрос (Query): интеграл по произвольной обобщённой прямоугольной области вычисляется за время ${\displaystyle O(|V(D)|)}$ — число операций сложения и вычитания пропорционально количеству углов области.

Коэффициент ${\displaystyle \alpha _{D}({\vec {x}})}$ для каждой вершины определяется локально: достаточно проанализировать конфигурацию области в окрестности ${\displaystyle 2\times 2}$ вокруг точки ${\displaystyle {\vec {x}}}$. Существует 16 возможных конфигураций заполнения пикселей, которые однозначно маппятся на множество коэффициентов ${\displaystyle \{0,\pm 1,\pm 2\}}$.

В ${\displaystyle d}$-мерном пространстве интеграл по прямоугольному параллелепипеду аналогично выражается через ${\displaystyle 2^{d}}$ значений многомерной первообразной в его вершинах со знаками ${\displaystyle \pm 1}$. В компьютерном зрении это приводит к концепции интегрального видео (англ. integral video) или пространственно-временных интегральных изображений. Они позволяют за константное время ${\displaystyle O(1)}$ вычислять интегралы по произвольным трёхмерным кубоидам в видеопотоке, что критически важно для детекции событий и извлечения объёмных признаков (например, 3D-HOG)^[20].

• Компьютерное зрение. Основная область применения: вычисление интегралов по областям переменной формы за ${\displaystyle O(1)}$. Используется для обнаружения объектов, расширения Хаар-подобных признаков с прямоугольников на многоугольники^[18], распознавания людей по внешности в сетях камер^[3], моделирования контекста формы^[1].
• Интегральные гистограммы. Метод, предложенный Фатихом Порикли (2005), позволяет извлекать гистограммы градиентов или цветов по произвольным прямоугольным окнам за константное время, предварительно накопив префиксные суммы для каждого бина гистограммы^[21].
• Вычисление моментов изображения. Интегрирование функций вида ${\displaystyle x^{i}y^{j}f(x,y)}$ позволяет быстро находить локальные статистики (среднее, дисперсию, моменты высших порядков) и центроиды сложных областей без построения сетки.
• Промышленная обработка изображений. Применяется в задачах быстрого анализа форм, например, при автоматической детекции и классификации брёвен на лесопилках^[22].