En este documento se va a describir qué es un Sistema de Reconocimiento Óptico de Caracteres (OCR) Genérico, a través de la descripción de los algoritmos que se siguen en el desarrollo de un OCR.

Los puntos a tratar son los siguientes:

- Problemas del Reconocimiento de Caracteres à comentarios acerca de la problemática en los sistemas de Reconocimiento Óptico de Caracteres.

- Metodología de Trabajo para un OCR Genérico à explicación de los pasos a seguir en los algoritmos para realizar un sistema de Reconocimiento Óptico de Caracteres.

- Bibliografía.

PROBLEMAS DEL RECONOCEDOR DE CARACTERES

El Reconocimiento Óptico de Caracteres es un método para reconocer la parte textual de una imagen digitalizada. El OCR recibirá como entrada la imagen digitalizada y el resultado de esto es un archivo de texto que puede ser editado y usado como tal por cualquier programa o aplicación que lo necesite.

El Reconocimiento Óptico de Caracteres de una imagen perfecta, es decir, de una imagen de dos niveles de grises, consistirá en reconocer los caracteres de la página que deben crear el fichero de texto. El reconocimiento de estos caracteres se realizará básicamente con la comparación de cada carácter de la imagen con unos patrones o plantillas que contendrá todos los posibles caracteres.

Pero las imágenes reales no son perfectas, cuando estas imágenes son escaneadas introducen algunas alteraciones. Por lo que, el Reconocimiento Óptico de Caracteres se encuentra con varios problemas:

- El dispositivo que obtiene la imagen, puede introducir niveles de grises en el fondo de la imagen dando lugar a niveles de grises no pertenecientes a la imagen real.

- La resolución finita de estos dispositivos pueden afectar a los píxeles que deben ser evaluados.

- La posición de la imagen en la página escaneada es determinante, ya que un mismo símbolo no ocupa el mismo espacio horizontal que verticalmente.

- La conexión de dos o más caracteres por píxeles comunes. Por ejemplo, cuando dos caracteres estén unidos provocan que existan píxeles que pertenezcan tanto a uno como a otro carácter.

- La separación de los caracteres. La no existencia de un espacio fijo entre caracteres puede provocar errores a la hora del reconocimiento.

- Ruido en la imagen. El dispositivo que obtiene la imagen puede insertar niveles de grises dentro de los píxeles que deberían ser negros y pequeñas regiones negras dentro de los píxeles que deberían ser blancos.

Debido a todos estos problemas a la hora de reconocer los distintos caracteres hacen que el sistema de Reconocimiento Óptico de Caracteres deba tener en cuenta la información contextual.

METODOLOGÍA DE TRABAJO.

Todos los algoritmos de Reconocimiento Óptico de Caracteres persiguen la finalidad de poder reconocer un texto para poderlo tratar posteriormente.

Los algoritmos de Reconocimiento Óptico de Caracteres se basan en cinco pasos:

- Adquisición y Binarización

- Fragmentación de la imagen.

- Adelgazamiento de las componentes.

- Comparación con patrones.

Binarización.

La mayor parte de los algoritmos para reconocer escritura están escritos a partir de imágenes binarias, por lo que se hace conveniente el paso de una imagen en niveles de gris (o color) a una binaria, además esto permite reducir el volumen de los datos a tratar.

La binarización de una imagen digital consiste en convertir la imagen digital en una imagen en blanco y negro, de tal manera que se preserven las propiedades esenciales de la imagen.

Uno de los métodos para poder binarizar una imagen digital es mediante el histograma de dicha imagen. A través del histograma obtenemos una gráfica donde se muestran el número de píxeles por cada nivel de gris que aparecen en la imagen. Para binarizar la imagen, se deberá elegir un valor adecuado dentro de los niveles de grises (umbral), de tal forma que el histograma forme un valle en ese nivel. Todos los niveles de grises menores al umbral calculado se convertirán en negro y todos los mayores en blanco.

Ilustración: Histograma de una imagen en escala de grises

Fragmentación o segmentación la imagen

Una vez obtenida la imagen binaria se deberá fragmentar o segmentar en las diferentes componentes conexas (parte de la imagen donde todos los píxeles son adyacentes entre sí) que la componen.

La fragmentación o segmentación de la imagen constituye una de las mayores dificultades del reconocimiento, y se hace necesaria para poder reconocer cada uno de los caracteres de la imagen binaria.

La fragmentación o segmentación es la operación que permite la descomposición de un texto en diferentes entidades lógicas. Estas entidades lógicas deben ser lo suficientemente invariables, para ser independientes del escritor, y lo suficientemente significativas para su reconocimiento.

Con la segmentación se debería localizar las zonas de interés y separar por dichas zonas. Las zonas de interés estarán caracterizadas por unos atributos comunes como son dimensión, superficie, densidad, inclinación, longitud del trazo, etc.

No existe ningún método genérico para realizar la segmentación de la imagen que sea lo suficiente eficaz para el análisis de un texto. Los métodos mayormente utilizados son variaciones del método de ‘Proyecciones Vertical’.

Otro ejemplo, sería utilizar un método que segmentase la imagen en entidades que no tuviesen ningún punto en común (Tsujimoto). En imágenes perfecta daría un resultado favorable. Sin embargo, en la realidad, teniendo en cuenta el ruido, esto no se produce.

Todos estos métodos no pueden ser aplicados al cien por cien, y se hace necesario el estudio del contexto para poder realizar una segmentación correcta. Pero el estudio del contexto no se puede aplicar hasta que no hayan sido extraídos y reconocidos todas las entidades.

Una vez que se hayan extraídos todas los posibles cortes por algunos de los métodos de segmentación, se puede emplear un árbol de decisión. Para ello haríamos:

Determinar todas las posiciones de cortes.
Crearíamos un árbol de decisión, cada región entre dos cortes correspondería a un nodo del árbol.
Asociaríamos a cada nodo un carácter y ponderaríamos su idoneidad respecto a esa región.

Ilustración: Árbol de decisión en un OCR Genérico

La segmentación o fragmentación de una imagen también se puede conseguir mediante la detección de fronteras o bordes. Algunos de los métodos de detección de bordes son:

- El detector de bordes de Sobel.

- El operador de Kirsch.

- Detector de bordes de Marr-Hildreth.

- Detector de bordes de Canny.

Según el grado de asociación entre las operaciones de segmentación y las de reconocimiento, se distinguen tres tipos principales de métodos de segmentación:

- Los Métodos explícitos o segmentación en unidades físicas: Estos métodos, intervienen avanzando el proceso de reconocimiento. Las partes segmentadas se dividen prácticamente en letras, tanto que la segmentación se considera una parte del proceso de reconocimiento.

- Los Métodos de segmentación implícitos o segmentación en unidades lógicas: Los métodos implícitos, consisten generalmente en una segmentación más fina y así conseguir los puntos de corte correctos. Las partes segmentadas son llamadas grafemas. Estos se usarán más adelante, durante el proceso de reconocimiento/ clasificación. Los grafemas estarán compuestos por fragmentos de caracteres, caracteres o grupos de caracteres.

- Los Métodos de segmentación implícitos y exhaustivos: En este caso, es el reconocimiento quien guía la segmentación, así que el sistema de evaluación que se aplica aquí implica un reconocimiento por cálculo de las posiciones sucesivas de la imagen y escoger las posiciones de segmentación que se correspondan con las responsables de las partes más significativas.

Adelgazamiento de las componentes.

Una vez obtenida las componentes conexas de la imagen, se deberá realizar un proceso de adelgazamiento de cada una de ellas.

El procedimiento de adelgazamiento consiste en ir borrando sucesivamente los puntos del borde de cada componente conexa, de forma que se preserve su topología.

Las condiciones exactas que determinan si un punto se puede borrar están relacionadas con el concepto de punto simple (un píxel negro P del borde de la imagen se considera simple si el conjunto de los vecinos en negro de P tienen exactamente una componente conexa que es adyacente a P) y punto final (un punto es final si tiene exactamente un vecino negro; un punto final no es más que un punto extremo de la imagen). Es decir, un punto del borde cada componente se puede eliminar si es simple y no es final.

El borrado de puntos debe seguir un esquema de barridos sucesivos para que la imagen siga teniendo las mismas proporciones que la original y conseguir así que no quede deformada. El borrado en cada rastreo debe hacerse en paralelo, es decir, señalar los píxeles borrables para eliminarlos todos a la vez.

Cuadro de texto: Ilustración: Adelgazamiento de una imagen

Comparar con patrones.

Una vez realizada el adelgazamiento de la imagen, se deberá realizar la comparación con patrones o plantillas.

En esta etapa se deberá comparar los caracteres obtenidos con unos caracteres teóricos almacenados en una base de datos.

Este paso es bastante importante, ya que el buen funcionamiento del OCR se debe en gran medida a una buena definición de esta etapa.

Para poder realizar este paso, se debe disponer en el OCR Genérico de una base de datos en la que se debe almacenar todos los caracteres que deben ser reconocidos por dicho OCR Genérico. En esta base de datos se almacenará, por tanto, todos los patrones o plantillas.

Existen varios métodos para el reconocimiento de caracteres basados en la programación dinámica:

- Métodos geométricos o estadísticos: Consisten en extraer de los caracteres extraídos de la imagen, un conjunto de m medidas que constituyen la composición de un vector de un espacio de representación Rm de dimensión m. Estas medidas suelen ser elevadas en número (m>100). Sus componentes fundamentales son medidas topológicas y métricas, como superficies, regiones, perfiles, concavidades, bucles, intersecciones...

- Métodos estructurales: Estos métodos pasan por una esqueletización de los caracteres extraídos de la imagen, de manera que pasan por una detección de contornos interiores y exteriores para detectar una serie de puntos singulares, de estos puntos se extraerá una información topológica. Posteriormente, se pasará a una vectorización, que permite representar una descripción en forma de cadena de símbolos o de gráficos.

- Métodos Neuro-Miméticos: Están basados en la utilización de redes neuronales de todo tipo: perceptrones multinivel, catas de Kohonen, TDNN, RBF, neocognitrones, colonias corticales,... La mecánica general es partir de una imagen con caracteres normalizados o de símbolos. Los resultados obtenidos, son buenos con la condición de disponer de grandes bases de datos de aprendizaje. Como contrapartida, los tiempos de aprendizaje serán elevados, además sería muy difícil determinar las causas de errores de estos métodos.

- Métodos Markovianos: Se basan en hacer tablas de búsqueda de secuencias de señales de caracteres pero variables en el transcurso del tiempo. Es algo parecido a un caché de reconocimiento de caracteres. Esto en cuanto a almacenamiento, pero el proceso de reconocimiento, combina el uso de un grafo y un proceso aleatorio en las transiciones del grafo así como en su retroalimentación. (Su recomposición a lo largo del tiempo de uso).

- Métodos basados en IA: Estos métodos aplican sistemas de decisión a base de reglas al proceso de reconocimiento. Son algoritmos de búsqueda de árboles que se sustentan la base de algoritmos clásicos (A*).

- Métodos de Zadeh: Estos métodos basados en la lógica borrosa, están muy bien adaptados al reconocimiento de caracteres con un tipo de datos impreciso. Usan Máquinas de estados o reglas de Zadeh.

- Métodos Mixtos: Consisten en una combinación de algunos métodos anteriores, como por ejemplo un sistema CTRBF, que combina un árbol de decisión con una red neuronal.

EJEMPLO: OCR BASADO EN ARBOL BINARIO (pasa a página web independiente)

Bibliografía

- Algorithms for Image Processing and Compunter. J.R. Parker

- Páginas webs diversas relacionadas con el tema, entre las que debemos destacar:

1. www.claraocr.org

2. dkc.jhu.edu/gamera

3. www.gnu.org/software/ocrad

4. http.cs.berkeley.edu/ocrchie

5. jocr.souceforge.net