Líneas fijas

Resumen

Land Lines es un experimento que te permite explorar imágenes satelitales de Google Earth a través de gestos. Mediante una combinación de aprendizaje automático, optimización de datos y potencia de la tarjeta gráfica, el experimento puede ejecutarse de manera eficiente en el navegador web del teléfono sin necesidad de servidores de backend. Esta es una mirada a nuestro proceso de desarrollo y los diversos enfoques que probamos que nos llevan al resultado final.

https://g.co/LandLines

Cuando el equipo de Data Arts se me acercó para explorar un conjunto de datos de imágenes de la Tierra, me entusiasmó bastante. Las imágenes eran hermosas, revelaban todos los diferentes tipos de estructuras y texturas, tanto hechas por seres humanos como naturales, y me intrigó cómo conectar este conjunto de datos. Hice varios experimentos iniciales en el análisis de la similitud de imágenes y las diferentes formas de filtrarlas y organizarlas.

Diseño de similitud t-sne
Diseño de similitud t-sne, alta resolución, 50 MB

Como grupo, volvimos a revisar las líneas hermosas y dominantes de las imágenes. Fue fácil identificar estas líneas: autopistas, ríos, bordes de montañas y parcelas de tierra, por lo que diseñamos algunos proyectos para explorarlas. Como artista, me inspiró las cosas hermosas que se pueden hacer con colecciones de líneas (por ejemplo, el trabajo de Cassandra C Jones con los relámpagos), y estaba entusiasmado por trabajar con este conjunto de datos.

Detección de línea

Uno de los desafíos iniciales fue cómo detectar líneas en las imágenes. Es fácil tomar un trozo de papel de calco, arrojarlo sobre una impresión de una de estas fotos y dibujar las líneas que ve tu ojo, pero, en general, los algoritmos de visión por computadora para encontrar líneas tienden a no funcionar bien en imágenes muy diversas.

Desarrollé una versión anterior de la búsqueda dibujando el algoritmo en un proyecto con Proyectos locales y, para ello, anotamos a mano las líneas que se deben buscar. Fue divertido dibujar sobre obras de arte, pero tedioso pasar de decenas de imágenes a miles. Quería intentar automatizar el proceso de búsqueda de líneas.

Con estas imágenes aéreas, probé los algoritmos tradicionales de detección de líneas, como el algoritmo de detección de bordes cansados de openCv, pero comprobé que proporcionaban segmentos de línea muy discontinuos o, si el umbral era demasiado relajado, toneladas de líneas falsas. Además, los umbrales para obtener buenos resultados eran diferentes entre los distintos conjuntos de imágenes y yo quería un algoritmo para encontrar un conjunto coherente de líneas buenas sin supervisión.

Experimenté con una variedad de algoritmos de detección de líneas, incluidos algunos recientes, como gPb (PDF), que, si bien produce resultados asombrosos, requiere minutos para ejecutarse por imagen. Al final, establecí la detección de bordes de bosque estructurado, un algoritmo que se envía con openCV.

Una vez que tuve una buena "imagen de línea", todavía tenía el problema de obtener las líneas y de identificar líneas individuales entre sí, es decir, cómo tomo estos datos de trama y los convierte en vectores. A menudo, cuando tengo problemas de visión artificial, investigo imageJ, un entorno de procesamiento de imágenes basado en Java de código abierto que usan investigadores y científicos, y que tiene un ecosistema saludable de complementos. Encontré un complemento llamado detección de cresta, que ayuda a tomar una imagen de intensidad y convertirla en un conjunto de segmentos de línea. (Como nota al margen, también encontré útil este código de detección y etiquetado de bordes de Matlab).

Imagen con segmentos de línea detectados
Imagen con segmentos de línea detectados

Sin servidores

También quería ver si es posible hacer una app de visualización de datos que sea básicamente sin servidores, en la que el arduo trabajo de hacer coincidir y conectar ocurre en el cliente. Por lo general, trabajo en openFrameworks, un framework de c++ para programar creatividades y, además de los proyectos de nodos ocasionales, no he realizado mucha programación en el servidor. Tenía curiosidad por saber si era posible hacer todos los cálculos del lado del cliente y usar solo el servidor para entregar datos de imagen y JSON.

Para la aplicación de dibujo, la coincidencia es una operación muy pesada. Cuando dibujas una línea, debemos encontrar la coincidencia más cercana entre más de decenas de miles de segmentos de línea. Para calcular la distancia de un dibujo a otro, usamos una métrica del reconocimiento de gestos de dólar, que implica muchos cálculos de distancia. Antes, usaba subprocesos y otros trucos, pero, para que funcionara en tiempo real en un dispositivo cliente (incluidos los teléfonos celulares), necesitaba algo mejor. Busqué árboles de métricas para encontrar vecinos más cercanos y me decidí por árboles de puntos panorámicos (implementación de JavaScript). El árbol de puntos de observación, básicamente, se crea a partir de un conjunto de datos y una métrica de distancia, y cuando agregas un dato nuevo, te brinda rápidamente una lista de los valores más cercanos. La primera vez que vi este trabajo en un teléfono celular, quedé impactado. Uno de los grandes beneficios de esta implementación particular del árbol de puntos de vista es que puedes guardar el árbol después de calcularlo y ahorrar en los costos de procesamiento.

Resultados más cercanos Resultados obtenidos
Los ejemplos de resultados del árbol de puntos de vista; las entradas dibujadas están del lado derecho y los más cercanos, a la izquierda.

Otro desafío de hacer que funcione sin un servidor es cargar los datos en un dispositivo móvil. Para el dibujo, los datos de los segmentos de árbol y línea superan los 12 MB y las imágenes son bastante grandes. Queríamos que la experiencia fuera rápida y responsiva, y el objetivo era intentar que la descarga fuera pequeña. Nuestra solución fue cargar los datos de forma progresiva. En la app de dibujo, dividimos el conjunto de datos del árbol de puntos de observación en 5 partes y, cuando la app carga, solo carga el primer fragmento y, luego, cada 10 segundos, carga otro en segundo plano. Esencialmente, la app mejora durante el primer minuto de uso. En la app de arrastre, también se esforzó mucho para almacenar en caché imágenes, de modo que, a medida que arrastras, se carguen nuevas imágenes en segundo plano.

Por último, algo que me resultó más difícil de lo esperado fue crear un precargador para ambas apps, por lo que sería comprensible el retraso inicial en la carga de datos. Usé la devolución de llamada de progreso en las solicitudes ajax y, en el lado de pixi.js, comprobé que las imágenes que se cargaban de forma asíncrona se hayan cargado y lo usen para impulsar el mensaje de precarga.

Línea conectada

Para la función de arrastrar, quería crear una línea infinita a partir de las líneas que encontramos en la detección de bordes. El primer paso fue filtrar las líneas del algoritmo de detección de líneas y, luego, identificar las líneas largas que comienzan en un borde y terminan en uno de los otros tres bordes.

Líneas correctas para conexiones marcadas en rojo Líneas correctas para conexiones marcadas en rojo
Líneas buenas para la conexión marcadas en rojo

Una vez que tuve un conjunto de líneas largas (o, para usar un término más preciso, polilíneas, una colección de puntos conectados) a fin de conectarlas, convirtí estas líneas en un conjunto de cambios de ángulo. Por lo general, cuando piensas en una polilínea, se la imagina como un conjunto de puntos: el punto a está conectado con el punto b, que está conectado al punto c. En cambio, puedes tratar la línea como un conjunto de cambios de ángulo: avanzar y rotar cierta cantidad, avanzar y rotar cierta cantidad. Una buena manera de visualizar esto es pensar en las máquinas de doblaje de cables, que toman un trozo de alambre y, mientras se lo extruy, realizan rotaciones. La forma del dibujo proviene del giro.

Si consideras que la línea cambia de ángulo y no de puntos, se vuelve más fácil combinar líneas en una línea más grande con menos discontinuidades, en lugar de unir puntos, lo que haces es agregar cambios de ángulo relativos. Para agregar una línea, debes tomar el ángulo actual de la línea principal y agregarle los cambios relativos de la línea que deseas agregar.

Como nota al margen, usé esta técnica de convertir una línea en un conjunto de cambios de ángulo para un aprovechamiento artístico; puedes hacer que los dibujos se “desenrollen” de manera similar a como se enrolla en el cable y se desenrolla. Estos son algunos ejemplos: uno, dos, tres

Este cálculo del ángulo es lo que nos permite dirigir la línea a medida que arrastras. Calculamos qué tan lejos está el ángulo principal de donde queremos estar y buscamos una imagen que ayude en mayor medida a que la línea vaya en la dirección correcta. Es cuestión de pensar de manera relativamente.

Por último, quiero decir que fue un proyecto muy divertido en el que participar. Es emocionante como artista que se les pida usar un conjunto de datos tan hermoso como estas imágenes, y me honra que el equipo de Data Arts se haya comunicado con nosotros. ¡Espero que te diviertas experimentando con ella!