- O Shape Assist do Canva é um recurso que reconhece, dentro do navegador, formas desenhadas com um único traço no Draw tool, mesmo que saiam tremidas, e as transforma em gráficos vetoriais limpos
- Heurísticas de visão computacional baseadas em regras e limiares funcionavam para retângulos, círculos e triângulos, mas tinham limitações com formas mais complexas como nuvens, estrelas e corações, além de dificultarem a adição de novas formas
- O modelo trata o traço não como imagem, mas como uma sequência de coordenadas x·y, e para rodar no cliente optou por uma arquitetura baseada em RNN/LSTM e código de inferência customizado em vez de CNN
- O modelo final é composto por uma única camada LSTM e uma camada Gemm com configuração
P = 25,H = 100,N = 9, totalizando64.109parâmetros e cerca de 250KB, com execução em menos de 10ms em notebooks modernos - Ele funciona sem ida e volta ao servidor, mas foi projetado para substituir automaticamente a forma apenas quando o usuário mantém o cursor parado por mais de 1 segundo após desenhá-la e quando há correspondência suficiente com uma forma predefinida
O papel do Draw tool e do Shape Assist
- O Draw tool do Canva permite que o usuário adicione desenhos feitos à mão diretamente a um design
- O Shape Assist foi criado para transformar rabiscos com tremor em gráficos vetoriais mais suaves
- Como a latência de classificação era um requisito importante, foi escolhida a execução no navegador em vez de processamento no servidor
- O usuário pode receber feedback assim que desenha a forma
- É possível evitar a latência causada pelo processamento baseado em servidor
- Também pode ser usado offline, sem conexão contínua com a internet
Por que migrar de heurísticas para um modelo de ML
- As primeiras versões do Shape Assist usavam heurísticas de visão computacional que analisavam propriedades geométricas das coordenadas desenhadas pelo usuário
- Formas específicas, como retângulos, círculos e triângulos, eram detectadas com regras e limiares
- As coordenadas eram analisadas como pontos em um sistema cartesiano
- Isso funcionava para reconhecer formas básicas, mas dificultava adicionar novas formas ou lidar com desenhos mais complexos
- A implementação inicial era limitada a formas que podiam ser desenhadas com um único traço
- A lista de formas sugeridas incluía nuvens, estrelas e corações, difíceis de tratar com a abordagem heurística
- Um modelo de ML podia aprender diferentes estilos e variações a partir de um conjunto de dados de desenhos à mão dos usuários, permitindo expandir o Shape Assist para além de formas geométricas simples
Dados de desenho à mão e representação baseada em coordenadas
- O Canva coletou dados de desenhos à mão dos usuários com uma interface simples para desenhar formas de traço único
- Cada traço era registrado como uma sequência de coordenadas x·y
- Essa abordagem oferece mais flexibilidade para pré-processamento e aumento de dados do que armazenar a forma como imagem binária
- Em uma abordagem baseada em imagem, é possível aplicar aumentos espaciais como espelhamento, rotação e cisalhamento
- Em uma abordagem baseada em coordenadas, também é possível aplicar aumentos como remoção aleatória de coordenadas, tremor aleatório na posição dos pontos e inversão da ordem dos pontos
- Mesmo só com dados de voluntários, foi possível reunir um conjunto considerável, mas os desenhos de engenheiros e designers não representavam bem o usuário médio do Canva
- Engenheiros de ML tendiam a fornecer dados adversariais
- Os desenhos dos designers eram bons demais, então alguns foram orientados a desenhar com a mão não dominante
- Depois de fornecer diretrizes e expectativas mais rígidas, o Canva conseguiu reunir um conjunto de dados substancial
Projeto do modelo e método de treinamento
- Como o modelo precisava rodar no cliente e não podia afetar negativamente o tempo de carregamento da página, seu tamanho precisava ser mínimo
- Em vez de uma CNN, que exigiria converter pontos em pixels, o Canva experimentou uma RNN usando diretamente as coordenadas x·y do traço
- Foi realizada uma busca de hiperparâmetros para encontrar as melhores propriedades do modelo
- Foram ajustados parâmetros como tamanho de entrada, número de camadas e quantidade de atributos do hidden state
- Como cada usuário desenha em velocidades diferentes, até a mesma forma pode gerar listas de pontos com comprimentos distintos
- Usuários que desenham devagar deixam mais pontos
- Usuários que desenham rápido deixam menos pontos
- Era possível fixar a quantidade de pontos com interpolação linear por intervalos de distribuição uniforme, mas isso removia pontos importantes e causava perda de detalhes
- Em vez disso, o Canva desenvolveu uma variação do algoritmo Ramer-Douglas-Peucker
- O RDP é um algoritmo de simplificação de curvas que reduz o número de pontos preservando os detalhes importantes da curva
- Ele remove recursivamente pontos que não se desviam de forma significativa da curva simplificada
Método de classificação para reduzir substituições automáticas incorretas
- O Shape Assist não deveria substituir automaticamente o desenho se ele não fosse suficientemente parecido com uma das classes predefinidas
- Como apenas uma forma poderia ser a resposta correta, a ativação softmax com perda cross-entropy parecia uma escolha natural
- A ideia era rejeitar a previsão quando a confiança da classe de maior probabilidade ficasse abaixo de um limiar
- Mas nessa abordagem o modelo ainda apresentava alta confiança mesmo quando errava
- No fim, o modelo foi treinado como um classificador multiclasse e multirrótulo com ativação sigmoid em cada classe de saída
- Se nenhuma classe ultrapassar o limiar, a previsão é rejeitada
Arquitetura de inferência no cliente
- Modelos de ML normalmente são grandes e exigem muito processamento, por isso costumam rodar em máquinas poderosas na nuvem
- O modelo do Shape Assist é pequeno e envolve poucas operações matemáticas, então todo o processamento pode rodar dentro da aplicação cliente
- Isso elimina a necessidade de conexão com o servidor e remove o tempo de ida e volta, permitindo reconhecer formas quase instantaneamente
Arquitetura do modelo e tamanho
- O modelo final tem uma única camada LSTM seguida por uma camada Gemm
- Gemm também é chamada de camada Dense ou Fully Connected
- Os principais valores de configuração são os seguintes
- Número de pontos interpolados:
P = 25 - hidden size:
H = 100 - Número de formas predefinidas:
N = 9
- Número de pontos interpolados:
- A quantidade de parâmetros é calculada assim
- LSTM:
4H * 2 + 4H * H + 8H = 41,600 - Gemm:
P * H * N + N = 22,509 - Total:
64,109
- LSTM:
- Considerando 4 bytes por parâmetro no padrão de ponto flutuante IEEE754 de 32 bits, o tamanho do modelo fica em cerca de 250KB
- É comparável ao tamanho de uma imagem 360p 16:9 sem compressão
- Pode ser reduzido ainda mais se os parâmetros forem armazenados com precisão menor
- Em vez de usar um engine de ML genérico, o Canva implementou diretamente em TypeScript as operações de LSTM e Gemm
- Essa abordagem não generaliza bem para modelos mais complexos
- A implementação tem menos de 300 linhas
- Ela roda em menos de 10ms em notebooks modernos
Substituição e alinhamento de formas
- Depois que o modelo identifica a forma desenhada à mão, o Canva ajusta o caminho do desenho à sua representação vetorial com uma abordagem de template matching
- O processo de alinhamento acontece após a normalização da forma de entrada e da forma de template
- A forma de template é rotacionada em tentativas de 15°
- No espaço de coordenadas rotacionado, são calculados os momentos de primeira e segunda ordem dos pontos de entrada
- É calculada a dissimilaridade entre os pontos de entrada e a forma de template
- A rotação com menor dissimilaridade é escolhida como ângulo ideal
- Se, após desenhar a forma, o usuário mantiver o cursor parado no mesmo lugar por pelo menos 1 segundo, o Shape Assist substitui a forma quando houver correspondência suficiente com uma forma predefinida
1 comentários
Opiniões no Hacker News
Acho que redes neurais recorrentes (RNNs) são exagero para esse problema, e o simples e elegante $1 unistroke recognizer parece mais adequado
Mesmo treinando com apenas uma amostra por gesto, ele funciona razoavelmente bem, e dá para integrar em qualquer projeto em uma tarde para tornar a UI mais amigável com reconhecimento de gestos
Se cada letra for um único traço, ele também funciona de forma bastante estável para entrada de texto Graffiti, no estilo Palm, e o artigo original também é fácil de ler e bem claro
https://depts.washington.edu/acelab/proj/dollar/index.html
Por exemplo, ao desenhar um círculo, você precisa fazê-lo no sentido anti-horário; se desenhar no sentido horário, que parece mais natural, ele é reconhecido como um acento circunflexo
Em um contexto de desenho livre, em que o usuário não conhece os detalhes da implementação, é difícil usar na prática
O artigo linkado[0] trata da taxa de erro, e ela melhora bem rapidamente com apenas mais alguns exemplos
[0]https://faculty.washington.edu/wobbrock/pubs/uist-07.01.pdf , página 8
O retângulo que desenhei foi reconhecido como um acento circunflexo, e o zigue-zague como uma chave
Também não dá suporte a formas desenhadas com dois traços, como setas
Comparar as formas de exemplo “delete” e “x” é uma boa forma de ver como o desempenho é ruim
Pode ser um bom ponto de partida para uma interface gestual que espera que você desenhe as formas sempre do mesmo jeito, mas não se encaixa bem no uso de criação de diagramas discutido aqui
Fiz uma implementação em ES6 como projeto de faculdade; se houver interesse, está aqui: https://github.com/gurgunday/onedollar-unistroke-es6
Entendo a explicação de que “até uma linha reta simples traçada com mouse ou trackpad pode parecer o caminho percorrido por um esquilo bêbado”, mas não sei quem, no Canva, precisa desenhar formas à mão com o mouse
Antigamente, o Miro tinha um recurso que transformava uma estrela desenhada de qualquer jeito com o mouse em uma estrela, um círculo, um triângulo etc. geometricamente corretos, e eu achava isso legal, mas na prática nunca precisei usar
Ao criar diagramas, é mais rápido usar formas prontas; ao criar ícones, uso um fluxo de trabalho separado, centrado em operações booleanas, movimentação de pontos e a ferramenta Pen, normalmente em um programa dedicado como o Illustrator
Quando desenho ilustrações de verdade, pego um tablet, então, embora a tecnologia em si seja legal, fico curioso sobre qual é o caso de uso
A biblioteca de assets é imensa e tem milhões, talvez dezenas de milhões, de imagens, incluindo fotos e gráficos vetoriais
Pela minha experiência limitada, era especialmente irritante ter que pesquisar em uma biblioteca interminável mesmo quando eu já sabia exatamente a forma simples que queria; esta ferramenta provavelmente tenta reduzir essa dor
Trabalhei no Canva alguns anos atrás
Não tenho nenhuma informação interna, mas, como o Canva também quer ser uma ferramenta de diagramas competitiva, esse caso de uso pode ser importante. Dito isso, deve haver a restrição de não poder mudar fundamentalmente a experiência de design de 99% dos usuários atuais
Mesmo que a forma esteja disponível diretamente, sem menu, desenhar tudo com um único cursor pode ser mais rápido do que posicionar e redimensionar vários ícones e depois trocar para a função de seta para adicionar uma seta
A biblioteca que o Canva usa para desenhar linhas também pode ser interessante: https://github.com/steveruizok/perfect-freehand
A parte que diz que “desenvolvemos uma variação do algoritmo Ramer-Douglas-Peucker (RDP)” me lembrou um antigo projeto paralelo
Em uma apresentação no Strange Loop em 2018, apliquei Douglas-Peucker ao Picasso
Picasso's Bulls: Deconstructing his design process with Python
https://rrherr.github.io/picasso/
Fico curioso para saber como o Macromedia Flash conseguiu fazer algo parecido há bem mais de 20 anos
Na época, o desempenho das CPUs era muito mais limitado do que hoje, e lembro nitidamente de ficar impressionado ao ver as curvas sendo suavizadas ao desenhar linhas livres
Ainda assim, fazer isso rodar de forma leve e rápida no navegador continua sendo uma conquista. No fim, o que importa é sempre a experiência do usuário
https://en.wikipedia.org/wiki/MessagePad#User_interface
Se, ao desenhar uma linha quase reta, surgissem 100 pontos de controle, o software os reduziria para algo como 4 pontos
Quando o desenho terminava, ele devia redesenhar a linha usando os mesmos pontos como entrada para um algoritmo de curvas spline
O cálculo para desenhar splines em si não é muito mais difícil, mas o ponto importante é que, ao adicionar um ponto no fim, parte da linha já desenhada muda
Isso obriga a redesenhar tudo que está atrás daquela linha, o que tem um custo computacional alto e dificulta garantir que tudo rode com segurança a 60 fps
É um bom texto, e o trabalho é muito interessante
Pode ser um gosto de nicho, mas, curiosamente, eu prefiro a sensação trêmula de rabisco feito à mão a gráficos vetoriais lisos
Claro que a preferência pode mudar conforme o contexto, então o recurso em si é ótimo. Num mundo cheio de perfeição artificial, há algo que nos atrai essencialmente em resultados realmente desenhados à mão
Se forem implementar esse recurso, espero que ele seja definitivamente opcional e que fique claro quando estiver ativado
Quando uma ferramenta tenta ser esperta demais e não acerta perfeitamente, isso dá muita raiva. Eu mesmo já cometi esse erro
Alguns anos antes da moda recente de machine learning/IA, havia um jogo chamado Scribblenauts, que as crianças adoravam, e que transformava rabiscos muito grosseiros em uma variedade surpreendente de objetos
Não sei como fazia isso, mas eu também fiquei impressionado, e as crianças achavam que era magia
https://store.steampowered.com/app/218680/Scribblenauts_Unli...
Seria bom se isso fosse open source
Ultimamente têm aparecido vários modelos pequenos. Este modelo tem 250 KB, e, em tarefas simples de ajuste fino de modelos grandes, já vi modelos de cerca de 50 KB
Estou ansioso pelo momento em que pequenos modelos voltem a poder ser usados de fato em aplicações úteis
Um pentagrama e uma estrela brilhante não são a mesma coisa. Isso é um exemplo de subajuste?