Immagine integrale

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.

UnTemplate:'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 $(x,y)$ è dato dalla somma di tutti i punti nel rettangolo che va dall'origine fino a $(x,y)$

$I(x,y)=\sum _{\begin{array}{c}{x}^{\prime }\le x\\ y^{\prime }\le y\end{array}}i(x^{\prime },y^{\prime })$

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{array}{c}{x}_0<x\le x_1\\ y_0<y\le y_1\end{array}}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-\Vert p{\Vert }_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{array}{c}{x}^{\prime }\le x\\ y^{\prime }\le y\end{array}}i(x^{\prime },y^{\prime })$

$I^2(x,y)=\sum _{\begin{array}{c}{x}^{\prime }\le x\\ y^{\prime }\le y\end{array}}{i}^2(x^{\prime },y^{\prime })$

la varianza è data da

$\begin{array}{cc}\mathrm{Var}(X)& =\frac{1}{n}\sum _{i=1}^n(x_i-\mu {)}^2\\ & =\mathrm{Var}(X)=\frac{1}{n}\sum _{i=1}^n(x_i^2-2\mu x_i+{\mu }^2)\\ & =\frac{1}{n}(\sum _{i=1}^n{x}_i^2-2\sum _{i=1}^n\mu x_i+\sum _{i=1}^n{\mu }^2)\\ & =\frac{1}{n}(\sum _{i=1}^n{x}_i^2-2\sum _{i=1}^n\mu x_i+n{\mu }^2)\\ & =\frac{1}{n}(\sum _{i=1}^n{x}_i^2-2\mu \sum _{i=1}^n{x}_i+n{\mu }^2)\\ & =\frac{1}{n}(S_2-2\frac{S_1}{n}{S}_1+n{\left(\frac{S_1}{n}\right)}^2)\\ & =\frac{1}{n}(S_2-\frac{S_1^2}{n})\end{array}$

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.