- Shape Assist de Canva est une fonctionnalité du Draw tool qui reconnaît dans le navigateur des formes tracées en un seul trait, même de façon irrégulière, pour les convertir en graphiques vectoriels propres
- Les heuristiques de vision par ordinateur fondées sur des règles et des seuils fonctionnaient pour les rectangles, cercles et triangles, mais montraient leurs limites pour des formes complexes comme les nuages, étoiles ou cœurs, ainsi que pour l’ajout de nouvelles formes
- Le modèle traite les traits non pas comme des images mais comme des séquences de coordonnées x·y et, pour une exécution côté client, Canva a choisi une architecture basée sur RNN/LSTM avec un code d’inférence personnalisé plutôt qu’un CNN
- Le modèle final se compose d’une seule couche LSTM et d’une couche Gemm avec la configuration
P = 25,H = 100,N = 9, pour64,109paramètres et une taille d’environ 250 KB, avec une exécution en moins de 10 ms sur un ordinateur portable récent - Le système fonctionne sans aller-retour vers le serveur, mais il est conçu pour ne remplacer automatiquement une forme que lorsque l’utilisateur garde le curseur immobile plus d’une seconde après l’avoir dessinée et qu’elle correspond suffisamment à une forme prédéfinie
Rôle du Draw tool et de Shape Assist
- Le Draw tool de Canva permet aux utilisateurs d’ajouter directement des dessins à leurs créations
- Shape Assist a été conçu pour transformer des croquis tremblants en graphiques vectoriels plus fluides
- La latence de classification étant une contrainte importante, Canva a choisi une exécution dans le navigateur plutôt qu’un traitement serveur
- l’utilisateur peut recevoir un retour immédiatement après avoir dessiné une forme
- cela évite la latence liée au traitement côté serveur
- la fonctionnalité peut être utilisée hors ligne, sans connexion Internet permanente
Pourquoi passer des heuristiques à un modèle de ML
- La première version de Shape Assist utilisait des heuristiques de vision par ordinateur qui analysaient les propriétés géométriques des coordonnées dessinées par l’utilisateur
- des formes spécifiques comme les rectangles, cercles et triangles étaient détectées à l’aide de règles et de seuils
- les coordonnées étaient analysées comme des points dans un repère cartésien
- Cela fonctionnait pour la reconnaissance de formes simples, mais rendait difficile l’ajout de nouvelles formes ou la prise en charge de formes plus complexes
- l’implémentation initiale se limitait aux formes pouvant être tracées en un seul trait
- la liste des formes proposées incluait des nuages, étoiles et cœurs, difficiles à traiter avec une approche heuristique
- Un modèle de ML pouvait apprendre, à partir d’un jeu de données de dessins d’utilisateurs, des styles et variations très divers, ce qui permettait d’étendre Shape Assist au-delà des formes géométriques simples
Données de dessins à la main et représentation par coordonnées
- Canva a collecté des données de dessins d’utilisateurs au moyen d’une interface simple permettant de tracer des formes en un seul trait
- Chaque trait est enregistré comme une séquence de coordonnées x·y
- cette approche est plus flexible pour le prétraitement et l’augmentation de données que le stockage sous forme d’image binaire
- avec une représentation image, on peut appliquer des augmentations spatiales comme le retournement, la rotation ou le cisaillement
- avec une représentation par coordonnées, on peut aussi effectuer des augmentations comme la suppression aléatoire de coordonnées, de petites perturbations aléatoires de la position des points ou l’inversion de l’ordre des points
- Même avec les seules données des volontaires, Canva a réuni un jeu de données conséquent, mais les dessins d’ingénieurs et de designers ne représentaient pas bien l’utilisateur moyen de Canva
- les ingénieurs ML avaient tendance à fournir des données adversariales
- les dessins des designers étaient trop réussis, si bien qu’on a demandé à certains de dessiner avec leur main non dominante
- après avoir fourni des consignes et attentes plus strictes, Canva a obtenu un jeu de données substantiel
Conception du modèle et apprentissage
- Le modèle devait s’exécuter côté client et ne pas dégrader le temps de chargement de la page, ce qui imposait de minimiser sa taille
- Au lieu d’un CNN qui aurait nécessité de convertir les points en pixels, Canva a expérimenté des RNN utilisant directement les coordonnées x·y des traits
- Une recherche d’hyperparamètres a été menée pour identifier les meilleures caractéristiques du modèle
- des paramètres comme la taille d’entrée, le nombre de couches ou le nombre de caractéristiques du hidden state ont été ajustés
- Les utilisateurs dessinent à des vitesses différentes, si bien qu’une même forme peut produire des listes de points de longueur variable
- les utilisateurs qui dessinent lentement laissent plus de points
- ceux qui dessinent rapidement en laissent moins
- Il aurait été possible de fixer le nombre de points par interpolation linéaire sur des intervalles uniformément répartis, mais cela supprimait des points importants et faisait perdre des détails
- Canva a donc développé une variante de l’algorithme de Ramer-Douglas-Peucker
- RDP est un algorithme de simplification de courbe qui réduit le nombre de points tout en préservant les détails importants
- il supprime récursivement les points qui ne s’écartent pas de manière significative de la courbe simplifiée
Méthode de classification pour réduire les remplacements automatiques erronés
- Shape Assist ne doit pas remplacer automatiquement un dessin si celui-ci ne ressemble pas suffisamment à l’une des classes prédéfinies
- Comme une seule forme peut être correcte, une activation softmax avec une perte de type cross-entropy semblait être un choix naturel
- l’idée consistait à rejeter la prédiction si la confiance de la classe la plus probable était inférieure à un seuil
- Mais cette approche posait problème, car le modèle pouvait afficher une forte confiance même lorsqu’il se trompait
- Au final, Canva a entraîné un classifieur multiclasse et multilabel avec une activation sigmoid pour chaque classe de sortie
- si aucune classe ne dépasse le seuil, la prédiction est rejetée
Architecture d’inférence côté client
- Les modèles de ML sont souvent volumineux et coûteux en calcul, et s’exécutent fréquemment sur des machines puissantes dans le cloud
- Le modèle de Shape Assist est suffisamment compact et peu gourmand en opérations mathématiques pour que tout le traitement puisse s’exécuter dans l’application cliente
- Cette approche supprime le besoin de connexion au serveur et élimine le temps d’aller-retour, ce qui permet une reconnaissance de forme presque immédiate
Architecture et taille du modèle
- Le modèle final repose sur une seule couche LSTM, suivie d’une couche Gemm
- Gemm est aussi appelée couche Dense ou Fully Connected
- Les principaux paramètres sont les suivants
- nombre de points interpolés :
P = 25 - hidden size :
H = 100 - nombre de formes prédéfinies :
N = 9
- nombre de points interpolés :
- Le nombre de paramètres se calcule ainsi
- LSTM :
4H * 2 + 4H * H + 8H = 41,600 - Gemm :
P * H * N + N = 22,509 - total :
64,109
- LSTM :
- Avec des nombres flottants IEEE754 32 bits, à raison de 4 octets par paramètre, la taille du modèle est d’environ 250 KB
- c’est comparable à une image 360p 16:9 non compressée
- il serait possible de réduire encore cette taille en stockant les paramètres avec une précision plus faible
- Canva a implémenté directement en TypeScript les opérations LSTM et Gemm au lieu d’utiliser un moteur de ML généraliste
- cette approche se généralise mal à des modèles plus complexes
- l’implémentation fait moins de 300 lignes
- elle s’exécute en moins de 10 ms sur un ordinateur portable récent
Remplacement et alignement des formes
- Une fois la forme dessinée à la main identifiée par le modèle, Canva aligne le tracé sur sa représentation vectorielle à l’aide d’une méthode de template matching
- Le processus d’alignement commence par une normalisation de la forme d’entrée et de la forme modèle
- la forme modèle est testée avec des rotations par pas de 15°
- les moments du premier et du second ordre des points d’entrée sont calculés dans l’espace de coordonnées tourné
- une mesure de dissimilarité est calculée entre les points d’entrée et la forme modèle
- la rotation qui minimise cette dissimilarité est choisie comme angle optimal
- Si l’utilisateur garde le curseur immobile pendant au moins une seconde après avoir dessiné la forme, Shape Assist la remplace lorsqu’elle correspond suffisamment à une forme prédéfinie
1 commentaires
Avis de Hacker News
Un réseau de neurones récurrent (RNN) me semble excessif pour ce problème ; le $1 unistroke recognizer, simple et élégant, paraît plus approprié.
Il fonctionne plutôt bien même avec un seul échantillon d’apprentissage par geste, et on peut l’intégrer à n’importe quel projet en un après-midi pour rendre l’UI plus conviviale grâce à la reconnaissance de gestes.
Si chaque lettre est tracée d’un seul trait, il fonctionne aussi de manière assez fiable pour la saisie de texte façon Graffiti de Palm ; l’article original est également facile à lire et à comprendre.
https://depts.washington.edu/acelab/proj/dollar/index.html
Par exemple, pour dessiner un cercle, il faut le tracer dans le sens antihoraire ; si on le trace dans le sens horaire, ce qui paraît plus naturel, il est reconnu comme un caret.
Dans un contexte de dessin libre, où l’utilisateur ne connaît pas les détails d’implémentation, c’est difficilement utilisable en pratique.
L’article cité[0] traite du taux d’erreur, et l’ajout de quelques exemples seulement améliore les résultats assez rapidement.
[0]https://faculty.washington.edu/wobbrock/pubs/uist-07.01.pdf , page 8
Mon carré a été reconnu comme un caret, et mon zigzag comme une accolade.
Il ne prend pas non plus en charge les formes tracées en deux traits, comme les flèches.
Comparer les formes d’exemple « delete » et « x » est un bon moyen de voir à quel point les performances sont mauvaises.
C’est peut-être un bon point de départ pour une interface gestuelle qui suppose que l’on dessine toujours les formes de la même manière, mais cela ne convient pas vraiment à l’usage de création de diagrammes dont il est question ici.
J’en ai fait une implémentation ES6 pour un projet universitaire ; si ça vous intéresse, elle est ici : https://github.com/gurgunday/onedollar-unistroke-es6
Je comprends l’explication selon laquelle « même une simple ligne droite tracée à la souris ou au trackpad peut ressembler au trajet d’un écureuil ivre », mais je ne vois pas bien qui, dans Canva, aurait besoin de dessiner des formes à la main avec une souris.
Il y a longtemps, Miro avait une fonctionnalité qui transformait une étoile grossièrement dessinée à la souris en étoile, cercle, triangle, etc. géométriquement corrects ; je trouvais ça génial, mais en pratique je n’en ai jamais eu besoin.
Quand je fais des diagrammes, utiliser des formes prédéfinies est plus rapide ; quand je crée des icônes, j’utilise un autre flux de travail centré sur les opérations booléennes, le déplacement de points et l’outil Pen, généralement dans un logiciel dédié comme Illustrator.
Pour dessiner de vraies illustrations, je sors une tablette ; donc même si la technologie est impressionnante, je me demande quel est le cas d’usage.
Sa bibliothèque d’assets est énorme, avec des millions, peut-être des dizaines de millions d’images, incluant des photos et des graphismes vectoriels.
D’après mon expérience limitée, même quand on sait exactement quelle forme simple on veut, il est particulièrement pénible de devoir fouiller une bibliothèque sans fin ; cet outil semble probablement chercher à réduire cette friction.
J’ai travaillé chez Canva il y a quelques années.
Je n’ai aucune information interne, mais comme Canva veut aussi devenir un outil de diagrammes compétitif, ce cas d’usage pourrait être important. Cela dit, il doit y avoir la contrainte de ne pas pouvoir changer fondamentalement l’expérience de design de 99 % des utilisateurs actuels.
Même si la forme est directement accessible sans menu, tout tracer avec un seul curseur peut être plus rapide que placer et redimensionner plusieurs icônes, puis passer à la fonction flèche pour ajouter une flèche.
La bibliothèque que Canva utilise pour tracer les lignes peut aussi être intéressante : https://github.com/steveruizok/perfect-freehand
Le passage « nous avons développé une variante de l’algorithme de Ramer-Douglas-Peucker (RDP) » m’a rappelé un ancien projet parallèle.
Lors d’une présentation à Strange Loop en 2018, j’avais appliqué Douglas-Peucker à Picasso.
Picasso's Bulls: Deconstructing his design process with Python
https://rrherr.github.io/picasso/
Je me demande comment Macromedia Flash arrivait déjà à faire quelque chose de similaire il y a bien plus de 20 ans
À l’époque, les performances des CPU étaient bien plus limitées qu’aujourd’hui, et je me souviens encore très vivement de ma surprise en voyant les courbes tracées à main levée être lissées proprement
Cela dit, réussir à faire tourner ça légèrement et rapidement dans un navigateur reste un bel accomplissement. Au final, ce qui compte, c’est toujours l’expérience utilisateur
https://en.wikipedia.org/wiki/MessagePad#User_interface
Si, en traçant une ligne presque droite, on obtient 100 points de contrôle, le logiciel les réduit par exemple à environ 4 points
Une fois le tracé terminé, il a sans doute repris les mêmes points en entrée pour redessiner la ligne avec un algorithme de courbes splines
Le calcul nécessaire pour dessiner une spline n’est pas forcément beaucoup plus difficile, mais le point important est qu’ajouter un point à la fin peut modifier une partie de la ligne déjà dessinée
Il faut alors redessiner tout ce qui se trouve derrière cette ligne, ce qui coûte cher en calcul, et il est difficile de garantir que cela se fera sûrement à 60 fps
C’est un bon article, et le travail est vraiment très intéressant
C’est sans doute une préférence de niche, mais étrangement, je trouve que le côté gribouillis tremblant dessiné à la main est plus agréable que des graphismes vectoriels bien lisses
Bien sûr, la préférence peut varier selon le contexte, donc la fonctionnalité en elle-même est chouette. Dans un monde saturé de perfection artificielle, il y a quelque chose qui nous attire intrinsèquement vers de vrais résultats dessinés à la main
Si une telle fonctionnalité est implémentée, j’aimerais vraiment qu’elle soit désactivable, et que son activation soit clairement visible
Quand un outil fait trop le malin mais n’arrive pas à viser parfaitement juste, c’est vraiment rageant. J’ai déjà commis ce genre d’erreur moi-même
Quelques années avant la vague récente du machine learning/de l’IA, il y avait un jeu que les enfants adoraient, Scribblenauts, qui transformait des gribouillis très grossiers en une variété étonnante d’objets
Je ne sais pas comment c’était fait, mais moi aussi j’étais impressionné, et les enfants y voyaient de la magie
https://store.steampowered.com/app/218680/Scribblenauts_Unli...
J’aimerais que ce soit open source
Ces derniers temps, on voit apparaître plusieurs modèles de petite taille. Celui-ci fait 250 Ko, et pour de simples tâches de fine-tuning de grands modèles, il y avait même des modèles d’environ 50 Ko
J’ai hâte de voir le moment où l’on pourra de nouveau utiliser concrètement de petits modèles dans des applications utiles
Une étoile pentagonale et une étoile scintillante ne sont pas la même chose. Est-ce un exemple de sous-ajustement ?