domingo, 28 de febrero de 2010

Reconocimiento óptico de caracteres.

Hoy he encontrado una aplicación bastante curiosa para mi Nokia 5800 la cual te permite traducir un texto con la cámara de fotos. Me explico:

Estás en un pais extranjero y necesitas saber que significa un determinado cartel que hay en una tienda o un bar o cualquier sitio. Pues con esta aplicación basta con hacer una foto al cartel donde se vean bien las letras y esta puede traducir a tu idioma lo que pone en el cartel.

Esto me ha parecido un poco increible, pero la verdad es que funciona.

Ya sabía de la existencia de scaners que podían hacer algo parecido. Podemos escanear un folio con apuntes de clase escritos a mano y este nos lo convierte a caracteres en el PC. Pero nunca lo había visto a partir de una foto.

Tras descargarme la aplicación y ver que funcionaba me he puesto a buscar información sobre con que tipos de algoritmos se puede conseguir esto y he encontrado alguna información interesante sobre como se hace y cuales son los problemas actuales de estos algoritmos asi como algunas otras aplicaciones de este método:

Partiendo de una imagen perfecta, es decir, una imagen con sólo dos niveles de gris, el reconocimiento de estos caracteres se realizará básicamente comparándolos con unos patrones o plantillas que contienen todos los posibles caracteres. Ahora bien, las imágenes reales no son perfectas, por lo tanto el Reconocimiento Óptico de Caracteres se encuentra con varios problemas:

  • El dispositivo que obtiene la imagen puede introducir niveles de grises al fondo que no pertenecen a la imagen original.
  • La resolución de estos dispositivos puede introducir ruido en la imagen, afectando los píxeles que han de ser procesados.

  • La distancia que separa a unos caracteres de otros, al no ser siempre la misma, puede producir errores de reconocimiento.

  • La conexión de dos o más caracteres por píxeles comunes también puede producir errores.

Todos los algoritmos de Reconocimiento Óptico de Caracteres tienen la finalidad de poder diferenciar un texto de una imagen cualquiera. Para hacerlo se basan en 4 etapas:


Binarización

La mayor parte de algoritmos de OCR parten como base de una imagen binaria (dos colores) por lo tanto es conveniente convertir una imagen de escala de grises, o una de color, en una imagen en blanco y negro, de tal forma que se preserven las propiedades esenciales de la imagen. Una forma de hacerlo es mediante el histograma de la imagen donde se muestra el número de pixeles para cada nivel de grises que aparece a la imagen. Para binarizarla tenemos que escoger un umbral adecuado, a partir del cual todos los pixeles que no lo superen se convertirán en negro y el resto en blanco.

Mediante este proceso obtenemos una imagen en blanco y negro donde quedan claramente marcados los contornos de los caracteres y símbolos que contiene la imagen. A partir de aquí podemos aislar las partes de la imagen que contienen texto (mas transiciones entre blanco y negro).


Fragmentación o segmentación de la imagen

Este es el proceso más costoso y necesario para el posterior reconocimiento de caracteres. La segmentación de una imagen implica la detección de los contornos o regiones de la imagen, basándose en la información de intensidad o información espacial.

Una de las técnicas más clásicas y simples para imágenes de niveles de grises consiste en al determinación de los modos o agrupamientos (“clusters”) a partir del histograma, de tal forma que permitan una clasificación o umbralización de los pixeles en regiones homogéneas.


Adelgazamiento de las componentes

Una vez aisladas las componentes conexas de la imagen, se les tendrá que aplicar un proceso de adelgazamiento para cada una de ellas. Este procedimiento consiste en ir borrando sucesivamente los puntos de los contornos de cada componente de forma que se conserve su tipología.


Comparación con Patrones


En esta etapa se comparan los caracteres obtenidos anteriormente con unos teóricos (patrones) almacenados en una base de datos. El buen funcionamiento del OCR se basa en gran medida a una buena definición de esta etapa. Existen diferentes métodos para llevar a cabo la comparación. Uno de ellos es el Método de Proyección, en el cual se obtienen proyecciones verticales y horizontales del carácter por reconocer y se comparan con el alfabeto de caracteres posibles hasta encontrar la máxima coincidencia.


Algunas otras aplicaciones pueden ser el reconocimiento de matrículas que se utiliza en los radares o el reconocimiento de texto manuscrito.



Por cierto, la aplicación de la que hablaba era esta: ABBYY Foto Translate

miércoles, 3 de febrero de 2010

El Bug de 2038

He estado buscando información de un fenómeno que me pareció muy interesante cuando lo escuché hace tiempo en clase de MP1

Resulta que en el año 2038 tendremos que enfrentarnos a otro bug igual de serio que el pasado bug del famoso "efecto 2000" por el que algunos ordenadores fueron afectados.

Esta vez el fallo tiene que ver con la forma en la que se representan las fechas en POSIX: en segundos desde el 1 de Enero de 1970 a las 00:00:00. En sistemas de 32 bits este valor suele guardarse en variables de tipo entero con signo, siendo el valor máximo que puede representar este tipo 2.147.483.647, valor que se alcanzará a las 03:14:07 del 19 de Enero de 2038, exactamente.

Esta variable (int time_t) puede almacenar valores hasta el 2147483647. Un segundo después del indicado arriba, esta variable pasará a ser el mismo número pero en negativo (-2147483647) causado por un desbordamiento. Muchos programas, entonces, interpretarán que estamos en 1901 o en 1970 en vez de en 2038. Esto haría que muchisimos cálculos fallaran.


La solución sería cambiar esa variable a 64 bits pero esto no es nada facil, ya que se rompería la compatibilidad binaria para el software.

Si consiguieramos cambiar esa variable a 64 bits se retrasaría el problema unos 290 mil millones de años. Para entonces, el sol se habrá extinguido.

¿Donde estaremos en 2038? ¿Se habrá solucionado esto para entonces?¿Qué pasaría si no se soluciona?