Tabla de áreas sumadas

Tipo de algoritmo de estructura de datos

Usar una tabla de áreas sumadas ( 2. ) de un cuadrado mágico de orden 6 ( 1. ) para resumir un subrectángulo de sus valores; cada punto coloreado resalta la suma dentro del rectángulo de ese color.

Una tabla de áreas sumadas es una estructura de datos y un algoritmo para generar rápida y eficientemente la suma de valores en un subconjunto rectangular de una cuadrícula. En el ámbito del procesamiento de imágenes , también se la conoce como imagen integral . Fue introducido en los gráficos por computadora en 1984 por Frank Crow para su uso con mapas mip . En visión por computadora, Lewis ^[1] lo popularizó y luego se le dio el nombre de "imagen integral" y se utilizó 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 la probabilidad multidimensional. funciones de distribución, concretamente 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 acumuladas . ^[2]

el algoritmo

Como sugiere el nombre, el valor en cualquier punto ( x ,  y ) en la tabla de áreas sumadas es la suma de todos los píxeles arriba 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 áreas sumadas se puede calcular eficientemente en una sola pasada sobre la imagen, ya que el valor en la tabla de áreas sumadas 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 de cómo calcular una suma en la estructura/algoritmo de datos de la tabla de áreas sumadas

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, que tiene A = ( x ₀ , y ₀ ) , B = ( x ₁ , y ₀ ) , C = ( x ₀ , y ₁ ) y D = ( x ₁ , y _1). ) , 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 dentro de , entonces la suma de los valores de la imagen contenidos en el rectángulo se calcula con la fórmula donde está 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 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 alto orden como en el trabajo de Phan et al. ^[7] quienes proporcionaron dos, tres o cuatro imágenes integrales para calcular rápida y eficientemente 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 la desviación estándar de un bloque, necesitamos dos imágenes integrales: La varianza viene dada por: Sean y denotemos las sumatorias del bloque de y , respectivamente. y se calculan rápidamente mediante 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 en las potencias tercera y cuarta de las imágenes (es decir ,) para obtener la asimetría y la curtosis. ^[7] Pero un detalle de implementación importante que debe tenerse en cuenta para los métodos anteriores, como lo mencionan F Shafait et al. ^[8] es el desbordamiento de enteros que se produce para las imágenes integrales de orden superior en el 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 mayor que el tipo de datos utilizado para los valores originales, a fin de acomodar la suma más grande esperada sin desbordamiento . Para datos de punto flotante, el error se puede reducir mediante la suma compensada .

Ver también

• Suma de prefijo

Referencias

1. Lewis, JP (1995). Coincidencia rápida de plantillas . Proc. Interfaz de visión . págs. 120-123.
2. Finkelstein, Amir; Neeratsharma (2010). "Integrales dobles sumando valores de la función de distribución acumulativa". Proyecto de demostración de Wolfram .
3. Cuervo, Franklin (1984). "Tablas de áreas sumadas para mapeo de texturas". SIGGRAPH '84: Actas de la undécima conferencia anual sobre gráficos por computadora y técnicas interactivas . págs. 207–212. doi :10.1145/800031.808600.
4. Viola, Pablo; Jones, Michael (2002). "Detección robusta de objetos en tiempo real" (PDF) . Revista Internacional de Visión por Computadora .
5. BADGERATI (3 de septiembre de 2010). "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". Letras de reconocimiento de patrones . 32 (2): 197–201. Código Bib : 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 la imagen basada en análisis de 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. S2CID  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 Bib : 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