Immagine integrale

Immagine integrale (metà destra) di un'immagine pixel art in scala di grigi a 2 bit (metà sinistra), normalizzata e ingrandita per renderla visibile.

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.

Descrizione

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

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

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

${\displaystyle 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 ${\displaystyle (x_{0},y_{0})}$ e ${\displaystyle (x_{1},y_{1})}$, usando solo quattro accessi in memoria e tre operazioni, indipendentemente dalla dimensione della regione:

${\displaystyle \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 ${\displaystyle d}$ dimensioni, con vertici in ${\displaystyle x_{p},\;p\in \{0,1\}^{d}}$, la somma dell'intensità nel rettangolo è data da

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

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

la varianza è data da

${\displaystyle {\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 ${\displaystyle S_{1}}$ e ${\displaystyle S_{2}}$ sono le rispettive somme dei rettangoli in ${\displaystyle I}$ e ${\displaystyle I^{2}}$, ${\displaystyle \mu ={\frac {S_{1}}{n}}}$ e ${\displaystyle 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.

Note

Portale Informatica

Portale Matematica

Portale Statistica