Universidad Nacional de San Agust́ın
Facultad de Producción y Servicios
Reconocimiento de Palabras en Manuscritos
Históricos Basado en Aprendizaje Online
Graciela Lecireth Meza Lovón
Orientador: Prof. Dr. José Eduardo Ochoa Luna
Tesis Doctoral presentada a la Facultad de
Producción y Servicios como parte de los re-
quisitos para obtener el grado de Doctor en
Ciencia de la Computación.
Julio, 2016
Reconocimiento de Palabras en Manuscritos Históricos
Basado en Aprendizaje Online
Este ejemplar corresponde a la redacción
final de la tesis doctoral defendida por
Graciela Lecireth Meza Lovón y aproba-
da por el jurado dictaminador.
Arequipa - Perú, Julio, 2016
Jurado Dictaminador:
Prof. Dr. Luis Alberto Alfaro Casas
Prof. Dr. Javier Leandro Tejada Cárcamo
Prof. Dr. José Eduardo Ochoa Luna (Orientador)
Agradecimientos
Primero, agradezco a Dios y a la vida por todo lo bueno y lo malo que han puesto
en mi camino. ¡Deb́ıa aprender tantas lecciones para crecer! En retrospectiva, miro
el camino andado y me siento feliz de haber salido fortalecida.
Agradezco a mis padres, Edward y Chela, por el amor incondicional que siempre
me han brindado, por haber inculcado en mi el deseo de superación y el sentido de
responsabilidad, por haberme enseñado las más grandes lecciones de mi vida, por
los “estos” y los “aquellos” que nunca terminaré de listar. Muchas veces se dice que
uno no elige a los padres, pero yo los elijo, una y mil veces, yo los elijo.
Agradezco a mis hermanos, Johanna y Giovanni por estar conmigo siempre que
los he necesitado, por haberme acompañado y haberse dejado acompañar en los
momentos tan dif́ıciles que nos tocó vivir en estos años. También agradezco a mi
cuñada Karen por darme a mis sobrinitos, Math́ıas y Thiago, quienes a pesar de
haber llegado en tiempos tan duros, me han dado momentos incréıbles de felicidad.
No quiero olvidarme de agradecer a mi abuela, mamá Zoilita, por el ejemplo de vida,
de fortaleza y de perseverancia.
Agradezco a mis amigos y amigas Muna, Nicola, Yan, Herbert, Marco V., Marco
P., Sharmeĺı y Carolina, por la diversión, por sus consejos, por haberme escuchado
cuando estaba triste y desalentada. Ustedes son mis grandes amigos y yo lamento
haber sido un poco ingrata.
Agradezco a mi asesor de tesis, Dr. José Ochoa Luna, por su apoyo, orientación y
buena disposición. También agradezco al profesor Luis Diaz, no solo por las suge-
rencias técnicas que contribuyeron a la consecución de esta tesis, sino también por
compartir sus conocimientos y consejos de hombre sabio.
Finalmente, agradezco al Consejo Nacional de Ciencia, Tecnoloǵıa e Innovación Tec-
nológica (CONCYTEC) por el apoyo financiero.
A mi Chelita, el gran amor de mi vida.
A mi Nañito, el mejor padre del mundo.
Resumen
En esta tesis se propone un método de reconocimiento online para la transcrip-
ción de palabras contenidas en manuscritos históricos. El método propuesto incluye
las etapas de: preprocesamiento, que emplea diversas técnicas para segmentar el
documento en imágenes de palabras; extracción de caracteŕısticas, que extrae in-
formación relevante usando, en este caso, caracteŕısticas basadas en el gradiente,
en particular, magnitud y orientación; y finalmente, el reconocimiento propiamente
dicho, donde se concentran las principales contribuciones de esta tesis.
En esta última etapa, se propusieron dos extensiones de la SVM-Online: la
primera permite que el modelo opere en escenarios con conjuntos de datos de más
de dos clases, para lo cual se usa la estrategia “uno contra uno”; la segunda extensión
permite que el modelo emita salidas probabiĺısticas y no sólo salidas discretas. Esta
última extensión es de vital importancia, ya que posibilita el correcto funcionamiento
del Reconocedor Basado en Grafos (RBG). El RBG es otra contribución de esta tesis
y tiene la finalidad de evitar la segmentación del documento a nivel de caracter.
Para ello, cada imagen a ser reconocida es representada por un grafo direccionado,
cuyas aristas están relacionadas a una subimagen y a una probabilidad. En función
de esta se estima, para cada arista, un costo que es empleado por el algoritmo
Dijkstra Modificado, también propuesto en esta tesis, para emitir la transcripción
de la imagen en cuestión.
Los experimentos fueron realizados con tres conjuntos de datos: el corpus Ejecu-
toŕıa y Certificación del Escudo de Armas de Apellidos, el corpus Cristo Salvador,
y el corpus Doña Germana de Foix.
En base a los experimentos realizados, podemos concluir que los resultados ob-
tenidos son satisfactorios en relación a otras propuestas de transcripción de textos
presentadas en la literatura.
Abstract
In this thesis, we propose a recognition method for transcribing words contained
in historical manuscripts. The proposed method is based on online learning and
includes the steps of: preprocessing, in which various techniques for segmenting
document images into words images are employed; feature extraction, which extracts
relevant information using, in this thesis, features based on the gradient magnitude
and orientation; and finally, the method includes the recognition itself.
The main contributions of this thesis are focused on the recognition phase. Two
extensions of the SVM-Online were proposed: the first one allows the model to
operate in scenarios with data sets containing more than two classes, and for this
end, it uses the strategy “one vs. one”; the second one allows the model to give
not only probabilistic outputs but also discrete ones. The other extension is also
important, since it enables the proper functioning of the Graph-Based Recognizer
(RBG). The RBG is another contribution of this thesis and its purpose is to prevent
the segmentation at character level. To this end, each word image to be recognized
is represented by a directed graph whose edges are associated with a subimage and
a probability. Based on such probability, the model estimates, for each edge, a cost,
that is subsequently employed by the Modified Dijkstra algorithm, proposed in this
thesis, to issue the sequence of characters that better suits the word image at hand.
The experiments were performed with three data sets, namely, the corpus Ejecu-
toŕıa y Certificación del Escudo de Armas de Apellidos, the corpus Cristo Salvador,
and the corpus Doña Germana de Foix.
Based on our experiments, we can conclude that the results are satisfactory in
relation to other proposals in literature.
Índice general
1. Introducción 14
1.1. Planteamiento del Problema . . . . . . . . . . . . . . . . . . . . . . . 14
1.2. Justificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3. Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.3.1. Objetivos Espećıficos . . . . . . . . . . . . . . . . . . . . . . . 17
1.4. Visión General del Modelo Propuesto . . . . . . . . . . . . . . . . . . 17
1.5. Contribuciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
1.6. Organización de esta Tesis . . . . . . . . . . . . . . . . . . . . . . . . 20
2. Fundamento Teórico 21
2.1. Aprendizaje de Máquina . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.2. Máquinas de Vectores de Soporte . . . . . . . . . . . . . . . . . . . . 22
2.2.1. Hiperplano de Separación Óptimo . . . . . . . . . . . . . . . 23
2.2.2. Hiperplano de Separación de Margen Blando . . . . . . . . . . 25
2.2.3. Hiperplano de Separación para Casos No Lineales . . . . . . . 26
2.3. Optimización Secuencial Mı́nima . . . . . . . . . . . . . . . . . . . . 27
2.4. Consideraciones Finales . . . . . . . . . . . . . . . . . . . . . . . . . 29
3. Revisión de la Literatura 30
3.1. Reconocimiento de Textos Manuscritos . . . . . . . . . . . . . . . . . 30
3.2. Modelos de Aprendizaje usados en el Reconocimiento de Manuscritos 32
3.2.1. Modelos Generativos: Modelo Oculto de Markov . . . . . . . . 33
3.2.2. Modelos Discriminativos . . . . . . . . . . . . . . . . . . . . . 33
3.3. Máquinas de Vectores de Soporte Online . . . . . . . . . . . . . . . . 36
3.4. Estimación de Probabilidad para Clasificación Multiclase . . . . . . . 38
3.5. Consideraciones Finales . . . . . . . . . . . . . . . . . . . . . . . . . 40
4. Reconocimiento de Palabras 41
4.1. Preprocesamiento . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
4.1.1. Aumento del Contraste . . . . . . . . . . . . . . . . . . . . . . 43
4.1.2. Corrección de la Inclinación de las Páginas . . . . . . . . . . . 44
4.1.3. Segmentación de las Páginas en Ĺıneas . . . . . . . . . . . . . 45
4.1.4. Corrección de la Inclinación de la Escritura . . . . . . . . . . . 47
4.1.5. Normalización de las Ĺıneas de Texto . . . . . . . . . . . . . . 47
4.1.6. Segmentación de las Ĺıneas en Palabras . . . . . . . . . . . . . 48
4.2. Extracción de Caracteŕısticas . . . . . . . . . . . . . . . . . . . . . . 49
4.3. Aprendizaje y Reconocimiento . . . . . . . . . . . . . . . . . . . . . 50
4.3.1. Aprendizaje: Máquinas de Vectores de Soporte Basadas en
Aprendizaje Online . . . . . . . . . . . . . . . . . . . . . . . . 50
7
ÍNDICE GENERAL
4.3.2. Aprendizaje: Extensión del Modelo de Bordes et al. para Cla-
sificación Multiclase . . . . . . . . . . . . . . . . . . . . . . . . 52
4.3.3. Aprendizaje: Extensión del Modelo de Bordes et al. para Sa-
lidas Probabiĺısticas . . . . . . . . . . . . . . . . . . . . . . . . 53
4.3.4. Reconocimiento: Descripción Formal del Problema . . . . . . . 56
4.3.5. Reconocimiento Basado en Grafos . . . . . . . . . . . . . . . . 56
4.3.5.1. Relación entre los Frames de una Imagen y su Grafo 57
4.3.5.2. Procedimiento de Construcción del Grafo . . . . . . 58
4.3.6. La Secuencia Óptima de Caracteres . . . . . . . . . . . . . . . 59
4.4. Consideraciones Finales . . . . . . . . . . . . . . . . . . . . . . . . . 66
5. Experimentos y Resultados 67
5.1. Descripción de los Corpus Utilizados . . . . . . . . . . . . . . . . . . 67
5.1.1. Cristo Salvador . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.1.2. Ejecutoŕıa y Certificación del Escudo de Armas de Apellidos . 68
5.1.3. Doña Germana de Foix . . . . . . . . . . . . . . . . . . . . . . 71
5.2. Medidas de Evaluación . . . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3. Descripción de los experimentos . . . . . . . . . . . . . . . . . . . . . 73
5.4. Resultados de los Experimentos de la Fase de Aprendizaje: Experi-
mentos 1 y 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.4.1. Corpus CS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.4.2. Corpus ECA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.4.3. Corpus Germana . . . . . . . . . . . . . . . . . . . . . . . . . 84
5.5. Resultados de la Fase de Reconocimiento: Experimento 3 . . . . . . . 89
5.5.1. Corpus CS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89
5.5.2. Corpus ECA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.5.3. Corpus Germana . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.6. Consideraciones Finales . . . . . . . . . . . . . . . . . . . . . . . . . 93
6. Conclusiones y Trabajos Futuros 95
6.1. Contribuciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
6.2. Publicaciones Relacionadas a esta Tesis . . . . . . . . . . . . . . . . . 96
6.3. Trabajos Futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
Bibliograf́ıa 106
Universidad Nacional de San Agust́ın - UNSA 8
Índice de tablas
5.1. Estad́ısticas del corpus CS. . . . . . . . . . . . . . . . . . . . . . . . . 68
5.2. Estad́ısticas del corpus ECA. . . . . . . . . . . . . . . . . . . . . . . . 68
5.3. Estad́ısticas del corpus Germana. . . . . . . . . . . . . . . . . . . . . 71
5.4. Resultados de la SVM-Offline ejecutado sobre el corpus CS usando
bloques de 3× 3 y 16 intervalos. . . . . . . . . . . . . . . . . . . . . 75
5.5. Resultados de la SVM-Offline ejecutado sobre el corpus CS usando
bloques de 5× 5 y 16 intervalos . . . . . . . . . . . . . . . . . . . . . 75
5.6. Resultados de la SVM-Offline ejecutado sobre el corpus CS usando
bloques de 3× 3 y 32 intervalos . . . . . . . . . . . . . . . . . . . . . 75
5.7. Resultados de la SVM-Offline ejecutado sobre el corpus CS usando
bloques de 5× 5 y 32 intervalos . . . . . . . . . . . . . . . . . . . . . 76
5.8. Resultados de la SVM-Online ejecutado sobre el corpus CS usando
bloques de 3× 3 y 16 intervalos. . . . . . . . . . . . . . . . . . . . . 77
5.9. Resultados de la SVM-Online ejecutado sobre el corpus CS usando
bloques de 5× 5 y 16 intervalos. . . . . . . . . . . . . . . . . . . . . 77
5.10. Resultados de la SVM-Online ejecutado sobre el corpus CS usando
bloques de 3× 3 y 32 intervalos. . . . . . . . . . . . . . . . . . . . . 77
5.11. Resultados de la SVM-Online ejecutado sobre el corpus CS usando
bloques de 5× 5 y 32 intervalos. . . . . . . . . . . . . . . . . . . . . 78
5.12. Resultados de la SVM-Offline ejecutado sobre el corpus ECA usando
bloques de 3× 3 y 16 intervalos. . . . . . . . . . . . . . . . . . . . . 80
5.13. Resultados de la SVM-Offline ejecutado sobre el corpus ECA usando
bloques de 5× 5 y 16 intervalos. . . . . . . . . . . . . . . . . . . . . 80
5.14. Resultados de la SVM-Offline ejecutado sobre el corpus ECA usando
bloques de 3× 3 y 32 intervalos. . . . . . . . . . . . . . . . . . . . . 80
5.15. Resultados de la SVM-Offline ejecutado sobre el corpus ECA usando
bloques de 5× 5 y 32 intervalos. . . . . . . . . . . . . . . . . . . . . 80
5.16. Resultados de la SVM-Online ejecutado sobre el corpus ECA usando
bloques de 3× 3 y 16 intervalos. . . . . . . . . . . . . . . . . . . . . 82
5.17. Resultados de la SVM-Online ejecutado sobre el corpus ECA usando
bloques de 5× 5 y 16 intervalos. . . . . . . . . . . . . . . . . . . . . 82
5.18. Resultados de la SVM-Online ejecutado sobre el corpus ECA usando
bloques de 3× 3 y 32 intervalos. . . . . . . . . . . . . . . . . . . . . 82
5.19. Resultados de la SVM-Online ejecutado sobre el corpus ECA usando
bloques de 5× 5 y 32 intervalos. . . . . . . . . . . . . . . . . . . . . 83
5.20. Resultados de la SVM-Offline ejecutado sobre el corpus Germana
usando bloques de 3× 3 y 16 intervalos. . . . . . . . . . . . . . . . . 84
5.21. Resultados de la SVM-Offline ejecutado sobre el corpus Germana
usando bloques de 5× 5 y 16 intervalos. . . . . . . . . . . . . . . . . 85
9
ÍNDICE DE TABLAS
5.22. Resultados de la SVM-Offline ejecutado sobre el corpus Germana
usando bloques de 3× 3 y 32 intervalos. . . . . . . . . . . . . . . . . 85
5.23. Resultados de la SVM-Offline ejecutado sobre el corpus Germana
usando bloques de 5× 5 y 32 intervalos. . . . . . . . . . . . . . . . . 85
5.24. Resultados de la SVM-Online ejecutado sobre el corpus Germana
usando bloques de 3× 3 y 16 intervalos. . . . . . . . . . . . . . . . . 87
5.25. Resultados de la SVM-Online ejecutado sobre el corpus Germana
usando bloques de 5× 5 y 16 intervalos. . . . . . . . . . . . . . . . . 87
5.26. Resultados de la SVM-Online ejecutado sobre el corpus Germana
usando bloques de 3× 3 y 32 intervalos. . . . . . . . . . . . . . . . . 87
5.27. Resultados de la SVM-Online ejecutado sobre el corpus Germana
usando bloques de 5× 5 y 32 intervalos. . . . . . . . . . . . . . . . . 88
5.28. Word Error Rate del RBG ejecutado con minf = 4 y SVM - Online
entrenado con parámetros γ = 0,058, C = 2, 3 × 3 bloques y 16
intervalos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.29. Word Error Rate del RBG ejecutado con minf = 5 y SVM-Online
entrenado con parámetros γ = 0,058, C = 2, 3 × 3 bloques y 16
intervalos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.30. Word Error Ratedel RBG ejecutado con minf = 6 y SVM-Online
entrenado con parámetros γ = 0,058, C = 2, 3 × 3 bloques y 16
intervalos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91
5.31. Word Error Rate del Reconocedor Basado en Grafos, propuesto en
esta tesis, versus el modelo de Romero et al. [77]. . . . . . . . . . . . 91
5.32. Word Error Rate del RBG ejecutado con minf = 4 y SVM-Online
entrenado con parámetros γ = 0,057, C = 4, 3 × 3 bloques y 32
intervalos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.33. Word Error Rate del RBG ejecutado con minf = 5 y SVM - Online
entrenado con parámetros γ = 0,057, C = 4, 3 × 3 bloques y 32
intervalos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.34. Word Error Rate del RBG ejecutado con minf = 6 y SVM-Online
entrenado con parámetros γ = 0,057, C = 4, 3 × 3 bloques y 32
intervalos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.35. Word Error Rate del RBG ejecutado con minf = 4 y SVM-Online
entrenado con parámetros γ = 0,048, C = 1, 3 × 3 bloques y 16
intervalos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.36. Word Error Rate del RBG ejecutado con minf = 5 y SVM-Online
entrenado con parámetros, γ = 0,048, C = 1, 3 × 3 bloques y 16
intervalos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.37. Word Error Rate del RBG ejecutado con minf = 4 y SVM - Online
entrenado con parámetros γ = 0,048, C = 1, 3 × 3 bloques y 16
intervalos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
Universidad Nacional de San Agust́ın - UNSA 10
Índice de figuras
1.1. Visión general del modelo propuesto. . . . . . . . . . . . . . . . . . . 19
4.1. Esquema de la propuesta de tesis en mayor detalle. . . . . . . . . . . 42
4.2. a)Imagen original. b) Imagen después de aumentar el contraste. Este
proceso hace que las áreas de texto resalten del fondo de la imagen. . 44
4.3. a)Imagen antes y b) después de aplicar el proceso de corrección de la
inclinación de una página generalmente producida durante el proceso
de digitalización del documento. . . . . . . . . . . . . . . . . . . . . . 45
4.4. Segmentación de la imagen de una página en imágenes de ĺıneas de
texto usando perfiles de proyección. . . . . . . . . . . . . . . . . . . . 46
4.5. Corrección de la inclinación propia de la escritura a mano usando
perfiles de proyección. . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.6. Tres zonas de la imagen de una ĺınea de texto: zona de los trazos
ascendentes, zona de los trazos descendentes y zona del cuerpo central
que captura la mayor información de la imagen. . . . . . . . . . . . . 48
4.7. a) Imagen antes y b) después del proceso de normalización, el cual
consiste en reducir la zona de los trazos ascendentes y descendentes
de tal manera que todas las imágenes tengan la misma altura. . . . . 48
4.8. Extracción de caracteŕısticas: Una imagen dividida en 3×3 zonas, pa-
ra cada zona se calcula la magnitud del gradiente, el cual se acumula
de acuerdo a su orientación en un vector de acumulación, n = 16. El
vector de caracteŕısticas resulta de concatenar los vectores de acumu-
lación de cada zona. . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
4.9. SVM-Online para K clases en la fase de entrenamiento. . . . . . . . . 52
4.10. SVM-Online para K clases en la fase de reconocimiento. . . . . . . . 52
4.11. División de una imagen en frames. p1 representa a la coordenada 0
en el eje x. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.12. Caracteres ‘i’ y ‘s’ se expanden a lo largo de 3 y 5 frames respectiva-
mente. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.13. Relación entre los frames de una imagen y los elementos constituyen-
tes de un grafo: nodos y aristas. . . . . . . . . . . . . . . . . . . . . . 59
4.14. Adición de aristas y nodos en el proceso de construcción del grafo que
representa una imagen. . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.15. Grafo resultante del proceso de construcción. . . . . . . . . . . . . . . 61
11
ÍNDICE DE FIGURAS
4.16. Grafo simplificado con dos únicos caminos: A = p1, p6, p11, p16, p20 de
longitud 4 y B = p1, p4, p4, p12, p16, p20 de longitud 5. c representa el
costo de cada arista, d la distancia desde el nodo origen hasta el nodo
en cuestión y h la altura máxima del nodo en cuestión. La distancia
mı́nima se almacena en el nodo p20 y representa el costo total mı́nimo
del camino más óptimo. . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.17. Ilustración del problema del algoritmo de Dijkstra. La ruta más corta
resaltada en azul es el camino A = p1, p6, p11, p16, p20 a pesar de que
el camino B = p1, p4, p4, p12, p16, p20 presenta mejores probabilidades
asociadas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
4.18. Ilustración de la solución dada por el algoritmo de Dijkstra modifica-
do. La ruta más corta está dada por el caminoB = p1, p4, p4, p12, p16, p20.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
5.1. Una página del Corpus CS. . . . . . . . . . . . . . . . . . . . . . . . 69
5.2. Una página del Corpus ECA . . . . . . . . . . . . . . . . . . . . . . . 70
5.3. Una página del Corpus Germana. . . . . . . . . . . . . . . . . . . . . 72
5.4. Resultados SVM-Offline - CS. Los mejores resultados para C = 3,
γ=0.058, γ=0.059, γ=0.061. bloques de 3 × 3 y 16 intervalos. . . . . 76
5.5. Resultados SVM-Online-CS. Los mejores resultados fueron obtenidos
usando γ=0.058, γ=0.059, γ=0.061, C = 2, bloques de 3 × 3 y 16
intervalos, validación cruzada de 3 iteraciones. . . . . . . . . . . . . . 78
5.6. Evolución de la Exactitud del Corpus CS. Los parámetros del método
del gradiente son bloques= 3×3, intervalos=16. Los parámetros para
el entrenamiento del SVM-Online son γ = 0,058, γ = 0,059, γ =
0,061, C = 2. Validación cruzada de 3 iteraciones. . . . . . . . . . . . 79
5.7. Resultados SVM-Offline - ECA. Los mejores resultados para γ=0.057,
γ=0.060, C = 3, bloques de 3 × 3 y 32 intervalos. . . . . . . . . . . . 81
5.8. Resultados SVM-Online - ECA. Los mejores resultados para γ =
0,057, γ = 0,048, γ = 0,051, C = 4, bloques de 3 × 3 y 32 intervalos. 83
5.9. Evolución de la Exactitud del Corpus ECA. Los parámetros del mé-
todo del gradiente son bloques= 3×3, intervalos=32. Los parámetros
para el entrenamiento del SVM-Online son γ = 0,057, γ = 0,048, γ =
0,051, C = 4. Validación cruzada de 3 iteraciones. . . . . . . . . . . . 84
5.10. Resultados SVM-Offline - Germana. Los mejores resultados para C =
2, γ=0.048, y C = 1, γ = 0,051, γ = 0,049, bloques de 3 × 3 y 16
intervalos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.11. Resultados SVM-Online -Germana. Los mejores resultados para C =
1 y γ = 0,049, bloques de 3 × 3 y 16 intervalos. . . . . . . . . . . . . 88
5.12. Evolución de la Exactitud del Corpus Germana. Los parámetros del
método del gradiente son bloques= 3×3, intervalos=16. Los paráme-
tros para el entrenamiento del SVM-Online son C = 1 y γ = 0,049.
Validación cruzada de 3 iteraciones. . . . . . . . . . . . . . . . . . . 89
Universidad Nacional de San Agust́ın - UNSA 12
Lista de Abreviaturas
BLSTM . . . . . . . Memoria Bidireccional a Corto y Largo Plazo - Bidirectional
Large Short Term Memory
CNN . . . . . . . . . . Red Neuronal Convolucional - Convolutional Neural Network
CS . . . . . . . . . . . . . Corpus Cristo Salvador
ECA . . . . . . . . . . . Corpus Ejecutoŕıa y Certificación del Escudo de Armas de los
Apellidos
HMM . . . . . . . . . Modelo Oculto de Markov - Hidden Markov Model
Germana . . . . . . Corpus Doña Germana de Foix
GHMM . . . . . . . Modelo Oculto de Markov Generalizado - Generalized Hidden
Markov Model
OCR . . . . . . . . . . . Reconocimiento Óptico de Caracteres - Optical Character
Recognition
RBG . . . . . . . . . . . Reconocedor Basado en Grafos
SMO . . . . . . . . . . Optimización Secuencial Mı́nima - Sequential Minimal Optimi-
zation
SVM . . . . . . . . . . Máquina de Vectores de Soporte - Support Vector Machine
SVM-Online . . Máquina de Vectores de Soporte Basada en Aprendizaje On-
line - Support Vector Machine Online
WER . . . . . . . . . . Tasa de Error de Palabra - Word Error Rate
13
Caṕıtulo 1
Introducción
Debido a la rápida evolución de los sistemas de almacenamiento masivo en térmi-
nos de capacidad y costo, y al interés en preservar la cultura material contenida
en documentos impresos y manuscritos antiguos, se ha incrementado considerable-
mente los proyectos relacionados a la digitalización de documentos. Por mencionar
un ejemplo, Larry Page, cofundador de Google, anunció la puesta en marcha de un
proyecto para digitalizar algunas colecciones de las bibliotecas de las universidades
de Harvard, Michigan, Oxford, Standord y New York [45]. Otro ejemplo es el de la
Biblioteca Virtual del Patrimonio Cultural de España 1, la cual contiene a la fecha
una colección digitalizada de 2208 manuscritos, que abarcan desde el año 770 al
1904, y que fueron escritos en idiomas tan variados como el castellano, provenzal,
catalán, valenciano, entre otros.
Generalmente, la gran mayoŕıa de documentos digitalizados no poseen transcrip-
ciones ya que los costos de transcripción son elevados, y además, en el caso de
documentos históricos, requieren de personal especializado, como historiadores y
paleógrafos, lo que eleva aún más los precios. La carencia de transcripciones limita
el tipo de consultas que pueden ejecutarse, pues aunque es posible consultar un re-
positorio usando campos como autor, t́ıtulo, año de publicación, etc., no es posible
efectuar consultas en base al contenido de los textos. En este sentido y con el fin de
posibilitar otras formas de indexación y búsqueda, es que se ha hecho imperativo
explorar nuevas formas de transcripción automática o semiautomática.
1.1. Planteamiento del Problema
Durante las últimas décadas grandes avances en el reconocimiento de escritura han
sido realizados; inicialmente, el mayor interés se enfocó en el reconocimiento de d́ı-
gitos y de caracteres aislados; y posteriormente, en aplicaciones con léxico cerrado
como el reconocimiento de códigos postales [63], de secuencias de d́ıgitos, y de pala-
1http://bvpb.mcu.es/es
14
Caṕıtulo 1. Introducción
bras que representan cantidades en cheques [32] [37]. Generalmente, en tales casos
se ha conseguido tasas de reconocimiento que permiten su aplicación en la práctica.
A pesar de los resultados promisorios, existen escenarios en los cuales las tasas de
reconocimiento no son razonables para ser usadas comercialmente. Ejemplos de estos
escenarios son las aplicaciones donde no hay restricciones para el número de palabras
que deben ser reconocidas; en particular, se puede mencionar el caso de la transcrip-
ción de documentos históricos. En esta aplicación, existen dificultades adicionales
que provienen de las caracteŕısticas propias de los documentos antiguos, como la
degradación del papel, el desvanecimiento de la tinta, la variedad de estilos de escri-
tura influenciada por la época en que fueron escritos, entre otros. Por tal motivo y
como fue mencionado anteriormente, el reconocimiento completamente automático,
en la práctica, ha producido tasas de reconocimiento poco aceptables [33] [54].
Tratando de lidiar con ese problema, es que el paradigma de reconocimiento comple-
tamente automático ha comenzado a cambiar a un enfoque en el cual el proceso de
reconocimiento recibe la retroalimentación de un experto. A este nuevo aprendizaje
se le conoce como Aprendizaje Interactivo, y recibe el nombre interactivo ya que el
usuario y el sistema interactúan, lo que finalmente, se refleja en mejores tasas de
reconocimiento.
Bajo el enfoque interactivo, la transcripción de documentos está dividida en dos
etapas: en la primera el reconocimiento es automático, i.e., sin intervención de un
experto; mientras que en la segunda un experto (un conocedor de escrituras antiguas,
como un paleógrafo) corrige en ĺınea la transcripción dada por el sistema, y este, lue-
go, produce una nueva transcripción usando la retroalimentación del experto. Cada
vez que el usuario corrige información en estados anteriores, las predicciones poste-
riores son más exactas, lo que consecuentemente reduce el esfuerzo de transcripción
del experto.
Lamentablemente, aunque el esfuerzo de posedición disminuye usando el aprendizaje
interactivo, dicho esfuerzo no es aprovechado del todo, ya que cuando el sistema
produce, en base a una interacción con el usuario, una nueva salida, dicha salida es
también una nueva entrada al sistema, que está complemente validada por el usuario;
y por lo tanto, podŕıa ser usada como nueva instancia de entrenamiento de algún
modelo de aprendizaje. Una caracteŕıstica indispensable que debeŕıa poseer dicho
modelo es que su estructura debeŕıa permitir que sus parámetros se ajusten conforme
llegan nuevas instancias de entrenamiento, i.e., sin necesidad de reentrenar de nuevo
usado los antiguos ejemplos de entrenamiento. A dicho paradigma de aprendizaje se
le denomina Aprendizaje Online. Desafortunadamente, de la revisión de la literatura
realizada, no se ha observado a la fecha ninguna propuesta de reconocimiento de
escritura a mano, que sea capaz de aprender usando el aprendizaje online.
Es importante aclarar que esta propuesta de tesis no se enfoca en el aprendizaje
interactivo, sino en un aprendizaje que al ser usado conjuntamente, lo repotenciaŕıa,
a saber, el aprendizaje online.
Universidad Nacional de San Agust́ın - UNSA 15
1.2. Justificación
1.2. Justificación
La digitalización de manuscritos históricos ha crecido en la última década debido al
abaratamiento de los dispositivos de almacenamiento masivo; sin embargo, muchos
de estos documentos no poseen transcripciones que permitan búsquedas por conteni-
do. Con el fin de producir tales transcripciones, se han propuesto varios métodos, los
que en su mayoŕıa siguen el enfoque de reconocimiento tradicional; es decir, aquel
donde los resultados son obtenidos de un proceso completamente automático; no
obstante, las tasas de reconocimiento obtenidas de aplicar este enfoque aún no son
aceptables para ser usadas comercialmente. De hecho esta situación no sólo sucede
en el área de escritura a mano, sino también en otras como el reconocimiento del
habla [83] y la traducción de documentos [49] [58] [59].
De cara a esta problemática, algunos autores han optado por un enfoque de apren-
dizaje semiautomático, el cual produce mejores predicciones, usando la retroalimen-
tación proveniente de la interacción entre sistema y el experto. Un aspecto funda-
mental de este enfoque es que se podŕıa sacar mayor ventaja de esa interacción, si
se le lograse incorporar el aprendizaje online; sin embargo y como se mencionó en
la sección anterior, dicho aprendizaje todav́ıa no ha sido explorado en el contexto
de documentos históricos.
Por otra parte, vale la pena mencionar que no sólo el área de reconocimiento de do-
cumentos históricos se beneficia con los aportes del aprendizaje online, sino cualquier
otra área donde se observen escenarios en los que:
a) sea costoso recolectar un conjunto importante de instancias de entrenamiento con
el que un modelo de reconocimiento pueda ser entrenado;
b) el ambiente sea cambiante y que debido a esa caracteŕıstica los parámetros del
modelo deban ajustarse a esos cambios.
c) existan restricciones de almacenamiento, ya que una caracteŕıstica del aprendizaje
online que es no necesita tener todo el conjunto de entrenamiento en memoria,
sino únicamente la instancia en base a la cual el modelo ajusta sus parámetros.
1.3. Objetivo
Proponer un modelo de reconocimiento de palabras que incorpore el aprendizaje
online a fin de que el sistema, a diferencia de las propuestas actuales, tenga la
capacidad de continuar aprendiendo.
Universidad Nacional de San Agust́ın - UNSA 16
Caṕıtulo 1. Introducción
1.3.1. Objetivos Espećıficos
Construir con conjunto de datos propio que sirva para realizar los experimentos
de esta investigación e de investigaciones futuras. Este objetivo se formula
en respuesta a que una de las principales dificultades de esta tesis fue que
la mayoŕıa de documentos usados en investigaciones relacionadas no están
disponibles, y los pocos disponibles, o no están anotados, o las anotaciones son
básicas, i.e., sólo poseen la transcripción de los documentos.
Adaptar técnica(s) de preprocesamiento de imágenes a fin de obtener imágenes
de palabras que se encuentren en la mejor condición posible y que sirvan de
entrada para el proceso de extracción de caracteŕısticas.
Adaptar técnica(s) de extracción de caracteŕısticas que permitan extraer la
información más relevante y que posibiliten la discriminación entre clases.
Extender el modelo de Máquina de Vectores de Soporte Basada en Aprendizaje
Online, que funciona para clasificación binaria, a escenarios de clasificación
multiclase, como es el caso de los conjuntos de datos utilizados en esta tesis.
Proponer un modelo de reconocimiento en el cual no sea necesario aplicar
técnicas de segmentación a nivel de caracteres. Es indispensable evitar dicho
proceso, puesto que en documentos escritos a mano, el proceso de segmentación
de texto en caracteres tiene un alto costo computacional.
1.4. Visión General del Modelo Propuesto
El modelo propuesto opera en dos modos, a saber, el modo de aprendizaje y el modo
de reconocimiento.
Cuando el modelo opera en el modo de aprendizaje, necesita de un conjunto de en-
trenamiento constituido por imágenes de caracteres, obtenidas mediante un proceso
semiautomático, que requiere tanto del módulo de preprocesamiento, para obte-
ner imágenes de palabras, como de un usuario, para segmentar manualmente las
imágenes en sus caracteres constituyentes. También usa el módulo de extracción
de caracteŕısticas para transformar las imágenes de caracteres en vectores reales
n-dimensionales, los cuales constituyen las entradas para entrenar la SVM.
Vale la pena mencionar que, la Máquina de Vectores de Soporte implementada en
este proyecto es una versión online; y que por lo tanto, aprende ejemplo por ejemplo,
i.e., sin necesidad de volver a ver un ejemplo por segunda vez. Como se mencionó en
secciones anteriores, esta caracteŕıstica es importante ya que el modelo puede seguir
aprendiendo de futuros nuevos ejemplos, habiendo inclusive terminado el proceso de
aprendizaje, y sin necesidad de reentrenar el clasificador.
Universidad Nacional de San Agust́ın - UNSA 17
1.5. Contribuciones
Además, usando las transcripciones de los conjuntos de datos, se crea un diccionario
y un modelo del lenguaje. En la parte superior de la Figura 1.1, se muestra el módulo
de Aprendizaje del modelo propuesto.
Cuando el modelo opera en modo de reconocimiento, no es necesario que las imágenes
de las palabras hayan sido manualmente segmentadas en sus caracteres constituyen-
tes; en vez de ello, se emplea un enfoque basado en grafos, que evita la segmentación
referida. En este enfoque, cada imagen de una palabra es representada por un grafo
direccionado, el cual se construye dividiendo verticalmente la imagen en ventanas
llamadas frames. Cada nodo del grafo representa una columna de la imagen (donde
un frame inicia), a partir de la cual se pueden tomar un número diferente de frames
consecutivos, i.e., se pueden tomar subimágenes de diferente anchura. Esta variedad
de opciones para obtener dichas subimágenes está asociada a las aristas que salen
del nodo en cuestión.
Aśı, cada arista está asociada a una subimagen, que se extrae a partir de la columna
señalada por su nodo de origen y que se extiende hasta la columna señalada por su
nodo de destino; sin embargo, cada arista no solo está asociada a dicha imagen sino
también a su vector de caracteŕısticas, obtenido del módulo de extracción de carac-
teŕısticas; y a la predicción de clase, obtenida de la Máquina de Vectores de Soporte
Basada en Aprendizaje Online previamente entrenada. Al reconocedor basado en el
enfoque anteriormente descrito, se le llamará Reconocedor Basado en Grafos.
Por otra parte, la idea fundamental del Reconocedor Basado en Grafos se basa en
que: el problema de reconocimiento de palabras, planteado como “el problema de
encontrar la secuencia óptima de caracteres” que mejor se ajuste a la información
de la imagen, puede ser reformulado como “el problema de encontrar la ruta de costo
mı́nimo” de un grafo; y por lo tanto, se lo podŕıa resolver empleando un algoritmo
como Dijkstra. Para dicha reformulación, se requiere asociar a cada arista un costo,
el cual bajo la formulación de esta tesis es calculado en función de la inversa de la
probabilidad de la clase predicha por la Máquina de Vectores de Soporte Basada en
Aprendizaje Online previamente entrenada. Note entonces, que las aristas del grafo
también están asociadas a una probabilidad.
Finalmente, habiendo obtenido la ruta de costo mı́nimo, y apoyándose en el dicciona-
rio y en el modelo del lenguaje creados durante la fase aprendizaje, el modelo provee
la secuencia de caracteres que mejor se acomoda a la imagen de una determinada
palabra. En la parte interior de la Figura 1.1, se muestra el Módulo de Aprendizaje
del modelo propuesto.
1.5. Contribuciones
Las contribuciones de esta tesis son las siguientes:
La primera contribución de esta tesis fue incluir el enfoque del aprendizaje
Universidad Nacional de San Agust́ın - UNSA 18
Caṕıtulo 1. Introducción
Figura 1.1: Visión general del modelo propuesto.
online en el sistema de reconocimiento de manuscritos históricos. Para ello,
fue necesario extender la propuesta de Bordes et al. [9] en dos aspectos. El
primer aspecto permite que el modelo de Bordes et al. [9] funcione para más
de dos clases, y el segundo, permite que el modelo emita salidas probabiĺısticas
aśı como también, salidas discretas. Estas salidas probabilistas son el insumo
del Reconocedor Basado en Grafos.
El Reconocedor Basado en Grafos constituye la segunda contribución de esta
tesis y tiene como propósito evitar la segmentación de la imagen de una palabra
en los caracteres que la constituyen. Para ello, cada imagen a ser reconocida
es representada por un grafo, cuyas aristas están asociadas a una subimagen y
a una probabilidad, en base a la cual se calcula un costo que es utilizado por
el algoritmo Dijkstra para producir la transcripción de la palabra.
Finalmente, uno de los problemas que se tuvo de encarar al inicio de este
proyecto de tesis fue que existen pocos conjuntos de datos de documentos
históricos sobre los cuales realizar experimentos. La mayoŕıa de ellos perte-
necen a proyectos particulares y no se encuentran disponibles. Por ello, otra
contribución de este proyecto fue crear un conjunto de datos propio.
Universidad Nacional de San Agust́ın - UNSA 19
1.6. Organización de esta Tesis
1.6. Organización de esta Tesis
Esta tesis está organizada en seis caṕıtulos:
En el primer caṕıtulo, se define el problema y se justifica la propuesta. Además,
se definen los objetivos, y se proporciona una visión general de modelo de
reconocimiento propuesto.
En el segundo caṕıtulo, se presentan los métodos básicos y el fundamento
teórico, sobre los cuales se apoya esta investigación. En este sentido, se describe
el modelo clásico de las Máquinas de Vectores de Soporte y el algoritmo de
Optimización Secuencial Mı́nima en las Secciones 2.2 y 2.3, respectivamente.
Ambos métodos son indispensables para entender el modelo de aprendizaje
online que forma parte de la propuesta de esta tesis.
En el tercer caṕıtulo, se expone el estado del arte dividiéndolo en cuatro sec-
ciones. En la Sección 3.1 se describe la evolución de los trabajos relacionados
con escritura a mano. En la Sección 3.2, se hace una revisión desde la pers-
pectiva de los modelos de aprendizaje, haciendo distinción entre los modelos
generativos y los modelos discriminativos; además, se brindan las razones que
motivan la utilización de las Máquinas de Vectores de Soporte. Aśı mismo, en
la Sección 3.3 se describen los modelos de aprendizaje online en el contexto
de las Máquinas de Vectores de Soporte. Finalmente, en la Sección 3.4 se pre-
sentan los métodos que permiten convertir valores discretos, correspondientes
a clases, a probabiĺısticos.
En el cuarto caṕıtulo, se presenta la propuesta de esta tesis. El caṕıtulo se
desarrolla según las etapas en la que se divide el proceso de reconocimiento
propuesto, a saber, preprocesamiento, descrito en la Sección 4.1; extracción
de caracteŕısticas, descrita en la Sección 4.2; y aprendizaje-reconocimiento,
descrito en la Sección 4.3. En esta última se centra la contribución de esta
tesis. El aprendizaje se lleva a cabo adaptando una Máquina de Vectores de
Soporte Basada en Aprendizaje Online; y el reconocimiento, representando
cada imagen por un grafo el cual incluye una Máquina de Vectores de Soporte
Basada en Aprendizaje Online previamente entrenada.
En el quinto caṕıtulo, se presentan los experimentos y resultados. Previamente,
se detallan los conjuntos de datos que se han usado en los experimentos.
En el sexto caṕıtulo, se exponen las conclusiones de la tesis y se describen
algunas ideas para trabajos futuros.
Universidad Nacional de San Agust́ın - UNSA 20
Caṕıtulo 2
Fundamento Teórico
En este caṕıtulo son descritos los fundamentos teóricos que cimientan esta tesis. En
la Sección 2.1 se abordan los conceptos de aprendizaje de máquina, y se describen
los tres tipos de aprendizaje que existen en esta área. Aśı mismo, es necesario, en
la Sección 2.2, ahondar en los conceptos teóricos de las Máquinas de Vectores de
Soporte toda vez que el algoritmo base escogido para esta tesis es una versión online
de ellas. Finalmente, en la Sección 2.3 se describe el método de Optimización Se-
cuencial Mı́nima que es una de las formas de implementar una Máquina de Vectores
de Soporte.
2.1. Aprendizaje de Máquina
Desde la invención de las computadoras, los cient́ıficos se han esforzado en crear
sistemas digitales que posean habilidades que se relacionan con la inteligencia, entre
ellas, el razonamiento, el lenguaje y la visión. Sin embargo e inclusive en los seres
humanos, estas habilidades no se desarrollaŕıan si no tuviéramos la capacidad de
adquirir conocimiento y usarlo en el futuro. A esta capacidad se le llama aprendizaje
y constituye el núcleo de la inteligencia humana.
En base a lo mencionado, un sistema artificial no podŕıa ser verdaderamente inteli-
gente, a menos que posea la capacidad de aprender. Tomando esto en consideración,
existe una área dentro de la Inteligencia Artificial, conocida como Aprendizaje de
Máquina, cuyo propósito es dotar a los dispositivos digitales de la capacidad huma-
na de aprender, sin que estos sean programados expĺıcitamente. Los algoritmos de
esta área utilizan algún tipo de experiencia directa o un conjunto de datos, también
llamado conjunto de ejemplos u observaciones.
Se pueden distinguir tres tipos de aprendizaje:
El primer tipo es el Aprendizaje Supervisado, en el cual un supervisor provee
una etiqueta (e.g. una clase) para cada ejemplo del conjunto de observaciones;
21
2.2. Máquinas de Vectores de Soporte
y durante el aprendizaje, el supervisor espera que el sistema ajuste sus pará-
metros de tal manera que la salida para un determinado ejemplo, sea aquella
que el supervisor etiquetó.
En el tipo de Aprendizaje No Supervisado no se cuenta con un supervisor que
provea algún tipo de conocimiento apriori sobre los ejemplos del conjunto de
datos; y por lo tanto, el sistema debe analizar por śı mismo la información,
y descubrir agrupamientos en el conjunto. Dependiendo del tipo de algorit-
mo usado pueden haber variaciones en el número de agrupamientos y en los
ejemplos que los constituyen.
El último tipo es el Aprendizaje por Refuerzo, en el cual el supervisor no
indica la etiqueta de las observaciones, sino que el sistema aprende gracias a la
recompensa o castigo provéıda por el supervisor. Aśı, cada vez que el sistema
produce una etiqueta tentativa para un determinado ejemplo, el supervisor
recompensa al sistema si la etiqueta tentativa es correcta, o lo castiga si la
etiqueta es incorrecta.
El objetivo del aprendizaje supervisado es encontrar una función que tome como
argumento un ejemplo de entrenamiento, y que prediga la salida indicada por su
etiqueta. La idoneidad de esa salida es evaluada en base a una función de pérdida,
cuya definición depende de la naturaleza de las etiquetas del conjunto de observacio-
nes. En caso de que una etiqueta sea un valor real perteneciente a un subconjunto
propio de los reales, Y ⊂ R, el aprendizaje toma el nombre de Predicción. Por el
contrario, si una etiqueta toma un valor simbólico perteneciente a un conjunto finito
no vaćıo de etiquetas o clases Y = {c1, c2, . . . , cp}, entonces el aprendizaje toma el
nombre de Clasificación. Por ejemplo, el problema de reconocimiento de las letras
del alfabeto español es un problema de clasificación donde Y está formado por las
letras de dicho alfabeto.
2.2. Máquinas de Vectores de Soporte
Las Máquinas de Vectores de Soporte - Support Vector Machines (SVMs) se fun-
damentan en la teoŕıa del aprendizaje estad́ıstico propuesta por Vapnik [10] para
resolver problemas de clasificación binaria. Su objetivo es encontrar el hiperplano óp-
timo, el cual se define como aquel que genera el mayor margen entre los ejemplos de
dos clases distintas. El problema de encontrar el hiperplano de mayor margen puede
ser formulado como un problema de optimización sujeto a ciertas restricciones.
En la Sección 2.2.1 se describe el problema de optimización para un escenario ideal,
donde los datos son linealmente separables. Para tomar en cuenta a los datos que
contienen ruido y que son casi linealmente separables, se incorpora el concepto de
variable de holgura, la cual permite encontrar hiperplanos de separación de mar-
gen blando, que son descritos en la Sección 2.2.2. Para escenarios en los cuales la
separación lineal no es posible, es necesario el uso de funciones kernel que simulan
Universidad Nacional de San Agust́ın - UNSA 22
Caṕıtulo 2. Fundamento Teórico
un mapeo de los datos en un espacio de dimensión mayor donde la separación es
posible; la descripción de este nuevo problema es visto en la Sección 2.2.3.
2.2.1. Hiperplano de Separación Óptimo
Sea H, un espacio vectorial con producto interno y x1,x2, . . . ,xm ∈ H, un conjun-
to de vectores pertenecientes a dicho espacio vectorial, donde cada vector xi está
asociado a una etiqueta o clase yi que puede tomar los valores +1 o -1. El i-ésimo
vector y su correspondiente clase forman un par denotado por (xi, yi). Cualquier
hiperplano del espacio vectorial H puede ser representado por
H = {x ∈ H|〈w,x〉+ b = 0},w ∈ H, b ∈ R, (2.1)
donde w ∈ H es un vector ortogonal al hiperplano H, b ∈ R es el bias, y 〈w,x〉 es el
producto interno de w y x, el cual representa la proyección del vector x en w. Aśı,
el hiperplano H es un conjunto que contiene todos vectores xi que al proyectarse en
w caen en el mismo punto de la ĺınea extendida por w.
Si la tupla (w, b) ∈ H × R, cumple con la restricción de que,
mı́n |〈wi,x〉+ b| = 1, (2.2)
i=1,...,m
entonces a dicha tupla se le denomina forma canónica del hiperplano H con respecto
a los vectores x1,x2, . . . ,xm ∈ H.
Nótese que cuando (w, b) satisface dicha restricción también lo hace la tupla (−w,−b).
Ambas tuplas generan dos hiperplanos diferentes, a saber, H+1 = {x ∈ H|〈w,x〉 +
b = +1} y H−1 = {x ∈ H|〈w,x〉+ b = −1}, los que a su vez originan las siguientes
funciones de decisión,
fw,b(x) = sgn(〈w,x〉+ b). (2.3)
Por otra parte, si se supone la existencia de un conjunto de datos ideal, i.e., cuando
los ejemplos son linealmente separables, se cumple que para todo (xi, yi), la función
de decisión satisface que fw,b(xi) = yi, lo cual implica también que para todo (xi, yi),
se cumple que, yi(〈w,xi〉+ b) ≥ 1.
La restricción de la Ecuación 2.2 obliga a que el punto más cercano al hiperplano
H, tenga una distancia de 1
|| || . De aqúı, se desprende que el margen entre H
w +1 (o
H−1) y H es también 1
|| || ; y que el margen entre H 2
w +1 y H−1 es || .
w||
Según lo demostrado por Vapnik, el hiperplano que produce una mejor generaliza-
ción es aquel que posee el mayor margen de los puntos más cercanos a este, por lo
cual el hiperplano óptimo se puede obtener maximizando la inversa de ||w||, o equi-
valentemente, minimizando ||w||. A partir de esto, se construye el siguiente problema
Universidad Nacional de San Agust́ın - UNSA 23
2.2. Máquinas de Vectores de Soporte
de programación cuadrática, llamado también problema primal,
1
minimizar(w) = ||w||2
w∈H,b∈R 2
sujeto a yi(〈w,xi〉+ b) ≥ 1 para todo i = 1, . . . ,m. (2.4)
Según la teoŕıa de optimización, cuando la función objetivo es convexa y las restric-
ciones son afines, tal como sucede en la Ecuación 2.4, el problema dual produce la
misma solución que el problema primal; y en algunos casos, como en el de las SVMs,
operar con este es más conveniente que hacerlo con el primal.
Para formular el problema dual, es necesario, primero, aplicar el método de Lagrange,
y aśı, obtener la función Lagrangiana,
1 ∑m
L(w, b,α) = ||w||2 − αi(yi(〈w,xi〉+ b− 1)
2
i=1
m m m
1 ∑ ∑ ∑
= ||w||2 − αiyi〈w,xi〉 − b αiyi + αi, (2.5)
2
i=1 i=1 i=1
con multiplicadores de Lagrange αi ≥ 0.
Aplicando las condiciones de Karush-Kuhn-Tucker (condiciones KKT), que estable-
cen las restricciones para que un elemento w de H sea solución del problema primal,
se procede a derivar la función Lagrangiana L(w, b,α) con respecto a las variables
primales w, b; y a igualarlas a cero, obteniendo que,
∑m
αiyi = 0, (2.6)
i=1
y ∑m
w = αiyixi. (2.7)
i=1
Sustituyendo las Ecuaciones 2.6 y 2.7 en la Ecuación 2.5 se obtiene una nueva ex-
presión que sol(amente dep)en(de de α, tal)com(o se muestr)a a(continuació)n,
m m
1 ∑ ∑ ∑m ∑m ∑m
L(α) = ( αiyixi )( αjyjxj − αiyixi αjyjxj + αi
2
i=∑1 j=∑1 ) ∑i=1 j=1 i=1
m m m
−1
= αiyixi αjyjxj + αi
2 ∑i=1 j=1 ∑ i=1
m m
= −1
αiαjyiyj〈xi,xj〉+ αi (2.8)
2
i=1 i=1
Universidad Nacional de San Agust́ın - UNSA 24
Caṕıtulo 2. Fundamento Teórico
El problema dual del primal presentado en la Ecuación 2.4 consiste en optimizar la
Ecuación 2.8 sujeta a ciertas res∑tricciones c∑omo∑se muestra a continuación,
m m m
1
maximizar αi − αiαjyiyj〈xi,xj〉
α∈Rm
∑ 2
i=1 i=1 j=1
m
sujeto a αiyi = 0
i=1
αi ≥ 0 para todo i = 1, . . . ,m. (2.9)
Aśı mismo, aplicando la condición adicional de KKT, se obtiene que,
αi(yi(〈w,xi〉+ b)− 1) = 0. (2.10)
En base a la restricción de desigualdad de la Ecuación 2.9, se tiene que αi > 0 o
αi = 0. Si αi > 0, entonces mediante la Ecuación 2.10 se puede afirmar que,
yi(〈w,xi〉+ b) = 1,
i.e., el ejemplo de entrenamiento (xi, yi) satisface la restricción del problema primal
(presentado en la Ecuación 2.4) para el caso “igual que”. Dicho de otro modo, solo
los xi del conjunto de entrenamiento cuyos αi son estrictamente mayores que cero en
el punto de silla, satisfacen las restricciones del problema primal para el caso “igual
que”. A dichos ejemplos, se les llama vectores de soporte, y para ellos se cumple que
yi(〈w,xi〉+ b) = 1.
Por último, el hiperplano de separación en cuestión se construirá como una combi-
nación lineal de todos los ejemplos de entrenamiento; no obstante, aquellos xi con
αi = 0, i.e., los ejemplos que no son vectores de soporte, no tienen mayor relevancia
en la construcción de dicho hiperplano.
2.2.2. Hiperplano de Separación de Margen Blando
Obtener un hiperplano que separe linealmente a todos los ejemplos positivos de los
negativos es poco realista, ya que en la práctica, la mayoŕıa de conjuntos de datos
presentan ejemplos ruidosos o ejemplos que han sido erróneamente etiquetados. Una
alternativa para tratar este escenario es permitir que una fracción de los ejemplos
del conjunto de entrenamiento sea clasificada incorrectamente, es decir, relajar el
grado de separabilidad de los datos.
Esto se logra asociando a cada ejemplo xi una variable ξi, llamada variable de
holgura, la cual mide la distancia (desviación) de xi al hiperplano correspondiente
a la clase de yi. Esto hace que la restricciones del problema primal definido en la
Ecuación 2.4 se convierta en,
yi(〈w,xi〉+ b) ≥ 1− ξi, ξi ≥ 0, para todo i = 1, . . . ,m. (2.11)
Universidad Nacional de San Agust́ın - UNSA 25
2.2. Máquinas de Vectores de Soporte
Las variables de holgura permiten cuantificar el númer∑o de ejemplos no separables
que se está dispuesto a aceptar y la suma de todas ellas m
i=1 ξi, corresponde al costo
asociado al número de ejemplos no separables. Para incluir las variables de holgura
en la formulación del problema, no únicamente las restricciones del problema primal
deben cambiar, sino también la función a optimizar propiamente dicha, ya que de
no ser aśı, el máximo margen se podŕıa lograr admitiendo que muchos ejemplos sean
clasificados incorrectamente. Para evitar esto, se puede incorporar una co∑nstante C
que regule el grado de influencia del costo de los ejemplos no separables, m
i=1 ξi, en
la minimización de 1 ||w||2.
2
Reformulando el problema primal de la Ecuación 2.4 a fin de obtener el hiperplano
de separación de margen blando, se define un nuevo problema de primal tal como se
muestra a continuación,
m
1 ∑
minimizar ||w||2 + C ξi
w∈H,b∈R 2
i=1
sujeto a yi(〈w,xi〉+ b) + ξi − 1 ≥ 0,
ξi ≥ 0, para todo i = 1, . . . ,m. (2.12)
Consecuentemente, su problema dual correspondiente es el siguiente,
∑m ∑m1 ∑m
maximizar αi − αiαjyiyj〈xi,xj〉
α∈Rm
∑ 2
i=1 i=1 j=1
m
sujeto a αiyi = 0
i=1
C
0 ≤ αi ≤ para todo i = 1, . . . ,m. (2.13)
m
2.2.3. Hiperplano de Separación para Casos No Lineales
En las Secciones 2.2.1 y 2.2.2 se describió la formulación de los problemas duales
para datos linealmente separables o casi linealmente separables, respectivamente.
No obstante, existen situaciones en las que encontrar el hiperplano que separa o casi
separa completamente los datos no es posible. En este contexto, la teoŕıa del apren-
dizaje estad́ıstico indica que el número de posibles separaciones lineales aumenta con
la dimensionalidad de los datos, por lo que la separación lineal es posible mapeando
los datos, mediante una función Φ : H → F , a un espacio de mayor dimensión
llamado espacio de caracteŕısticas F .
Inicialmente e incorporando la función Φ, las operaciones referentes a los productos
internos deben ser cambiadas a 〈Φ(xi),Φ(xj)〉; sin embargo, no es necesario el mapeo
expĺıcito por medio de la función Φ, pues lo que realmente se necesita es el resultado
del producto interno. Esto se logra con una función kernel K, que tenga la propiedad
de corresponder a un producto interno en un algún espacio de dimensión mayor, i.e.,
Universidad Nacional de San Agust́ın - UNSA 26
Caṕıtulo 2. Fundamento Teórico
〈Φ(xi),Φ(xj)〉 = K(xi,xj). (2.14)
El teorema de Mercer proporciona el fundamento matemático para determinar la
validez de un kernel. Aśı, dicho teorema indica que para que un kernel K sea válido
i.e., para que cumpla la Ecuación 2.14, es necesario y suficiente que la matriz de
un conjunto finito de vectores x1,x1, . . . ,xm, sea simétrica semidefinida positiva.
Algunos funciones kernel que cumplen con el Teorema de Mercer son:
Kernel lineal: K(xi,xj) = 〈xi,xj〉
Kernel polinómico de grado p: K(xi,xj) = (γ〈x p
i,xj〉+ a)
Kernel sigmoidal: K(xi,xj) = tanh(γ〈xi,xj〉+ a)
Kernel gaussiano: K(xi,xj) = exp(−γ||xi − xj||2), γ > 0
El problema dual definido en la Ecuación 2.13 se reformula en el siguiente
problema dual de optimizaci∑ón:
m ∑m m
1 ∑
maximizar αi − αiαjyiyjK(xi,xj)
α∈Rm
∑ 2
i=1 i=1 j=1
m
sujeto a αiyi = 0
i=1
0 ≤ C
αi ≤ para todo i = 1, . . . ,m. (2.15)
m
En resumen, esta última formulación permite aplicar las SVMs en casos en que
la separación lineal en el espacio original no sea posible. Para ello, se mapean los
datos a una dimensión mayor, usando una función Φ, donde dicha separación
es posible; sin embargo, el mapeo expĺıcito no es necesario y se puede prescindir
de Φ usando una función kernel K que corresponda a un producto interno en
un espacio de mayor dimensión, i.e., que cumpla el teorema de Mercer.
2.3. Optimización Secuencial Mı́nima
El método de Optimización Secuencial Mı́nima - Sequential Minimal Optimization
(SMO) propuesto por Platt [64] permite resolver el problema de programación cua-
drática de las SVMs descomponiéndolo en pequeños problemas que son resueltos
anaĺıticamente. Dichos problemas incluyen solo dos multiplicadores de Lagrange.
Por ello, en cada paso del algoritmo se escogen dos elementos del conjunto de entre-
namiento cuyos multiplicadores de Lagrange son posteriormente optimizados.
En base al trabajo de Platt, otras variaciones del algoritmo de SMO fueron propues-
tas. Una de ellas fue planteada por Bordes et al. [9], quienes sostienen que haciendo
que α′i = αiyi, y sabiendo que yiyi = 1, la Ecuación 2.15 puede ser reescrita como,
Universidad Nacional de San Agust́ın - UNSA 27
2.3. Optimización Secuencial Mı́nima
∑m 1 ∑m ∑m
maximizarL(α′) = α′iyi − α′iα
′
jK(xi,xj)
α′∈Rm
∑ 2
i=1 i=1 j=1
m
sujeto a α′i = 0
i=1
A ≤ α′i i ≤ Bi, (2.16)
donde, {
0 si yk = 1
Ak = (2.17)
−C si yk = 0,
y {
C si yk = 1
Bk = (2.18)
0 si yk = 0.
Inicialmente, el algoritmo SMO asigna el valor de cero a cada α′k y calcula el gra-
diente, gk, de L(α) con respecto al α′ de∑l k-ésimo ejemplo de entrenamiento,
gk = yk − α′iK(i, k), (2.19)
i
donde K es la función kernel definida en la Ecuación 2.14. Luego, en cada iteración
se escoge un par de ejemplos del conjunto de entrenamiento (i, j) de acuerdo al
siguiente criterio:
i = arg máx gk con α′k < Bk (2.20)
k∈S
j = arg mı́n gk con α′k > Ak, (2.21)
k∈S
Posteriormente, si el par de ejemplos de entrenamiento (i, j) cumple el criterio -τ ,
definido en base a estas tres condiciones,
αi < Bi
αj > Aj
gi − gj > τ, (2.22)
donde τ es una constante positiva pequeña, entonces se actualiza los valores de α′i, de
α′j y del gradiente de cada ejemplo de entrenamiento. Para ello, se requiere calcular
una cantidad positiva,{denotada por λ, la cual calcula como se mue}stra,
gi − gj
λ = mı́n , B − α′ , α′i i j − Aj . (2.23)
K(i, i) +K(j, j)− 2K(i, j)
Universidad Nacional de San Agust́ın - UNSA 28
Caṕıtulo 2. Fundamento Teórico
Posteriormente, se actualiza α′i y α′j,
α′i = α′i + λ (2.24)
α′ = α′j j − λ, (2.25)
y el gradiente gk de cada ejemplo de entrenamiento k,
gk = gk − λ(K(i, k)−K(j, k)), ∀k. (2.26)
2.4. Consideraciones Finales
Una SVM es un método perteneciente al aprendizaje supervisado, que requiere de
un conjunto de datos compuesto de ejemplos y sus respectivas etiquetas (+1 o -1).
En base a este conjunto, una SVM construye un hiperplano que produce la máxima
separación entre esas dos clases, y en virtud a ello, conduce al mı́nimo error de
generalización. Paralelos a dicho hiperplano, se ubican dos hiperplanos de decisión
equidistantes que pasan por uno a más ejemplos del conjunto de datos. Los ejemplos
que encuentran sobre los hiperplanos de decisión se llaman vectores de soporte.
Cuando los ejemplos de las clases no pueden ser separados por un hiperplano óptimo,
debido a que existen algunos ejemplos que caen en el lado incorrecto del hiperplano,
se puede recurrir a la separación de margen blando, la cual con la ayuda de variables
de holgura, maximiza el margen con respecto a los ejemplos correctamente clasifica-
dos y minimiza el número de ejemplos mal clasificados. Cuando los ejemplos están
agrupados de tal forma que no son linealmente separables, se usa la separación no
lineal, la cual mapea los ejemplos del espacio original a un espacio de dimensión
mayor, donde la separación lineal śı es posible. Aunque el proceso de mapeo implica
un alto costo computacional, este no se realiza. De hecho, la búsqueda del hiper-
plano óptimo se ejecuta en el espacio original, pero el mapeo se simula gracias a una
función kernel que tiene los mismos efectos que el mapeo expĺıcito.
La búsqueda del hiperplano óptimo se formula como un problema de programación
cuadrática sujeto a ciertas restricciones. El inconveniente de aplicar las SVMs se
presenta cuando el conjunto de datos es de tamaño considerable, lo que conlleva a que
la cantidad de memoria requerida para solucionar de manera estándar el problema
de programación cuadrática crezca exponencialmente. El algoritmo de Optimización
Secuencial Mı́nima es un método de descomposición que eficientemente aborda el
problema dividiéndolo en pequeños problemas cuadráticos de dos ejemplos, que se
resuelven anaĺıticamente. En este algoritmo se fundamenta la propuesta de SVM-
Online usada en esta tesis y se describe en el siguiente caṕıtulo.
Universidad Nacional de San Agust́ın - UNSA 29
Caṕıtulo 3
Revisión de la Literatura
En este caṕıtulo, se realiza la revisión de los trabajos relacionados con este proyecto
de tesis. En particular, la Sección 3.1 aborda el reconocimiento de manuscritos de
manera general; la Sección 3.2 describe los modelos de aprendizaje más usados en
el área, haciendo una distinción entre los modelos generativos y discriminativos. En
relación a estos últimos, se hace énfasis en la Máquina de Vectores de Soporte, y
las versiones online de esta, que son descritas en la Sección 3.3. Finalmente, en la
Sección 3.4 se detallan varias técnicas para obtener probabilidades a partir de salidas
discretas proporcionadas por las máquinas de vectores de soporte. Dichas técnicas
son necesarias para construcción del modelo propuesto en el Cápitulo 4.
3.1. Reconocimiento de Textos Manuscritos
El interés por el reconocimiento de escritura a mano se inició con el reconocimiento
de d́ıgitos y caracteres para la lectura automática de direcciones y códigos postales
en servicios de correo [28] [51] [60] [82] [95]; y también para el reconocimiento de
cantidades escritas en números y letras en documentos bancarios [32] [39] [48] [61]
[89], como cheques. En estas áreas se ha logrado desarrollar aplicaciones comerciales
con altas tasas de reconocimiento; sin embargo en escenarios libres de restricciones
las tasas obtenidas no son todav́ıa aceptables.
Las aplicaciones de un número ilimitado o extenso de palabras a ser reconocidas son
ejemplos de escenarios libres de restricciones. En tales casos es común que se aplique
el Reconocimiento Óptico de Caracteres - Optical Character Recognition (OCR) –
que consiste en reconocer caracteres individuales – y luego identificar palabras en
base a la concatenación de los caracteres reconocidos. Ese enfoque también implica
identificar los puntos en los cuales dos caracteres se unen; para lo cual generalmente
se analiza las ligaduras y concavidades de los trazos de la imagen [27] [30] [56].
Otro escenario en el cual todav́ıa no se ha obtenido tasas de reconocimiento acepta-
bles, es el de los documentos históricos, pues en ellos hay que lidiar con problemas
30
Caṕıtulo 3. Revisión de la Literatura
como la degradación del papel, el desvanecimiento de la tinta, el estilo de la escritura
de época, etc. Manmatha et.al [42] [53] [68] [69] [70] [71] [72] analizaron estos proble-
mas y propusieron un nuevo enfoque cuyo objetivo no era transcribir el documento
completamente, sino más bien crear un ı́ndice de las palabras más representativas
del mismo; y aśı posibilitar búsquedas basadas en el contenido. A este enfoque, le
llamaremos, enfoque de indexación y búsqueda.
Manmatha et.al, en el enfoque de indexación y búsqueda, supusieron que un ma-
nuscrito es una colección de palabras; por lo que primero, segmentaron las páginas
en imágenes de palabras, que luego, agruparon usando técnicas de clustering ; pos-
teriormente, etiquetaron, asignando manualmente una palabra a los clusters más
representativos –dicha representatividad se basó en la frecuencia de las palabras
en el texto–; y finalmente, crearon un ı́ndice basado en las palabras asignadas. Sin
embargo, gran parte del éxito de dicho enfoque radica en segmentar las imágenes
palabras adecuadamente, lo que en la práctica no siempre es posible. Además, la
forma de determinar las palabras representativas puede provocar que palabras im-
portantes en un contexto histórico –como nombres propios– no sean consideradas
relevantes sólo por el hecho de no tener una frecuencia mayor a la esperada.
A pesar de las limitaciones del enfoque de indexación y búsqueda, este dio origen a
una nueva ĺınea de investigación llamada Búsqueda de Texto en Imágenes - Word
Spotting. De hecho, Manmatha et al. [52] acuñaron el término y lo usaron en el
sentido explicado anteriormente, para documentos históricos. Posteriormente, Word
Spotting fue redefinido en la práctica como el proceso que identifica todas las ocu-
rrencias de una palabra dada por un usuario, en una colección de imágenes. Para
esto, generalmente un sistema de word spotting recibe como consulta la imagen de
una palabra; y luego busca en la colección de imágenes, regiones de texto que tienen
una apariencia similar a la imagen consultada.
Shah y Suen [84] clasificaron las técnicas de word spotting en base a cómo se de-
termina la similitud de dos imágenes. Por una parte, existen técnicas que realizan
un matching entre los ṕıxeles de dos imágenes [46] [47] y entre las caracteŕısticas
extráıdas de dos imágenes [42] [68] [69]. Por otra parte, se encuentran las técni-
cas que usan modelos de aprendizaje como redes neuronales y modelos ocultos de
Markov [17] [18].
De lo anterior se puede ver que word spotting no requiere de una transcripción com-
pleta del documento; no obstante, información relevante se pierde por no contar con
transcripciones, sobre todo en el contexto de documentos antiguos. Debido a esto,
ha surgido un nuevo enfoque de reconocimiento que no es completamente automá-
tico, sino más bien interactivo, y permite a un experto retroalimentar el sistema
sucesivamente en respuesta a una salida que tal sistema previamente le proporcionó.
Esto produce que su desempeño mejore a cada paso de interacción. Vidal et al. [91]
llama a este enfoque Reconocimiento de Patrones Interactivo.
En este sentido, las primeras investigaciones sobre transcripción de documentos his-
tóricos usando el aprendizaje interactivo, fueron realizadas por Toselli et al. [90] y
Universidad Nacional de San Agust́ın - UNSA 31
3.2. Modelos de Aprendizaje usados en el Reconocimiento de Manuscritos
Romero-Gómez et al. [77] [78] [79] [80] [81]. Ellos dividieron el proceso de transcrip-
ción en dos etapas, a saber, reconocimiento y posedición. En la primera etapa, un
sistema probabiĺıstico basado en el modelo oculto de Markov y n-gramas realiza el
proceso de reconocimiento de una manera completamente automática; mientras que
la segunda, un usuario corrige la transcripción proporcionada en la etapa anterior y
el sistema produce, en ĺınea, un nueva salida en base a la retroalimentación del ex-
perto. Espećıficamente, el experto mientras lee, corrige en cada paso de interacción
la transcripción dada por el sistema (e.g., una letra de una palabra), y este asume
que todo lo que se encuentra antes del punto de edición es correcto y produce, en
respuesta, una nueva transcripción a partir de dicho punto.
Aunque se ha conseguido importantes avances en la transcripción de documentos his-
tóricos con el aprendizaje interactivo, existen ciertos aspectos que todav́ıa no se han
considerado y que podŕıan mejorar el desempeño de los sistemas de reconocimiento.
Uno de esos aspectos es el aprendizaje online; por medio del cual, los modelos son
capaces de aprender continuamente, i.e., pueden ajustar sus parámetros cada vez
aparecen nuevos ejemplos de entrenamiento.
Abordar el aprendizaje desde la perspectiva online es conveniente en algunos esce-
narios como por ejemplo, cuando las instancias de entrenamiento cambian con el
tiempo o cuando conseguir dichas instancias es costoso; este último escenario se da
en particular en los documentos históricos. Además, en este contexto existe otra ra-
zón que motiva la incorporación del aprendizaje online; esta es que la aparición de
nuevos ejemplos de entrenamiento está garantizada gracias al aprendizaje interacti-
vo, ya que después de cada paso de interacción con el usuario se producen nuevos
ejemplos que están completamente validados por el usuario.
En este sentido, el aprendizaje online es una ĺınea que todav́ıa no ha sido explorada
en manuscritos antiguos y constituye la principal contribución de esta tesis.
3.2. Modelos de Aprendizaje usados en el Reco-
nocimiento de Manuscritos
En esta sección se describirán los modelos de aprendizaje más usados en el reco-
nocimiento de escritura, ya sea en un contexto de documentos históricos o de do-
cumentos actuales. Dicha descripción está divida en modelos discriminativos y en
modelos generativos, donde los modelos discriminativos buscan encontrar una fron-
tera de decisión que separe las clases; y los modelos generativos intentan dar una
explicación de la forma en que los datos fueron generados, i.e., tratan de descubrir
la distribución de las clases.
Universidad Nacional de San Agust́ın - UNSA 32
Caṕıtulo 3. Revisión de la Literatura
3.2.1. Modelos Generativos: Modelo Oculto de Markov
El modelo generativo más usado en el reconocimiento de escritura es el Modelo
Oculto de Markov - Hidden Markov Model (HMM). Este es un modelo probabi-
ĺıstico conformado por dos procesos estocásticos de Markov; el primero es un pro-
ceso discreto, no observable, cuyas variables aleatorias representan estados Q =
{q1, q2, . . . , qN} y tiene asociado una distribución de probabilidades de transición de
estados A = {aij = Pr(qt+1
j )|qti}; el segundo proceso puede ser continuo o discreto,
y sus variables aleatorias representan observaciones V = {v1, v2, . . . , vM}. Ambos
procesos están relacionados pues la distribución de probabilidad de las observacio-
nes, B = {bj(k) = Pr(vtk)|qti} indica que la probabilidad de que una determinada
observación, vk, se emita depende del estado qi en el que el modelo se encuentra en
un determinado tiempo t.
Por otra parte, el HMM ha sido extensamente usado en el reconocimiento del habla,
y posteriormente, debido a la similitud entre las aplicaciones, ha sido usado en el
reconocimiento de la escritura. Algunos trabajos están orientados a word spotting,
reconocimiento de firmas, identificación de identidad, reconocimiento de cheques [2]
[15] [16] [34] [37] [67] [76] [92], etc.
En este contexto, algunas variantes del HMM han sido propuestas a fin de mejorar
las tasas de reconocimiento; e.g., Edward et al. [14] propuso el Modelo Oculto de
Markov Generalizado - Generalized Hidden Markov Model (GHMM) el cual difiere
del HMM en la manera en que representa las transiciones. En el HMM tradicional,
un estado oculto emite una sola observación, mientras que en un GHMM un estado
oculto puede emitir un conjunto de observaciones. Según Edwards et al. la ventaja
de este modelo estriba en la capacidad de unificar varias columnas de una imagen y
aśı reconocer subimágenes de bloques de texto de tamaño variable.
Asimismo, Kuo et al. [38] y Qi et al. [66] presentaron otra variación del HMM, lla-
mada pseudo 2D-HMM, para reconocer caracteres chinos. A diferencia del HMM
clásico, este método permite analizar una imagen de texto no sólo horizontalmente
sino también verticalmente lo que hace que el proceso de reconocimiento sea invaria-
ble al tamaño e inclinación de los caracteres y altamente tolerante a las deformación
de los mismos.
3.2.2. Modelos Discriminativos
A pesar de que el HMM ha sido el más utilizado en el contexto de reconocimiento de
escritura, existen otras propuestas que utilizan modelos discriminativos. Los modelos
discriminativos clasifican las observaciones mediante fronteras de decisión, las cuales
son creadas modelando directamente la probabilidad condicional de las etiquetas o
clases, dadas las observaciones. En el área de reconocimiento de escritura, los modelos
discriminativos que se han usado son redes neuronales profundas y máquinas de
vectores de soporte.
Universidad Nacional de San Agust́ın - UNSA 33
3.2. Modelos de Aprendizaje usados en el Reconocimiento de Manuscritos
Memoria a Corto y Largo Plazo Bidireccional
La Memoria Bidireccional a Corto y Largo Plazo - Bidirectional Large Short Term
Memory (BLSTM) es una red neuronal recurrente adecuada para el reconocimiento
de patrones secuenciales que vaŕıan con el tiempo. La red BLSTM posee 4 capas:
una de entrada, una de salida y dos capas ocultas. La primera capa oculta realiza
el proceso de activación hacia adelante, i.e., de la capa de entrada hacia la capa de
salida, y la segunda de la capa de salida hacia la entrada.
En vez de nodos, esta red utiliza bloques de memoria conformados por unidades
internas, cuya activación es controlada por 3 puertas que permiten guardar y acceder
a la información en largos periodos de tiempo. Cuando la puerta de entrada del
bloque de memoria se encuentra cerrada, la nueva información que llega a la red
no afecta el cálculo de la activación de este bloque. Similarmente, la activación del
bloque solo llega al resto de la red si la puerta de salida está abierta. La activación,
siempre que la puerta de olvido lo permita, es utilizada para realimentar el bloque
a fin de que pueda recordar información pasada.
Las capas ocultas están conectadas con la capa de salida, que a su vez se conecta
a un Clasificador Temporal Conexionista [22], el cual tiene por objetivo transfor-
mar las salidas de la red en una distribución de probabilidad condicional sobre una
secuencia de etiquetas, y de esta manera, encontrar la secuencia de etiquetas más
probable dada una entrada determinada. En el contexto de reconocimiento de es-
critura dichas etiquetas pueden ser los caracteres del alfabeto inglés. Por otro lado,
la red es entrenada usando el mismo fundamento del algoritmo de retropropagación
para la corrección de errores.
La red BLSTM fue propuesta por Graves et al. [23]; inicialmente, fue utilizada para el
reconocimiento de habla [25], y posteriormente, fue adaptada para el reconocimiento
de escritura [24]. En la misma ĺınea, Frinken et al. [19] presentaron un ensamble de
BLSTMs entrenados con diferentes parámetros, el que superó el desempeño de la
BLSTM individual, Luego, Frinken et al. [20] la utilizaron en documentos históricos
y Jain et al. [31] en documentos escritos en Hindi.
Red Neuronal Convolucional
La Red Neuronal Convolucional - Convolutional Neural Network (CNN) fue pro-
puesta por LeCun [44] para el reconocimiento de d́ıgitos y caracteres. Luego Bengio
et al. [6] [43] la emplearon para el reconocimiento online de palabras e incorporaron
también un modelo oculto de Markov cuya función era asignar puntajes (probabili-
dades) a la salida proporcionada por la CNN.
La CNN tiene una arquitectura y entrenamiento similar al del Perceptron Multicapa,
pero a diferencia de este, la CNN incorpora información de formas bidimensionales
(e.g. imágenes) usando conexiones locales y un mecanismo de parámetros compar-
tidos, i.e., pesos compartidos. Una caracteŕıstica importante de esta red es que el
Universidad Nacional de San Agust́ın - UNSA 34
Caṕıtulo 3. Revisión de la Literatura
proceso de extracción de caracteŕısticas es realizado internamente, y por lo tanto, es
innecesario utilizar métodos para la extracción de caracteŕısticas.
La CNN está compuesta de 4 capas; la primera está constituida por la imagen
misma; la siguiente está compuesta de 6 mapas de caracteŕısticas, donde cada mapa
está organizado en la forma de una malla de 13 × 13 neuronas. Durante la fase de
entrenamiento, dicho mapa es convolucionado con un kernel de 5 ×5. El número de
pesos depende del tamaño del kernel, del bias y del número de mapas; aśı el número
de pesos en la primera capa es (5 × 5+1(bias)) × 6. Debido a que todas las neuronas
de un mapa comparten los mismos pesos se reduce significativamente la complejidad
de la red. La tercera capa está completamente conectada a la capa anterior y tiene
50 mapas de caracteŕısticas de 5 ×5 neuronas. Cada mapa es mapeado a una única
neurona en la siguiente capa, i.e., la capa de salida. Los pesos son obtenidos usando
un algoritmo de retropropagación modificado que minimiza el error de un conjunto
de patrones de entrada.
Máquinas de Vectores de Soporte
Otro clasificador que pertenece al grupo de modelos discriminativos y ha sido usado
en el reconocimiento de escritura, es la Máquina de Vectores de Soporte - Support
Vector Machines (SVM) [12]. El aprendizaje de una SVM consiste en buscar un
hiperplano que separe óptimamente los ejemplos de dos clases. Dicho hiperplano
es aquel que tiene la distancia máxima a los ejemplos más cercanos a dos clases
distintas, i.e., a los vectores de soporte. Formalmente, sea H un espacio con pro-
ducto interno definido y un conjunto de elementos x1,x2, . . . ,xm ∈ H, donde cada
elemento xi tiene asociada una etiqueta o clase yi con valores +1 ó -1. Un elemen-
to y su correspondiente clase forman un par denotado por (xi, yi). La búsqueda del
hiperplano se plantea como un problema de p∑rogramación cuadrática definido como,
m
1
minimizar = ||w||+ C ξi (3.1)
w∈H,ξ∈Rm 2
i=1
sujeto a yi(〈Φ(w),Φ(xi)〉+ b)) ≥ 1− ξi,
ξi ≥ 0, i = 1, . . . ,m,
donde C es una constante positiva dada por el usuario, ξ’s son variables de holgura
que permiten un margen de error de los patrones con respecto al hiperplano, y Φ es
una función kernel que mapea un ejemplo a un espacio de dimensión mayor donde
la separación lineal es factible. Una revisión teórica más profunda de las SVMs fue
proporcionada en la Sección 2.2.
En el contexto de reconocimiento de escritura, las SVMs han sido utilizadas reciente-
mente, y por lo general, en combinación con otras técnicas. Por ejemplo, Bahlmann
et al. [4] presentaron un método en cual se acopla una SVM con dynamic time war-
ping. Ahmad et al. [1] propusieron un modelo h́ıbrido donde una SVM es entrenada
y sus respuesta son usadas posteriormente por un HMM. Otros modelos h́ıbridos que
incluyen una SVM se presentan en las investigaciones de Niu et al. [57] y Kamble
Universidad Nacional de San Agust́ın - UNSA 35
3.3. Máquinas de Vectores de Soporte Online
et al. [62]. Además, Simistira et al. [85] usaron una SVM para el reconocimiento de
fórmulas matemáticas, Guerbai et al. [26] la usaron para la identificación de per-
sonas utilizando firmas; Khayyat et al. [35] y Almazán et al. [3] la emplearon en
word spotting ; y finalmente, Surinta et al. [87] y Das et al. [13] la usaron para el
reconocimiento de caracteres de diferentes idiomas.
Una diferencia bastante notable de las SVMs en relación a otros modelos de apren-
dizaje, es su principio inductivo, el cual minimiza el riesgo estructural y emplea una
función kernel, lo que brinda una gran capacidad de generalización, incluso cuando
el conjunto de entrenamiento es pequeño, no siendo aśı en el caso de los HMMs, los
que necesitan una gran cantidad de datos para lograr generalizar adecuadamente.
Otro aspecto importante es que su capacidad de generalización como su entrena-
miento no dependen del número de caracteŕısticas, lo que permite un buen compor-
tamiento en problemas de alta dimensionalidad. Además como se mencionó ante-
riormente, las SVMs se basan en el principio de minimización del riesgo estructural
que ha mostrado tener un mejor desempeño que el obtenido al minimizar el riesgo
emṕırico; este último es el principio que emplean las redes neuronales.
Las caracteŕısticas mencionadas previamente motivaron el uso las SVMs en esta
tesis. Queda ahora realizar una revisión de los trabajos relacionados a aprendizaje
online usando SVMs. Dicha revisión será abordada en la siguiente sección.
3.3. Máquinas de Vectores de Soporte Online
Los modelos clásicos de aprendizaje, i.e., que usan aprendizaje en lote, necesitan ser
reajustados cada vez que aparecen nuevos ejemplos de entrenamiento, para lo cual
es necesario reentrenar dichos modelos usando tanto las antiguas como las nuevas
instancias de entrenamiento. Esto hace que los métodos clásicos no sean adecuados
para sistemas en tiempo real, los cuales por principio, deben dar respuestas rápidas,
y que por lo tanto, requieren de un tipo de aprendizaje que no solo permita que los
parámetros de un modelo se reajusten a medida que llegue nueva información, sino
también que lo hagan sin necesidad de volver a aprender lo que anteriormente ya
fue aprendido. A este tipo de aprendizaje se le llama Aprendizaje Online [96].
Por otra parte y como fue mencionado anteriormente, las Máquinas de Vectores
de Soporte poseen caracteŕısticas teóricas interesantes que motivan su uso; y ade-
más, se ha demostrado que al ser aplicadas a problemas reales como clasificación de
texto, regresión, reconocimiento de patrones, predicción de series temporales, bio-
informática, procesamiento de imágenes, etc. producen una buena generalización.
Tales razones han motivado a que en este proyecto de tesis se opte por utilizar las
SVMs.
Sin embargo, no existen muchos trabajos relacionados con máquinas de vectores de
soporte basadas en aprendizaje Online. Varias de las propuestas descritas a conti-
Universidad Nacional de San Agust́ın - UNSA 36
Caṕıtulo 3. Revisión de la Literatura
nuación, han sido planteadas teóricamente y probadas en conjuntos de datos simples;
y pocas en problemas reales, como es de interés en este proyecto de tesis.
Uno de las primeras técnicas que intentó plasmar la idea del aprendizaje online en
las SVMs fue la propuesta por Syed et al. [88]. Esta técnica realiza el entrenamiento
de una SVM de la manera usual conservando los vectores de soporte obtenidos en
este primer entrenamiento; y posteriormente cuando aparecen nuevas instancias,
el modelo es reentrenado usando las nuevas instancias y los vectores de soporte
previamente obtenidos.
Note que la propuesta de Syed et al. no es del todo online pues su modelo necesita
reentrenarse cada vez que se agrega un nuevo ejemplo. Otra alternativa alude al uso
del algoritmo del Gradiente Descendiente Estocástico (GDE) que tiene la propiedad
de aprender observando solo un vez cada ejemplo de entrenamiento. En este sentido
Souza et al. [86] usó la idea del GDE en problemas de regresión; y Kivibene et
al. [36] incorporaron el GDE en varios métodos de aprendizaje basado en kernels,
entre ellos las SVMs, pudiéndose emplear tanto en problemas de clasificación como
de regresión.
Por otro lado, Cauwenberghs y Poggio [11] afirmaron que reentrenar un modelo to-
mando en cuenta solo los vectores de soporte y las nuevas instancias de entrenamien-
to produce resultados aproximados y no exactos. Según los autores, este problema
se puede superar haciendo que las condiciones de Karush-Kuhn-Tucker (KKT) de
todos los ejemplos previamente vistos se mantengan en equilibrio. Otros autores se
basaron también en esta idea, e.g., Martin [55] y Ma et al. [50] extendieron el trabajo
de Cauwenberghs y Poggio [11] a fin de que sea aplicable en problemas de regresión;
y Laskov et al. [40] lo modificó a un nivel de implementación, optimizando el alma-
cenamiento y las operaciones numéricas, lo que finalmente disminuyó el tiempo de
entrenamiento.
Otros trabajos se inspiraron en las caracteŕısticas geométricas de las SVMs, y ana-
lizaron la envolvente convexa de los datos. E.g., Wang et al. [93] propusieron un
método de dos etapas: en la primera se requiere encontrar los vértices del esqueleto
de la envolvente convexa de la clases positiva y negativa, usando todos los ejemplos
de entrenamiento disponibles; mientras que en la segunda etapa, el modelo se ac-
tualiza usando los vértices del esqueleton y los nuevos ejemplos de entrenamiento.
Revathi et al. [74] aplicaron este método en la detección de peatones. Bajo el mismo
raciocinio, Bordes y Bottou [8], presentaron un método al que llamaron Huller que
posee la misma capacidad de convergencia que el SVM tradicional. No obstante, este
trabajo solo fue orientado a la SVM de margen duro.
La nueva propuesta de Bordes et al. [9] recoge algunas ideas presentadas en su
trabajo previo [8], pero a diferencia de este, utiliza la formulación del margen blando
para casos no lineales, y se basa en el algoritmo de Optimización Secuencial Mı́nima
propuesto por Platt [64] y descrito en la Sección 2.3. Los experimentos realizados por
Bordes et al. indican que alcanza tasas competitivas con respecto al SVM tradicional
de margen blando. Además una ventaja de este método en relación a otros métodos
Universidad Nacional de San Agust́ın - UNSA 37
3.4. Estimación de Probabilidad para Clasificación Multiclase
online es que entrena considerablemente más rápido e incluye la idea del aprendizaje
activo. Debido a estas caracteŕısticas, esta técnica es usada en este proyecto de tesis.
3.4. Estimación de Probabilidad para Clasifica-
ción Multiclase
El problema de programación cuadrática de las SVM ha sido formulado para proble-
mas con clases binarias. A fin de aplicar las SVMs en problemas con n clases, se han
propuesto varias estrategias, siendo las más usadas, “uno contra uno” y “uno contra
todos” [7]. En ambos casos, las respuestas que proporcionan dichas estrategias son
discretas; no obstante, como se explicó en la Sección 1.4, la propuesta de esta tesis
requiere probabilidades en vez de salidas discretas. A continuación, se realiza una
descripción de los métodos existentes en la literatura para convertir salidas discretas
en probabilidades.
Considere una estrategia de multiclasificación “uno contra uno” con K clases y
K(K−1) clasificadores. Sea (x, y), un vector donde x es una observación o ejemplo,
2
y es la clase asociada a dicho ejemplo dentro de un grupo de K clases. Sea rij, la
aproximación de la estimación de la probabilidad por pares de las clases i y j de µij
definida como,
µij = P (y = i|y = i ∨ j,x), (3.2)
para todo i, j = 1 . . . K. El objetivo es calcular la probabilidad de una determinada
clase i dada la observación x, i.e., pi = P (y = i|x). Existen diferentes métodos que
permiten calcular pi tal como se muestra a continuación.
Refrengier y Vallet [73] parten de la suposición de que
rij ≈ µij pi
= , (3.3)
rji µji pj
donde
pi
µij = . (3.4)
pi + pj
De los (K(K − 1)/2)rij’s exi∑stentes, se escogen (K − 1) r′ij al azar; posteriormente,
usando la condición de que K
i=1 pi = 1, se forma un sistema lineal de ecuaciones
del cual se puede obtener pi. Una deficiencia de este método es que los resultados
dependen del subconjunto de rij’s escogido.
Para evitar el problema de la dependencia, Price et al. [65] utilizan todos los rij’s,
i.e., K(K−1) rij’s; y estiman las probabilidades, pi, como se muestra,
2
1
pi = ∑ (3.5)
K 1
j,j 6=i − (K − 2)
rij
Universidad Nacional de San Agust́ın - UNSA 38
Caṕıtulo 3. Revisión de la Literatura
donde rij se calcula por medio de,
P (y = i|x)
rij ≈ µij = (3.6)
P (y = i ∨ j|x)
Por otra parte, Hastie y Tibshirani [29] estiman pi, minimizando la distancia Kullback-
Leibler entre r y µ, definida como,
∑K rij
D(r||µ) = nijrij log , (3.7)
µij
i,j:j=6 i
donde nij es el número de ejemplos de entrenamiento de las clases i y j; rij = 1−rji;
y µij se calcula como en la Ecuación 3.4.
Luego, se calcula la derivada parcial de D(r||µ) con respecto a pi y se la iguala a
cero, obteniendo que, ∑K ∑K
nijrij = nijµij, (3.8)
∑ j:j 6=i j:j 6=i
con K
i=1 pi = 1 y p > 1 para i = 1, . . . , K.
Por otra parte, Wu et al. [94] proponen un método similar al de Hastie y Tibshirani
[29] pero más simple en implementación y análisis. Dicho método se basa en la
resolución del siguiente problema de programación cuadrática con restricciones,
∑K ∑K
minimizar (r 2
jipi − rijpj)
p
∑i=1 j:j 6=i
K
sujeto a pi = 1, pi ≥ 0 para todo i = 1, . . . , K. (3.9)
i=1
Además, Wu et al. demostraron que las restricciones del problema 3.9 son redundan-
tes; y que la Ecuación 3.9 puede ser reescrita, por conveniencia, de forma matricial
como se muestra,
1
minimizar pTQp, (3.10)
p 2
donde {∑
2
Q = l:l 6=i rli si i = j
ij (3.11)
−rjirij si i =6 j.
También, Wu et al. probaron que gracias a las condiciones de optimalidad de La-
grange, el problema de la Ecuación 3.10 puede ser representado mediante un sistema
lineal de ecuaciones, con solució[n única]p[, s]iemp[re]y cuando se cumpla que,
Q e p 0
T = , (3.12)
e 0 λ 1
Universidad Nacional de San Agust́ın - UNSA 39
3.5. Consideraciones Finales
donde λ es el multiplicador de Lagrange de la restricción de igualdad de la Ecua-
ción 3.9, e es un vector K-dimensional cuyos elementos son todos unos, 0 es un
vector K-dimensional de ceros.
La Ecuación 3.12 se puede resolver a través de la Factorización de Cholesky, la cual
permite resolver sistemas de ecuaciones de la forma, Ax = b, donde A = [aij] es
una matriz n × n simétrica positiva definida y aij ∈ R. Dicha matriz puede ser
descompuesta en su matriz triangular inferior L y su respectiva transpuesta, LT ,
i.e., A = LLT. Wu et al. demostraron que a pesar de que Q es semi positiva definida
se puede utilizar la factorización de Cholensky, ya que Q es positiva definida bajo
condiciones generales. Por ende, se puede obtener el valor de p:
p = −λQ−1e, (3.13)
− 1
λ =
eTQ−
(3.14)
1e
3.5. Consideraciones Finales
Las técnicas utilizadas en el reconocimiento de texto se pueden dividir en métodos
generativos y discriminativos. El método generativo que ha sido ampliamente usado
es el modelo oculto de Markov; no obstante, su entrenamiento es lento, y para su ade-
cuado funcionamiento requiere de un conjunto de datos extenso, que en la mayoŕıa
de las veces toma tiempo crear, sobre todo cuando se refiere a manuscritos históricos.
Menos usados han sido los modelos discriminativos. Uno de los primeros métodos
discriminativos usados fue la CNN y produjo buenas tasas en el reconocimiento de
d́ıgitos, pero esta fue superada por la SVM [41].
Finalmente, es importante aclarar que según la revisión realizada, el tema de apren-
dizaje online no ha sido explorado en el contexto de la transcripción de palabras
contenidas en manuscritos históricos.
Universidad Nacional de San Agust́ın - UNSA 40
Caṕıtulo 4
Reconocimiento de Palabras
Tal como sucede en la mayoŕıa de los sistemas de reconocimiento de patrones, el
proceso de reconocimiento propuesto en esta tesis está compuesto de tareas agru-
padas en tres grandes etapas: Preprocesamiento, Extracción de Caracteŕısticas y
Aprendizaje-Reconocimiento. En las dos primeras, se han empleado técnicas ya usa-
das en el área de reconocimiento de texto; y se han ajustado los parámetros de dichas
técnicas en base a la experimentación. Las contribuciones de esta tesis radican en la
tercera etapa, donde se propone un modelo de aprendizaje-reconocimiento basado
en aprendizaje online, adaptando, para ello, el modelo de Bordes et al. [9], y exten-
diéndolo a fin de que proporcione salidas probabiĺısticas. Además, evitando recurrir
a la segmentación de caracteres durante la fase de reconocimiento, se propone repre-
sentar una imagen de una palabra como un grafo direccionado. El reconocimiento
se realiza en el grafo de la imagen, el cual usa el modelo SVM-Online previamente
entrenado.
La descripción detallada de cada una de estas etapas es presentada en las secciones
subsiguientes de este caṕıtulo; no obstante, con el objetivo de dar una visión general
de la propuesta, dichas etapas son ilustradas en la Figura 4.1, y descritas brevemente
a continuación.
La Etapa 1 consiste en preparar las imágenes y segmentar las páginas en ĺıneas
de texto, de tal manera que dichas imágenes puedan ser usadas directamen-
te en etapas posteriores. Para este objetivo, se ejecutan tareas que incluyen:
1)mejorar la calidad de las imágenes mediante el aumento del contraste; 2) co-
rregir la inclinación de las páginas que aparece como resultado del proceso de
escaneo; 3) segmentar las páginas en imágenes de ĺıneas de texto; 4) corregir la
inclinación propia de la escritura a mano; 5) normalizar las imágenes a fin de
que tengan la misma altura; y finalmente 6) segmentar las ĺıneas de texto en
imágenes de palabras. Vale la pena aclarar, que para construir el conjunto de
entrenamiento, las imágenes de palabras deben ser segmentadas en los carac-
teres que las componen, sin embargo, durante el reconocimiento de la imagen
la segmentación no es necesaria.
41
Imágenes de APRENDIZAJE
Conjunto de 
entrenamiento caracteres Vectores de características
Preprocesador Extractor de Clasificador
de Datos Características SVM - Online
Diccionario
Modelo 
entrenado
Modelo del 
Lenguaje
RECONOCIMIENTO
Reconocedor 
Subimágenes de Basado en Grafos
imágenes de palabras
Preprocesador 
de Datos
Extractor de 
Características
Conjunto de Palabras 
prueba reconocidas
Vectores de 
características
Imágenes 
de palabras
Figura 4.1: Esquema de la propuesta de tesis en mayor detalle.
La Etapa 2 corresponde a la creación de vectores de caracteŕısticas, los cuales
son obtenidos en base al cálculo de la magnitud y orientación del gradiente
de cada ṕıxel de una imagen. La magnitud y orientación del gradiente de los
ṕıxeles de una determinada zona de la imagen, sirven para formar un vector
de acumulación; el cual a su vez, conforma el vector de caracteŕısticas; de
hecho, este último es la concatenación de los vectores de acumulación de todas
las zonas de la imagen. Estas últimas se obtienen de la división vertical y
horizontal de la imagen en cuestión. A esta etapa se le conoce como extracción
de caracteŕısticas.
La Etapa 3 consiste en el aprendizaje y el reconocimiento propiamente dicho.
Para el proceso de aprendizaje se utiliza una SVM online entrenada con los
vectores de caracteŕısticas de las imágenes de los caracteres, obtenidos de la
segmentación manual de las imágenes de palabras. No obstante, como se men-
cionó anteriormente, durante el proceso de reconocimiento propiamente dicho
Universidad Nacional de San Agust́ın - UNSA 42
Caṕıtulo 4. Reconocimiento de Palabras
no se requiere que las imágenes de palabras estén divididas en sus caracte-
res componentes. Esto es posible ya que se diseñó un modelo en el que las
imágenes de palabras son representadas por un grafo dirigido. En dicho grafo
se lleva a cabo el reconocimiento usando una modificación del algoritmo de
Dijkstra, que a su vez, utiliza una SVM-Online previamente entrenada. Du-
rante la construcción del grafo se añaden nodos y aristas, y se asocia a cada
arista la siguiente información: 1) una subimagen (constituida de un número
determinado de columnas consecutivas de la imagen), 2) una etiqueta (clase
de carácter, e.g., ‘a’, ‘m’), y 3) un costo (que es inversamente proporcional a la
probabilidad de su clase). Una vez que el grafo está construido se puede efec-
tuar el reconocimiento, para lo cual, se encuentra el camino de menor costo, y
luego, de sus aristas se toman sus etiquetas asociadas, las que al concatenarse
producen la secuencia óptima de caracteres, i.e., la transcripción de la pala-
bra. Al reconocimiento basado en este enfoque, se le llamará Reconocimiento
Basado en Grafos.
4.1. Preprocesamiento
En esta sección, se expone el procedimiento para mejorar la calidad de las imáge-
nes, y se describen otras operaciones y técnicas de procesamiento de imágenes, que
preparan y acondicionan las imágenes de los documentos a fin que estén en el mejor
estado posible para ser usadas en la etapa de extracción de caracteŕısticas.
El producto final de la utilización de estas técnicas es un conjunto de imágenes de pa-
labras. Para realizar el entrenamiento de la SVM-Online se requiere adicionalmente,
segmentar manualmente tales imágenes en caracteres.
4.1.1. Aumento del Contraste
El primer paso del preprocesamiento es destacar las áreas de texto de la imagen
del fondo de la misma, de tal forma que estas se hagan más legibles. Esto se logra
aumentando el contraste de la imagen. Generalmente, el histograma de una imagen
con un bajo contraste presenta una gran densidad en un rango limitado; mientras
que en una imagen con un alto contraste la densidad se expande a lo largo de todo el
histograma. Una forma de incrementar el contraste se logra mediante la aplicación
de una transformación lineal, la cual asigna a cada pixel (x, y) de la imagen una
nueva intensidad p′(x, y).
Los resultados del aumento de contraste se ilustran en las Figuras 4.2(a) y 4.2(b),
que presentan una imagen antes, y otra, después de incrementar el contraste, res-
pectivamente.
Universidad Nacional de San Agust́ın - UNSA 43
4.1. Preprocesamiento
((a)) ((b))
Figura 4.2: a)Imagen original. b) Imagen después de aumentar el contraste. Este
proceso hace que las áreas de texto resalten del fondo de la imagen.
4.1.2. Corrección de la Inclinación de las Páginas
Usualmente, al colocar las páginas de los documentos f́ısicos en los dispositivos de
digitalización se produce una cierta inclinación en la orientación de las páginas, que
degrada la calidad de la imagen; y que por lo tanto, debe ser corregida. Existe una
heuŕıstica que corrige inclinaciones leves, la cual consiste en simular rotaciones usan-
do los ángulos en el intervalo [−π = −18;π = 18], y en escoger, posteriormente, un
ángulo α que produzca los valles más bajos y las mesetas más extensas [5]. Dicho
ángulo endereza las ĺıneas con respecto al eje x, pues siempre que la superposición
entre ĺıneas sea mı́nima, la varianza del perfil de proyección será mayor y presen-
tará valles más profundos. En base a α, se efectúa una transformación de rotación,
calculando, finalmente, una nueva posición (x′, y′) para cada pixel (x, y),
x′ = x cosα + y sinα (4.1)
y′ = −x sinα + y cosα (4.2)
La Figura 4.3 muestra una imagen después de corregir la inclinación de la página.
Universidad Nacional de San Agust́ın - UNSA 44
Caṕıtulo 4. Reconocimiento de Palabras
((a)) ((b))
Figura 4.3: a)Imagen antes y b) después de aplicar el proceso de corrección de la
inclinación de una página generalmente producida durante el proceso de
digitalización del documento.
4.1.3. Segmentación de las Páginas en Ĺıneas
Una vez que la inclinación de las páginas ha sido corregida, es necesario dividirla
en las ĺıneas que la conforman. Un método para conseguir esta división se basa
en el cálculo de la proyección horizontal de la página; dicha proyección puede ser
representada por un vector, P = [p1, p2, . . . , pH ], donde H es la altura de la imagen,
y py es la y-ésima componente del vector, que se calcula sumando las intensidades a
lo largo del ancho, W , de la imagen, tal como se muestra,
∑W
py = p(x, y) (4.3)
x=1
Luego, se identifican los espacios entre las ĺıneas de texto, llamados puntos de corte,
los cuales corresponden a los centros de las mesetas de la proyección, y posterior-
mente, se corta la imagen en base a dichos puntos.
Universidad Nacional de San Agust́ın - UNSA 45
4.1. Preprocesamiento
Figura 4.4: Segmentación de la imagen de una página en imágenes de ĺıneas de
texto usando perfiles de proyección.
Universidad Nacional de San Agust́ın - UNSA 46
Caṕıtulo 4. Reconocimiento de Palabras
4.1.4. Corrección de la Inclinación de la Escritura
Habiendo segmentado las imágenes en ĺıneas de texto, es necesario eliminar la in-
clinación, hacia la derecha o hacia la izquierda, propia de la escritura a mano; para
ello, se detecta el ángulo α que forma la escritura y la coordenada y. La técnica para
encontrar α es similar a la descrita en la Sección 4.1.2. Se realizan varias transfor-
maciones de arraste usando los ángulos en el intervalo [−π = −18; π = 18], y se
escogen, posteriormente, el ángulo α que produzca la separación más extensa entre
palabra y palabra.
Luego, se aplica a cada pixel (x, y) de la imagen una transformación de arraste
(shear), obteniendo para cada uno de ellos una nueva posición (x′, y′),
x′ = x− (y − yc) tan(α) (4.4)
y′ = y (4.5)
Una ilustración de este proceso es mostrada en la Figura 4.5.
((a)) Imagen antes de la corrección de la inclinación.
((b)) Imagen después de la corrección de la inclinación.
Figura 4.5: Corrección de la inclinación propia de la escritura a mano usando
perfiles de proyección.
4.1.5. Normalización de las Ĺıneas de Texto
Por último, buscando que el reconocimiento sea invariable al tamaño de las imá-
genes de las ĺıneas, es necesario normalizarlas; para tal propósito se usa el método
propuesto en [81], el cual requiere encontrar los ĺımites zonales de una ĺınea de texto,
a saber, el ĺımite X, el ĺımite central y el ĺımite base (ver Figura 4.6). Estos ĺımites
son determinados analizando la proyección horizontal de la imagen; en particular, el
ĺımite central lcentral está definido por el punto más alto de la proyección,
lcentral = arg máx P (i) (4.6)
1≤i≤W
donde P (i) es la proyección horizontal de la i-ésima fila de la imagen. Por otra parte,
los ĺımites X y base son determinados aumentando y disminuyendo un valor al ĺımite
central, respectivamente.
Universidad Nacional de San Agust́ın - UNSA 47
4.1. Preprocesamiento
Luego las áreas central, superior (ascendente) e inferior (descendente) son norma-
lizadas usando diferentes ratios dados por el usuario. Generalmente, las áreas as-
cendentes y descendentes son reducidas ya que estas contienen información menos
significativa. La Figura 4.7 muestra un ejemplo de imagen después de la normaliza-
ción.
Zona Ascender
Zona Central
Zona Descender
Línea X Línea central Línea base
Figura 4.6: Tres zonas de la imagen de una ĺınea de texto: zona de los trazos
ascendentes, zona de los trazos descendentes y zona del cuerpo central que captura
la mayor información de la imagen.
((a)) Imagen antes de la normalización
((b)) Imagen después de la normalización
Figura 4.7: a) Imagen antes y b) después del proceso de normalización, el cual
consiste en reducir la zona de los trazos ascendentes y descendentes de tal manera
que todas las imágenes tengan la misma altura.
4.1.6. Segmentación de las Ĺıneas en Palabras
Finalmente, la última operación es la segmentación de las ĺıneas de texto en palabras.
Para ello, se utiliza un método parecido al descrito en la Sección 4.1.3, i.e., un
método también basado en la proyección de perfiles. En este caso, en vez de calcular
la proyección horizontal, se calcula de la proyección vertical de la ĺınea de texto que
esta siendo procesada; dicha proyección puede ser representada por un vector, P =
[p1, p2, . . . , pW ], donde W es la anchura de la imagen, y px es la x-ésima componente
del vector, que se calcula sumando las intensidades a lo largo de la altura, H, de la
imagen, tal como se muestra,
∑H
px = p(x, y) (4.7)
y=1
Habiendo calculado la proyección vertical, posteriormente se identifican los espacios
entre las palabras, que en la proyección resaltan como mesetas. Dichas mesetas
constituyen los puntos en los cuales la imagen de una ĺınea será dividida.
Universidad Nacional de San Agust́ın - UNSA 48
Caṕıtulo 4. Reconocimiento de Palabras
4.2. Extracción de Caracteŕısticas
En el área de reconocimiento de escritura a mano, uno de los métodos de extracción
de caracteŕısticas que ha proporcionado buenos resultados es aquel basado en el
gradiente. Estos métodos se fundamentan en el cálculo de la fuerza y orientación del
gradiente de cada pixel (x, y) de la imagen; para lo cual, por lo general, se aplica el
operador de Robert [75]. Este operador calcula la magnitud s y la dirección θ del
gradiente de la intensidad del pixel (x, y√) por medio de,
s(x, y) = 4u2 +4v2 (4.8)
y (4v)
θ(x, y) = arctan (4.9)
4u
respectivamente, donde
4 ∂p
u = = p(x+ 1, y + 1)− p(x, y) (4.10)
x
y
4 ∂p
v = = p(x+ 1, y)− p(x, y + 1). (4.11)
y
El procedimiento usado en esta tesis para extraer caracteŕısticas del gradiente, con-
siste en dividir la imagen vertical y horizontalmente en bloques no superpuestos de
igual tamaño; y luego de calcular el gradiente, acumular por cada bloque, su fuerza
según su orientación o dirección en uno de los n intervalos, obtenidos de dividir el
espectro de orientaciones en intervalos de π/n cada uno. Aśı cada bloque tiene un
vector acumulador de n componentes. El valor de n es proporcionado por el usuario
y generalmente toma el valor de 16 o 32.
Además, se suaviza la información de cada vector aplicando un filtro lineal con
componentes [1 4 6 4 1], y un filtro 2D gausiano a los vectores de toda la imagen.
Como resultado se obtiene un vector global de caracteŕısticas x = (x1 . . . , xT ) ,
donde T = n ∗ B y B representa el número de bloques. En [21] se describe con
mayor detalle el método para extraer caracteŕısticas del gradiente.
Universidad Nacional de San Agust́ın - UNSA 49
4.3. Aprendizaje y Reconocimiento
Figura 4.8: Extracción de caracteŕısticas: Una imagen dividida en 3× 3 zonas, para
cada zona se calcula la magnitud del gradiente, el cual se acumula de acuerdo a su
orientación en un vector de acumulación, n = 16. El vector de caracteŕısticas
resulta de concatenar los vectores de acumulación de cada zona.
4.3. Aprendizaje y Reconocimiento
La tercera etapa de la propuesta la constituyen el aprendizaje y reconocimiento.
Para el aprendizaje, se usa en esta tesis una versión adaptada de las máquinas
de vectores de soporte online propuesta por Bordes et al. [9] que será vista en la
Sección 4.3.1. Para el reconocimiento, se propone un método basado en grafos al que
denominaremos Reconocimiento Basado en Grafos (RBG) y que desarrollaremos en
la Sección 4.3.5.
4.3.1. Aprendizaje: Máquinas de Vectores de Soporte Basa-
das en Aprendizaje Online
El modelo de aprendizaje utilizado en esta tesis es el modelo online propuesto por
Bordes et al. [9], el cual basa en el método de Optimización Secuencial Mı́nima
(SMO) de Platt [64]. Este método permite resolver el problema de programación
cuadrática de las SVMs dividiéndolo en múltiples pequeños problemas de progra-
mación cuadrática, los cuales pueden ser resueltos anaĺıticamente.
En la propuesta de Bordes et al., esos problemas de programación cuadrática peque-
ños se crean cada vez que aparece en nuevo ejemplo de entrenamiento, y se resuelven
de manera muy semejante a lo hecho por el algoritmo de Optimización Secuencial
Mı́nima, descrito en la Sección 2.3. Adicionalmente este algoritmo evalúa agregar y
remover algunos vectores de soporte aplicando dos operaciones denominadas Proceso
y Reproceso.
La operación de Proceso intenta insertar un nuevo ejemplo k al conjunto de vectores
de soporte actual S, y posteriormente busca un ejemplo i en el conjunto S con el
máximo gradiente. Si el par de elementos (i, j) infringe el criterio-τ , definido en la
Universidad Nacional de San Agust́ın - UNSA 50
Caṕıtulo 4. Reconocimiento de Palabras
Ecuación 2.22 entonces se actualiza los valores de αi y αj, y se recalcula el gradiente
de todos los ejemplos de S. Este procedimiento es ilustrado en el Algoritmo 1.
Por otra parte, la operación de Reproceso verifica si algunos de los vectores de soporte
actuales dejaron de serlo como consecuencia del ingreso del nuevo ejemplo k. Para
ello, primero identifica un par de elementos (i, j) de S que infrinja el criterio-τ ; y en
caso de encontrarlos, actualiza los valores de αi y αj, y los gradientes de todos los
elementos de S. Luego, remueve los vectores de soporte cuyo α sea igual a cero y cuyo
gradiente salga de los ĺımites de gi y gj. El Algoritmo 2 describe el procedimiento
anteriormente explicado.
Algorithm 1 Proceso
1: function Pro∑ceso(k)( k es un nuevo ejemplo de entrenamiento)
2: αk ← 0
3: gk ← yk − s∈S αkK(k, s)
4: S ← S ∪ {k}
5: if yk = +1 then
6: i← k
7: j ← arg mı́ns∈S gs con αs > As
8: else
9: j ← k
10: i← arg m{ı́ns∈S gs con αs < Bs
11: if (i, j) infringe el criterio-τ then }
12: λ← g −g
mı́n i j
K K − K , Bi − αi, αj − A(i,i)+ (j,j) 2 (i,j) j
13: αi ← αi + λ
14: αj ← αj − λ
15: gs ← gs − λ(K(i, s)−K(j, s)),∀s ∈ S.
Algorithm 2 Reproceso
1: function Reproceso
2: i← arg mı́ns∈S gs con αs < Bs
3: j ← arg m{ı́ns∈S gs con αs > As }
g −g
4: λ← mı́n i j
K(i,i)+K − K , Bi − αi, α − A(j,j) 2 (i,j) j j
5: αi ← αi + λ
6: αj ← αj − λ
7: gs ← gs − λ(K(i, s)−K(j, s)),∀s ∈ S.
8: i← arg mı́ns∈S gs con αs < Bs
9: j ← arg mı́ns∈S gs con αs > As
10: for s ∈ S cuyo αs = 0 do
11: if ys = −1 y gs ≤ gi then
12: S ← S − {s}
13: if ys = +1 y gs ≥ gj then
14: S ← S − {s}
Universidad Nacional de San Agust́ın - UNSA 51
4.3. Aprendizaje y Reconocimiento
4.3.2. Aprendizaje: Extensión del Modelo de Bordes et al.
para Clasificación Multiclase
Al igual que las SVM tradicionales, la SVM-Online de Bordes et al. es un clasificador
binario, y por lo tanto, debe ser extendido si se quiere utilizarla en aplicaciones con
múltiples clases. La estrategia usada para dicha extensión es uno contra uno [7], la
cual consiste en, dadas K clases, entrenar K(K − 1)/2 clasificadores, i.e., entrenar
K(K− 1)/2 SVMs-Online. Cada clasificador recibe los ejemplos de un par de clases
del conjunto de entrenamiento inicial, y debe aprender a distinguir entre esas dos
clases (ver Figura 4.9).
ENTRENAMIENTO Conjunto de Entrenamiento(CE) - K clases
División del 
CE
CE solo clases 1-2 CE solo clases 1-3 CE solo clases 2-3 CE solo clases 2-4 CE solo clases (K-1)-K
SVM SVM SVM SVM SVM
Online Online ... Online Online ... Online
 1 vs. 2  1 vs. 3  2 vs. 3  2 vs. 4  (K – 1) vs. K
K(K - 1) ) / 2 clasificadores
Figura 4.9: SVM-Online para K clases en la fase de entrenamiento.
Para determinar la clase de un ejemplo de prueba, este pasa por cada uno de los
K(K − 1)/2 clasificadores binarios, los cuales predicen una de dos clases. Estas pre-
dicciones son sometidas a un criterio de clasificación, que generalmente, se basa en
la votación de los clasificadores, i.e., la clase predicha será aquella que obtenga la
mayor votación (ver Figura 4.10). Sin embargo y como fue mencionado anteriormen-
te, este criterio produce salidas discretas por lo cual es necesario establecer algún
mecanismo que emita salidas probabiĺısticas.
RECONOCIMIENTO Ejemplo de Prueba
SVM SVM SVM SVM SVM
Online Online ... Online Online ... Online
 1 vs. 2  1 vs. 3  2 vs. 3  2 vs. 4  (K -1) vs. K
Criterio de 
Clasificación
Clase Predicha
Figura 4.10: SVM-Online para K clases en la fase de reconocimiento.
Universidad Nacional de San Agust́ın - UNSA 52
Caṕıtulo 4. Reconocimiento de Palabras
4.3.3. Aprendizaje: Extensión del Modelo de Bordes et al.
para Salidas Probabiĺısticas
El modelo online solamente provee salidas discretas; para obtener las salidas pro-
babiĺısticas que requiere el modelo de reconocimiento propuesto en esta tesis, se
implementó el método de Wu et al. [94], descrito en la Sección 3.4. Para su imple-
mentación se utilizó el método de Newton, descrito en el Algoritmo 3, que consta de
tres pasos principales: la actualización del gradiente y la matriz hessiana, descrito
en el Algoritmo 5; el cálculo de la dirección de búsqueda, descrito en el Algoritmo 6;
y finalmente, la realización de la búsqueda; detallado en el Algoritmo 7. Además se
usa el Algoritmo 4 para actualizar el valor de la función.
El Algoritmo 3, se aplica para cada uno de los K(K − 1)/2 SVMs-Online binarios
descritos en la Sección 4.3.2.
Algorithm 3 Algoritmo Wu
1: function Get Probs(iterM es el número máximo de iteraciones, ηm es el in-
cremento mı́nimo admitido por el algoritmo de búsqueda lineal, σ, e es el error
para el criterio de parada)
2: c+1 ← # de ejemplos con clase +1, c−1 ← # de ejemplos con clase -1
t ← c+1+1
3: +1 , t ← 1
c+1+2 −1 c−1+2
4: Si Li > 0, ti ← t+1, sino ti ← t−1, para todo Li, ti del vector L y t.
5: A← 0
6: B ← log( c−1+1)
c+1+1
7: fv ← 0
8: fv ← Act-Función(l, D, A, B, t)
9: for i ← 1 to iterM do
10: h11 ← σ, h22 ← σ, h21 ← 0, g1 ← 0, g2 ← 0
11: [H,G]← Act-Grad-y-Hess(H,G)
12: if |g1| < e ∧ |g2| < e then
13: break
14: [gd, gA, gB]← Enc-Dir-Bus-Newton(H,G)
15: η ← 1
16: [A,B, fv]← Buscar-Lineal(H,G, η, minη, dA, dB , gd)
17: return A,B
Algorithm 4 Actualizar Valor de Función
1: function Act-Función(l es el número de ejemplos, D = [di] es el vector de
decisiones, A, B, t)
2: for i = 0 to l do
3: fAB ←{DiA+B
f + tifAB + log(1 + exp(−fAB)) si fAB ≥ 0
4: f ←
f + (ti − 1)fAB + log(1 + exp(fAB)) otro caso
5: return f
Universidad Nacional de San Agust́ın - UNSA 53
4.3. Aprendizaje y Reconocimiento
Algorithm 5 Actualizar Gradiente y Hessiana
1: function Act-Grad-y-Hess(H = [hij] es la matriz hessiana, G = [gi] es el
vector gradiente, D = [Di] es el vector de decisión, t = [ti] es el vector auxiliar
calculado en la ĺınea 4 del Algoritmo 3, l es el número de ejemplos)
2: for i← 0 to l do
3: fAB ← DiA+B
4: if fAB ≥ 0 then
p← exp(−f
5: AB)
1+exp(−fAB)
6: q ← 1
1+exp(−fAB)
7: else
8: p← 1
1+exp(fAB)
q ← exp(f
9: AB)
1+exp(fAB)
10: d2 ← pq, d1 ← ti − p
11: h11 ← h11 +DiDid2, h22 ← h22 + d2, h21 ← h21 +Did2
12: g1 ← g1 +Did1, g2 ← g2 + d1
13: return H, G
Algorithm 6 Encontrar la Dirección de Búsqueda de Newton
1: function Enc-Dir-Bus-Newton(H = [hij] es la matriz hessiana, G = [gi] es
el vector gradiente)
2: det← h11h22 − h21h21
d ← −(h
3: 22g1−h21g2)
A det
d ← −(−h21g1+h g
4: 11 2)
B det
5: gd ← g1dA + g2dB
6: return gd, dA, dB
Algorithm 7 Búsqueda Lineal
1: function Buscar-Lineal(H = [hij] es la matriz hessiana, G = [gi] es el vector
gradiente, η es el valor de incremento, minη es mı́nimo incremento permitido,
dA, dB y gd son valores reales devueltos por el Algoritmo 6 )
2: c = 0,0001
3: while η ≥ minη do
4: A′ ← A+ ηdA
5: B′ ← B + ηdB
6: f ′ ← 0
7: f ′ ← Act-Función(l, D, A′, B′, t)
8: if f ′ < fv + cηgd then
9: A← A′
10: B ← B′
11: f ′
v ← f
12: break
13: else
η
14: η ←
2
15: return A,B, fv
Universidad Nacional de San Agust́ın - UNSA 54
Caṕıtulo 4. Reconocimiento de Palabras
Luego, durante la fase reconocimiento se aplica el Algoritmo 8, el cual opera en
un ambiente multiclase. Los argumentos A y B son matrices obtenidas al aplicar
K(K − 1)/2 veces el Algoritmo 3. Las componentes aij y bij almacenan los valores
A y B para las clases i y j, respectivamente. En la ĺınea 2, se calcula la matriz D
también de dimensiones K ×K, la cual almacena las salidas proporcionadas por el
SVM-Online multiclase discreto.
La condición de parada, en la ĺınea 9, se cumple cuando la Ecuación 3.12 es satisfecha,
devolviendo al concluir el bucle, un vector p de probabilidades para cada clase. En
cuestión de implementación, esta condición se puede cumplir al alcanzar un número
máximo de iteraciones, o verificando que para cada clase i ∈ {1, . . . , K}, el valor
absoluto de la diferencia entre T y pT
i Qq sea menor que un determinado error
dado como referencia, donde Ti es la i-ésima componente del vector resultante del
producto T = Qp. Finalmente, en la ĺınea 13, la clase predicha es aquella con mayor
probabilidad. Este es el criterio de clasificación especificado en la Sección 4.3.2.
Algorithm 8 SVM-Online-Probabilidades
1: function SVM-Online-Probabilidades(s es un ejemplo, K es el de clases,
C ← [cj] es un vector de clases, minp es la probabilidad mı́nima admitida,
A← [aij] es una matriz K ×K, B← [bij] es una matriz K ×K)
2: D← salidas proporcionadas por el SVM-Online para el ejemplo s
3: for i← 0 to K do
4: for j ← i+ 1 to K do
5: r{ij ← mı́n(máx(Sigmoide(dij, aij, bij),minp), 1−minp)
6: rji∑← 1− rij
2
7: Q ← l:l 6=i rli si i == j
ij −rjirij si i 6= j
8: pi ← 1 , para todo i ∈ {1, . . . , K}
K
9: while La condición de la Ecuación 3.12 no sea satisfecha do
10: for i← 1 to(K∑do )
11: pi ← 1 − T
Qii j:j 6=iQijpj + p Qp
12: Normalizar(p)
13: j ← máxi∈{1,...,K} pi
14: return [Cj, pj ]
Algorithm 9 Sigmoide
1: function Sigmoide(d es la salida proporcionada por el SVM Online Binario,
A y B son valores reales devueltos por el Algoritmo 3 )
2: f ← dA+B
3: if f ≥ 0 then
o← exp(−f)
4:
1+exp(−f)
5: else
6: o← 1
1+exp(f)
7: return o
Universidad Nacional de San Agust́ın - UNSA 55
4.3. Aprendizaje y Reconocimiento
4.3.4. Reconocimiento: Descripción Formal del Problema
Sea x, un vector de caracteŕısticas, y sea x = (x1, . . . ,xT), una secuencia de vec-
tores de caracteŕısticas que representan a una imagen de una ĺınea de texto, donde
xt ⊂ Rd. Por otra parte, la transcripción de una palabra l está conformada por la
concatenación de una secuencia de caracteres, l = (l1, . . . , lN), donde ln ∈ Σ, para
todo n, 1 ≤ n ≤ N . Σ es el conjunto de caracteres del alfabeto español y N es
número de caracteres que componen dicha palabra. Note que el valor de N no es fijo
ya que el número de caracteres en l vaŕıa dependiendo de la longitud de la palabra
en cuestión.
En base a lo anterior, podemos expresar el problema de la transcripción de texto
como: Dada una secuencia de vectores de caracteŕısticas x, se desea encontrar una
′
secuencia de caracteres l ∈ Σ∗, con la probabilidad condicional más alta,
′
l = arg máx p(l|x), (4.12)
l∈Σ∗
donde Σ∗ es conjunto de secuencias de tamaño finito que se pueden formar con los
elementos de Σ. Lamentablemente, encontrar dicha secuencia mediante una bús-
queda exhaustiva no es factible, puesto que el número de posibles secuencias es
exponencial con respecto a la cardinalidad de Σ.
Para resolver la inviabilidad de la búsqueda exhaustiva, esta tesis propone una heu-
ŕıstica basada en grafos que encuentra, de manera aproximada, la secuencia óptima,
′
l . Esta heuŕıstica es descrita en la siguiente sección.
4.3.5. Reconocimiento Basado en Grafos
La imagen de una palabra puede ser representada por un grafo direccionado, ha-
blando más espećıficamente, por un árbol con n hijos y un único nodo hoja. A
fin de explicar dicha representación, se abordarán a continuación algunos conceptos
básicos.
Una imagen puede ser dividida en N frames, f1, f2, . . . , fN , donde cada frame fi
agrupa un determinado número de columnas consecutivas de la imagen, y cuya an-
chura está determinada por el número de columnas agrupadas. Dicha anchura es
fija y proporcionada por el usuario. Cada frame posee un punto de inicio pi corres-
pondiente a la coordenada x, en la cual el frame empieza. Como se observa en la
Figura 4.11, los caracteres que conforman la imagen se expanden a lo largo de una
determinada cantidad de frames. Por ejemplo, en la Figura 4.12 se ilustra la expan-
sión de los caracteres ‘i’ y ‘s’, que se extienden por 3 y 5 frames respectivamente.
Además, denotaremos con minf , al número mı́nimo de frames que cualquier caracter
abarca, y similarmente con maxf al número máximo de frames. Ambos parámetros
sirven para definir el número de aristas que salen de cada nodo, y en la práctica
Universidad Nacional de San Agust́ın - UNSA 56
Caṕıtulo 4. Reconocimiento de Palabras
Figura 4.11: División de una imagen en frames. p1 representa a la coordenada 0 en
el eje x.
Figura 4.12: Caracteres ‘i’ y ‘s’ se expanden a lo largo de 3 y 5 frames
respectivamente.
pueden ser obtenidos fácilmente a partir del conjunto de entrenamiento, que posee
imágenes de caracteres individuales.
4.3.5.1. Relación entre los Frames de una Imagen y su Grafo
Las ideas expuestas en la sección anterior son la base para la construcción del grafo.
Antes iniciar esta construcción, es importante recordar que hasta este punto se
cuenta con:
la imagen a ser representada y dividida en frames;
la anchura del frame, establecida por el usuario;
los valores minf y maxf , obtenidos del conjunto de entrenamiento.
En este grafo, un nodo representa la coordenada x donde un frame se inicia, y las
aristas representan el número de frames que se toman a partir de la coordenada
x mencionada, es decir, a partir de su nodo origen. El nodo ráız, p1, representa la
primera columna de la imagen y el único nodo hoja a pN + 1, a la última columna
de la imagen más 1. Generalmente, todos los nodos, a excepción del nodo hoja y los
Universidad Nacional de San Agust́ın - UNSA 57
4.3. Aprendizaje y Reconocimiento
nodos que tienen un nivel menos que el nodo hoja, tienen el mismo número de hijos,
Nh, que se calcula usando minf y maxf tal como se muestra,
Nh = maxf −minf + 1 (4.13)
Intuitivamente, esto se puede interpretar de la siguiente manera: ubicándose en la
coordenada x (nodo) de la imagen tenemos n formas (aristas) de tomar subimágenes.
Estas formas abarcan desde tomar minf frames, i.e., tomar el número de frames que
abarca el caracter más angosto del conjunto de datos; hasta tomar maxf frames,
i.e., tomar el número de frames que abarca el caracter más ancho.
En la siguiente sección, se explica la forma en que se construye un grafo a partir de
una imagen dividida en frames.
4.3.5.2. Procedimiento de Construcción del Grafo
El primer nodo en ser creado es pi, con i = 1, el que corresponde a la coordenada
cero del eje x; luego, se añaden (maxf −minf + 1) aristas salientes de p1. Como se
mencionó en la introducción del Caṕıtulo 4, cada una de estas aristas está asociada
a una subimagen, que empieza en la posición p1, y cuya anchura está determinada
por un dado número de frames n en el intervalo [minf ,maxf ].
Posteriormente, se extraen las caracteŕısticas de esta subimagen usando el método
del gradiente, que describe en la Sección 4.2, y se obtiene de la SVM-Online pre-
viamente entrenada, tanto la clase como la probabilidad asociada a dicha clase; en
base a dicha probabilidad se calcula el costo asociado a la arista (ver Figura 4.13).
Además, cada vez que una arista es añadida, su nodo final también es añadido, si
este no existe. Este procedimiento se repite para cada nodo no hoja que no tenga
hijos, hasta que se alcance al nodo pN + 1.
Nótese también que los padres del nodo hoja pN + 1, pueden poseer un número de
aristas salientes que no se ajusten a la Ecuación 4.13. En este sentido se pueden
presentar dos escenarios:
La diferencia entre pN + 1 y pN es un valor que no abarca el mı́nimo número
de frames, minf . En tal caso, se creará sola una arista entre pN y pN + 1.
La diferencia entre pN + 1 y pN es un valor que abarca el mı́nimo número de
frames, minf , pero que no llega al número máximo de frames, maxf . En tal
caso, se crearán solo las aristas cuyos frames lleguen exactamente a pN + 1 y
aquellas que lo excedan serán desconsideradas.
Para ilustrar este proceso, considérese la Figura 4.13 y asúmase que ya se obtuvieron
los valores maxf = 5 y minf = 3. Primero, se añade el nodo inicial p1 y 3 aristas
salientes de p1, a saber, e14, e15 y e16. La arista e14 corresponde a la subimagen que
Universidad Nacional de San Agust́ın - UNSA 58
Caṕıtulo 4. Reconocimiento de Palabras
empieza en la coordinada p1 del eje x y se expande 3 frames a partir de p1. Luego se
calcula el vector de caracteŕısticas de la subimagen en cuestión, el cual se pasa a la
SVM-Online que a su vez provee tanto la clase como la probabilidad de la misma.
Posteriormente, su nodo final p4 es agregado.
Esta explicación puede ser interpretada de la siguiente manera: encontrándose en la
posición p1 y analizando 3 frames (3 fs), que corresponde a la arista e14, se termina
en la posición p4. Similarmente, tomando 4 y 5 frames que corresponden a las aristas
e15 y e16 se terminan en las posiciones p5 y p6 respectivamente (ver Figura 4.13).
Una vez creados los nodos p4, p5 y p6, se agregan 3 aristas salientes de p4 y lue-
go se agregan sus correspondientes nodos finales p7, p8, p9 (ver Figura 4.14(a)). El
mismo procedimiento se ejecuta para p5, p6, p7 (ver Figura 4.14(a)(b)(c)(d)). La
Figura. 4.15 muestra el grafo creado para la imagen de la palabra de parte superior
de la Figura 4.13.
Figura 4.13: Relación entre los frames de una imagen y los elementos
constituyentes de un grafo: nodos y aristas.
4.3.6. La Secuencia Óptima de Caracteres
Para resolver la Ecuación 4.12, se asume que la secuencia de caracteres más pro-
bable corresponde al camino con la mayor probabilidad condicional; de aqúı, la
Ecuación 4.12 es reformulada como se muestra a continuación,
r′ = arg máx p(r|x), (4.14)
r∈cam(G)
Universidad Nacional de San Agust́ın - UNSA 59
4.3. Aprendizaje y Reconocimiento
p1 p1
p4 p5 p6 p7 p4 p5 p6 p7
p8 p9 p8 p9 p10
((a)) Aristas salientes del nodo p4. ((b)) Aristas salientes del nodo p5
p1
p p
1 4 p5 p6 p7
p4 p5 p6 p7
p8 p9 p10 p11
p8 p9 p10 p11 p12
((c)) Aristas salientes del nodo p6 ((d)) Aristas salientes del nodo p7
Figura 4.14: Adición de aristas y nodos en el proceso de construcción del grafo que
representa una imagen.
donde r = (r1, . . . , rN) es un camino (o ruta) del grafo G, el cual está compuesto de
una secuencia de aristas y la probabilidad condicional p, que es definida como,
∏N
p(r|x) = p(rn|x), (4.15)
n=1
donde p(rn|x) es calculada por la SVM-Online previamente entrenada.
Buscando evitar que el producto de las probabilidades se vuelva extremadamente
pequeño, se aplica la función logaritmo, que es monotónicamente creciente, a la
Ecuación 4.14 y 4.15, obteniendo,
r′ = arg máx ln(p(r|x)) (4.16)
r∈cam(G)
Universidad Nacional de San Agust́ın - UNSA 60
Caṕıtulo 4. Reconocimiento de Palabras
p1
p4 p5 p6 p7
p8 p9 p10 p11
p12 p13 p14 p15
p16 p17 p18 p19
p20
Figura 4.15: Grafo resultante del proceso de construcción.
y ∑N
ln(p(r|x)) = ln(p(rn|xn)), (4.17)
n=1
donde, xn es la secuencia de vectores de caracteŕısticas asociadas a la arista rn.
Además, vale mencionar que no todos los caminos del grafo son caminos válidos.
Los únicos caminos relevantes son aquellos que empiezan en p1 y terminan en pN+1,
pues se busca reconocer la imagen completa, i.e., de p1 a pN+1 y no sólo una porción
de ella.
Por otra parte, en la teoŕıa de grafos son bastante conocidos los algoritmos que
resuelven el problema de la ruta de costo mı́nimo, como por ejemplo el algoritmo de
Dijkstra, cuya correctitud teórica ha sido ya demostrada. No obstante no podemos
utilizarlo si usamos ln p directamente, pero śı podemos hacerlo si se crea una función
de costo c (ver Ecuación 4.18) que sea inversamente proporcional a ln p; de esta
manera convertiŕıamos el problema del camino con costo máximo en su equivalente
con costo mı́nimo.
1
c = . (4.18)
ln p
Universidad Nacional de San Agust́ın - UNSA 61
4.3. Aprendizaje y Reconocimiento
A pesar que la función de costo c nos permite usar el algoritmo de Dijkstra, este
todav́ıa no resuelve el problema del todo, ya que de acuerdo a la descripción de la
construcción de un grafo expuesta en la Sección 4.3.5.2, el algoritmo de Dijkstra
favorece los caminos que tienen menos aristas y está sesgado a escoger caminos con
aristas ligadas a subimágenes de mayor anchura, i.e., aristas asociadas a una mayor
cantidad de frames.
Para ilustrar este problema, supóngase que el grafo de la Figura 4.16 contiene única-
mente dos caminos: A = p1, p6, p11, p16, p20 de longitud 4 y B = p1, p4, p8, p12, p16, p20
de longitud 5. Supóngase además que las tres primeras aristas del camino A tengan
un costo igual a 1.25, lo que implica que la probabilidad de estas aristas es 0.8;
supóngase además, que la cuarta arista tenga un costo de 1.1, con probabilidad de
0.9; y que consecuentemente, el costo total del camino sea 4,85; supóngase también
que cada arista del camino B tenga costo igual a 1.1, con probabilidad de 0.9, y con
costo total de 5.5. Evidentemente, las probabilidades del camino B son mayores a
las de A, por lo que B constituiŕıa una secuencia más óptima; sin embargo, ya que
el camino A tiene una menor longitud, el algoritmo de Dijkstra elige al camino A
como el camino de costo mı́nimo (ver Figura 4.17). Debido al problema planteado, es
necesario adaptar este algoritmo para que todos los caminos estén bien balanceados
y no se vean afectados por su longitud.
p
1 h=0
c=1.1 c=1.25
h=1 p p
4 6 h=1
c=1.1 c=1.25
h=2 p p h=2
8 11
c=1.1
c=1.25
h=3 p
12
c=1.1
h=4 p
16
c=1.1
p h=5
20
Figura 4.16: Grafo simplificado con dos únicos caminos: A = p1, p6, p11, p16, p20 de
longitud 4 y B = p1, p4, p4, p12, p16, p20 de longitud 5. c representa el costo de cada
arista, d la distancia desde el nodo origen hasta el nodo en cuestión y h la altura
máxima del nodo en cuestión. La distancia mı́nima se almacena en el nodo p20 y
representa el costo total mı́nimo del camino más óptimo.
El Algoritmo 10 muestra la manera tradicional en que el método de Dijkstra encuen-
Universidad Nacional de San Agust́ın - UNSA 62
Caṕıtulo 4. Reconocimiento de Palabras
d=0 p
1 h=0
c=1.1 c=1.25
d=1.1 h=1 p p
4 6 h=1 d=1.25
c=1.1 c=1.25
d=2.2 h=2 p p h=2 d=2.5
8 11
c=1.1
c=1.25
d=3.3 h=3 p
12
c=1.1
d=3.75 h=4 p
16
c=1.1
p h=5 d=4.85
20
Figura 4.17: Ilustración del problema del algoritmo de Dijkstra. La ruta más corta
resaltada en azul es el camino A = p1, p6, p11, p16, p20 a pesar de que el camino
B = p1, p4, p4, p12, p16, p20 presenta mejores probabilidades asociadas.
tra el camino de menor distancia, para ello cada nodo u tiene asociado una distancia
representada por distancia [u], que no es otra cosa que la menor distancia desde el
nodo inicial hasta el nodo u. En nuestro caso podemos verlo como el costo total mı́-
nimo desde el nodo inicial hasta el nodo u. En las ĺıneas 12 y 13 del Algoritmo 10 se
muestra el cálculo de la distancia de cada nodo hijo v de u, el cual solo se actualiza
cuando la suma de distancia[u] + costo(u, v) es inferior a la distancia[v].
Las modificaciones para lograr una compensación a los caminos de mayor longitud
afectan principalmente a estas dos ĺıneas de código. Se observa en la ĺıneas 13 y 14
del algoritmo modificado (ver Algoritmo 12) que a la suma distancia[u] + costo(u, v)
se le añade una cantidad de ajuste provéıda por una función de balance(u, v), cuyo
cálculo depende principalmente de la altura máxima asociada a los nodos u y v. La
altura máxima de todos los nodos es calculada inicialmente en la ĺınea 6.
El pseudocódigo de la función de balance aplicada al nodo padre u e a hijo v se
muestra en el Algoritmo 11; y consiste en tres pasos: 1) encontrar el promedio µ del
costo de las aristas del camino que parte en el nodo origen y llega al nodo v (ver
ĺınea 2); 2) calcular la diferencia de las alturas máximas del nodo padre u y el nodo
hijo v, la cual proporciona una medida de desbalance en términos de la altura de dos
nodos (ver ĺınea 3). Este desbalance se compensa calculando un factor de balance
resultante del producto del promedio del costo µ y el desbalance de altura ∆ (ver
ĺınea 4).
Universidad Nacional de San Agust́ın - UNSA 63
4.3. Aprendizaje y Reconocimiento
Volviendo al ejemplo desarrollado anteriormente, y aplicando esta heuŕıstica, el pun-
to donde se genera el desbalance es en el nodo p16, ya que la altura máxima del nodo
p11 y de p16 es 2 y 4, respectivamente. Al ejecutar la ĺınea 2, el promedio del costo del
camino p1, p6, p11, p16 es 1.25; luego, ejecutando la ĺınea 3, se obtiene que ∆ = 1, y
finalmente, en la ĺınea 4, el factor de balance fb es 1.25. Aśı, el costo total del camino
p1, p6, p11, p16 aumentaŕıa a 5, mientras que el costo total del camino p1, p4, p4, p12, p16
se mantendŕıa en 4.4, y consecuentemente el algoritmo modificado elegiŕıa al camino
B como el camino óptimo (ver Figura 4.18).
d=0 p
1 h=0
c=1.1 c=1.25
d=1.1 h=1 p p
4 6 h=1 d=1.25
c=1.1 c=1.25
d=2.2 h=2 p p h=2 d=2.5
8 11
c=1.1
c=1.25
d=3.3 h=3 p
12
c=1.1
d=4.4 h=4 p
16
c=1.1
p h=5 d=5.5
20
Figura 4.18: Ilustración de la solución dada por el algoritmo de Dijkstra
modificado. La ruta más corta está dada por el camino B = p1, p4, p4, p12, p16, p20.
Formalmente, la nueva di{stancia del nodo u se estima mediante la siguiente función:
du + cuv + buv si du + cuv + buv < dv
dv = (4.19)
dv otro caso,
donde dv y du son las distancias de los nodos v y u; cuv es el costo de la arista con
origen u y destino v; y buv es el factor de balance que a su vez se calcula por medio
de
du + cuv
buv = (hv − hu + 1), (4.20)
hu + 1
donde hu es la altura máxima del nodo u.
Universidad Nacional de San Agust́ın - UNSA 64
Caṕıtulo 4. Reconocimiento de Palabras
Algorithm 10 Algoritmo de Dijkstra
Require: Q es una cola de prioridad
1: function Dijkstra(Grafo G = (N,A), s es el nodo inicial, N es un conjunto
de nodos y A es un conjunto de aristas)
2: Q← ∅
3: for u ∈ N do
4: distancia[u]←∞
5: padre[u]←NULL
6: distancia[s]← 0
7: Q← Q ∪ {s}
8: while Q 6= ∅ do
9: u← nodo en Q con la mı́nima distancia
10: Q← Q− {u}
11: for v ∈ adyacencia[u] do
12: if distancia[v] >distancia[u] + costo(u, v) then
13: distancia[v] = distancia[u] + costo (u, v)
14: padre[v] = u
15: Q← Q ∪ {v}
Algorithm 11 Algoritmo del Balance
1: function Balance( u es un nodo padre, v es un nodo hijo)
2: µ← distancia[u]+ costo(u, v)/altura[u] + 1
3: ∆(u, v)← altura[v]-altura[u] + 1
4: fb ← µ×∆(u, v)
5: return fb
Algorithm 12 Algoritmo de Dijkstra Modificado
Require: Q es una cola de prioridad
1: function Dijkstra Modificado(Grafo G = (N,A), s es el nodo inicial, N es
un conjunto de nodos y A es un conjunto de aristas)
2: Q← ∅
3: for u ∈ N do
4: distancia[u]←∞
5: padre[u]← NULL
6: altura[u]← altura máxima del nodo u
7: distancia[s]← 0
8: Q← Q ∪ {s}
9: while Q 6= ∅ do
10: u← nodo en Q con la mı́nima distancia
11: Q← Q− {u}
12: for v ∈ adyacencia[u] do
13: if distancia[v] >distancia[u] + costo(u, v) + balance(u, v) then
14: distancia[v] = distancia[u] + costo (u, v)+ balance(u, v)
15: padre[v] = u
16: Q← Q ∪ {v}
Universidad Nacional de San Agust́ın - UNSA 65
4.4. Consideraciones Finales
4.4. Consideraciones Finales
El modelo de reconocimiento propuesto está compuesto por tres módulos: El módulo
de preprocesamiento, el módulo de extracción de caracteŕısticas y el módulo de
reconocimiento.
El módulo de preprocesamiento ejecuta todas las tareas que preparan las imágenes
y que segmentan las páginas en ĺıneas de texto, de tal manera que dichas imágenes
puedan ser usadas directamente en etapas posteriores. El módulo de extracción de
caracteŕısticas se encarga de la creación de vectores de caracteŕısticas, los cuales
son obtenidos en base al cálculo de la magnitud y orientación del gradiente de
cada ṕıxel de una imagen. La magnitud y orientación del gradiente de los ṕıxeles
de una determinada área de la imagen contribuyen en la creación de un vector de
acumulación. De la concatenación de los vectores de acumulación de todas las áreas
en que fue dividida la imagen se forma el vector de caracteŕısticas de la imagen
completa.
Por otra parte, en el módulo de reconocimiento se ejecuta el proceso de aprendizaje
ajustando los parámetros de la SVM-Online en base a los vectores de caracteŕısticas
de las imágenes de los caracteres. También, se realiza el proceso de reconocimiento
propiamente dicho, con el cual cada palabra a ser reconocida es representada por
un grafo; y luego, usando una modificación del algoritmo de Dijkstra se obtiene del
grafo creado, la secuencia óptima de caracteres, i.e., la transcripción de la palabra.
Las principales contribuciones de esta tesis se resumen en la creación del RBG, y
en dos extensiones de la SVM-Online, una para su funcionamiento en un entorno
multiclase y otra para proporcionar las salidas probabiĺısticas que el RBG requiere.
Universidad Nacional de San Agust́ın - UNSA 66
Caṕıtulo 5
Experimentos y Resultados
En este caṕıtulo se presentan los experimentos y los resultados del modelo propuesto.
En la Sección 5.1 se detallan las principales caracteŕısticas de los conjuntos de datos
sobre los que se aplican los experimentos. En la Sección 5.2 y 5.3 se presentan las
medidas de evaluación empleadas para medir el desempeño del modelo y se describen
los experimentos realizados, respectivamente. Finalmente, en la Sección 5.4 y 5.5 se
presentan tanto los resultados de la fase de aprendizaje como los de la fase de
reconocimiento.
5.1. Descripción de los Corpus Utilizados
Vale la pena mencionar que aunque existen muchos estudios sobre documentos his-
tóricos, sus conjuntos de datos no siempre están disponibles.
Por otra parte, hasta donde sabemos, no existen investigaciones que aborden el
aprendizaje online en el área de reconocimiento de texto para manuscritos históricos;
es por eso que las comparaciones son realizadas con investigaciones que todav́ıa no
incorporan el aprendizaje online. En este sentido, en esta tesis se va a utilizar un
corpus de uso libre, i.e., el “Corpus Cristo Salvador”. Aśı mismo, se va a utilizar un
conjunto de datos propio, al cual se le ha denominado,“Ejecutoŕıa y Certificación del
Escudo de Armas de Apellidos”. La construcción de este corpus también constituye
una contribución de esta tesis. También se usa un tercer corpus llamado “Doña
Germana de Foix”.
5.1.1. Cristo Salvador
El Corpus Cristo Salvador (CS) es un manuscrito de 53 páginas escritas en el
idioma español del siglo XIX por Vicente Boix. El documento se encuentra f́ı-
sicamente en la Biblioteca Valenciana Digital http://bv2.gva.es bajo el t́ıtulo
67
5.1. Descripción de los Corpus Utilizados
“Noticia histórica de las fiestas con que Valencia celebró el siglo sexto de la veni-
da a esta capital de la milagrosa imagen del Salvador”. Este corpus ha sido usa-
do por el centro de investigación en Pattern Recognition and Human Language
Technology de la Universidad Politécnica de Valencia y puede ser descargado de
https://www.prhlt.upv.es/page/projects/multimodal/cs/index. Las páginas
fueron escaneadas a color en 300dpi y guardadas en formato JPEG. De este modelo,
se dispone de las imágenes de las páginas y su transcripción. Un fragmento de este
corpus es presentado en la Figura 5.1.
La Tabla 5.1 muestra las estad́ısticas del corpus ECA.
Estad́ısticas Cristo Salvador
Páginas 53
Ĺıneas 681
Palabras 6435
Caracteres 36729 aprox.
Tabla 5.1: Estad́ısticas del corpus CS.
5.1.2. Ejecutoŕıa y Certificación del Escudo de Armas de
Apellidos
El corpus Ejecutoŕıa y Certificación del Escudo de Armas de Apellidos (ECA) es un
libro de 550 páginas escritas a mano por un solo autor en el idioma español del siglo
XVI. Trata de la certificación del escudo de armas de los apellidos Echapare, Loigorri,
Virto y Casado y fue escrito en 1756. Actualmente se encuentra “Biblioteca del
Patrimonio Bibliográfico”, España y está disponible digitalmente en el portal http:
//bvpb.mcu.es. De dicho documento solo se obtuvo las imágenes de las páginas del
libro en escala de grises en formato PNG, aśı que parte de la contribución de esta
tesis fue la transcripción de las páginas del conjunto de datos. Un fragmento de este
corpus es presentado en la Figura 5.2.
La Tabla 5.2 muestra las estad́ısticas del corpus ECA.
Estad́ısticas ECA
Páginas 550
Ĺıneas 10450
Palabras 69300
Caracteres 385000 aprox.
Tabla 5.2: Estad́ısticas del corpus ECA.
Universidad Nacional de San Agust́ın - UNSA 68
Caṕıtulo 5. Experimentos y Resultados
Figura 5.1: Una página del Corpus CS.
Universidad Nacional de San Agust́ın - UNSA 69
5.1. Descripción de los Corpus Utilizados
Figura 5.2: Una página del Corpus ECA
Universidad Nacional de San Agust́ın - UNSA 70
Caṕıtulo 5. Experimentos y Resultados
5.1.3. Doña Germana de Foix
El corpus Doña Germana de Foix (Germana), es un manuscrito 64 páginas titu-
lado “Noticias y documentos relativos a Doña Germana de Foix, última Reina de
Aragón”, escrito en el año 1891 por Vicent Salvador. El proceso de digitalización
del corpus Germana fue realizado por la “Biblioteca Valenciana Digital” (http:
//bivaldi.gva.es/). Las anotaciones del documento fueron realizadas el grupo
Pattern Recognition and Human Language Technology de la Universidad Politécnica
de Valencia. Tanto las imágenes como sus transcripciones pueden ser descargadas
de https://www.prhlt.upv.es/page/projects/multimodal/idoc/germana. Las
imágenes se encuentran en formato PNG en escala de grises.
Un fragmento de este corpus es presentado en la Figura 5.3.
La Tabla 5.3 muestra las estad́ısticas de este corpus.
Estad́ısticas Germana
Páginas 64
Ĺıneas 1472
Palabras 11776
Caracteres 61440 aprox.
Tabla 5.3: Estad́ısticas del corpus Germana.
Es importante mencionar que a pesar de que los conjuntos de datos son grandes,
los experimentos han sido ejecutados en conjuntos de datos más pequeños. Esos
conjuntos de datos están formados por las imágenes de mejor calidad de cada uno de
los corpus. Además, se está trabajando únicamente con los caracteres en minúscula
y no con caracteres en mayúscula.
5.2. Medidas de Evaluación
Para medir el desempeño del modelo SVM-Online se usará la medida usual, i.e.,
exactitud.
Sea una matriz A = [aij] con i, j ∈ t = {t1, t2, . . . , tK}, donde K es el número
de clases de un conjunto de datos y aij es el número de veces que un ejemplo con
etiqueta ti es clasificado como tj. La exactitud es definida como,
∑K
Exactitud = ∑ i∑=1 aii (5.1)
K K
i=1 j=1 aij
Podemos entender la exactitud como la proporción de ejemplos correctamente cla-
Universidad Nacional de San Agust́ın - UNSA 71
5.2. Medidas de Evaluación
Figura 5.3: Una página del Corpus Germana.
Universidad Nacional de San Agust́ın - UNSA 72
Caṕıtulo 5. Experimentos y Resultados
sificados considerando todos los ejemplos del conjunto de prueba.
En este trabajo la exactitud es usada junto a la técnica de validación cruzada. Esta
técnica ha sido ampliamente empleada en el contexto a de aprendizaje máquina con
el fin de asegurar que el resultado de la medida de evaluación sea independiente de la
partición del conjunto de datos en conjunto de entrenamiento y prueba. La idea de
este método es crear diferentes particiones del conjunto de datos y calcular la media
aritmética obtenida de la medida de evaluación usada sobre las particiones creadas.
Existen diferentes formas de crear dichas particiones una de ellas consiste en dividir
el conjunto de datos en I subconjuntos; uno de estos subconjuntos es usado como
conjunto de prueba y los (I − 1) restantes como conjunto de entrenamiento. Luego,
se calcula la media aritmética de los resultados de las I iteraciones, como se muestra:
I
1 ∑
Exactitud = Exactitudi (5.2)
I
i=1
A esta forma de dividir el conjunto de datos se le llama validación cruzada de I
iteraciones y será usada en esta tesis.
Por otra parte, la Tasa de Error de Palabra - Word Error Rate (WER) es una
medida bastante empleada para evaluar sistemas de traducción automática y de
reconocimiento del habla. Debido a la analoǵıa de estos sistemas y los sistemas de
reconocimiento de escritura es que ha sido también usado en esta área como medida
de evaluación. WER se obtiene dividiendo el número de correcciones que deben ser
hechas para obtener una transcripción perfecta, entre el número total de palabras
de la transcripción correcta, i.e.,
i+ e+m
WER = (5.3)
n
donde i es el número de inserciones, e es el número de eliminaciones y m el número
de modificaciones que deben ser realizadas en la transcripción proporcionada por
sistema de reconocimiento para que esta sea correcta, es decir, sea igual a la trans-
cripción real del documento; y n es número total de palabras en la transcripción
real.
5.3. Descripción de los experimentos
Los experimentos realizados en esta tesis se pueden agrupar en tres grupos que se
describen a continuación.
El primer grupo de experimentos permitió comparar el desempeño de la SVM-
Offline y la SVM-Online individualmente. Para su ejecución se utilizó valida-
ción cruzada de 3 iteraciones, se escogió el kernel Gaussiano, y se modificaron
los parámetros del costo C y de γ.
Universidad Nacional de San Agust́ın - UNSA 73
5.4. Resultados de los Experimentos de la Fase de Aprendizaje: Experimentos 1 y 2
El segundo grupo de experimentos tuvo por objetivo observar el comporta-
miento de la exactitud como respuesta del ajuste de parámetros debido a la
aparición de nuevas instancias de entrenamiento.
Por último, la finalidad del tercer grupo fue evaluar el comportamiento del
Reconocedor Basado en Grafos (RBG), usando la SVM-Online. Para estos
experimentos se fijaron los valores de C y γ pero se variaron los parámetros
minf , maxf , w, ∆ (el decremento para recorrer el intervalo [maxf ,minf ]).
Nótese que a pesar de que la Ecuación 4.13 muestra la forma de calcular el
número de hijos de cada nodo, esta solo se cumple cuando ∆ = 1. Si ∆ > 1,
entonces el número de hijos será menor al especificado en la Ecuación 4.13.
5.4. Resultados de los Experimentos de la Fase de
Aprendizaje: Experimentos 1 y 2
A continuación se muestran los resultados del entrenamiento de la SVM-Offline y
la SVM-Online para los conjuntos de datos CS, ECA y Germana en las Seccio-
nes 5.4.1, 5.4.2 y 5.4.3, respectivamente. Para estos experimentos, se han variado los
valores de los parámetros de la técnica de extracción de caracteŕısticas basada en el
gradiente, a saber:
el número de bloques en que la imagen se divide, y
el número de intervalos para las orientaciones del gradiente.
Por otra parte, para la SVM-Offline y la SVM-Online se han modificado los valores
de los siguientes parámetros:
costo de clasificación errónea de los ejemplos de entrenamiento, representado
por C;
el valor del parámetro γ utilizado por el kernel gaussiano.
5.4.1. Corpus CS
Se realizaron varios experimentos a fin de ajustar los valores de los parámetros. En
las Tablas 5.4, 5.5, 5.6 y 5.7 se muestra un resumen de los resultados de la SVM-
Offline para el corpus CS. El número de bloques usados fueron de 3× 3 y de 5× 5,
y el número de intervalos en los cuales la orientación del gradiente fue dividida es
de 16 y 32. Nótese que en la mayoŕıa de los casos, los mejores resultados se han
obtenido fueron usando C = 3. Además, se observa que el uso de bloques de 3 × 3
ofrece mejores tasas que el de 5 × 5. El parámetro γ ha sido bastante laborioso de
ajustar, y los mejores resultados caen en el intervalo de 0.049 a 0.0061.
Universidad Nacional de San Agust́ın - UNSA 74
Caṕıtulo 5. Experimentos y Resultados
Resultados SVM-Offline - CS
bloques: 3× 3, intervalos 16
γ 0.049 0.052 0.053 0.056 0.058 0.059 0.061
C = 1 74.26 75.25 76.24 76.24 76.24 76.24 77.23
C = 2 80.20 80.20 80.20 82.18 82.18 82.18 82.18
C = 3 80.20 82.18 82.18 82.18 83.17 83.17 83.17
Tabla 5.4: Resultados de la SVM-Offline ejecutado sobre el
corpus CS usando bloques de 3× 3 y 16 intervalos.
Resultados SVM-Offline - CS
bloques: 5× 5, intervalos 16
γ 0.049 0.052 0.053 0.056 0.058 0.059 0.061
C = 1 66.34 67.33 67.33 66.34 66.34 66.34 64.36
C = 2 66.34 66.34 66.34 66.34 65.35 65.35 64.36
C = 3 66.34 67.33 67.33 67.33 67.33 67.33 66.34
Tabla 5.5: Resultados de la SVM-Offline ejecutado sobre el
corpus CS usando bloques de 5× 5 y 16 intervalos
Resultados SVM-Offline - CS
bloques: 3× 3, intervalos 32
γ 0.049 0.052 0.053 0.056 0.058 0.059 0.061
C = 1 71.29 71.29 71.29 71.29 72.28 72.28 72.28
C = 2 76.24 76.24 76.24 76.24 76.24 75.25 75.25
C = 3 74.26 75.25 75.25 76.24 76.24 75.25 75.25
Tabla 5.6: Resultados de la SVM-Offline ejecutado sobre el
corpus CS usando bloques de 3× 3 y 32 intervalos
Los valores más promisorios fueron obtenidos para bloques de 3×3 con 16 intervalos,
C = 3 y γ=0.058, γ=0.059, γ=0.061. Con esta configuración de parámetros de
obtuvo una exactitud de 83.17 %.
Universidad Nacional de San Agust́ın - UNSA 75
5.4. Resultados de los Experimentos de la Fase de Aprendizaje: Experimentos 1 y 2
Resultados SVM-Offline - CS
bloques: 5× 5, intervalos 32
γ 0.049 0.052 0.053 0.056 0.058 0.059 0.061
C = 1 53.47 53.47 53.47 52.48 52.48 52.48 50.50
C = 2 59.41 58.42 58.42 57.43 56.44 55.45 53.47
C = 3 59.41 58.42 58.42 57.43 57.43 57.43 54.46
Tabla 5.7: Resultados de la SVM-Offline ejecutado sobre el
corpus CS usando bloques de 5× 5 y 32 intervalos
En la Figura 5.4 se muestra gráficamente los resultados mostrados en las Tablas 5.4, 5.5, 5.6
y 5.7.
((a)) ((b))
((c)) ((d))
Figura 5.4: Resultados SVM-Offline - CS. Los mejores resultados para C = 3,
γ=0.058, γ=0.059, γ=0.061. bloques de 3 × 3 y 16 intervalos.
Universidad Nacional de San Agust́ın - UNSA 76
Caṕıtulo 5. Experimentos y Resultados
Por otro lado, en las Tablas 5.8, 5.9, 5.10 y 5.11 se muestra un compendio de los
resultados de la SVM-Online para el corpus CS. Igual que en caso anterior fueron
usados bloques de 3×3 y de 5×5, e intervalos de orientación de 16 y 32. Se observa
que el uso de bloques de 3× 3 ofrece mejor exactitud que el de 5× 5.
Con la configuración de C = 2, γ = 0,058, γ = 0,059, γ = 0,061, bloques de 3× 3 y
16 intervalos se obtuvo una exactitud de 82.18 %.
En la Figura 5.5 se muestra los resultados de las Tablas 5.8, 5.9, 5.10 y 5.11.
A pesar de que la tasa de reconocimiento de la SVM-Offline es mayor que la de la
SVM-Online por 0.99 %, esta cantidad puede caer dentro del error estad́ıstico; y en
general, se puede observar que ambas versiones de SVM tienen un comportamiento
similar.
Resultados SVM-Online - CS
bloques: 3× 3, intervalos 16
γ 0.049 0.052 0.053 0.056 0.058 0.059 0.061
C = 1 63.37 63.37 64.36 65.35 66.34 68.32 67.33
C = 2 78.22 80.20 79.21 80.20 82.18 82.18 82.18
C = 3 80.20 79.21 79.21 78.22 79.21 79.21 80.20
Tabla 5.8: Resultados de la SVM-Online ejecutado sobre el
corpus CS usando bloques de 3× 3 y 16 intervalos.
Resultados SVM-Online - CS
bloques: 5× 5, intervalos 16
γ 0.049 0.052 0.053 0.056 0.058 0.059 0.061
C = 1 59.41 60.40 60.40 61.39 61.39 61.39 61.39
C = 2 66.34 67.33 67.33 67.33 66.34 66.34 65.35
C = 3 68.32 69.31 69.31 68.32 68.32 68.32 68.32
Tabla 5.9: Resultados de la SVM-Online ejecutado sobre el
corpus CS usando bloques de 5× 5 y 16 intervalos.
Resultados SVM-Online - CS
bloques: 3× 3, intervalos 32
γ 0.049 0.052 0.053 0.056 0.058 0.059 0.061
C = 1 64.36 63.37 63.37 63.37 63.37 64.36 64.36
C = 2 74.26 73.27 73.27 73.27 74.26 74.26 76.24
C = 3 74.26 74.26 74.26 75.25 74.26 74.26 76.24
Tabla 5.10: Resultados de la SVM-Online ejecutado sobre el
corpus CS usando bloques de 3× 3 y 32 intervalos.
Universidad Nacional de San Agust́ın - UNSA 77
5.4. Resultados de los Experimentos de la Fase de Aprendizaje: Experimentos 1 y 2
Resultados SVM-Online - CS
bloques: 5× 5, intervalos 32
γ 0.049 0.052 0.053 0.056 0.058 0.059 0.061
C = 1 59.41 61.39 61.39 61.39 61.39 60.40 60.40
C = 2 68.32 68.32 68.32 68.32 67.33 66.34 66.34
C = 3 67.33 68.32 68.32 68.32 67.33 67.33 67.33
Tabla 5.11: Resultados de la SVM-Online ejecutado sobre el
corpus CS usando bloques de 5× 5 y 32 intervalos.
((a)) ((b))
((c)) ((d))
Figura 5.5: Resultados SVM-Online-CS. Los mejores resultados fueron obtenidos
usando γ=0.058, γ=0.059, γ=0.061, C = 2, bloques de 3 × 3 y 16 intervalos,
validación cruzada de 3 iteraciones.
Universidad Nacional de San Agust́ın - UNSA 78
Caṕıtulo 5. Experimentos y Resultados
Figura 5.6: Evolución de la Exactitud del Corpus CS. Los parámetros del método
del gradiente son bloques= 3× 3, intervalos=16. Los parámetros para el
entrenamiento del SVM-Online son γ = 0,058, γ = 0,059, γ = 0,061, C = 2.
Validación cruzada de 3 iteraciones.
Por otra parte, la Figura 5.6 muestra el comportamiento de la exactitud obtenida
en el conjunto de prueba, a medida que la SVM-Online recibe nuevas instancias de
entrenamiento. Es importante mencionar que esta gráfica de evolución ha sido sua-
vizada, a fin de probar de que, de manera general, el modelo aprende de cada nuevo
ejemplo de entrenamiento que aparece. Las gráficas de evolución correspondientes a
los otros conjuntos de datos también han sido suavizadas.
5.4.2. Corpus ECA
En las Tablas 5.12, 5.13, 5.14 y 5.15 se muestran los resultados de los experimentos
de la SVM-Offline para el corpus ECA. Los intervalos de orientación fueron de 16 y
de 32, cada uno abarcando en 22,5◦ y 11,25◦, respectivamente. El número de bloques
empleados fueron de 3 × 3 y de 5 × 5. A diferencia de los experimentos realizados
con el corpus CS, los resultados de usar intervalos de 16 y 32 para un número de
bloques fijo son prácticamente los mismos.
Igual que en el corpus CS, el uso de bloques de 3 × 3 produce mejores resultados.
También nótese que para la configuración de 3×3 y 32 intervalos todos los resultados
superan el 93 %, y entre ellos la mejor tasa reconocimiento, 93.77 %, fue obtenida
con C = 3 y γ = 0,057, γ = 0,06.
Universidad Nacional de San Agust́ın - UNSA 79
5.4. Resultados de los Experimentos de la Fase de Aprendizaje: Experimentos 1 y 2
Resultados SVM-Offline - ECA
bloques: 3× 3, intervalos 16
γ 0.045 0.048 0.051 0.054 0.057 0.06 0.063
C = 2 93.26 93.13 93.26 93.26 93.13 93.13 93.13
C = 3 93.51 93.26 93.13 92.88 92.88 92.88 92.88
C = 4 93.00 92.75 92.62 92.62 92.75 92.75 92.88
Tabla 5.12: Resultados de la SVM-Offline ejecutado sobre el
corpus ECA usando bloques de 3× 3 y 16 intervalos.
Resultados SVM-Offline - ECA
bloques: 5× 5, intervalos 16
γ 0.045 0.048 0.051 0.054 0.057 0.06 0.063
C = 2 91.22 91.48 91.48 91.35 91.35 91.48 91.35
C = 3 90.97 91.22 91.22 91.35 91.35 91.22 91.09
C = 4 90.97 90.97 90.84 90.71 90.97 90.97 90.97
Tabla 5.13: Resultados de la SVM-Offline ejecutado sobre el
corpus ECA usando bloques de 5× 5 y 16 intervalos.
Resultados SVM-Offline - ECA
bloques: 3× 3, intervalos 32
γ 0.045 0.048 0.051 0.054 0.057 0.06 0.063
C = 2 93.38 93.51 93.38 93.38 93.38 93.38 93.51
C = 3 93.26 93.26 93.38 93.64 93.77 93.77 93.64
C = 4 93.38 93.38 93.38 93.51 93.38 93.51 93.51
Tabla 5.14: Resultados de la SVM-Offline ejecutado sobre el
corpus ECA usando bloques de 3× 3 y 32 intervalos.
Resultados SVM-Offline - ECA
bloques: 5× 5, intervalos 32
γ 0.045 0.048 0.051 0.054 0.057 0.06 0.063
C = 2 90.84 90.84 90.84 90.71 90.71 90.46 90.20
C = 3 90.71 90.71 90.59 90.46 90.33 90.08 89.82
C = 4 90.46 90.46 90.46 90.33 90.20 90.08 89.69
Tabla 5.15: Resultados de la SVM-Offline ejecutado sobre el
corpus ECA usando bloques de 5× 5 y 32 intervalos.
Universidad Nacional de San Agust́ın - UNSA 80
Caṕıtulo 5. Experimentos y Resultados
La Figura 5.7 muestra los resultados de las Tablas 5.12, 5.13, 5.14 y 5.15.
((a)) ((b))
((c)) ((d))
Figura 5.7: Resultados SVM-Offline - ECA. Los mejores resultados para γ=0.057,
γ=0.060, C = 3, bloques de 3 × 3 y 32 intervalos.
Universidad Nacional de San Agust́ın - UNSA 81
5.4. Resultados de los Experimentos de la Fase de Aprendizaje: Experimentos 1 y 2
Los resultados de los experimentos de la SVM-Online usando el corpus ECA son
presentados en las Tablas 5.16, 5.17, 5.18 y 5.19. Una vez más el uso de bloques de
3× 3 produce mejores resultados que aquellos de usar bloques de 5× 5. Aśı mismo,
para un número de bloques fijo, los resultados de usar intervalos de 16 y 32 no vaŕıan
mucho. Similar al caso de la SVM-Offline, empleando bloques de 3×3, 32 intervalos
de orientación, un costo de C = 4 y γ = 0,057, γ = 0,048, γ = 0,051 se obtiene una
tasa de reconocimiento de 93.64 %.
Podemos decir que los resultados de la SVM-Offline y Online son comparables.
La Figura 5.8 grafica los resultados de las Tablas 5.16, 5.17, 5.18 y 5.19.
Resultados SVM-Online - ECA
bloques: 3× 3, intervalos 16
γ 0.045 0.048 0.051 0.054 0.057 0.06 0.063
C = 2 92.88 93.13 93.13 93.26 93.13 92.88 92.88
C = 3 93.00 93.26 93.26 93.38 93.26 93.13 93.13
C = 4 92.49 92.62 92.24 92.11 92.24 92.11 92.11
Tabla 5.16: Resultados de la SVM-Online ejecutado sobre el
corpus ECA usando bloques de 3× 3 y 16 intervalos.
Resultados SVM-Online - ECA
bloques: 5× 5, intervalos 16
γ 0.045 0.048 0.051 0.054 0.057 0.06 0.063
C=2 89.69 89.69 90.33 90.33 90.33 90.08 90.08
C=3 89.57 89.82 90.46 90.59 90.71 91.60 91.60
C=4 89.57 89.57 90.46 90.46 90.59 90.59 90.59
Tabla 5.17: Resultados de la SVM-Online ejecutado sobre el
corpus ECA usando bloques de 5× 5 y 16 intervalos.
Resultados SVM-Online - ECA
bloques: 3× 3, intervalos 32
γ 0.045 0.048 0.051 0.054 0.057 0.06 0.063
C = 2 92.62 92.75 92.88 92.88 92.88 92.88 92.88
C = 3 92.75 92.75 92.88 93.00 93.26 93.38 93.64
C = 4 93.51 93.64 93.64 93.51 93.64 93.51 93.38
Tabla 5.18: Resultados de la SVM-Online ejecutado sobre el
corpus ECA usando bloques de 3× 3 y 32 intervalos.
Finalmente, en la Figura 5.9 se ilustra el comportamiento de la tasa de reconoci-
miento obtenida en el conjunto de prueba de ECA, a medida que la SVM-Online
recibe nuevas instancias de entrenamiento.
Universidad Nacional de San Agust́ın - UNSA 82
Caṕıtulo 5. Experimentos y Resultados
Resultados SVM-Online - ECA
bloques: 5× 5, intervalos 32
γ 0.045 0.048 0.051 0.054 0.057 0.06 0.063
C = 2 91.09 91.22 91.09 91.09 91.09 90.97 90.97
C = 3 90.97 91.09 91.09 91.48 91.48 91.48 91.35
C = 4 91.09 91.09 90.97 90.84 90.71 90.33 90.08
Tabla 5.19: Resultados de la SVM-Online ejecutado sobre el
corpus ECA usando bloques de 5× 5 y 32 intervalos.
((a)) ((b))
((c)) ((d))
Figura 5.8: Resultados SVM-Online - ECA. Los mejores resultados para
γ = 0,057, γ = 0,048, γ = 0,051, C = 4, bloques de 3 × 3 y 32 intervalos.
Universidad Nacional de San Agust́ın - UNSA 83
5.4. Resultados de los Experimentos de la Fase de Aprendizaje: Experimentos 1 y 2
Figura 5.9: Evolución de la Exactitud del Corpus ECA. Los parámetros del método
del gradiente son bloques= 3× 3, intervalos=32. Los parámetros para el
entrenamiento del SVM-Online son γ = 0,057, γ = 0,048, γ = 0,051, C = 4.
Validación cruzada de 3 iteraciones.
5.4.3. Corpus Germana
En las Tablas 5.20, 5.21, 5.22 y 5.23 se muestran los resultados de los experimentos
de la SVM-Offline para el corpus Germana. Los intervalos de orientación escogidos
fueron de 16 y de 32.
Resultados SVM-Offline - Germana
bloques: 3× 3, intervalos 16
γ 0.047 0.048 0.049 0.05 0.051 0.052 0.053
C = 1 84.90 85.42 85.94 85.42 85.94 85.42 85.42
C = 2 85.42 85.94 85.42 85.42 85.42 84.90 84.90
C = 3 84.38 84.38 84.90 84.90 85.42 84.90 84.90
Tabla 5.20: Resultados de la SVM-Offline ejecutado sobre el
corpus Germana usando bloques de 3× 3 y 16 intervalos.
Universidad Nacional de San Agust́ın - UNSA 84
Caṕıtulo 5. Experimentos y Resultados
El número de bloques empleados fueron de 3× 3 y de 5× 5. Parecido al corpus CS,
el uso de bloques de 3× 3 produce mejores resultados que los bloques de 5× 5. Los
mejores resultados se obtuvieron con la configuración de 3× 3 y 16 intervalos. Con
C = 2, γ = 0,048 y con C = 1, γ = 0,051, γ = 0,049 se obtuvo la tasa de 85.94 %.
Resultados SVM-Offline - Germana
bloques: 5× 5, intervalos 16
γ 0.039 0.04 0.041 0.042 0.043 0.044 0.045
C = 1 79.69 79.69 79.69 80.21 79.17 79.17 79.17
C = 2 79.69 79.17 79.17 79.17 78.13 78.13 78.13
C = 3 79.17 79.17 79.17 79.17 78.65 79.17 78.65
Tabla 5.21: Resultados de la SVM-Offline ejecutado sobre el
corpus Germana usando bloques de 5× 5 y 16 intervalos.
Resultados SVM-Offline - Germana
bloques: 3× 3, intervalos 32
γ 0.054 0.055 0.056 0.057 0.058 0.059 0.06
C = 1 84.38 84.38 83.85 83.33 83.85 83.85 83.85
C = 2 82.81 82.29 82.29 82.81 82.81 82.81 82.81
C = 3 83.85 83.33 82.81 83.33 83.33 83.33 83.33
Tabla 5.22: Resultados de la SVM-Offline ejecutado sobre el
corpus Germana usando bloques de 3× 3 y 32 intervalos.
Resultados SVM-Offline - Germana
bloques: 5× 5, intervalos 32
γ 0.039 0.04 0.041 0.042 0.043 0.044 0.045
C = 1 68.23 67.71 67.71 68.23 69.27 68.23 68.75
C = 2 72.92 73.44 72.40 71.88 71.88 72.40 72.40
C = 3 71.88 71.88 71.88 72.40 72.40 72.40 71.88
Tabla 5.23: Resultados de la SVM-Offline ejecutado sobre el
corpus Germana usando bloques de 5× 5 y 32 intervalos.
Universidad Nacional de San Agust́ın - UNSA 85
5.4. Resultados de los Experimentos de la Fase de Aprendizaje: Experimentos 1 y 2
La Figura 5.10 muestra los resultados de las Tablas 5.20, 5.21, 5.22 y 5.23. Con la
configuración C = 2, γ = 0,048 y con C = 1 γ = 0,051, γ = 0,049 usando 3× 3 y 16
intervalos se obtuvo una exactitud de 85.94 %.
((a)) ((b))
((c)) ((d))
Figura 5.10: Resultados SVM-Offline - Germana. Los mejores resultados para
C = 2, γ=0.048, y C = 1, γ = 0,051, γ = 0,049, bloques de 3 × 3 y 16 intervalos.
Universidad Nacional de San Agust́ın - UNSA 86
Caṕıtulo 5. Experimentos y Resultados
Los resultados de los experimentos de la SVM-Online usando el corpus Germana
son presentados en las Tablas 5.24, 5.25, 5.26 y 5.27. De manera general, otra vez los
resultados de la SVM-Offline son mejores que los de la SVM-Online, no obstante,
para este conjunto de datos en particular, la tasa de reconocimiento obtenida por
la SVM-Online es igual a la de la SVM-Offline. Se obtuvo un 85.94 % con C = 1 y
γ = 0,049, bloques de 3 × 3 y 16 intervalos.
La Figura 5.11 grafica los resultados de las Tablas 5.24, 5.25, 5.26 y 5.27.
Resultados SVM-Online - Germana
bloques: 3× 3, intervalos 16
γ 0.047 0.048 0.049 0.05 0.051 0.052 0.053
C = 1 82.29 84.90 85.94 84.38 83.33 83.33 84.90
C = 2 82.29 82.29 84.90 83.85 82.81 82.29 81.77
C = 3 82.81 82.81 82.81 82.29 82.29 81.77 81.25
Tabla 5.24: Resultados de la SVM-Online ejecutado sobre el
corpus Germana usando bloques de 3× 3 y 16 intervalos.
Resultados SVM-Online - Germana
bloques: 5× 5, intervalos 16
γ 0.039 0.04 0.041 0.042 0.043 0.044 0.045
C = 1 77.08 76.56 77.08 77.08 76.56 76.04 77.08
C = 2 77.08 76.04 76.56 76.56 76.04 75.52 76.04
C = 3 76.56 76.04 76.04 76.56 76.04 76.04 76.56
Tabla 5.25: Resultados de la SVM-Online ejecutado sobre el
corpus Germana usando bloques de 5× 5 y 16 intervalos.
Resultados SVM-Online - Germana
bloques: 3× 3, intervalos 32
γ 0.054 0.055 0.056 0.057 0.058 0.059 0.06
C = 1 83.33 83.33 83.33 83.33 83.33 83.85 83.33
C = 2 81.25 81.25 81.77 81.77 82.29 81.77 81.77
C = 3 83.33 82.81 82.81 82.81 83.33 82.81 82.81
Tabla 5.26: Resultados de la SVM-Online ejecutado sobre el
corpus Germana usando bloques de 3× 3 y 32 intervalos.
Universidad Nacional de San Agust́ın - UNSA 87
5.4. Resultados de los Experimentos de la Fase de Aprendizaje: Experimentos 1 y 2
Resultados SVM-Online - Germana
bloques: 5× 5, intervalos 32
γ 0.039 0.04 0.041 0.042 0.043 0.044 0.045
C = 1 67.19 67.19 67.19 67.71 67.71 67.19 67.71
C = 2 72.40 72.40 71.88 71.35 71.88 71.88 71.35
C = 3 71.35 71.35 71.35 70.83 70.83 71.35 71.35
Tabla 5.27: Resultados de la SVM-Online ejecutado sobre el
corpus Germana usando bloques de 5× 5 y 32 intervalos.
((a)) ((b))
((c)) ((d))
Figura 5.11: Resultados SVM-Online -Germana. Los mejores resultados para
C = 1 y γ = 0,049, bloques de 3 × 3 y 16 intervalos.
Universidad Nacional de San Agust́ın - UNSA 88
Caṕıtulo 5. Experimentos y Resultados
Figura 5.12: Evolución de la Exactitud del Corpus Germana. Los parámetros del
método del gradiente son bloques= 3× 3, intervalos=16. Los parámetros para el
entrenamiento del SVM-Online son C = 1 y γ = 0,049. Validación cruzada de 3
iteraciones.
Finalmente, en la Figura 5.12 se ilustra el comportamiento de la tasa de reconoci-
miento obtenida en el conjunto de prueba de Germana, a medida que la SVM-Online
recibe nuevas instancias de entrenamiento.
5.5. Resultados de la Fase de Reconocimiento: Ex-
perimento 3
En esta sección se muestran los resultados del tercer experimento. Este permite eva-
luar el comportamiento del Reconocedor Basado en Grafos propuesto en esta tesis.
Para los experimentos se utilizó, en cada caso, la mejor configuración de parámetros
obtenidos en los experimentos anteriores.
5.5.1. Corpus CS
Las Tablas 5.28, 5.29 y 5.30 muestran los resultados del Reconocedor Basado en
Grafos. En la primera columna de la izquierda se colocan los valores para el pará-
metro de anchura del frame, w, mientras que en la segunda se muestran los valores
para la variable ∆ que representa el incremento con el que se va a recorrer el rango
Universidad Nacional de San Agust́ın - UNSA 89
5.5. Resultados de la Fase de Reconocimiento: Experimento 3
de maxf a minf . La tercera columna muestra el WER obtenido cuando minf = 4 y
maxf = 9. Aśı, el valor de 0.350 es el WER obtenido al utilizar una anchura de frame
igual a 2 (w = 2), un número mı́nimo de frames igual a 4 (minf = 4), un número
máximo de frames igual a 9 (maxf = 9), y avanzar en ese rango en incrementos de
2 frames (∆ = 2).
Word Error Rate ( %)
Reconocedor Basado en Grafos - RBG
SVM Online - CS
minf −maxf minf −maxf minf −maxf minf −maxf
w ∆ 4 – 9 4 – 10 4 – 11 4 – 12
2 2 33.00 58.30 42.10 60.00
3 2 55.00 36.70 71.70 60.00
2 3 28.80 50.00 37.10 45.40
3 3 78.30 40.00 75.00 90.00
Tabla 5.28: Word Error Rate del RBG ejecutado con minf = 4 y SVM - Online
entrenado con parámetros γ = 0,058, C = 2, 3× 3 bloques y 16 intervalos.
Word Error Rate ( %)
Reconocedor Basado en Grafos - RBG
SVM-Online - CS
minf −maxf minf −maxf minf −maxf minf −maxf
w ∆ 5 – 9 5 – 10 5 – 11 5 – 12
2 2 33.30 33.80 42.10 52.10
3 2 55.00 83.30 71.70 90.00
2 3 28.80 43.80 37.10 45.40
3 3 78.30 88.30 75.00 90.00
Tabla 5.29: Word Error Rate del RBG ejecutado con minf = 5 y SVM-Online
entrenado con parámetros γ = 0,058, C = 2, 3× 3 bloques y 16 intervalos.
Se observa que los mejores resultados se obtienen cuando w = 2,minf = 4,maxf = 9
y ∆ = 3. En este caso el WER baja a 28.8 %.
Finalmente, la Tabla 5.31 muestra una comparación de los resultados del Reconoce-
dor Basado en Grafos y el modelo propuesto por Romero et al. [77].
Universidad Nacional de San Agust́ın - UNSA 90
Caṕıtulo 5. Experimentos y Resultados
Word Error Rate ( %)
Reconocedor Basado en Grafos - RBG
SVM-Online - CS
minf −maxf minf −maxf minf −maxf minf −maxf
w ∆ 6 – 9 6 – 10 6 – 11 6 – 12
2 2 48.80 33.80 33.30 52.10
3 2 80.00 83.30 90.00 90.00
2 3 28.80 43.80 48.30 45.40
3 3 78.30 88.30 91.70 90.00
Tabla 5.30: Word Error Ratedel RBG ejecutado con minf = 6 y SVM-Online
entrenado con parámetros γ = 0,058, C = 2, 3× 3 bloques y 16 intervalos.
Resultados Comparativos
Word Error Rate ( %)
Romero et al. [77] HMM 28.5
Esta tesis RBG con SVM-Online 28.8
w = 2, ∆ = 3, minf = 4,
maxf = 9, 3× 3 bloques, 16
intervalos
Tabla 5.31: Word Error Rate del Reconocedor Basado en Grafos, propuesto en esta
tesis, versus el modelo de Romero et al. [77].
5.5.2. Corpus ECA
Las Tablas 5.32, 5.33 y 5.34 presentan los resultados del Reconocedor Basado en
Grafos para el conjunto de datos ECA. En las tres tablas se puede observar que la
configuración de los parámetros w y ∆ con la que se obtuvo mejores resultados fue
w = 2 y ∆ = 3. Con estos valores se produjo un WER de 17.68 % para un minf = 4
y maxf = 12, y de 13.99 % para un minf = 5 o minf = 6 y maxf = 12.
De manera general, se puede decir que los cuatro parámetros del reconocedor pro-
puesto son bastante sensibles al cambio. Además, de los experimentos se puede ver
que w = 3 y ∆ = 3 producen los mayores WER. Esto se explica ya que mientras
mayores sean w y ∆ = 3, un menor número de aristas salen de cada nodo del grafo,
lo que limita las posibilidades de búsqueda.
Universidad Nacional de San Agust́ın - UNSA 91
5.5. Resultados de la Fase de Reconocimiento: Experimento 3
Word Error Rate ( %)
Reconocedor Basado en Grafos - RBG
SVM-Online - ECA
minf −maxf minf −maxf minf −maxf minf −maxf
w ∆ 4 – 10 4 – 11 4 – 12 4 – 9
2 2 28.75 19.97 24.55 20.36
2 3 25.70 18.83 13.99 23.41
3 2 29.01 36.90 37.79 24.55
3 3 29.01 38.55 40.97 30.03
Tabla 5.32: Word Error Rate del RBG ejecutado con minf = 4 y SVM-Online
entrenado con parámetros γ = 0,057, C = 4, 3× 3 bloques y 32 intervalos.
Word Error Rate ( %)
Reconocedor Basado en Grafos - RBG
SVM-Online - ECA
minf −maxf minf −maxf minf −maxf minf −maxf
w ∆ 5-10 5 - 11 5 - 12 5 - 9
2 2 18.83 19.97 17.68 20.36
2 3 21.12 18.83 13.99 23.41
3 2 32.06 36.90 40.97 24.55
3 3 40.20 38.55 40.97 30.03
Tabla 5.33: Word Error Rate del RBG ejecutado con minf = 5 y SVM - Online
entrenado con parámetros γ = 0,057, C = 4, 3× 3 bloques y 32 intervalos.
Word Error Rate ( %)
Reconocedor Basado en Grafos - RBG
SVM-Online - ECA
minf −maxf minf −maxf minf −maxf minf −maxf
w ∆ 6-10 6 - 11 6 - 12 6 - 9
2 2 18.83 17.68 17.68 15.27
2 3 21.12 25.70 13.99 23.41
3 2 32.06 43.89 40.97 37.79
3 3 40.20 45.17 40.97 30.03
Tabla 5.34: Word Error Rate del RBG ejecutado con minf = 6 y SVM-Online
entrenado con parámetros γ = 0,057, C = 4, 3× 3 bloques y 32 intervalos.
Universidad Nacional de San Agust́ın - UNSA 92
Caṕıtulo 5. Experimentos y Resultados
5.5.3. Corpus Germana
Las Tablas 5.35, 5.36 y 5.37 presentan los resultados del Reconocedor Basado en
Grafos para el conjunto de datos Germana. En las tres tablas se puede observar que
la configuración de los parámetros w y ∆ con la que se obtuvo mejores resultados fue
w = 2 y ∆ = 3. Con estos valores se produjo un WER de 18.53 % para un minf = 4
y maxf = 11.
Word Error Rate ( %)
Reconocedor Basado en Grafos - RBG
SVM-Online - Germana
minf −maxf minf −maxf minf −maxf minf −maxf
w ∆ 4 – 9 4 – 10 4 – 11 4 – 12
2 2 38.93 27.42 24.69 31.51
3 2 29.87 28.47 27.94 36.37
2 3 25.86 19.49 18.53 25.90
3 3 30.22 39.95 41.54 39.95
Tabla 5.35: Word Error Rate del RBG ejecutado con minf = 4 y SVM-Online
entrenado con parámetros γ = 0,048, C = 1, 3× 3 bloques y 16 intervalos.
Word Error Rate ( %)
Reconocedor Basado en Grafos - RBG
SVM-Online - Germana
minf −maxf minf −maxf minf −maxf minf −maxf
w ∆ 5 – 9 5 – 10 5 – 11 5 – 12
2 2 38.93 35.4 24.69 52.1
3 2 29.87 22.56 27.94 37.32
2 3 25.86 20.41 18.53 25.90
3 3 30.22 55.22 41.54 39.95
Tabla 5.36: Word Error Rate del RBG ejecutado con minf = 5 y SVM-Online
entrenado con parámetros, γ = 0,048, C = 1, 3× 3 bloques y 16 intervalos.
5.6. Consideraciones Finales
En este caṕıtulo se mostraron los experimentos y resultados del Reconocedor Basado
en Grafos junto con la SVM-Online extendido. Fueron usados tres conjuntos de
datos, a saber, CS, ECA y Germana. El primer conjunto de datos fue usado para
poder realizar comparaciones el modelo propuesto por Romero et al. [77]
Se realizaron tres experimentos: el primero se enfocó en evaluar el desempeño de la
SVM-Online con respecto a la SVM-Offline, el segundo mostró la evolución de la
exactitud a medida que nuevas instancias de entrenamiento fueron agregadas a la
Universidad Nacional de San Agust́ın - UNSA 93
5.6. Consideraciones Finales
Word Error Rate ( %)
Reconocedor Basado en Grafos - RBG
SVM-Online - Germana
minf −maxf minf −maxf minf −maxf minf −maxf
w ∆ 6 – 9 6 – 10 6 – 11 6 – 12
2 2 48.48 35.4 33.35 52.10
3 2 28.86 22.56 37.21 37.32
2 3 25.86 20.41 41.85 25.90
3 3 30.22 55.22 41.32 39.95
Tabla 5.37: Word Error Rate del RBG ejecutado con minf = 4 y SVM - Online
entrenado con parámetros γ = 0,048, C = 1, 3× 3 bloques y 16 intervalos.
SVM-Online, el tercero evaluó el desempeño del sistema completo. i.e., del Recono-
cedor Basado en Grafos. Se usó la métrica más usada en sistemas de reconocimiento
de texto, a saber, el WER.
En los experimentos se demostró que los resultados son comparables al modelo de
Romero et al. [77].
Universidad Nacional de San Agust́ın - UNSA 94
Caṕıtulo 6
Conclusiones y Trabajos
Futuros
En este trabajo de doctorado, se presenta un sistema de reconocimiento de palabras
contenidas en manuscritos históricos, basado en aprendizaje Online. Este tipo de
aprendizaje ofrece a los sistemas la posibilidad de ajustar sus parámetros sin la
necesidad de reiniciar el entrenamiento, i.e., sin necesidad de retomar los ejemplos
que fueron utilizados en el entrenamiento inicial.
Para evaluar el desempeño del sistema, fueron utilizados tres conjuntos de entrena-
miento. Uno de ellos, “Ejecutoŕıa y Certificación del Escudo de Armas de Apellidos”,
es un corpus especialmente creado para esta investigación. El corpus “Cristo Salva-
dor”, es usado para posibilitar comparaciones con otra propuesta de la literatura.
También se usó el corpus “Doña Germana de Foix”.
En concordancia con los experimentos, se puede afirmar que los resultados obteni-
dos son satisfactorios en relación a otros resultados presentados en la literatura de
transcripción de textos.
6.1. Contribuciones
Las contribuciones de esta tesis son las siguientes:
Se construyó un conjunto de datos propio. El documento fue obtenido de
la “Biblioteca del Patrimonio Bibliográfico” de España y está disponible en
http://bvpb.mcu.es. El documento fue transcrito y a cada página del docu-
mento se les aplicó un serie de algoritmos de procesamiento. Las páginas fueron
segmentadas en ĺıneas y estas últimas en palabras. Adicionalmente, para cons-
truir el conjunto de entrenamiento, las palabras fueron divididas en caracteres.
Fueron anotadas las posiciones donde cada palabra empieza y termina, aśı co-
mo también, donde comienza y termina cada caracter.
95
6.2. Publicaciones Relacionadas a esta Tesis
Se construyó un sistema de reconocimiento de palabras que usa el aprendizaje
online. En particular, se utilizó la SVM-Online de Bordes et al. [9], y se la
modificó en dos aspectos. El primer aspecto permite que el clasificador pueda
desenvolverse en un ambiente multiclase y no solo en el contexto clásico de
dos clases. El segundo aspecto busca que el clasificador pueda actuar junto al
reconocedor basado en grafos, y para ello, se modificó la SVM-Online para que
produzca salidas probabiĺısticas y no solo salidas discretas.
Se construyó un Reconocedor Basado en Grafos que tiene por objetivo evitar la
segmentación de un palabra a nivel de caracter durante el reconocimiento. Di-
cho reconocedor usa las salidas probabiĺısticas provéıdas por una SVM-Online
previamente entrenada, y en base a ella se calcula un costo para cada arista.
Finalmente, para obtener la la secuencia de caracteres que más se ajusta a la
imagen, se utiliza el algoritmo de Dijkstra.
6.2. Publicaciones Relacionadas a esta Tesis
Graciela Lecireth Meza Lovón. A Language Model for Improving the Graph-
Based Transcription Approach for Historical Documents. Advances in Artifi-
cial Intelligence - IBERAMIA 2014 - 14th Ibero-American Conference on AI,
Santiago de Chile, Chile, November 24-27, 2014, Proceedings, pág. 229-241,
2014.
Graciela Lecireth Meza Lovón. A Graph-Based Approach for Transcribing An-
cient Documents. Advances in Artificial Intelligence - IBERAMIA 2012 - 13th
Ibero-American Conference on AI, Cartagena de Indias, Colombia, November
13-16, 2012, Proceedings, pág. 210-220, 2012.
6.3. Trabajos Futuros
Una de las razones para incorporar este tipo de aprendizaje nace de las nuevas
tendencias en esta área. Como se mencionó en el Caṕıtulo 1, en el contexto de reco-
nocimiento de manuscritos históricos, la transcripción completamente automática en
la mayoŕıa de los casos no produce buenos resultados, en consecuencia, se requiere en
la práctica de un trabajo de posedición, el cual es realizado por un experto humano,
quien va corrigiendo los errores producidos durante el reconocimiento automático.
Estas correcciones constituyen datos ya validados, y pueden ser utilizados como
nuevas instancias de entrenamiento, en base a las cuales se puede seguir ajustando
el modelo de reconocimiento. Esta continuidad en el ajuste de los parámetros puede
resultar conveniente en el contexto de reconocimiento de escritura, pues existen
palabras y/o caracteres que son menos frecuentes, y por tal motivo, el conjunto de
entrenamiento inicial podŕıa estar un tanto desbalanceado, y con clases que están
mejor entrenadas que otras.
Universidad Nacional de San Agust́ın - UNSA 96
Caṕıtulo 6. Conclusiones y Trabajos Futuros
Por lo tanto, un primer trabajo relacionado se refiere a la extensión de nuestra
propuesta al aprendizaje interactivo, el cual aprovechando la retroalimentación del
experto podŕıa mejorar el desempeño del sistema en dos aspectos:
El primero se refiere a que, habiendo el usuario, corregido y/o validado su
predicción en un tiempo t, el componente de reconocimiento del sistema podŕıa
refinar (actualizar) su salida para un tiempo t+ 1.
El segundo se refiere al aspecto online mencionado en el párrafo anterior, i.e.,
habiendo el usuario, corregido y/o validado su predicción en un tiempo t, el
componente de aprendizaje del sistema podŕıa ajustar sus parámetros para
que el aprendizaje continúe en clases no tan bien entrenadas.
Por otra parte, un aspecto no considerado en esta tesis es el problema del vocabulario
abierto, por lo cual seŕıa importante incorporar un componente que permita tener en
cuenta las transcripciones que no correspondan a ninguna palabra del diccionario.
Adicionalmente, como se puede observar en el Caṕıtulo 4, el diccionario de esta tesis
se construye en base a la transcripción del conjunto de datos. En este sentido, se
podŕıan usar otros diccionarios o documentos de origen similar a fin de expandir el
diccionario inicial.
Finalmente, el tercer trabajo futuro se refiere a la creación de un protocolo de inter-
acción entre el usuario y el sistema. Con dicho protocolo se definiŕıan las acciones
que debe realizar un usuario para, por ejemplo:
Indicar que un prefijo está siendo validado, i.e., para indicar que se acepta la
transcripción dada por el sistema.
Indicar que se está realizando una corrección.
Indicar que terminó la corrección.
Indicar que el sistema debe aceptar la corrección.
Etc.
Universidad Nacional de San Agust́ın - UNSA 97
Bibliograf́ıa
[1] A.R. Ahmad, C. Viard-Gaudin, and M. Khalid. Lexicon-Based Word Recogni-
tion Using Support Vector Machine and Hidden Markov Model. In Proceedings
of the 2009 10th International Conference on Document Analysis and Recogni-
tion(ICDAR ’09), pages 161–165, 2009.
[2] J.H. AlKhateeb, J. Ren, J. Jiang, and H. Al-Muhtaseb. Offline handwritten
Arabic cursive text recognition using Hidden Markov Models and re-ranking.
Pattern Recognition Letters, 32(8):1081–1088, 2011.
[3] J. Almazán, A. Gordo, A. Fornés, and E. Valveny. Segmentation-free word
spotting with exemplar SVMs. Pattern Recognition, 47(12):3967 – 3978, 2014.
[4] C. Bahlmann, B. Haasdonk, and H. Burkhardt. On-line Handwriting Recogni-
tion with Support Vector Machines - A Kernel Approach. In Proc. of the 8th
International Workshop on Frontiers in Handwriting Recognition (IWFHR),
pages 49–54, 2002.
[5] H.S. Baird. The skew angle of printed documents. In Document image analysis,
pages 204–208. IEEE Computer Society Press, 1995.
[6] Y. Bengio, Y. LeCun, and D. Henderson. Globally Trained Handwritten Word
Recognizer Using Spatial Representation, Convolutional Neural Networks, and
Hidden Markov Models. In Proc. 7th Neural Information Processing Systems-
Conference (NIPS’93), pages 937–944, 1993.
[7] C.M. Bishop. Pattern Recognition and Machine Learning (Information Science
and Statistics). Springer-Verlag New York, Inc., Secaucus, NJ, USA, 2006.
[8] A. Bordes and L. Bottou. The Huller: a simple and efficient online SVM.
Machine Learning: ECML 2005, 2005.
[9] A. Bordes, S. Ertekin, J. Weston, and L. Bottou. Fast Kernel Classifiers with
Online and Active Learning. J. Mach. Learn. Res., 6:1579–1619, December
2005.
[10] B.E. Boser, I.M. Guyon, and V.N. Vapnik. A Training Algorithm for Optimal
Margin Classifiers. In Proceedings of the Fifth Annual Workshop on Compu-
tational Learning Theory, COLT ’92, pages 144–152, New York, NY, USA, 1992.
ACM.
[11] G. Cauwenberghs and T. Poggio. Incremental and decremental support vec-
tor machine learning. In Advances in Neural Information Processing Systems
(NIPS*2000), volume 13, 2001.
98
BIBLIOGRAFÍA
[12] C. Cortes and V. Vapnik. Support-vector networks. Maching Learning,
20(3):273–297, 1995.
[13] Nibaran Das, Ram Sarkar, Subhadip Basu, Punam K. Saha, Mahantapas Kun-
du, and Mita Nasipuri. Handwritten bangla character recognition using a soft
computing paradigm embedded in two pass approach. Pattern Recognition,
48(6):2054 – 2071, 2015.
[14] Jaety Edwards, Yee Whye Teh, David Forsyth, Roger Bock, Michael Maire,
and Grace Vesom. Making latin manuscripts searchable using gHMM’s. In
Lawrence K. Saul, Yair Weiss, and Léon Bottou, editors, Advances in Neural
Information Processing Systems 17, pages 385–392. MIT Press, Cambridge,
MA, 2005.
[15] A. El-Yacoubi, R. Sabourin, C. Y. Suen, and M. Gilloux. An HMM-based
approach for off-line unconstrained handwritten word modeling and recognition.
IEEE Trans. Pattern Anal. Mach. Intell., 21(8):752–760, 1999.
[16] J. Fierrez, J. Ortega-Garcia, D. Ramos, and J. Gonzalez-Rodriguez. HMM-
based on-line signature verification: Feature extraction and signature modeling.
Pattern Recognition Letters, 28(16):2325–2334, 2007.
[17] A. Fischer, A. Keller, V. Frinken, and H. Bunke. HMM-based Word Spotting
in Handwritten Documents Using Subword Models. In Proceedings of the 20th
International Conference on Pattern Recognition (ICPR ’10), pages 3416–3419,
2010.
[18] V. Frinken, A. Fischer, and H. Bunke. Combining neural networks to impro-
ve performance of handwritten keyword spotting. In Proc. 9th Int. Conf. on
Multiple Classifier Systems (MCS’10), pages 215–224, 2010.
[19] V. Frinken, A. Fischer, and H. Bunke. Combining neural networks to improve
performance of handwritten keyword spotting. In Proceedings of the 9th inter-
national conference on Multiple Classifier Systems (MCS’10), pages 215–224,
2010.
[20] V. Frinken, A. Fischer, H. Bunke, and R. Manmatha. Adapting BLSTM Neural
Network Based Keyword Spotting Trained on Modern Data to Historical Docu-
ments. In Proceedings of the 2010 12th International Conference on Frontiers
in Handwriting Recognition (ICFHR ’10), pages 352–357, 2010.
[21] Y. Fujisawa, M. Shi, T. Wakabayashi, and F. Kimura. Handwritten Numeral
Recognition Using Gradient and Curvature of Gray Scale Image. In Proc. 5th
Int. Conf. on Document Analysis and Recognition (ICDAR ’99), pages 277–300,
1999.
[22] A. Graves, S. Fernández, and F. Gomez. Connectionist temporal classification:
Labelling unsegmented sequence data with recurrent neural networks. In In
Proceedings of the International Conference on Machine Learning, ICML 2006,
pages 369–376, 2006.
Universidad Nacional de San Agust́ın - UNSA 99
BIBLIOGRAFÍA
[23] A. Graves, S. Fernández, and J. Schmidhuber. Bidirectional LSTM networks
for improved phoneme classification and recognition. In Proceedings of the 15th
international conference on Artificial neural networks: formal models and their
applications - Volume Part II (ICANN’05), pages 799–804, 2005.
[24] A. Graves, M. Liwicki, S. Fernández, R. Bertolami, H. Bunke, and J. Schmidhu-
ber. A Novel Connectionist System for Unconstrained Handwriting Recognition.
IEEE Trans. Pattern Anal. Mach. Intell., 31(5):855–868, 2009.
[25] A. Graves and J. Schmidhuber. Framewise phoneme classification with bi-
directional LSTM and other neural network architectures. Neural Networks,
18(5-6):602–610, 2005.
[26] Y. Guerbai, Y. Chibani, and B. Hadjadji. The effective use of the one-class SVM
classifier for handwritten signature verification based on writer-independent
parameters. Pattern Recognition, 48(1):103 – 113, 2015.
[27] K. Gyeonghwan and V. Govindaraju. A lexicon driven approach to handwritten
word recognition for real-time applications. IEEE Transactions on Pattern
Analysis and Machine Intelligence, 19(4):366–379, 1997.
[28] K. Gyeonghwan, L. Seokgoo, S. Miyoung, and S. N. Yun. Analysis of postal
address fields for efficient encoding of Korean mail pieces. In Proceedings of the
Sixth International Conference on Document Analysis and Recognition (ICDAR
’01), pages 675–679, 2001.
[29] T. Hastie and R. Tibshirani. Classification by pairwise coupling. In Proceedings
of the 1997 Conference on Advances in Neural Information Processing Systems
10, NIPS ’97, pages 507–513, Cambridge, MA, USA, 1998. MIT Press.
[30] S. Impedovo, L. Ottaviano, and S. Occhinegro. Optical character recognition: A
survey. International Journal of Pattern Recognition and Artificial Intelligence,
05(01n02):1–24, 1991.
[31] R. Jain, V. Frinken, C. V. Jawahar, and R. Manmatha. BLSTM Neural Net-
work Based Word Retrieval for Hindi Documents. In Proceedings of the 2011
International Conference on Document Analysis and Recognition (ICDAR ’11),
pages 83–87, 2011.
[32] R. Jayadevan, S. R. Kolhe, P. M. Patil, and U. Pal. Automatic processing of
handwritten bank cheque images: a survey. International Journal on Document
Analysis and Recognition (IJDAR), 15(4):267–296, 2012.
[33] A. Juan, A. H. Toselli, J. Domnech, J. González, I. Salvador, E. Vidal, and
F. Casacuberta. Integrated handwriting recognition and interpretation via
finite-state models. International Journal of Pattern Recognition and Artifi-
cial Intelligence, 18(04), 2001.
[34] Yousri Kessentini, Thierry Paquet, and AbdelMajid Ben Hamadou. Off-line
handwritten word recognition using multi-stream hidden markov models. Pat-
tern Recogn. Lett., 31(1):60–70, 2010.
Universidad Nacional de San Agust́ın - UNSA 100
BIBLIOGRAFÍA
[35] M. Khayyat, L. Lam, and C.Y. Suen. Learning-based word spotting system for
arabic handwritten documents. Pattern Recognition, 47(3):1021 – 1030, 2014.
Handwriting Recognition and other PR Applications.
[36] J. Kivinen, A. J. Smola, and R. C. Williamson. Online Learning with Kernels.
IEEE Transactions on Signal Processing, 52:2165–2176, August 2004.
[37] S. Knerr, E. Augustin, O. Baret, and D. Price. Hidden markov model based
word recognition and its application to legal amount reading on french checks.
Computer Vision and Image Understanding, 70(3):404–419, 1998.
[38] S. S. Kuo and O. E. Agazzi. Keyword Spotting in Poorly Printed Documents
using Pseudo 2-D Hidden Markov Models. IEEE Trans. Pattern Anal. Mach.
Intell., 16(8):842–848, 1994.
[39] L. Lam, C.Y. Suen, D. Guillevic, M. Cheriet N. W. Strathy, K. Liu, and J.N.
Said. Automatic processing of information on cheques. In The Proceeding of the
IEEE International Conference on Systems, Man and Cybernetics, volume 3,
pages 2353–2358, 1995.
[40] P. Laskov, C. Gehl, S. Krüger, and K.-R. Müller. Incremental Support Vector
Learning: Analysis, Implementation and Applications. J. Mach. Learn. Res.,
7:1909–1936, December 2006.
[41] F. Lauer, C.Y. Suen, and G. Bloch. A trainable feature extractor for handw-
ritten digit recognition. Pattern Recognition, 40(6):1816 – 1824, 2007.
[42] V. Lavrenko, T. Rath, and R. Manmatha. Holistic word recognition for handw-
ritten historical documents. In Proceedings of the First International Workshop
on Document Image Analysis for Libraries, pages 278–287, 2004.
[43] Y. LeCun and Y. Bengio. word-level training of a handwritten word recog-
nizer based on convolutional neural networks. In Proc. of the International
Conference on Pattern Recognition, volume II, pages 88–92, 1994.
[44] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning ap-
plied to document recognition. Proceedings of the IEEE, 86(11):2278–2324,
November 1998.
[45] S. Levy. Google’s Two Revolutions. [Online]. http://abcdefgh.livejournal.com/
438110.html. Access: 2012, Jan. 3.
[46] Y. Leydier, F. Lebourgeois, and H. Emptoz. Text search for medieval manus-
cript images. Pattern Recogntion, 40(12):3552–3567, 2007.
[47] Y. Leydier, A. Ouji, F. Lebourgeois, and H. Emptoz. Towards an omnilingual
word retrieval system for ancient manuscripts. Pattern Recognition, 42(9):2089–
2105, 2009.
Universidad Nacional de San Agust́ın - UNSA 101
BIBLIOGRAFÍA
[48] D. Liu and Y. Chen. A Courtesy Amount Recognition System for Chinese Bank
Checks. In International Conference on Frontiers in Handwriting Recognition
(ICFHR’12), pages 710–715, 2012.
[49] F.-J. López-Salcedo, G. Sanchis-Trilles, and F. Casacuberta. Online learning of
Log-linear Weights in Interactive Machine Translation. In Doroteo Torre Tole-
dano, Alfonso Ortega, António Teixeira, Joaqúın González Rodŕıguez, Luis Her-
nández Gómez, Rub́ın San-Segundo, and Daniel Ramos Castro, editors, Advan-
ces in Speech and Language Technologies for Iberian Languages (iberSPEECH
2012), pages 277–286. Springer, 2012.
[50] J. Ma, J. Theiler, and S. Perkins. Accurate On-line Support Vector Regression.
Neural Comput., 15(11):2683–2703, November 2003.
[51] U. Mahadevan and S.N. Srihari. Parsing and recognition of city, state, and
zip codes in handwritten addresses. In Proceedings of the Fifth International
Conference on Document Analysis and Recognition (ICDAR ’99), pages 325–
328, 1999.
[52] R. Manmatha, C. Han, and E. M. Riseman. Word spotting: A new approach
to indexing handwriting. In Proceedings of the 1996 Conference on Computer
Vision and Pattern Recognition (CVPR ’96), pages 631–637, 1996.
[53] R. Manmatha and J. Rothfeder. A scale space approach for automatically
segmenting words from degraded handwritten documents. Journal of Transac-
tions on Pattern Analysis and Machine Intelligence (TPAMI), 27(8):1212–1225,
2004.
[54] U.-V. Marti and H. Bunke. Using a statistical language model to improve the
performance of an HMM-based cursive handwritting recognition system. Inter-
national Journal of Pattern Recognition and Artificial Intelligence, 15(01):65–
90, 2001.
[55] M. Martin. On-Line Support Vector Machine Regression. In Tapio Elomaa,
Heikki Mannila, and Hannu Toivonen, editors, Machine Learning: ECML 2002,
volume 2430 of Lecture Notes in Computer Science, pages 282–294. Springer
Berlin Heidelberg, 2002.
[56] S. Mori, C.Y. Suen, and K. Yamamoto. Historical review of ocr research and
development. Proceedings of the IEEE, 80(7):1029–1058, 1992.
[57] X.-X. Niu and C.Y. Suen. A novel hybrid CNN–SVM classifier for recognizing
handwritten digits. Pattern Recognition, 45(4):1318 – 1325, 2012.
[58] D. Ortiz-Mart́ınez, I. Garćıa-Varea, and F. Casacuberta. Online Learning for In-
teractive Statistical Machine Translation. In Proceedings of the North American
Chapter of the Association for Computational Linguistics - Human Language
Technologies (NAACL HLT), pages 546–554, 2010.
Universidad Nacional de San Agust́ın - UNSA 102
BIBLIOGRAFÍA
[59] D. Ortiz-Mart́ınez, G. Sanchis-Trilles, F. Casacuberta, V. Alabau, E. Vidal,
J.-M. Bened́ı, J. González-Rubio, A.Sanchis, and J. González. The CASMA-
CAT Project: The Next Generation Translator’s Workbench. Proceedings of
iberSPEECH 2012, 2012.
[60] U. Pal, R.K. Roy, K. Roy, and F. Kimura. Indian multi-script full pin-code string
recognition for postal automation. In Proceedings of the 10th International
Conference on Document Analysis and Recognition (ICDAR ’09), pages 456–
460, 2009.
[61] R. Palacios and A. Gupta. A system for processing handwritten bank checks
automatically. Image Vision Computing, 26(10):1297–1313, 2008.
[62] M.K. Parshuram and S.H. Ravinda. Handwritten Marathi Character Recogni-
tion Using R-HOG Feature. Procedia Computer Science, 45:266 – 274, 2015.
International Conference on Advanced Computing Technologies and Applica-
tions (ICACTA).
[63] M. Pfister, S. Behnke, and R. Rojas. Recognition of handwritten zip codes in a
real worldnon standard letter sorting system. Applied Intelligence, 12(1-2):95–
115, 2000.
[64] J. Platt. Sequential Minimal Optimization: A Fast Algorithm for Training Sup-
port Vector Machines. Technical Report MSR-TR-98-14, Microsoft Research,
1998.
[65] D. Price, S. Knerr, L. Personnaz, and G. Dreyfus. Pairwise Neural Network
Classifiers with Probabilistic Outputs. In Advances in Neural Information Pro-
cessing Systems 7, [NIPS Conference, Denver, Colorado, USA, 1994], pages
1109–1116, 1994.
[66] F. Qi, M. Deng, M. Qian, and X. Zhu. A Novel Algorithm for Handwritten
Chinese Character Recognition. In Proceedings of the Third International Con-
ference on Advances in Multimodal Interfaces (ICMI’00), pages 379–385, 2000.
[67] L.R. Rabiner. Readings in speech recognition. chapter A tutorial on hidden
Markov models and selected applications in speech recognition, pages 267–296.
Morgan Kaufmann Publishers Inc., 1990.
[68] T. Rath, V. Lavrenko, and R. Manmatha. Retrieving historical manuscripts
using shape. MM 328, University of Massachusetts, 2003.
[69] T. Rath and R. Manmatha. Features for word spotting in historical manuscripts.
In Proceedings of the Seventh International Conference on Document Analysis
and Recognition (ICDAR ’03), pages 218–222, 2003.
[70] T. Rath and R. Manmatha. Word image matching using dynamic time war-
ping. In IEEE Computer Society Conference on Computer Vision and Pattern
Recognition, volume 2, pages 521–527, 2003.
Universidad Nacional de San Agust́ın - UNSA 103
BIBLIOGRAFÍA
[71] T. Rath and R. Manmatha. Word spotting for historical documents. Internatio-
nal Journal on Document Analysis and Recognition (IJDAR), pages 139–152,
2005.
[72] T. Rath, R. Manmatha, and V. Lavrenko. A search engine for historical ma-
nuscript images. In Proceedings of the 27th Annual International ACM SIGIR
Conference on Research and Development in Information Retrieval, pages 369–
376, 2004.
[73] Ph Refregier and F. Vallet. Probabilistic Approach for Multiclass Classification
with Neural Networks. In Proceedings of International Conference on Artificial
Networks, pages 1003–1007, 1991.
[74] M. K. Revathi, K. P. Ramya, and G. Sona. Multiview Pedestrian Detection
Based on Online Support Vector Machine Using Convex Hull . In Proceedings
of International Conference On Global Innovations In Computing Technology
(ICGICT’14), volume 2, 2014.
[75] L. G. Roberts. Machine perception of three-dimensional solids. PhD thesis,
Dept. of Electrical Engineering, Massachusetts Institute of Technology, 1963.
[76] J.A. Rodŕıguez-Serrano and F. Perronnin. Handwritten word-spotting using
hidden Markov models and universal vocabularies. Pattern Recogn., 42(9):2106–
2116, 2009.
[77] V. Romero. Multimodal Interactive Transcription of Handwritten Text Images.
PhD thesis, Universidad Politécnica de Valencia, 2010.
[78] V. Romero and M. Pastor. Multimodal Interactive Pattern Recognition and Ap-
plications, chapter Computer Assisted Transcription of Text Images. Springer,
2011.
[79] V. Romero and Luis Rodŕıguez-Ruiz. Multimodal Interactive Pattern Recogni-
tion and Applications, chapter Computer Assisted Transcription: General Fra-
mework. Springer, 2011.
[80] V. Romero, J. A. Sánchez, N. Serrano, and E. Vidal. Handwritten text recog-
nition for marriage register books. Proceedings of the International Conference
on Document Analysis and Recognition (ICDAR ’11), 0:533–537, 2011.
[81] V. Romero, A.H. Toselli, and E. Vidal. Computer assisted transcription of
text images: Results on the germana corpus and analysis of improvements nee-
ded for practical use. In Pattern Recognition (ICPR), 2010 20th International
Conference on, pages 2017–2020, 2010.
[82] K. Roy, S. Vajda, U. Pal, B.B. Chaudhuri, and A. Belaid. A system for indian
postal automation. In Proceedings of the Eighth International Conference on
Document Analysis and Recognition (ICDAR ’05), volume 2, pages 1060–1064,
2005.
Universidad Nacional de San Agust́ın - UNSA 104
BIBLIOGRAFÍA
[83] I. Sánchez-Cortina. Advances in Interactive Speech Transcription. Master’s the-
sis, Departament de Sistemes Informátics (DSIC) de la Universitat Politécnica
de Valéncia (UPV), 2012.
[84] M. I. Shah and C. Y. Suen. The Present State and Role of Word Spotting
Techniques in Document Analysis and Retrieval - A Comprehensive Survey,
pages 353–376. World Scientific Publishing, 2010.
[85] F. Simistira, V. Katsouros, and G. Carayannis. Recognition of online handw-
ritten mathematical formulas using probabilistic SVMs and stochastic context
free grammars. Pattern Recognition Letters, 53:85 – 92, 2015.
[86] R. C. S. N. P. Souza, S. C. Leite, C. C. H. Borges, and R. F. Neto. Online algo-
rithm based on support vectors for orthogonal regression. Pattern Recognition
Letters, 34(12):1394 – 1404, 2013.
[87] O. Surinta, M. F. Karaaba, L. R. B. Schomaker, and M.A. Wiering. Recognition
of handwritten characters using local gradient feature descriptors. Engineering
Applications of Artificial Intelligence, 45:405 – 414, 2015.
[88] N. A. Syed, H. Liu, and K. K. Sung. Handling Concept Drifts in Incremental
Learning with Support Vector Machines. In Proceedings of the Fifth ACM
SIGKDD International Conference on Knowledge Discovery and Data Mining,
KDD ’99, pages 317–321, New York, NY, USA, 1999. ACM.
[89] H. Tang, E. Augustin, C. Y. Suen, O. Baret, and M. Cheriet. Recognition of
unconstrained legal amounts handwritten on chinese bank checks. In Procee-
dings 17th International Conference on Pattern Recognition (ICPR’04), pages
610–613, 2004.
[90] A. H. Toselli, V. Romero, M. Pastor, and E. Vidal. Multimodal interactive
transcription of text images. Pattern Recognition, 43(5):1814–1825, 2010.
[91] E. Vidal, L. Rodŕıguez, F. Casacuberta, and I. Garćıa-Varea. Interactive pattern
recognition. In A. Popescu-Belis, S. Renals, and H. Bourlard, editors, Machine
Learning for Multimodal Interaction, volume 4892 of Lecture Notes in Computer
Science, pages 60–71. Springer Berlin Heidelberg, 2008.
[92] A. Vinciarelli, S. Bengio, and H. Bunke. Offline Recognition of Unconstrained
Handwritten Texts Using HMMs and Statistical Language Models. IEEE Trans.
Pattern Anal. Mach. Intell., 26(6):709–720, 2004.
[93] Di Wang, Hong Qiao, Bo Zhang, and Min Wang. Online support vector machine
based on convex hull vertices selection. IEEE Trans. Neural Netw. Learning
Syst., 24(4):593–609, 2013.
[94] T.-F. Wu, C.-J. Lin, and R.C. Weng. Probability Estimates for Multi-class Clas-
sification by Pairwise Coupling. J. Mach. Learn. Res., 5:975–1005, December
2004.
Universidad Nacional de San Agust́ın - UNSA 105
BIBLIOGRAFÍA
[95] X. Yao and Y. Lu. A post-processing approach to chinese address recognition.
In Proceedings of the Eighth International Conference on Fuzzy Systems and
Knowledge Discovery (FSKD), volume 3, pages 1906–1910, 2011.
[96] X. Zhou, X. Zhang, and B. Wang. Online Support Vector Machine: A Survey.
In Joong Hoon Kim and Zong Woo Geem, editors, Harmony Search Algorithm,
volume 382 of Advances in Intelligent Systems and Computing, pages 269–278.
Springer Berlin Heidelberg, 2016.
Universidad Nacional de San Agust́ın - UNSA 106