Immagine integrale

Un'immagine integrale è una struttura dati per il calcolo rapido della somma dei valori in un sottoinsieme rettangolare di una griglia. Storicamente, il concetto era noto nel calcolo delle distribuzioni di probabilità multidimensionali a partire dalla funzione di ripartizione. L'idea è stata introdotta in computer grafica nel 1984 da Frank Crow con applicazioni legate alle mipmap, ed ha assunto il nome di immagine integrale e ottenuto ampia diffusione in visione artificiale a seguito dell'uso nell'algoritmo di Viola-Jones nel 2001.

Esempio di immagine integrale (2.) calcolata a partire dall'immagine in input (1.). Ogni pixel colorato nell'immagine integrale contiene la somma dell'intensità nel rettangolo di colore corrispondente nell'immagine di partenza.

Descrizione

Il valore dell'immagine integrale in un punto $(x,y)$ è dato dalla somma di tutti i punti nel rettangolo che va dall'origine fino a $(x,y)$

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

dove $i(x,y)$ è l'intensità dell'immagine di partenza in $(x,y)$. L'immagine integrale può essere calcolata efficacemente in un singolo passo, poiché il valore può essere riscritto come

$I(x,y)=i(x,y)+I(x,y-1)+I(x-1,y)-I(x-1,y-1)$

Usando l'immagine integrale è possibile calcolare la somma dell'intensità in una regione rettangolare allineata con gli assi coordinati, con vertici in $(x_{0},y_{0})$ e $(x_{1},y_{1})$, usando solo quattro accessi in memoria e tre operazioni, indipendentemente dalla dimensione della regione:

$\sum _{\begin{smallmatrix}x_{0}<x\leq x_{1}\\y_{0}<y\leq y_{1}\end{smallmatrix}}i(x,y)=I(x_{1},y_{1})+I(x_{0},y_{0})-I(x_{1},y_{0})-I(x_{0},y_{1})$

Estensioni

Il metodo può essere naturalmente esteso a domini continui e a immagini multi-dimensionali. Dato un iper-rettangolo in $d$ dimensioni, con vertici in $x_{p},\;p\in \{0,1\}^{d}$, la somma dell'intensità nel rettangolo è data da

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

Il metodo può anche essere esteso per calcolare la varianza. Date due immagini integrali definite come

$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')$

la varianza è data da

${\begin{aligned}\operatorname {Var} (X)&={\frac {1}{n}}\sum _{i=1}^{n}(x_{i}-\mu )^{2}\\&=\operatorname {Var} (X)={\frac {1}{n}}\sum _{i=1}^{n}(x_{i}^{2}-2\mu x_{i}+\mu ^{2})\\&={\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)\\&={\frac {1}{n}}\left(\sum _{i=1}^{n}x_{i}^{2}-2\sum _{i=1}^{n}\mu x_{i}+n\mu ^{2}\right)\\&={\frac {1}{n}}\left(\sum _{i=1}^{n}x_{i}^{2}-2\mu \sum _{i=1}^{n}x_{i}+n\mu ^{2}\right)\\&={\frac {1}{n}}\left(S_{2}-2{\frac {S_{1}}{n}}S_{1}+n\left({\frac {S_{1}}{n}}\right)^{2}\right)\\&={\frac {1}{n}}\left(S_{2}-{\frac {S_{1}^{2}}{n}}\right)\end{aligned}}$

dove $S_{1}$ e $S_{2}$ sono le rispettive somme dei rettangoli in $I$ e $I^{2}$, $\mu ={\frac {S_{1}}{n}}$ e $S_{2}=\sum _{i=1}^{n}(x_{i}^{2})$.

Similarmente, immagini integrali di terzo e quarto grado possono essere usate per calcolare momenti di ordine superiore, come indice di simmetria e curtosi. Una delle principali limitazioni all'aumentare del grado è costituita dall'overflow aritmetico.