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

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

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

Алгоритм

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

${displaystyle I(x,y)=sum _{egin{smallmatrix}x'leq xy'leq yend{smallmatrix}}i(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 _{egin{smallmatrix}x_{0}<xleq x_{1}y_{0}<yleq 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 _{pin {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 _{egin{smallmatrix}x'leq xy'leq yend{smallmatrix}}i(x',y')}$

${displaystyle I^{2}(x,y)=sum _{egin{smallmatrix}x'leq xy'leq yend{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}-2cdot mu cdot x_{i}+mu ^{2})={frac {1}{n}}(sum _{i=1}^{n}(x_{i})^{2}-2cdot sum _{i=1}^{n}(mu cdot x_{i})+sum _{i=1}^{n}(mu ^{2}))={frac {1}{n}}(sum _{i=1}^{n}(x_{i})^{2}-2cdot sum _{i=1}^{n}(mu cdot x_{i})+ncdot (mu ^{2}))}$

${displaystyle ={frac {1}{n}}(sum _{i=1}^{n}(x_{i})^{2}-2cdot mu cdot sum _{i=1}^{n}(x_{i})+ncdot (mu ^{2}))={frac {1}{n}}(S_{2}-2cdot S_{1}/ncdot S_{1}+ncdot ((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})}$.

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

Рекомендации

1. Льюис, Дж. П. (1995). Быстрое сопоставление шаблонов. Proc. Видение Интерфейс. С. 120–123.
2. Финкельштейн, Амир; neeratsharma (2010). «Двойные интегралы путем суммирования значений кумулятивной функции распределения». Демонстрационный проект Вольфрама.
3. Ворона, Франклин (1984). «Таблицы суммированных площадей для наложения текстуры» (PDF). SIGGRAPH '84: Материалы 11-й ежегодной конференции по компьютерной графике и интерактивным методам. С. 207–212.
4. Виола, Поль; Джонс, Майкл (2002). «Надежное обнаружение объектов в реальном времени» (PDF). Международный журнал компьютерного зрения.
5. БАДГЕРАТИ (03.09.2010). «Компьютерное зрение - целостное изображение». компьютерыciencesource.wordpress.com. Получено 2017-02-13.
6. Тапиа, Эрнесто (январь 2011 г.). «Заметка о вычислении многомерных интегральных изображений». Письма с распознаванием образов. 32 (2): 197–201. Дои:10.1016 / j.patrec.2010.10.007.
7. Фан, Тхиен; Сохони, Сохум; Ларсон, Эрик С .; Чендлер, Дэймон М. (22 апреля 2012 г.). Ускорение оценки качества изображения на основе анализа производительности (PDF). Юго-западный симпозиум IEEE 2012 г. по анализу и интерпретации изображений. С. 81–84. CiteSeerX  10.1.1.666.4791. Дои:10.1109 / SSIAI.2012.6202458. ISBN  978-1-4673-1830-3.
8. Шафаит, Фейсал; Кейзерс, Дэниел; М. Бреуэль, Томас (январь 2008 г.). «Эффективная реализация методов локальной адаптивной пороговой обработки с использованием интегральных изображений» (PDF). Электронное изображение. Распознавание и поиск документов XV. 6815: 681510–681510–6. CiteSeerX  10.1.1.109.2748. Дои:10.1117/12.767755.

внешняя ссылка

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

Видео лекций

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