HMER论文系列
1、论文阅读和分析：When Counting Meets HMER Counting-Aware Network for HMER_KPer_Yang的博客-CSDN博客
2、论文阅读和分析：Syntax-Aware Network for Handwritten Mathematical Expression Recognition_KPer_Yang的博客-CSDN博客
3、论文阅读和分析：A Tree-Structured Decoder for Image-to-Markup Generation_KPer_Yang的博客-CSDN博客
4、 论文阅读和分析：Watch, attend and parse An end-to-end neural network based approach to HMER_KPer_Yang的博客-CSDN博客
5、 论文阅读和分析：Multi-Scale Attention with Dense Encoder for Handwritten Mathematical Expression Recognition_KPer_Yang的博客-CSDN博客
6、 论文阅读和分析：Mathematical formula recognition using graph grammar_KPer_Yang的博客-CSDN博客
7、 论文阅读和分析：Hybrid Mathematical Symbol Recognition using Support Vector Machines_KPer_Yang的博客-CSDN博客
8、论文阅读和分析：HMM-BASED HANDWRITTEN SYMBOL RECOGNITION USING ON-LINE AND OFF-LINE FEATURES_KPer_Yang的博客-CSDN博客

Mathematical formula recognition using graph grammar

主要工作：

1、第一次实现Ofr(Optical Formula Recognition)系统，提取和识别数学表达式；

2、三个部分：OCR、构建图、解析图到语法树；

3、使用压缩子图成为一个节点的方法，自底向上解析图；

架构：

在ocr识别公式的字符后，得到字符的特征；

特征包括：符号、bounding box、baseline、size：

例如$x^2+y^2$：

对图的定义

顶点vertex：$V(t,v,i)$三元组：

​ - $t$：lexical type 符号类型：例如"Operator" , "Variable’ , ‘Digit’,etc.

​ - $v$：值，代表数学表达式 例如$x,Plus(x,(Mult(2,y))),etc$.

​ - $i$：标识，区分同一个表达式中的相同符号但是出现在不同地方；

边edge：$E(t,v_1,v_2)$:

​ - $v_1、v_2$：顶点

​ - $t$：边的类型。二元组$L(d,w)$：$d$：图的方向：例如’Left". ‘Right’, ‘Top’, etc。$w$：权重，使用在平面上的相关关系进行编码；

图graph：一些列边的集合
{ E ( t 1 , v 11 , v 2 , 1 ) , … , E ( t n , v 1 n , v 2 , n ) } . \{E(t_1,v_{11},v_{2,1}),\ldots,E(t_n,v_{1n},v_{2,n})\}. {E(t1​,v11​,v2,1​),…,E(tn​,v1n​,v2,n​)}.

使用符号规则（Lexer rules）构建图；

定义符号的方向：left(l)、right®、top(t)、bottom(b)、top-left(tl)、bottom-left(bl)、top-right(tr)、bottom-right(br)、in(i)

规则1：符号的类型规则，对每种类型指定可以连接的类型；例如：

规则2：顺序规则，基于left->right的顺序，比如像top-left 或者 bottom-right是比较接近的，使用引力等势场来描述，如下图所示：（相当于计算节点的weight），可以看到横向的关系可能会很长。

a grid like structure to be able to have a good algorithm complexity

使用语法规则（grammar rules）解析图到语法树；

核心思路：自底向上将图进行压缩，不断把子图压缩到一个节点，最后得到公式的符号表示。

给一个公式的图表示（边、顶点），规则尝试通过使用顶点（顶点的值是被识别的子公式）重写它的子图（不断坍缩子图到节点）。过程使用匹配和替换方式。

图转换到节点的规则：

​ - $V$：节点，叫做规则的production；

​ - $G$：图，叫做规则的pattern；

​ - $C$：graphs的有限集合； 叫做规则的context；

grammer：一个规则rules的有限集合；

匹配和替换过程：

• 替换是$T(F,V)$的自同态（endomorphism），即$\sigma f(t_1,\dots ,t_n)=f(\sigma t_1,\dots \sigma t_n)$对于所有的$f$和所有的terms：$t_1,\dots ,t_n$，一个$\sigma$是唯一被确定的。
• 一个$t$匹配$t^{\prime }$,注意是$t\le t^{\prime }$，当且仅当替换$\sigma$满足$\sigma t=t^{\prime }$.

匹配有限集被定义成：
{ t 1 , … , t n } ≤ { t 1 ′ , … , t m ′ } ⇔ ∃ σ { σ t 1 , … , σ t n } = { t 1 ′ , … , t m ′ } \{t_1,\dots,t_n\}\leq\{t_1',\dots,t_m'\}\Leftrightarrow\exists\sigma\{\sigma t_1,\dots,\sigma t_n\}=\{t_1',\dotsc,t_m'\}\quad {t1​,…,tn​}≤{t1′​,…,tm′​}⇔∃σ{σt1​,…,σtn​}={t1′​,…,tm′​}
一个规则$r=V\leftarrow G,$，$C$重写一个图$G_1$到一个图$G_2$ ,记作$G_1{\to }_r{G}_2$，当且仅当存在替换$\sigma$，一个$G$的子图$G^{\prime }$，得：

• $\sigma G=G^{\prime }.$；

• 对于contex $C$的所有图$H$，没有替换$\tau$ such that${\tau }_{|Var(G)}={\sigma }_{|Var(G)}\text{and}\tau H\subset G_1.$

• $G_2$是由$G^{\prime }$坍缩得到的$\sigma V$，即是移除$G_1$属于$G^{\prime }$所有的边和使用$\sigma V$替换属于$G^{\prime }$顶点

注：消除歧义的情况，对于一个导致歧义的图语法，在其规则中添加上下文，尽可能自动地消除这些歧义。