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

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

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

Алгоритм [ править ]

Как следует из названия, значение в любой точке ( x ,  y ) в таблице суммированной площади представляет собой сумму всех пикселей выше и слева от ( x ,  y ) включительно: ^{[3] [4]}

${\displaystyle I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')}$

где - значение пикселя в точке (x, y). ${\displaystyle i(x,y)}$

Таблица суммированных площадей может быть эффективно вычислена за один проход по изображению, поскольку значение в таблице суммированных площадей в ( x ,  y ) просто: ^[5]

${\displaystyle 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 ₁₎ ) сумма i (x, y) по прямоугольнику, натянутому на A, B, C и D, равна:

${\displaystyle \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)}$

Расширения [ править ]

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

Этот метод также можно распространить на изображения большой размерности. ^[6] Если углы прямоугольника с в , то сумма значений изображения , содержащиеся в прямоугольнике вычисляются по формуле${\displaystyle x^{p}}$${\displaystyle p}$${\displaystyle \{0,1\}^{d}}$

${\displaystyle \sum _{p\in \{0,1\}^{d}}(-1)^{d-\|p\|_{1}}I(x^{p})\,}$

где - интегральное изображение при и размер изображения. Обозначения соответствуют в примере с , , , и . В нейровизуализации , например, изображения имеют размер или , при использовании вокселей или вокселей с отметкой времени.${\displaystyle I(x)}$${\displaystyle x}$${\displaystyle d}$${\displaystyle x^{p}}$${\displaystyle d=2}$${\displaystyle A=x^{(0,0)}}$${\displaystyle B=x^{(1,0)}}$${\displaystyle C=x^{(1,1)}}$${\displaystyle D=x^{(0,1)}}$${\displaystyle d=3}$${\displaystyle d=4}$

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

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

${\displaystyle I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')}$

${\displaystyle I^{2}(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i^{2}(x',y')}$

Разница определяется по формуле:

${\displaystyle \operatorname {Var} (X)={\frac {1}{n}}\sum _{i=1}^{n}(x_{i}-\mu )^{2}.}$

Пусть и обозначают сложения блока в и , соответственно. и быстро вычисляются по интегральному изображению. Теперь мы манипулируем уравнением дисперсии следующим образом:${\displaystyle S_{1}}$${\displaystyle S_{2}}$${\displaystyle ABCD}$${\displaystyle I}$${\displaystyle I^{2}}$${\displaystyle S_{1}}$${\displaystyle S_{2}}$

${\displaystyle \operatorname {Var} (X)={\frac {1}{n}}\sum _{i=1}^{n}(x_{i}^{2}-2\cdot \mu \cdot x_{i}+\mu ^{2})={\frac {1}{n}}(\sum _{i=1}^{n}(x_{i})^{2}-2\cdot \sum _{i=1}^{n}(\mu \cdot x_{i})+\sum _{i=1}^{n}(\mu ^{2}))={\frac {1}{n}}(\sum _{i=1}^{n}(x_{i})^{2}-2\cdot \sum _{i=1}^{n}(\mu \cdot x_{i})+n\cdot (\mu ^{2}))}$

${\displaystyle ={\frac {1}{n}}(\sum _{i=1}^{n}(x_{i})^{2}-2\cdot \mu \cdot \sum _{i=1}^{n}(x_{i})+n\cdot (\mu ^{2}))={\frac {1}{n}}(S_{2}-2\cdot S_{1}/n\cdot S_{1}+n\cdot ((S_{1}/n)^{2}))={\frac {1}{n}}(S_{2}-(S_{1})^{2}/n)}$

Где и .${\displaystyle \mu =S_{1}/n}$${\displaystyle S_{2}=\sum _{i=1}^{n}(x_{i}^{2})}$

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

Ссылки [ править ]

Внешние ссылки [ править ]

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

Видео лекций

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