Таблица суммированных площадей

Использование таблицы суммированных площадей ( 2. 6-го порядка ) магического квадрата ( 1. ) для суммирования подпрямоугольника его значений; каждое цветное пятно выделяет сумму внутри прямоугольника этого цвета.

Таблица суммированных площадей — это структура данных и алгоритм для быстрого и эффективного создания суммы значений в прямоугольном подмножестве сетки. В области обработки изображений оно также известно как целостное изображение . Он был представлен в компьютерной графике в 1984 году Фрэнком Кроу для использования с MIP-картами . В компьютерном зрении его популяризировал Льюис. а затем получил название «интегральное изображение» и широко использовался в рамках системы обнаружения объектов Виолы-Джонса в 2001 году. Исторически этот принцип очень хорошо известен при изучении многомерных функций распределения вероятностей, а именно при вычислениях 2D (или ND). вероятности (площадь под распределением вероятностей) из соответствующих кумулятивных функций распределения .

Алгоритм

Как следует из названия, значение в любой точке ( x , y ) в таблице суммированных площадей представляет собой сумму всех пикселей выше и слева от ( x , y ), включительно: $$I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')$$где $i(x,y)$ — значение пикселя в точке ( x , y ).

Таблицу суммированной площади можно эффективно вычислить за один проход по изображению, поскольку значение в таблице суммированной площади в ( x , y ) просто: $$I(x,y)=i(x,y)+I(x,y-1)+I(x-1,y)-I(x-1,y-1)$$ (Обратите внимание, что суммированная матрица рассчитывается из верхнего левого угла)

Описание вычисления суммы в структуре/алгоритме данных таблицы суммируемых площадей.

После вычисления таблицы суммированных площадей для оценки суммы интенсивностей по любой прямоугольной области требуется ровно четыре обращения к массиву независимо от размера области. То есть обозначения на рисунке справа, где A = ( x ₀ , y ₀ ) , B = ( x ₁ , y ₀ ) , C = ( x ₀ , y ₁ ) и D = ( x ₁ , y _{1 )} ) , сумма i ( x , y ) по прямоугольнику, охватываемому A , B , C и D , равна: $$\sum _{\begin{smallmatrix}x_{0}<x\leq x_{1}\\y_{0}<y\leq y_{1}\end{smallmatrix}}i(x,y)=I(D)+I(A)-I(B)-I(C)$$

Расширения

Этот метод естественным образом распространяется на непрерывные области.

Этот метод также можно распространить на изображения большой размерности. Если углы прямоугольника $x^{p}$ с $p$ в $\{0,1\}^{d}$, то сумма значений изображений, содержащихся в прямоугольнике, вычисляется по формуле $$\sum _{p\in \{0,1\}^{d}}(-1)^{d-\|p\|_{1}}I(x^{p})$$где $I(x)$ является целостным изображением на $x$ и $d$ размерность изображения. Обозначения $x^{p}$ соответствуют в примере $d=2$, $A=x^{(0,0)}$, $B=x^{(1,0)}$, $C=x^{(1,1)}$ и $D=x^{(0,1)}$. при нейровизуализации изображения имеют размерность. Например, $d=3$ или $d=4$, при использовании вокселей или вокселей с отметкой времени.

Этот метод был распространен на интегральное изображение высокого порядка, как в работе Phan et al. который предоставил два, три или четыре интегральных изображения для быстрого и эффективного расчета стандартного отклонения (дисперсии), асимметрии и эксцесса локального блока изображения. Подробно это описано ниже:

Чтобы вычислить дисперсию или стандартное отклонение блока, нам нужны два целых изображения: $$I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')$$$$I^{2}(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i^{2}(x',y')$$Отклонение определяется: $$\operatorname {Var} (X)={\frac {1}{n}}\sum _{i=1}^{n}(x_{i}-\mu )^{2}.$$Позволять $S_{1}$ и $S_{2}$ обозначим суммы блока $ABCD$ из $I$ и $I^{2}$, соответственно. $S_{1}$ и $S_{2}$ быстро вычисляются по интегральному изображению. Теперь мы манипулируем уравнением дисперсии следующим образом: $${\begin{aligned}\operatorname {Var} (X)&={\frac {1}{n}}\sum _{i=1}^{n}\left(x_{i}^{2}-2\mu x_{i}+\mu ^{2}\right)\\[1ex]&={\frac {1}{n}}\left[\sum _{i=1}^{n}x_{i}^{2}-2\sum _{i=1}^{n}\mu x_{i}+\sum _{i=1}^{n}\mu ^{2}\right]\\[1ex]&={\frac {1}{n}}\left[\sum _{i=1}^{n}x_{i}^{2}-2\sum _{i=1}^{n}\mu x_{i}+n\mu ^{2}\right]\\[1ex]&={\frac {1}{n}}\left[\sum _{i=1}^{n}x_{i}^{2}-2\mu \sum _{i=1}^{n}x_{i}+n\mu ^{2}\right]\\[1ex]&={\frac {1}{n}}\left[S_{2}-2{\frac {S_{1}}{n}}S_{1}+n\left({\frac {S_{1}}{n}}\right)^{2}\right]\\[1ex]&={\frac {1}{n}}\left[S_{2}-{\frac {S_{1}^{2}}{n}}\right]\end{aligned}}$$Где $\mu =S_{1}/n$ и ${\textstyle S_{2}=\sum _{i=1}^{n}x_{i}^{2}}$.

Аналогично оценке среднего ( $\mu$) и дисперсия ( $\operatorname {Var}$), для чего требуются целые изображения первой и второй степени изображения соответственно (т.е. $I,I^{2}$); манипуляции, подобные упомянутым выше, можно производить с третьей и четвертой степенями изображений (т.е. $I^{3}(x,y),I^{4}(x,y)$.) для получения асимметрии и эксцесса. Но одна важная деталь реализации, которую следует учитывать для вышеупомянутых методов, как упоминалось F. Shafait et al. Это переполнение целых чисел, возникающее для целочисленных изображений более высокого порядка в случае использования 32-битных целых чисел.

Рекомендации по реализации

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

См. также

• Префиксная сумма

Внешние ссылки

• Реализация таблицы суммирования при обнаружении объектов

Видео лекций

• Введение в теорию алгоритма интегрального изображения
• Демонстрация непрерывной версии алгоритма интегрального изображения из демонстрационного проекта Wolfram.