Click I Love Computer Vision to star and get faster access to new CVML technologies
This article introduces a relatively niche but very interesting new paper on hand-drawn sketch recognition “Multi-Graph Transformer for Free-Hand Sketch Recognition”, which essentially proposes a novel Transformer network.
Author information:
All authors are from Nanyang Technological University.
I. Research Motivation
Typically, the input to a Transformer is in a serialized format. When a sentence is given as input, the Transformer allows establishing attention relationships among all words in the sentence. Essentially, the Transformer views each input sentence as a fully-connected graph, thus it can be considered a special type of Graph Neural Network (GNN). However, how to inject prior knowledge into the Transformer to guide it in learning structural patterns on the graph more precisely is a question worth pondering. This paper proposes using hand-drawn sketches as an experimental bed for GNN to explore a novel Transformer network.
Hand-drawn sketches (free-hand sketches) are a special type of data, essentially a dynamic serialized data format. The process of drawing itself is a “connecting points to form lines” process (as shown in Figure 1(b)).
Figure 1: Schematic understanding of the discretization of hand-drawn sketches
Existing research on hand-drawn sketches has modeled them in Euclidean space, where hand-drawn sketches are understood as static images input into CNNs or as sequences of coordinates of key points of strokes input into RNNs.
However, in human-computer interaction scenarios where real-time performance is crucial, storing and transmitting images incurs significant overhead, making the storage and transmission of stroke key point coordinates a better choice. The main motivation of this text is to represent hand-drawn sketches as sparse graphs, understanding stroke key points as nodes (nodes), and using Transformers to model them in geometric space, to understand and represent hand-drawn sketches from a more universal perspective.
Through experiments, this paper found and confirmed that the original Transformer (Vanilla Transformer) cannot reasonably represent hand-drawn sketches. Therefore, this paper proposes a novel Graph Neural Network, namely Multi-Graph Transformer (MGT) architecture, which represents each hand-drawn sketch as multiple graph structures (multiple graph structures), integrating domain knowledge of hand-drawn sketches into these graph structures (as shown in Figures 1(b) and 1(c)).
The Multi-Graph Transformer network proposed in this paper can also be used for modeling other structured and serialized data.
II. Multi-Graph Transformer (MGT)
The network structure proposed in this paper can be divided into three parts:
(1) The input layer of the network;
(2) The backbone of the network, which is a multi-layer Multi-Graph Transformer structure;
(3) The output layer of the network, which is a classifier.
2.1 Multi-Modal Input Layer
This paper uses the Google QuickDraw dataset, taking the first 100 key points of each hand-drawn sketch, truncating (truncation) sketches with more than 100 key points or padding (padding) those with fewer than 100 key points. Each node is represented as a 4-dimensional vector, where the first two dimensions are the x and y coordinates of the node on the canvas, the third dimension is a flag to describe the pen state, and the fourth dimension is the position encoding. The x and y coordinates are elevated through a linear layer, while the flag and position encoding are elevated through an embedding layer, and they are concatenated to form the input of MGT.
Figure 2: Structure diagram of the Multi-Graph Transformer network
2.2 Multi-Graph Transformer
As shown in Figure 2, overall, the Multi-Graph Transformer (MGT) proposed in this paper is an L-layer structure, with each layer consisting of two sub-layers, namely the Multi-Graph Multi-Head Attention (MGMHA) sub-layer and the position-wise fully connected Feed-Forward (FF) sub-layer.
The MGMHA sub-layer proposed in this paper is a multi-path parallel structure, where each path is a graph-structured Multi-Head Attention module. The “graph” structure here is defined by the domain knowledge of hand-drawn sketches, which is the various adjacency matrices defined in the original text. These adjacency matrices are used to describe the connectivity between nodes on each hand-drawn sketch.
Furthermore, in the Multi-Head Attention operation, the connectivity described by the adjacency matrices is used to control the connectivity in the attention score matrix, allowing or masking specific attention relationships between nodes.
The FF sub-layer mainly performs operations such as residual connections and BN, which will not be elaborated on here.
2.3 Sketch Embedding and Classification Layer
Given a sketch, after passing through MGT, each node will be represented as a vector, and the vector representation of these nodes will be summed to form the vector representation of the sketch. During the summation process, additional nodes introduced during the padding operation in the data preprocessing phase are not considered. The classifier at the end of the network is implemented using a multi-layer perceptron, utilizing the softmax cross-entropy loss function.
III. Experiments
The paper provides a performance comparison of MGT with numerous classic RNN structures and CNN networks, as well as detailed ablation study results and visualizations. Although the truncation operation in the data preprocessing phase determines that CNN is the performance upper bound for MGT, the recognition accuracy achieved by MGT not only far exceeds that of networks based on LSTM and GRU but also surpasses many classic CNN networks, being only slightly lower than Inception V3 and MobileNet V2.
Table 1: Test set performance of MGT vs. the state-of-the-art RNN and CNN architectures. The 1st/2nd/3rd best results per column are indicated in red/blue/magenta.
The following figure provides a visual analysis, inputting a sketch of a clock into the trained MGT, and obtaining corresponding attention weights (attention heads) after each layer. Some representative heads are selected here. It can be seen that in the initial layers, heads focus more on local areas, and message passing unfolds along the strokes. In higher layers, local attention gradually diminishes, and the model is aggregating relationships on the graph from a global perspective.
At the same time, the attention heads learned based on global graph structure prior knowledge are also crucial for cross-stroke message passing, for example, capturing the relationship between the body and feet of the clock.
Figure 3: Visualization of attention weights
IV. Conclusion
This paper proposes a novel Graph Neural Network, namely Multi-Graph Transformer (MGT), and also presents a novel representation method for hand-drawn sketches, representing each hand-drawn sketch as multiple sparsely connected graphs. The main characteristics of the proposed MGT network include:
(1) It can simultaneously model the geometric structure information and stroke timing information in hand-drawn sketches;
(2) It injects domain knowledge into the Transformer structure through predefined various graph structures;
(3) It fully utilizes the global and local graph structures of hand-drawn sketches, namely the multiple graph structures within and between strokes.
It is hoped that this text can help scholars in the hand-drawn sketch field model hand-drawn data from a more universal geometric space perspective, while also helping scholars in the graph neural network field treat hand-drawn data as a new type of experimental data bed.
Paper link:
https://arxiv.org/pdf/1912.11258.pdf
Code link:
https://github.com/PengBoXiangShang/multigraph_transformer
Hand-Drawn Sketch Recognition Communication Group
To provide a more professional communication platform for those engaged in or interested in hand-drawn sketch recognition research in China, CV君 has invited the authors of this paper to establish a communication group. You are welcome to scan the QR code to add CV君 to pull you into the group (if you are already friends with CV君’s other accounts, please message directly).
(Please be sure to specify: Hand-Drawn Sketch)
For those who prefer to communicate on QQ, you can join the official QQ group: 805388940.
(I may not be online all the time, so please forgive me if I cannot verify you promptly)
Long press to follow I Love Computer Vision