Tabla de áreas sumadas

Tipo de algoritmo de estructura de datos

Utilizando una tabla de áreas sumadas ( 2. ) de una matriz de 6×6 ( 1. ) para sumar un subrectángulo de sus valores; cada punto de color resalta la suma dentro del rectángulo de ese color.

Una tabla de área sumada es una estructura de datos y un algoritmo para generar de manera rápida y eficiente la suma de valores en un subconjunto rectangular de una cuadrícula. En el dominio del procesamiento de imágenes , también se la conoce como imagen integral . Fue introducida en gráficos por computadora en 1984 por Frank Crow para su uso con mapas MIP . En visión por computadora, fue popularizada por Lewis ^[1] y luego se le dio el nombre de "imagen integral" y se usó de manera destacada dentro del marco de detección de objetos de Viola-Jones en 2001. Históricamente, este principio es muy conocido en el estudio de funciones de distribución de probabilidad multidimensionales, es decir, en el cálculo de probabilidades 2D (o ND) (área bajo la distribución de probabilidad) a partir de las respectivas funciones de distribución acumulativa . ^[2]

El algoritmo

Como sugiere el nombre, el valor en cualquier punto ( x ,  y ) en la tabla de área sumada es la suma de todos los píxeles por encima y a la izquierda de ( x ,  y ), inclusive: ^{[3] [4]} donde es el valor del píxel en ( x , y ). $${\displaystyle I(x,y)=\sum _{\begin{smallmatrix}x'\leq x\\y'\leq y\end{smallmatrix}}i(x',y')}$$ ${\displaystyle i(x,y)}$

La tabla de área sumada se puede calcular de manera eficiente en una sola pasada sobre la imagen, ya que el valor en la tabla de área sumada en ( x ,  y ) es simplemente: ^[5] (Tenga en cuenta que la matriz sumada se calcula desde la esquina superior izquierda) $${\displaystyle I(x,y)=i(x,y)+I(x,y-1)+I(x-1,y)-I(x-1,y-1)}$$

Una descripción del cálculo de una suma en la estructura de datos/algoritmo de la tabla de área sumada

Una vez calculada la tabla de áreas sumadas, evaluar la suma de intensidades sobre cualquier área rectangular requiere exactamente cuatro referencias de matriz independientemente del tamaño del área. Es decir, la notación en la figura de la derecha, con A = ( x ₀ , y ₀ ) , B = ( x ₁ , y ₀ ) , C = ( x ₀ , y ₁ ) y D = ( x ₁ , y ₁ ) , la suma de i ( x , y ) sobre el rectángulo abarcado por A , B , C y D es: $${\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)}$$

Extensiones

Este método se extiende naturalmente a dominios continuos. ^[2]

El método también se puede extender a imágenes de alta dimensión. ^[6] Si las esquinas del rectángulo están en , entonces la suma de los valores de la imagen contenidos en el rectángulo se calcula con la fórmula donde es la imagen integral en y la dimensión de la imagen. La notación corresponde en el ejemplo a , , , y . En neuroimagen , por ejemplo, las imágenes tienen dimensión o , cuando se utilizan vóxeles o vóxeles con una marca de tiempo. ${\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}$

Este método se ha extendido a imágenes integrales de orden superior, como en el trabajo de Phan et al. ^[7], quienes proporcionaron dos, tres o cuatro imágenes integrales para calcular de manera rápida y eficiente la desviación estándar (varianza), la asimetría y la curtosis del bloque local en la imagen. Esto se detalla a continuación:

Para calcular la varianza o desviación estándar de un bloque, necesitamos dos imágenes integrales: La varianza viene dada por: Sea y las sumas del bloque de y , respectivamente. y se calculan rápidamente mediante la imagen integral. Ahora, manipulamos la ecuación de varianza como: Donde y . $${\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 {\begin{aligned}\operatorname {Var} (X)&={\frac {1}{n}}\sum _{i=1}^{n}\left(x_{i}^{2}-2\mu x_{i}+\mu ^{2}\right)\\[1ex]&={\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]\\[1ex]&={\frac {1}{n}}\left[\sum _{i=1}^{n}x_{i}^{2}-2\sum _{i=1}^{n}\mu x_{i}+n\mu ^{2}\right]\\[1ex]&={\frac {1}{n}}\left[\sum _{i=1}^{n}x_{i}^{2}-2\mu \sum _{i=1}^{n}x_{i}+n\mu ^{2}\right]\\[1ex]&={\frac {1}{n}}\left[S_{2}-2{\frac {S_{1}}{n}}S_{1}+n\left({\frac {S_{1}}{n}}\right)^{2}\right]\\[1ex]&={\frac {1}{n}}\left[S_{2}-{\frac {S_{1}^{2}}{n}}\right]\end{aligned}}}$$ ${\displaystyle \mu =S_{1}/n}$ ${\textstyle S_{2}=\sum _{i=1}^{n}x_{i}^{2}}$

Similar a la estimación de la media ( ) y la varianza ( ), que requiere las imágenes integrales de la primera y segunda potencia de la imagen respectivamente (es decir, ); se pueden realizar manipulaciones similares a las mencionadas anteriormente para la tercera y cuarta potencia de las imágenes (es decir , .) para obtener la asimetría y la curtosis. ^[7] Pero un detalle de implementación importante que se debe tener en cuenta para los métodos anteriores, como lo mencionan F Shafait et al. ^[8] es el desbordamiento de enteros que ocurre para las imágenes integrales de orden superior en caso de que se utilicen enteros de 32 bits. ${\displaystyle \mu }$ ${\displaystyle \operatorname {Var} }$ ${\displaystyle I,I^{2}}$ ${\displaystyle I^{3}(x,y),I^{4}(x,y)}$

Consideraciones de implementación

Es posible que el tipo de datos para las sumas deba ser diferente y más grande que el tipo de datos utilizado para los valores originales, a fin de dar cabida a la suma más grande esperada sin desbordamiento . Para los datos de punto flotante, el error se puede reducir utilizando la suma compensada .

Véase también

• Prefijo suma

Referencias

1. Lewis, JP (1995). Coincidencia rápida de plantillas . Proc. Vision Interface . Págs. 120–123.
2. Finkelstein, Amir; neeratsharma (2010). "Integrales dobles mediante la suma de valores de la función de distribución acumulativa". Proyecto de demostración Wolfram .
3. Crow, Franklin (1984). "Tablas de área sumadas para mapeo de texturas". SIGGRAPH '84: Actas de la 11.ª conferencia anual sobre gráficos por computadora y técnicas interactivas . págs. 207–212. doi :10.1145/800031.808600.
4. Viola, Paul; Jones, Michael (2002). "Detección robusta de objetos en tiempo real" (PDF) . Revista internacional de visión artificial .
5. BADGERATI (3 de septiembre de 2010). «Computer Vision – The Integral Image» (Visión por computadora: la imagen integral). computersciencesource.wordpress.com . Consultado el 13 de febrero de 2017 .
6. Tapia, Ernesto (enero de 2011). "Una nota sobre el cálculo de imágenes integrales de alta dimensión". Pattern Recognition Letters . 32 (2): 197–201. Código Bibliográfico :2011PaReL..32..197T. doi :10.1016/j.patrec.2010.10.007.
7. Phan, Thien; Sohoni, Sohum; Larson, Eric C.; Chandler, Damon M. (22 de abril de 2012). "Aceleración de la evaluación de la calidad de imagen basada en el análisis del rendimiento". Simposio IEEE Southwest de 2012 sobre análisis e interpretación de imágenes (PDF) . págs. 81–84. CiteSeerX 10.1.1.666.4791 . doi :10.1109/SSIAI.2012.6202458. hdl :11244/25701. ISBN .  978-1-4673-1830-3. Número de identificación del sujeto  12472935.
8. Shafait, Faisal; Keysers, Daniel; M. Breuel, Thomas (enero de 2008). Yanikoglu, Berrin A.; Berkner, Kathrin (eds.). "Implementación eficiente de técnicas de umbralización adaptativa local utilizando imágenes integrales" (PDF) . Imágenes electrónicas . Reconocimiento y recuperación de documentos XV. 6815 : 681510–681510–6. Código Bibliográfico :2008SPIE.6815E..10S. CiteSeerX 10.1.1.109.2748 . doi :10.1117/12.767755. S2CID  9284084. 

Enlaces externos

• Implementación de tabla sumada en detección de objetos

Vídeos de conferencias

• Una introducción a la teoría detrás del algoritmo de imagen integral
• Una demostración de una versión continua del algoritmo de imagen integral, del Proyecto de Demostraciones Wolfram