Canva Ship Shape: Shape Assist verwandelt handgezeichnete Formen in Vektoren

• Shape Assist von Canva erkennt im Draw tool verwackelt gezeichnete Formen mit einem einzelnen Strich direkt im Browser und wandelt sie in saubere Vektorgrafiken um
• Computer-Vision-Heuristiken, die auf Regeln und Schwellwerten basieren, funktionierten für Rechtecke, Kreise und Dreiecke, stießen aber bei komplexeren Formen wie Wolken, Sternen oder Herzen sowie beim Hinzufügen neuer Formen an Grenzen
• Das Modell verarbeitet Striche nicht als Bilder, sondern als x·y-Koordinatensequenzen; für die Ausführung auf dem Client wurde statt eines CNN eine RNN-/LSTM-basierte Architektur mit benutzerdefiniertem Inferenzcode gewählt
• Das finale Modell besteht aus einer einzelnen LSTM-Schicht und einer Gemm-Schicht mit den Einstellungen P = 25, H = 100, N = 9; es hat 64,109 Parameter, ist rund 250 KB groß und läuft auf aktuellen Laptops in unter 10 ms
• Es arbeitet ohne Server-Roundtrip, ist aber so ausgelegt, dass eine automatische Ersetzung nur erfolgt, wenn der Nutzer nach dem Zeichnen den Cursor länger als 1 Sekunde stillhält und die Form ausreichend gut zu einer vordefinierten Form passt

---

Die Rolle von Draw tool und Shape Assist

• Das Draw tool von Canva ermöglicht es Nutzern, direkt gezeichnete Skizzen zu einem Design hinzuzufügen
• Shape Assist wurde entwickelt, um verwackelte Kritzeleien in glattere Vektorgrafiken zu verwandeln
• Da die Latenz der Klassifizierung ein entscheidender Faktor war, fiel die Wahl auf Ausführung im Browser statt auf Server-Verarbeitung
  • Nutzer erhalten sofort Feedback, sobald sie eine Form zeichnen
  • Verzögerungen serverbasierter Verarbeitung lassen sich vermeiden
  • Die Funktion kann auch offline ohne permanente Internetverbindung genutzt werden

Warum von Heuristiken zu einem ML-Modell gewechselt wurde

• Die erste Version von Shape Assist nutzte Computer-Vision-Heuristiken, die geometrische Eigenschaften der vom Nutzer gezeichneten Koordinaten analysierten
  • Bestimmte Formen wie Rechtecke, Kreise und Dreiecke wurden anhand von Regeln und Schwellwerten erkannt
  • Die Koordinaten wurden als Punkte in einem kartesischen Koordinatensystem analysiert
• Für grundlegende Formen funktionierte das, doch neue oder komplexere Formen ließen sich damit nur schwer ergänzen
  • Die erste Implementierung war auf Formen beschränkt, die sich mit einem einzigen Strich zeichnen lassen
  • Die vorgeschlagene Formenliste enthielt Wolken, Sterne und Herzen, die sich heuristisch nur schwer behandeln lassen
• Ein ML-Modell konnte aus einem Datensatz handgezeichneter Nutzerskizzen unterschiedliche Stile und Variationen lernen und Shape Assist so über einfache geometrische Formen hinaus erweitern

Handgezeichnete Daten und koordinatenbasierte Repräsentation

• Canva sammelte Nutzerdaten zu handgezeichneten Formen über eine einfache UI zum Zeichnen von Einzelstrich-Formen
• Jeder Strich wurde als x·y-Koordinatensequenz aufgezeichnet
  • Dieser Ansatz ist bei Vorverarbeitung und Data Augmentation flexibler, als Formen als binäre Bilder zu speichern
  • Bei einem bildbasierten Ansatz lassen sich räumliche Augmentierungen wie Spiegeln, Rotieren und Scheren anwenden
  • Bei einem koordinatenbasierten Ansatz sind auch Augmentierungen wie zufälliges Entfernen von Koordinaten, zufälliges Verwackeln von Punktpositionen oder das Umkehren der Punktreihenfolge möglich
• Schon mit Daten von Freiwilligen kam ein beachtlicher Datensatz zusammen, doch die Zeichnungen von Engineers und Designern repräsentierten den durchschnittlichen Canva-Nutzer nicht gut
  • ML-Engineers lieferten tendenziell adversariale Daten
  • Zeichnungen von Designern waren zu sauber, sodass einige gebeten wurden, vorwiegend mit der nicht dominanten Hand zu zeichnen
  • Nach strengeren Richtlinien und klareren Erwartungen konnte ein umfangreicher Datensatz aufgebaut werden

Modelldesign und Training

• Das Modell musste auf dem Client laufen und durfte die Ladezeit der Seite nicht negativ beeinflussen, daher musste es möglichst klein sein
• Statt eines CNN, bei dem Punkte erst in Pixel umgewandelt werden müssten, experimentierte Canva mit einem RNN, das die x·y-Koordinaten eines Strichs direkt verarbeitet
• Um optimale Modelleigenschaften zu finden, wurde eine Hyperparameter-Suche durchgeführt
  • Dabei wurden Parameter wie Eingabegröße, Anzahl der Schichten und Zahl der Merkmale im hidden state variiert
• Da Nutzer mit unterschiedlicher Geschwindigkeit zeichnen, kann dieselbe Form unterschiedlich lange Punktlisten erzeugen
  • Wer langsam zeichnet, hinterlässt mehr Punkte
  • Wer schnell zeichnet, hinterlässt weniger Punkte
• Um die Punktzahl zu fixieren, hätte man lineare Interpolation über gleichmäßig verteilte Intervalle einsetzen können, doch dabei gingen wichtige Details verloren
• Stattdessen entwickelte Canva eine Variante des Ramer-Douglas-Peucker-Algorithmus
  • RDP ist ein Kurvenvereinfachungsalgorithmus, der die Zahl der Punkte reduziert und dabei wichtige Details einer Kurve erhält
  • Er entfernt rekursiv Punkte, die nicht wesentlich von der vereinfachten Kurve abweichen

Klassifizierung zur Verringerung falscher automatischer Ersetzungen

• Shape Assist sollte eine Skizze nicht automatisch ersetzen, wenn sie keiner der vordefinierten Klassen hinreichend ähnlich ist
• Da jeweils nur eine Form korrekt sein kann, waren Softmax-Aktivierung und Cross-Entropy-Loss zunächst eine naheliegende Wahl
  • Dabei wird eine Vorhersage verworfen, wenn das Vertrauen in die wahrscheinlichste Klasse unter einem Schwellwert liegt
• In diesem Ansatz zeigte das Modell jedoch auch bei falschen Vorhersagen oft hohe Konfidenz
• Schließlich wurde ein Multi-Class-/Multi-Label-Klassifikator mit Sigmoid-Aktivierung pro Ausgabeklasse trainiert
  • Überschreitet keine Klasse den Schwellwert, wird die Vorhersage verworfen

Clientseitige Inferenzarchitektur

• ML-Modelle sind oft groß und rechenintensiv und laufen daher häufig auf leistungsstarken Cloud-Systemen
• Das Shape-Assist-Modell ist klein und benötigt nur wenige mathematische Operationen, sodass die gesamte Verarbeitung innerhalb der Client-Anwendung erfolgen kann
• Dadurch entfällt die Notwendigkeit einer Serververbindung, und die Server-Roundtrip-Zeit wird eliminiert, sodass Formen nahezu sofort erkannt werden

Modellarchitektur und Größe

• Das finale Modell besteht aus einer einzelnen LSTM-Schicht, gefolgt von einer Gemm-Schicht
  • Gemm wird auch als Dense- oder Fully-Connected-Schicht bezeichnet
• Die wichtigsten Konfigurationswerte sind:
  • Anzahl interpolierter Punkte: P = 25
  • hidden size: H = 100
  • Anzahl vordefinierter Formen: N = 9
• Die Zahl der Parameter berechnet sich wie folgt:
  • LSTM: 4H * 2 + 4H * H + 8H = 41,600
  • Gemm: P * H * N + N = 22,509
  • Gesamt: 64,109
• Bei IEEE754-32-Bit-Gleitkommazahlen und 4 Byte pro Parameter ergibt das eine Modellgröße von rund 250 KB
  • Das entspricht ungefähr einem unkomprimierten 360p-16:9-Bild
  • Mit geringerer Präzision ließe sich die Größe möglicherweise weiter reduzieren
• Canva implementierte LSTM- und Gemm-Operationen direkt in TypeScript statt eine allgemeine ML-Engine zu verwenden
  • Dieser Ansatz lässt sich nicht gut auf komplexere Modelle verallgemeinern
  • Die Implementierung umfasst weniger als 300 Zeilen
  • Auf aktuellen Laptops läuft sie in unter 10 ms

Formersetzung und Ausrichtung

• Nachdem das Modell eine handgezeichnete Form erkannt hat, passt Canva den gezeichneten Pfad per Template Matching an eine Vektorgrafik-Repräsentation an
• Der Ausrichtungsprozess erfolgt nach der Normalisierung von Eingabeform und Template-Form
  • Die Template-Form wird in 15°-Schritten rotiert
  • Im rotierten Koordinatenraum werden erste und zweite Momente der Eingabepunkte berechnet
  • Anschließend wird die Unähnlichkeit zwischen Eingabepunkten und Template-Form bestimmt
  • Die Rotation mit der geringsten Unähnlichkeit wird als optimaler Winkel gewählt
• Wenn der Nutzer nach dem Zeichnen den Cursor mindestens 1 Sekunde an derselben Stelle hält und die Skizze ausreichend gut zu einer vordefinierten Form passt, ersetzt Shape Assist die Form

[GN⁺]

Meinungen auf Hacker News

• Für dieses Problem scheint ein rekurrentes neuronales Netz (RNN) überdimensioniert; der einfache und elegante $1 Unistroke Recognizer wirkt passender.
  Er funktioniert schon ziemlich gut, wenn man pro Geste nur ein einziges Beispiel trainiert, und man kann ihn in jedes Projekt an einem halben Nachmittag einbauen, um die UI mit Gestenerkennung vertrauter zu machen.
  Wenn jeder Buchstabe aus einem Strich besteht, funktioniert er auch für Texteingabe im Palm-Stil mit Graffiti ziemlich zuverlässig; auch das Originalpaper ist leicht zu lesen und gut verständlich geschrieben.
  https://depts.washington.edu/acelab/proj/dollar/index.html

  • Das große Problem des $1 Recognizer ist, dass man Striche auf eine bestimmte Weise zeichnen muss.
    Einen Kreis muss man zum Beispiel gegen den Uhrzeigersinn zeichnen; wenn man ihn im natürlicher wirkenden Uhrzeigersinn zeichnet, wird er als Caret erkannt.
    In einem Freehand-Drawing-Kontext, in dem Nutzer die Implementierungsdetails nicht kennen, ist das praktisch schwer einsetzbar.
  • Was Leute übersehen, die die Beispiele auf dieser Seite testen und Fehler melden: Diese Demo wurde nur mit einem einzigen Beispiel „trainiert“.
    Das verlinkte Paper[0] behandelt die Fehlerrate, und schon mit ein paar zusätzlichen Beispielen wird sie recht schnell besser.
    [0]https://faculty.washington.edu/wobbrock/pubs/uist-07.01.pdf , Seite 8
  • Ich habe es selbst ausprobiert, und zumindest ohne Training war es ziemlich schlecht.
    Mein gezeichnetes Rechteck wurde als Caret erkannt, mein Zickzack als geschweifte Klammer.
    Formen, die man mit zwei Strichen zeichnet, wie Pfeile, werden ebenfalls nicht unterstützt.
  • Nach kurzem Ausprobieren wirkte es zu simpel. Wenn man die Beispielform nicht exakt nachzeichnet, werden sie miteinander verwechselt.
    Ein guter Test dafür, wie schlecht die Leistung ist, ist der Vergleich der Beispielformen „delete“ und „x“.
    Als Ausgangspunkt für ein Gesten-Interface, das erwartet, dass man Formen jedes Mal auf dieselbe Weise zeichnet, ist es okay; für den hier behandelten Zweck der Diagrammerstellung passt es aber nicht gut.
  • Ich stimme zu, dass es für etwas wirklich Einfaches viel zu gut funktioniert.
    Für ein Uni-Projekt habe ich eine ES6-Implementierung gebaut; falls es jemanden interessiert, hier ist sie: https://github.com/gurgunday/onedollar-unistroke-es6

• Ich verstehe die Beschreibung, dass „selbst eine einfache gerade Linie, die mit Maus oder Trackpad gezeichnet wurde, wie die Spur eines betrunkenen Eichhörnchens aussehen kann“, aber ich weiß nicht, wer in Canva Formen direkt mit der Maus zeichnen soll.
  Früher hatte Miro eine Funktion, die eine grob mit der Maus gezeichnete Sternform in einen geometrisch korrekten Stern, Kreis, ein Dreieck usw. umwandelte; ich fand das cool, habe es aber in der Praxis nie gebraucht.
  Beim Erstellen von Diagrammen ist es schneller, vorbereitete Formen zu verwenden; beim Erstellen von Icons nutzt man eher einen separaten Workflow mit booleschen Operationen, Verschieben von Punkten und dem Pen-Tool, meist in einem spezialisierten Programm wie Illustrator.
  Wenn ich echte Illustrationen zeichne, hole ich ein Tablet heraus; die Technik selbst ist also cool, aber ich frage mich, was der Use Case ist.

  • Canva ist kein Diagramm-Tool, sondern ein visuelles Design-Tool mit einer ziemlich anderen Nutzerbasis.
    Die Asset-Bibliothek ist riesig und enthält Millionen, vielleicht sogar Dutzende Millionen Bilder, darunter Fotos und Vektorgrafiken.
    Nach meiner begrenzten Nutzungserfahrung war es besonders nervig, die endlose Bibliothek durchsuchen zu müssen, obwohl ich schon genau wusste, welche einfache Form ich wollte; dieses Tool scheint wahrscheinlich diesen Schmerz zu lindern.
    Ich habe vor ein paar Jahren bei Canva gearbeitet.
    Ich habe keinerlei Insiderinformationen, aber da Canva offenbar auch ein wettbewerbsfähiges Diagramm-Tool werden will, könnte dieser Use Case wichtig sein. Allerdings dürfte es die Einschränkung geben, dass man die Designerfahrung von 99 % der heutigen Nutzer nicht grundlegend verändern kann.
  • Für Designer oder Marketer, die keine Tastenkürzel lernen, ist „eine Form mit der Maus zeichnen“ schnell, während „durch halb fertige Menüs gehen, die passende Form auswählen und platzieren und dann die Größe anpassen“ langsamer ist.
    Selbst wenn die Form ohne Menü direkt verfügbar ist, kann es schneller sein, alles mit einem einzigen Cursor zu zeichnen, als mehrere Icons zu platzieren und zu skalieren, dann zur Pfeilfunktion zu wechseln und Pfeile hinzuzufügen.

• Auch die Bibliothek, die Canva fürs Zeichnen von Linien verwendet, könnte interessant sein: https://github.com/steveruizok/perfect-freehand

  • Canva scheint kein Sponsor zu sein.

• Der Teil, dass sie „eine Variante des Ramer-Douglas-Peucker(RDP)-Algorithmus entwickelt“ haben, erinnerte mich an ein altes Nebenprojekt.
  In einem Strange Loop-Vortrag von 2018 habe ich Douglas-Peucker auf Picasso angewendet.
  Picasso's Bulls: Deconstructing his design process with Python
  https://rrherr.github.io/picasso/

• Ich frage mich, wie Macromedia Flash vor weit über 20 Jahren etwas Ähnliches hinbekommen hat.
  Die CPU-Leistung war damals deutlich begrenzter als heute, und ich erinnere mich noch lebhaft daran, wie überrascht ich war, als beim Zeichnen von Freihandkurven die Linien geglättet wurden.

  • LeCun und Kollegen erreichten 1995 bei der Erkennung handgeschriebener Ziffern eine Genauigkeit von über 99 %, was der Erkennung von Formen recht ähnlich ist.
    Trotzdem ist es nach wie vor eine Leistung, so etwas leichtgewichtig und schnell im Browser laufen zu lassen. Am Ende zählt immer die User Experience.
  • Beim Apple Newton von 1993 war diese Funktion selbst mit einem 20-MHz-ARM-Prozessor ein Kernfeature.
    https://en.wikipedia.org/wiki/MessagePad#User_interface
  • Glättung ist ein separater Schritt, bei dem nahezu redundante Punkte aus Bézierkurven entfernt werden, um sie zu vereinfachen.
    Wenn beim Zeichnen einer fast geraden Linie 100 Kontrollpunkte entstehen, reduziert die Software sie etwa auf vier Punkte.
  • Vermutlich wurden zunächst Mausereignisse entgegengenommen und die Ereignispunkte mit geraden Linien verbunden. Auf Hardware der 1990er war das Zeichnen gerader Linien schnell, und weil schnell gezeichnet werden musste, war das wohl nötig.
    Nach Abschluss des Zeichnens wurden wahrscheinlich dieselben Punkte als Eingabe verwendet, um die Linie mit einem Spline-Kurven-Algorithmus neu zu zeichnen.
    Die Berechnung des Splines selbst ist nicht unbedingt viel schwieriger, aber entscheidend ist, dass sich beim Hinzufügen eines Punkts am Ende ein Teil der bereits gezeichneten Linie ändert.
    Dann muss alles hinter dieser Linie neu gezeichnet werden, was rechenintensiv ist und sich schwer zuverlässig mit 60 fps garantieren lässt.

• Guter Artikel, und die Arbeit ist sehr interessant.
  Das ist sicher Geschmackssache, aber seltsamerweise gefällt mir dieses wackelige, handgezeichnete Kritzelgefühl besser als glatte Vektorgrafik.
  Natürlich kann die Präferenz je nach Kontext unterschiedlich sein, also ist die Funktion an sich großartig. In einer Welt voller künstlicher Perfektion gibt es etwas, das einen grundsätzlich zu echten handgezeichneten Ergebnissen hinzieht.

• Wenn man so eine Funktion implementiert, sollte sie unbedingt optional sein und klar erkennbar machen, wenn sie aktiviert ist.
  Wenn ein Tool zu sehr so tut, als wäre es clever, dann aber nicht perfekt trifft, macht mich das wirklich wütend. Ich habe solche Fehler selbst schon gemacht.

• Ein paar Jahre vor dem jüngsten Machine-Learning-/AI-Hype gab es ein Spiel namens Scribblenauts, das Kinder liebten; es verwandelte sehr grobe Kritzeleien in erstaunlich viele verschiedene Objekte.
  Ich weiß nicht, wie es das gemacht hat, aber ich war beeindruckt, und Kinder hielten es für Magie.
  https://store.steampowered.com/app/218680/Scribblenauts_Unli...

  • Ich habe es gespielt, und es war wirklich erstaunlich. Wenn ich mich richtig erinnere, gab es das wohl auch für iOS.

• Ich wünschte, das wäre Open Source.
  In letzter Zeit kommen mehrere kleine Modelle heraus. Dieses Modell ist 250 KB groß, und bei einfachen Aufgaben wie dem Fine-Tuning großer Modelle gab es auch Modelle von etwa 50 KB.
  Ich freue mich auf den Zeitpunkt, an dem kleine Modelle in nützlichen Anwendungen wieder tatsächlich eingesetzt werden können.

• Ein Pentagramm und ein funkelnder Stern sind nicht dasselbe. Ist das ein Beispiel für Underfitting?

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