Proposta
Alunos: Bruno Yoiti Ozahata e Ricardo Sider
Supervisora: Profª Dra. Nina S. T. Hirata
Tema: Análise Estrutural de Expressões Matemáticas Manuscritas Online (Projeto ExpressMath)
Resumo da monografia
Converter expressões matemáticas para um formato digital estruturado não é uma tarefa trivial. Diferentemente de textos convencionais uma fórmula matemática pode abrigar uma grande variedade de símbolos (muitos deles especiais), dispostos bidimensionalmente das mais variadas maneiras [1]. O ExpressMath [2] surgiu com o objetivo de automatizar esse processo, que pode ser naturalmente dividido em duas etapas: segmentação e reconhecimento de símbolos, e análise estrutural [3, 4]. Esse trabalho se limita à segunda etapa.
A análise estrutural de uma expressão matemática consiste na definição das relações espaciais entre símbolos, bem como suas relações de dominância. Para atingir esse resultado utilizaremos uma variação da abordagem proposta por E. Tapia [5], usando dominância entre símbolos, baselines [6, 7], e a construção de uma árvore geradora mínima da expressão.
Nessa abordagem, cada símbolo da expressão matemática é representado por um vértice num grafo conexo, a cujas arestas atribuimos pesos calculados com base nas relações espaciais e de dominância entre os símbolos que elas unem. Em seguida calculamos a árvore geradora mínima desse grafo, inicializando-a com os símbolos que compõe a baseline principal da expressão. Cada aresta na árvore ao final desse passo representa a melhor possibilidade de associação entre dois símbolos, de modo que obtemos uma representação estruturada da fórmula original.
Objetivos
O objetivo final deste trabalho é apresentar um analisador estrutural de expressões matemáticas robusto e portável, baseado em dominância de símbolos, baselines e árvores geradoras mínimas.
Esse analisador, juntamente com um um segmentador e reconhecedor de símbolos, formará o ExpressMath: um reconhecedor de expressões matemáticas manuscritas online de código aberto, que poderá ser utilizado tanto no ambiente acadêmico quanto profissional.
O ExpressMath herda algumas ideias implementadas no Math-Picasso [8], e está sendo desenvolvido em conjunto com um outro grupo que deverá trabalhar na parte de reconhecimento de símbolos.
Atividades realizadas
- Estudo de algoritmos e leitura de artigos relacionados à análise estrutural de expressões matemáticas publicados no meio acadêmico [5, 6].
- Definição da abordagem a ser utilizada (dominância entre símbolos, baselines, e árvores geradoras mínimas).
- Escolha da liguagem Java para a implementação do algoritmo.
- Adaptação do Math-Picasso para ser usado como base de coleta de dados, e futuramente como base de operação do nosso projeto.
- Inicio da implementação da leitura da baseline principal de uma expressão.
Cronograma
| Mês | Atividade |
|---|---|
| Junho | Coleta de dados e geração de uma base de testes de eficiência |
| Julho | Implementação do algoritmo de árvores geradoras mínimas. Inicio da redação da monografia |
| Agosto | Consolidação da integração com o reconhecedor |
| Setembro | Estudo e implementação de técnicas para melhorar a eficiência do algoritmo |
| Outubro | Prazo máximo para o término da redação da monografia |
| Novembro | Revisões no texto e programa. Entrega e apresentação do trabalho final |
| Dezembro | Publicação da versão 1.0 do programa |
Estrutura esperada da monografia
1. Introdução
2. Motivação
3. Apresentação do problema
4. Algoritmo implementado
5. Desenvolvimento do projeto
6. Resultados obtidos
7. Conclusão
Referências
[1] B. P. Berman, R. J. Fateman, "Optical Character Recognition for Typeset Mathematics".
[2] ExpressMath. Disponível em: http://www.vision.ime.usp.br/~nina/projetos/expressmath/
[3] H. J. Lee, J. S. Wang, "Design of a Mathematical Expression Understanding System".
[4] D. Blostein, A. Grbavec, "Recognition of Mathematical Notation".
[5] E. Tapia, R. Rojas, "Recognition of On-line Hand-written Mathematical Expressions Using a Minimal Spanning Tree Construction and Symbol Dominance".
[6] R. Zanibbi, D. Blostein, J. Cordy, "Recognizing Mathematical Expressions Using Tree Transformation".
[7] N. Matsakis, "Recognition of Handwritten Mathematical Expressions".
[8] Math-Picasso. Disponível em: http://code.google.com/p/math-picasso/