OCR para caracteres impresos basados en Árboles Binarios

El OCR (Optic Character Recognition), trata como su propia definición indica, del reconocimiento óptico de caracteres, es decir, conseguir sacar de una imagen el texto que en ella se encuentre y ser capaz de pasarlo a cualquier formato de texto.

Existen multitud de técnicas de OCR, basadas en estadísticas, en las formas de los caracteres, transformadas y en comparaciones. Otra nueva propuesta es usar las características especiales que tienen los caracteres escritos por ordenadores, para detectarlos.

Nuestro proyecto parte de un documento cuyo título es “A Binary-Tree-Based OCR Technique for Machina-Printed Characters“, elaborado por “B.Gatos”, “N.Papamarkos” y “C.Chamzas”de 1997, es decir usaremos una técnica basada en la creación de un árbol binario, para la detección de texto impreso (solo tomaremos texto impreso por computadoras, no texto escrito a mano).

Para realizarlo necesitaremos de varios pasos:

· Preprocesamiento

· Extracción de características

· Construcción del árbol, usando la entropía

· Comparación de patrones

Uno de los pasos más difíciles es la extracción de las características, ya que es de gran dificultad elegir un conjunto óptimo de características. En general para que una característica sea buena debe tener:

a) Discriminación: Deben ser características que diferencien suficientemente una clase de otra

b) Deben tener igual valor para mismas clases

c) Independencia: Las características deben estar incorreladas unas de otras

d) Pequeño espacio para características: El número de características debe ser pequeño para la rapidez y facilidad de clasificación

Además las características deben contar con otros requerimientos como son que tengan un bajo gasto computacional, tanto en tiempo como en complejidad. Debido a estos motivos es muy difícil conseguir unas características óptimas.

Por otro lado algunos OCR usan características continuas, que tienen el problema de que son muy sensibles al ruido y discriminan en un grado muy bajo. Por eso usamos características binarias (en realidad usamos algunas discretas y luego las pasamos a binarias).

Las características binarias poseen dos aspectos muy importantes:

a) Alto nivel de discriminación: El hecho de que un carácter tenga un agujero o no es vital en la discriminación.

b) Exactitud de las determinaciones: No nos interesa saber exactamente donde están los puntos finales, sino que nos basta con saber si tiene o no. Con lo que lo hacemos poco sensible al ruido.

Nota: En cada capítulo hemos añadido un apartado de implementación indicando como se ha realizado esta en el programa.

2. Arquitectura General del Sistema

En este capítulo vamos a tratar de explicar a grandes rasgos que es en lo que se basa esta técnica, y por lo tanto lo que realiza nuestro programa.

Existen dos partes diferenciadas en esta técnica, por un lado hay una parte de aprendizaje en la que nuestro árbol aprende patrones y crea el árbol (Fig.1) y otra en la que teniendo ya el árbol construido recorremos el árbol y reconocemos caracteres (Fig. 2)

Partimos de un papel impreso con caracteres provenientes de cualquier procesador de textos convencional (a). El primer paso obvio es escasearlo con un escáner y obtener un archivo de imagen (b) (en cualquier formato: bmp, jpg, …) .

Ahora necesitamos buscar donde está el texto dentro de la imagen, identificar las líneas de texto, y segmentar esas líneas en caracteres (c).

Tenemos un trozo de imagen donde tenemos un carácter, ahora necesitamos normalizar este carácter, es decir adelgazarlo (que el grosor de la línea sea igual a 1), y reducirlo a una ventana de 16x16, para su posterior estudio.

Una vez normalizado solo tenemos que ir obteniendo características del carácter para su posterior identificación. (d).

Hasta aquí todos los pasos son comunes tanto para el aprendizaje como para el reconocimiento.

I. Aprendizaje (Fig. 1):

Construimos el árbol binario (e) a partir de todos los patrones que tenemos guardados, y del actual que se está introduciendo. Para su construcción usamos la entropía de las características, es decir calculamos cual de todas las características discrimina en grupos más heterogéneos y usamos esa para el primer nodo del árbol.

Así operaremos sucesivamente, hasta que tengamos creado el árbol. Después de esto solo queda guardarlo (g).

II. Recorrido (Fig. 2):

Recorremos el árbol según las características del carácter a reconocer.

Si durante el recorrido llegamos a una hoja del árbol, reconocemos el carácter.

Si no llegamos a una hoja, aprendemos ese carácter, y añadimos el patrón a nuestro árbol

3. Preprocesamiento

Para que el proceso de OCR funcione correctamente, se debe realizar en la imagen un buen preprocesamiento de la imagen para su posterior estudio. En este preprocesamiento incluimos:

o Selección del contraste y brillo óptimos: Para que no aparezca demasiado ruido y que a la vez el texto se diferencie lo suficiente del fondo.

o Rotar la imagen: Para tener líneas rectas.

o Segmentar la imagen: Cortar cada carácter y desechar los espacios en blanco es fundamental para poder estudiar los caracteres individualmente.

o Normalizar la imagen: Para trabajar siempre con las mismas dimensiones, ya que algunas características podrían variar, además del posible aumento del tiempo computacional.

3.1.-Selección del brillo y contraste óptimos

El primer pasa es graduar el brillo y contraste de la imagen para que no exista mucho ruido y exista suficiente distinción entre el texto y el fondo.

Para ello se utiliza una técnica basada en el histograma de la imagen, en la que se aproxima mediante una función racional y el algoritmo de minimización de Goleen (Papamarkos et al., 1988)

En primer lugar se determinan los picos del histograma, calculando los máximos locales que en el existen. A continuación aproximamos el valle (región entre dos picos) mediante una función racional y el criterio de mínimos y máximos.

Por último se aplica a cada valle el algoritmo de Golden para calcular el brillo y contraste idóneos

3.2.-Rotar la imagen

Rotar para quitar la rotación al documento así como inclinaciones. Esto se realiza con un método basado en la correlación entre los píxeles de las líneas verticales. (Gatos et al.,1995)

Después de este método todos los caracteres tendrán aproximadamente la misma orientación.

3.3.-Segmentar la imagen

Segmentar los caracteres del fondo, asumiendo que se puedan separar en bloques blancos y caracteres. También se usa una técnica de separado de caracteres que están en contacto.(E.Wahletal.(1982)).

3.4.-Normalizar la imagen

Se usa una técnica de normalizado que escala la imagen a una ventana de 16x16. El valor de escala dependerá del tamaño original de la imagen aunque a pesar de esto, el valor de las posiciones relativas de los píxeles de la imagen no cambiará, incluso si existe ruido.

También se realiza un adelgazamiento de la imagen, es decir se obtienen líneas de grosor un píxel, para su buen reconocimiento.

3.5.-Añadidos

Además de los procesamientos que nos han sido indicados en el artículo hemos añadido un par de ellos que nos han parecido útiles.

3.5.1.-Paso a blanco y negro

Aunque normalmente los textos no suelen venir en colores, nos ha resultado útil el hecho de obtener una imagen en la que los píxeles fueran blancos o negros exclusivamente.

Para ello hemos recorrido la matriz de la imagen y para cada píxel hemos realizado una aproximación de su color o a blanco o a negro.

3.5.2.-Eliminación de algunos Puntos de árbol y Puntos finales

Encontramos muchas imágenes en la que las normalizaciones que se realizaban con algoritmos estándar, no funcionaban correctamente y debido a eso el número de puntos de árbol y finales se disparaban. Debido a esto realizamos un pequeño algoritmo que corregía estos casos indeseables. (Está explicado con más detalle en la parte de implementación)

3.6.2.-Eliminación de algunos Puntos de árbol y Puntos finales

Este método calcula los puntos finales y de árbol. Cuando están calculados comprueba si se ha dado algún caso excepcional (puntos de árbol adyacentes unos a otros) y si es así busca el real (o por máximo numero de píxeles adyacentes o por centridad respecto los demás puntos de árbol) y elimina todos los demás (adyacentes)

4. Extracción de características

Se ha tomado un total de 34 características binarias.

4.1. Transiciones verticales y horizontales

Se basa en calcular los ejes de nuestra imagen normalizada. Para ello basta con tomar el tamaño del eje de las “x” y dividirlo entre 2, y realizar lo mismo con el de las “y”. Ahora solo hay que recorrer los ejes y contar el número de transiciones que existen.

El número de contactos se calcula dividiendo entre 2 el número de transiciones.

Las características binarias serán:

Característica 1:

Verdadero: si el numero de contactos con el eje “x” es menor que 2.

Falso: en cualquier otro caso.

Característica 2:

Verdadero: si el numero de contactos con el eje “x” es igual que 2.

Falso: en cualquier otro caso.

Característica 3:

Verdadero: si el numero de contactos con el eje “y” es menor que 2.

Falso: en cualquier otro caso.

Característica 4:

Verdadero: si el numero de contactos con el eje “y” es igual que 2.

Falso: en cualquier otro caso.

4.2.-Agujeros

La segunda característica que vamos a tratar es si existen agujeros en la imagen. Esta característica es muy importante ya que divide muy claramente la imagen dentro de una clase u otra. Además es una característica que no depende de la escala, ni de la rotación. Además ni siquiera requiere del adelgazamiento de la imagen.

Para esto hemos utilizado el método de etiquetado de componentes blancos explicado en los temas 1 y 2 de los apuntes de esta asignatura.

Una vez obtenidos los componentes, el numero de agujeros será el numero de componentes menos 1 (la componente exterior).

Característica 5:

Verdadero: si el numero de agujeros es igual a 0.

Falso: en cualquier otro caso.

Característica 6:

Verdadero: si el numero de agujeros es igual a 1.

Falso: en cualquier otro caso.

4.3.-Puntos finales y puntos de árbol

A groso modo los puntos finales son aquellos donde se ha acabado de escribir y los puntos de árbol son aquellos donde un píxel se ramifica.

Para su cálculo se examinan las 8 adyacencias de cada píxel y según este dato se determina si son punto de árbol, finales, o nada.

Si el número de píxeles adyacentes con valor negro es igual a 1, entonces será un punto final. Por otro lado si este numero es mayor o igual a 3 será un punto de árbol.

A continuación usamos un acumulador para obtener los puntos predominantes de los puntos de árbol y finales (explicado en el capitulo 8), y obtenemos las características:

Característica 7 + n:

Verdadero: si el numero de puntos finales es igual a “n”.

Falso: en cualquier otro caso.

Para valores de n = 0, 1, 2, 3

Característica 10 + n:

Verdadero: si el numero de puntos de árbol es igual a “n”.

Falso: en cualquier otro caso.

Para valores de n = 0, 1, 2, 3

Característica 13 + n:

Verdadero: Si para cada punto final predominante existe un punto final dentro del rango de las 8 adyacencias (este valor ha sido el que hemos tomado pudiendo tomar cualquier otro)

Falso: en cualquier otro caso.

Para valores de n = 1, 2, 3, 4, 5, 6

Característica 19 + n:

Verdadero: Si para cada punto de árbol predominante existe un punto de árbol dentro del rango de las 8 adyacencias (este valor ha sido el que hemos tomado pudiendo tomar cualquier otro)

Falso: en cualquier otro caso.

Para valores de n = 1, 2, 3, 4, 5, 6

El algoritmo lo que realiza es un recorrido por la imagen, y cada vez que encuentra un píxel con color negro, inspecciona sus 8 adyacencias, y comprueba si es un punto final o de árbol. Si lo es, los añade a un vector denominado Tree[] o End[], donde almacenamos los puntos para su posterior uso.

4.4.-Perímetro

Para cada carácter calculamos el perímetro exterior. Una vez calculado usamos un acumulador y obtenemos los 6 puntos predominantes (Capitulo 8).

De aquí sacamos las características:

Característica 25 + n:

Verdadero: Si para cada punto del perímetro predominante existe un punto del perímetro dentro del rango de las 8 adyacencias (este valor ha sido el que hemos tomado pudiendo tomar cualquier otro)

Falso: en cualquier otro caso.

Para valores de n = 1, 2, 3, 4, 5, 6

Para el cálculo del perímetro externo, hacemos lo siguiente:

I. Buscamos el primer píxel que tenga color negro, empezando por la parte superior-derecha de la imagen.

II. Dentro de la función tenemos una variable que se llama “dirección” que nos indica el siguiente punto que vamos a inspeccionar. Una vez encontrado el primer punto negro la dirección apuntara hacia arriba.

III. Rotamos la dirección en el sentido de las agujas del reloj hasta que encontremos un píxel negro.

IV. Lo añadimos al perímetro

V. Ponemos el valor de la dirección totalmente a la izquierda y volvemos a girar hasta encontrar un punto negro.

VI. …

VII. …

VIII. Si volvemos al primer punto negroà Fin

4.5.-Posición Relativa

Para esta característica necesitamos tener el texto sin segmentar. Consiste en que se divide la línea en tres alturas distintas, y dependiendo para cada carácter si tiene o no algún píxel dibujado en esa línea, se establecen las siguientes características:

Característica 31 + n:

Verdadero: Si alguna parte del carácter se encuentra dentro de la zona

Falso: en cualquier otro caso.

Para valores de n = 1, 2, 3

5. Construcción del árbol

Una vez obtenidas las características del carácter, tenemos que construir el árbol binario. Para la óptima construcción del árbol necesitamos un criterio para seleccionar en cada nodo si hace falta extenderlo o no. El criterio que se establece en cada nodo, es el de la característica que posea mayor poder de discriminación.

La información obtenida está definida por la reducción de la entropía de Shannon.

Si Nk es el numero de patrones de la clase”k” del carácter a aprender en un nodo concreto, la entropía viene dada por:

E = -∑ (nk/N) * log2 (nk/N)

Donde N = n1 + n2 + … + nk y K es el número de clases.

Si E1 y E2 son las entropías calculadas de dos grupos de patrones M y N-M que han sido creados basados en una característica concreta, entonces la información obtenida para esta característica es:

I = E – (ME1/N) – ((N-M)*E2) / N

Por último para saber si seguimos extendiendo o no, lo que se hace es simplemente comprobar cuando no existe ninguna característica que pueda discriminar en ese nodo.

6. Comparación de patrones

Cuando llegamos a un nodo del árbol binario es posible que tengamos más de una clase de carácter en este nodo. Con ello nos surge el problema de ¿Cuál elegir?

Para clasificar los caracteres que nos lleguen a este nodo, en una de las clases, se usa la comparación de patrones.

Para ello se obtiene de los patrones información procedente de las 8 líneas de dirección de la matriz del carácter (horizontal, diagonal y vertical). Se aquí obtenemos 8 números binarios.

Definimos en cada nodo terminal, para cada clase:

n el número de patrones

λ λ será el entero del patrón k

i i

μi El entero del carácter de entrada a reconocer

El carácter de entrada es reconocido si la distancia Euclidea mínima es menor que el valor de umbral tomado.

Entonces la distancia del carácter hasta una clase particular será:

D = min ∑∑ |Mij-Lkij | , k=1...n|

donde Mij es el bit numero j del entero μi y Lkij es el bit número j del entero λki

El carácter de entrada es reconocido si la distancia Euclidea mínima es menor que el valor de umbral tomado.

7. Vector acumulador y cálculo de los vectores predominantes

Para definir los puntos predominantes de los puntos finales, puntos de árbol y del perímetro, se usa la siguiente técnica estadística:

Tomamos (xi,yi), i=1…n que son las coordenadas de todos los “n” puntos finales del carácter en estudio en una ventana de 16x16 normalizada. Definimos un vector acumulador de tamaño 16x16 inicialmente inicializado a 0 y tomamos una región cuadrada para cada punto final de tamaño (2*l+1)(2*l+1), centrada en el punto final.

El vector acumulador se calcula:

for i=0 ti n

for k=0 to l

for x=xi-k to xi+k

for y=yi-k to yi+k

C(x,y)=c(x,y)+1/(k+1)

Una vez creado el vector acumulador, solo falta calcular los puntos predominantes (6)

El primer punto corresponderá al máximo global de C

Una vez obtenido, se decrementa una zona acotada alrededor del máximo, y volvemos a calcular el máximo, obteniendo así el segundo punto predominante.

Así se itera 4 veces más hasta obtener los 6 puntos predominantes.

Este proceso es equivalente para obtener los puntos de árbol y para los puntos del perímetro (aunque en este último se usa un acumulador unidimensional)

8. Referencias

- https://www.us.es/gtocoma/pid

- Trabajo dirigido año 2003/04 “OCR basado en árboles binarios”. Autores: José Ramón Rodón Ortiz, Javier Ráez Rus, Ismael Vargas Pina.