Tabla de áreas sumadas

Una tabla de área sumada es una estructura de datos y un algoritmo para generar de forma rápida y eficiente 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 introducida en los gráficos por computadora en 1984 por Frank Crow para su uso con mipmaps . En visión por computadora, fue popularizada por Lewis ^{[ 1 ]} y posteriormente recibió el nombre de "imagen integral", utilizándose prominentemente 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, 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 acumulativa . ^{[ 2 ]}

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

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

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, con la notación de la figura de la derecha, donde 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)}$$

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

El método también puede extenderse a imágenes de alta dimensión. ^{[ 6 ]} Si las esquinas del rectángulo son${\displaystyle x^{p}}$con${\displaystyle p}$en${\displaystyle \{0,1\}^{d}}$, luego la suma de los valores de la imagen contenidos en el rectángulo se calcula con la fórmula $${\displaystyle \sum _{p\in \{0,1\}^{d}}(-1)^{d-\|p\|_{1}}I(x^{p})}$$ dónde${\displaystyle I(x)}$es la imagen integral en${\displaystyle x}$y${\displaystyle d}$la dimensión de la imagen. La notación${\displaystyle x^{p}}$corresponder en el ejemplo a${\displaystyle d=2}$,${\displaystyle A=x^{(0,0)}}$,${\displaystyle B=x^{(1,0)}}$,${\displaystyle C=x^{(1,1)}}$y${\displaystyle D=x^{(0,1)}}$En neuroimagen , por ejemplo, las imágenes tienen dimensión${\displaystyle d=3}$o${\displaystyle d=4}$, cuando se utilizan vóxeles o vóxeles con una marca de tiempo.

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 forma rápida y eficiente la desviación estándar (varianza), la asimetría y la curtosis de bloques locales 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: $${\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 viene dada por: $${\displaystyle \operatorname {Var} (X)={\frac {1}{n}}\sum _{i=1}^{n}(x_{i}-\mu )^{2}.}$$ Dejar${\displaystyle S_{1}}$y${\displaystyle S_{2}}$denotan las sumas de bloques${\displaystyle ABCD}$de${\displaystyle I}$y${\displaystyle I^{2}}$, respectivamente.${\displaystyle S_{1}}$y${\displaystyle S_{2}}$se calculan rápidamente mediante la imagen integral. Ahora, manipulamos la ecuación de la varianza de la siguiente manera: $${\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}}}$$ Dónde${\displaystyle \mu =S_{1}/n}$y${\textstyle S_{2}=\sum _{i=1}^{n}x_{i}^{2}}$.

Similar a la estimación de la media (${\displaystyle \mu }$) y varianza (${\displaystyle \operatorname {Var} }$), lo que requiere las imágenes integrales de la primera y segunda potencia de la imagen respectivamente (es decir,${\displaystyle I,I^{2}}$); se pueden realizar manipulaciones similares a las mencionadas anteriormente con la tercera y cuarta potencia de las imágenes (es decir,${\displaystyle I^{3}(x,y),I^{4}(x,y)}$.) para obtener la asimetría y la curtosis. ^{[ 7 ]} Pero un detalle importante de implementación que debe tenerse en cuenta para los métodos anteriores, como 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.

Es posible que el tipo de datos para las sumas deba ser diferente y de mayor tamaño que el tipo de datos utilizado para los valores originales, para poder acomodar la suma máxima esperada sin desbordamiento . Para datos de punto flotante, el error se puede reducir mediante la suma compensada .

• Suma de prefijo

• Implementación de tablas sumadas en la detección de objetos