Интегральное представление изображения

Интегральное представление изображения (также известное как суммированная таблица площадей, summed-area table) — это структура данных, используемая в компьютерном зрении и обработке изображений, которая позволяет за константное время (O(1)) вычислять сумму значений пикселей в любой прямоугольной области изображения, независимо от её размера. Представляет собой матрицу, каждый элемент которой содержит сумму всех пикселей исходного изображения, расположенных выше и левее данного элемента (включительно).

История

Метод интегрального представления был впервые описан Франклином Кроу в 1984 году в контексте компьютерной графики для ускорения вычислений при текстурировании и освещении (алгоритм mip-карт). Однако широкую известность техника получила после 2001 года, когда Пол Виола и Майкл Джонс использовали её в своём знаменитом алгоритме детектирования объектов (каскадный классификатор Виолы — Джонса). Именно этот алгоритм лёг в основу первых систем реального времени для распознавания лиц, встроенных в цифровые камеры и программное обеспечение начала 2000-х годов.

Принцип работы

Построение интегрального изображения

Пусть исходное изображение представлено в виде матрицы I размером M × N, где I(x, y) — яркость пикселя в строке y и столбце x (координаты обычно отсчитываются от верхнего левого угла, начиная с 1).

Интегральное изображение S (summed-area table) строится по следующему рекуррентному правилу:

S(x, y) = I(x, y) + S(x-1, y) + S(x, y-1) - S(x-1, y-1)

где S(0, y) = 0 и S(x, 0) = 0 для всех значений.

Иными словами, значение в точке (x, y) равно сумме всех пикселей прямоугольника, верхний левый угол которого совпадает с верхним левым углом изображения, а нижний правый — с точкой (x, y).

Вычисление суммы в произвольном прямоугольнике

Для того чтобы получить сумму пикселей в прямоугольнике с вершинами (x1, y1) (верхний левый угол) и (x2, y2) (нижний правый угол), достаточно выполнить всего 4 операции обращения к интегральному изображению:

Sum = S(x2, y2) - S(x1-1, y2) - S(x2, y1-1) + S(x1-1, y1-1)

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

Алгоритм построения

Существует два основных подхода к построению интегрального изображения:

1. Прямой проход (двухпроходный): Сначала вычисляется сумма по строкам (кумулятивная сумма по горизонтали), затем по столбцам (кумулятивная сумма по вертикали). Этот метод требует двух проходов по изображению, но легко векторизуется.
2. Рекурсивный проход (однопроходный): Используется приведённая выше рекуррентная формула. Каждый элемент вычисляется на основе трёх уже вычисленных соседей. Этот метод требует одного прохода, но сложнее для параллельной обработки.

Варианты и расширения

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

Для вычисления дисперсии или стандартного отклонения в прямоугольной области используется интегральное представление квадратов значений пикселей:

S2(x, y) = I(x, y)^2 + S2(x-1, y) + S2(x, y-1) - S2(x-1, y-1)

Интегральное представление для повёрнутых прямоугольников

Для детектирования объектов под углом 45° (например, в детекторах лиц) используется интегральное представление для повёрнутых на 45° прямоугольников (rotated summed-area table). В этом случае суммируются пиксели, лежащие в ромбовидной области.

Интегральное представление для многоканальных изображений

Для цветных изображений (RGB) интегральное представление строится отдельно для каждого канала. Для изображений с глубиной (например, с датчика Kinect) интегральное представление может хранить сумму значений глубины.

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

В некоторых алгоритмах (например, в методе SURF) используется интегральное представление, адаптированное для быстрого вычисления откликов вейвлетов Хаара.

Применение

Обнаружение объектов (алгоритм Виолы — Джонса)

Наиболее известное применение. Каскадный классификатор использует интегральное представление для быстрого вычисления признаков Хаара — прямоугольных шаблонов, разность сумм пикселей в которых позволяет выделить характерные черты объекта (например, область глаз и переносицы на лице). Благодаря O(1)-вычислению, классификатор может за доли секунды просканировать всё изображение в разных масштабах.

Стереозрение и оптический поток

При вычислении стоимости сопоставления блоков (block matching) в стереопарах или при оценке оптического потока используется сумма квадратов разностей (SSD) или сумма абсолютных разностей (SAD). Интегральное представление позволяет ускорить эти вычисления, особенно при использовании больших окон поиска.

Вычисление локальных статистик

Интегральное представление широко используется для вычисления:

• Среднего значения яркости в окне.
• Дисперсии (через интегральное представление квадратов).
• Локального контраста.
• Медианы (с помощью гистограммного подхода, где интегральное представление строится для каждого бина гистограммы).

Фильтрация изображений

• Бокс-фильтр (Box filter): Фильтр усреднения, который заменяет каждый пиксель средним значением в окне. С помощью интегрального представления такой фильтр работает за константное время, независимо от размера ядра.
• Фильтр Гаусса: Хотя сам фильтр Гаусса не является прямоугольным, его можно аппроксимировать несколькими проходами бокс-фильтра (согласно центральной предельной теореме). Интегральное представление позволяет делать это быстро.
• Адаптивная бинаризация: Методы, такие как алгоритм Брэдли, используют интегральное представление для вычисления порога для каждого пикселя на основе средней яркости в его окрестности.

Компьютерная графика

• Mip-карты: Интегральное представление лежит в основе построения пирамид изображений (mip-карт), используемых для текстурирования с LOD (уровнем детализации).
• Суммированные таблицы площадей: Используются для быстрого вычисления освещения от площадных источников света (area lights) в алгоритмах рендеринга.

Преимущества и недостатки

Преимущества

• Высокая скорость: Вычисление суммы любого прямоугольника за O(1).
• Простота реализации: Алгоритм построения и использования тривиален.
• Масштабируемость: Эффективность растёт с увеличением размера изображения и размера окна.
• Параллелизуемость: Построение интегрального изображения может быть распараллелено (например, с помощью префиксной суммы на GPU).

Недостатки

• Требования к памяти: Интегральное изображение имеет тот же размер, что и исходное, но каждый элемент требует большего разряда (например, 32-битное целое или 64-битное число с плавающей точкой) для хранения больших сумм. Для цветных изображений требуется в 3-4 раза больше памяти.
• Переполнение: При работе с большими изображениями и высокими значениями яркости (например, 16-битные изображения) сумма может превысить диапазон 32-битного целого числа. Требуется использование 64-битных типов данных или плавающей точки.
• Ограниченная форма: Позволяет быстро вычислять только прямоугольные области. Для произвольных форм (круги, многоугольники) требуются другие методы.

Интересные факты

• Алгоритм Виолы — Джонса, основанный на интегральном представлении, стал первым методом, позволившим детектировать лица в реальном времени на обычных процессорах начала 2000-х (с частотой около 700 МГц).
• Интегральное представление является частным случаем многомерной префиксной суммы (prefix sum), которая широко используется в параллельных вычислениях на GPU.
• В библиотеке OpenCV существует функция cv::integral(), которая позволяет построить интегральное представление для одноканального изображения, а также для квадратов и повёрнутых прямоугольников.

Источники

• Crow, F. C. (1984). "Summed-area tables for texture mapping". ACM SIGGRAPH Computer Graphics, 18(3), 207-212.
• Viola, P., & Jones, M. (2001). "Rapid object detection using a boosted cascade of simple features". Proceedings of the 2001 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR).
• Bay, H., Ess, A., Tuytelaars, T., & Van Gool, L. (2008). "Speeded-Up Robust Features (SURF)". Computer Vision and Image Understanding, 110(3), 346-359.
• Bradley, D., & Roth, G. (2007). "Adaptive Thresholding using the Integral Image". Journal of Graphics Tools, 12(2), 13-21.
• OpenCV documentation: cv::integral().