论文阅读和分析:Mathematical formula recognition using graph grammar
Mathematical formula recognition using graph grammar
主要工作:
1、第一次实现Ofr(Optical Formula Recognition)系统,提取和识别数学表达式;
2、三个部分:OCR、构建图、解析图到语法树;
3、使用压缩子图成为一个节点的方法,自底向上解析图;
架构:
在ocr识别公式的字符后,得到字符的特征;
特征包括:符号、bounding box、baseline、size:
例如 x 2 + y 2 x^2+y^2 x2+y2:
对图的定义
顶点vertex: V ( t , v , i ) V(t,v,i) V(t,v,i)三元组:
- t t t:lexical type 符号类型:例如"Operator" , "Variable’ , ‘Digit’,etc.
- v v v:值,代表数学表达式 例如 x , P l u s ( x , ( M u l t ( 2 , y ) ) ) , e t c x, Plus(x, (Mult(2, y))), etc x,Plus(x,(Mult(2,y))),etc.
- i i i:标识,区分同一个表达式中的相同符号但是出现在不同地方;
边edge: E ( t , v 1 , v 2 ) E(t,v_1,v_2) E(t,v1,v2):
- v 1 、 v 2 v_1、v_2 v1、v2:顶点
- t t t:边的类型。二元组 L ( d , w ) L(d,w) L(d,w): d d d:图的方向:例如’Left". ‘Right’, ‘Top’, etc。 w w 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 V V:节点,叫做规则的production;
- G G G:图,叫做规则的pattern;
- C C C:graphs的有限集合; 叫做规则的context;
grammer:一个规则rules的有限集合;
匹配和替换过程:
- 替换是 T ( F , V ) T(F,V) T(F,V)的自同态(endomorphism),即 σ f ( t 1 , … , t n ) = f ( σ t 1 , … σ t n ) sigma f(t_{1},ldots,t_{n})=f(sigma t_{1},ldotssigma t_{n}) σf(t1,…,tn)=f(σt1,…σtn)对于所有的 f f f和所有的terms: t 1 , … , t n t_1,dots,t_n t1,…,tn,一个 σ sigma σ是唯一被确定的。
- 一个 t t t匹配 t ′ t^{prime} t′,注意是 t ≤ t ′ tleq t' t≤t′,当且仅当替换 σ sigma σ满足 σ t = t ′ sigma t=t^{prime} σt=t′.
匹配有限集被定义成:
{
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'}Leftrightarrowexistssigma{sigma t_1,dots,sigma t_n}={t_1',dotsc,t_m'}quad
{t1,…,tn}≤{t1′,…,tm′}⇔∃σ{σt1,…,σtn}={t1′,…,tm′}
一个规则
r
=
V
←
G
,
r=Vleftarrow G,
r=V←G,,
C
C
C重写一个图
G
1
G_1
G1到一个图
G
2
G_2
G2 ,记作
G
1
→
r
G
2
G_1
ightarrow_r G_2
G1→rG2,当且仅当存在替换
σ
sigma
σ,一个
G
G
G的子图
G
′
G^{prime}
G′,得:
-
σ G = G ′ . sigma G=G^{prime}. σG=G′.;
-
对于contex C C C的所有图 H H H,没有替换 τ au τ such that τ ∣ V a r ( G ) = σ ∣ V a r ( G ) and τ H ⊂ G 1 . au_{|Var(G)}=sigma_{|Var(G)} ext{and} au Hsubset G_1. τ∣Var(G)=σ∣Var(G)andτH⊂G1.
-
G 2 G_2 G2是由 G ′ G^{prime} G′坍缩得到的 σ V sigma V σV,即是移除 G 1 G_1 G1属于 G ′ G^{prime} G′所有的边和使用 σ V sigma V σV替换属于 G ′ G^{prime} G′顶点
注:消除歧义的情况,对于一个导致歧义的图语法,在其规则中添加上下文,尽可能自动地消除这些歧义。
相关文章
- 物联网技术应用机遇与挑战并存,该如何突破困局?
- [当人工智能遇上安全] 3.安全领域中的机器学习及机器学习恶意请求识别案例分享
- [当人工智能遇上安全] 4.基于机器学习的恶意代码检测技术详解
- 腾讯企点×GITA2021营销节 | 新制造时代的to B发展趋势:营销协同
- 案例|深圳机场:新一代机场服务平台
- 腾讯云前端性能优化大赛火热招募中
- 11月腾讯云微服务&中间件产品动态
- [AI安全论文] 03.什么是生成对抗网络?GAN的前世今生(Goodfellow)
- [AI安全论文] 04.NLP知识简单总结及NLP论文撰写之道——Pvop老师
- [AI安全论文] 05.RAID-Cyber Threat Intelligence Modeling Based on GCN
- [AI安全论文] 06.NDSS20 UNICORN: Provenance-Based Detector for APTs
- 腾讯云微搭低代码栅格布局介绍
- 腾讯多媒体自由视角技术首次亮相中国网媒论坛
- [AI安全论文] 07.S&P19 HOLMES:基于可疑信息流相关性的实时APT检测
- 智慧灯杆解决方案
- 工业互联网平台激发经济高质量发展新动能
- 爬虫和马甲工具
- 【Python100天学习笔记】Day15 图像和办公文档处理
- 小白入门机器学习的三个问题
- Turla PowerShell攻击手法学习