Chrome

Juan Mellado, 28 Mayo, 2011 - 10:41

Este paso es el último en lo que a manipulación de imágenes se refiere. Admite como entrada la imagen en escala de grises creada en el primer paso, y los cuadriláteros candidatos encontrados en el último. Para cada cuadrilátero extrae la región de la imagen que cubre cada uno de ellos eliminando la transformación de perspectiva, es decir, la deformación que se produce en el marcador debido a la perspectiva.

Transformación de Perspectiva (Homography)
WarpCuando se toma una imagen de un marcador, y de hecho de cualquier objeto, se produce una deformación debido a la perspectiva. Los marcadores que son cuadrados pierden sus ángulos rectos y se convierten en cuadriláteros con lados más grandes que otros. El objetivo de ese paso es tratar de recuperar la imagen del marcador original. Es decir, superponer los cuadriláteros encontrados encima de la imagen original (en escala de grises), y proyectar la región de la imagen que cubren sobre un cuadrado, ya que esa es su forma original que se quiere restaurar.

A grandes rasgos, se trata de encontrar la operación que proyecte las cuatro esquinas de un cuadrilátero en las cuatro esquinas de un cuadrado. Y que además sirva para todos los puntos intermedios. Afortunadamente este es un procedimiento sobre el que existe mucha información, ya que es como el que se utiliza para aplicar texturas a los modelos tridimensionales, aunque en sentido contrario.

ArUco, la librería de realidad aumentada que estoy portando a JavaScript, utiliza dos funciones de OpenCV para este paso: getPerspectiveTransform y warpPerspective. La primera calcula una matriz que multiplicada por un punto en el cuadrilátero origen devuelve un punto equivalente en el cuadrado destino. La segunda acepta una imagen, un cuadrilátero, una matriz de transformación, y retorna una nueva imagen del área cubierta por el cuadrilátero sobre la que se ha aplicado la matriz de transformación para eliminar la deformación debida a la perspectiva. El problema de estas dos funciones es que son demasiado complejas de portar directamente a JavaScript debido a que hacen uso de LAPACK, una librería matemática con la que resuelven el sistema de ecuaciones lineales necesario para calcular la transformación de perspectiva. Así que, aprovechando que estoy en un entorno mucho más controlado y menos genérico que al que tiene que enfrentarse OpenCV, he optado por una implementación mucho más liviana usando las ecuaciones de toda la vida expuestas por Paul Heckbert en su tesis ¿doctoral? titulada Fundamentals of Texture Mapping and Image Warping. Este "paper" es un clásico, e incluso tiene un apéndice con código en C, mucho más sencillo de portar a JavaScript que el de OpenCV.

El resultado de este proceso es cada una de las figuras que he puesto en la primera imagen. Una para cada cuadrilátero candidato. ArUco utiliza un tamaño de 50x50 pixels para los cuadrados destino, aunque yo he preferido utilizar un tamaño de 49x49, ya que los marcadores son matrices de 7x7.

Para terminar, dos detalles acerca de la implementación. El primero es que en realidad se recorre el cuadrado y se calculan los puntos en el cuadrilátero, y no al revés, ya que es mucho más sencillo recorrer el cuadrado. Y el segundo es que no he implementado ningún tipo de interpolación, por lo que en cuanto se gira un poco la imagen aparecen los clásicos "dientes de sierra". Esto último no ocurre en ArUco, ya que que OpenCV utiliza interpolación bilineal para obtener una imagen mejor. En general, esta función es una de las más serias candidatas a ser modificadas y optimizadas.

Umbralización (Otsu)
OtsuUna vez obtenidas esas pequeñas imágenes del paso anterior hay que volver a comenzar el proceso de análisis por el principio. Es decir, aplicando un valor umbral que reduzca la cantidad de información a procesar. Por suerte, esta vez se pueden tomar decisiones de forma mucho menos subjetiva que al principio. El factor diferenciador está en el hecho de que los marcadores sólo tienen dos colores: blanco y negro, lo que permite automatizar el proceso de cálculo del valor umbral ideal.

El método de Otsu se basa en el análisis del histograma de una imagen dada. Es decir, en el número de veces que aparece cada tono de gris dentro de ella. Divide el histograma en dos grandes grupos, de forma que a un lado quedan los valores que representan el "fondo" de la imagen y al otro los que representan el "frente". Matemáticamente se dice que calcula un valor tal que la varianza (dispersión de los tonos de gris) es mínima dentro de cada grupo, pero que es máxima entre los dos grupos.

El algoritmo es sencillo de implementar, y como se observa en la segunda imagen, resultante de aplicar a la primera imagen el valor umbral calculado por el método de Otsu, hace realmente un gran trabajo.

Actualizado 19/03/2012: Actualmente js-aruco implementa supersampling evitando la aparición de "dientes de sierra" en los bordes.

Realidad Aumentada
1. Introducción
2. Escala de grises (Grayscale & Gaussian Blur)
3. Umbralización (Adaptive Thresholding)
4. Detección de contornos (Suzuki)
5. Aproximación a polígonos (Douglas-Peucker)
6. Transformación de perspectiva (Homography & Otsu)
7. Detección de marcadores
8. js-aruco: Realidad Aumentada en JavaScript

Juan Mellado, 27 Mayo, 2011 - 15:43

El siguiente eslabón de la cadena en la búsqueda de los cuadriláteros candidatos disminuye de forma drástica la información a procesar. Parte de los contornos encontrados en el paso anterior, los aproxima a polígonos, y los descarta rápidamente mediante una serie de decisiones muy sencillas e intuitivas.

Aproximación a Polígonos (Douglas-Peucker)
Douglas-PeuckerLos contornos de los que se parte para este paso son colecciones de puntos. Todos y cada uno de los pixels que forman parte de ellos, ya que no se guardaron sólo las esquinas, sino cada pixel individual encontrado. Esto permite tomar algunas decisiones tempranas, como por ejemplo descartar los contornos que no tengan un mínimo de puntos. Es decir, los más pequeños. ArUco descarta aquellos que no tengan al menos un 20% del ancho de la imagen. Es un número arbitrario que simplemente da buen resultado. En la primera imagen puede verse el resultado del descarte. Los contornos más pequeños, los pixels aislados, han desaparecido.

Tratar los contornos como colecciones de puntos tiene sus ventajas, pero también sus inconvenientes. Por ejemplo, son difíciles de estudiar. Para solventar este problema se transportan a otro contexto, como es el de los polígonos, sobre el que existe mucha información y métodos disponibles para su análisis. ArUco utiliza la función approxPolyDP de OpenCV para convertir una colección de puntos en un polígono mediante el algoritmo de Douglas-Peucker.

Un buen ejemplo del propósito de este algoritmo es pensar en una bicicleta que registra su posición cada pocos metros con ayuda de un GPS. Si después de varios kilómetros consultamos la ruta completa que ha seguido, mirando todas las posiciones registradas por el GPS, esta parecerá bastante errática, con continuos pequeños giros a izquierda y derecha, cuando en realidad sabemos que su recorrido habrá consistido en ir de un punto A a otro B, pasando por una serie de puntos intermedios importantes. El algoritmo de Douglas-Peucker lo que hace es suavizar esa línea errática, proporcionando una línea que se ajusta más al recorrido real sin perder los puntos intermedios importantes.

Douglas-PeuckerEl algoritmo admite como entrada una lista de puntos y una distancia máxima permitida. Define un segmento que va desde el primer punto de la lista hasta el último, y calcula la distancia más corta que hay desde dicho segmento a todos y cada uno del resto de puntos de la lista. Si encuentra un punto a una distancia mayor que la máxima pasada como parámetro divide la lista y el segmento en dos, utilizando el punto encontrado como nuevo extremo. Y vuelve a empezar el proceso comprobando cada nueva lista contra cada nuevo segmento de forma individual, creando nuevas listas y segmentos si fuera necesario, de forma recursiva.

En la segunda imagen puede verse los polígonos resultantes de aplicar el algoritmo. Hay uno un poco "feo" que atraviesa la imagen. Puede parecer un error, pero en realidad no lo es. ArUco utiliza como distancia máxima para al algoritmo el 5% del número de puntos que tiene cada contorno de forma individual. El contorno "feo" tiene 2218 puntos, por lo que distancia máxima permitida es de 110 pixels, lo que prácticamente descarta todos los puntos, excepto los más alejados.

La implementación que he hecho en JavaScript del algoritmo está tomada directamente del código de OpenCV, que incorpora un tratamiento específico para los contornos cerrados, e implementa la recursividad mediante un array tratado como una pila.

Douglas-Peucker

En la tercera imagen se puede ver la ventaja de aproximar los contornos a polígonos. Por ejemplo, lo primero que puede hacerse es descartar los polígonos que no tengan cuatro lados, ya que recordemos que estamos buscando cuadriláteros. Aún así, algún polígono se puede escapar de la criba, como por ejemplo esa especie de triángulo degenerado de la parte superior derecha que también tiene cuatro lados. Afortunadamente también se puede descartar rápidamente quedándonos sólo con los polígonos convexos. Y aún así, hay pequeños polígonos aquí y allá. Pero también se pueden descartar rápidamente quedándonos sólo con aquellos que tengan un tamaño de lado mínimo. ArUco concretamente descarta todos aquellos cuyo lado mínimo no supere los 10 pixels de largo. Como resultado de todos estos descartes se acaba teniendo seis candidatos, que además son los deseados.

Douglas-PeuckerEstos descartes son triviales de implementar. No obstante, ArUco incorpora un control adicional para un caso que puede llegar a darse pero que durante el análisis de la imagen que estoy utilizando como referencia no ha sucedido. Debido a que en el paso previo se detectaron contornos tanto exteriores como interiores, puede ocurrir que se detecten dos cuadriláteros, uno dentro de otro, siendo necesario descartar el más interno. Para probar este caso he utilizado otra imagen prácticamente igual pero donde sí se reproducía esta situación.

Como se observa, hay dos cuadriláteros interiores que deberían descartarse. ArUco calcula la distancia media entre las esquinas de los polígonos y si encuentra dos que están muy cerca descarta el de menor perímetro, que necesariamente será el más interno. Entendiendo por "muy cerca" que se encuentren a menos de 10 pixels de distancia.

Douglas-Peucker

Por último, indicar que esos dibujos con tantos colorines del final son el resultado de un paso previo necesario al cálculo de las distancias entre esquinas. Para que funcione correctamente el proceso, las esquinas tienen que estar ordenadas en el sentido contrario de las agujas del reloj. He utilizado los colores rojo-verde-azul-negro (RGBA) para indicar el orden antes y después del giro. Aunque yo los veo al revés... eso del giro siempre me ha dado problemas. Y en cualquier caso, creo que para que el proceso de descarte fuera más eficaz sería necesario además comparar las esquinas partiendo de una referencia concreta común para los dos polígonos siendo comparados. Como por ejemplo partiendo de la esquina que se encuentre más arriba a la izquierda.

Realidad Aumentada
1. Introducción
2. Escala de grises (Grayscale & Gaussian Blur)
3. Umbralización (Adaptive Thresholding)
4. Detección de contornos (Suzuki)
5. Aproximación a polígonos (Douglas-Peucker)
6. Transformación de perspectiva (Homography & Otsu)
7. Detección de marcadores
8. js-aruco: Realidad Aumentada en JavaScript

Juan Mellado, 26 Mayo, 2011 - 17:52

El siguiente paso del proceso es la detección de contornos, una operación un tanto distinta a las anteriores por dos motivos principales. El primero es que no consiste en iterar aplicando una misma función de forma monótona sobre todos los pixels de la imagen. Y el segundo es que el resultado que se obtiene no es una nueva imagen, sino un colección de conjuntos de puntos sobre la imagen.

Detección de Contornos (Suzuki)
Contour DetectionPara este paso se parte de la imagen resultante del Adaptive Thresholding del paso anterior. Es decir, de una imagen que tan solo consta de pixels con valor cero o uno. Sobre ella se aplica un algoritmo que la barre, empezando por su esquina superior izquierda, a la busca de un primer pixel a uno, y que cuando lo encuentra es capaz de seguir la cadena de pixels con valor uno que se encuentran unidos a él hasta volver al pixel de partida. Esa cadena de pixels a uno encontrados se denomina contorno. Y es más, el algoritmo es capaz de encontrar todos los contornos presentes en la imagen, ya que cuando termina con uno empieza de nuevo el proceso hasta asegurarse de haber barrido la imagen por completo.

El algoritmo es bastante notable, ya que no sólo es capaz de encontrar los contornos exteriores, sino también los interiores a otros, y retornarlos clasificados jerárquicamente. En la imagen que puesto en este post he utilizado colores distintos para los contornos en función de que sean exteriores o interiores, y que se aprecie mejor el increíble trabajo que es capaz de hacer. Por cierto, las imágenes que estoy poniendo son el resultado de la ejecución de mi librería en JavaScript, dibujando directamente en un canvas de HTML5.

ArUco utiliza la función findContours de OpenCV que implementa este algoritmo. En la documentación, como toda referencia de implementación, se refiere al "paper" original donde sus autores lo describen en detalle: "Topological structural analysis of digitized binary images by border following" Satoshi Suzuki and Keiichi Abe. [suzuki85]

No obstante, en la práctica existe toda una familia de algoritmos de extracción de contornos que recorren pixels vecinos rotando a izquierda o derecha dependiendo del valor del pixel en curso. Lo que diferencia a este es la forma en que etiqueta los pixels visitados para catalogarlos y clasificarlos. El proceso completo es un poco largo de explicar, pero sus pautas generales no son demasiado complejas de entender. Básicamente hay un contador de contornos encontrados y un buffer de pixels recorridos. El contador se inicializa a cero y el buffer con una copia de la imagen original. Se barre el buffer de arriba abajo y de izquierda a derecha. Una transición de un pixel 0 a otro 1 indica que se ha detectado un borde exterior, momento en que se suma uno al contador de contornos encontrados y se buscan todos los pixels 1 vecinos del encontrado. Si el pixel no tiene vecinos a 1 se cambia el valor del pixel por el del contador con signo contrario y se empieza otra vez con el siguiente pixel. En caso contrario se cambia el valor del pixel por el del contador, excepto que su valor sea mayor que 1, lo que significa que ya ha sido visitado, y se continúa buscando vecinos a 1 hasta retornar al pixel inicial. Una transición de un pixel con valor igual o mayor que 1 a otro 0 indica que se ha detectado un borde interior, momento en que se repite el mismo proceso usado para los contornos exteriores.

El algoritmo presenta una pequeña dificultad en los bordes de la imagen, y para solventarlo presupone que la imagen está rodeada por los cuatro costados de pixels con valor 0. Es decir, que el buffer que utiliza tiene una fila más por encima y por debajo, y una columna más a derecha e izquierda, que la imagen original.

La implementación del algoritmo en OpenCV es bastante eficiente y es la que he seguido, pero de un manera mucho más simplificada, eliminando una serie de parámetros que admite la función original y que permiten controlar como quiere que se devuelvan los contornos, o la coordenada del pixel concreto a partir del cual se quiere empezar a buscar contornos dentro de la imagen. De hecho, esto está siendo una constante a lo largo de todo el desarrollo. OpenCV es una librería que ofrece funciones que admiten muchos paths de ejecución distintos, y me estoy limitando a implementar sólo aquellos que estoy usando realmente.

Realidad Aumentada
1. Introducción
2. Escala de grises (Grayscale & Gaussian Blur)
3. Umbralización (Adaptive Thresholding)
4. Detección de contornos (Suzuki)
5. Aproximación a polígonos (Douglas-Peucker)
6. Transformación de perspectiva (Homography & Otsu)
7. Detección de marcadores
8. js-aruco: Realidad Aumentada en JavaScript

Juan Mellado, 25 Mayo, 2011 - 17:53

El tercer paso a la caza y captura de cuadriláteros que puedan contener marcadores es la umbralización (menuda palabreja), que consiste en definir un valor umbral y compararlo con cada uno de los pixels de la imagen. A los pixels que estén por debajo del umbral se les asigna un valor, y a los que estén por encima otro. De esta forma se divide toda la población de valores en tan sólo dos grupos, reduciendo considerablemente la complejidad de la información a analizar.

Umbralización (Adaptive Thresholding)
Adaptive ThresholdingAplicar un valor umbral a una imagen presenta dos dificultades. La primera es decidir que valor concreto tomar, y la segunda es conseguir que dicho valor sirva para cualquier imagen posible que pueda llegar desde la webcam. Si los pixels tienen un valor que se encuentra dentro del rango que va de 0 a 255, ¿cual es el mejor valor para el umbral? ¿128, que está en la mitad del rango? ¿Y por qué no 57?

Pues resulta que no se puede decidir de antemano sin echarle un vistazo antes a la imagen, ya que el mayor inconveniente que presenta este procedimiento es que es muy sensible a la iluminación. Con poca iluminación los pixels tienden a tomar valores bajos, oscuros, cercanos al 0, y con mucha iluminación toman valores altos, claros, cercanos al 255. Y peor es el caso cuando la iluminación varía dentro de la propia imagen, con algunas zonas muy oscuras y otras muy claras.

Afortunadamente se han desarrollado soluciones distintas para tratar de resolver este problema del thresholding básico. En el código fuente de ArUco, la librería que estoy tomando como referencia para la implementación, hay constancia de pruebas con tres algoritmos distintos. Incluso en uno de los comentarios se señala que un método llamado de Canny normalmente debería ser el que mejor resultado ofreciera, pero que después de probarlo se encontraron con problemas debidos a que se generaban huecos no deseados en los contornos de los cuadriláteros que hacían imposible su correcta detección posterior.

Finalmente se decidieron por el Adaptive Thresholding. Este algoritmo no aplica el umbral de una manera global sobre todos los pixels de la imagen, sino que tiene en cuenta las variaciones en la iluminación de una manera local para cada pixel de forma individual. Algo que consigue tomando el valor original de cada pixel de la imagen, y comparándolo con otro valor calculado que sea algún tipo de media de los valores de los pixeles que tiene alrededor. En las zonas homogéneas el valor del pixel se asemejará mucho a la de la media de sus vecinos, mientras que en las zonas de transición abruptas, en los "bordes", se diferenciará de dicha media.

ArUco utiliza la función adaptiveThreshold de OpenCV, pasándole la imagen en escala de grises como imagen original, e indicándole que utilice un filtro gaussiano para calcular los valores medios. Y de igual forma, en mi implementación en JavaScript, como expliqué en el artículo anterior, ya tengo calculadas una imagen en escala de grises y otra con un filtro gaussiano, por lo que puedo imitar el funcionamiento de dicha función. Al final, todo lo que hay que hacer es restar a la primera imagen la segunda y aplicar el umbral sobre la imagen resultante:

Adaptive Thresholding

Un momento, ¿"aplicar el umbral"? ¿Pero qué valor finalmente? ¿El algoritmo no calcula el valor umbral? Pues no, lo único que ofrece es una imagen más propicia para realizar el thresholding básico sin que se vea afectado por las variaciones de iluminación de la imagen original. ArUco utiliza un valor fijo de 7 como umbral. Puede parecer un poco arbitrario, pero da buen resultado.

A los pixels que están por debajo del umbral se les asigna un 1, y a los que están por encima un 0. De esta forma se obtiene una imagen "binaria", en el sentido de que sólo tiene dos valores (blanco y negro), reduciendo la cantidad de información a tratar a tan sólo un 12,5% (un octavo) de la que se encuentra presente en la imagen en escala de grises.

Algo que sería interesante probar en un futuro es utilizar otro tipo de filtros más económicos de calcular que el gaussiano, como una media ordinaria por ejemplo. O realizar una implementación en un shader con WebGL.

Actualizado 19/03/2012: Actualmente js-aruco implementa un Stack Box Blur que resulta más eficiente que el Gaussian Blur.

Realidad Aumentada
1. Introducción
2. Escala de grises (Grayscale & Gaussian Blur)
3. Umbralización (Adaptive Thresholding)
4. Detección de contornos (Suzuki)
5. Aproximación a polígonos (Douglas-Peucker)
6. Transformación de perspectiva (Homography & Otsu)
7. Detección de marcadores
8. js-aruco: Realidad Aumentada en JavaScript

Juan Mellado, 24 Mayo, 2011 - 17:07

Los dos primeros pasos para localizar cuadriláteros candidatos que puedan contener marcadores son: convertir la imagen original a escala de grises, y crear una nueva imagen desenfocada. El primer paso tiene la finalidad de simplificar la cantidad de información a procesar, ya que en realidad los colores no son significativos para el proceso. El segundo paso se realiza con el objetivo de eliminar ruidos, aunque en realidad es sólo una parte de un proceso posterior que se explicará más adelante.

Escala de grises (Grayscale)
GrayscaleEl proceso de conversión de una imagen en color a otra en escala de grises es bastante conocido, todo un clásico dentro del mundillo del procesamiento de imágenes por ordenador. Consiste en recorrer todos los pixels de la imagen, y para cada pixel de forma individual multiplicar sus componente RGB (rojo, verde y azul), cuyos valores oscilan entre 0 y 255, por unos coeficientes y sumarlos.

Los componentes RGB originales del pixel se sustituyen por el valor resultante de esa suma. Los tres componentes con el mismo valor, para lograr así el efecto de escala de grises, ya que cuando los tres componentes tienen un mismo valor lo que se obtiene es un tono gris, excepto en los extremos, donde (0, 0, 0) es negro y (255, 255, 255) es blanco.

Los coeficientes que se utilizan normalmente son 0.299 para el rojo (R), 0.587 para el verde (G), y 0.114 para el azul (B). Si se suman los tres coeficientes se observa que el total vale 1 (= 0.299 + 0.587 + 0.114), lo que garantiza que el valor resultante de la suma de los productos por los componentes originales del pixel será un valor comprendido también entre 0 y 255.

En JavaScript se puede acceder a las imágenes a través del canvas 2D introducido con HTML5. La función "getImageData" devuelve un objeto "ImageData" que contiene un array que proporciona acceso directo a los pixels. Es un array plano que empieza con los componentes RGBA del primer pixel en las posiciones 0, 1, 2 y 3, continúa con los componentes RGBA del segundo pixel en las posiciones 4, 5, 6 y 7, y así sucesivamente. En nuestro caso concreto el componente A (alpha), utilizado para las transparencias, puede ignorarse tranquilamente, ya que no tiene sentido considerarlo para las imágenes típicas obtenidas de una webcam.

En la práctica, el proceso de conversión suele adquirir un aspecto similar al siguiente:

dst[j] = src[i] * 0.299 + src[i + 1] * 0.587 + src[i + 2] * 0.114;

Aunque es muy sencillo, hay un par de cosas a considerar. El primero es que no necesitamos realmente generar una nueva imagen con todos sus componentes RGBA, ya que no es algo que se vaya a mostrar por pantalla, excepto quizás para labores de depuración. Sólo necesitamos un componente de los cuatro, por lo que la cantidad de información a procesar se reduce al 25% de su tamaño original. El segundo punto a considerar es que este proceso hay que realizarlo para cada imagen, y que será más lento cuanto mayor sea la imagen. Una posible solución es utilizar imágenes más pequeñas a las originales proporcionadas por la webcam. Otras soluciones a estudiar son tratar de optimizar el cálculo precalculando los productos en una tabla, o incluso ejecutarlo mediante un shader utilizando WebGL. Pero hablar de estas cosas en este punto es cometer un error de "optimización temprana".

Desenfoque (Gaussian Blur)
Gaussian BlurEste segundo proceso, el de desenfoque utilizando un filtro gaussiano, es otro clásico. Buscando información me encontré una página que me gustó mucho por la gran cantidad de técnicas y efectos que aborda, y lo bien que están expuestos. Con un particular sentido del humor además.

Aplicar un filtro sobre una imagen normalmente consiste en recorrer todos los pixels de la imagen, y para cada pixel de forma individual aplicar una operación que genere un nuevo valor para el pixel. En nuestro caso concreto, para conseguir difuminar la imagen de forma coherente, lo que se utiliza como base para calcular el nuevo valor para cada pixel son los pixels más cercanos que tiene a su alrededor. Es decir, si tenemos un pixel negro rodeado de pixels blancos, lo que se quiere obtener es un nuevo pixel gris que difumine la imagen, eliminando ese "ruido" que representa el pixel negro aislado.

El proceso consiste es definir un tamaño de ventana, por ejemplo de 3x3 pixels, a cada celda de esta ventana asignarle un coeficiente numérico, y mover la ventana por encima de cada pixel de la imagen original de forma individual, multiplicando los coeficientes de la ventana por los valores de los pixels que cubre cada una de las celdas.

Lógicamente la gracia de todo esto está en los coeficientes que se utilicen. Para una ventana de 3x3 (= 9 celdas), si se utilizara un valor de 1/9 en cada celda se obtendría una nueva imagen donde cada pixel sería la media ponderada de todos sus pixels vecinos inmediatos (incluido el mismo). No obstante, parece lógico pensar que unos mejores coeficientes serían aquellos que dieran más importancia al pixel original, y fueran decrementado la importancia a medida que se fueran alejando de él. Y eso es precisamente lo que persigue el "Gaussian Blur", lo que consigue usando unos coeficientes que se calculan con la siguiente fórmula:

(1 / (2 * PI * sigma^2) ) * e^( -(x^2 + y^2) / (2 * sigma^2) )

Donde x e y son la distancia al pixel original, y sigma la desviación típica de la distribución gaussiana.

¿Asustado? ¡Bienvenido al club! No obstante, en la práctica resulta que no hay por que preocuparse por entender nada de esto. Como ya comenté en el artículo anterior, estoy siguiendo el código de ArUco para tratar de portarlo a JavaScript, y para obtener los coeficientes de la ventana, que técnicamente recibe el nombre de "kernel", se utiliza la función getGaussianKernel de OpenCV. Mirando en la documentación y el código fuente se ve que en realidad implementa una fórmula un poco distinta a la original, y que además, para ventanas de tamaño 3x3, 5x5 y 7x7 tiene unos valores precalculados.

Como ArUco utiliza una ventana fija de 7x7, entonces siempre utiliza los mismos coeficientes:

[0.03125, 0.109375, 0.21875, 0.28125, 0.21875, 0.109375, 0.03125]

De igual forma que en el proceso de conversión a escala de grises, se verifica que la suma de los coeficientes es igual a 1. Y como se observa los coeficientes centrales tienen mucho más peso que los de los extremos. Y aunque sólo he puesto una fila, en la práctica ha de verse como una matriz de 7x7 con los coeficientes distribuidos de manera uniforme alrededor del elemento central. Pero como se verá inmediatamente, el resto de coeficientes no son importantes.

Implementar el filtro resulta sencillo, pero muy lento, ya que por cada pixel hay que realizar 49 (= 7*7) multiplicaciones. No obstante, el filtro tiene una característica particular. Es un filtro "separable", lo que quiere decir que se puede aplicar en un primer paso en horizontal, multiplicando cada pixel sólo por la fila central de la ventana, y al resultado de ese primer paso aplicarle el filtro en vertical, multiplicando cada pixel nuevamente sólo por la fila central. De esta forma se reduce a 14 (= 7*2) multiplicaciones por pixel. Lo que de todas formas sigue siendo bastante trabajo para JavaScript dependiendo del tamaño de la imagen que se utilice. Sería interesante en un futuro probar con otro tipo de filtros, e incluso tratar de implementarlo en un shader mediante WebGL.

Por último, comentar que el filtro plantea un problema de implementación en los bordes, donde la ventana abarca pixels que no existen, y que se ha resuelto duplicando los pixels de los bordes para cubrir la ventana. Aunque existen otras estrategias posibles.

Actualizado 19/03/2012: Actualmente js-aruco implementa un Stack Box Blur que resulta más eficiente que el Gaussian Blur.

Realidad Aumentada
1. Introducción
2. Escala de grises (Grayscale & Gaussian Blur)
3. Umbralización (Adaptive Thresholding)
4. Detección de contornos (Suzuki)
5. Aproximación a polígonos (Douglas-Peucker)
6. Transformación de perspectiva (Homography & Otsu)
7. Detección de marcadores
8. js-aruco: Realidad Aumentada en JavaScript