Using BLSTM for interpretation of 2-D languages:Case of handwritten mathematical expressions

Ting Zhang; Harold Mouchère; Christian Viard-Gaudin

Document numérique 2016/2-3 Vol. 19

Article de revue

Using BLSTM for interpretation of 2-D languages

Case of handwritten mathematical expressions

Pages 135 à 157

Figure 1

Description de l'image par IA : Réseau récurrent unidirectionnel avec couches d'entrée, cachée et de sortie, vecteurs de probabilités et séquences temporelles.

L'image représente un réseau récurrent unidirectionnel déplié. Elle montre une séquence d'entrée sur une ligne horizontale avec des points temporels étiquetés t_{i-1}, t_{i}, et t_{i+1}. Chaque point temporel est connecté à une couche d'entrée composée de cercles vides. Au-dessus de la couche d'entrée, il y a une couche cachée avec des cercles contenant des sinusoïdes, indiquant des unités de traitement. Chaque unité de la couche cachée est connectée à l'unité suivante par des flèches étiquetées w2, représentant les poids des connexions. Au-dessus de la couche cachée, il y a une couche de sortie avec des cercles contenant des sinusoïdes similaires, mais ces cercles sont également connectés à des vecteurs de probabilités. Chaque vecteur de probabilités est étiqueté avec des probabilités pour différentes classes (class_1 et class_2) à différents points temporels. Les flèches entre les couches montrent le flux de données à travers le réseau, de la couche d'entrée à la couche cachée, puis à la couche de sortie. Le temps progresse de gauche à droite, indiquant un traitement séquentiel des données d'entrée.

An unfolded single-directional recurrent network

Figure 2

Description de l'image par IA : Bloc de mémoire LSTM avec une cellule, portes d'entrée, sortie et oubli, connexions entre les composants.

L'image représente un bloc de mémoire LSTM (Long Short-Term Memory) avec une seule cellule. Le bloc est structuré avec une cellule centrale, étiquetée "Cell", qui est entourée de divers éléments interconnectés. À gauche de la cellule, il y a une porte d'entrée avec une étiquette "Input Gate". À droite, il y a une porte d'oubli avec une étiquette "Forget Gate". Au-dessus de la cellule, il y a une porte de sortie avec une étiquette "Output Gate". Chaque porte est représentée par un cercle avec des flèches indiquant les connexions et les interactions entre les portes et la cellule centrale. Les flèches montrent les flux d'information et les interactions dynamiques entre les différentes portes et la cellule. Les portes d'entrée et de sortie sont reliées à la cellule par des flèches pointant vers et à partir de celle-ci, indiquant les informations qui entrent et sortent de la cellule. La porte d'oubli est connectée à la cellule par des flèches bidirectionnelles, suggérant qu'elle contrôle quelles informations doivent être conservées ou oubliées. L'ensemble du bloc est encadré dans un rectangle étiqueté "Block".

LSTM memory block with one cell, figure extracted from (Graves et al., 2012)

Figure 3

Description de l'image par IA : Deux arbres de relations de symboles avec des flèches et des labels "Au-dessus" et "En dessous".

L'image montre deux diagrammes de relations de symboles (SRT) étiquetés (a) et (b). Chaque diagramme représente des relations entre différents symboles. Dans le diagramme (a), il y a quatre symboles : un signe moins (-), une lettre "a", un signe plus (+), et une lettre "b". Les relations entre ces symboles sont indiquées par des flèches et des étiquettes. Une flèche part du signe moins (-) et pointe vers la lettre "a" avec l'étiquette "Above" (Au-dessus). Une autre flèche part de la lettre "a" et pointe vers le signe plus (+) avec l'étiquette "R" (Relation droite). Une autre flèche part du signe plus (+) et pointe vers la lettre "b" avec l'étiquette "R" (Relation droite). Enfin, une flèche part du signe moins (-) et pointe vers la lettre "c" avec l'étiquette "Below" (En dessous). Dans le diagramme (b), il y a également quatre symboles : la lettre "a", un signe plus (+), un signe moins (-), et la lettre "b". Les relations entre ces symboles sont indiquées par des flèches et des étiquettes. Une flèche part de la lettre "a" et pointe vers le signe plus (+) avec l'étiquette "R" (Relation droite). Une autre flèche part du signe plus (+) et pointe vers le signe moins (-) avec l'étiquette "R" (Relation droite). Une autre flèche part du signe moins (-) et pointe vers la lettre "b" avec l'étiquette "Above" (Au-dessus). Enfin, une flèche part du signe moins (-) et pointe vers la lettre "c" avec l'étiquette "Below" (En dessous). Les relations entre les symboles sont représentées par des flèches avec des étiquettes "R" pour les relations de gauche à droite et "Above" ou "Below" pour les relations de positionnement vertical.

The symbol relation tree (SRT) for (a) and (b) ’R’ is for left-right relationship

Figure 4

Description de l'image par IA : Deux écritures de "2 2" avec quatre traits, leurs relations et leur SLG.

L'image contient trois parties étiquetées (a), (b) et (c). Dans la partie (a), il y a deux représentations visuelles de la manière dont le caractère "2 2" est écrit. La première représentation montre quatre traits nommés s1, s2, s3 et s4 dans l'ordre d'écriture. La deuxième représentation montre les mêmes traits avec des flèches indiquant la direction des mouvements pour chaque trait. Dans la partie (b), il y a un diagramme de l'arbre des relations des symboles pour "2 2". Ce diagramme montre comment les traits s1, s2, s3 et s4 sont liés entre eux. Les traits s1 et s4 sont reliés à un nœud central qui représente la combinaison des traits s2 et s3. Dans la partie (c), il y a un diagramme de la Structure de Ligne Graphique (SLG) pour "2 2". Ce diagramme montre les relations entre les traits s1, s2, s3 et s4. Les traits s1 et s4 sont reliés à un nœud central étiqueté "ver." (vertical) qui est à son tour relié à un autre nœud étiqueté "hor." (horizontal). Les flèches indiquent les directions des relations entre les nœuds. Les relations entre les traits sont indiquées par "R" pour la relation gauche-droite. Les traits verticaux et horizontaux sont différenciés par les étiquettes "ver." et "hor." respectivement.

(a) ’2 + 2’ written with four strokes; (b) the symbol relation tree of ’2 + 2’; (c) the SLG of ’2 + 2’. The four strokes are indicated as s1, s2, s3, s4 in writing order. (ver.) and (hor.) are added to differentiate the vertical and the horizontal strokes for ’+’. ’R’ is for left-right relationship

Figure 5

Description de l'image par IA : Trois diagrammes avec des cercles et des flèches, des étiquettes "ver", "hor", "R", et des chemins temporels en rouge et bleu.

L'image contient trois diagrammes étiquetés (a), (b) et (c), représentant des chemins temporels et des graphes simplifiés (SLG). Dans le diagramme (a), trois cercles sont connectés par des flèches et des lignes. Les cercles sont étiquetés "s1", "s2" (ver), "s3" (hor) et "s4". Les flèches sont marquées "R" et "i+". Une ligne rouge traverse le diagramme, indiquant le chemin temporel dans le SLG. Dans le diagramme (b), trois cercles sont également connectés par des flèches. Les cercles sont étiquetés "s1", "s2" (ver) et "s3" (hor). Une flèche est marquée "i+" et une autre "R". Le chemin temporel est représenté par une ligne droite. Dans le diagramme (c), trois cercles sont connectés par des flèches et des lignes. Les cercles sont étiquetés "s1", "s2" (ver) et "s3" (hor). Les flèches sont marquées "R" et "i+". Les lignes ajoutées sont représentées en gras, indiquant les modifications apportées au SLG. Les flèches et les lignes montrent les relations et les transitions entre les différents états ou nœuds dans les graphes.

(a) The time path (red) in SLG; (b) the time path; (c) the built SLG of ’2 + 2’, added edges are depicted as bold

Figure 6

Description de l'image par IA : Descriptions de diagrammes de traçage et de SRT pour les caractères Peo et r2h.

L'image contient quatre sous-images étiquetées (a), (b), (c) et (d). Sous-image (a) montre un caractère écrit avec quatre traits. Les traits sont numérotés de s1 à s4. Le trait s1 est une ligne horizontale, le trait s2 est une boucle, le trait s3 est une autre boucle et le trait s4 est une ligne courbe. Sous-image (b) représente le SRT (Séquence de Reconnaissance de Tracé) du caractère Peo. Il y a trois cercles reliés par des flèches. Le cercle P est relié au cercle E par une flèche étiquetée "Superscript". Le cercle E est relié au cercle O par une flèche étiquetée "R". Sous-image (c) montre un autre caractère écrit avec trois traits. Les traits sont numérotés de s1 à s3. Le trait s1 est une boucle, le trait s2 est une autre boucle et le trait s3 est une ligne courbe. Sous-image (d) représente le SRT du caractère r2h. Il y a quatre cercles reliés par des flèches. Le cercle r est relié au cercle 2 par une flèche étiquetée "Superscript". Le cercle r est relié au cercle h par une flèche rouge étiquetée "R".

(a) Peo written with four strokes; (b) the SRT of Peo; (c) r2h written with three strokes; (d) the SRT of r2h, the red edge cannot be generated by the time sequence of strokes

Figure 7

Description de l'image par IA : Points bleus et rouges en mouvement, numérotés de 1 à 11.

The illustration of on-paper points (blue) and in-air points (red) in time path, a1 + a2 written with 6 strokes

Figure 8

Description de l'image par IA : Le diagramme montre une séquence de points avec des étiquettes et des boucles entre les points "vide" et "fin".

L'image représente un diagramme de flux avec plusieurs nœuds et flèches indiquant des séquences possibles de points étiquetés dans une seule course. Le diagramme commence par un nœud intitulé "start" (début) et se termine par un nœud intitulé "end" (fin). Entre ces deux nœuds, il y a trois nœuds intermédiaires étiquetés "blank" (vide) et "label". Les flèches montrent les directions possibles de progression entre ces nœuds. Les nœuds "blank" et "label" ont des flèches qui pointent vers eux-mêmes, indiquant qu'une action peut se répéter. Il y a également des flèches qui montrent des transitions entre les nœuds "blank" et "label", ainsi que des boucles entre les nœuds "start" et "blank", et entre "blank" et "end". Ce diagramme illustre les différentes étapes et répétitions possibles dans une seule course de points étiquetés.

The possible sequences of point labels in one stroke

Figure 9

Description de l'image par IA : Cercle noir étiquettes, blanc vide, flèches transitions autorisées, mise à jour avant-arrière.

L'image représente un algorithme de reconnaissance de séquence utilisant le Local CTC (Connectionist Temporal Classification) forward-backward. Les cercles noirs représentent des étiquettes tandis que les cercles blancs représentent des blancs. Les flèches indiquent les transitions autorisées. Les variables forward sont mises à jour dans le sens des flèches, et les variables backward sont mises à jour dans le sens inverse des flèches. Les lignes horizontales marquées par des traits rouges indiquent différentes "strokes" ou séquences nommées '2', 'R' et 'a'. Les numéros en bas de l'image (1 à 14) représentent les étapes temporelles. Les cercles gris et blancs sont disposés en grille, et les flèches montrent les chemins possibles entre ces cercles. Les annotations "a(T, U'-1)" et "a(T, U')" indiquent des positions spécifiques dans la séquence temporelle.

Local CTC forward-backward algorithm. Black circles represent labels and white circles represent blanks. Arrows signify allowed transitions. Forward variables are updated in the direction of the arrows, and backward variables are updated in the reverse direction

Figure 10

Description de l'image par IA : Illustration montrant l'étiquetage des traits pour une meilleure lisibilité, chaque trait est étiqueté correctement sauf le trait 6.

L'image montre une illustration pour la décision de l'étiquette d'une série de traits (strokes). Les traits sont numérotés de 1 à 11 et sont représentés par des lignes bleues et des points orange. Chaque trait est étiqueté avec une lettre ou un nombre spécifique. Les étiquettes des traits sont les suivantes : - Trait 1 : 1 - Trait 2 : 2 - Trait 3 : 3 - Trait 4 : 4 - Trait 5 : 5 - Trait 6 : 6 - Trait 7 : 7 - Trait 8 : 8 - Trait 9 : 9 - Trait 10 : 10 - Trait 11 : 11 En dessous de l'illustration des traits, il y a une légende qui explique les étiquettes des traits et leurs relations. Les étiquettes des traits sont classées en deux catégories : "strokeU label" et "strokeD label". Les étiquettes "strokeU label" sont marquées en rouge et incluent : - Sub (Sous) - + (Plus) - Right (Droit) - 2 (Deux) Les étiquettes "strokeD label" sont marquées en bleu et incluent : - a - 1 - a - 2 Les relations entre les étiquettes sont représentées par des flèches et des signes plus ou moins. Par exemple, le trait 6 est lié à "Sub" et "Right" avec des flèches indiquant une relation positive (+). L'illustration vise à rendre les traits plus lisibles en leur attribuant des étiquettes correctes, sauf pour le trait 6.

Illustration for the decision of the label of stroke. For being more readable, all the strokes are given the correct label except stroke 6

Figure 11

Description de l'image par IA : L'image montre deux schémas avec des points rouges représentant des calculs de caractéristiques à pi, étiquetés θi, φi et ψi.

L'image montre deux schémas étiquetés (a) et (b), représentant des points et des angles utilisés dans la description des caractéristiques. Dans le schéma (a), plusieurs points sont représentés par des cercles. Les points importants pour le calcul des caractéristiques sont mis en évidence en rouge. Un angle θi est tracé entre deux points, et un autre angle φi est montré entre un point et une ligne horizontale. Les points rouges sont connectés par des flèches et des lignes, indiquant des relations ou des calculs spécifiques entre eux. Dans le schéma (b), des points similaires sont représentés, avec certains points également mis en évidence en rouge. Une ligne horizontale traverse le schéma, et un angle ψi est tracé entre deux points rouges. Les points rouges sont connectés par des flèches et des lignes, indiquant des relations ou des calculs spécifiques entre eux. Les deux schémas utilisent des flèches et des lignes pour montrer les relations et les calculs entre les points, avec une attention particulière portée aux points rouges pour les calculs des caractéristiques.

The illustration of (a) θi, φi and (b) ψi used in feature description. The points related to feature computation at pi are depicted in red

Figure 12

Description de l'image par IA : x égale r cosinus thêta

A real example from CROHME 2014 data set (sample from the data set 1)

Table 1

Résultats d'évaluation du niveau de symbole sur l'ensemble de test CROHME 2014.

<div> <body> <div class="page"> <table> <tbody> <tr> <th>Data set, features</th> <th colspan="2">Segments (%)</th> <th colspan="2">Seg + Class (%)</th> <th colspan="2">Tree Rels. (%)</th> </tr> <tr> <td></td> <th>Rec.</th> <th>Prec.</th> <th>Rec.</th> <th>Prec.</th> <th>Rec.</th> <th>Prec.</th> </tr> <tr> <th>1,5</th> <td>90.11</td> <td>80.75</td> <td>78.91</td> <td>70.71</td> <td>79.87</td> <td>73.66</td> </tr> <tr> <th>2,5</th> <td>91.88</td> <td>84.47</td> <td>82.42</td> <td>75.77</td> <td>64.75</td> <td>71.96</td> </tr> <tr> <th>3,5</th> <td>93.26</td> <td>86.86</td> <td>84.40</td> <td>78.61</td> <td>61.85</td> <td>75.06</td> </tr> <tr> <th>system</th> <th colspan="6">CROHME 2014 participant results (Top 4)</th> </tr> <tr> <th>IⅢI</th> <th>98.42</th> <th>98.13</th> <th>93.91</th> <th>93.63</th> <th>94.26</th> <th>94.01</th> </tr> <tr> <th>I</th> <td>93.31</td> <td>90.72</td> <td>86.59</td> <td>84.18</td> <td>84.23</td> <td>81.96</td> </tr> <tr> <th>VII</th> <td>89.43</td> <td>86.13</td> <td>76.53</td> <td>73.71</td> <td>71.77</td> <td>71.65</td> </tr> <tr> <th>V</th> <td>88.23</td> <td>84.20</td> <td>78.45</td> <td>74.87</td> <td>61.38</td> <td>72.70</td> </tr> </tbody> </table> </div> </body> </div>

The symbol level evaluation results on CROHME 2014 test set, including the experiment results in this work and CROHME 2014 participant results (Top 4 by recall of Segments)

Table 2

Table résultats évaluation niveaux d'expression CROHME 2014.

<div> <body> <div class="page"> <table> <tbody> <tr> <th>Data set, features</th> <th>correct (%)</th> <th><= 1 error</th> <th><=2errors</th> <th><=3 errors</th> </tr> <tr> <td>1,5</td> <td>25.28</td> <td>40.75</td> <td>49.06</td> <td>52.08</td> </tr> <tr> <td>2,5</td> <td>12.76</td> <td>25.07</td> <td>31.16</td> <td>36.20</td> </tr> <tr> <td>3,5</td> <td>12.63</td> <td>21.28</td> <td>27.70</td> <td>31.98</td> </tr> <tr> <td>system</td> <td colspan="4">CROHME 2014 participant results (Top 2)</td> </tr> <tr> <td>IⅢ</td> <td>62.68</td> <td>72.31</td> <td>75.15</td> <td>76.88</td> </tr> <tr> <td>I</td> <td>37.22</td> <td>44.22</td> <td>47.26</td> <td>50.20</td> </tr> <tr> <td>VII</td> <td>26.06</td> <td>33.87</td> <td>38.54</td> <td>39.96</td> </tr> <tr> <td>VI</td> <td>25.66</td> <td>33.16</td> <td>35.90</td> <td>37.32</td> </tr> </tbody> </table> </div> </body> </div>

The expression level evaluation results on CROHME 2014 test set, including the experiment results in this work and CROHME 2014 participant results (Top 4)

Figure 13

Description de l'image par IA : Diagram (a) montre une écriture en quatre traits ; (b) montre un schéma SLG avec des étiquettes correctes.

L'image contient deux parties étiquetées (a) et (b). Dans la partie (a), il y a trois figures distinctes. La première figure est un ovale avec un trait qui commence en haut à gauche, fait une boucle et se termine en bas à droite. La deuxième figure est une série de trois lignes droites numérotées de 0 à 2. La troisième figure est un ovale avec un trait qui commence en haut à droite, fait une boucle et se termine en bas à droite. Dans la partie (b), il y a un diagramme avec des cercles et des flèches. Le diagramme commence avec un cercle étiqueté "a 0" à gauche. Ce cercle est connecté par des flèches à deux autres cercles étiquetés "racine 1" et "racine 2". Ces cercles sont à leur tour connectés par des flèches à un autre cercle étiqueté "b 3" à droite. Les flèches sont étiquetées avec des termes tels que "Right", "Left", "Right", et "Left".

(a) a ≥ b written with four strokes; (b) the built SLG of a ≥ b according to the recognition result, all labels are correct

Figure 14

Description de l'image par IA : L'image montre trois schémas : (a) écriture en six traits, (b) SLG de référence, (c) SLG reconstruite avec quatre erreurs de liaison.

L'image contient trois parties étiquetées (a), (b) et (c). (a) Montre une série de six traits manuscrits numérotés de 0 à 5. Chaque trait est représenté par une ligne courbe ou droite avec des numéros correspondants indiqués à côté. (b) Représente un graphe de liaison spatial (SLG) de référence. Il montre une série de cercles numérotés de 0 à 4, chaque cercle étant connecté par des flèches indiquant des relations spatiales. Les relations indiquées sont "Right" (à droite) entre les cercles 0 et 1, 1 et 2, 2 et 4. Le cercle 4 a des relations "Above" (au-dessus) et "Below" (en dessous) avec les cercles 3 et 5 respectivement. (c) Représente un SLG reconstruit avec quatre erreurs de reconnaissance. Les cercles sont également numérotés de 0 à 4. Les relations indiquées sont "Right" (à droite) entre les cercles 0 et 1, 1 et 2, 2 et 3. Cependant, il y a des erreurs : la relation "Right" entre les cercles 2 et 4 est manquante, la relation entre les cercles 4 et 3 est manquante, et la relation entre les cercles 2 et 3 est incorrectement reconnue comme "NoRelation" (aucune relation) au lieu de "Right". La relation entre les cercles 4 et 5 est "Below" (en dessous). L'image illustre les différences entre le graphe de référence et le graphe reconstruit, mettant en évidence les erreurs de reconnaissance dans le processus de reconstruction.

(a) written with six strokes; (b) the ground-truth SLG; (c) the 44 rebuilt SLG according to the recognition result. Three edge errors occurred: the Right relation between stroke 2 and 4 was missed because there is no edge from stroke 2 to 4 in the time path; the edge from stroke 4 to 3 was missed for the same reason; the edge from stroke 2 to 3 was wrongly recognized and it should be labeled as NoRelation

Table 3

Table de résultats d'évaluation à différents niveaux symboliques.

<div> <body> <div class="page"> <table> <tbody> <tr> <th>Feat.</th> <th>Train</th> <th>Decode</th> <th colspan="2">Segments (%)</th> <th colspan="2">Seg + Class (%)</th> <th colspan="2">Tree Rels. (%)</th> </tr> <tr> <td></td> <td></td> <td></td> <th>Rec.</th> <th>Prec.</th> <th>Rec.</th> <th>Prec.</th> <th>Rec.</th> <th>Prec.</th> </tr> <tr> <td>5</td> <td>frame-wise</td> <td>maximum</td> <td>92.71</td> <td>85.88</td> <td>83.76</td> <td>77.59</td> <td>59.84</td> <td>73.71</td> </tr> <tr> <td>5</td> <td>local CTC</td> <td>maximum</td> <td>93.21</td> <td>86.73</td> <td>84.11</td> <td>78.26</td> <td>61.25</td> <td>74.51</td> </tr> <tr> <td>5</td> <td>local CTC</td> <td>local CTC</td> <td>93.2</td> <td>86.71</td> <td>84.11</td> <td>78.25</td> <td>61.71</td> <td>74.67</td> </tr> <tr> <td>7</td> <td>local CTC</td> <td>maximum</td> <td>93</td> <td>86.43</td> <td>84</td> <td>78.06</td> <td>61.73</td> <td>74.06</td> </tr> </tbody> </table> </div> </body> </div>

The symbol level evaluation results on CROHME 2014 test set with different training and decoding methods, features

Compte personnel

Using BLSTM for interpretation of 2-D languages

Case of handwritten mathematical expressions

Accès institutions

Toutes les institutions

Using BLSTM for interpretation of 2-D languages

Case of handwritten mathematical expressions

Citer cet article

Accès institutions

Toutes les institutions