Canva Ship Shape: Shape Assist yang Mengubah Bentuk Gambar Tangan Menjadi Vektor

• Shape Assist dari Canva adalah fitur di Draw tool yang mengenali bentuk goresan tunggal yang digambar tidak rapi di dalam browser dan mengubahnya menjadi grafik vektor yang rapi
• Heuristik visi komputer yang bergantung pada aturan dan ambang batas bisa digunakan untuk persegi, lingkaran, dan segitiga, tetapi memiliki keterbatasan untuk bentuk yang lebih kompleks seperti awan, bintang, dan hati, serta saat menambahkan bentuk baru
• Model memperlakukan goresan sebagai urutan koordinat x·y, bukan gambar, dan untuk eksekusi di klien memilih arsitektur berbasis RNN/LSTM serta kode inferensi kustom alih-alih CNN
• Model akhir terdiri dari satu lapisan LSTM dan lapisan Gemm dengan konfigurasi P = 25, H = 100, N = 9, memiliki 64,109 parameter dan ukuran sekitar 250KB, serta berjalan dalam kurang dari 10ms di laptop modern
• Sistem bekerja tanpa perjalanan bolak-balik ke server, tetapi dirancang agar hanya mengganti bentuk secara otomatis ketika pengguna menahan kursor selama lebih dari 1 detik setelah menggambar dan hasilnya cukup cocok dengan bentuk yang telah ditentukan sebelumnya

---

Peran Draw tool dan Shape Assist

• Draw tool dari Canva memungkinkan pengguna menambahkan gambar buatan tangan langsung ke desain
• Shape Assist dibuat untuk mengubah coretan tangan yang goyah menjadi grafik vektor yang lebih halus
• Karena latensi klasifikasi adalah syarat penting, Canva memilih eksekusi di dalam browser alih-alih pemrosesan di server
  • Pengguna bisa langsung mendapat umpan balik saat menggambar bentuk
  • Dapat menghindari latensi yang muncul pada pemrosesan berbasis server
  • Bisa digunakan secara offline tanpa koneksi internet yang terus aktif

Alasan beralih dari heuristik ke model ML

• Shape Assist versi awal menggunakan heuristik visi komputer yang menganalisis sifat geometris dari koordinat yang digambar pengguna
  • Mendeteksi bentuk tertentu seperti persegi, lingkaran, dan segitiga dengan aturan dan ambang batas
  • Koordinat dianalisis sebagai titik dalam sistem koordinat Kartesius
• Ini bekerja untuk pengenalan bentuk dasar, tetapi sulit menambahkan bentuk baru atau menangani bentuk yang lebih kompleks
  • Implementasi awal dibatasi pada bentuk yang bisa digambar dengan satu goresan
  • Daftar bentuk yang diusulkan mencakup awan, bintang, dan hati, yang sulit ditangani dengan pendekatan heuristik
• Model ML dapat mempelajari beragam gaya dan variasi dari dataset gambar tangan pengguna, sehingga memungkinkan Shape Assist diperluas ke bentuk yang lebih kompleks, melampaui bentuk geometris sederhana

Data gambar tangan dan representasi berbasis koordinat

• Canva mengumpulkan data gambar tangan pengguna melalui UI sederhana untuk menggambar bentuk satu goresan
• Setiap goresan dicatat sebagai urutan koordinat x·y
  • Pendekatan ini lebih fleksibel untuk prapemrosesan dan augmentasi data dibanding menyimpan bentuk sebagai gambar biner
  • Pada pendekatan berbasis gambar, augmentasi spasial seperti pembalikan, rotasi, dan shear bisa diterapkan
  • Pada pendekatan berbasis koordinat, augmentasi seperti penghapusan koordinat secara acak, guncangan acak pada posisi titik, dan pembalikan urutan titik juga dimungkinkan
• Meski hanya dengan data sukarelawan sudah terkumpul dataset yang cukup besar, gambar dari engineer dan desainer tidak mewakili rata-rata pengguna Canva dengan baik
  • Engineer ML cenderung memberikan data yang bersifat adversarial
  • Gambar dari desainer terlalu bagus, sehingga sebagian diminta menggambar dengan tangan yang tidak dominan
  • Setelah memberikan panduan dan ekspektasi yang lebih ketat, Canva berhasil memperoleh dataset yang cukup besar

Desain model dan metode pelatihan

• Model harus berjalan di klien dan tidak boleh berdampak buruk pada waktu muat halaman, sehingga ukurannya harus diperkecil semaksimal mungkin
• Alih-alih CNN yang mengharuskan titik dikonversi menjadi piksel, Canva bereksperimen dengan RNN yang langsung menggunakan koordinat x·y dari goresan
• Canva melakukan pencarian hyperparameter untuk menemukan sifat model yang optimal
  • Parameter seperti ukuran input, jumlah lapisan, dan jumlah fitur pada hidden state disesuaikan
• Kecepatan menggambar berbeda-beda untuk tiap pengguna, sehingga panjang daftar titik bisa berbeda meski bentuknya sama
  • Pengguna yang menggambar lambat meninggalkan lebih banyak titik
  • Pengguna yang menggambar cepat meninggalkan lebih sedikit titik
• Untuk menetapkan jumlah titik yang tetap, bisa saja digunakan interpolasi linear per interval dengan distribusi seragam, tetapi hal ini menyebabkan hilangnya detail karena titik penting terhapus
• Sebagai gantinya, Canva mengembangkan varian dari algoritme Ramer-Douglas-Peucker
  • RDP adalah algoritme penyederhanaan kurva yang mengurangi jumlah titik sambil mempertahankan detail penting pada kurva
  • Algoritme ini secara rekursif menghapus titik-titik yang tidak menyimpang secara bermakna dari kurva yang telah disederhanakan

Metode klasifikasi untuk mengurangi penggantian otomatis yang salah

• Shape Assist tidak boleh melakukan penggantian otomatis jika gambar tangan tidak cukup mirip dengan salah satu kelas yang telah ditentukan sebelumnya
• Karena hanya satu bentuk yang bisa menjadi jawaban benar, aktivasi softmax dan loss cross-entropy tampak sebagai pilihan yang alami
  • Pendekatannya adalah menolak prediksi jika tingkat keyakinan kelas dengan probabilitas tertinggi berada di bawah ambang batas
• Namun, pada pendekatan ini model tetap menunjukkan keyakinan tinggi bahkan saat salah
• Pada akhirnya, model dilatih sebagai pengklasifikasi multi-kelas dan multi-label yang menggunakan aktivasi sigmoid pada setiap kelas output
  • Jika tidak ada kelas yang melampaui ambang batas, prediksi ditolak

Arsitektur inferensi di klien

• Model ML biasanya besar dan membutuhkan banyak komputasi, sehingga sering dijalankan di komputer cloud yang kuat
• Model Shape Assist kecil dan membutuhkan operasi matematika yang sedikit, sehingga semua pemrosesan bisa dijalankan di dalam aplikasi klien
• Pendekatan ini menghilangkan kebutuhan koneksi ke server dan menghapus waktu bolak-balik ke server, sehingga bentuk bisa dikenali hampir seketika

Arsitektur model dan ukuran

• Model akhir memiliki struktur satu lapisan LSTM yang diikuti lapisan Gemm
  • Gemm juga disebut lapisan Dense atau Fully Connected
• Nilai konfigurasi utamanya adalah sebagai berikut
  • Jumlah titik hasil interpolasi: P = 25
  • Hidden size: H = 100
  • Jumlah bentuk yang telah ditentukan sebelumnya: N = 9
• Jumlah parameter dihitung sebagai berikut
  • LSTM: 4H * 2 + 4H * H + 8H = 41,600
  • Gemm: P * H * N + N = 22,509
  • Total: 64,109
• Dengan standar floating point IEEE754 32-bit yang memakai 4 byte per parameter, ukuran model sekitar 250KB
  • Ukurannya mirip dengan satu gambar 360p 16:9 tanpa kompresi
  • Ukuran ini berpotensi diperkecil lagi jika parameter disimpan dengan presisi lebih rendah
• Canva mengimplementasikan sendiri operasi LSTM dan Gemm langsung dalam TypeScript alih-alih memakai engine ML umum
  • Pendekatan ini tidak mudah digeneralisasi ke model yang lebih kompleks
  • Implementasinya kurang dari 300 baris
  • Berjalan dalam kurang dari 10ms di laptop modern

Penggantian dan penyelarasan bentuk

• Setelah model mengidentifikasi bentuk gambar tangan, Canva menyesuaikan jalur gambar tangan ke representasi grafik vektor menggunakan pendekatan template matching
• Proses penyelarasan dilakukan setelah bentuk input dan bentuk template dinormalisasi
  • Bentuk template dicoba dengan rotasi dalam kelipatan 15°
  • Momen orde pertama dan kedua dari titik input dihitung dalam ruang koordinat yang telah diputar
  • Ketakmiripan antara titik input dan bentuk template dihitung
  • Rotasi dengan ketakmiripan paling kecil dipilih sebagai sudut optimal
• Jika setelah menggambar bentuk pengguna menahan kursor tetap di tempat selama minimal 1 detik, Shape Assist akan mengganti bentuk tersebut bila cukup cocok dengan bentuk yang telah ditentukan sebelumnya

[GN⁺]

Komentar Hacker News

• Untuk masalah ini, recurrent neural network (RNN) rasanya berlebihan; $1 unistroke recognizer yang sederhana dan elegan tampaknya lebih tepat
  Cukup melatih satu sampel untuk tiap gesture saja sudah bekerja lumayan baik, dan pada proyek apa pun bisa dipasang dalam setengah hari untuk membuat UI terasa lebih akrab lewat pengenalan gesture
  Jika tiap huruf dibuat dengan satu goresan, ini juga bekerja cukup stabil untuk input teks Graffiti ala Palm, dan makalah aslinya pun ditulis dengan mudah dibaca dan dipahami
  https://depts.washington.edu/acelab/proj/dollar/index.html

  • Masalah besar $1 recognizer adalah goresan harus digambar dengan cara tertentu
    Misalnya saat menggambar lingkaran, harus digambar berlawanan arah jarum jam; jika digambar searah jarum jam yang terasa lebih alami, ia dikenali sebagai caret
    Dalam konteks menggambar bebas, saat pengguna tidak tahu detail implementasinya, ini sulit dipakai secara nyata
  • Hal yang terlewat oleh orang-orang yang menguji contoh di halaman ini dan melaporkan kesalahan adalah bahwa demo ini hanya “dilatih” dengan satu contoh
    Makalah yang ditautkan[0] membahas tingkat kesalahan, dan hanya dengan menambahkan beberapa contoh lagi hasilnya membaik cukup cepat
    [0]https://faculty.washington.edu/wobbrock/pubs/uist-07.01.pdf , halaman 8
  • Setelah mencobanya sendiri, setidaknya tanpa pelatihan hasilnya cukup buruk
    Persegi yang saya gambar dikenali sebagai caret, dan zigzag sebagai kurung kurawal
    Ia juga tidak mendukung bentuk yang digambar dengan dua goresan seperti panah
  • Setelah sebentar dipakai, ini terlalu sederhana. Kalau tidak menggambar persis mengikuti bentuk contoh, bentuk-bentuknya saling tertukar
    Membandingkan bentuk contoh “delete” dan “x” adalah cara bagus untuk melihat seberapa buruk performanya
    Mungkin oke sebagai titik awal antarmuka gesture yang mengharapkan pengguna selalu menggambar bentuk dengan cara yang sama, tetapi kurang cocok untuk keperluan pembuatan diagram yang dibahas di sini
  • Saya setuju bahwa untuk sesuatu yang benar-benar sederhana, ini bekerja terlalu baik
    Saya pernah membuat implementasi ES6 sebagai proyek kuliah; kalau berminat ada di sini: https://github.com/gurgunday/onedollar-unistroke-es6

• Saya paham penjelasan bahwa “bahkan garis lurus sederhana yang digambar dengan mouse atau trackpad bisa terlihat seperti jejak tupai mabuk”, tetapi saya tidak tahu siapa di Canva yang perlu menggambar bentuk langsung dengan mouse
  Dulu Miro punya fitur yang mengubah bintang yang digambar asal-asalan dengan mouse menjadi bintang, lingkaran, segitiga, dan sebagainya yang akurat secara geometris, dan saya pikir itu keren, tetapi dalam praktiknya saya tidak pernah membutuhkannya
  Saat membuat diagram, memakai bentuk yang sudah disiapkan biasanya lebih cepat; saat membuat ikon, workflow terpisah yang berpusat pada operasi Boolean, memindahkan titik, dan Pen tool dipakai, biasanya menggunakan program khusus seperti Illustrator
  Saat menggambar ilustrasi sungguhan, saya akan mengeluarkan tablet, jadi meski teknologinya sendiri keren, saya penasaran apa use case-nya

  • Canva bukan alat diagram, melainkan alat desain visual dengan basis pengguna yang cukup berbeda
    Pustaka asetnya sangat besar dan berisi jutaan, mungkin puluhan juta, gambar termasuk foto dan grafik vektor
    Dari pengalaman saya yang terbatas, hal yang sangat menjengkelkan adalah harus menelusuri pustaka yang tak ada habisnya meski sudah tahu persis bentuk sederhana yang diinginkan, dan alat ini mungkin dimaksudkan untuk mengurangi rasa sakit itu
    Saya pernah bekerja di Canva beberapa tahun lalu
    Saya sama sekali tidak punya informasi internal, tetapi karena Canva juga ingin menjadi alat diagram yang kompetitif, use case ini bisa jadi penting. Namun sepertinya ada batasan bahwa pengalaman desain 99% pengguna saat ini tidak bisa diubah secara mendasar
  • Bagi desainer atau marketer yang tidak mempelajari shortcut keyboard, “menggambar bentuk dengan mouse” itu cepat, sementara “melewati menu yang setengah matang untuk memilih dan menempatkan bentuk yang sesuai lalu mengubah ukurannya” lebih lambat
    Sekalipun bentuknya langsung tersedia tanpa menu, menggambar semuanya dengan satu kursor bisa lebih cepat daripada menempatkan dan mengubah ukuran beberapa ikon lalu beralih ke fitur panah untuk menambahkan panah

• Library yang dipakai Canva untuk menggambar garis juga mungkin menarik: https://github.com/steveruizok/perfect-freehand

  • Sepertinya Canva bukan sponsornya

• Bagian “kami mengembangkan variasi algoritma Ramer-Douglas-Peucker (RDP)” mengingatkan saya pada side project lama
  Dalam presentasi Strange Loop 2018, saya menerapkan Douglas-Peucker pada Picasso
  Picasso's Bulls: Deconstructing his design process with Python
  https://rrherr.github.io/picasso/

• Jadi penasaran bagaimana Macromedia Flash melakukan hal serupa lebih dari 20 tahun lalu
  Saat itu performa CPU jauh lebih terbatas dibanding sekarang, tetapi saya masih ingat jelas betapa terkejutnya melihat kurva bebas yang digambar lalu dirapikan menjadi mulus

  • LeCun dan rekan-rekannya pada 1995 mencapai akurasi lebih dari 99% dalam pengenalan angka tulisan tangan, dan ini cukup mirip dengan identifikasi bentuk
    Meski begitu, membuatnya berjalan ringan dan cepat di browser tetap merupakan pencapaian. Pada akhirnya, yang selalu penting adalah pengalaman pengguna
  • Pada 1993, Apple Newton menjadikan fitur ini sebagai fitur inti meski hanya memakai prosesor ARM 20MHz
    https://en.wikipedia.org/wiki/MessagePad#User_interface
  • Smoothing adalah pekerjaan terpisah: menyederhanakan kurva Bézier dengan menghapus titik-titik yang hampir redundan
    Misalnya ketika Anda menggambar garis yang nyaris lurus lalu muncul 100 titik kontrol, perangkat lunak akan menguranginya menjadi sekitar 4 titik
  • Mungkin awalnya ia menerima event mouse lalu menggambar dengan menghubungkan event-event itu menggunakan garis lurus. Pada perangkat keras era 1990-an, menggambar garis lurus itu cepat, dan karena harus digambar cepat, ini mungkin memang diperlukan
    Setelah proses menggambar selesai, kemungkinan garis digambar ulang dengan algoritma kurva spline memakai titik-titik yang sama sebagai masukan
    Perhitungan untuk menggambar spline sendiri tidak jauh lebih sulit, tetapi poin pentingnya adalah saat satu titik ditambahkan di ujung, sebagian garis yang sudah digambar ikut berubah
    Itu berarti semua yang berada di belakang garis tersebut harus digambar ulang, sehingga biaya komputasinya besar dan sulit menjamin bisa diproses secara konsisten pada 60fps

• Tulisan yang bagus dan pekerjaannya juga sangat menarik
  Mungkin ini selera minoritas, tetapi anehnya saya merasa nuansa coretan tangan yang goyah lebih menarik daripada grafis vektor yang mulus
  Tentu preferensi bisa berubah tergantung konteks, jadi fiturnya sendiri tetap keren. Di dunia yang dipenuhi kesempurnaan artifisial, ada sisi yang secara mendasar tertarik pada hasil gambar tangan yang asli

• Kalau mengimplementasikan fitur seperti ini, saya harap fitur itu dibuat opsional dan terlihat jelas saat aktif
  Kalau sebuah alat terlalu sok pintar tetapi tidak bisa menebak dengan sempurna, itu benar-benar menjengkelkan. Saya juga pernah membuat kesalahan seperti itu

• Beberapa tahun sebelum tren machine learning/AI belakangan ini, ada game bernama Scribblenauts yang disukai anak-anak; game itu mengubah coretan yang sangat kasar menjadi berbagai macam objek dengan cara yang mengejutkan
  Saya tidak tahu bagaimana caranya, tetapi saya juga kagum, dan anak-anak menganggapnya seperti sihir
  https://store.steampowered.com/app/218680/Scribblenauts_Unli...

  • Saya pernah mencobanya dan memang luar biasa. Kalau ingatan saya benar, sepertinya juga pernah dirilis untuk iOS

• Saya berharap ini open source
  Belakangan ini ada beberapa model berukuran kecil yang muncul. Model ini 250KB, dan untuk tugas sederhana fine-tuning model besar, ada juga model sekitar 50KB
  Saya menantikan saat model kecil benar-benar bisa dipakai lagi dalam aplikasi yang berguna

• Bintang berujung lima dan bintang berkilau bukanlah hal yang sama. Apakah ini contoh underfitting?

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