pfc luis roman

7/23/2019 Pfc Luis Roman

1/87

ESCUELA TCNICA SUPERIOR DE INGENIERA INFORMTICA

INGENIERA INFORMTICA

RECONOCIMIENTO DE TEXTO MATEMTICO IMPRESO

Realizado por:

LUIS ROMN GUTIRREZ

Dirigido por:JOS ANDRS ARMARIO SAMPALO

PEDRO REAL JURADO

Departamento:

MATEMTICA APLICADA I

Sevilla, Junio 2008


2/87


3/87

Resumen Reconocedor de texto matemtico

RESUMEN

Reconocimiento de texto matemtico impreso

El objetivo de este proyecto fin de carrera es el desarrollo de mtodos para el reconocimiento detexto matemtico impreso, y posteriormente escaneado, usando tcnicas basadas en tcnicas deprocesamiento de imagen y anlisis de lenguajes formales, para generar una salida en texto plano(posiblemente LaTeX, pero no limitado a esto) que conserve el significado de la frmula.

ABSTRACT

Printed mathematical text recognition

The main goal of this master thesis is the development of methods suitable for therecognizement of printed, and then scanned, mathematical text using methods based on imageprocessing and formal language analysis techniques, so a text-only output possibly LaTeX, butnot limited to it - keeping the formula's meaning can be generated.

3


4/87

Reconocedor de texto matemtico Luis Romn Gutirrez

4


5/87

Reconocedor de texto matemtico

ndice de contenidoResumen ..............................................................................................................................................3Abstract.................................................................................................................................................31.Introduccin.......................................................................................................................................92.Problema terico y anlisis de la solucin......................................................................................11

2.1.Segmentado y reconocimiento de caracteres...........................................................................13a.Preprocesamiento...................................................................................................................13b.Extraccin de la informacin de las imgenes.......................................................................15c.Almacenamiento de la informacin extrada, aprendizaje y reconocimiento........................21d.Segmentacin.........................................................................................................................23e.Smbolos reconocidos............................................................................................................26

2.2.Secuenciacin y anlisis lxico................................................................................................26a.Secuenciacin.........................................................................................................................27b.Anlisis lxico........................................................................................................................28

2.3.Anlisis sintctico....................................................................................................................28a.Estructura general del mtodo................................................................................................28b.Especializacin del mtodo para nuestro caso particular.......................................................30

3.Diseo e implementacin del software............................................................................................333.1.Arquitectura del sistema y diagramas de clase........................................................................33

a.Secuenciacin y reconocimiento de caracteres......................................................................34b.Anlisis lxico y anlisis sintctico.......................................................................................36c.Diseo de la conexin entre los controladores y las interfaces grficas de usuario...............37

3.2.Descripcin de la implementacin...........................................................................................38a.MathTextLibrary....................................................................................................................40b.MathTextCustomWidgets......................................................................................................46

c.MathTextLearner....................................................................................................................47d.MathTextLearnerLauncher....................................................................................................47e.MathTextRecognizer..............................................................................................................47

4.Experimentacin..............................................................................................................................534.1.Caso experimental 1.................................................................................................................53

a.Segmentado y reconocimiento de smbolos...........................................................................54b.Secuenciacin y anlisis lxico..............................................................................................54c.Anlisis sintctico..................................................................................................................54

4.2.Caso experimental 2.................................................................................................................55a.Segmentado y reconocimiento de smbolos...........................................................................55b.Secuenciacin y anlisis lxico..............................................................................................55

c.Anlisis sintctico..................................................................................................................564.3.Caso experimental 3.................................................................................................................56a.Segmentado y reconocimiento de caracteres..........................................................................56b.Secuenciacin y anlisis lxico..............................................................................................57c.Anlisis sintctico..................................................................................................................57

4.4.Conclusiones obtenidas de la experimentacin.......................................................................575.Posibilidades de futuro y mejoras....................................................................................................59

5.1.Mejoras del reconocimiento de smbolos................................................................................595.2.Mejoras en el reconocimiento del lenguaje.............................................................................595.3.Otras mejoras...........................................................................................................................60

6.Manual de usuario...........................................................................................................................63

6.1.Instalacin................................................................................................................................63

5


6/87


6.2.Reconocedor de texto matemtico...........................................................................................63a.Modo educativo......................................................................................................................64b.Modo desasistido....................................................................................................................69c.Modo pizarra..........................................................................................................................69

d.Visin del resultado...............................................................................................................70e.Editor de la lista de smbolos.................................................................................................70f.Gestor de reglas lxicas..........................................................................................................71g.Gestor de reglas sintcticas....................................................................................................72h.Preferencias de la salida.........................................................................................................75i.Gestor de bases de datos.........................................................................................................75

6.3.Aprendedor de smbolos matemticos.....................................................................................76a.Crear nueva base de datos......................................................................................................76b.Aadir smbolos a una base de datos.....................................................................................78

7.Carga de trabajo...............................................................................................................................818.Referencias......................................................................................................................................87

6


7/87

Reconocedor de texto matemtico

ndice de figurasFigura 1: Problema de ordenacin en las frmulas............................................................................11Figura 2: Los mismos smbolos, distintos significados......................................................................12Figura 3: Carcter original..................................................................................................................13Figura 4: Carcter binarizado ............................................................................................................13Figura 5: Carcter encuadrado............................................................................................................14Figura 6: Carcter escalado................................................................................................................14Figura 7: Carcter adelgazado usando Zhang-Suen con post-procesamiento de Holt.......................15Figura 8: Carcter adelgazado usando Zhang-Suen con preprocesamiento Stentiford .....................15Figura 9: Carcter adelgazado usando Zhang-Suen con preprocesamiento Stentiford y con post-procesamiento de Holt........................................................................................................................15Figura 10: Caractersticas binarias: cambios de color respecto a la lnea media horizontal..............17Figura 11: Caractersticas binarias: cambios de color respecto al eje de ordenadas..........................17Figura 12: Caractersticas binarias: puntos finales.............................................................................18

Figura 13: Caractersticas binarias: puntos de rbol...........................................................................18Figura 14: Nmero de agujeros..........................................................................................................19Figura 15: Receptores sobre una imagen preprocesada.....................................................................20Figura 16: Estructura de un rbol binario para almacenar smbolos..................................................21Figura 17: Aprendizaje con vectores binarios....................................................................................22Figura 18: Reconocimiento con vectores binarios.............................................................................22Figura 19: Aprendizaje con vectores triestado...................................................................................23Figura 20: Proyecciones de una imagen.............................................................................................24Figura 21: Imagen sin huecos, pero segmentable...............................................................................24Figura 22: Segmentacin en cascada..................................................................................................25Figura 23: Un compilador tambin necesita preparar la entrada para el anlisis lxico....................27

Figura 24: Ordenar los smbolos rompe los tems..............................................................................27Figura 25: Parmetros de la tipografa...............................................................................................27Figura 26: Generacin de un lenguaje a partir de su gramtica.........................................................29Figura 27: rbol de recubrimiento de una gramtica.........................................................................30Figura 28: La raz est ocultada por el smbolo de fraccin...............................................................31Figura 29: La raz esta ocultada por el 2, pero no por la y.................................................................31Figura 30: La raz principal es la que contiene a la y, ya que es ms alta..........................................32Figura 31: Estructura del espacio de nombres Databases..................................................................34Figura 32: Diseo de las bases de datos de caractersticas binarias...................................................34Figura 33: Diseo de las bases de datos de receptores.......................................................................35Figura 34: Diseo del subsistema de segmentacin de imgenes......................................................35

Figura 35: Diseo del subsistema de proyecciones de la imagen......................................................35Figura 36: Diseo del sistema del control del reconocimiento..........................................................36Figura 37: Diseo de los subsistemas de anlisis lxico y sintctico.................................................36Figura 38: Diseo del sistema de control del anlisis lxico y el anlisis sintctico.........................37Figura 39: Diseo de la conexin entre los controladores y la interfaz.............................................37Figura 40: Diseo del sistema de persistencia de la configuracin....................................................38Figura 41: Algunas de las imgenes de prueba utilizadas durante la experimentacin.....................53Figura 42: Imagen del caso experimental 1........................................................................................53Figura 43: Resultado del caso experimental 1....................................................................................55Figura 44: Imagen del caso experimental 2........................................................................................55Figura 45: Resultado caso experimental 2..........................................................................................56

Figura 46: Imagen del caso experimental 3........................................................................................56

7


8/87


Figura 47: Salida del caso experimental 3..........................................................................................57Figura 48: Pantalla de bienvenida del instalador................................................................................63Figura 49: Pantalla inicial de MathTextRecognizer...........................................................................63Figura 50: Pantalla Acerca de de MathTextRecognizer.................................................................64

Figura 51: Modo educacional, fase de segmentacin y OCR (1).......................................................64Figura 52: Modo educativo, segmentacin y OCR (2).......................................................................65Figura 53: Modo educativo, segmentacin y OCR (3).......................................................................65Figura 54: Modo educativo, segmentacin y OCR (4).......................................................................65Figura 55: Modo educativo, anlisis lxico (1)..................................................................................66Figura 56: Modo educativo, anlisis lxico (2)..................................................................................66Figura 57: Modo educativo, anlisis lxico (3)..................................................................................67Figura 58: Modo educativo, anlisis lxico (4)..................................................................................67Figura 59: Modo educativo, anlisis sintctico (1)............................................................................68Figura 60: Modo educativo, anlisis sintctico (2)............................................................................68Figura 61: Modo desasistido..............................................................................................................69Figura 62: Modo pizarra virtual.........................................................................................................70Figura 63: Ventana mostrando la salida del proceso..........................................................................70Figura 64: Lista de smbolos..............................................................................................................71Figura 65: Editor de la lista de smbolos............................................................................................71Figura 66: Gestor de reglas lxicas....................................................................................................71Figura 67: Editor de reglas lxicas.....................................................................................................71Figura 68: Gestor de reglas sintcticas...............................................................................................72Figura 69: Editor de reglas sintcticas................................................................................................72Figura 70: Control que representa al tem en la expresin.................................................................73Figura 71: Ventana de opciones del tem...........................................................................................73Figura 72: Control para el grupo de tems..........................................................................................74Figura 73: Opciones del grupo de elementos.....................................................................................74Figura 74: Control para la llamada a reglas........................................................................................74Figura 75: Opciones de la llamada a regla.........................................................................................75Figura 76: Ventana de preferencias de la salida.................................................................................75Figura 77: Ventana del gestor de bases de datos................................................................................75Figura 78: Vista inicial del aprendedor de smbolos matemticos.....................................................76Figura 79: Asistente de creacin de bases de datos, seleccin del tipo..............................................76Figura 80: Asistente de creacin de bases de datos, seleccin de imgenes de inicio.......................77Figura 81: Asistente de creacin de bases de datos, seleccin del preprocesado...............................77Figura 82: Asistente de creacin de bases de datos, seleccin del preprocesado (previsualizacin).77Figura 83: Asistente de creacin de bases de datos, editor de parmetros del algoritmo depreprocesado.......................................................................................................................................77

Figura 84: Asistente de creacin de bases de datos, establecer descripcin......................................78Figura 85: Aadir smbolos a la base de datos (1).............................................................................78Figura 86: Aadir smbolos a la base de datos (2).............................................................................79Figura 87: Aadir smbolos a la base de datos (3).............................................................................79

8


9/87

Introduccin Reconocedor de texto matemtico

1. INTRODUCCIN

El presente proyecto fin de carrera se basa en un trabajo realizado para la asignatura PID de la

Escuela Tcnica Superior de Ingeniera Informtica durante el curso 2005/06, y como se expuso enla documentacin de dicho trabajo[2], aunque existen muchas herramientas de OCR, es decir, dereconocimiento ptico de textos, la gran mayora de ellas enfocan el problema del reconocimientode textos ms o menos formales, pero sin contenido matemtico.

Hay varios problemas nicos que presenta un texto matemtico con respecto al que puedaaparecer, por ejemplo, en una novela o una postal. Estos problemas derivan de la naturaleza de lossmbolos utilizados (un conjunto de smbolos mucho ms amplio que el alfabeto estndar decualquier lengua occidental, y debido a esto ms complejos, para facilitar la diferenciacin entresmbolos similares), y tambin de las relaciones espaciales entre estos smbolos (que van ms alldel concepto de smbolos siguiente, o que comparten una misma linea base.

Se han realizado dos aplicaciones complementarias: una para aprender smbolos y otra parareconocer frmulas que contengan los smbolos aprendidos. La implementacin se ha realizado enC# sobre Mono[4] usando GTK# para la interfaz de usuario, debido a que este proyecto se distribuyecon la licencia libre GNU GPL. Adems el uso de Mono nos permite obtener una aplicacin quefuncione en la mayora de plataformas principales.

Mediante el aprendizaje el usuario carga varias imgenes e indica a qu smbolo correspondecada una. El conjunto de estos smbolos se almacenan en una base de datos que se usar en elproceso de reconocimiento de caracteres.

La aplicacin de aprendizaje ahora presentada mejora a la entregada en el trabajo de PID enaspectos como una mayor facilidad y control a la hora de crear una base de datos.

El programa reconocedor ha sufrido muchos ms cambios, pues ha sido en el reconocimientodel texto donde ms se ha trabajado durante el desarrollo de este proyecto fin de carrera.

El reconocimiento se ha convertido en un proceso mucho ms modular y flexible, que permiteser expandido fcilmente sin necesidad (dentro de unos lmites lgicos) de reconocer cualquier tipode frmula sin necesidad de modificar el cdigo del programa.

Todos estos cambios y mejoras se documentan en el presente documento, as como losfundamentos tericos y prcticos en los que se han basado las decisiones de diseo eimplementacin del sistema de reconocimiento de texto matemtico.

9


10/87


10


11/87

Problema terico y anlisis de la solucin Reconocedor de texto matemtico

2. PROBLEMA TERICO Y ANLISIS DE LA SOLUCIN

El problema terico de reconocer texto matemtico difiere enormemente de reconocer texto en

prosa de un lenguaje natural occidental como se ha comentado en la introduccin.Los motivos principales de esta enorme diferencia son:

Hacer el reconocimiento de caracteres es ms complicado

El reconocimiento de caracteres con alfabetos occidentales es un problema que se consideracerrado desde hace tiempo. Hay multitud de soluciones disponibles que basan su efectividaden sistemas muy variados de reconocimiento propiamente dicho, y anlisis del contexto.

Este anlisis del contexto permite que si hay dudas en un carcter de una palabra, sebusquen palabras similares a la que se ha reconocido parcialmente en una base de datosconstruida por idiomas.

El texto matemtico es mucho ms complejo que esto, y tener bases de datos de quecaracteres pueden aparecer junto a otros es impracticable.

Los smbolos de las frmulas son variables

Los smbolos utilizados para la construccin de frmulas son mucho ms variables. No nosreferimos aqu que exista un mayor nmero de ellos (y adems muy parecidos, con sutilesvariaciones dotando al smbolo de significados completamente distintos), sino a que lapropia forma del carcter cambia, mantenindose el significado.

Un caso claro de esto es como un smbolo de raz crece tanto en altura como en anchura paraadecuarse a sus contenidos, o como el texto de un superndice utiliza una tipografa con unasmedidas distintas.

Este problema se trata en la fase de segmentacin y reconocimiento de caracteres, aunqueslo se consigue solventar de forma parcial como se explicar en un capitulo posterior.

El texto matemtico no tiene un orden obvio

Un texto extrado, por ejemplo, de una novela, se compone de prrafos, que a su vez secomponen de lneas, que estn compuestas por palabras.

Dentro de una lnea, todos los caracteres ocupan la posicin siguiente a otro carcter(excepto el primero) y lo mismo ocurre con las lineas dentro de un prrafo.

Es muy fcil por tanto saber cual es el orden de lossmbolos. El primer carcter de un prrafo siempreaparecer en su esquina superior izquierda (en lenguajesque se escriben de izquierda a derecha), y el carctersiguiente es el situado inmediatamente a su derecha.

En una frmula, el primer elemento es un concepto muchoms complicado. En la figura 1 se refleja esta circunstancia,cual es el primer smbolo? la x que aparece ms laizquierda? No, es la raz, puesto que la x simplemente es unaccesorio de la raz que modifica su significado.

Para resolver este problema, consistente en determinar cuales el primer smbolo que debe ser reconocido, se ha

11

Figura 1: Problema de ordenacinen las frmulas


12/87


desarrollado una tcnica de basada en la bsqueda forzada de smbolos como se explicarms adelante cuando se trate el proceso de anlisis sintctico.

El texto matemtico no es lineal

El hecho de que las formulas no se constituyan de simples secuencias lineales de texto conun orden tan claro como en el texto convencional, adems del problema de la ordenacin,nos trae el problema de la relaciones entre smbolos, estando ambos problemas ntimamenterelacionados.

Las tcnicas de procesado de lenguajes habituales definen el concepto de smbolosiguiente. En un texto no matemtico, sea del lenguaje natural o de un lenguaje formalcomo puede ser un lenguaje de programacin cualquiera, el smbolo siguiente essimplemente el smbolo a la derecha del smbolo que estamos considerando.

Si el texto aparece en varias lneas, puede reducirse alcaso de una sola lnea eliminando los retornos decarro (esto ocurre por ejemplo, en la fase depreprocesado de cualquier compilador de lenguaje deprogramacin, que no es ms en esencia, que unprocesador de lenguajes formales).

Para las frmulas no podemos hacer esto, puesto queel significado de los distintos elementos puededepender de la posicin espacial que ocupen, ademsde su forma, como puede verse en la figura 2.

Por ello tendremos en cuenta, en la fase de anlisissintctico, expandir el concepto de smbolo siguiente,y permitir definir relaciones entre smbolos del tipo arriba de, debajo de, superndice

de, subndice de y dentro de.Estos que hemos visto son los problemas digamos obvios que se deducen de las diferencias

entre el texto matemtico y el texto normal, y que nos impide simplemente aplicar cualquierpaquete de OCR existente y aplicarlo a una frmula, dando motivos al desarrollo del presenteproyecto fin de carrera.

Para resolver estos problemas, se ha decidido usar una aproximacin basada en elreconocimiento de lenguajes formales, una tcnica utilizada, por ejemplo, en la construccin decompiladores para lenguajes de programacin, y otros sistemas que requieren del procesamiento detextos.

Esta aproximacin requiere del uso de una fase de anlisis lxico (para reconocer las categoras

de elementos usados para construir la formula, como son funciones, nmeros, operadores, etc.), y deanlisis sintctico (que encuentra la relacin entre dichos elementos basndose en su posicin en elflujo de entrada).

Estos dos mtodos se desarrollan originalmente por sus creadores para trabajar con entradas detexto plano, como por ejemplo el cdigo fuente de un programa de ordenador. Por ello, para podertrabajar con imgenes que contienen frmulas, es necesario una fase previa de segmentacin deimgenes (para trocear una imagen en las imgenes que contienen los smbolos) y reconocimientode caracteres, para extraer los smbolos de dichas imgenes.

12

Figura 2: Los mismos smbolos, distintossignificados


13/87


2.1. Segmentado y reconocimiento de caracteresLa fase de segmentado y reconocimiento de caracteres es la que ha sufrido un menor nmero de

cambios conceptuales en comparacin al trabajo de PID [2] del que se parte de base para esteproyecto.

a. Preprocesamiento

Antes de poder trabajar con la imagen de cara a su reconocimiento o aprendizaje es necesario untratamiento previo de la misma. Este procesado es necesario porque en principio una imagen quecontenga una frmula puede ser en color, escala de grises o blanco y negro, y puede tener cualquiertamao y tipografa, e incluso podra presentar ruido, aunque durante el desarrollo del proyectosiempre se ha supuesto que la calidad de las imgenes sera alta, sin ruido, por simplificar elproblema.

El problema de las imgenes a color se solventa al cargar la imagen a procesar, convirtindola a

escala de grises utilizando la luminosidad de cada pxel de la misma.La posible presencia de ruido y la distinta naturaleza de las distintas tipografas nos obliga a que

para, preparar la imagen para un reconocimiento de caracteresaceptable debamos procesarla ms all de un simple paso a a escalade grises.

Para ello, se han generalizado el sistema de preprocesadoheredado de la herramienta que estamos mejorando, de forma quepodemos elegir la combinacin ms adecuada a partir de una baterade algoritmos de preprocesado que se ha hecho accesible yconfigurable visualmente por el usuario para que pueda asegurar paraque en su caso (tipografa, ruido) concreto el preprocesado esadecuado al problema.

Los procesos a continuacin explicados se aplicarn comoejemplo sobre el carcter representado en la figura 3.

i. Binarizacin

El proceso de binarizacin convierte una imagen en escala de grises en una imagen en blanco ynegro.

Puede observarse un ejemplo de binarizacin aplicado al carcteroriginal en la figura 4.

Se pueden utilizar dos algoritmos distintos para la binarizacin de lasimgenes a reconocer:

Binarizado de los dos picos

Para el binarizado de los dos picos se asume como cierta lasiguiente hiptesis: La mayor parte de los pxeles de la imagen quevamos a intentar binarizar (para su posterior reconocimiento) son obien blancos o negros (o mejor dicho lo mas blanco o mas negroposible de la imagen), y los tonos de gris intermedios son minora.

Por tanto, los dos valores mximos en un histograma deben representar los puntos negros y

los blancos, y el punto medio entre ambos un buen lugar para establecer el umbral con elque binarizar.

13

Figura 3: Carcter original

Figura 4: Carcterbinarizado


14/87


Sin embargo, se comprueba experimentalmente que para que la hiptesis de partida searealmente cierta, la imagen a procesar debe tener un buen tamao y una buena calidad, paraque el difuminado inherente a imgenes pequeas o de baja calidad no afecte al histograma.

Si la imagen tiene poca calidad habr muchos pxeles con muchos niveles de gris distintos,

impidiendo la buena eleccin de dos picos, uno verdaderamente negro, y otro blanco ydando un resultado no deseado.

Binarizado de umbral fijo

El binarizado de umbral fijo es ms simple en su forma de trabajar que el de los dos picos,ya que requiere de la intervencin del usuario para fijar el nivel a partir del cual seconsideran blancos o negros los pxeles.

Esto hace este mtodo mucho ms apropiado para imgenes de baja calidad, ya que elusuario puede valorar como afecta considerar un determinado nivel al binarizar a unaimagen de determinadas caractersticas.

Cualquiera de los dos mtodos explicados puede ser elegido junto con el resto depreprocesamientos de imgenes al crear una base de datos de smbolos, como se ver ms adelante.

ii. Encuadrado

El encuadrado consiste en obtener el menor cuadrado que contiene todos los pxeles negros de laimagen dejando un marco de un pxel blanco alrededor.

Puede observarse un ejemplo de encuadrado aplicado al carcter ya binarizado en la figura 5.

iii. Escalado

El escalado consiste en cambiar el tamao de la imagen considerada.La necesidad de este procesado nace de los diferentes tamaos que puedepresentar una imagen. Sin escalar una imagen podra ser tan grande comose desease, lo cual tendra un efecto muy negativo en el rendimiento de laaplicacin, que necesita realizar muchas operaciones posteriores con cadapxel de la imagen.

Sin embargo, el escalado tiene el problema de que resta informacin ala imagen, tanto al reducir el tamao como al aumentarlo (aunque estoultimo no interesa por la consideracin acerca del rendimiento expuestaanteriormente).

Puede observarse un ejemplo de normalizacin aplicado al carcter ya encuadrado en la figura 6.En esta figura, la imagen tendra un tamao de 50 x 50 pxeles, pero se muestra a mayor tamao loque provoca un difuminado provocado por el procesador de textos.

iv. Adelgazado

El adelgazamiento es el procedimiento que permite obtener elesqueleto de una imagen, el cual es la subimagen con el menor nmero depxeles que mantiene todas las propiedades morfolgicas de la imagenoriginal. Este procesamiento ha sido necesario porque el mtodo escogidopara el reconocimiento de caracteres, las caractersticas binarias, necesitaen general que la imagen a reconocer contenga el esqueleto de un carcter.

14

Figura 5: Carcterencuadrado

Figura 6: Carcter

escalado


15/87


Si se hubiese optado por otros mtodos de reconocimiento este ltimo procesado podra haberseobviado.

Se han implementado tres algoritmos distintos de adelgazamiento:

Zhang-Suen con postprocesamiento de Holt Zhang-Suen con preprocesamiento de Stentiford

Zhang-Suen con preprocesamiento de Stentiford y postprocesamiento de Holt

La figura 7 muestra el resultado del adelgazamiento de Zhang-Suen con post-procesamiento deHolt, la figura 8 el resultado del adelgazamiento de Zhang-Suen con pre-procesamiento deStentiford y la figura 9 el resultado del adelgazamiento de Zhang-Suen con pre-procesamiento deStentiford y post-procesamiento de Holt.

El tipo de adelgazamiento a utilizar depender muy mucho de cual deje un resultado ms limpio(con menos agujeros artificiales, etc.) con el juego de caracteres con el que nos tengamos queenfrentar.

En general, esto es aplicable a todas las posibles combinaciones de algoritmos que hemospresentado. Al aprender un nuevo juego de caracteres, habr que seleccionar la combinacin dealgoritmos que proporcione un mejor resultado.

b. Extraccin de la informacin de las imgenes

Para poder reconocer (o aprender) una imagen que contenga un smbolo es necesario obtenerciertas mtricas que permitan obtener una informacin til de la imagen.

Por informacin til entendemos una informacin que nos permita diferenciar unos smbolos deotros, que sea poco variables sobre distintas representaciones del mismo smbolo, y que sean fcilesde almacenar.

Se han creado varios mtodos (implementados como se ver ms tarde en el softwaredesarrollado) intentando conseguir estos objetivos, que son los que se describen a continuacin,ordenados cronolgicamente segn cuando se desarrollaron.

15

Figura 7: Carcter adelgazadousando Zhang-Suen con post-

procesamiento de Holt

Figura 8: Carcter adelgazadousando Zhang-Suen con

preprocesamiento Stentiford

Figura 9: Carcter adelgazadousando Zhang-Suen con

preprocesamiento Stentiford y conpost-procesamiento de Holt


16/87


i. Caractersticas binarias

Concepto

Una caracterstica binaria es una funcin aplicada a una imagen que slo puede tomar dosvalores: cierto y falso. El hecho de que solo se disponga de dos valores no supone una limitacin,una funcin que dada una imagen pueda generar N posibles resultados puede descomponerse enN-1 caractersticas binarias: cada caracterstica binaria sera cierta si la imagen cumple uno de los Nvalores posibles. Si todas son falsas eso implicara que la imagen tiene el valor no contemplado enlas N-1 caractersticas binarias.

Aplicacin

Las caractersticas se han implementado de forma que todas siguen una misma estructura dadapor una clase base que todas implementan. De esta forma aadir nuevas caractersticas es muysencillo, y adems permite a las bases de datos que las usan cargar todas las caractersticas de forma

dinmica (usando tcnicas de reflexin sobre las libreras donde se implementan dichascaractersticas), puesto que se conoce la clase de la que heredan.

Cada caracterstica tiene unas condiciones de rendimiento diferente, pero se puede conseguir unrendimiento muy aceptable trabajando sobre imgenes de un tamao pequeo (para lo que se debeusar el algoritmo de escalado durante el preprocesado).

Dependientes de los cambios de color en un eje

Las caractersticas dependientes de los cambios blanco-negro trabajan contando el numero decambios de color en los ejes situados en la mitad de la imagen, horizontal o verticalmente.

Las caractersticas binarias dependientes de los cambios blanco-negro son: ColorChangesXAboveFourCharacteristic

Tomar valor cierto cuando el nmero de cambios de color de blanco a negro en lnea mediahorizontal sea superior a cuatro y falso en caso contrario.

ColorChangesXBelowTwoCharacteristic

Tomar valor cierto cuando el nmero de cambios de color de blanco a negro en la lneamedia horizontal sea inferior a dos y falso en caso contrario.

ColorChangesXEqualsFourCharacteristic

Tomar valor cierto cuando el nmero de cambios de color de blanco a negro en la lnea

media horizontal sea igual a cuatro y falso en caso contrario. ColorChangesXEqualsTwoCharacteristic

Tomar valor cierto cuando el nmero de cambios de color de blanco a negro en la lneamedia horizontal sea igual a dos y falso en caso contrario.

ColorChangesYAboveFourCharacteristic

Tomar valor cierto cuando el nmero de cambios de color de blanco a negro en la lneamedia vertical sea superior a cuatro y falso en caso contrario.

ColorChangesYBelowTwoCharacteristic

Tomar valor cierto cuando el nmero de cambios de color de blanco a negro en la lneamedia vertical sea inferior a dos y falso en caso contrario.

16


17/87


ColorChangesYEqualsFourCharacteristic

Tomar valor cierto cuando el nmero de cambios de color de blanco a negro en la lneamedia vertical sea igual a cuatro y falso en caso contrario.

ColorChangesYEqualsTwoCharacteristicTomar valor cierto cuando el nmero de cambios de color de blanco a negro en la lneamedia vertical sea igual a dos y falso en caso contrario.

En la figura 10 se muestra un ejemplo de cambios de color con respecto a la lnea mediahorizontal y en la figura 11 con respecto a la lnea media vertical. Dependientes de la relacinanchura-altura.

Estas caractersticas se basan en medir la diferencia existente entre la altura y anchura de unaimagen. Para ello se compara el nmero de pxeles de la altura con el nmero de pxeles de laanchura.

Ntese que la altura y la anchura a efectos de esta caracterstica son la altura y la anchura delmenor rectngulo que contiene todos los pxeles negros de la imagen, no la altura y la anchura de laimagen (que podra ser siempre cuadrada independientemente de los contenidos si se usan losalgoritmos de preprocesado encuadre y escalado)

Las caractersticas binarias dependientes de la relacin anchura-altura son:

ThriceTallerThanWiderCharacteristic

Tomar valor cierto cuando la altura sea tres o ms veces mayor que la anchura y falso encaso contrario.

TwiceTallerThanWiderCharacteristic

Tomar valor cierto cuando la altura sea dos o ms veces mayor que la anchura y falso encaso contrario.

TallerThanWiderCharacteristic

Tomar valor cierto cuando la altura sea mayor que la anchura y falso en caso contrario.

17

Figura 10: Caractersticas binarias: cambios

de color respecto a la lnea media horizontal Figura 11: Caractersticas binarias:cambios de color respecto al eje de

ordenadas


18/87


Dependientes de los puntos finales

Estas caractersticas diferencian las imgenes en base a su nmero de puntos finales. Los puntosfinales en imgenes binarias son aquellos pxeles negros que slo poseen un vecino negro en 8-adyacencia.

Las caractersticas binarias dependientes de los puntos finales son:

EndingPointsEqualsOneCharacteristic

Tomar valor cierto cuando el nmero de puntos finales de la imagen sea igual a uno y falsoen caso contrario.

EndingPointsEqualsThreeCharacteristic

Tomar valor cierto cuando el nmero de puntos finales de la imagen sea igual a tres y falsoen caso contrario.

EndingPointsEqualsTwoCharacteristic

Tomar valor cierto cuando el nmero de puntos finales dela imagen sea igual a dos y falso en caso contrario.

EndingPointsEqualsZeroCharacteristic

Tomar valor cierto cuando el nmero de puntos finales dela imagen sea igual a cero y falso en caso contrario.

La figura 12 muestra un ejemplo de clculo de puntos finales.

Dependientes de los puntos de rbol

Estas caractersticas diferencian las imgenes en base a su nmero de puntos de rbol. Los

puntos de rbol en imgenes binarias son aquellos pxeles negros que poseen tres o ms vecinosnegros en 8-adyacencia.

Las caractersticas binarias dependientes de los puntos finales son:

TreePointsEqualsOneCharacteristic

Tomar valor cierto cuando el nmero de puntos de rbol de la imagen sea igual a uno yfalso en caso contrario.

TreePointsEqualsThreeCharacteristic

Tomar valor cierto cuando el nmero de puntos de rbolde la imagen sea igual a tres y falso en caso contrario.

TreePointsEqualsTwoCharacteristic

Tomar valor cierto cuando el nmero de puntos de rbolde la imagen sea igual a dos y falso en caso contrario.

TreePointsEqualsZeroCharacteristic Tomar valorcierto cuando el nmero de puntos de rbol de la imagensea igual a cero y falso en caso contrario.

La figura 13 muestra un ejemplo de clculo de puntos derbol.

18

Figura 12: Caractersticas binarias:puntos finales

Figura 13: Caractersticas binarias:puntos de rbol


19/87


Dependientes del nmero de pxeles

Estas caractersticas binarias se basan en dividir la imagen en regiones y analizar en cual de ellastiene dicha imagen ms pxeles. Existen tres grupos fundamentales dentro de estas caractersticasbinarias. El primero divide la imagen en dos mitades: la superior y la inferior. El segundo divide la

imagen en otras dos mitades: derecha e izquierda. Finalmente la tercera divide la imagen en cuatrocuadrantes: noroeste, noreste, sureste y suroeste.

Las caractersticas binarias dependientes del nmero de pxeles son:

PixelsLeftHalfCharacteristic

Tomar valor cierto cuando el nmero de pxeles de la mitad izquierda sea mayor que el dela derecha y falso en caso contrario.

PixelsNortheastQuadrantCharacteristic

Tomar valor cierto cuando el nmero de pxeles del cuadrante noreste sea mayor que el delas otras regiones y falso en caso contrario.

PixelsNorthwestQuadrantCharacteristic

Tomar valor cierto cuando el nmero de pxeles del cuadrante noroeste sea mayor que el delas otras regiones y falso en caso contrario.

PixelsSoutheastQuadrantCharacteristic

Tomar valor cierto cuando el nmero de pxeles del cuadrante sureste sea mayor que el delas otras regiones y falso en caso contrario.

PixelsSouthwestQuadrantCharacteristic

Tomar valor cierto cuando el nmero de pxeles del cuadrante suroeste sea mayor que el de

las otras regiones y falso en caso contrario. PixelsTopHalfCharacteristic

Tomar valor cierto cuando el nmero de pxeles de la mitad superior sea mayor que el de lainferior y falso en caso contrario.

Dependientes del nmero de agujeros

Estas caractersticas diferencian las imgenes segn su nmero de agujeros. Se define unagujero como un conjunto de pxeles blancos conexos en 4-adyacencia rodeados por un caminocerrado de pxeles negros con 8-adyacencia. Adems se define agujero grande como aquel cuyonmero de pxeles supera cierto umbral, actualmente 4. Esto se hace as para evitar el conteo

errneo de agujeros por las regiones blancas introducidas errneamente por el adelgazamiento sobreciertos caracteres.

Para contar el nmero de agujeros se ha utilizado unalgoritmo que permite contar el nmero de regiones blancas enuna imagen. El nmero de agujeros ser el nmero de regionesblancas menos uno, ya que no se debe contar el fondo blancoque rodea el contenido de la imagen.

Ntese que en la figura 14 hay un agujero grande (rayado)pero tambin un agujero pequeo (cerca de el punto donde

19

Figura 14: Nmero de agujeros


20/87


comienza el rabo de la a), producto del algoritmo de adelgazamiento, que sera descartado usandoel algoritmo actual.

Las caractersticas binarias dependientes del nmero de agujeros blancos de la imagen son:

NumberBigHolesEqualsOneCharacteristicTomar valor cierto cuando el nmero de agujeros sea igual a uno y falso en caso contrario.

NumberBigHolesEqualsTwoCharacteristic

Tomar valor cierto cuando el nmero de agujeros sea igual a dos y falso en caso contrario.

NumberBigHolesEqualsZeroCharacteristic

Tomar valor cierto cuando el nmero de agujeros sea igual a cero y falso en caso contrario.

La figura 14 muestra un ejemplo de clculo del nmero de agujeros. Puede verse un agujero deun nico pxel cerca de la parte inferior, que es considerado pequeo por el algoritmo actual y portanto no se contabilizara.

Estas caractersticas binarias son las que ms se benefician de un tamao de imagen pequeo enlo que respecta a la velocidad de aplicacin de los algoritmos involucrados.

ii. Receptores sobre la imagen

Concepto

El concepto de receptores sobre las imgenes se tom de unarticulo escrito en la web CodeProjectpor Andrew Kirillov[8], en elque eran usados tambin como etapa de extraccin de informacin de

la imagen para un sistema de OCR basado en redes neuronales.La idea es muy simple, basndose en posicionar sobre el

rectngulo que contiene la imagen una serie de segmentos, a los quellamamos receptores. Para cada segmento se comprobar si la imagentiene un pxel negro bajo la lnea, y el resultado ser un valorbooleano indicando el resultado de dicha comprobacin, como sepuede observar en el figura 15, en la que los segmentos (dispuestosaleatoriamente) que intersectan la imagen se muestran en verde, y losque no, en rojo.

Aplicacin

Para aplicar un receptor sobre la imagen, se pueden utilizar varios mtodos. El propuesto en lapgina citada anteriormente supone recorrer toda la imagen en busca de pxeles negros (lo que nosda una complejidad de orden cuadrtico) y cuando se encuentra, repasar una lista de receptores paraver si la posicin del pxel se encuentra dentro del segmento usando la ecuacin de la recta, yrepetir para todos los pxeles negros de la imagen (la cual es una operacin de coma flotante, y porlo tanto ms costosa en tiempo de procesador que una operacin con operandos enteros).

El tiempo necesario para comprobar una imagen se ha mejorado mucho utilizando para lacomprobacin los receptores sobre la imagen un mtodo muy diferente que resulta mucho mseficiente.

Para implementar este mtodo se ha usado un algoritmo de dibujado de segmentos, en concretoel algoritmo de Bressard. Lgicamente, en vez de dibujar el segmento en la imagen, lo que hacemos

20

Figura 15: Receptores sobre unaimagen preprocesada
http://www.codeproject.com/script/Membership/Profiles.aspx?mid=1181072http://www.codeproject.com/script/Membership/Profiles.aspx?mid=1181072http://www.codeproject.com/script/Membership/Profiles.aspx?mid=1181072http://www.codeproject.com/script/Membership/Profiles.aspx?mid=1181072http://www.codeproject.com/script/Membership/Profiles.aspx?mid=1181072http://www.codeproject.com/script/Membership/Profiles.aspx?mid=1181072http://www.codeproject.com/script/Membership/Profiles.aspx?mid=1181072http://www.codeproject.com/script/Membership/Profiles.aspx?mid=1181072


21/87


es usar los puntos que el algoritmo debera usar para dibujar para ver si la imagen tiene un puntonegro y si es el caso, la comprobacin fue positiva.

Esto reduce el numero de operaciones a efectuar de forma bastante apreciable. Por ejemplo, enimgenes previamente escaladas a 50 x 50 pxeles, y 30 receptores (valores por defecto para las

nuevas bases de datos con este mtodo, como veremos posteriormente), con el mtodo propuestopor el autor del artculo tenemos 50 x 50 x 30 = 7500 comprobaciones en el peor de los casos (yadems de coma flotante, que pueden llegar a ser cuatro veces ms lentas que las enteras) frente a

30502502

2=1060 operaciones enteras usando el mtodo del algoritmo de dibujado de

segmentos, calculado usando el nmero de receptores, se multiplica por la longitud del semento,que como mximo puede ser la mitad de la longitud de la diagonal de la imagen (por como se hadefinido el algoritmo, ya que se ha considerado que segmentos ms largos dejan de ser relevantes alser mucho ms posible que pase por un pxel negro de la imagen).

c. Almacenamiento de la informacin extrada, aprendizaje yreconocimiento

Las tcnicas para el almacenamiento de la informacin obtenida mediante los mtodosexplicados anteriormente se han desarrollado intentando obtener siempre una buena relacin entrela velocidad de reconocimiento, la precisin del mismo, y la adaptabilidad del mtodo (la capacidadde generalizar sobre los smbolos aprendidos).

Por orden temporal de desarrollo, y con la consecuencia de una cada vez mejor adaptacin a lospropsitos antes enunciados, los mtodos desarrollados (y que son usados en la implementacincomo se ver ms adelante) para solventar el problema de almacenar la informacin obtenida apartir de las imgenes son los siguientes:

i. rboles binarios

Los rboles binarios son una conocida herramienta para organizar un conjunto de informacinsobre el que se requiere una velocidad de bsqueda elevada, ya que la propia estructura del rbolsupone un concepto de orden sobre la informacin almacenada que no se encuentra en otrasestructuras de datos como las listas o los diccionarios.

Dado que la aplicacin de cualquiera de los mtodos desarrollados para la obtencin de lainformacin relevante para el reconocimiento a partir de una imagen devuelve un valor booleano, esrazonable asociar a cada nodo del rbol binario la aplicacin de una caracterstica binaria o receptorsobre la imagen, y en las ramas hijas se considerarn los casos para los que la comprobacin fue

cierta o falsa, como se aprecia en la figura 16.Para aprender un smbolo, basta con ir

aplicando las comprobaciones binarias para cadaelemento considerado segn el mtodo, e irexpandiendo el rbol. En el nodo de la ltimacomprobacin se almacena la estructura querepresenta al smbolo aprendido (generalmente elcarcter o una etiqueta formada por varioscaracteres, al estilo de algunos smbolos LaTeX).

Si en el nodo final que le corresponde a la

imagen segn sus parmetros ya existe unsmbolo con la misma etiqueta, se considera que

21

Figura 16: Estructura de un rbol binario para almacenarsmbolos

-

S No

-

S No

a, \alpha

S No

b

S No

-

S No

+

S No

Parmetro 2

Parmetro 1

Smbolos


22/87


ha habido un conflicto. En cualquier otro caso se aade la etiqueta de la nueva imagen al nodo hojaencontrado.

Para reconocer una imagen como un smbolo, se obtienen los parmetros binarios de la imagen,en el mismo orden que se aplican para aprenderlos, y se va recorriendo el rbol tomando las ramas

derecha o izquierda del rbol segn vayan siendo los resultados obtenidos. Los smbolos asociadossern aquellos que estn en el nodo hoja que le corresponda a la imagen.

Este mtodo de reconocimiento es muy rpido, ya que su duracin es lineal respecto del nmerode parmetros que haya que comprobar sobre la imagen. Sin embargo, es muy estricto respecto aque requiere mucha precisin por parte de los parmetros a tener en cuenta. De esta forma, unparmetro aplicado a la imagen que cambie de valor hace que entremos en una rama del rboldistinta a la que almacena al smbolo buscado y por lo tanto hace que este mtodo no searecomendable por su poca capacidad de admitir una cierta tolerancia a la variabilidad en losparmetros de reconocimiento.

ii. Vectores binariosDada la limitacin expuesta para el mtodo anterior, se desarroll una nueva solucin buscando

una mejor resistencia a la variabilidad antes mencionada, consistente en almacenar la informacinde los parmetros asociado a un conjunto de smbolos en vectores que admitan valores binarios , ydefinir un concepto de distancia entre estos vectores para que podamos tener un determinadoumbral de reconocimiento que permita hacer ms flexible el proceso.

El proceso de aprendizaje, que se muestra en lafigura 17, consiste en calcular el vector de parmetrosbinarios correspondiente a la imagen, aplicndolealguna de las tcnicas de extraccin de la informacinvistas anteriormente. Una vez tenemos este vector, lobuscamos en una lista de vectores para ver si yaexiste. Si no es el caso, aadimos el vector junto conel smbolo que se ha asociado a la imagen. Si existeya, lo que se debe hacer es ver si ya tiene asociado elsmbolo (en cuyo caso tenemos un conflicto), o no, encuyo caso se aadir a la lista de smbolos asociado al vector.

El reconocimiento de un carcter, como semuestra en la figura 18, se realiza calculando elvector de parmetros binarios para la imagen, e ircomprobando todos los vectores almacenados, para

ver si la distancia al de la imagen cuyo smboloqueremos obtener es menor que un determinadoumbral (en cuyo caso los smbolos asociados seaadirn al conjunto de smbolos para la imagen areconocer), que debe depender de la longitud dedichos vectores linealmente, ya que de esta formaevitamos que un mayor nmero de parmetrosprovoque un reconocimiento ms estricto, perdiendode esta forma el sentido de usar un umbral.

Esta distancia se define como el producto escalar entre los dos vectores (el almacenado, y elconstruido para la imagen), pero como tratamos con vectores de valores binarios, puede

implementarse fcilmente como un simple conteo de las diferencias entre ambos vectores.

22

Figura 17: Aprendizaje con vectores binarios

Calcular el vector de parmetros

Existe elvector?

Aadirlo junto conel smbolo

vcontieneal smbolo?

Informar de queya se aprendi

No

S, es v

S

Aadir elsmbolo a v

No

Figura 18: Reconocimiento con vectores binarios

Calcular el vector parala imagen, i

Quedan

vectores almacenados porcomprobar?

Devolvemos el conjunto desmbolos para la imagen

No

Considerar un nuevovector almacenado, v

S

d(v, i) < umbral

Aadir los smbolos deval conjunto resultado

S

No


23/87


Este proceso es algo ms lento al reconocer que el uso de rboles binarios, ya que es necesariorecorrer todos los vectores almacenados, pero es capaz de devolver ms smbolos dependiendo devariaciones en un cierto nmero de parmetros dependiendo del umbral, lo cual lo hace msadecuado para reconocer.

iii. Vectores de tres estados

Un paso ms hacia conseguir un reconocimiento de caracteres fiable y rpido supone el aadir lacapacidad de generalizacin sobre la informacin aprendida. Para ello una posibilidad es detectarque parmetros considerados durante la extraccin de la informacin no son relevantes para undeterminado smbolo. La estructura para los vectores triestado es similar a la que se vio para losvectores binarios, excepto por que aceptan un tercer valor, que denotaremos como ? o noimporta para complementar los cierto y falso que tenamos anteriormente.

El algoritmo de aprendizajede la figura 19 cambia bastante

respecto del visto anteriormente,como se puede apreciar en lafigura , porque es aqu donde seimplementa la mencionadageneralizacin. El procesoconsiste en buscar si existe unvector en la base de datos quecontenga el smbolo quequeremos asociar a la imagen. Sino existe, aadimos el vectorgenerado junto con el smbolo.

Si existe, en los lugares delvector almacenado que noconcuerden con los del vector de la imagen, se sustituye la informacin que est almacenada (0,1) por un elemento ?, indicando de esta forma que dicho parmetro no importa para el carcterque estamos aprendiendo.

El proceso de reconocimiento es idntico al visto para los vectores binarios, salvo queredefinimos el concepto de distancia para que no tenga en cuenta aquellas componentes del vectoralmacenado en la base de datos que se hayan marcado no importantes para el smbolo. Como en elcaso del vector binario, la distancia umbral depende de la longitud del vector de parmetros, salvoque en este caso a esta longitud se le resta el nmero de parmetros que se han ignorado. De estaforma, cuando ignoramos ms parmetros, permitimos menos fallos al reconocer, para no hacer que

al reducir el nmero de parmetros hagamos el vector de reconocimiento tan general que cualquierimagen resulte en una coincidencia.

d. Segmentacin

Si ninguna de las bases de datos que hayamos utilizado durante el reconocimiento de unaimagen nos ha devuelto un smbolo, debemos considerar la opcin de que dicha imagen norepresentase un smbolo, sino un conjunto de smbolos. Para poderlos reconocer, debemos trocear laimagen y trocearla de forma que cada subimagen obtenida contenga un smbolo (o un conjunto desmbolos, ms pequeo, para aplicar este proceso de forma recursiva).

23

Figura 19: Aprendizaje con vectores triestado

Calcular el vectorde la imagen, i

Existe elsmbolo en la base

de datos?

Aadir ia la basedatos con el smbolo

No

S, es vQuedan

parmetros de iy v porcomparar?

i[k]=v[k]

S, en la posicin k

v[k] ?

No

S

Guardar vcon lasmodificaciones

No


24/87


Una primera aproximacin a la segmentacin es la separacin de los caracteres de la imagen porlos espacios en blanco que hay entre ellos, que llamaremos huecos, tanto horizontalmente comoverticalmente. Para simplificar este proceso definimos proyecciones para la imagen:

Proyeccinhorizontal

Se recorre la imagen obteniendo el nmero depxeles negros que hay en cada columna (recurdeseque la imagen se preprocesa, por lo que estbinarizada). El resultado por tanto es un vector de Ncomponentes, cada una de ellas indicando el nmerode pxeles negros en la columna apropiada.

Proyeccinvertical

Idntica a la proyeccin horizontal, pero se calcula elnmero de pxeles negros en cada fila.

Estos conceptos pueden apreciarse en la figura 20.Vemos que los espacios entre caracteres en la proyeccin horizontal presentan no acumulan ningnpxel, creando un hueco, dado que no hay ningn pxel negroen dichas columnas.

Los algoritmos de segmentacin ms simples ideados seaprovechan de este hecho para decidir por dnde cortar lasimgenes. El problema es que no todas las imgenes quepueden (y deben) ser segmentadas presentan huecos quepodamos aprovechar, como se muestra en la figura 21. Porello es necesario algoritmos ms complejos como elsegmentador en cascada que funciona con un proceso

iterativo sobre la imagen a segmentar que simula la forma enque un fluido rodea a un objeto al caerle desde arriba.

Los algoritmos segmentado desarrollados son lossiguientes:

i. Segmentador horizontal

La segmentacin horizontal toma este nombre porque utiliza proyecciones horizontales (ver lafigura 20) para determinar los huecos en blanco.

Cortando por las posiciones de inicio y finalizacin de estos huecos, extraemos todas las

posibles zonas de la imagen con esta orientacin.

ii. Segmentador vertical

El segmentador vertical funciona exactamente igual que el horizontal, salvo que considera loshuecos encontrados con una proyeccin vertical, extrayendo todos los trozos entre los lmites de loshuecos obtenidos en dicha proyeccin.

En el trabajo[2] a partir del cual se ha desarrollado este proyecto fin de carrera, esta algoritmo eradistinto, utilizndose algoritmos especializados para la deteccin de caractersticas sintcticas de laformula analizada, como detectar numeradores y denominadores de fracciones, etc., a la vez que sehaca el reconocimiento de smbolos, una tarea que requiere una informacin que no tenamos an,

24

Figura 20: Proyecciones de una imagen

Figura 21: Imagen sin huecos, perosegmentable


25/87


y por tanto un enfoque equivocado que se ha eliminado de este proyecto, para realizar esa tarea mstarde y con toda la informacin necesaria disponible, como veremos posteriormente.

iii. Segmentador en cascada

El segmentador en cascada es la herramienta desarrollada para resolver casos como los vistos enla figura 21.

El funcionamiento se basa en partir del borde superior de la imagen e intentar buscar el bordeinferior. Para ello buscamos un pxel blanco en la imagen que tenga bajo l un pxel negro, paratener un punto inicial a partir del cual trabajar. A partir de este momento, se sigue iterativamente unproceso de bsqueda de un pxel blanco, dando prioridad a la bajada hacia el borde inferior de laimagen, pero tambin pudiendo desplazarnos lateralmente y en diagonales.

Una vez que hemos llegado al borde inferior, habremos construido a partir del recorrido por lospxeles hecho en el paso anterior una imagen con una lnea desde el borde superior de la imagen alborde inferior. Coloreando de negro una de las dos regiones de la imagen que quedan divididas por

dicha lnea, podemos usar esta imagen y su inversa para obtener dos regiones de la imagen original,habiendo separado al menos dos smbolos. El proceso puede ser visto grficamente en la figura 22.

En la figura se aprecia que inicialmente rotamos la imagen y luego deshacemos la rotacin. Esto sehace as para poder aplicar el algoritmo (que siempre funciona del borde superior al inferior) desdetodos los bordes de la imagen. Tambin se puede reflejar horizontalmente la imagen, resultando untotal de 8 combinaciones posibles para aplicar el algoritmo.

Este algoritmo de segmentado extrae (si tiene xito) dos imgenes. Se podra hacer que extrajeratodas las componentes conexas de la imagen, aplicando el algoritmo repetidamente con las ochocombinaciones de rotacin y reflexin mencionada. Sin embargo, debemos ser ms conservadores,ya que obtener todas las componentes conexas nos dara ms subimgenes de las que realmentenecesitamos, separando por ejemplo el punto de una i, empeorando el reconocimiento.

25

Figura 22: Segmentacin en cascada

Giramosla imagen

Extraemos la lneade segmentacin

Deshacemos la rotacin

+

+

Rellenamos una delas dos regiones

Segmentamos


26/87


De hecho, debemos ser conservadores con la segmentacin en general, e ir aplicando losalgoritmos de los que disponemos nicamente hasta que uno de ellos sea capaz de segmentar laimagen. En el momento en que esto ocurre, debemos dejar de aplicar los algoritmos de segmentadoy aplicar el reconocimiento de caracteres de nuevo. Al ser conservadores, las imgenes que

intentamos reconocer como smbolos contienen ms informacin (por ejemplo y como se hacomentado, smbolos formados por varias componentes conexas).

e. Smbolos reconocidos

Una vez que la imagen ha sido segmentada y reconocida por completo, debido a la recursividaddel proceso obtenemos un rbol de imgenes, en el que un padre contiene la imagen de la que seextrajeron las imgenes de los nodos hijos. Los nodos hoja del rbol contienen los smbolosasociados a la imagen. Idealmente, slo debe haber un smbolo por nodo hoja del rbol construido.

Estos smbolos poseen informacin, adems de como es lgico el propio smbolo matemticoque representan, su posicin en la imagen original, su tamao, etc.

Pero puede ocurrir que no hayamos sido capaz de obtener un smbolo de una base de datos parala imagen del nodo, y no hayamos podido segmentar ms la imagen. Tambin puede ocurrir que losparmetros de la imagen concuerden con varios smbolos distintos en una base de datos (o varias).

En este caso, el proceso de segmentacin y reconocimiento de caracteres ha fallado, y la ayudadel usuario para aprender los caracteres no reconocidos o seleccionar entre las varias opcionesencontradas.

2.2. Secuenciacin y anlisis lxicoEn principio, los smbolos obtenidos en la fase de segmentacin y reconocimiento de caracteres

no nos sirven como unidades mnimas de informacin con sentido para el lenguaje de lasmatemticas, porque estos smbolos, por s mismos no aportan toda la informacin necesaria para ellenguaje de las matemticas.

Estas unidades mnimas de informacin, que en procesamiento de lenguajes formales sedenominan tems (o tokens, en ingls), ser, de forma general, un conjunto de smbolos. Un tem esel equivalente a un lexema en una palabra de un lenguaje natural, portando la informacin designificado un determinado conjunto de smbolos que lo forman.

Por qu decimos que un smbolo no contiene toda la informacin, y un item s? Por ejemplo, sihemos reconocido los smbolos 2, 3, . y 4, trabajar con estos smbolos es errneo, ya queen la formula original de donde se extrajeron los caracteres estaran formando el nmero 23.4,que por tanto s es una unidad lxica o tem.

Los tems, por tanto, estarn formados por uno o varios smbolos, que tendrn asociados unaetiqueta segn su significado en el lenguaje matemtico. Tendremos tems nmero,identificador, operador , etc.

Sin embargo, dada la naturaleza del problema, no podemos utilizar las tcnicas utilizadas enprocesamiento de lenguajes formales, consistentes en aplicar un analizador lxico (scanner, eningls) directamente a una entrada lineal de smbolos, porque nuestros smbolos no vienen dados,como se ha visto antes, nicamente por su posicin horizontal sino que estamos en un caso deorganizacin bidimensional. Para poder aplicar un analizador lxico debemos, por tanto, reducireste caso bidimensional a mltiples casos unidimensionales para poder aplicar la tecnologa queconocemos, lo cual resulta en un paso previo al anlisis lxico que hemos llamado secuenciacin.

26


27/87


Por lo tanto, los problemas a los que nos enfrentamos desde un punto de vista lxico son lasecuenciacin, y el anlisis lxico:

a. Secuenciacin

Como hemos visto anteriormente, paranosotros la secuenciacin ser un paso previoal anlisis lxico que nos permita reducir lacomplejidad propia de nuestro problemaconcreto (en este caso, la bidimensionalidad),para poder utilizar tcnicas ya conocidas. Encierto modo, es similar al preprocesamientoque realiza, por ejemplo, un compilador paraobtener una secuencia de smbolos lineal, en elque exista un concepto claro de siguiente.

En el caso del compilador, basta con eliminar retornos de carro y espacios en blanco entresmbolos (excepto los casos en que estos espacios en blanco no se usan como separador sino quetienen un significado, formando parte de cadenas de caracteres, por ejemplo).

Nuestro caso es bastante ms complicado, ya que debemos renunciar a obtener una nicasecuencia lineal de caracteres, dado que sisimplemente ordensemos los smbolos segn laposicin horizontal del smbolo, romperamos muyposiblemente secuencias de smbolos que debenformar parte de un tem, como se muestra en lafigura 24.

Para poder extraer secuencias de tems que se consideren que estn en la misma lnea, debemostener en cuenta los conceptos tipogrficos de lnea de base y altura del cuerpo de un carcter,definidos segn el tipo de letra que se usa parala imagen, explicados en la figura 25. Se sueletomar la altura de una x como la medida delcuerpo de una determinada fuente.

Se considerar que dos smbolos estn en lamisma lnea si comparten la lnea de base, yson cercanos (definiendo la cercana como queno estn separados horizontalmente ms de un

tanto por ciento de la media del ancho de la imagen que contiene los smbolos involucrados en la

comprobacin).De esta forma se van buscando secuencias, estando la primera de ellas formada por el smbolo

ms a la izquierda. Los siguientes smbolos se irn comprobando con el ltimo smbolo de cada unade las secuencias definidas en pasos anteriores. Si el nuevo smbolo considerado forma parte de lasecuencia se aade y se toma otro smbolo. Si no, se aade una secuencia nueva para ese smbolo.

As, al final obtenemos una lista de secuencias de smbolos, que podemos tratar en el anlisislxico.

27

Figura 23: Un compilador tambin necesita preparar laentrada para el anlisis lxico

#include

void main (void){

printf(hola mundo!);}

#includevoidmain(void){printf(hola mundo!);}

Figura 24: Ordenar los smbolos rompe los tems

Figura 25: Parmetros de la tipografa

x t r f y Altura del cuerpoLnea de base


28/87


b. Anlisis lxico

El anlisis lxico consistir en aplicar una serie de reglas lxicas en un determinado orden a unasecuencia de smbolos, hasta que se encuentren los tems que contiene, repitindose esto para todaslas secuencias de smbolos obtenidas en el paso de secuenciacin.

Una regla se compone de una serie de patrones (expresadas en forma de expresiones regulares) yun etiqueta, que servir a la vez para identificar la regla, y como tipo para los tems creados por laconcordancia de un conjunto de smbolos con alguno de los patrones de la regla.

El orden en que se aplican las reglas y los patrones que contienen es importante, ya que permiteal usuario definir reglas similares con ms o menos prioridad segn este orden.

La aproximacin utilizada difiere del modelo utilizado en los procesadores de lenguajesformales en los que basamos nuestros mtodos, en en los que el anlisis lxico funciona supeditadoal analizador sintctico, extrayendo un nuevo tem bajo demanda cuando se requiere. Nuestromtodo para este caso es distinto, y lo que se hace es extraer todos los tems directamente. Otradiferencia es las expresiones regulares para todos las reglas se comprueban a la vez, mediante laconstruccin de un autmata de pila, y nosotros vamos comprobando regla a regla por simplicidad.

Cuando no se detecta un tem en una secuencia determinada, eliminamos el ltimo smbolo, yvolvemos a comprobar con las reglas sobre la secuencia con los smbolos que nos han quedado. Sivuelve a no poder ser reconocido, el ltimo smbolo se inserta en una secuencia previo a los que sefueron descartados antes. Si una subsecuencia de la secuencia de smbolos original concuerda conuna regla, volvemos a repetir el proceso sobre la secuencia de los smbolos descartados, para verque tems les corresponden.

En vez de extraer los tems bajo demanda del analizador sintctico, lo que hacemos es extraertodos los tems posibles de cada una de las secuencias de smbolos obtenidas en el proceso desecuenciacin descrito anteriormente, de una forma voraz.

Al final de proceso, para cada secuencia habremos obtenidos una lista de tems, cada uno elloscon un determinado tipo, el texto que representan (la concatenacin de los textos de los smbolosque los componen), y la imagen de la que se obtiene el tem (la unin de las imgenes de lossmbolos que lo componen), junto con la posicin y tamao de la misma. La unin de las listas detems de cada secuencia, con los tems ordenados por su posicin horizontal son los datos deentrada de la fase de anlisis sintctico.

2.3. Anlisis sintctico

a. Estructura general del mtodoSe llama anlisis sintctico al proceso de analizar una secuencia de tems de entrada utilizandopara ello una gramtica formal, que no es ms que una descripcin precisa de un lenguaje formal.Una gramtica formal describe que clase de construcciones son vlidas en un determinado lenguaje,pero no nos dice su significado (en nuestro caso, por ejemplo, significa que lo que hacemos esreconocer la estructura de las frmulas y actuar en consecuencia, pero no evaluamos las expresionesmatemticas), utilizando para ellos reglas de transformacin de secuencias de tems.

Formalmente, segn la definicin de Chomsky[3], una gramtica G, se define como una tupla (N,, P, S) donde N representa un conjunto de smbolos no terminales (etiquetas de las reglas deproduccin), representa un conjunto de smbolos no terminales (el vocabulario de la gramtica, esdecir, los tipos de tems que se pueden usar), P es el conjunto de reglas de produccin, y S es unaregla de produccin especial denominada regla de inicio.

28


29/87


Las reglas de produccin son construcciones de la forma (N )* N(N )* ( N )* (de forma general, nosotros usamos una simplificacin de esto, como veremos a continuacin)donde * representa el operador estrella de Kleene, de concatenacin mltiple no obligada de uncierto elemento en una secuencia.

En la practica, la expresin anterior significa que los smbolos que aparecen a la izquierda de laflecha puede ser sustituido por los elementos de la derecha, ya sea por aplicacin de otras reglasrecursivamente (si se trata de elemento de N) o retirando un tem de la entrada (si se trata de unelemento de ).

Vamos a ver un ejemplo de esto definiendo una gramtica sencilla, y obviando el proceso deanlisis lxico:

N = {A, B, C}

= {'0', '1', '+'}

P = {A B,A BC, B '0', B '1', C '+'A}

S =ASi partiendo de S vamos

sustituyendo recursivamente lossmbolos que nombran lasproducciones por las partes derechade los smbolos de produccinvamos generando todas las entradasaceptadas por la gramtica, es decir,todas las frases del lenguaje,como se muestra en la figura 26.Esto es lo que se llama el lenguajede la gramtica, o L(G). En nuestragramtica de ejemplo, el lenguajeaceptado (o generado) sera L(G) ={0, 1, 0+0, 0+1, 1+0, 1+1, 0+0+0,0+0+1, 0+1+0, 0+1+1, 1+0+0,1+0+1, 1+1+0, 1+1+1, 0+0+0+0,0+0+0+1}, etc.

Invirtiendo este proceso, podemos, en vez de generar el lenguaje, analizar secuencias de entradapara ver si forman parte del mismo (y, de paso, realizar otras acciones sobre l).

Uno de tcnicas ms usuales para hacer esto son los reconocimientos de arriba a abajo (top-

down en ingls). En esta aproximacin, vamos, a partir de la regla inicial, recorriendorecursivamente las reglas y eliminando tems de la entrada.

Si el lenguaje cumple unas ciertas caractersticas (es LL(k), es decir, un lenguaje en el que esposible predecir cual es el tem de la posicin ken la secuencia de entrada sin necesidad de efectuarel reconocimiento), podemos hacer este recorrido de forma predictiva, ya que es posible construir,para cada regla, un conjunto con los tems que pueden aparecer en la posicin k-sima, de formaque podemos hacer un reconocimiento dirigido, sin necesidad de ir buscando regla por regla entrelas distintas posibilidades de sustitucin, e ir fallando en el caso de no haberse utilizado la reglaadecuada.

29

Figura 26: Generacin de un lenguaje a partir de su gramtica

A B

BC

0

1

0C

1C

0+A

1+A

0+B

0+BC

1+B

1+BC

0+0

0+1

1+0

1+1

0+0C

0+1C

1+0C

1+1C ...

...

...

...


30/87


En cualquiera de los dos casos, con un analizadorrecursivo, vamos generando un rbol de recubrimiento delos tems de entrada, en el que cada nodo representa unelemento elegido para reconocer, ya sea una sustitucin de

una regla de produccin o una correspondencia con un tem(que forman las hojas del rbol). Un ejemplo de esto, para laentrada 0+1+0 en el lenguaje definido anteriormentepuede verse en la figura 27.

b. Especializacin del mtodo paranuestro caso particular

Lo expuesto anteriormente representa el mtodo generalutilizado en anlisis sintctico, pero para nuestro casoparticular estos mtodos pueden ser simplificados en

algunos puntos, y deben ser ampliados en otros.Un punto donde podemos simplificar es en la estructura

de las reglas de produccin. Nuestras reglas no tendrn ensu parte izquierda ms que un smbolo no terminal, lo cualsignifica que el lenguaje aceptado no depende del contexto,es decir, para que la regla pueda usarse no se tiene en cuentael conjunto de tems que rodea al punto en el que se aplicala regla.

Sin embargo, hemos hecho la parte derecha de las reglasms expresivas, permitiendo utilizar los siguientes operadores sobre los smbolos terminales y noterminales (as como grupos de los mismos, delimitados por parntesis):

Operador ?

Indica que el smbolo no tiene porqu tener correspondencia en la secuencia de tems deentrada, siendo, de esta forma, opcional.

Operador *

Es el operador estrella de Kleene, con el significado usual. El smbolo que lo precede puedeno aparecer, o aparecer un nmero indeterminado de veces.

Operador +

Este operador es similar a la estrella de Kleene, salvo porque obliga a que el smbolo que lo

precede aparezca al menos una vez.La mayor riqueza expresiva que nos ofrece el uso de estos operadores nos permite reducir el

nmero de reglas a utilizar para definir conceptos. As, el conjunto de reglas de produccin definidoanteriormente quedara muy simplificado:P = {A B ('+' B)*, B 0, B 1}.

An podemos reducir ms el numero de reglas si permitimos fusionar reglas cuya parteizquierda (que puede verse como un identificador) sean iguales. El conjunto de reglas deproduccin quedara as:P = {A B ('+' B)*, B 0 | 1}.

Esto es un avance sobre la teora de procesamiento de lenguajes, en el que este aumento deexpresividad dificulta las demostraciones necesarias para justificar los mtodos de los que hemoshablado, pero no es suficiente para procesar el lenguaje de las matemticas tal y como aparece en

30

Figura 27: rbol de recubrimiento de unagramtica

A

BC

+ A

B

0

1

C

+ A

B

0


31/87


imgenes de frmulas debido a dos problemas que hemos enunciado anteriormente y a los quevamos a ver ahora las soluciones propuestas.

El problema de las relaciones espaciales con significado entre los smbolos se ha tratado aqu,definiendo unos operadores binarios que definen una relacin espacial entre un smbolo terminal

(un tem) de referencia, que antecede al smbolo del operador, y otro smbolo (o grupo desmbolos), en un determinada posicin: arriba , abajo , superndice , subndice , ndice de raz

, interior . Para reconocer las expresiones asociadas a estos smbolos, se calcula la secuencia de tems que se encuentran en la posicin indicada por el operador respecto al primer operando deloperador, o tem de referencia.

Esta secuencia auxiliar de smbolos relacionados con el smbolo de referencia se utiliza comoentrada de una nueva fase de anlisis sintctico, de esta forma no tenemos en cuenta los tems de laentrada que no podran pertenecer al superndice, subndice, etc., y simplificamos el problema.

Cuando construimos una secuencia relacionada en una posicin determinada, el momento deparar de aadirle smbolos es cuando encontramos el primer smbolo en una posicin normal (de

forma visual, en la misma lnea de base, pero de formal formal lo consideramos normal si no esten ninguna de las posiciones relativas especificadas anteriormente).

Podemos escribir la regla de produccin para una fraccin como

fracFRAC expresin expresin

y para una raz de ndice genrico como

raz RAZ expresin expresin.

Otra herramienta necesaria para poder analizar sintcticamente es la capacidad de romper elorden de bsqueda de tems dentro de la secuencia de tems de entrada. La justificacin de esto esten el problema de desorden de la entrada visto anteriormente. Por ejemplo, en la regla definida para

la raz el primer elemento esperado es el tem que contiene el smbolo de la raz, y sin embargo, lostems que corresponden a la expresin del ndice de la raz aparecern antes en la secuencia detems de entrada, ya que aparecen ms a la izquierda que el smbolo de la raz.

La solucin a este problema ha sido el permitir que los smbolosterminales que aparecen en las reglas de produccin (que como se havisto son los que retiran tems de la secuencia de tems de entrada)puedan marcarse en la definicin de las reglas para indicar que no tienenque aparecer en la posicin en que se han definido en la regla deproduccin sino que han de ser buscados. Cuando se busque un temdeterminado en la secuencia, han de tenerse en cuentas varios factores:

Se debe buscar un tem que no est ocultado por otroEsto quiere decir que debemos buscar un tem que no estprecedido por ninguno otro (exceptuando, como es lgico, losndices de las races, ya que sino el mtodo no nos servira).Tampoco es posible que el smbolo que elijamos estocultado por otro smbolo que lo cubra horizontalmente,esto permite que no nos adelantemos al reconocer

En la figuras 28 y 29 podemos ver un ejemplo de a loque nos referimos.

31

Figura 28: La raz estocultada por el smbolo de

fraccin

Figura 29: La raz esta ocultada por el 2,pero no por la y


32/87


Se debe buscar el tem con ms altura

El tem con ms altura, en los casos como races, sumatorios, integrales, etc., es el que tienems prioridad.

Esto nos ayuda a decidir en casos como el que se muestraen la figura 30, en los que hay varios smboloscorrespondientes al tem buscado que no estn ocultos y porlo tanto seran elegibles. S nos quedamos con el ms alto,nos aseguramos de estar eligiendo correctamente.

El hecho de que la entrada nos venga desordenada respecto decomo se definen las reglas de produccin tiene el inconveniente deque no podemos construir el conjunto primero para dichas reglas, ypor lo tanto no podemos utilizar un reconocimiento predictivo, sinoque debemos ir pasando por todas las expresiones que contiene una regla, e ir fallando no slo enlos fallos reales provocados por una entrada defectuosa (casos que no deberan producirse si la

entrada est bien construida), sino tambin habr fallos por haber entrado por una expresin de unaregla que no se corresponda con la entrada que estamos reconociendo de entre muchasposibilidades.

Por ello, no podemos tratar un error de reconocimiento como algo fatal, ya que debemos dar laoportunidad de si una alternativa falla, seguir reconociendo por otra rama posible del rbol derecubrimiento, que presentar ramas muertas que no nos fueron tiles para retirar tems de laentrada, pero s para decidir a que expresin realmente le corresponda a la entrada, utilizando unatcnica de fallo y vuelta a atrs (tambin conocida como backtracking).

Otro aspecto particular a tener en cuenta para nuestro sistema, es que aunque de forma generalen un sistema de anlisis sintctico se pueda aplicar cualquier tipo de accin al ir construyendo el

rbol de cobertura, nosotros hemos limitados estas opciones a ir generando la salida en texto segnun formato dado al definir las reglas sintcticas.

32

Figura 30: La raz principal es la quecontiene a la y, ya que es ms alta


33/87

Diseo e implementacin del software Reconocedor de texto matemtico

3. DISEO E IMPLEMENTACIN DEL SOFTWARE

Aparte del requisito funcional de crear una suite de programas que permitiera demostrar,

mediante la prctica, que los mtodos anteriormente expuestos son los adecuados a la hora deafrontar el problema del reconocimiento de texto matemtico, a travs de la implementacin dedichos mtodos, para realizar el software del proyecto se han tenido en cuenta otra serie decaractersticas al hora de desarrollar el software, de tipo no funcional, como son:

El uso del patrn Vista Modelo Controlador

Esto nos permitira por ejemplo, tener varias interfaces de usuario que utilizasen un mismocontrolador para realizar los procesos.

Un modo de ejecucin paso a paso

La ejecucin paso a paso de los distintos procesos implicados en la resolucin del problema

final permite observar grficamente la forma en que se comportan los mtodosdesarrollados, de tal forma que la aplicacin sea ms adecuada para una utilizacin didcticade la misma. Tambin es til para tareas de depuracin durante el propio desarrollo de laaplicacin.

Uso de formatos de archivos XML

El uso de un formato para el almacenamiento de la configuracin de los programas y lasbases de datos nos permite por un lado tener acceso a los datos de forma sencilla, porejemplo con un simple editor de texto, permitiendo que cualquier persona sea capaz decomprender la estructura de estos datos. Tambin es un formato con el que la aplicacinpuede trabajar de forma sencilla.

La divisin del software en mdulos segn su funcinPara esto se debe dividir el software en varios proyectos que colaboren para realizar la tareaesperada.

La implementacin sobre la plataforma Mono, e interfaces grficas en GTK#.

3.1. Arquitectura del sistema y diagramas de claseLa arquitectura del sistema es el resultado del proceso anlisis y diseo realizado como etapa

previa a la implementacin. Mediante el anlisis detectamos las necesidades

pfc luis roman

Documents