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

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

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

Алгоритм

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

${\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) це просто^[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}$, при використанні вокселів або вокселів із часовою міткою.

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

Інтегральне зображення (права половина) 2-бітного піксельного малюнку у градаціях сірого (ліва половина), нормалізоване та збільшене для видимості.

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

${\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)}$) для отримання коефіцієнтів асиметрії та ексцесу.^[7] Але одна важлива деталь втілення, яку слід мати на увазі для вищевказаних методів, як зазначили Ф. Шафаіт зі співавт.,^[8] полягає в переповненні цілих чисел, що виникає для інтегральних зображень вищого порядку у випадку використання 32-розрядних цілих чисел.

Див. також

• Префіксна сума^[en]