Texto completo
| |
| Autor(es): |
Frank Dennis Julca Aguilar
Número total de Autores: 1
|
| Tipo de documento: | Tese de Doutorado |
| Imprenta: | São Paulo. |
| Instituição: | Universidade de São Paulo (USP). Instituto de Matemática e Estatística (IME/SBI) |
| Data de defesa: | 2016-04-29 |
| Membros da banca: |
Ricardo da Silva Torres;
Bertrand Couasnon;
Nina Sumiko Tomita Hirata;
Jean Yves Ramel;
Christian Viard Gaudin
|
| Orientador: | Nina Sumiko Tomita Hirata |
| Resumo | |
Expressões matemáticas manuscritas online estão constituídas por sequências de traços. O reconhecimento automático de tais expressões requer a solução de três subproblemas: segmentação de símbolos, classificação de símbolos e análise estrutural (isto é, a identificação de relações espaciais, tais como sobrescrito e subscrito, entre símbolos). Uma das dificuldades principais do problema é a ambiguidade no nível de símbolos ou relações, que frequentemente sugere várias possíveis interpretações de uma mesma expressão. Alguns métodos de reconhecimento tratam o problema de maneira sequencial, onde um processo de segmentação e classificação de símbolos é seguido de análise estrutural. Um problema principal de tais métodos é que eles determinam interpretações no nível de símbolos sem considerar informação estrutural, a qual é importante para solucionar ambiguidades. Para solucionar esse problema, métodos mais recentes adaptaram técnicas de parsing de strings. Dado que gramáticas de strings foram originalmente projetadas para modelar arranjos lineares de tokens (como texto, onde símbolos são arranjados de esquerda a direita), a estrutura não linear dos símbolos matemáticos (dada pelos multiples tipos de relações espaciais) é modelada como uma composição de regras de produção de estruturas lineares. Dessa maneira, o parsing de uma expressão consiste em determinar estruturas lineares na expressão que são consistentes com as estruturas das regras de produção. Esse último passo requer a introdução de restrições, baseadas na definição de uma ordem em relação ao tempo ou espaço, para linearizar os componentes da expresão. Os requerimentos das gramáticas de strings não apenas limitam a efectividade dos métodos, mas também dificultam a extensão dos métodos na inclusão de novas estruturas. Neste trabalho, o problema de reconhecimento de expressões matemáticas é modelado como um problema de parsing de grafos. A representação por meio de grafos nas regras de produção permite uma representação direta das estruturas não lineares das expressões matemáticas. O algoritmo de parsing determina partições dos traços de entrada que induzem grafos isomorfos aos grafos das regras de produção. Para mitigar o custo computacional, restringimos as possíveis partições a aquelas derivadas de um conjunto de possíveis símbolos e relações identificados por classificadores previamente treinados. Um conjunto de rótulos que indica interpretações alternativas é associado a cada símbolo e relação; a decisão da melhor interpretação é realizada pelo parser. O parser construi uma floresta na qual uma árvore representa uma possível interpretação da entrada, e atribui um custo de interpretação para cada árvore, baseado nas relações e símbolos definidas na árvore. O resultado do reconhecimento é dado pela extração de uma árvore com custo mínimo. Resultados experimentais do método proposto mostram um melhor desempenho em comparação com vários métodos descritos na literatura. A pesar do parsing de grafos ser um processo computacionalmente caro, a restrição do espaço de busca proposto reduz a complexidade o suficiente para permitir uma aplicação prática da abordagem. Adicionalmente, dado que a abordagem não pressupõe estruturas particulares das expressões matemática, o método tem potencial para ser adaptado para o reconhecimento de outras estruturas bidimensionais. Uma contribuição secundaria deste trabalho é o desenvolvimento de uma framework para construção automática de bancos de dados de expressões matemáticas manuscritas. A framework tem sido implementada num sistema usado para criar parte das amostras de expressões usadas para avaliação do método de reconhecimento. (AU) | |
| Processo FAPESP: | 12/08389-1 - Uso de informação contextual em reconhecimento online de expressões matemáticas manuscritas |
| Beneficiário: | Frank Dennis Julca Aguilar |
| Modalidade de apoio: | Bolsas no Brasil - Doutorado Direto |