Chrome

Juan Mellado, 23 Mayo, 2011 - 18:04

Realidad AumentadaLas aplicaciones de Realidad Aumentada se han convertido en algo corriente hoy en día, sobre todo por el hecho de que prácticamente todos los dispositivos electrónicos que salen al mercado tienen algún tipo de cámara y cierta capacidad de proceso. Las demostraciones con esta tecnología suelen ser muy llamativas, y hacía tiempo que me picaba la curiosidad por conocer el detalle de la cadena completa de pasos concretos que se habían de seguir para hacerlas funcionar.

Al final he dedicado estas últimas semanas a leer un montón de documentación, mirar bastante código, y he acabado desarrollando una pequeña librería en JavaScript que casi implementa un sistema de Realidad Aumentada completo. Y digo "casi" porque me he encontrado con dos problemas que he dejado abiertos para resolverlos más adelante, el primero por una cuestión de índole puramente técnica, y el segundo por falta de talento. Pero vayamos por partes.

Me he centrado en la idea de averiguar como funciona un sistema ya implementado, en vez de estar reinventado la rueda. Quería que no fuese un sistema muy grande, ya que a medida que las aplicaciones empiezan a crecer puede resultar difícil entender su filosofía de funcionamiento, sobre todo cuando no se ha trabajado en la elaboración de las mismas. De hecho, a mi a veces me gusta descargarme las versiones más antiguas de los repositorios públicos en vez de las más recientes.

Otro requisito que quería que cumpliese el sistema es que utilizara los clásicos "marcadores", que son esas tarjetas tan características que llevan dibujadas algún motivo en blanco y negro. Y aunque por lo que he podido leer hay bastante interés en la Realidad Aumentada sin marcadores, a mi eso de las "tarjetitas" me llamó mucho la atención en su día y era algo que antes o después sabía que acabaría abordando, y esta era mi oportunidad.

ArUcoFinalmente he optado por ArUco, una librería bastante pequeña y con un código bastante fácil de seguir, ya que prácticamente todo el grueso del proceso está desarrollado en una única función. Un código con un estilo muy "académico" en realidad, y yo me entiendo cuando digo esto. Como curiosidad, comentar que es un desarrollo del grupo de investigación "Aplicaciones de la Visión Artificial" (AVA) de la Universidad de Córdoba (UCO). De aquí al lado, vamos. [La imagen está cogida de su web]

La librería es de código abierto, bajo licencia BSD, y está escrita originalmente en C++ apoyándose en OpenCV, una librería esta última con mucha solera y toda una referencia dentro del mundo de los desarrollos de todo tipo de aplicaciones de visión artificial. Después de haberme pasado unas cuantas horas buceando por su código he llegado a apreciar la cantidad enorme de trabajo que han debido invertir en ella.

Lo que más me enganchó de ArUco fue que entendí bastante bien la sencilla descripción que dan en la web acerca del funcionamiento de la misma. Sobre todo acerca del proceso de detección de los marcadores. Es la parte más "algorítmica", así que supongo que por eso me sentí más cómodo con ella y me animó a ir implementando paso a paso mi propia versión de la librería.

A grandes rasgos, he acabado dividiendo el proceso en cuatro bloques:

1) Captura de vídeo
Estoy trabajando con un PC de sobremesa, y lo lógico sería capturar vídeo desde una webcam, pero resulta que a día de hoy eso es algo que no se puede hacer de forma nativa en un navegador utilizando única y exclusivamente JavaScript. Aunque se puede hacer desde Flash, por ejemplo. Y de hecho, una de las librerías más populares para la creación de aplicaciones de Realidad Aumentada es una conversión a Flash de otra librería escrita originalmente en C.

Según he podido averiguar, dentro del estándar HTML5 están trabajando en exponer la función "getUserMedia" en JavaScript, que dará acceso a la webcam y cualquier otro tipo de dispositivo de vídeo o audio conectado al PC (tras la correspondiente autorización por parte del usuario). Pero todavía falta un tiempo para que los navegadores la implementen, así que he dejado aparcado de momento este tema del vídeo y me he centrado en procesar imágenes estáticas individuales.

2) Extracción de candidatos
Esta parte es sobre la que más tiempo he invertido. Para explicarla en pocas palabras bastaría con decir que consiste en analizar una imagen a la busca de cuadriláteros. Para explicarla con un poco más de detalle hay que explayarse en el cómo y porqué se realizan los siguientes procesos:
- Conversión a escala de grises (Grayscale)
- Eliminación de ruidos (Gaussian Blur)
- Umbralización (Adaptive Thresholding)
- Extracción de contornos (Suzuki)
- Aproximación a polígonos (Douglas-Peucker)
- Transformación de perspectiva (Homography)
- Umbralización (Otsu)

Mi idea es detallar estos pasos en artículos posteriores, sobre todo para que me sirvan como recordatorio a mi mismo.

3) Identificación de marcadores
Un vez extraídos una serie de cuadriláteros candidatos hay que averiguar si alguno de ellos es un marcador. Para ello se comprueba uno a uno si contienen una imagen válida reconocible como marcador.

En el caso de ArUco, no se utiliza una imagen libre cualquiera, sino un código binario dibujado en forma de una matriz de cuadrados de 7x7. Un 1 se representa con un cuadrado negro y un 0 con un cuadrado blanco. Intuitivamente debería resultar evidente que este tipo de códigos son más fáciles de identificar que una imagen libre cualquiera, además de que permiten añadir de una forma bastante natural bits de paridad para la comprobación de errores. De hecho, ArUco trata los marcadores que es capaz de identificar como un código Hamming, aunque bastante modificado para sus propósitos concretos.

Una vez entendida esta parte no me ha llamado tanto la atención, y he hecho un "port" casi directo del original a JavaScript. De hecho, cuando haga una limpieza de mi código, me gustaría tratar este proceso de forma independiente, como una función que se pase como parámetro, que admita un cuadrilátero candidato, y que decida si lo reconoce o no como marcador.

4) Traslación a tres dimensiones
Una vez identificado un marcador, lo más normal es calcular a continuación la posición que ocupa en el espacio con respecto a la cámara. O lo que es igual, la posición de la cámara con respecto al marcador. De esta forma se puede hacer eso tan característico de dibujar un modelo 3D sobre el marcador, consiguiendo además que se gire, acerque o aleje según se mueva el marcado o la cámara.

El problema es que esto no es algo inmediato. De hecho, el cálculo a realizar depende de las características físicas concretas de la cámara que se esté utilizando, pues hay toda una serie de parámetros intrínsecos como son el centro óptico real del sensor, las distancias focales en cada de unos de los ejes, y los factores de distorsión radial. Y esos parámetros, o se conocen, o es necesario obligar al usuario a que los obtenga de antemano de forma manual mediante algún programa que implemente un proceso de calibración.

Yo me había hecho la idea de que esto era más automático, pero parece que no. Esto de los parámetros y el proceso de calibración me ha matado bastante. Y de hecho no tengo ningún reparo es decir que además toda la matemática implicada ha conseguido liarme y no he conseguido sacar nada en claro. Se ha convertido en mi particular "pons asinorum".

Después de rebuscar entre un montón de documentación y unas cuantas implementaciones he decidido que este problema es lo bastante grande por si mismo para mi como para sacarlo aparte y tratarlo como una "mini-librería" con entidad propia. Trataré de retomarlo más adelante.

Para terminar, me gustaría dejar que claro que lo que describo en esta serie de artículos es una forma concreta de implementar las bases de un sistema de Realidad Aumentada. Pero no es ni mucho menos la única forma de hacerlo, ni probablemente la más eficiente. ArUco es un desarrollo totalmente ajeno a mi, pero cualquier error o imprecisión sobre ella en estos artículos son sólo atribuibles a mi persona.

Actualizado 19/03/2012: Actualmente js-aruco implementa un Coplanar POSIT que permite obtener la pose de los marcadores en tres dimensiones a partir de sus proyecciones en dos dimensiones.

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, 23 Abril, 2011 - 12:19

Sigo analizando el rendimiento de js-openctm y tratando de ver donde puedo recortar un poco de tiempo de proceso. Después de realizar las optimizaciones obvias para reducir la cantidad y complejidad del código que se ejecuta dentro de los bucles más largos, he llegado al punto en que no encuentro forma de ganar una forma substancial de ciclos de reloj sólo y exclusivamente a base de realizar cambios en el código. Y es que definitivamente: ¡necesito un JavaScript ninja en mi vida!

El verdadero caballo de batalla es sin duda el proceso de descompresión, pero eso es harina de otro costal. En lo que me estoy centrado es en las funciones que tardan más, y más concretamente en la que se encarga de restaurar las normales. Si está leyendo este blog he de suponer que sabe lo que es una normal, pero por si las dudas, una imagen vale más que mil palabras. O al menos eso dicen.

WebGL - Drawing normals

En la primera imagen puede verse un render del dragón de Standford que he hecho dibujando las normales en cada vértice. Las normales son vectores que salen perpendiculares a la superficie, por lo que parece como si al modelo le hubiese salido pelo. En la segunda imagen he puesto una ampliación de la cola, que parece un cactus.

WebGL - Drawing normalsEl problema con las normales en OpenCTM es que resulta muy costoso restaurarlas, hay que hacer un montón de raíces cuadradas para calcular longitudes y normalizar vectores, y la función Math.sqrt es una total y absoluta "JavaScript perfomance killer". Sobre todo para modelos con millones de polígonos.

Además, analizando más en detalle el proceso. Resulta que hay algunas operaciones un poco discutibles. Por ejemplo, para restaurar las normales que vienen dentro de un fichero, el primer paso que se realiza es: ¡calcular las normales!. A ver si me explico. En el fichero vienen unas normales, pero no son las definitivas, sino que están almacenadas de forma relativa a las normales "nominales" del modelo. Así que para restaurarlas, primero hay que calcular esas normales "nominales". Siendo la normal "nominal" de un vértice la suma de todas las normales de las caras que comparten dicho vértice. Es decir, ¡las normales tal y como se han calculado toda la vida!.

La pregunta del millón es: si de todas formas se tienen que calcular las normales, ¿para qué queremos las del fichero? Pues la única explicación es que las normales que vengan en un fichero no tienen porque ser las mismas que las calculadas de la forma habitual. Para verificar este punto he tenido que ir depurando paso a paso un fichero concreto de ejemplo (en formato MG2, que no tiene porque almacenar con una precisión 1:1) y viendo los valores que obtenía por un procedimiento y otro. Y efectivamente, se obtienen valores distintos.

Por lo que a mi respecta, para mis propósitos concretos, no tiene sentido almacenar las normales en los ficheros. Sólo sirve para aumentar el tamaño de los ficheros y el tiempo necesario para descomprimirlos y procesarlos. Es mucho más rápido calcular las normales en el cliente. Además, el proceso que utiliza OpenCTM no es del todo eficiente. En un primer bucle calcula las normales que comparten un mismo vértice. Y en un segundo bucle las normaliza dividiéndolas por su longitud (raíz cuadrada al canto). El problema es que en el primer bucle también normaliza (otra raíz cuadrada al canto), cuando esto no es estricta y necesariamente necesario hacerlo. Y para rematar la faena, el proceso de restauración posterior implica realizar una nueva raíz cuadrada para cada normal.

Analizando lo que hace el proceso de restauración he conseguido reordenar el código para hacerlo más eficiente, detectando algunos casos especiales que he podido aislar en su propio flujo de ejecución de forma independiente. Un 30% de reducción de tiempo de proceso en general, que no está nada mal. No obstante, el cuello de botella sigue siendo el cálculo de las normales "nominales", que además no puedo modificar, ya que si lo hago se producen desviaciones con respecto a los valores que obtiene el SDK.

Así que al final, lo dicho: "No guardar las normales en el fichero, es mejor calcularlas online".

Juan Mellado, 21 Abril, 2011 - 18:00

WebGL tiene una limitación en la función DrawElements por la que sólo se pueden utilizar buffers de 8 o 16 bits para los índices. Lo que implica que es necesario cortar las mallas con muchos vértices para poder representarlas. Ya tenía noticias de esta limitación, pero la verdad es que hasta ahora no me había importado demasiado. Me ha empezado a dar problemas en unas pruebas que estoy haciendo con js-openctm y ficheros con mallas muy densas.

WebGL - Split mesh Estoy haciendo pruebas con mallas de más de 1 millón de triángulos, y el problema es que cuando los índices superan el límite de 65.535 ya no se representan correctamente. La solución obvia es dividir la lista de índices en varias sublistas, ajustar los valores de las sublistas al rango 0-65.535, y realizar una llamada a DrawElements para cada sublista en vez de una sola con la lista original.

En la primera imagen de las tres que acompañan este post se puede ver el famoso "Happy Buda" de Standford, con 1.087.716 triángulos para ser exactos, tal cual lo estoy renderizando con WebGL en el navegador, y justo a su lado el mismo modelo, pero con un color distinto aplicado a cada una de las submallas que he tenido que generar para poder representarlo.

Cambiar la lista de índices originales no me parece algo trivial, ya que puede implicar tener que reorganizar los vértices, normales, y todos los demás atributos de la malla, con el consiguiente gasto de tiempo y reserva de memoria intermedia. E incluso en el peor de los casos puede que sea necesario duplicar vértices, ya que pueden darse situaciones en las que un triángulo tenga un vértice al principio de la lista y otro al final, y duplicar sea la solución más efectiva.

WebGL - Split meshMirando algunas implementaciones por ahí, he visto que algunos optan por cortar a saco, sin mucho miramiento, sin tener en cuenta los casos especiales y, para mi sorpresa, ¡les funciona!. El truco está en aprovechar la "coherencia" espacial de los modelos, en la distribución que normalmente tienen los triángulos dentro de la malla.

En la segunda imagen, con el Buda de perfil, se aprecia claramente porque no hay ningún problema en cortar la lista sin prestar atención a nada más para este modelo en particular. Todas las submallas contienen triángulos que están conectados unos con otros dentro de regiones muy claramente acotadas del espacio. En este caso, como los cortes de un sandwich helado.

Con los modelos propios, o con los que se puede suponer como estará organizada la malla, se pueden tomar este tipo de decisiones tan drásticas. Pero si se intenta hacer un visor genérico entonces si que sería conveniente buscar la forma correcta de hacer las subdivisiones.

Un hombre sabio dijo una vez que "los algoritmos son para la gente que no sabe comprar módulos de memoria", y yo no tengo palabras para explicar cuanta verdad encuentro en ello. Bueno, vale, la verdad es que eso de hacer algoritmos se me da muy mal y esa frase me sirve de consuelo. Incluso en esta era de Internet en la que se puede encontrar todo tipo de papers y código, me cuesta elaborar un algoritmo que me deje satisfecho. Y lo que es peor, que deje "satisfecho" al problema.

WebGL - Split meshAl final, he decidido seguir la corriente y olvidarme de los casos difíciles y cortar la malla con un sencillo procedimiento que no consume apenas tiempo y evita tener que reservar memoria adicional ni mover cosas de un lado a otro. Básicamente lo que hago es recorrer secuencialmente la lista de índices buscando un mínimo y un máximo, cuando la diferencia entre esos dos valores es mayor que 65.535 entonces guardo la posición en la que empecé a buscar, el número de elementos que llevo recorridos, el mínimo encontrado, y vuelvo a empezar la búsqueda desde el punto en que me encuentro repitiendo este sencillo proceso hasta haber recorrido toda la lista.

Al final lo que obtengo como salida del proceso anterior es un array con tres valores para cada una de las submallas. A saber, la posición del primer índice de la submalla, el número de índices de la submalla, y el valor a restar a cada índice de la submalla para dejarlos en el rango 0-65.535. El valor a restar evidentemente es ese valor mínimo encontrado en cada iteración para cada submalla.

De esta manera se puede seguir realizando una única llamada a createBuffer para crear cada uno de los tipos de buffers (índices, vértices, normales, ...), como hasta ahora. Y lo que cambia es que se debe realizar una llamada a bindBuffer/vertexAttribPointer/drawElements para cada submalla, indicando en vertexAttribPointer un offset que apunte a ese valor mínimo encontrado para cada submalla.

En la tercera imagen se puede ver un modelo con 1.448.269 triángulos, sin textura, sólo colores por vértice, creado por la empresa Cyberware con el detalle de las submallas. Como se observa, el algoritmo propuesto también funciona con este modelo por el mismo motivo que el anterior, pero para otro tipo de disposición de mallas no está garantizado que vaya a hacerlo.

Juan Mellado, 19 Abril, 2011 - 18:50

Esto de hacer en JavaScript lo que toda la vida se ha hecho en C hace que uno se relaje y se le olviden los problemas clásicos. ¡Pero siguen estando ahí! Tengo que recordarme que un byte sigue siendo un byte, que un bit sigue siendo un bit, y que el orden que ocupan cada uno de ellos es importante.

Todo esto viene a cuenta de que he notado que js-openctm no era endianness safe. O sea, que sólo la he probado en mi máquina, que es little endian, y estoy casi seguro que no iba a funcionar en arquitecturas big endian.

Las especificaciones del formato OpenCTM dicen que los datos se almacenan entrelazados a nivel de byte, de forma que la secuencia:


a1 b1 c1 d1  a2 b2 c2 d2  ...  aN bN cN dN


Se almacena como:

a1 a2 ... aN  b1 b2 ... bN  c1 c2 ... cN  d1 d2 ... dN

Donde a, b, c y d son los cuatro bytes de una cantidad de 32 bits. Siendo a el byte más significativo (esto último no lo dice la documentación).

Revisando el código original del SDK de OpenCTM veo que reserva memoria para un buffer temporal, recupera todos los bytes del fichero, los recorre convirtiéndolos a los valores definitivos (instanciando un int o un float) y finalmente los vuelca en el buffer definitivo. Por su parte, en js-openctm, lo que se hace es poner directamente los bytes en su posición final dentro del buffer definitivo, evitando la reserva de memoria y los pasos intermedios.

El problema está en que en las arquitecturas big endian el primer byte a emitir al buffer definitivo deber el más significativo (a), mientras que la librería está emitiendo siempre el menos significativo (d) como corresponde a una máquina little endian, como la mía.

¿Solución? Comprobar el endianness de la máquina sobre la que se está ejecutando la librería con la típica función de toda la vida:

CTM.isLittleEndian = (function(){
  var buffer = new ArrayBuffer(2),
      bytes = new Uint8Array(buffer),
      ints = new Uint16Array(buffer);

  bytes[0] = 1;

  return ints[0] === 1;
}());

La función reserva un buffer de 2 bytes e instancia dos vistas sobre él. Una vista de byte y otra de entero de 16 bits. En la vista de byte se escribe un 1 en la posición 0. Y a continuación se comprueba si la vista de entero devuelve un 1. Si la máquina es little endian debe devolver un 1 (0x0001), si la máquina es big endian debe devolver un 256 (0x0100).

Con esta función, que sólo se evalúa una vez al principio, ya se puede decidir el orden correcto con el que se tienen gestionar los bytes, y la librería debería pasar a ser endianness safe, aunque me sigue faltando ejecutarla sobre una máquina big endian para comprobarlo.

Juan Mellado, 18 Abril, 2011 - 18:16

El primer intento de análisis del rendimiento de js-lzma ha ido bastante bien. El cambio de una única línea de código ha disparado el rendimiento de una forma brutal. No me lo esperaba, y me ha dado bastante que pensar. Pero vayamos por partes.

Lo primero ha sido coger un fichero bastante grande para forzar que la librería ejecutara un ciclo de trabajo grande y poder analizarlo, ya que con los ciclos muy cortos apenas se puede sacar conclusiones. Chrome tiene integradas una serie de herramientas para desarrolladores bastante útiles para medir el rendimiento, y yo particularmente me he centrado en los resultados de las pestañas "Profiles" y "Timeline".

Chrome tools

En la tabla de la izquierda se ve como se distribuye el tiempo empleado durante la ejecución del programa. Y está claro que hay algo que no funciona bien, ya que prácticamente el 86% del tiempo el navegador está ocupado lanzando el Garbage Collector (GC). Algo que corrobora además la gráfica de la derecha, que muestra claramente como cada pocos milisegundos está saltando el GC, consumiendo prácticamente todo el tiempo de proceso.

Inmediatamente me ha venido a la cabeza algo que leí hace un tiempo sobre los Arrays en JavaScript. (La verdad es que no sé como lo he asociado tan pronto, mi cerebro debió registrarlo en su momento como algo crítico y a tener muy en cuenta.) He abierto el código y cambiado la siguiente línea:

_buffer = new Array(windowSize);

Por esta otra:

_buffer = [];

La diferencia de un cambio tan pequeño se aprecia claramente en la tabla de la izquierda de la siguiente imagen, donde el tiempo del GC se reduce drasticamente hasta un 6%.

Chrome tools

Esta claro que sigue siendo un valor muy alto, y en la gráfica de la derecha se ve como de todas formas el GC sigue saltando muy de continuo, pero la mejora de rendimiento es sencillamente brutal.

Técnicamente son dos formas distintas de crear un array, la primera creando una instancia de la clase Array a través de new, y la segunda creando un array mediante la notación literal. La diferencia es que la máquina virtual del navegador hace un mejor trabajo con el objeto literal a la hora de gestionar el acceso a sus elementos. Es un "tip" bastante conocido y hay mucha información sobre esto en Internet. Lo que no me esperaba es que la diferencia de tiempos fuera a ser tan brutal. Hay más sentencias como esa en el código, pero ninguna de ellas supone una mejora significativa, aunque pretendo cambiarlas todas.

Me ha dejado un tanto preocupado la cantidad de veces que salta el GC. Y me ha hecho suponer/temer que parte de mi trabajo a partir de ahora consistirá en tratar de que no salte tan a menudo. Se supone que debería poder sacar alguna conclusión haciendo un "heap snapshot" desde el propio Chrome, pero la verdad es que no me he enterado de mucho. Tengo que mirarlo con más calma.