HTML5

Juan Mellado, 13 Junio, 2011 - 11:03

Tenía pendiente hacer una prueba en la nueva versión de Firefox para comparar el rendimiento de js-openctm con respecto a Chrome, y la verdad es que el resultado ha sido bastante decepcionante. Firefox tarda del orden de cuatro veces más con los modelos grandes (1 millón y medio de polígonos). Y lo que es peor, aún no tiene implementado antialias. En la imagen puede verse un modelo renderizado con WebGL en Chrome (izquierda) y Firefox (derecha).

WebGL - Antialias

Los característicos "dientes de sierra" que aparecen debido a la falta de antialias son bastante evidentes en el render de Firefox, aun cuando se supone que debería estar activado por defecto según se indica en la especificaciones de WebGL.

He tratado de activarlo por software, a través de los "hints" que se le pueden pasar como parámetro a la hora de obtener el contexto, pero no ha servido para nada.

canvas.getContext("webgl", {antialias:true});

Buscando por Internet me he encontrado una respuesta del equipo de Firefox a este comportamiento. Y viene a decir que realmente lo del antialias no es obligatorio, sólo eso, un "hint". Que por ahora no lo tienen implementado, y que no les parece prioritario.

Lo que si funciona es decirle a Chrome que desactive el antialias para que se vea igual de mal que en Firefox. Aunque no resulta de mucha utilidad, sólo para constatar que tiene implementada la gestión del antialias.

Juan Mellado, 11 Junio, 2011 - 14:30

Después de unas cortas, pero merecidas vacaciones, he retomado el proyecto de realidad aumentada para darle los últimos toques finales. En la lista del TODO me quedaron unas cuantas cosas por hacer que creía importante revisar. Al final he conseguido quitarme las más grandes de en medio, aunque alguna de ellas me han dado algún que otro dolor de cabeza.

Memoria
Lo primero era disminuir la reserva de memoria dinámica y reutilizar buffers. Esto ha sido sencillo, ha bastado con hacer una única reserva de memoria al principio, y luego reutilizar esa misma memoria reservada una y otra vez. La sorpresa desagradable vino cuando me fijé en que el monitor de memoria de Chrome me detectaba un "memory leak" enorme.

Chrome - Memory leak

Como se observa en la primera imagen, la memoria empieza con unos valores iniciales aceptables. No obstante, el problema viene cuando a partir de ahí la memoria reservada no hace más que crecer y crecer, hasta que al alcanzar el límite de 2GB se cuelga la pestaña del navegador. Un error que ya había detectado antes, y que me tenía algo mosqueado.

Chrome - Memory leak

En la segunda imagen se ve la memoria a punto de alcanzar el máximo y provocar que el proceso aborte. No obstante, en esa imagen hay algo aún más importante en lo que fijarse. Y es en el hecho de que la memoria reservada por JavaScript y Flash sigue siendo del mismo orden de magnitud que al principio. La buena noticia es que todo apunta a que el problema no lo está generando el programa, ya que ni JavaScript ni Flash aparentan ser los culpables. Y la mala es que entonces surge la duda: ¿quién diablos está reservando toda esa memoria?

Después de revisar todo una y otra vez, al final me he dado cuenta de que la memoria sólo crece de esa forma cuando tengo abierta la ventana de depuración de Chrome. O sea, que el problema es del navegador, no mía (\o/). Cuando tengo abierta la ventana de depuración (lo que en mi caso es prácticamente el 100% de las veces) la memoria no hace más que crecer y crecer. Pero cuando la tengo cerrada, haciendo una navegación normal, la memoria mantiene sus valores iniciales. ¡Aclarado el misterio!

Rendimiento
El otro gran tema pendiente era el rendimiento de la librería. Y la única forma de sacar conclusiones a este respecto era tomar tiempos.

Chrome - PerformanceEn la imagen de la izquierda puede verse los tiempos de ejecución para cada iteración de la librería. Es decir, cada vez que analiza un fotograma a la búsqueda de marcadores. Como se observa, los tiempos eran bastante estables (una característica de ejecución que he observado en Chrome). Pero eso sí, lamentables.

Mi webcam, la más barata que encontré, es capaz de tomar imágenes a un ritmo de 15 fotogramas por segundo. Lo que da un tiempo de proceso de unos 67 (= 1000 / 15) milisegundos entre un fotograma y otro, mientras que librería estaba tardando 300 milisegundos por fotograma. La buena noticia es que al desplegar el detalle de los tiempos se observaba que en realidad el proceso de detección de marcadores apenas demoraba 40 milisegundos. Así que volvía a surgir una nueva pregunta: ¿en qué se estaba yendo el resto del tiempo?

Pues resulta que todo el tiempo se consume en enviar los fotogramas desde Flash a JavaScript. Y por desgracia estoy obligado a utilizar Flash para capturar el vídeo, ya que todavía no puede hacer directamente desde JavaScript. Resulta que el paso de información entre Flash y JavaScript es bastante lento en general por culpa del proceso de serialización. Cuando implementé la librería de captura de vídeo en Flash me limité a guardar la imagen capturada en un Array y pasárselo a JavaScript, pero eso a la larga ha resultado ser muy sencillo de implementar pero muy poco eficiente.

Chrome - PerformanceEn la imagen de la izquierda puede verse los nuevos tiempos después de una serie de optimizaciones, como la de reserva de memoria inicial indicada anteriormente. Como se observa, el tiempo de proceso en cada iteración cae hasta los 100 milisegundos, todavía alejados de los 67 objetivos, aún cuando el tiempo de proceso de la librería ahora se encuentra alrededor de los 25 milisegundos.

Para acelerar el proceso de transferencia de datos entre Flash y JavaScript he realizado un montón de pruebas. Al final, la mejor implementación que he conseguido realizar, en cuanto a rendimiento, ha consistido en convertir todos los pixels de la imagen a cadena de caracteres y concatenarlos en un String separados por comas. Muy tosco, pero efectivo. Para disminuir el tamaño de la cadena de caracteres lo que he hecho es enviar la diferencia de un pixel con respecto al anterior, ya que normalmente tienden a parecerse. Y para reducir un poco más el número de caracteres los he codificado en base 36. Esto último puede sonar raro, pero es que esa es la mayor conversión de base que realizan de forma nativa tanto como Flash como JavaScript. De esta forma he encontrado un equilibrio entre la cantidad de información a intercambiar y el tiempo necesario para procesarla. He subido la clase ActionScript en un nuevo proyecto que he creado llamado flashcam.

Por último, y entrando un poco más en detalle acerca de los tiempos de proceso de la librería, la función que más tarda con diferencia es la que realiza el filtro gaussiano, ya que ella sola se lleva el 75% del tiempo de ejecución. Curioso que al final una función "auxiliar" sea la que más tiempo tarde. Habrá que buscarle una alternativa.

Juan Mellado, 30 Mayo, 2011 - 07:37

He subido a un repositorio público todo el código JavaScript que he ido generando estos últimos días resultado de portar ArUco, una librería para la construcción de aplicaciones de realidad aumentada escrita en C++ utilizando OpenCV. He llamado js-aruco al proyecto, espero que el nombre no me cause problemas, pero me parecía el más adecuado.

En contra de mi costumbre, he creado una pequeña demo, que tiene la particularidad de que es capaz de obtener imágenes de una webcam a través de una pequeña librería que he escrito en Flash, y que es capaz de capturar vídeo y enviar las imágenes a JavaScript. La demo requiere un ordenador bastante rápido, un navegador moderno actualizado (Chrome o Firefox), Flash para la captura de vídeo, y una webcam.

js-aruco

Demo online:
http://inmensia.com/files/aruco/webcam/webcam.html

La demo detecta los marcadores y dibuja un borde rojo alrededor de los mismos, muestra en azul los números identificadores de cada uno de ellos, y destaca las esquinas superiores izquierda con un pequeño cuadro verde para poder hacer un seguimiento de su orientación real con respecto a la cámara.

Los marcadores deben ser matrices de 7x7, con un borde negro de 1 celda de ancho. La matriz más interna de 5x5 puede tener filas con cualquiera de las siguiente combinaciones válidas:
blanco - negro - negro - negro - negro
blanco - negro - blanco - blanco - blanco
negro - blanco - negro - negro - blanco
negro - blanco - blanco - blanco - negro

TODO
- Optimizar. Para capturar imágenes a un mínimo de 20 fps se requiere ser capaz de procesar cada imagen en tan sólo 50 (= 1000/20) milisegundos, algo bastante alejado del rendimiento actual de la librería, incluso para resoluciones pequeñas de 320x240. [Solucionado]
- Reducir el uso de memoria. Hay unas cuantas funciones que reservan memoria que luego no reutilizan ya que vuelven a hacer la misma reserva para cada imagen procesada. [Solucionado]
- Implementar interpolación bilineal en el warp. En ángulos en torno a los 45 grados, para imágenes pequeñas, no se están detectando a veces los marcadores debido a que se forman "dientes de sierra" en la imagen que provocan que falle la cuenta de pixels para diferenciar los cuadrados blancos de los negros. [Implementado]
- Después de varios minutos de funcionamiento la ventana del navegador da un error, aunque aún no sé si porque falla Flash o JavaScript. Posiblemente sea porque falla el mecanismo que he puesto para intercambiar datos entre Flash y JavaScript, o porque el proceso se queda sin memoria. [Solucionado]
- Sustituir Flash por la futura función JavaScript "getUserMedia", un estándar que aún se está definiendo y que espero que los navegadores implementen algún día. [Implementado]

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