论文推荐|[TMM 2021]Instance GNN: 联机手写示意图符号分割与识别学习框架

本文简要介绍近期发表于IEEE Transactions on Multimedia (TMM) 的论文“Instance GNN: A Learning Framework for Joint Symbol Segmentation and Recognition in Online Handwritten Diagrams”，论文作者来自中国科学院自动化所模式识别国家重点实验室。该论文提出了一种基于实例图神经网络的联机手写示意图符号分割与识别方法。同时，该论文发布了一个迄今为止规模最大的带有标记信息的联机手写流程图数据集CASIA-OHFC。

一、研究背景

手写方式作为人类最自然的信息记录方式，具有书写自由、无需理会排版等优点，其效率和直观性都远远优于传统的键盘输入。随着智能手机、平板电脑、电子白板及电子手写笔的广泛普及，在智能电子设备上记录信息成为一种重要的信息记录形式。这些信息通常以联机手写文档（Online Handwritten Document）形式（也即数字墨水形式）保存。与常见的扫描图像不同的是，联机手写文档由一系列有序的笔画轨迹点组成，具有高度的稀疏性以及丰富的动态信息等特性。目前，自动识别与理解联机手写文档得到学术界与产业界越来越多的关注。手写示意图识别的目的是将图中有一定含义的符号（如流程框、箭头、文字等）分割出来并标出符号的类别和符号之间的关系，以便恢复成标准形式的结构化印刷示意图。尽管取得一定的进展，然而，由于其结构复杂性、内容多样性（图文混杂，包含文字、数学公式、表格、流程图以及其他类型的示意图等）、书写风格多样性以及大规模标记数据的缺乏，诸如流程图、电路图、音乐符号等手写示意图（这些文档通常包含图形符号以及文本）的识别依然是一个挑战。联机手写示意图（Online Handwritten Diagrams）作为联机手写文档中常见的元素，广泛应用于多个领域，如人机交互、教育、办公自动化以及会议系统等。

联机手写示意图识别与理解涉及两个相互依赖的任务：符号分割，即将整个示意图中的笔画划分为一系列具有一定语义的符号；符号识别，即将分割所得符号进行分类。现存的联机手写示意图符号分割与识别算法大致可分为自底向上与自顶向下两类。自底向上方法首先进行符号分割，之后进行符号识别。与此相对应，自顶向下方法将上述两个步骤集成在一个框架之下，同时进行符号分割与识别。这些方法大都采用传统的机器学习方法，在学习高层表示以及建模复杂结构方面存在一定的局限性，而这对于高精度的手写示意图识别具有重要意义。

二、方法简述

本文提出了一个基于实例图神经网络的联机手写文档符号分割与识别框架。该方法将联机手写文档建模为时空关系图，用以表示笔画之间的时序关系以及空间关系，通过节点和边分类可以对符号进行实例分割和识别。具体地，将笔画建模为图中的节点，而将笔画之间的相互关系建模为边。之后，通过特征工程方法，从原始文档中每个笔画提取27维描述笔画几何形状、方向、尺度等属性的特征作为节点的初始表示，提取19维笔画间时间空间关系作为边的初始表示。通过将笔画分类问题形式化为节点分类，将符号分割与识别建模为图中节点聚类或边分类问题，采用多任务学习的图神经网络架构同时进行笔画分类、符号分割与识别。整个系统的架构如下图1所示，其由特征提取与时空关系图构建、InstGNN模型（Instance Graph Neural Network，InstGNN）以及后处理三个模块组成。下文将对InstGNN模型进行详细介绍。

图1 本文提出的联机手写示意图识别框架。黄色的线表示边信息流，蓝色的线表示节点信息流。

本文将每个文档表示为时空关系图（Space-Time Relationship Graph，STRG）。在STRG中，图中的节点表示笔画，边表示笔画与在空间上及时间上的相互关系。生成的图表示为，其中为节点集，为边集。每个节点与边均由一个实数特征向量来描述。对于图中边的构建，本文采用时间K近邻法及空间K近邻法。

本文提出的实例图神经网络模型（InstGNN）由许多节点学习层及边学习层构成。具体而言，InstGNN由一个共享的骨干网络及三个交互连接分支组成，这三个分支分别完成节点分类、边分类及节点表示学习任务。骨干网络、节点分类分支、节点表示学习分支均由节点学习层组成，而边分类分支由一系列边学习层组成。

每个节点学习层及边学习层的输入包括一系列节点特征，， 与边特征，其中，|V|表示图中的节点数目，P、Q分别表示节点特征及边特征的维度。节点学习层对输入的边特征及节点特征融合后输出新的节点特征，，为输出的节点特征维度。类似地，每个边学习层对输入的边特征及节点特征融合后输出新的边特征，，其中，为输出的边特征维度。下文将对边学习层以及节点学习层的具体实现进行详细的描述。

• 节点学习层

节点学习层中，每个节点通过注意力机制聚合其邻居节点的特征，从而更新自己的原有表示。首先，我们采用自我注意力机制来度量节点与的相似性，

除了经典的自我注意力机制，我们引入了边注意力机制，利用边的特征来度量邻居的重要性：

由于上述注意力系数在不同的节点之间无法比较，我们使用softmax函数对它们进行归一化，从而可得归一化的注意力权重如下：

其中，N(i)表示节点的邻居节点。

通过多头注意力权重聚合邻居节点的特征，可得节点学习层的输出特征如下：

上式中，表示由第k个注意力头计算所得的归一化的注意力权重，K为注意力头的数目。

在最后一层节点学习层中，我们采用均值池化来得到学习层的输出，并且去除了非线性变换：

• 边学习层

直觉上，如果不同符号之间边的表示与同一符号内边的表示清晰可分，则可以通过边分类，将整个文档划分为一系列符号。受此启发，我们设计了一个独立的边学习层来显式地学习边表示，计算公式如下：

上式中，W为可学习参数矩阵。

• 损失函数

InstGNN的三个分支分别完成节点分类（Node Classification，NC）、边分类（EdgeClassification，EC）以及节点嵌入学习（Node Embedding Learning，NE）任务。为了同时求解这三个任务，本文提出如下的节点分类损失、边分类损失以及节点嵌入损失以及联合损失函数。节点分类与边分类损失均为加权交叉熵损失，而嵌入损失有如下三项组成：（1）符号间方差项，目标是使得属于相同符号的笔画的嵌入之间的距离足够小；（2）符号内距离项，使得不同符号之间的嵌入相互远离；（3）正则项，用以约束节点嵌入的幅值。从而，可得嵌入损失的形式化定义如下：

在网络训练中，本文同时优化节点分类、边分类以及节点嵌入任务，总的损失函数定义如下：

三、主要实验结果及可视化结果

网络训练完毕之后，便可以对文档中的笔画以及笔画之间的相互关系进行预测。在得到InstGNN的输出后，本文提出三种不同的方法来产生最终的符号分割与识别结果：基于边分类的方法（InstGNN-EC）、基于节点嵌入的方法（InstGNN-NE）以及这两者结合的方法（InstGNN）。下表1，2，3展示了在两个公开的联机手写流程图数据集FC_A、FC_B以及一个有限自动机数据集FA上的实验结果。本文提出的三种方法均取得了最优或与当前最优结果相当的性能。在提出的三种方法中，InstGNN在所有三个数据集上取得了最佳性能且大幅度地超越先前的方法。图2展示了采用InstGNN方法在FC_A数据集上得到的一些识别结果样例。 

表1 FC_A数据集上的实验结果。本文报告了整体（Overall）以及类别平均（Avg.）的笔画分类准确率（Stroke Classification Accuracy, SCA）以及符号识别召回（Symbol Recognition Recall, SRR）。

 表2 FC_B数据集上的实验结果

 表3 FA数据集上的实验结果

图2  采用InstGNN方法，在FC_A数据集上， 存在识别错误的流程图样例。（a） 一个“text”分割正确，但却被识别为“connection”。（b）两个“arrow”被错误地分割为一个。（c）“decision”中一个笔画被错误分类为“arrow”，从而导致“decision”识别不正确。

四、总结

本文提出了一种新颖的基于图神经网络的联机手写示意图识别框架InstGNN。将联机手写文档建模为时空关系图，将笔画建模为图中节点，将笔画之间在时间与空间上的关系建模为边，使用传统手工特征作为节点与边的初始表示，通过设计节点分类、边分类、节点特征联合学习的多任务图神经网络架构，同时完成笔画分类、符号分割与识别等任务。通过在公开流程图数据集FC_A、FC_B，有限自动机基准数据集 FA 上进行大量的实验，本文提出的方法显著地超越先前的方法并取得目前最优的性能。通过一系列对比实验，验证了InstGNN各个模块的作用与功能。此外，本文构建了一个公开的大规模的联机手写流程图数据集CASIA-OHFC，并在该数据集上下进行了一系列基准实验。

五、相关资源

• 联机手写流程图数据集CASIA-OHFC地址：
  http://www.nlpr.ia.ac.cn/databases/CASIA-OHFC

• 论文地址：
  https://ieeexplore.ieee.org/document/9447983

---

原文作者: Xiaolong Yun，Yanming Zhang，Fei Yin，and ChengLin Liu

撰稿：云小龙编排：高 学审校：连宙辉发布：金连文

---

免责声明：（1）本文仅代表撰稿者观点，撰稿者不一定是原文作者，其个人理解及总结不一定准确及全面，论文完整思想及论点应以原论文为准。（2）本文观点不代表本公众号立场。 

往期精彩内容回顾

征稿启事：本公众号将不定期介绍文档图像分析与识别及相关领域的论文、数据集、代码等成果，欢迎自荐或推荐相关领域最新论文/代码/数据集等成果给本公众号审阅编排后发布。

扫描二维码，关注我们: