Una tabla de área sumada 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 dominio de procesamiento de imágenes , también se conoce como imagen integral . Fue introducido a los gráficos por computadora en 1984 por Frank Painter para su uso con mipmaps . En visión por computadora , Lewis [1] lo popularizó y luego se le dio el nombre de "imagen integral" y se usó de manera prominente dentro del marco de detección de objetos 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 funciones de distribución acumulativa respectivas . [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 arriba y a la izquierda de ( x , y ), inclusive: [3] [ enlace muerto ] [ 4]
dónde es el valor del píxel en (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 solo: [5]
- (Observó que la matriz sumada se calcula desde la esquina superior izquierda)
Una vez que se ha calculado 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 0 , y 0 ), B = (x 1 , y 0 ), C = (x 0 , y 1 ) y D = (x 1 , y 1 ), la suma de i (x, y) sobre el rectángulo formado por A, B, C y D es:
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 son con en , entonces la suma de los valores de imagen contenidos en el rectángulo se calcula con la fórmula
dónde es la imagen integral en y la dimensión de la imagen. La notación corresponden 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.
Este método se ha extendido a la imagen integral de alto orden como en el trabajo de Phan et al. [7] quien proporcionó 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 la desviación estándar de un bloque, necesitamos dos imágenes integrales:
La varianza viene dada por:
Dejar y denotar las sumas de bloque de y , respectivamente. y se calculan rápidamente por imagen integral. Ahora, manipulamos la ecuación de varianza como:
Dónde y .
Similar a la estimación de la media () y varianza (), que requiere las imágenes integrales de la primera y segunda potencia de la imagen respectivamente (es decir, ); manipulaciones similares a las mencionadas anteriormente se pueden hacer a la tercera y cuarta potencia de las imágenes (es decir,.) 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 lo mencionan F Shafait et al. [8] es el desbordamiento de enteros que se produce para las imágenes integrales de orden superior en caso de que se utilicen enteros de 32 bits.
Referencias
- ^ Lewis, JP (1995). Emparejamiento rápido de plantillas . Proc. Interfaz de visión . págs. 120-123.
- ^ a b Finkelstein, Amir; neeratsharma (2010). "Integrales dobles sumando valores de función de distribución acumulativa" . Proyecto de demostración Wolfram .
- ^ Cuervo, Franklin (1984). "Tablas de área sumada para mapeo de texturas" (PDF) . SIGGRAPH '84: Actas de la 11ª conferencia anual sobre gráficos por ordenador y técnicas interactivas . págs. 207–212.
- ^ Viola, Paul; Jones, Michael (2002). "Detección robusta de objetos en tiempo real" (PDF) . Revista Internacional de Visión por Computador .
- ^ BADGERATI (3 de septiembre de 2010). "Visión por computadora - La imagen integral" . Computersciencesource.wordpress.com . Consultado el 13 de febrero de 2017 .
- ^ Tapia, Ernesto (enero de 2011). "Una nota sobre el cálculo de imágenes integrales de alta dimensión". Cartas de reconocimiento de patrones . 32 (2): 197-201. doi : 10.1016 / j.patrec.2010.10.007 .
- ^ a b 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 (PDF) . 2012 Simposio IEEE Southwest sobre análisis e interpretación de imágenes . págs. 81–84. CiteSeerX 10.1.1.666.4791 . doi : 10.1109 / SSIAI.2012.6202458 . ISBN 978-1-4673-1830-3.
- ^ Shafait, Faisal; Keysers, Daniel; M. Breuel, Thomas (enero de 2008). "Implementación eficiente de técnicas locales de umbralización adaptativa utilizando imágenes integrales" (PDF) . Imágenes electrónicas . Reconocimiento y recuperación de documentos XV. 6815 : 681510–681510–6. CiteSeerX 10.1.1.109.2748 . doi : 10.1117 / 12.767755 .
enlaces externos
- Videos 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 Wolfram Demonstrations Project