Canva Ship Shape: Shape Assist, que convierte figuras dibujadas a mano en vectores

• Shape Assist de Canva es una función que reconoce en el navegador figuras de un solo trazo dibujadas de forma temblorosa con la herramienta Draw y las convierte en gráficos vectoriales limpios
• Las heurísticas de visión por computadora basadas en reglas y umbrales servían para cuadrados, círculos y triángulos, pero tenían límites con figuras complejas como nubes, estrellas y corazones, y para agregar nuevas figuras
• El modelo trata el trazo no como una imagen, sino como una secuencia de coordenadas x·y; para ejecutarse en el cliente, se eligió una arquitectura basada en RNN/LSTM y código de inferencia personalizado en lugar de una CNN
• El modelo final consiste en una única capa LSTM con configuración P = 25, H = 100, N = 9 y una capa Gemm; tiene 64,109 parámetros, ocupa unos 250 KB y se ejecuta en menos de 10 ms en laptops modernas
• Funciona sin ida y vuelta al servidor, pero está diseñado para reemplazar automáticamente la figura solo cuando el usuario mantiene el cursor quieto durante al menos 1 segundo después de dibujarla y esta coincide lo suficiente con una figura predefinida

---

El rol de la herramienta Draw y Shape Assist

• La herramienta Draw de Canva permite a los usuarios agregar dibujos hechos directamente en sus diseños
• Shape Assist se creó para convertir garabatos temblorosos en gráficos vectoriales más suaves
• Como la latencia de clasificación era un requisito importante, se eligió la ejecución dentro del navegador en lugar del procesamiento en servidor
  • El usuario puede recibir feedback inmediatamente después de dibujar una figura
  • Se evita la latencia que genera el procesamiento basado en servidor
  • Puede usarse sin conexión, sin necesidad de una conexión permanente a Internet

Por qué se pasó de heurísticas a un modelo de ML

• La primera versión de Shape Assist usaba heurísticas de visión por computadora que analizaban las propiedades geométricas de las coordenadas dibujadas por el usuario
  • Detectaba ciertas figuras, como cuadrados, círculos y triángulos, mediante reglas y umbrales
  • Las coordenadas se analizaban como puntos en un sistema de coordenadas cartesianas
• Funcionaba para reconocer figuras básicas, pero era difícil agregar nuevas figuras o manejar figuras más complejas
  • La implementación inicial se limitaba a figuras que podían dibujarse con un solo trazo
  • La lista de figuras propuestas incluía nubes, estrellas y corazones, que son difíciles de manejar con un enfoque heurístico
• Un modelo de ML podía aprender distintos estilos y variaciones a partir de un dataset de dibujos a mano de usuarios, lo que permitió ampliar Shape Assist más allá de figuras geométricas simples hacia figuras más complejas

Datos de dibujos a mano y representación basada en coordenadas

• Canva recopiló datos de dibujos a mano de usuarios mediante una UI simple para dibujar figuras de un solo trazo
• Cada trazo se registró como una secuencia de coordenadas x·y
  • Este enfoque es más flexible para el preprocesamiento y la aumentación de datos que guardar la figura como una imagen binaria
  • Con un enfoque basado en imágenes, se pueden aplicar aumentaciones espaciales como volteo, rotación o cizallamiento
  • Con un enfoque basado en coordenadas, también son posibles aumentaciones como eliminar coordenadas al azar, añadir ruido aleatorio a la posición de los puntos o invertir el orden de los puntos
• Aunque solo con datos de voluntarios se reunió un dataset considerable, los dibujos de ingenieros y diseñadores no representaban bien al usuario promedio de Canva
  • Los ingenieros de ML tendían a aportar datos adversariales
  • Los dibujos de los diseñadores estaban demasiado bien hechos, por lo que a algunos se les indicó que dibujaran con la mano que no usan habitualmente
  • Tras proporcionar guías y expectativas más estrictas, se consiguió un dataset considerable

Diseño del modelo y método de entrenamiento

• Como el modelo tenía que ejecutarse en el cliente y no debía afectar negativamente el tiempo de carga de la página, era necesario minimizar su tamaño
• En lugar de una CNN, que requeriría convertir los puntos en píxeles, Canva experimentó con una RNN que usa directamente las coordenadas x·y del trazo
• Para encontrar las propiedades óptimas del modelo, se realizó una búsqueda de hiperparámetros
  • Se ajustaron parámetros como el tamaño de entrada, el número de capas y la cantidad de características del hidden state
• Como cada usuario dibuja a distinta velocidad, incluso una misma figura puede tener listas de puntos de diferente longitud
  • Los usuarios que dibujan despacio dejan más puntos
  • Los usuarios que dibujan rápido dejan menos puntos
• Para fijar la cantidad de puntos se podría haber usado interpolación lineal por intervalos de distribución uniforme, pero eso eliminaba puntos importantes y generaba pérdida de detalle
• En su lugar, Canva desarrolló una variante del algoritmo Ramer-Douglas-Peucker
  • RDP es un algoritmo de simplificación de curvas que reduce la cantidad de puntos preservando los detalles importantes de la curva
  • Elimina recursivamente los puntos que no se apartan de forma significativa de la curva simplificada

Método de clasificación para reducir reemplazos automáticos incorrectos

• Shape Assist no debe reemplazar automáticamente un dibujo a mano si no se parece lo suficiente a una de las clases predefinidas
• Como solo una figura puede ser la respuesta correcta, usar activación softmax y pérdida cross-entropy era una opción natural
  • El enfoque consiste en rechazar la predicción si la confianza de la clase con mayor probabilidad está por debajo de un umbral
• Sin embargo, con este enfoque el modelo podía mostrar alta confianza incluso cuando se equivocaba
• Finalmente, se entrenó como un clasificador multiclase y multietiqueta usando activación sigmoid en cada clase de salida
  • Si ninguna clase supera el umbral, se rechaza la predicción

Arquitectura de inferencia en el cliente

• Los modelos de ML suelen ser grandes y requerir mucho cómputo, por lo que a menudo se ejecutan en computadoras potentes en la nube
• El modelo de Shape Assist es pequeño y requiere pocas operaciones matemáticas, lo que permitió ejecutar todo el procesamiento dentro de la aplicación cliente
• Este enfoque elimina la necesidad de conexión al servidor y quita el tiempo de ida y vuelta, permitiendo reconocer las figuras casi al instante

Arquitectura y tamaño del modelo

• El modelo final tiene una estructura con una única capa LSTM seguida de una capa Gemm
  • Gemm también se conoce como capa Dense o Fully Connected
• Los valores principales de configuración son los siguientes
  • Cantidad de puntos interpolados: P = 25
  • hidden size: H = 100
  • Cantidad de figuras predefinidas: N = 9
• La cantidad de parámetros se calcula así
  • LSTM: 4H * 2 + 4H * H + 8H = 41,600
  • Gemm: P * H * N + N = 22,509
  • Total: 64,109
• Usando 4 bytes por parámetro con punto flotante de 32 bits IEEE754, el tamaño del modelo es de unos 250 KB
  • Es un tamaño similar al de una imagen 360p 16:9 sin comprimir
  • Podría reducirse aún más almacenando los parámetros con menor precisión
• Canva implementó directamente en TypeScript las operaciones LSTM y Gemm, en lugar de usar un motor de ML de propósito general
  • Es un enfoque que no se generaliza bien a modelos más complejos
  • La implementación tiene menos de 300 líneas
  • Se ejecuta en menos de 10 ms en laptops modernas

Reemplazo y alineación de figuras

• Después de que el modelo identifica la figura dibujada a mano, Canva ajusta la ruta del dibujo a la representación de gráfico vectorial mediante template matching
• El proceso de alineación se realiza tras normalizar la figura de entrada y la figura de plantilla
  • Prueba rotar la figura de plantilla en incrementos de 15°
  • Calcula los momentos de primer y segundo orden de los puntos de entrada en el espacio de coordenadas rotado
  • Calcula la disimilitud entre los puntos de entrada y la figura de plantilla
  • Elige como ángulo óptimo la rotación con menor disimilitud
• Si el usuario mantiene el cursor en su lugar durante al menos 1 segundo después de dibujar la figura, Shape Assist reemplaza la figura cuando coincide lo suficiente con una figura predefinida

[GN⁺]

Opiniones en Hacker News

• Me parece que una red neuronal recurrente (RNN) es excesiva para este problema, y que el sencillo y elegante $1 unistroke recognizer sería más adecuado.
  Funciona bastante bien entrenándolo con una sola muestra por gesto, y en cualquier proyecto se puede integrar en una tarde para hacer que la UI sea más amigable con reconocimiento de gestos.
  Si cada letra es de un solo trazo, también funciona de forma bastante estable para la entrada de texto tipo Graffiti de Palm, y el paper original está escrito de manera fácil de leer y entender.
  https://depts.washington.edu/acelab/proj/dollar/index.html

  • El gran problema del $1 recognizer es que hay que dibujar los trazos de una forma específica.
    Por ejemplo, al dibujar un círculo hay que hacerlo en sentido antihorario; si lo dibujas en sentido horario, que se siente más natural, lo reconoce como un caret.
    En un contexto de dibujo libre, donde el usuario no conoce los detalles de implementación, es difícil usarlo en la práctica.
  • Lo que pasan por alto quienes prueban los ejemplos de esta página y reportan errores es que esta demo fue “entrenada” con un solo ejemplo.
    El paper enlazado[0] trata la tasa de error, y mejora bastante rápido con solo agregar unos pocos ejemplos más.
    [0]https://faculty.washington.edu/wobbrock/pubs/uist-07.01.pdf , página 8
  • Lo probé, y al menos para usarlo sin entrenamiento me pareció bastante malo.
    El rectángulo que dibujé lo reconoció como un caret, y el zigzag como una llave.
    Tampoco admite figuras dibujadas con dos trazos, como las flechas.
  • Lo usé un momento y era demasiado simple. Si no dibujas exactamente como las figuras de ejemplo, las confunde entre sí.
    Comparar las figuras de ejemplo “delete” y “x” sirve para ver qué tan malo es el desempeño.
    Puede estar bien como punto de partida para una interfaz gestual que espera que siempre dibujes las figuras de la misma manera, pero no encaja bien para el uso de diagramación del que se habla aquí.
  • Coincido en que funciona demasiado bien para algo tan simple.
    Hice una implementación en ES6 como proyecto universitario; si a alguien le interesa, está aquí: https://github.com/gurgunday/onedollar-unistroke-es6

• Entiendo la explicación de que “incluso una línea recta simple dibujada con mouse o trackpad puede parecer el camino que recorrió una ardilla borracha”, pero no sé quién en Canva tendría que dibujar figuras a mano con el mouse.
  Antes, Miro tenía una función que, si dibujabas más o menos una estrella con el mouse, la convertía en una estrella geométricamente precisa, un círculo, un triángulo, etc.; me pareció genial, pero en la práctica nunca la necesité.
  Al hacer diagramas, suele ser más rápido usar figuras ya preparadas; al crear íconos, uso un flujo de trabajo separado centrado en operaciones booleanas, mover puntos y la herramienta Pen, normalmente en un programa especializado como Illustrator.
  Cuando dibujo ilustraciones reales, saco la tablet, así que aunque la tecnología en sí es genial, me pregunto cuál es el caso de uso.

  • Canva no es una herramienta de diagramación, sino una herramienta de diseño visual con una base de usuarios bastante distinta.
    Su biblioteca de assets es enorme e incluye millones, quizá decenas de millones, de imágenes entre fotos y gráficos vectoriales.
    Según mi experiencia limitada, era especialmente molesto tener que buscar en una biblioteca interminable incluso cuando ya sabía exactamente qué figura simple quería, y esta herramienta probablemente busca reducir ese dolor.
    Trabajé en Canva hace unos años.
    No tengo ninguna información interna, pero como Canva quiere ser también una herramienta de diagramación competitiva, este caso de uso podría ser importante. Aun así, parece existir la restricción de que no pueden cambiar de raíz la experiencia de diseño del 99% de los usuarios actuales.
  • Para diseñadores o marketers que no aprenden atajos de teclado, “dibujar una figura con el mouse” es rápido, y “pasar por medio menú, elegir la figura adecuada, colocarla y luego ajustar su tamaño” es más lento.
    Incluso si la figura estuviera disponible directamente sin menú, dibujarlo todo con un solo cursor puede ser más rápido que colocar y redimensionar varios íconos, cambiar a la función de flechas y agregar una flecha.

• La biblioteca que usa Canva para dibujar líneas también podría ser interesante: https://github.com/steveruizok/perfect-freehand

  • No parece que Canva sea patrocinador.

• La parte de que “desarrollaron una variante del algoritmo Ramer-Douglas-Peucker (RDP)” me recordó un viejo proyecto paralelo.
  En una charla de Strange Loop de 2018 apliqué Douglas-Peucker a Picasso.
  Picasso's Bulls: Deconstructing his design process with Python
  https://rrherr.github.io/picasso/

• Me da curiosidad cómo lograron algo parecido hace más de 20 años en Macromedia Flash.
  En esa época el rendimiento de las CPU era mucho más limitado que ahora, y recuerdo vívidamente haberme sorprendido al ver cómo suavizaba las curvas al dibujar trazos libres.

  • LeCun y su equipo lograron en 1995 una precisión superior al 99% en el reconocimiento de dígitos escritos a mano, lo cual es bastante parecido a identificar formas.
    Aun así, hacer que corra de forma ligera y rápida en el navegador sigue siendo un logro. Al final, lo importante siempre es la experiencia de usuario.
  • En 1993, Apple Newton tenía esta función como una característica central incluso con un procesador ARM de 20 MHz.
    https://en.wikipedia.org/wiki/MessagePad#User_interface
  • El suavizado es una tarea aparte que simplifica las curvas de Bézier eliminando puntos casi redundantes.
    Por ejemplo, si al dibujar una línea casi recta se generaran 100 puntos de control, el software los reduciría a unos 4 puntos.
  • Probablemente recibía eventos del mouse y, al principio, dibujaba uniendo los eventos con líneas rectas. En el hardware de los años 90, dibujar líneas rectas era rápido, y seguramente era necesario porque había que dibujar con rapidez.
    Una vez terminado el trazo, habría usado esos mismos puntos como entrada para redibujar la línea con un algoritmo de curvas spline.
    El cálculo para dibujar una spline en sí no es mucho más difícil, pero lo importante es que, si agregas un punto al final, puede cambiar parte de la línea ya dibujada.
    Entonces habría que volver a dibujar todo lo que está detrás de esa línea, lo que implica un costo computacional alto y hace difícil garantizar que se pueda manejar de forma confiable a 60 fps.

• Es un buen artículo y el trabajo es muy interesante.
  Quizá sea un gusto minoritario, pero curiosamente me resulta más agradable esa sensación de garabato tembloroso dibujado a mano que los gráficos vectoriales lisos.
  Claro que la preferencia puede cambiar según el contexto, así que la función en sí está genial. En un mundo lleno de perfección artificial, hay algo que nos atrae de forma esencial en los resultados verdaderamente hechos a mano.

• Si implementan una función así, espero que sea opcional y que quede claramente visible cuando esté activada.
  Cuando una herramienta pretende ser demasiado inteligente y no acierta a la perfección, da mucha rabia. Yo también he cometido ese error.

• Algunos años antes de la reciente moda de machine learning/IA, había un juego que les gustaba a los niños llamado Scribblenauts, que convertía garabatos muy toscos en una variedad sorprendente de objetos.
  No sé cómo lo hacía, pero a mí también me impresionó, y los niños lo veían como magia.
  https://store.steampowered.com/app/218680/Scribblenauts_Unli...

  • Lo probé y era realmente asombroso. Si no recuerdo mal, creo que también salió para iOS.

• Ojalá esto fuera open source.
  Últimamente están apareciendo varios modelos de tamaño pequeño. Este modelo pesa 250 KB, y en tareas simples de fine-tuning de modelos grandes incluso había modelos de alrededor de 50 KB.
  Me entusiasma el momento en que volvamos a poder usar modelos pequeños de verdad en aplicaciones útiles.

• Una estrella pentagonal y una estrella brillante no son lo mismo. ¿Esto es un ejemplo de subajuste?

  • https://en.wikipedia.org/wiki/Star_polygon