inmensia |
Stratos
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) 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) 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
Juan Mellado, 23 Mayo, 2011 - 18:04
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.
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 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 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 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 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
Juan Mellado, 16 Abril, 2011 - 06:43
La idea de implementar esta librería nació a raíz de unas pruebas que estuve haciendo con WebGL. Me surgió la necesidad de leer un modelo 3D de un fichero, y buscando información acerca de los distintos formatos me topé con este OpenCTM. Me llamó la atención el SDK, así como las herramientas de visualización y conversión que tiene implementadas, y me pareció un reto interesante intentar portar partes del SDK, escrito originalmente en C, a JavaScript. El formato OpenCTM está bastante documentado, a excepción de una parte referida a como se empaquetan las normales, pero en líneas generales se puede entender todo sin demasiados problemas leyendo el código fuente y la documentación al mismo tiempo. Su principal característica es que saca partido del conocimiento del dominio para obtener unos ratios de compresión bastantes grandes. Por ejemplo, sabiendo que las mallas se describen con vértices, índices, normales, etc... lo que hace es reordenar dichos componentes para favorecer la compresión de los mismos. Por ejemplo, si se utiliza un entero de 32 bits para los índices, será bastante normal que el byte más significativo sea cero, por lo que es mejor almacenar todos esos bytes de forma consecutiva para obtener una larga cadena de ceros que cualquier compresor puede detectar y almacenar de forma muy eficiente. Y lo mismo para el resto de bytes, ya que si bien inicialmente serán todos ceros, luego pasarán todos a valor uno, luego a dos, y así sucesivamente. De igual forma, si en vez de almacenar los valores tal cual se guardan las diferencias entre ellos, se favorece la compresión, ya que estas representan valores más pequeños y que tienden a ser iguales. OpenCTM define un formato de almacenamiento en binario con tres niveles de compresión llamados "RAW", "MG1" y "MG2". El formato RAW simplemente almacena los distintos componentes de la malla en binario. El formato MG1 reordena, almacena diferencias, y utiliza LZMA para comprimir. Y por último, el formato MG2, además de LZMA, implementa un proceso de empaquetamiento más elaborado para obtener un mayor nivel de compresión. Naturalmente, la ganancia en compresión se paga en el proceso de descompresión, bastante costoso en algunos casos para JavaScript. La librería js-lzma que escribí para descomprimir es bastante lenta en su estado actual, y los cálculos que tiene que realizar js-openctm para restaurar la malla original en algunos casos implica realizar bucles que recorren las listas completas de vértices e indices. ![]() En la imagen que acompaña este post pueden verse los distintos modelos que he utilizado para ir probando la librería, dibujados directamente en el navegador utilizando WebGL. La primera figura es el famoso conejo de Stanford. Sólo índices y vértices ahí, sin ningún tipo de iluminación, de ahí que parezca una imagen 2D cuando en realidad es 3D. La segunda figura es un neumático de Audi, los colores en los vértices aportan algo de profundidad. El símbolo de Audi con los círculos entrelazados en el centro no es una textura, sino que la malla es muy densa. La tercera figura es el dragón de Stanford, la utilicé para probar la carga de normales, por lo que apliqué un shader muy sencillo con una luz que llega desde arriba para comprobar que se cargaban correctamente. La última figura es de una ambulancia con muy pocos polígonos pero con una textura bastante bien elaborada y muy resultona. Me sirvió para probar que las coordenadas de textura se estaban cargando de forma correcta. En cuanto al uso en sí de la librería, está pensada para ser utilizada a partir de ficheros recuperados de la web con XMLHttpRequest de la forma habitual, utilizando el objeto var stream = new CTM.Stream(request.responseText);
Los ficheros .ctm tienen cabecera y cuerpo, y esto es lo que se obtiene en la variable He liberado la librería como código abierto en Google Code. Hay una documentación un poco más detallada en la página del proyecto. El siguiente gran paso sería optimizar el rendimiento de las librerías, lo que representa una buena oportunidad de profundizar en el manejo de las herramientas de "profiling" de Chrome, que es el navegador con el que estoy realizando las pruebas de todas estas tecnologías que siguen siendo bastante experimentales hoy en día.
Juan Mellado, 1 Abril, 2011 - 19:04
Como parte de un proyecto personal en el que estoy trabajando me ha surgido la necesidad de descomprimir desde JavaScript un fichero utilizando LZMA, el algoritmo de compresión utilizado por el popular 7-Zip. Al final he acabado produciendo mi propia versión y publicándola como código abierto bajo el nombre de js-lzma en Google Code. El código es una traducción directa, prácticamente línea por línea, de la versión Java original que se encuentra disponible como parte del LZMA SDK liberado al dominio público por su autor, Igor Pavlov. Lo cierto y verdad es que sólo he codificado la parte correspondiente al algoritmo de descompresión, que es la que me interesaba para mi proyecto. Puede que en un futuro me anime a implementar la compresión, pero a día de hoy no he tomado ninguna decisión al respecto. Dependerá de si continúa mi actual interés por las posibilidades que ofrece JavaScript para el tratamiento de grandes bloques de información binaria, uno de sus muchos caballos de batalla. Bueno, y ahora la parte técnica. Para descomprimir hay que llamar a la función LZMA.decompress(properties, inStream, outStream, outSize);Aunque por cierto, lo de los namespaces en JavaScript es una auténtica locura. Cometí el error de mirarme unos cuantos blogs aquí y allá al azar, en vez de ir directo a la especificación, y al final he acabado más liado de lo que empecé. Al final he utilizado un poco de todo, pero predominando el Revealing Module Pattern, que hace que el aspecto del código final sea bastante parecido al concepto de "clases" de otros lenguajes como Java, lo que era perfecto para mis propósitos. Los parámetros de entrada de la función son: - - - - Los streams de entrada deben ser objetos JavaScript que expongan un función pública llamada var inStream = {Los streams de salida deben ser objetos JavaScript que expongan un función pública llamada var outStream = {Debe quedar claro que en vez de un Array para contener los datos se puede utilizar un String, algún tipo de Typed Array, o lo que se quiera. Por último, notar que a diferencia de la versión original, que admite un tamaño de salida de 64 bits, esta versión en JavaScript limita la salida a 32 bits. Pero no es una limitación de JavaScript verdaderamente, sino que para lo que yo uso la librería me basta y sobra con ese tamaño. ¡Y del rendimiento hablamos otro Nota: Es bastante probable que acabe cambiando la interface pública por una más sencilla (e incompatible con la actual).
Juan Mellado, 1 Marzo, 2011 - 20:06
Aunque prácticamente devorado por las redes sociales, aún sobrevive gracias a los blogs más veteranos y comerciales que lo utilizan para promocionar al máximo sus productos, junto con algunos posts más personales que hacen una breve aparición de vez de en cuando rescatando a sus autores del olvido. En este último año se habló mucho de HTML5 vs Flash, pero Google dijo que Flash era un estándar y se acabó la guerra. Hace pocos días Chrome habilitó WebGL por defecto para el público general, y ahora vendrán las comparaciones con Molehill, el API 3D de Flash. Aunque el IDE de Adobe debería seguir siendo imbatible de momento. Movimientos en su día como el de ActionScript 3 y Flex además consiguieron ganar para su causa un buen puñado de programadores. ¿Para cuando ActionScript 3 con soporte nativo en el navegador? También llegó Kinect, el hack, y Microsoft ya prepara SDK público. Con la Wii también pasó algo parecido, aunque quizás la diferencia es que el mando de este última no daba para tanto en comparación, aunque no faltó quien le sacó provecho, ¡y se fue a trabajar a Microsoft! Con mucho menos acogida por parte del gran público también llegó OnLive. La "nube" amenaza tormenta y a más de uno nos va a pillar sin paraguas. Y además: los portales Flash (y Unity), los juegos de FaceBook, la tienda de Apple (y la de Google), los gadgets con Android (y WP7), los canales indies de las consolas, ... ¿Cuantas versiones eres capaz de hacer un mismo juego? En el panorama nacional, aparte del Mundial de Fútbol, se le hizo mucha publicidad a los señores de Mercury Steam. No obstante, el que entiende de estas cosas dijo en su día que aparte de ellos otro centenar de empresas en España viven de esto de los videojuegos. Y entre el poco más de una decena que se muestran sólidas, alegra v e r a varias de ellas apuntadas al Planet. Y poco más, a soplar velitas y pedir buenos deseos. Gracias a todos los que participáis compartiendo vuestros logros con el resto de los mortales, a los que los leéis haciendo que merezca la pena mantener la página en funcionamiento, y al señor Arteaga por dejarme utilizar el nombre de Stratos. ¡Feliz cumpleaños planetarios! |