Reconnaissance dynamique des formules mathématiques

Description

Reconnaissance dynamique de formules mathematiques· Marcel Remon· Departement· de Mathematique· Universite· de Namur B-5000 Namur [e-mail] · ·RESUME. Les algorithmes de reconnaissance d’objets procedent habituellement en comparant l’objet a reconna? tre a une col- lection d’objets de ref· er· ence, appelee· base d’entra? nement. Cette dernier e ne comporte qu’un nombre ni d’el· ements.· Dans plusieurs applications, telle que la reconnaissance de formules mathematiques,· le nombre de situations plausibles est quasi- ment illimite,· vu la structuration propre de ce type d’expression. Il est important de developper· des systemes dynamiques de reconnaissance qui puissent gen· er· er, a la demande, des nouvelles situations de ref· er· ence. L’aspect le plus ardu de cette recherche est l’automatisation du choix des nouvelles ref· er· ences que devra proposer le gen· er· ateur (optimisation dynamique), en fonction de l’etape· ou le programme de reconnaissance se trouve. ·MOTS-CLES : Classi cation, Reconnaissance de caracter es, Discrimination, Analyse d’images 1. Introduction Dans le domaine de la reconnaissance de documents, celle de formules mathematiques· a dej· a fait l’objet de nombreuses etudes[F· AU 00, LAV 00, KAC 01]. L’extraction automatique de formules mathematiques· est un probleme plus dif cile qu’il n’y para? t a premiere vue, car la complexite· d’une formule peut etre? tres grande.

Informations

• Publié par: theorwag
• Publié le: 25 octobre 2013
• Nombre de lectures: 94
• Langue: Français

Extrait

Reconnaissance dynamique

MarcelR´emon

D´artementdeMath´ematique
ep
Universit´edeNamurB-5000Namur
[e-mail]

de formules

mathematiques
´

´UM´E.lgorithLesannoassidsemcerespetc`roedncbj’ollmetieuhtbadenentl’parancomenteıˆannocera`tejbol-coneaue`tr
RESa
lectiond’objetsder´efe´rence,appele´ebased’entraˆınement.Cettederni`erenecomportequ’unnombrefinid’e´l´ements.Dans
plusieurs applications, telle que la reconnaissance de formules mathe´matiques, le nombre de situations plausibles est quasi-
mentillimit´e,vulastructurationpropredecetyped’expression.
Ilestimportantdede´velopperdessyste`mesdynamiquesdereconnaissancequipuissentge´n´erer,`alademande,desnouvelles
situationsder´ef´erence.L’aspectleplusardudecetterechercheestl’automatisationduchoixdesnouvellesr´efe´rencesque
devraproposerlege´n´erateur(optimisationdynamique),enfonctiondel’e´tapeo`uleprogrammedereconnaissancesetrouve.

MOTS-CL´ES:Classification, Reconnaissance de caracte`res, Discrimination, Analyse d’images

1. Introduction

Dansledomainedelareconnaissancededocuments,celledeformulesmath´ematiquesad´ej`afaitl’objet
denombreuses´etudes[FAU00,LAV00,KAC01].L’extractionautomatiquedeformulesmath´ematiquesestun
proble`meplusdifficilequ’iln’yparaˆıt`apremie`revue,carlacomplexit´ed’uneformulepeuteˆtretr`esgrande.
L’id´eepre´conise´edanscettepr´esentationestdepermettrea`l’algorithmedereconnaissancedeg´ene´rer,a`lade-
mande,denouveauxobjetsdere´f´ence,afinquelabased’entraıˆnement(lesformulesdere´f´erence)nesoitplus
er
limit´eeentaille.

2. Segmentation de la formule

SoitFl’ensemble des formules mathe´matiques possibles. Cet ensemble est infini. SoitFla formule a re-
`
connaˆıtre.

Lapremie`ree´tapedereconnaissanceestclassique,maispeutˆetrecomplexe.Ils’agitdel’e´tapedesegmenta-
tionsert´po,tarearuethrie-m´alofmrlueesnmyoblesatomiques(letnenenoitisse´titOns.lemppeouecd´dequael’´
tique).Pourcela,onproc`eded’aborda`unese´parationdessymbolesmathe´matiquesselonl’axevertical,puisselon
l’axehorizontal,etainsidesuitejusqu’a`l’obtentiondezonesnons´eparablesniverticalement,nihorizontalement.
Dans ces zones, on proce`de a` une identification (qui n’est pas encore de la reconnaissance) des symboles ato-
miquesparconnexite´.Uneentit´eestd´efiniecommeunensembledepixelsconnexes.Leproble`medessymboles
nonconnexesesttrait´e(signe=, lettresietjtlesalocntee´eitC.)uqah`eslraprrepatruiocsnederaenfisie´ederbra’
la formule.

2
3+y

=⇒

y

Figure 1.eSeusssemnattointd´eeattaitqihg´meemn

3. Reconnaissance des entite´s

Chaquesymboleatomiqueainsiidentifie´estcompare´avecles´el´ementsbienu’esabne’dˆartde,fiie´milpnestnıme
soitBleeletrdeuatern´e´gnutuafsuonli,celaPour.salintipcrtituepnustituetatsereg´en´ererence.Cdsree´´festntie´
LAsoit efficace, il nous faut une distance robuste, peu sensible a` la casse ou a` laTEX. Pour que cette reconnaissance
policedecaract`ereutilis´ee(italique,gras,policeg´ene´r´eeparWordouLATEX).
A`splusieurstests,ladistanceretenueestde´finiecommesuit:onge´n`ereungrandnombrededroites
pre
ale´atoiresdanslafenˆetrecontenantl’entit´eetoncomptelafre´quencededroitesrencontrantl’entite´0,1,2, , n
fois1. Ensuite on compare (distance euclidienne dansRn les rce vecteur de fre´quences avec ceux tro ´)
uves pou en-
tit´esbidf´erer´eesr`tteseastburoteC.ecneerusemetontitrs,diuxtalar,sntatolsnaoitaepermetdions.Ellredesircmi
entredessymbolestr`esproches.Achaqueentite´identifi´eeestassocie´une´le´mentdeB, ou plusieurs, selon le seuil
dediscriminationaccept´eentrelesentit´sdere´f´erence.
e
xx e
Figure 2.Exemple de mesure morphologique.
(f1, f2, f3, f4)o`ufiest la fre´quence des droites rencontrantiitne’lsioft´e.
Pour la figure :(0,8,8,0),(0,8,8,8)et(8,8,8,8).

bi

+
1
2
3
5
x

x

0
0,0
0,2834
0,1264
0,1255
0,1238
0,1201
0,18

0,1652

Figure 3.

1
1,0
0,5391
0,7880
0,6273
0,5751
0,5743
0,4671

2
0,0
0,1774
0,0852
0,2289
0,2826
0,2933
0,3081

0,4970 0,3062

3
0,0
0,0
0,0
0,0182
0,0184
0,0122
0,0428

0,0310

4
0,0
0,0
0,0
0,0
0,0
0,0
0,0019

0,0004

kbi xk
0,6124
0,1825
0,3687
0,1571
0,0923
0,0923
0,0355

Comparaison entrexestneirudsretie´eren´ef´ceuspletbi.

1einau2rs00d0ortiseodnnentd´ej`auneboannneenentes´mgi´traeo´i0d0n2leepaop0r0olbaaubriulrifitg´,empeou3.o
droite quelconque de rencontrerifois l’entite´. Le nombrenrencontreelletediuqno¸cafeqr´afeleredncuehoisestcn+ 1fois
l’entite´ est nulle.

4.

Premie`re estimation de la formule

Apartirdelalocalisationdesentite´slorsdel’´etapedesegmentation,nousconstruisons,demanie`rer´ecursive,
unarbreassocie´a`laformule.L’arbreainsiconstruitsebasesurlagrammairedesformulesmath´ematiques.Ilest
importantquel’arbresoitmath´ematiquementinterpr´etable,etnonpasunesuitedesymbolesatomiques.

Dansunpremieressai,nousavionscommer´esultatunarbrecompose´defonctionsinterpr´etablesparLATEX, ce
qui nous permettait de redessiner la formule. Mais, cela n’est pas suffisant, car il n’y a pas de diffe´rence en LATEX
entre2 5et25. De plus, LATEX ne peut manipuler les formules.
C’estpourquoinoussommesentraindetravailler`alaconstructiond’arbresquisoientinterpr´etablesmathe´ma-
tiquement, par exemple, en Matlab. La reconnaissance de la formule est alors quasiment effective, car on peut la
reprendre dans un algorithme de calcul.

Pourcela,nousavonsbesoind’unegrammairedesop´erateursetdestermes.Cettegrammaireeste´galement
utilise´e pour affiner notre reconnaissance de la formule globale, car les expressions non valides sont e´limin´
ees
d’office.

Lorsquelede´coupagen’estpasclair-parexemple,danslecasd’exposantoud’indice-,l’algorithmegardeen
me´moirelesstructurationspossiblesdelaformule´etudie´e.Parexemple,nousretenonscommechoixpossiblesxy,
xyetxyit´tesil’enyiveauqu’enseptsaxecaetemtnuaˆmmenexennsnasethrietm´oitieuqnalecutia,`acondqieu
(on ne peut avoir+y).

5.

Figure 4.

x

^ ou nul

2 ou z

\frac

\sqrt

+

y

3
Exempled’arbreavecm´emoiredeschoixpossibles.

Reconnaissance dynamique de la formule globale

Ils’agitd’am´eliorerl’estimationdeFitilasitnoedalemsureex-gtpi´ne´taredrueoreflemut`se’ualrcsuaecaˆrG.
pos´eepr´ece´demment,ilestais´edecomparern’importequelleformulemath´ematiqueaveclaformulea`reconnaıˆtre.

Leprobl`emeestdefourniraug´ene´rateurdeformulesdebonscandidatspourlesestimationssuccessives.
Lorsdel’e´tapedereconnaissancedesentite´s,nousavonsgard´e,parchaqueentit´e,unoudeuxcandidatsdans
l’ensembleB la formule. Nous testons alors ´ tant r e, et nous avons fait de meˆme lors de la cre´ation de l’arb
r epresen
syst´ematiquementtouteslescombinaisonsapparaissantdansl’arbredelaformule.Ainsi,pourl’exempledela
2z
figure1,l’algorithmeg´en´ereralesformulessuivantes:3+y,3+y,3+yet3+y.
Cen’estqu’`apartirdesformulesglobalesge´ne´re´esparl’algorithmequeseferalareconnaissanceultimede
laformule.La`encore,ladistancebas´eesurunensembleale´atoirededroitesestutilis´ee,vusarobustesse.Etles
r´esultatssontvraimentencourageants,quecesoitpourdesformulesge´n´ere´esenLATEXou en Word.

6. Bibliographie

[FAU 00] FAUREC.,http ://www.tsi.enst.fr/
mathe´matiques, 2000.

cfaure/math.html,

Liste de re´fe´rences pour la reconnaissance de formules

[KAC 01] KACEMA., BELA I¨DA., BANAHMEDM., Automatic extraction of printed mathematical formulas using fuzzy
logic and propagation of context,International journal on Document Analysis and Recognition 4,, vol. 2001.
[LAV 00] LEVIATTROS.,Reconnaissance structurelle de formules mathematiques typographie´es et manuscrites,
´
d´efendue`al’UniversitedeNiceSophia-Antipolis,2000.
´

Th`
ese