Таблиця сумарних площ

Табли́ця сума́рних пло́щ (англ. summed-area table) — це структура даних та алгоритм для швидкого й ефективного породжування суми значень у прямокутній підмножині ґратки. В галузі обробки зображень вона також відома як інтегра́льне зобра́ження (англ. integral image). Її було запроваджено в комп'ютерній графіці 1984 року ^[en] для використання з MIP-текстуруванням. У комп'ютернім баченні її популяризував Льюїс, а потім вона отримала назву «інтегрального зображення» та широке використання в системі Віоли — Джонса виявляння об'єктів 2001 року. Історично цей принцип дуже добре відомий у дослідженні багатовимірних функцій розподілу ймовірності, а саме в обчисленні двовимірних (або N-вимірних) імовірностей (площ під розподілом імовірності) з відповідних кумулятивних функцій розподілу.

Використання таблиці сумарних площ (2.) магічного квадрата шостого порядку (1.) для підсумовування підпрямокутника його значень; кожна кольорова пляма висвітлює суму всередині прямокутника її кольору.

Алгоритм

Як підказує назва, значення в будь-якій точці (x, y) таблиці сумарних площ — це сума всіх пікселів вище та ліворуч від (x, y), включно:

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

де ${\displaystyle i(x,y)}$ це значення пікселя в (x, y).

Таблицю сумарних площ можливо ефективно обчислювати за один прохід зображенням, оскільки значення в ній в (x, y) це просто

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

Розширення

Цей метод природно розширюється на неперервні області.

Цей метод також можливо розширити на зображення високої вимірності. Якщо кути прямокутника — ${\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}$, при використанні вокселів або вокселів із часовою міткою.

Цей метод було розширено до інтегрального зображення високого порядку, як у праці Фана зі співавт., які запропонували два, три або чотири інтегральні зображення для швидкого та ефективного обчислювання стандартного відхилення (дисперсії), коефіцієнту асиметрії та коефіцієнта ексцесу локального блоку зображення. Це описано докладно нижче:

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

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

Подібно до оцінювання середнього значення (${\displaystyle \mu }$) та дисперсії (${\displaystyle Var}$), для яких потрібні інтегральні зображення першого та другого степеня зображення відповідно (тобто ${\displaystyle I,I^{2}}$), маніпуляції, подібні до згаданих вище, можливо виконати з третім і четвертим степенями зображень (тобто ${\displaystyle I^{3}(x,y),I^{4}(x,y)}$) для отримання коефіцієнтів асиметрії та ексцесу. Але одна важлива деталь втілення, яку слід мати на увазі для вищевказаних методів, як зазначили Ф. Шафаіт зі співавт., полягає в переповненні цілих чисел, що виникає для інтегральних зображень вищого порядку у випадку використання 32-розрядних цілих чисел.

Див. також

• ^[en]

Примітки

1. Lewis, J.P. (1995). Fast template matching. Proc. Vision Interface. с. 120—123. (англ.)
2. Finkelstein, Amir; neeratsharma (2010). Double Integrals By Summing Values Of Cumulative Distribution Function. Wolfram Demonstration Project. (англ.)
3. Crow, Franklin (1984). Summed-area tables for texture mapping. SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques. с. 207—212. (англ.)
4. Viola, Paul; Jones, Michael (2002). Robust Real-time Object Detection (PDF). International Journal of Computer Vision. (англ.)
5. BADGERATI (3 вересня 2010). Computer Vision – The Integral Image. computersciencesource.wordpress.com. Процитовано 13 лютого 2017. (англ.)
6. Tapia, Ernesto (January 2011). A note on the computation of high-dimensional integral images. Pattern Recognition Letters. 32 (2): 197—201. doi:10.1016/j.patrec.2010.10.007. (англ.)
7. Phan, Thien; Sohoni, Sohum; Larson, Eric C.; Chandler, Damon M. (22 квітня 2012). (PDF). с. 81—84. CiteSeerX 10.1.1.666.4791. doi:10.1109/SSIAI.2012.6202458. ISBN . Архів оригіналу (PDF) за 24 травня 2014. Процитовано 1 січня 2023. {{}}: Проігноровано |journal= () (англ.)
8. Shafait, Faisal; Keysers, Daniel; M. Breuel, Thomas (January 2008). (PDF). Electronic Imaging. Document Recognition and Retrieval XV. 6815: 681510–681510–6. CiteSeerX 10.1.1.109.2748. doi:10.1117/12.767755. Архів оригіналу (PDF) за 15 грудня 2014. Процитовано 1 січня 2023. (англ.)

Посилання

• Втілення сумарної таблиці у виявлянні об'єктів

Відео лекцій

• Вступ до теорії алгоритму інтегрального зображення (англ.)
• Демонстрація безперервної версії алгоритму інтегрального зображення від Wolfram Demonstrations Project (англ.)