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.

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.[1] 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)}$[2][3]

${\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[4]

${\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[1] e a immagini multi-dimensionali.[5] 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})}$.[6]

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

Note

1. Amir Finkelstein e neeratsharma, Double Integrals By Summing Values Of Cumulative Distribution Function, in Wolfram Demonstration Project, 2010.
2. Franklin Crow, Summed-area tables for texture mapping (PDF), in SIGGRAPH '84: Proceedings of the 11th annual conference on Computer graphics and interactive techniques, 1984, pp. 207–212. URL consultato il 3 novembre 2019 (archiviato dall'url originale il 4 giugno 2011).
3. Paul Viola e Jones, Michael, Robust Real-time Object Detection (PDF), in International Journal of Computer Vision, 2002.
4. BADGERATI, Computer Vision – The Integral Image, su computersciencesource.wordpress.com, 3 settembre 2010. URL consultato il 13 febbraio 2017.
5. Ernesto Tapia, A note on the computation of high-dimensional integral images, in Pattern Recognition Letters, vol. 32, n. 2, gennaio 2011, pp. 197–201, DOI:10.1016/j.patrec.2010.10.007.
6. Thien Phan, Sohum Sohoni, Eric C. Larson e Damon M. Chandler, Performance-analysis-based acceleration of image quality assessment (PDF), in 2012 IEEE Southwest Symposium on Image Analysis and Interpretation, 22 aprile 2012, pp. 81–84, DOI:10.1109/SSIAI.2012.6202458, ISBN 978-1-4673-1830-3. URL consultato il 3 novembre 2019 (archiviato dall'url originale il 24 maggio 2014).
7. Faisal Shafait, Daniel Keysers e Thomas M. Breuel, Efficient implementation of local adaptive thresholding techniques using integral images (PDF), in Electronic Imaging, Document Recognition and Retrieval XV, vol. 6815, gennaio 2008, pp. 681510–681510–6, DOI:10.1117/12.767755. URL consultato il 3 novembre 2019 (archiviato dall'url originale il 15 dicembre 2014).