61490306 - Lecture notes 1 PDF

Preview

Summary

DESC...

Description

Científica ISSN: 1665-0654 [email protected] Instituto Politécnico Nacional México

Toscano Medina, Karina; Nakano Miyatake, Mariko; Sánchez Pérez, Gabriel; Pérez Meana, Héctor M.; Yasuhara, Makoto Reconocimiento de caracteres manuscritos usando la función spline natural Científica, vol. 9, núm. 3, 2005, pp. 143-154 Instituto Politécnico Nacional Distrito Federal, México

Disponible en: http://www.redalyc.org/articulo.oa?id=61490306

Cómo citar el artículo Número completo Más información del artículo Página de la revista en redalyc.org

Sistema de Información Científica Red de Revistas Científicas de América Latina, el Caribe, España y Portugal Proyecto académico sin fines de lucro, desarrollado bajo la iniciativa de acceso abierto

©

Científica

V ol. 9 N úm. 3 pp. 143-1

2005 ESIME-IPN. ISSN 1665-0654. Impreso en Méx

Reconocimiento de caracteres manuscritos usando la función spline natural Karina Toscano-Medina1 Mariko Nakano-Miyatake1 Gabriel Sánchez-Pérez1 Héctor M. Pérez-Meana1 Makoto Yasuhara2 Sección de Estudios de Posgrado e Investigación (SEPI), Escuela Superior de Ingeniería Mecánica y Eléctrica (ESIME), Unidad Culhuacán, Instituto Politécnico Nacional. Av. Santa Ana 1000, Col. San Francisco Culhuacán, CP 04430, Del. Coyoacan, México, DF. MÉXICO 2 University of Electro-Communications. Chofugaoka 1-5-1, Tokyo, Japan. JAPÓN 1

trazos, se determina a cual caracter pertenece los p significativos del caracter de entrada. La taza de re cimiento global del sistema propuesto es aproximadam de 96.0%.

2. Abstract (Handwriting Character Recognition Sys using Natural Spline Function)

During last two decade, numerous handwriting char recognition systems have been proposed. Many of presented their limitation when the handwriting chara cursive type and it has some deformation. However thi of cursive characters is easily recognized by the human b In this paper we research its human ability and apply the dynamic handwriting character recognition. I proposed system, significant knots of each characte extracted using natural Spline function named SLALOM their position is optimized Steepest Descent Method. optimal knots of the training set, character’s mode email: [email protected] constructed. The optimal knots of an unknown character are compared with each model of all chara Recibido el 7 de junio de 2004; aceptado el 18 de febrero de 2005. and it is classified to one group of character with max similitude score. The recognition stage consists in twoclassification using global feature and classification 1. Resumen local feature. The global recognition rate after two recognition stage in the proposed system is approxim Durante las últimas dos décadas se han propuesto una gran 96.0%. cantidad de sistemas para el reconocimiento de caracteres manuscritos. Sin embargo aún existen varias limitaciones Palabras clave: reconocimiento de caracteres manusc relativas a su funcionamiento y porcentaje de reconocimiento, reconocimiento en línea, función spline natural, méto sobre todo cuando los caracteres manuscritos son de tipo Slalom, método de búsqueda gradiente, longitud mínim cursivo. Para reducir este problema, en este artículo se propone descripción. un nuevo algoritmo de reconocimiento dinámico de caracteres manuscritos de tipo cursivo. En el algoritmo propuesto, los 3. Introducción puntos significativos para cada caracter se estiman usando una función spline natural llamada Slalom. Posteriormente, El reconocimiento convencional de caracteres manus partiendo de los puntos significativos se construye un modelo está basado en la extracción de características a partir para cada caracter. En la etapa de reconocimiento, los puntos forma particular del caracter bajo análisis, tales com significativos de un caracter de entrada desconocido se inclinación de las líneas, la posición relativa de cada lín comparan con los modelos de cada uno de los caracteres ancho de las diferentes partes de la línea, etc. [1]. Este m existentes para identificar el caracter de entrada. La etapa de de reconocimiento se puede usar para reconocer cara reconocimiento consiste de dos niveles de clasificación. En manuscritos en letra de molde (no cursivo) de una m la primera etapa se agrupan las letras parecidas, mientras que eficiente. Sin embargo, para el reconocimiento de cara en la segunda etapa, usando las características locales de los cursivos, éste no es eficiente.

Científica

Una razón por la cual los seres humanos pueden leer y entender los caracteres cursivos (muy aerodinámicos o deformados) es porque tenemos la habilidad de trazar mentalmente, varias veces la letra en el orden en que fue escrita. Cuando una persona escribe un caracter, generalmente realiza los siguientes 4 pasos: 1) Tener en mente el símbolo que se va a escribir. 2) El orden de los movimientos del caracter a escribir. 3) La realización del trazo. 4) La imagen del caracter. El proceso de generación del caracter se realiza del paso 1 al 4, mientras el proceso de reconocimiento puede ser realizado en orden inverso al de la generación, esto es del 4 al 1. Sin embargo la realización de este proceso inverso es sumamente difícil. Los sistemas de reconocimiento se dividen en dos categorías: sistemas en línea y sistemas fuera de línea [1]. En los sistemas en línea se requiere de la presencia física de la persona que realiza el trazo de un caracter; de aquí que se utilicen características como la inclinación del bolígrafo, la velocidad del trazo, la secuencia de direcciones tomadas por el trazo, los momentos gráficos, entre otras[1]. Los procesos de reconocimiento de caracteres manuscritos en línea equivalen a realización de los procesos inversos del 3 a 1, mientras los procesos de reconocimiento fuera de línea equivalen a los procesos inversos completos de 4 a 1. Por lo tanto se puede decir que el reconocimiento en línea es una parte del proceso inverso completo del reconocimiento fuera de línea de caracteres manuscritos. Hasta la fecha se han propuestos varios sistemas para realizar el reconocimiento de caracteres manuscritos en línea, por ejemplo, Manke y Bodenhausen [2] realizaron una investigación proponiendo una solución conexionista para el problema del reconocimiento de la escritura cursiva y del caracter aislado. Ellos proponen a la MS-TDNN (red neuronal de retraso en tiempo con estados múltiples) el cual integra a la red TDNN (red neuronal de retraso en tiempo) con un procedimiento de alineación no lineal en tiempo, para encontrar los movimientos y los límites tanto de los caracteres aislados como de las palabras; para posteriormente llevar a cabo el reconocimiento. Las palabras manuscritas se pueden representar como una secuencia de tiempo, la velocidad y la presión variante en cada coordenada. El problema principal de reconocer palabras continuas es que los caracteres o los límites del movimiento no son conocidos y se debe encontrar una alineación de tiempo óptima. El reconocedor conexionista, integra el reconocimiento y la segmentación dentro de una sola arquitectura de red MS-TDNN, que fue propuesta originalmente para las tareas del reconocimiento del habla continuo.

Nakatani et al. [3] propusieron un sistema de reconocim en línea para caracteres manuscritos en hiragana usan modelo de AR complejo. El sistema fue evaluado po escritores, quienes evaluaron el funcionamiento del si cambiando los valores de los parámetros usados en el m de AR. El funcionamiento de reconocimiento al que se después de adecuar los valores de los parámetros del si fue de aproximadamente 98 %. Plamondon y Maarse [4] propusieron el estudio de la esc desde el programa motor del cerebro que es donde se p lo que se quiere escribir, después se transmite esta inform a los nervios, posteriormente los movimientos del músc activan, para finalmente trazar la trayectoria en una t digitalizadora. De esta manera, se lleva a cabo la escritu embargo los autores querían determinar que caracterís variable debe ser controlada para llevar a cabo el proce forma inversa, desde la trayectoria de la escritura en la t digitalizadora hasta el programa motor del cerebro. Los au haciendo pruebas, llegaron a la conclusión de que usan teoría de la transformada de Laplace y los modelos lin hasta de segundo orden usando la velocidad como va de control es posible realizar el proceso inverso. Mezghani et al. [5] propusieron un sistema de reconocim de caracteres arábigos usando redes neuronales de Koh Aquí de la información dinámica de las letras arábig extrajeron los coeficientes de Fourier elípticos. Los a evaluaron el sistema usando 18 letras arábigas, trazan escritores cada letra 24 veces construyendo así 7400 t Los resultados de reconocimiento varían dema dependiendo de la letra (desde un 40% hasta un 2% de e debido a la similitud existentes entre las diferentes letr reconocimiento global para solo un escritor es de apro damente 88%. Sin et al. [6] propusieron un sistema combinado de mo ocultos de markov (HMM) y programación dinámica p reconocimiento de caracteres tipo cursivo. El sistema re tanto la segmentación de cada caracter dentro de la p como el reconocimiento del caracter segmentado usan mismo HMM. El funcionamiento del sistema para cara (alfabeto inglés) escritos dentro de una región establec de aproximadamente 91%. Este artículo se enfoca en la realización de los pro inversos de escritura mencionados anteriormente des paso (3) al paso (1). Aquí la realización del paso (3) al pa está basada en una aproximación por medio de la fu spline natural, mediante la cual es posible obtener el ord movimiento requerido para realizar el trazo del caracter a de los datos capturados en tableta digitalizadora, mi

Científica

α

que la realización del paso (2) al paso (1) se lleva a cabo mediante la creación de modelos y cálculo de similitud entre los modelos y los datos obtenidos del caracter a analizar.

donde

Este artículo está organizado de la siguiente manera: en la sección 1 se describió la metodología para atacar el problema del reconocimiento de caracteres cursivos y los principales trabajos reportados en la literatura. En la sección 2, se explica brevemente el método de Slalom que juega un papel importante en el sistema propuesto, el sistema propuesto se describe detalladamente en la sección 3. En la sección 4, los resultados obtenidos por simulación computacional son mostrados y finalmente las conclusiones de este artículo se proporcionan en la sección 5.

El valor de la primera derivada de la función g(t) correspon al i+1-ésimo nodo en manera discreta, lo podemos escri

es un factor en el intervalo [0,1] que determ

peso o importancia de las

condiciones

anteriorm

mencionadas.

'

g i+ 1 =

gi +1 − gi ti +1 − ti

=

gi +1 − gi ∆

donde: ∆ es el intervalo entre el i-ésimo nodo y el i+1nodo, y de manera similar el valor de la segunda derivad el i+1-ésimo nodo está dada por:

4. Desarrollo 4.1 Método de Slalom

''

g i+ 1 =

g 'i+1 − g i' ti+1 − ti

El método de Slalom fue desarrollado como un método de cuantificación inversa para señales o imágenes [7]. Usando Suponiendo que los intervalos de los dos nodos consecu este método, partir de los datos muestreados f1, f2, ..., fM en son iguales, la ecuación (5) se puede escribir como: tiempo t1, t2, ..., tM (t1 < t2 < ... < tM ) se puede obtener una g − gi g − gi −1 g 'i+1 = i +1 g 'i = i función suave y continua g(ti). Por lo tanto el método de ∆ ∆ Slalom se puede considerar como un método para generar una función spline natural. El método de Slalom obtiene una función g(ti) que cumple las dos condiciones siguientes: Sustituyendo la ecuación (6) en (5), obtenemos: 1. La diferencia entre g(ti) y fi debe ser menor que un valor g’’i + 1 = 1/∆ (gi+ 1 − gi)−(gi − gi−1) aceptable δ. ∆ 2. La función g(ti) debe ser una función suave y continua. = (gi+ 1 − 2gi + gi−1) ∆2 Sin embargo estas dos condiciones no se pueden satisfacer fácilmente de manera simultánea ya que, para que la función g(ti) sea suave, la diferencia entre valores de g(ti) y fi no se Suponiendo que ∆ es igual a 1, se obtiene: puede mantener en cero. El grado de suavización de la función g’’ = g - 2g + g g(t) se determina por medio de la función J[g] dada en ecuación (1).

}/ ]

[{

/

i + 1

i+ 1

i

i-1

El primer término de la ecuación (3) en forma discre d2 J [g] =m( 2 g(t))2 dt dx

(1)

Σ(g ’’(t)) , por lo cual ésta se puede rescribir usando la 2

i

ción (8) como M

N−1

Cuando la ecuación (1) se minimiza, la función aproxima a una función más suave. La primera condición se puede escribir como se indica en la ecuación (2) |g(t) - f | < i

donde

δ es

δ

para

i = 1, 2, …, M

(2)

un valor aceptable de error. Así para satisfacer

las dos condiciones de manera simultanea, se define una función J’[g] como: [8,9],

2

M  d2  J ' [ g ] = ∫  2 g ( t )  dt + α ∑ ( g ( ti ) − fi  dx  i= 1  

)2 dx

J’[g] = Σ (gi+ 1 − 2gi + gi−1)2 + αΣ (gji − fi)2 i=1

j=2

donde N (>M) es el número de nodos para estimar la fu g(t) y M es el número de muestras, gi es el valor de la imuestra de la función Spline g y gji es el valor del jinodo. El problema de minimizar J’[g] se puede resolver u la condición de que la derivada parcial de J’[g] con resp gk, sea igual a cero.

(3) o sea:

MJ’ = 0, Mgk

k = 1, ..., N

Científica Así el primer término de la ecuación (9) queda de la siguiente El segundo término de la ecuación (9) se resuelve u manera: método de búsqueda de gradiente. En el sistema prop N−1 se consideró que la condición de ser una función su A = Σ (gj−1 − 2 gj + gj+1)2 diferencia entre g y f mínima tenga el mismo peso, por lo j=2 el valor a es igual a 1. La ecuación (15) muestra la soluc = (g1 − 2g2 + g3)2 + (g2 − 2g3 + g4)2 + (g3 − 2g4 + g5)2 + ... (11) la ecuación (10) en el segundo término de la ecuación ( 2 2 ... + (gN−3 − 2gN−2 + gN−1) + (gN−2 − 2gN−1 + gN)

Las derivadas parciales de la ecuación (11) se determinan de la siguiente manera:

g(n) = g(n − 1) − λ [MS/ Mg(n − 1)] M

donde S = Σ (gj − fi)

∂J ' = 2( g1 − 2 g 2 + g 3 ) + 2 αδ1, Ω ( g1 − f1 ) = 0 ∂g1

i=1

∂J ' = 2(− 2 g 1 + 5 g 2 − 4 g 3 + g 4 ) + 2αδ 2,Ω ( g 2 − f 2 ) = 0 ∂g2

i

g(n) es la función g en tiempo n de adaptación.

4.2 Sistema propuesto

∂ J' = 2( g1 − 4 g2 + 6 g3 − 4 g4 + g5 ) + 2 αδ3, Ω( g3 − f3 ) = 0 ∂g3

La figura 1 muestra una forma esquemática del si propuesto, el cual realiza el reconocimiento de cara manuscritos a partir de su trazo u orden de su articul ∂J ' Aquí el trazo se captura por medio de una tableta digitaliz = 2(g N −4 − 4g N −3 + 6g N −2 − 4g N −1+ g N ) ∂ g N −2 generando posteriormente los datos de dichos caracteres. + 2αδ N − 2,Ω (g N − 2 − f N − 2 )= 0 datos generados se emplean para encontrar las caracter propias de cada caracter manuscrito, por medio d ∂J ' = 2(− 2g N −3 + 5g N −2 − 4g N −1 + g N ) preprocesamiento que consiste de filtraje y normalizació ∂ g N −1 permita posteriormente realizar la extracción de caracter + 2αδ N −1,Ω (g N −1 − f N −1 ) = 0 en la que se estiman los nodos significativos usando el m de Slalom. Finalmente el reconocimiento se realiza por ∂J ' = 2( g N − 2− 2 g N − 1+ g N ) de la construcción de los modelos de caracteres. Con e ∂gN (12) las características extraídas del caracter de entrada se em + 2αδ N ,Ω ( gN − fN ) = 0 para construir un modelo el cual se compara con los mo de todos los caracteres existentes, calculándose el gra Para obtener el valor de gk, k = 1, 2, …, N, hay que resolver el similitud entre éstos para identificar así al caracter de en siguiente sistema lineal: Cada etapa del sistema propuesto se mencionará detalladam ...

1 −2 1 −2 5 −4 1 1 −4 6 −4 1 ... 1 −4 6 −4 1 1 −4 5 −2 1 −2 1

g1 g2 g3 ... = gN-2 gN-1 gN

αδ1,Ω (f1 − g1) αδ2,Ω (f2 − g2) αδ3,Ω (f3 − g3) ... αδN-2,Ω (fN-2 − gN-2) αδN-1,Ω (fN-1 − gN-1) αδN,Ω (fN − gN)

4.2.1 Adquisición de datos

Los datos de la escritura se obtienen por medio de la t digitalizadora y la pluma o lápiz ergonómico Intuo Wacom, con la cual los escritores trazan los caracteres la tableta digitalizadora conociendo así el orde articulación de cada caracter. La tableta arroja la imag lo que se escribe en el monitor, así como también los donde Ω es el espacio de muestreo y δj, Ω se puede representar de acuerdo al orden de articulación como se escrib como: caracter. La figura 2 muestra los datos adquiridos de l 0 j0Ω 'h' y sus señales en los ejes x, y. δj,Ω = 1 j 0 Ω (14)

{

δj,Ω = 0, cuando el nodo j-ésimo no corresponde a un tiempo de muestreo y δj,Ω = 1, cuando el nodo j-ésimo es un tiempo de muestreo. Para resolver la ecuación (13), no se puede usar el método tridiagonal, debido a la forma de la matriz, por lo que se usa el método de eliminación gaussiana.

4.2.2 Construcción de base de datos Se construye una base de datos de caracteres manus con la tableta digitalizadora. Se tomó en cuenta a 26 le caracteres del alfabeto inglés realizado 100 veces cada ca con 3 escritores, por lo que, la base de datos cuenta con

Científica

Adquisición de datos por medio de la tableta digitalizadora y construcción de base de datos

Preprocesamientos (Normalización en tamaño, posición y tiempo)

Extracción de características (nodos óptimos) usando el método de Slalom

Construcción de modelos de caracteres

Reconocimiento de caracteres manuscritos usando el modelo del caracter

Fig. 1. Sistema propuesto.

datos. De aquí se toman 4 680 datos para la creación del Fig. 3. Ejemplos de letras que forman en bases de datos. modelo de cada caracter, lo que equivale a 60 veces cada caracter y 3120 datos para la prueba, que son 40 veces cada caracter. La figura 3 muestra algunos de los caracteres (a,n,m,o) 4.2.4 Filtraje que forman parte de la base de datos. Para eliminar los componentes de alta frecuencia produ por la vibración de la mano, se aplica un filtro pasa ba señal de trazo en eje-x y en eje-y. En este artículo se util Los datos capturados varían en tamaño, posición y la filtro Butterworth con orden 5. La figura 4 muestra el velocidad de escritura. Estas variaciones afectan a una original y el trazo filtrado. extracción de características adecuada. Además de las variaciones geométricas mencionadas, generalmente los datos 4.2.5 Normalización capturados contienen componentes de alta frecuencia introducidos por una vibración pequeña de la mano a la hora Después de que realiza un filtraje pasa bajas, la letra fi de la escritura. Como preprocesamientos, se realizan el filtraje se normaliza en posición, en tamaño y en tiempo. La n y la normalización en posición, tamaño y tiempo. lización en posición y en tamaño se realiza aplicando la formada Affine, mientras que la normalización en tiem

4.2.3 Preprocesamiento

(a)

(b) (a)

Fig. 2. Los datos capturados partir del trazo de la letra 'h', (a) trazo realizado, (b) señales en eje-x y en eje-y.

Fig. 4. (a) Trazos original de la letra 'e' y (b) el trazo filtrado de (a).

(b)

Científica

(a)

(b)

Fig. 5. (a) Trazo original, (b) trazo después del filtrado y normalización.

(a) realiza usando interpolación y decimación. La figura 5 muestra el trazo original y el trazo filtrado y normalizado tanto en tamaño como en posición y en tiempo.

4.2.6 Extracción de características El proceso de extracción de c...