Stratos

Juan Mellado, 29 Mayo, 2011 - 10:44

El último paso del proceso es tratar de identificar marcadores. Es decir, analizar una a una las imágenes que se han obtenido en el paso anterior, y comprobar si realmente su contenido se corresponde con una matriz reconocible y válida de cuadrados blancos y negros que identifican de forma inequívoca a un marcador.

ArUco utiliza una matriz de cuadrados de dimensiones 7x7 para los marcadores, aunque en realidad sólo utiliza la matriz central de 5x5 para codificarlos, ya que impone que el borde exterior se componga sólo y exclusivamente de cuadrados negros. De igual forma, impone una serie de restricciones sobre las combinaciones válidas de cuadrados por fila mediante el uso de un código Hamming modificado. Lo que básicamente quiere decir que los cuadrados negros se identifican como "0", los cuadrados blancos como "1", y que se tratan como si fueran dígitos binarios (bits).

Los bits se numeran de izquierda a derecha, siendo 0 la primera posición. Los bits 1 y 3 se utilizan para almacenar datos, y los bits 0, 2 y 4 para control de errores. Como sólo hay dos bits para datos, entonces sólo hay 4 (= 2^2) combinaciones válidas por fila. Y como hay cinco filas por marcador, entonces hay un máximo de 1024 (= 4^5) marcadores distintos.

Las combinaciones válidas por fila están prefijadas, y son las siguientes:

[ [1,0,0,0,0], [1,0,1,1,1], [0,1,0,0,1], [0,1,1,1,0] ]

El algoritmo de detección funciona tratando la imagen como si estuviera dividida en una matriz de 7x7, contando el número de pixels con valor 1 en cada una de las celdas de la matriz. Si el número de pixels con valor 1 es mayor que el 50% del tamaño de la celda entonces se considera que la celda representa un bit con valor 1, y con valor 0 en caso contrario.

MarkersUna vez obtenida la secuencia de bits que representa cada fila se comprueba si es correcta. Pero debido a que no se conoce la posición que ocupa la cámara con respecto al marcador, en realidad la comprobación se realiza 4 veces, rotando 90 grados cada vez la matriz de bits encontrados. Si la secuencia de bits es correcta entonces se considera que se ha detectado un marcador, por lo que se obtiene su valor identificador a partir de los bits de datos, y se rotan las esquinas del cuadrilátero para que casen con las rotaciones realizadas a la matriz. En la imagen puede verse los marcadores identificados, rotados para mostrar su orientación real, y con su identificador justo debajo de ellos. Se puede comprobar que el primero de ellos, por ejemplo, tiene un valor 601 en decimal, que se corresponde con el valor 1001011001 en binario, obtenido tomando los bits de datos de las posiciones 1 y 3.

ArUco realiza un paso más después de este, que yo de momento he omitido, consistente en comprobar si se ha identificado más de una vez un mismo marcador, y eliminando el de menor perímetro en ese caso. Con esto trata de resolver un problema que presenta la detección inicial de contornos, que retorna contornos exteriores e interiores, lo que puede provocar que un mismo cuadrilátero se detecte dos veces.

¡Y eso es prácticamente todo! Una vez identificados los marcadores sólo resta aplicar un poco de imaginación para "aumentar la realidad".

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, 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