Repositorio Institucional de Documentos

Proyecto Final de Carrera Ingeniería en Informática Curso 2010/2011 Interpretación de carteles con la cámara de un móvil Ana Belén Cambra Linés Abril de 2011 Directora: Ana Cristina Murrillo Arnal Departamento de Informática e Ingeniería de Sistemas Centro Politécnico Superior Universidad de Zaragoza RESUMEN Mucha de la información que recibimos es visual y, cada vez encontramos más cámaras y bases de datos de imágenes a nuestra disposición. Por ello, el procesamiento automático e “inteligente” de imágenes tiene mucho interés en el desarrollo de nuevas tecnologías y aplicaciones basadas en visión artificial. En particular, en este proyecto el trabajo se centra en las tecnologías en auge de aplicaciones móviles, y cómo hacer uso de las cámaras integradas en los smartphones y de su capacidad cada vez mayor de cómputo. Gracias a esto, se pueden desarrollar aplicaciones relacionadas con la visión por computador en móviles, algo impensable hasta hace poco debido a las grandes limitaciones que presentaban. En el presente proyecto se desarrolla una aplicación para el iPhone capaz de extraer el texto de carteles rectangulares presentes en una imagen. Aunque actualmente existen muchos reconocedores de caracteres, llamados Optical Character Recognitions (OCRs), que permiten extraer el texto de una imagen, sus buenos resultados están muy condicionados a cómo se presenta el texto dentro de dicha imagen. Se requiere que el usuario enfoque con mucha precisión dónde se encuentran los textos a leer. Esta situación es una gran restricción y sobretodo muy poco realista y robusta, además de no permitir aprovechar estas tecnologías para, por ejemplo, dar servicios a personas con problemas de visión. Por ello, un objetivo principal de este proyecto es desarrollar una aplicación que libere al usuario de tal restricción. El funcionamiento de la aplicación desarrollada puede resumirse en tres pasos: elección, procesamiento y lectura del texto de una imagen. Primero el usuario debe capturar una imagen. En el segundo paso se procesa dicha imagen para obtener una nueva que sea más adecuada, para que en el último paso, su texto pueda ser extraído fácilmente por un OCR ya existente integrado también en el teléfono. El trabajo desarrollado en este proyecto, se centra sobretodo en el segundo paso: diseñar e implementar un proceso por el cual obtener una imagen adecuada para conseguir unos buenos resultados con un OCR, y en diseñar un prototipo que presente un funcionamiento satisfactorio en el teléfono. Para ello, antes de comenzar con la fase de desarrollo ha sido necesario una familiarización con el entorno: desde el sistema operativo al entorno de programación, así como estudiar la viabilidad de la inclusión de librerías estándar al dispositivo. En el proyecto se ha diseñado e implementado un detector de rectángulos y un modelo para evaluar la probabilidad de que éstos contengan texto. También se han comparado tres OCRs con el fin de seleccionar aquel que mejor se adapta al proyecto y se ha integrado todo lo anterior creando un prototipo real para el iPhone. La aplicación se ha probado tanto en el simulador como en dos dispositivos físicos: un iPhone 4 y un iPod Touch. Los resultados obtenidos han sido satisfactorios, consiguiendo un prototipo realista, y que podría utilizarse tanto como traductor de textos como asistente de lectura ante deficiencias visuales. i Agradecimientos Mi primer agradecimiento es para ti, Ana Cris, gracias por guiarme a lo largo de todo este proyecto, por los ánimos recibidos en momentos de crisis y sobretodo por tu interés. Me ha encantado que hayas sido la directora de mi proyecto. En especial a “caramelito” y “cuchurita”, porque gracias a “ARToolKit” descubrí con vosotras que hay vida en el CPS pasadas las 5 de la madrugada... Gracias chicas, por vuestros ánimos y paciencia. A ti hippie, por estar allí siempre (aún estando a 2000 Km), por tu apoyo y paciencia pero sobretodo por lo mucho que me quieres y como soy cuando estoy contigo. A vosotras crías, por todos los momentos vividos juntas, por vuestra ayuda, cariño y comprensión en momentos de desesperación. También a vosotros, papá y mamá, por la paciencia demostrada con mi carácter y mal humor, por el apoyo incondicional que me dais y por estar siempre ahí, por y para nosotras. También al resto de mi familia porque estar siempre para lo bueno y lo malo. A Naiara, por estar conmigo, siempre dispuesta a escucharme y entenderme. También gracias a todos los que me habéis escuchado y aguantado mis interminables conversaciones sobre imágenes, rectas, esquinas, histogramas y OCRs... En definitiva, gracias a todos los que formáis parte en mi vida. “Sólo hay 10 tipo de personas en el mundo, las saben binario y las que no” iii Índice general 1. Introducción 1 1.1. Trabajorelacionado............................... 2 1.2. Motivación.................................... 4 1.3. Objetivos .................................... 5 1.4. Estructura de la memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2. Proceso de Desarrollo 7 2.1. Búsqueda de rectángulos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.1. Preprocesado de la imagen . . . . . . . . . . . . . . . . . . . . . . . 8 2.1.2. Detección de rectas . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.1.3. Obtención de esquinas . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.1.4. Búsqueda de hipótesis de rectángulos . . . . . . . . . . . . . . . . . 11 2.2. Evaluación de las hipótesis . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 2.2.1. Filtrado de carteles . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.3. Proyección de hipótesis aceptadas . . . . . . . . . . . . . . . . . . . . . . . 16 2.4. Filtrado de hipótesis proyectadas . . . . . . . . . . . . . . . . . . . . . . . 18 2.4.1. Binarización de la imagen . . . . . . . . . . . . . . . . . . . . . . . 19 2.4.2. Análisis de trazos rectos en hipótesis proyectadas . . . . . . . . . . 20 2.5. IntegracióndeunOCR............................. 20 3. Diseño y validación 23 3.1. Verificación del funcionamiento de la aplicación . . . . . . . . . . . . . . . 25 3.1.1. Pruebas unitarias . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 v 3.1.2. Pruebas de validación . . . . . . . . . . . . . . . . . . . . . . . . . . 25 3.2. Resultados del proyecto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4. Conclusiones y valoración personal 31 4.1. Conclusiones................................... 31 4.2. Trabajofuturo ................................. 32 4.3. Valoraciónpersonal............................... 32 Glosario de acrónimos 35 Bibliografía 38 Apéndices 41 A. Herramientas utilizadas 41 B. Gestión del tiempo 43 C. Obtención de contornos 45 C.1. Ejemplo de resultados proporcionados por varios extractores de rectas . . . 47 D. Comparativa entre los OCRs disponibles 49 E. Diagramas de navegación 59 F. Resultados empleados en la comparación 67 vi Capítulo 1 Introducción Cada día es más habitual hacer un uso diario del teléfono móvil para multitud de tareas, aparte de las típicas de un teléfono común. Además, dicho uso se ve incentivado por la aparición de los móviles de última generación, los llamados smartphones. Un smartphone es el término comercial que denomina a un teléfono móvil que ofrece algunas de las características que posee un ordenador personal, además de proporcionar las funcionalidades propias de una PDA. Existen multitud de modelos fabricados por diferentes empresas, como puede verse en la Figura 1.1, cuyo funcionamiento se basa sobre diferentes sistemas operativos. Dependiendo del fabricante y modelo, los smartphones pueden incluir distintos dispositivos y funcionalidades, como por ejemplo: cámara de fotos y/o vídeo de alta definición integrada, acceso a internet vía Wi-Fi,GPS, acelerómetro, teclado qwerty y/o una pantalla táctil; así como distintas aplicaciones: navegador Web, servicios de correo electrónico, editor/lector de textos, etc. Sin embargo, todos comparten una característica destacable: la posibilidad de desarrollar aplicaciones para su instalación en el teléfono. Figura 1.1: Diferentes modelos de smartphones 1 2.1 Búsqueda de rectángulos 2. Proceso de Desarrollo A lo largo de este capítulo, se profundiza en cada paso realizado durante el proceso, centrando especial atención en los conceptos teóricos necesarios para su comprensión y posterior implementación. 2.1. Búsqueda de rectángulos Uno de los objetivos ya mencionado de este proyecto es liberar al usuario de la imposición de que la imagen a leer, contenga un texto de frente y perfectamente encuadrado. Por lo tanto, al desconocer a priori la ubicación del cartel a procesar, y poder ser ésta cualquiera dentro de la imagen, el primer paso es buscar su posible ubicación en ella. Mirando a nuestro alrededor se observan carteles de muy diferentes colores, tamaños y formas, aunque como la mayoría se asemeja a una forma rectangular, el trabajo se va a centrar en este tipo. Por lo tanto, el primer paso es detectar formas rectangulares. Figura 2.2: Diferentes carteles con texto El proceso implementado para detectar los rectángulos, inspirado en [12], consiste en obtener rectas que aparecen en la imagen, para a partir de ellas encontrar esquinas y así, construir hipótesis de posibles rectángulos intentando agruparlas. Con este proceso, se consigue reducir la zona a analizar de la imagen, intentando procesar sólo aquella que puede ser de interés. 2.1.1. Preprocesado de la imagen En todo proceso de visión artificial el preprocesamiento de una imagen tiene como finalidad producir otra de mayor calidad que simplifique y facilite etapas posteriores. El objetivo es actuar convenientemente sobre los niveles de gris de la imagen para compensar posibles defectos de iluminación así como eliminar ruido y efectos espurios. Técnicas de realce. Su objetivo principal es aumentar el contraste de una imagen mediante la redistribución de sus niveles de gris. En visión por computador, la finalidad de este aumento de contraste no es mejorar la calidad de la imagen para una mejor visualización, sino obtener una imagen resultante que sea más adecuada que la original 8 2. Proceso de Desarrollo 2.1 Búsqueda de rectángulos para una determinada aplicación. Dentro de estas técnicas se encuentra la equalización del histograma [13] que reasigna los niveles de gris de la imagen original para que queden más uniformemente repartidos. Técnicas de suavizado. Su objetivo principal es reducir el ruido y/o espurios que pueden presentarse en una imagen. El ruido no es más que información no deseada que contamina la imagen, es decir, píxeles representados en la imagen que no existen en realidad en la escena capturada. Este ruido es adherido a la imagen a causa del proceso de captura, de su digitalización o incluso de su transmisión. Estas técnicas tienen en cuenta el nivel de gris de los píxeles vecinos para corregir el valor de cada píxel [14]. Las diferentes variantes difieren en cómo escogen los píxeles vecinos y en la ponderación que se les da a cada uno de ellos. En cualquier caso, esta operación se lleva a cabo mediante la convolución de la imagen con una máscara. Y aunque estas técnicas consigan gratamente reducir el ruido existente, tienen un gran inconveniente: el enturbiamiento que se produce en la imagen, provocando el difuminado de los bordes, por lo que deben ser usadas con cierta precaución. 2.1.2. Detección de rectas El primer paso para poder encontrar las rectas presentes en una imagen es extraer los contornos de la imagen. Son regiones de la imagen donde existe un cambio brusco en el nivel de gris entre los píxeles adyacentes y normalmente su causa principal es la intersección de los objetos. Además de suministrar una valiosa información reducen de manera considerable la cantidad de información a manejar; eliminando información innecesaria pero preservando las características fundamentales de la imagen. En el Anexo C se encuentra información más detallada sobre la extracción de contornos. Una vez extraídos los píxeles de contorno, se desea agrupar los segmentos en rectas. Existen distintos métodos como son: la transformada de Hough [13] o el método de Burns [15]. Aquí se ha utilizado el método [16], ya que tras unos experimentos iniciales proporciona mejores resultados que los nombrados anteriormente en el tipo de imágenes que se utilizan (en el Anexo C.1 puede verse un ejemplo de los resultados obtenidos con cada uno de ellos). En este método, las rectas se obtienen agrupando los píxeles mediante un algoritmo de seguimiento de contornos teniendo en cuenta la orientación del gradiente de cada píxel así como la orientación de sus píxeles vecinos. Todas las posibles orientaciones de la dirección del gradiente se dividen en ocho conjuntos. Los píxeles de contorno pertenecientes a un mismo conjunto se unen en cadenas siguiendo un algoritmo de seguimiento de contornos. Este algoritmo los agrupa mientras que sean píxeles vecinos, considerando píxeles vecinos a los ocho adyacentes. El hecho de que los píxeles pertenecientes a un segmento de recta caigan en distintos conjuntos, por su dirección del gradiente, se ven 9 2.1 Búsqueda de rectángulos 2. Proceso de Desarrollo solventadas en la etapa de seguimiento de contornos, donde se tiene en cuenta también los píxeles de los conjuntos adyacentes. Filtrado de rectas. Como resultado de la extracción se obtienen segmentos de rectas representadas por su punto inicial y su punto final. Para evitar tener segmentos de rectas repetidos, que debido al ruido o a la discretización caracterizan a la misma recta, se realiza un filtrado de estos segmentos, cuando sus extremos son muy similares o se realiza una fusión entre segmentos solapados parcialmente. Además se realiza un filtrado de segmentos por su longitud, despreciando aquellos inferiores a 50 píxeles. 2.1.3. Obtención de esquinas Como se ha mencionado, cada segmento sestá representado por su punto inicial (x0, y0) y su punto final (x1, y1). A partir de ellos, se puede calcular la recta ra la que pertenecen: s: (x0, y0)(x1, y1) r:y=m·x+bcon m=(y1−y0) (x1−x0) Si se agrupan los segmentos en horizontales y verticales se pueden combinar, siempre seleccionando uno de cada tipo, para encontrar los puntos de cortes entre ellos. Entre dos rectas coplanares existe un punto en el espacio donde se cortan (incluso las paralelas lo hacen en el infinito). Para calcular el punto de corte entre dos segmentos se calcula el punto de corte entre las rectas a las que pertenecen resolviendo el típico sistema: r1 : yc=m1·xc+b1 r2 : yc=m2·xc+b2 (a) (b) (c) (d) Figura 2.3: Tipos de esquinas detectadas: (a) Superior izquierda, (b) Superior derecha, (c) Inferior izquierda e (d) Inferior derecha 10 2. Proceso de Desarrollo 2.1 Búsqueda de rectángulos De todos los puntos de corte obtenidos sólo interesan aquellos que aparezcan dentro de la imagen y estén próximos a los extremos de los segmentos, ya que éstos son los que tienen más opciones de ser esquinas reales, y corresponder con las esquinas de los carteles. Dependiendo de la localización de éstas en relación a los segmentos se agrupan en cuatro tipos de esquinas, como puede verse en la Figura 2.3. Figura 2.4: Situación en la que un punto de corte entre dos segmentos pertenece a varios tipos de esquinas, en este caso la esquina es tanto superior izquierda como superior derecha En las situaciones en que el punto de corte cae en un zona más o menos central del segmento, si se considera que la esquina sólo puede pertenecer a un tipo, es posible perder algunas hipótesis interesantes. Por ello, cuando sucede esta situación se opta por añadir la esquina a todos los tipos que sea necesario. Un ejemplo de esta situación se ilustra en la Figura 2.4. 2.1.4. Búsqueda de hipótesis de rectángulos Con las esquinas encontradas, se construyen las hipótesis de los rectángulos. Primero se intentan agrupar formando áreas rectangulares y finalmente, si las hipótesis han quedado incompletas, se estima como completarlas. Alineación de esquinas. En primer lugar, para poder construir los rectángulos de la imagen es necesario buscar aquellas esquinas que sean candidatas a pertenecer a un mismo rectángulo y para ello se comprueba si están alineadas. Cada pareja alineada de esquinas debe cumplir las siguientes condiciones: Los segmentos alineados (horizontales o verticales, dependiendo del tipo de esquinas) deben pertenecer a la misma recta, como se ve en la Figura 2.5 (a). 11 2.1 Búsqueda de rectángulos 2. Proceso de Desarrollo La posición relativa de las esquinas debe ser correcta, evidentemente, una esquina superior no puede pertenecer al mismo rectángulo que un esquina inferior que se encuentra por encima de ella. Un ejemplo de este caso puede verse en la Figura 2.5 (b). Debe existir una cierta distancia entre esquinas, ya que como hay esquinas incluidas en varios grupos, o incluso hay algunas que pueden estar demasiado cercanas, se comprueba que no se realicen alineamientos entre la misma esquina. (a) (b) (c) (d) Figura 2.5: Agrupación de esquinas evaluando distintos criterios Primero se buscan los alineamientos entre parejas, formando hipótesis de una alineación como en la Figura 2.5 (a). Sobre las hipótesis encontradas, se intentan forman ahora agrupamientos entre tres esquinas consiguiendo formar hipótesis de dos alineaciones, Figura 2.5 (c). Por último, se intentan alinear con la última esquina, formando hipótesis de cuatro alineamientos cuando se produce un doble alineamiento entre la nueva esquina y sus dos adyacentes, Figura 2.5 (d). Las hipótesis se guardan con el mayor número de alineamientos obtenidos y en el caso de que alguna esquina no forme parte de ninguna hipótesis, se crea una nueva hipótesis que contiene únicamente a dicha esquina, formando las hipótesis más simples. Completado de los rectángulos. Según el número de esquinas que se ha conseguido agrupar en cada hipótesis, existen rectángulos incompletos, exceptuando el caso de las hipótesis de cuatro alineamientos. Por lo tanto, se aproxima la localización del rectángulo completo. Dependiendo del número de esquinas agrupadas, se generan una o varias nuevas hipótesis. En la Figura 2.6 pueden verse ejemplos de cada tipo de hipótesis. En el caso de las hipótesis de tres alineamientos de esquinas se generan dos nuevas hipótesis de rectángulos como muestra la Figura 2.6 (a). En hipótesis de dos y uno se generan tres nuevos rectángulos Figuras 2.6 (c) y (d) respectivamente, aunque no siempre para esta última con el fin de evitar que aparezcan rectángulos muy desproporcionados. Y por último, en el caso de las hipótesis de las esquinas sin agrupar, se crea un único rectángulo Figura 2.6 (b). 12 2. Proceso de Desarrollo 2.2 Evaluación de las hipótesis (a) (b) (c) (d) Figura 2.6: Hipótesis de rectángulos generados a partir de la agrupación de esquinas, en grupos de 1(d), 2(c) y 3(a) alineamientos o de esquinas sueltas (b) 2.2. Evaluación de las hipótesis Junto con la posibilidad de que no todas las rectas y esquinas hayan podido ser detectadas correctamente, también es necesario barajar la posibilidad de que no todas las detectadas son de interés. Por tanto, es muy probable que las hipótesis generadas se hayan obtenido de rectas procedentes de otros elementos de la escena como puertas, ventanas, paredes de baldosas o ladrillo... en lugar de las que corresponden con los bordes del cartel, que son las que interesan. Por esto, es necesario desarrollar un proceso por el cual se pueda evaluar qué hipótesis de rectángulos son más probables de corresponder a un cartel y contener texto. 13 2.2 Evaluación de las hipótesis 2. Proceso de Desarrollo 2.2.1. Filtrado de carteles Para realizar esta evaluación, se han diseñado una serie de filtros para analizar el contenido dentro de cada hipótesis rectangular, para determinar si es probable que éste contenga texto o no. Para el análisis de su contenido se realizan observaciones sobre la región rectangular en escala de grises. El histograma de la imagen representa la frecuencia con la que los niveles de gris aparecen en la imagen. El eje de abscisas indica los distintos niveles (discretos) de grises y en el eje de ordenadas se representa la frecuencia, o el número de píxeles que poseen ese nivel de gris. El histograma proporciona información de cómo están distribuidos los distintos niveles de gris. Figura 2.7: Imagen con su histograma Para poder especificar los parámetros que debe cumplir un rectángulo que contenga texto, se han seleccionado unos cuantos ejemplos, positivos y negativos, y se han observado sus distribuciones. Se han observado las siguientes características: Un cartel típicamente tiene una distribución de colores para las letras muy contrastada con el color destinado para el fondo, para que sea lo más legible posible. Parece que la distribución de los píxeles de los rectángulos de carteles deberán tener claramente dos picos: uno correspondiente al texto y el otro al fondo. Un rectángulo con contenido uniforme, por ejemplo una baldosa, suele tener un único tono de gris dominante en el histograma, que corresponderá con la moda de la distribución. Como la mayoría de los píxeles se agrupan alrededor de la moda, el valor de la media y la moda serán muy próximos y además la desviación típica de la distribución suele ser pequeña. Otro indicador a evaluar, relacionado con este aspecto, es el coeficiente de Curtosis. Analiza el grado de concentración o dispersión que presenta una distribución. Si es leptocúrtica (el coeficiente es mayor que 0) los datos están muy concentrados o cercanos al promedio de la distribución. 14 2. Proceso de Desarrollo 2.2 Evaluación de las hipótesis Los carteles, normalmente, se espera que sean rectangulares, pero sin ser excesivamente alargado o aplastados. Por ello, se van a descartar aquellos rectángulos cuya relación entre anchura y altura no es adecuada, como por ejemplo los mostrados en la Figura 2.8. Figura 2.8: Rectángulo esperado y rectángulos descartados por su forma Gracias a las anteriores observaciones sobre los valores de la distribución típica de grises en un cartel con texto, y sobre su forma, se diseñan los siguientes criterios. Para calcular la probabilidad de que un rectángulo tenga texto, se evaluan las siguientes expresiones: (¯x > 1) ∧(Mo>1) (2.1) (σ > 2) (2.2) (K < 1) (2.3) (Max1(h)<40 %) (2.4) (si ∃(Max1(h)∧Max2(h))) (2.5) (ratio ≥0,5) ∧(ratio ≤6) (2.6) Donde ¯x,Moyσcorresponden con la media, moda y desviación típica de la distribución respectivamente; hes el histograma de la distribución y Maxi(h)corresponde máximo iésimo de los canales del histograma hyratio es la proporción entre los lados del rectángulo: ¯x=Pn i(xi·fi) n(2.7) σ=sPn i(xi−¯x)2 n−1(2.8) K=µ4 σ4= 1 n·Pn i(xi−¯x)4·ni (1 n·Pn i(xi−¯x)2·ni)2−3(2.9) 15 2.3 Proyección de hipótesis aceptadas 2. Proceso de Desarrollo ratio =ladoHorizontal ladoV ertical (2.10) Cada uno de los criterios anteriores que se cumple vota para determinar si la hipótesis analizada es texto o no. Más formalmente, y de cara a ordenar qué hipótesis son más probables, para seleccionar cuales van a continuar el proceso restante, se estima su probabilidad Pcomo sigue: P(T|Ri) = Fi |F|(2.11) La probabilidad de que la hipótesis rectangular Risea de la clase texto (T), depende de cuantos votos recibe (Fi) del total de votos posibles |F|.|F|es 13 ya que los criterios (2.6) y (2.5) tienen un peso de 7 y 2 respectivamente, mientras que el resto tienen peso 1. A los criterios (2.6) y (2.5) se les ha asignado un peso superior por considerarlos características de mayor importancia. Únicamente se aceptan aquellas hipótesis cuya probabilidad sea superior al 75 %. En el caso de que existan demasiadas hipótesis caracterizadas como texto, sólo se considerarán aquellas de mayor P, con el fin de no sobrecargar el trabajo de la aplicación. 2.3. Proyección de hipótesis aceptadas Llegado a este punto del proceso, se dispone del grupo de hipótesis de rectángulos encontrados en la imagen cuyo contenido es muy probable que sea texto. Como paso previo a reconocer los caracteres con un OCR se proyecta la imagen a una vista frontal con el fin de proporcionar al OCR una imagen más fácil de procesar. Al fotografiar un mismo plano, desde distinto ángulo, se obtienen imágenes desde distintas perspectivas del mismo. En las distintas imágenes algunas propiedades geométricas se conservan, como la colinealidad (una línea recta se proyecta como una línea en las imágenes) mientras que otras no se mantienen, como el paralelismo. Las líneas paralelas de la realidad, dependiendo del ángulo al capturar la imagen, no se presentan como tal en la imagen. Por ello, es muy probable que los rectángulos obtenidos de la imagen seleccionada por el usuario correspondan más bien con cuadriláteros deformados; en el que sus lados enfrentados no sean paralelos ni los ángulos que forman sean de 90o, y por lo tanto, que el texto contenido en dichos rectángulos esté deformado también. Una limitación impuesta por la mayoría de OCRs y en particular los de libre disposición, es que para llevar a cabo un correcto reconocimiento de los caracteres, el texto debe estar lo más frontal y paralelo a los bordes de la imagen posible. Por ello, se intenta transformar la imagen en otra (como se sugiere en la Figura 2.9) que muestre la escena 16 2. Proceso de Desarrollo 2.3 Proyección de hipótesis aceptadas Figura 2.9: Vista actual y objetivo del rectángulo como si ésta hubiera sido capturada de frente, para corregir la deformación presente en el texto en la medida de lo posible. Como el área buscada corresponde al mismo plano, se puede realizar una transformación proyectiva entre la vista actual y la objetivo. En geometría proyectiva [17], esta transformación se representa mediante una homografía, que relaciona cada píxel del plano en una imagen con su proyección en la otra imagen. Para estimarla, basta con obtener puntos o rectas coplanares de la escena y sus correspondencias en la otra imagen. En nuestro caso, la segunda imagen es una vista “ideal” frontal que se quiere tener del cartel, así que se debe construir esta imagen “objetivo”. En primer lugar, se estima que forma debería tener cada rectángulo posible si estuviera de frente. Por un lado se puede establecer que la altura vertical es la mayor de las alturas verticales observadas en la hipótesis MAX(¯ AC, ¯ BD), y que la anchura será similar o algo mayor al lado horizontal (¯ CD)que se ve en la Figura 2.9. Según si la vista ya era casi frontal o no, este lado horizontal se debería ver de un tamaño u otro, pero siempre paralelo y de la misma longitud que el lado (¯ AB0). Experimentalmente se ha definido que la longitud de los lados estimados (¯ AB0)y (¯ CD0), según el ángulo αque forman con la vertical, se aproximen como sigue: lado =                lado si α > 83o lado ·1,1si 63o< α ≤83o lado ·1,2si 46o< α ≤63o lado ·1,3si 23o< α ≤46o lado ·1,5si α≤23o (2.12) Con las coordenadas de las esquinas del rectángulo estimado, ya se dispone de las correspondencias entre las cuatro esquinas del rectángulo detectado (ABCD) y su estimación en posición frontal (AB’CD’). Estas cuatro correspondencias, son lo mínimo necesario para estimar la transformación (homografía) que se debe aplicar a todo el plano para pasar de una posición a otra. Un ejemplo de cómo una homografía relaciona dos planos puede 17 3. Diseño y validación !"#"$$%&'() *+(,"' -)(./$0&) -)(./$0&) 1&%$"23") 1&%$"23") 456")()7 +%"'0)(5 6)&$"5(7 280"'")70"90& :&5%8#"57 (6#%$($%&'"5 $&'7"#70"90&7 &80"'%.& Figura 3.2: Pantallas de la aplicación final esta posibilidad no se permite. Tras la elección de la imagen se lleva a cabo todo el proceso descrito en el Capítulo 2. La realización de este proceso es transparente al usuario, el cuál debe permanecer a la espera de que concluya. Para acabar, se muestran los resultados obtenidos en la pantalla. Una vez obtenido el texto de la imagen puede utilizarse para otro tipo de aplicaciones: permitir hacer una consulta a un traductor online, como Google Translator o podría ser reproducido para escuchar el texto sin necesidad de verlo. La interfaz de la aplicación final puede verse en la Figura 3.2. Como un posible uso de esta aplicación es prestar asistencia a personas con algún tipo de discapacidad visual, en un primer momento se pensó incluir un sintetizador de voz que 24 3. Diseño y validación 3.1 Verificación del funcionamiento de la aplicación fuera capaz de leer los resultados mostrados. Pero dadas las características de accesibilidad disponibles en el iPhone 3GS,iPhone 4 y en el iPod Touch (3ageneración y posteriores) no es necesario. VoiceOver1es un lector de pantalla instalado por defecto que se controla únicamente con gestos sobre la pantalla táctil, por lo cual, sólo ha sido necesario adaptar el diseño para que fuera compatible con este sistema. 3.1. Verificación del funcionamiento de la aplicación Para garantizar que la aplicación desarrollada es funcional se han realizado múltiples pruebas con imágenes reales, tomadas con el móvil, para comprobar su correcto funcionamiento, tanto en el simulador como en dos dispositivos físicos. Para realizar una evaluación del prototipo, se ha realizado una comparación entre los resultados que aporta un OCR por sí solo y los que aporta ese mismo OCR una vez integrado en el proceso realizado en este proyecto. 3.1.1. Pruebas unitarias A la hora de desarrollar una aplicación para un dispositivo físico hay que tener especial cuidado con los recursos de los que se disponen, es por ello, que cada paso implementado del proceso ha sido comprobado individualmente en el simulador del iPhone para garantizar que se ejecutaba en un tiempo razonable. Además, se ha realizado pruebas con varias imágenes para verificar que el comportamiento era el esperado. Para facilitar estas pruebas unitarias se ha desarrollado una interfaz secundaria, con la que ha sido más fácil localizar y subsanar de errores existentes en las fases iniciales del proceso y así evitar su acumulación. En el Anexo E puede verse con más detalle el diseño de esta interfaz. Estas pruebas también se han realizado sobre dispositivos reales con el fin de evitar futuras complicaciones o posibles errores de compatibilidad entre el simulador y el dispositivo, o posibles ejecuciones excesivamente lentas. 3.1.2. Pruebas de validación Al describir los objetivos de este proyecto se comparaba el funcionamiento de un OCR ante dos imágenes: una con el texto frontal y perfectamente encuadrado y otra en la que se observaba un cartel desde mayor distancia y con una cierta perspectiva, Figura 1.2. Con esta última imagen el OCR era incapaz de extraer su texto. Si ahora, una vez finalizado este proyecto, se ejecuta la aplicación desarrollada con esa imagen puede verse en la Figura 3.3 (a) que esta vez sí se ha conseguido extraer su texto (b). Tal y como se refleja en la misma figura, también es posible detectar el texto cuando existe más de un cartel como en (c). 1http://www.apple.com/es/accessibility/voiceover/ 25 3.2 Resultados del proyecto 3. Diseño y validación (a) (b) (c) (d) Figura 3.3: Demostración aplicación. A partir de la imagen (a) se obtiene el texto mostrado en (b). Incluso, cuando hay 2 carteles como en (c), se detectan el texto de los 2 (d) 3.2. Resultados del proyecto Para medir de manera más objetiva las mejoras y rendimiento de la aplicación diseñada, se ha realizado la misma comparación de la Figura 3.3 con 30 imágenes, 16 imágenes frontales y 14 no frontales. Se comparan los resultados obtenidos con la aplicación desarro- 26 3. Diseño y validación 3.2 Resultados del proyecto vistas frontales vistas NO frontales PFC OCR PFC OCR µ|σ µ |σ µ |σ µ |σ %lineas 91,67%| 0,260 %57,50 %| 0,500 %60,71 %| 0,490 %28,57 %| 0,47 % %char 76,83 %| 0,290 %39,71 %| 0,400 %39,35 %| 0,400 %9,030 %| 0,18 % %éxitos 68,75%|−−− 25,00%|−−− 30,76%|−−− 0,000 %|−−− %fracasos 6,250%|−−− 37,50 %|−−− 46,15%|−−− 76,92 %|−−− Cuadro 3.1: Tabla que contiene un resumen de los resultados obtenidos por el OCR con y sin añadir el proceso propuesto en este proyecto llada y con los obtenidos con el mismo OCR pero sin el proceso propuesto en este proyecto. Para cada imagen se va a contabilizar el número de líneas y caracteres que se han acertado para calcular una tasa de aciertos. Se han tenido en cuenta las siguientes consideraciones: 1. Cuando en una imagen, no se consigue reconocer ni una sílaba del texto buscado, se considera que no se ha reconocido ningún carácter y que todo es ruido. 2. Para que una línea se considere acertada debe existir al menos una sílaba de la línea correspondiente de la imagen. 3. Si se han detectado más líneas de texto, además de las correctas, se consideran falsos positivos, es decir, ruido. 4. Un carácter se ha acertado si es el mismo que el del texto de la imagen, es decir, si entre el carácter reconocido y el del texto lo único que varía es su acento o si es mayúscula o minúscula. Se considera acierto ya que su lectura no conduce a error. 5. Debido a los problemas en la distinción entre la “o” y el “0”, si se detecta alguno de los caracteres anteriores en respuesta al otro, se considera acierto. 6. Una imagen se considera que ha sido reconocida con éxito si se reconocen correctamente su número de líneas y más del 70 % de sus caracteres. Por el contrario, sólo será considerada como fracaso si no se ha conseguido reconocer ni una línea, en otras palabras, no se ha conseguido reconocer ni una sílaba del texto. Las tablas con los resultados individuales de cada imagen pueden consultarse en el Anexo F, donde también pueden verse el conjunto de imágenes de prueba. Para realizar 27 3.2 Resultados del proyecto 3. Diseño y validación dichas pruebas, las imágenes se han dividido en dos grupos pensando en la facilidad que tendrá el OCR al reconocer su texto. El primer grupo contiene las imágenes cuyo cartel o carteles se encuentran de frente, y en el otro, aquellas en las que éstos se encuentran inclinados y/o deformados. En la tabla 3.2, la columna OCR contiene los resultados proporcionados por el OCRbase, mientras que la columna PFC muestra los datos obtenidos por el mismo OCR pero integrado junto con el proceso desarrollado en este proyecto. Esta tabla recoge la media y la desviación típica de los resultados obtenidos con las imágenes de prueba siguiendo los criterios explicados anteriormente. Para realizar una comparación se calculan los siguientes porcentajes: Líneas acertadas Caracteres acertados Imágenes reconocidas con éxito Fracaso en el reconocimiento Observando los datos se comprueba que, como era de esperar, el OCRbase por si solo, consigue mejores resultados cuando las imágenes están de frente. También se observa que todos los porcentajes de aciertos del OCRbase son inferiores a cuando éste esta integrado en el proceso desarrollado, es decir, que con este proyecto se ha conseguido reconocer más caracteres que antes. Pero lo interesante de estos resultados no es sólo su aumento, sino que se ha conseguido, en un 50 %, un éxito en imágenes que con el OCRbase eran fracasos. Esto puede verse en los resultados del Anexo F. Existe un único caso en el que el proceso fracasa mientras que el OCRbase es capaz de reconocer algo, sin llegar a ser un éxito. Esto se produce por una mala binarizacion durante el proceso como se refleja en la Figura 3.4. En resumen, con este proceso se ha conseguido casi un 70 % de éxitos frente al 25% que proporciona el OCRbase. El porcentaje de no éxitos de este proyecto aún se podría reducir, ya que existen casos en los que se realiza una mala binarización, como ya se ha visto en el ejemplo anterior de la Figura 3.4, y otros en los que el OCR no es capaz de reconocer correctamente el texto aún estando la imagen perfectamente segmentada y binarizada como se observa en la Figura 3.5. Para concluir, se puede afirmar que el proceso implementado en este proyecto cumple su propósito general: extraer el texto de imágenes que un OCR común no consigue obtener. Cabe destacar que los resultados se han obtenido con el simulador, siendo posible que en función de la versión y/o resolución del dispositivo físico utilizado, las imágenes seleccionadas pueden ser redimensionadas automáticamente, y por lo tanto ofrecer algún tipo de variación en los resultados. 28 3. Diseño y validación 3.2 Resultados del proyecto (a) (b) (c) Figura 3.4: (a) Imagen de prueba en la que el OCR consigue reconocer más caracteres (b) frente al fracaso del PFC por una mala binarización (c) (a) (b) Figura 3.5: (a) Aunque el cartel se ha detectado y binarizado correctamente, el OCR no es capaz de reconocer su texto (b) 29 Capítulo 4 Conclusiones y valoración personal Este capítulo contiene las conclusiones extraídas tras la realización de este Proyecto Final de Carrera y una propuesta de posibles líneas de trabajo futuro. Al final se presenta una valoración de lo que su realización ha supuesto a nivel personal. 4.1. Conclusiones El avance en la tecnología utilizada en teléfonos móviles abre todo un mundo nuevo de posibilidades a la hora de desarrollar aplicaciones para estos dispositivos. La calidad que ofrecen sus cámaras, así como el incremento en la capacidad de cómputo, permiten construir aplicaciones que hace unos años eran impensables debido a su consumo de recursos. Gracias a ello y con el deseo de crear una aplicación para un teléfono móvil, combinada con técnicas del campo de la visión por computador, se ha desarrollado este proyecto. Al comienzo de este proyecto se esperaba construir un aplicación capaz de extraer el texto de una imagen mejorando los resultados que presentan los actuales reconocedores de caracteres. Para ello, se ha desarrollado todo un proceso a través del cual se obtiene el texto de un cartel, o carteles, con forma rectangular, que puede encontrarse en cualquier parte de una imagen. El hecho de liberar al usuario de la obligación de que el texto a leer debe estar cercano, de frente y encuadrado, permite el diseño de una aplicación mucho más robusta que incluso podría ayudar a personas con algún tipo de deficiencia visual. Con el proceso desarrollado se ha conseguido proporcionar al OCR únicamente aquellas zonas que poseen una mayor probabilidad de ser un cartel y contener texto, para lo que se ha segmentando la imagen en rectángulos. Con este objetivo se aproximan los contornos de los objetos de la imagen en rectas. En un primer momento, para la extracción de rectas, se utilizó una función proporcionada por OpenCV, pero tras observar que los resultados no eran satisfactorios ni tampoco las soluciones diseñadas para subsanarlos, se optó por implementar otro extractor. Usando las rectas obtenidas por el extractor se construyó un detector de hipótesis de rectángulos. A su vez se ha diseñado un modelo que evalúa eficazmente aquellos rectángulos cuyo contenido parezca o no texto. Tras el 31 4.2 Trabajo futuro 4. Conclusiones y valoración personal estudio, investigación y evaluación de diversas técnicas, finalmente se ha optado por basar el proceso en la forma y la distribución de los niveles de gris en la hipótesis. Como es posible que la imagen hayan sufrido deformaciones a causa de la perspectiva y además una limitación de los OCRs es que para un correcto reconocimiento de caracteres éstos deben estar de frente, se ha diseñado como proyectar los rectángulos a través de una homografía. Con el mismo objetivo de mejorar los resultados obtenidos por el OCR se ha hecho una binarización adaptativa de la imagen, ya que aunque el OCR ya realiza una, ésta es fija y provoca pérdidas o introduce demasiado ruido en los caracteres en algunas imágenes. Como paso final, se ha realizado un análisis de trazos rectos de las imágenes binarizadas, para comprobar que realmente tienen texto y no ralentizar el proceso de lectura de rectángulos sin caracteres. Con el proceso desarrollado se ha conseguido implementar una aplicación real y funcional que además cumple con los objetivos marcados en el proyecto: consigue extraer texto de carteles en imágenes que un OCR base no consigue hacerlo. Con objeto de validar el proceso, se ha llevado a cabo una evaluación exhaustiva con imágenes reales. 4.2. Trabajo futuro Tras la realización del presente proyecto, se proponen a continuación algunas posibles líneas de trabajo futuro: Mejorar el modelo desarrollado de evaluación de hipótesis. Éste sólo analiza los niveles de gris, la forma y la existencia de trazos rectos. Podría completarse con más medidas como la distribución y orientación de los trazos verticales y horizontales, y el estudio de la distribución del gradiente y su orientación en imágenes de texto. También podría estudiarse la viabilidad de integrar un método para que la aplicación fuera aprendiendo a reconocer los carteles conforme su uso, con técnicas de aprendizaje automático. Mejorar el OCR integrado para conseguir un mejor reconocimiento o realizar consultas de diccionario con las cadenas obtenidas con el fin de completar o rectificar cadenas incompletas o mal detectadas. Desarrollar una aplicación todavía más funcional. El proceso podría realizarse sobre una captura de vídeo en tiempo real, de esta manera se podría avisar al usuario cuando se detectara un posible texto. 4.3. Valoración personal La realización de este proyecto ha ampliado mis conocimientos, desde darme la oportunidad de aprender a manejar un nuevo sistema operativo, entorno y lenguaje de pro- 32 4. Conclusiones y valoración personal 4.3 Valoración personal gramación hasta conceptos mucho más teóricos sobre la visión por computador. También, explorar el campo de la programación sobre dispositivos móviles me ha aportado una visión mucho más cuidadosa hacia la programación, ya que en estos dispositivos, los recursos son limitados. A nivel personal he aprendido a ser constante y a dar la importancia que requiere al diseño de las aplicaciones. He perdido el miedo a enfrentarme con lo desconocido y a ser más paciente a la hora de obtener unos buenos resultados. Pero sobretodo, que el esfuerzo invertido ha merecido la pena. 33 Apéndice A Herramientas utilizadas Uno de los objetivos de este proyecto ha consistido en la familiarización con el entorno de programación: Mac OS, iOs, X-Code y el simulador del iPhone, así como el aprendizaje del lenguaje de programación Objective-C. También se ha estudio la librería de código abierto OpenCV para facilitar las tareas relacionadas con la visión por computador. Con más detalle, a continuación se nombran algunas de las herramientas empleadas para el desarrollo de este proyecto. Para poder construir aplicaciones para el iPhone, la empresa Apple proporciona un Software Development Kit (SDK) que permite desarrollar, probar, depurar y simular las aplicaciones. Las aplicaciones desarrolladas funcionan tanto en el iPhone como en el iPad y en el iPod Touch (productos también de la misma empresa). Dentro del SDK se dispone de tres herramientas: Xcode: es un IDE. Para desarrollar aplicaciones para el iPhone, el lenguaje de programación empleado debe ser Objective-C. Este entorno únicamente funciona en sistemas operativos MAC. Interfaz Builder: es una herramienta para el desarrollo visual de la interfaz gráfica de las aplicaciones. Instruments: es una potente herramienta de depuración y análisis del rendimiento de las aplicaciones que se están ejecutando, ya sean desde el simulador o desde el propio teléfono. Permite averiguar el consumo de memoria, de batería, el uso de la red... Una vez desarrollada y probada la aplicación en el simulador, el siguiente paso es instalarla en el dispositivo físico. Una restricción que impone Apple es que no permite instalar aplicaciones que no están firmadas por ellos, de modo que, es necesario inscribirse en el programa de desarrolladores de Apple para obtener un certificado que te proporcione los permisos necesarios. Como paso final en el desarrollo de este tipo de aplicaciones, Apple pone a disposición de los desarrolladores una tienda online llamada App Store, donde se pueden subir estas aplicaciones para su venta. Sin embargo, por las restricciones de la 41 A. Herramientas utilizadas Figura A.1: Herramientas principales utilizadas licencia para educación, el proceso de desarrollo termina con la instalación en un dispositivo físico. En particular se han realizado pruebas en un iPhone 4 y en un iPod Touch. Debido a que en este proyecto se centra en temas de visión por computador, se hace uso de la biblioteca externa, OpenCV, con el propósito de facilitar las tareas relacionadas con el manejo de imágenes. OpenCV es una biblioteca de código libre1dedicada a la visión por computador. Está desarrollada en C y C++ además de ser multiplataforma, ya que existen versiones para GNU/Linux,Mac OS X yWindows. En este proyecto se usa su versión desarrollada en C para Mac OS. Un esquema de las herramientas empleadas para el desarrollo de este proyecto pueden verse en la Figura A.1. 1Disponible en http://opencv.willowgarage.com/wiki/ 42 Apéndice B Gestión del tiempo A continuación, en la Figura B.1 se muestra las tareas más importantes realizadas para llevar a cabo este proyecto y en la Figura B.2 el tiempo dedicada a cada una de ellas. !"#$%"&'(")*+,+ -.$/'(")*+,+ 0- 1%"& '( ")*+, + ! " # $ % & ' ! " # $ % & ' ! " # $ % & ' !"#$% !"# !"#$%&' & ' ( ) !* !! !" $%&'()!* ( ) !* !! !" !# !$ !# !$ !% !& !' !( !) !! !" !# !$ !% !& !' !% !& !' !( !) "* "! "* "! "" "# "$ "% "& !( !) "* "! "" "# "$ "" "# "$ "% "& "' "( "' "( ") #* "% "& "' "( ") #* #! ") #* 2%.%"&'(" )*+,+ "0"(-)*+,, 3" '(" (-) *+,, ! " # $ % & ' ! " # $ % & ' ! " # $ % & ' !"#$% !" !"#$%& & ' ( ) !* !! !" #$%&'() '()!* !! !" !# !# !$ !% !& !' !( !) !* !! !" !# !$ !% !& !$ !% !& !' !( !) "* "* "! "" "# "$ "% "& !' !( !) "* "! "" "# "! "" "# "$ "% "& "' "' "( ") #* #! "$ "% "& "' "( ") #* "( #! &4 (5 -)* +,, 4' (% 6) *+,, &47-)*+,, ! " # $ % & ' ! " # $ % & ' ! " # $ % & ' !"#$%& !"# ! ' ( ) !* !! !" !# $%&'()!* "#$%&'( !$ !% !& !' !( !) "* !! !" !# !$ !% !& !' )!* !! !" !# !$ !% "! "" "# "$ "% "& "' !( !) "* "! "" "# "$ !& !' !( !) "* "! "" "( ") #* #! "% "& "' "( ") #* "# "$ "% "& "' "( ") #* #! 34!")2"6)#(-7".$- +,-.-/ +,01232.-4,5651/725895./,12.1/5./,59359,1/:,/5895;:/<:272.-4, =:/<:272.-4,5895:9.1>,<?3/05?02,8/5@;9,AB C?901:25:9.1205/D19,-8205./,5@;9,AB E-31:28/5895:9.1205@;9,AB =:?9D259F1:2.1/:90G589.-0-4,5-7;3979,12:5/1:/59F1:2.1/:5895:9.120 +7;3979,12.-4,59F1:2.1/: A/7;:/D2.-4,59F1:2.1/:5-7;3979,128/5 E-31:28/G590H?-,20G597;2:9I27-9,1/ =:?9D25-=/8 C/8-J-.2.-4,5-,19:J2KL50939..-4,5J/1/53-D:9:-2M.>72:2 =:?9D25-=N/,9 O/3?.-/,2:59::/:90597;2:9I27-9,1/565./7;3912:5N-;/190-0 PQ0H?9825@AR =:?9D25895@AR565./7;2:21-S2 T/.?79,12.-4,58919..-4,519F1/5M39.1?:252:1-.?3/0 @D19,.-4,589590128U01-.205895-7><9,905./,5650-,519F1/ +7;3979,12.-4,57/893/58919..-/,519F1/565=:?9D2 +,19<:2.-4,5@AR =:?9D258935;:/.90/5./7;391/ P-,2:-K2.-4,565:9./:195D/:895;2:2579I/:2:5:90?3128/0 +,19:J2K5J-,23565;:?9D20 T/.?79,12.-4,5895;:/69.1/G5:982..-4,5895325797/:-2 E-,58935;:/69.1/ Figura B.1: Tareas desarrolladas en este proyecto 43 B. Gestión del tiempo !"#$%"&'(")*+,+ -.$/'(")*+,+ 0- 1%"& '( ")*+,+ ! " # $ % & ' ! " # $ % & ' ! " # $ % & ' !"#$% !"# !"#$%&' & ' ( ) !* !! !" $%&'()!* ( ) !* !! !" !# !$ !# !$ !% !& !' !( !) !! !" !# !$ !% !& !' !% !& !' !( !) "* "! "* "! "" "# "$ "% "& !( !) "* "! "" "# "$ "" "# "$ "% "& "' "( "' "( ") #* "% "& "' "( ") #* #! ") #* 2%.%"& '(" )*+,+ "0"(-)*+,, 3" '(" (-) *+,, ! " # $ % & ' ! " # $ % & ' ! " # $ % & ' !"#$% !" !"#$%& & ' ( ) !* !! !" #$%&'() '()!* !! !" !# !# !$ !% !& !' !( !) !* !! !" !# !$ !% !& !$ !% !& !' !( !) "* "* "! "" "# "$ "% "& !' !( !) "* "! "" "# "! "" "# "$ "% "& "' "' "( ") #* #! "$ "% "& "' "( ") #* "( #! &4 (5 -)* +,, 4' (% 6) *+,, &47-) *+,, ! " # $ % & ' ! " # $ % & ' ! " # $ % & ' !"#$%& !"# ! ' ( ) !* !! !" !# $%&'()!* "#$%&'( !$ !% !& !' !( !) "* !! !" !# !$ !% !& !' )!* !! !" !# !$ !% "! "" "# "$ "% "& "' !( !) "* "! "" "# "$ !& !' !( !) "* "! "" "( ") #* #! "% "& "' "( ") #* "# "$ "% "& "' "( ") #* #! 34!")2"6)#(-7".$- +,-.-/ +,01232.-4,5651/725895./,12.1/5./,59359,1/:,/5895;:/<:272.-4, =:/<:272.-4,5895:9.1>,<?3/05?02,8/5@;9,AB C?901:25:9.1205/D19,-8205./,5@;9,AB E-31:28/5895:9.1205@;9,AB =:?9D259F1:2.1/:90G589.-0-4,5-7;3979,12:5/1:/59F1:2.1/:5895:9.120 +7;3979,12.-4,59F1:2.1/: A/7;:/D2.-4,59F1:2.1/:5-7;3979,128/5 E-31:28/G590H?-,20G597;2:9I27-9,1/ =:?9D25-=/8 C/8-J-.2.-4,5-,19:J2KL50939..-4,5J/1/53-D:9:-2M.>72:2 =:?9D25-=N/,9 O/3?.-/,2:59::/:90597;2:9I27-9,1/565./7;3912:5N-;/190-0 PQ0H?9825@AR =:?9D25895@AR565./7;2:21-S2 T/.?79,12.-4,58919..-4,519F1/5M39.1?:252:1-.?3/0 @D19,.-4,589590128U01-.205895-7><9,905./,5650-,519F1/ +7;3979,12.-4,57/893/58919..-/,519F1/565=:?9D2 +,19<:2.-4,5@AR =:?9D258935;:/.90/5./7;391/ P-,2:-K2.-4,565:9./:195D/:895;2:2579I/:2:5:90?3128/0 +,19:J2K5J-,23565;:?9D20 T/.?79,12.-4,5895;:/69.1/G5:982..-4,5895325797/:-2 E-,58935;:/69.1/ Figura B.2: Tiempo dedicado a las tareas desarrolladas en este proyecto 44 Apéndice C Obtención de contornos Un contorno o borde es una región de la imagen donde existe un cambio fuerte en el nivel de gris entre los píxeles adyacentes, es decir, donde existen un cambio de intensidad abrupta. Su causa principal es la intersección entre objetos, que al tener distintos niveles de reflectancias y al ser éstos proyectados sobre la cámara, generan discontinuidades de intensidad. Aunque también aparecen bordes no deseados provocados por la presencia de ruido, por el efecto de sombras de los objetos o provocados por una iluminación no uniforme en la escena. Los contornos de una imagen suministran una valiosa información que es utilizada en muchas tareas de visión por computador, como la segmentación de la imagen o el reconocimiento de objetos, y que además reducen de manera significante la cantidad de información a manejar; eliminando aquella innecesaria pero preservando las características fundamentales de la imagen. Es por ello, que estos métodos son una herramienta muy poderosa en este campo. Si se considera la intensidad de la imagen como una función, al buscar sus contornos, estaríamos buscando los picos de dicha función. En una función continua, el cálculo de la primera derivada nos sirve para encontrar sus picos. Si estamos en dos dimensiones, el cálculo de la primera derivada viene determinado por el gradiente. Las ecuaciones del gradiente se ven en la Figura C.1. En el caso de las imágenes, la intensidad de la imagen es una función discreta, por lo tanto, un aproximación al gradiente se basa en el cálculo de las diferencias entre los niveles de gris de la imagen, usando para ello máscara de convolución. La variación de gris se calcula como muestra la figura C.2. Existen numerosos métodos de detección de contornos como son el LoG [13] o el explicado en [18], en este proyecto, para obtener los contornos de la imagen, se le aplica el método de Canny [19] por ser unos de los métodos más empleados. Algoritmo de Canny El valor de la primera derivada es usado porque toma el valor cero en aquellas regiones donde no se produce un cambio de intensidad y tiene un valor constante en toda la transición de intensidad, por lo tanto, un cambio de intensidad se manifiesta como un cambio brusco en la primera derivada; característica usada para 45 C. Obtención de contornos Figura C.1: Gradientes Figura C.2: Máscara convolución detectar un borde. El operador propuesto por Canny se aproxima mediante la derivada de la Gausiana en la dirección perpendicular al borde. Los pasos a seguir son los siguientes: 1. Calcular el módulo y la dirección del gradiente de la imagen suavizada aplicando un operdor DroG. 2. En la dirección del gradiente, eliminar puntos que no sean máximos locales del 46 C. Obtención de contornosC.1 Ejemplo de resultados proporcionados por varios extractores de rectas Figura C.3: Máscaras para el cálculo del gradiente módulo para conseguir un adelgazamiento de los bordes hasta un píxel de ancho. Se consideran cuatro direcciones del gradiente 0o, 45o, 90oy 135o(con respecto al eje horizontal). Para cada píxel se encuentra aquella dirección que mejor se aproxime a su dirección del gradiente. Posteriormente se observa si el valor de la magnitud del gradiente es menor que sus vecinos en dicha dirección. De ser así, se le asigna un cero, en caso contrario, la magnitud del gradiente. 3. Se aplica una función de histéresis basada en dos umbrales: un gradiente alto yun gradiente bajo, que pretende reducir las falsas detecciones. Cada segmento de un borde debe tener un píxel cuyo módulo del gradiente supere el umbral máximo, así como todos los píxeles vecinos siguiendo la orientación del borde mientras que el valor de su gradiente no caiga por debajo del umbral mínimo. C.1. Ejemplo de resultados proporcionados por varios extractores de rectas En la Figura C.4 se ve un ejemplo de las rectas que se obtienen con los distintos métodos. Tanto el método de Burns como el finalmente implementado. Éstos proporcionan unos mejores resultados que el disponible en la librería de OpenCV y dado que había que adaptar cualquiera de ellos para poder utilizarlo en este proyecto, se decidió adaptar aquel 47 C.1 Ejemplo de resultados proporcionados por varios extractores de rectasC. Obtención de contornos que proporcionaba mejores resultados. (a) (b) (c) Figura C.4: Rectas obtenidas con distintos extractores: (a) Transformada de Hough proporcionada por la biblioteca OpenCV, (b) Método de Burns y (c) Extractor implementado para este proyecto 48 Apéndice D Comparativa entre los OCRs disponibles En este anexo se muestra los resultados obtenidos de comparar los tres OCRs de código disponible: OCRAD,TESSERACT yGOCR. Se han seleccionado varias imágenes, a partir de ellas, se ha recortado su texto, ya que los OCRs en la mayoría de los casos, no eran capaces de extraerlo por sí solos. Las imágenes también han sido binarizadas para facilitar el reconocimiento a los OCRs. En las comparaciones se ha tenido en cuenta la inclinación del texto, incluyendo imágenes inclinadas y estas mismas pero corrigiendo su inclinación manualmente. En la Figura D.1 se recogen los datos obtenidos, teniendo en cuenta el número de caracteres que se ha conseguido reconocer correctamente y aquellos que se han reconocido mal. Tras la tabla, se muestran las imágenes de prueba y sus resultados con cada OCR, así como la binarización, recorte y rectificación de la inclinación según la imagen a analizar. 49 D. Comparativa entre los OCRs disponibles !"#$% !"#"$%&'()*+$",-./.#01-"0!.2-3"$"*4,!5)#.46789:,;9*.E>2.=>/.!>i.2.?,#< B6SK(( &'(('#$"& !"#"$%&'()*+$",-./.#01-$)**)!.0$-3"$"*4,!5)#.46789:,;9*.E>2.=>/.!>i.2.?$>3-!)*5E-GE-*,. C)**)!.0$-6,)/-B"5!0)-678-D/;>/) !"#"$%&'()*+$",-./.#01-<"!)-!)*5E?$F$ BASK(A )!"# !"#"$%&'()*+$",-./.#01-;"0!-G<-H-3"$"*4,!5)#.46789:,;9*.E>2.=>/.!>i.2.?,#< *44444 !"#$% !"#"$%&'()*+$",-./.#01-"0!.2-3"$"*4,!5)#.46789:,;9*.E>2.=>/.!>i.2.K?,#<- BA4K(A &'(('#$"& !"#"$%&'()*+$",-./.#01-$)**)!.0$-3"$"*4,!5)#.46789:,;9*.E>2.=>/.!>i.2.K?$>3-!)*5E-GE-*,. C)**)!.0$-6,)/-B"5!0)-678-D/;>/) K<.;)-P.*-g-h-H-#>$*-,)!-,>F)EI-./2-*>i)-jHgkIkumn 8)*"E5$>"/_m% !"#"$%&'()*+$",-./.#01-<"!)-!)*5E?$F$ BASK(A )!"# !"#"$%&'()*+$",-./.#01-;"0!-G<-H-3"$"*4,!5)#.46789:,;9*.E>2.=>/.!>i.2.K?,#<- B4>>44 56 D. Comparativa entre los OCRs disponibles !"#$% !"#"$%&'()*+$",-./.#01-"0!.2-3"$"*4,!5)#.46789:,;9*>/Q5<"*=>/.!>i.2.?,#<-I\\\-4-II 4-I-r-dr! \]$I 4ST4rv44-4 w !I-Gm4-4 44TxK7K6-ST=8D-(D-Q5@"4 AJA3rRrD4y7I4w?-BR-7Iw?LA88KSS6 ?-w T 4??j?-?p-\-??->Dz-k-4XX& r-?-r4T-K=?6?A?-&&-H-K66&w E-\ &'(('#$"& !"#"$%&'()*+$",-./.#01-$)**)!.0$-3"$"*4,!5)#.46789:,;9*>/Q5<"*=>/.!>i.2.?$>3-!)*5E-GE-*,. C)**)!.0$-6,)/-B"5!0)-678-D/;>/) K<.;)-P.*-g-h-H-#>$*-,)!-,>F)EI-./2-*>i)-jq%uImkqn 8)*"E5$>"/_m% !"#"$%&'()*+$",-./.#01-<"!)-!)*5E?$F$-\I ?\v\\-@{ v-\-h8-r# %-I3-%k-I &-h3|P-h SS-[-} ~rK5<t D(KxK7K6-OSn=8D-(D-Q5<"* AJALRDALRKr-BR-LKLA88KSS6 v-4h---s--- ÄG-4-----j*?"?AI )!"# !"#"$%&'()*+$",-./.#01-;"0!-G<-H-3"$"*4,!5)#.46789:,;9*>/Q5<"*=>/.!>i.2.?,#<- 4D4E4--44$4!$---E--f 44' 4 o---E r4-4-4_ 4j-4 K--4$ 4 &K!$4j444 (b#.!0"2)-$c,)_d5/+/"e/d-9fb#.!0"2)-$c,)_d5/+/"e/d-9f x---XE4r=4D-4-D-Qr-5-<-"-* A4ALRDI4444L?KBRb#.!0"2)-$c,)_d5/+/"e/d-9fb#.!0"2)-$c,)_d5/+/"e/d-9f b#.!0"2)-$c,)_d5/+/"e/d-9fb#.!0"2)-$c,)_d5/+/"e/d-9f L----6 4 4---------4-o-4-$ r 9----j-=?-"?-A? ------&&-H-%-6-6 57 Apéndice E Diagramas de navegación El funcionamiento general de la aplicación se resumen en tres pasos como muestra el diagrama diagrama E.1: 1. El usuario debe seleccionar una imagen 2. De manera transparente al usuario, se debe calcular las hipótesis de carteles 3. Se muestran los resultados de leer con cada hipótesis aceptada con un OCR. La imagen puede elegirse, como puede verse en el diagrama E.2, tanto de las almacenadas en la propia biblioteca del dispositivo como capturando una nueva con la cámara, siempre que el dispositivo disponga de ella. El proceso realizado y detallado en el Capítulo 2 para extraer las hipótesis de los rectángulos se realiza de una manera transparente al usuario, pero para comprobar el funcionamiento de la implementación y posterior depuración de la misma, se ha realizado una navegación secundaria que permite realizar dicho proceso paso a paso. El diagrama E.3 permite realizar las tareas especificadas en la sección 2.1. El diagrama E.4 muestra la navegación para llevar a cabo la evaluación de una hipótesis tal y como se explica en la sección 2.2. En el diagrama E.5 se observa el proceso detallado en la sección 2.3 y 2.4. El último paso de la aplicación es donde se muestran al usuario los resultados obtenidos con las hipótesis aceptadas. La tarea individual de leer cada hipótesis también se puede realizar de manera individual gracias a la navegación, puede verse en el diagrama E.6. 59 E. Diagramas de navegación !"#$%&''()*# (+,-&* ."#$/&'0'()*#1&%#234'&54#1&5,334%%,14 6"#7&'803,# 1&%#8&984 Figura E.1: Funcionamiento general de la aplicación 60 E. Diagramas de navegación !"#$$%&'()#("*(%+*,#' -*'.*""*(%'$%/($/+0"#.* !1234!5627 8!(69:7;7 3#"#$$%&'()#("*(%+*,#' -</$#=*<("*%*+,#'' Figura E.2: Elección de la imagen a procesar 61 E. Diagramas de navegación !"#"$%&'()*+,$ +* -*./012)34' !"#"#$5-*67-4.*',+4$ +*$3, $89,2*1 !"#"!$:*/*..8;1$ +*$ -*./,' !"#"<$=>/*1.8;1 +* *'()81,' !"#"?$%&'()*+,$ +*$ 87;/*'8' $+*$-*./012)34' Figura E.3: Búsqueda de rectángulos 62 E. Diagramas de navegación !"!"#$%&'(&)*+,# -. /*0+1.2*2 3.'.))*+,&4#(,& /*0+1.2*2 !"!"5#6*'14&-7 689:;< 3*#0&2&#.'#=*'147 3*#,7#0&2&#.'#=*'147 Figura E.4: Evaluación de hipótesis 63 E. Diagramas de navegación !"#"$%&'()**+,-$.) /01$2+3,4)1+1 0*)340.01 5)/)**+,-0&$6-0 7+3,4)1+1$*'-$4)84' !"9"!$:-;/+1+1$.)$4&0<'1$ &)*4'1 =>? :!?" =!?:5 !"#$%&'()!!" !"#$%&'()"!" %&'()*40&$/0$2+3,4)1+1 !"9"#$$+-0&+<0&$/0$2+3,4)1 1)/)**+'-0.0 !"9"$%'1%3&'*)10.' .)$/0$+&0')- Figura E.5: Proyección y posprocesado de las hipótesis 64 E. Diagramas de navegación !"#$%&'()*#+%,#-%.'/ 0123'%414#2)/5%&'*+*#5 6%&/)'*+* $%&'()*#+%,#'%.'/#&/7# %,#896 :/41;,%4#*2,1&*&1/7%4# &/7#%,#'%.'/# /;'%71+/ -)*+(&'/) -)*+(&'/) </1&%8=%) </1&%8=%) Figura E.6: Lectura del texto 65 F. Resultados empleados en la comparación !"#$% !&'()*+, !"# -.-+#/+01223445 6-437-89:;9*< 0-23-+45!=> !4-.?-+ -!-+8":99(#)< !4-.?-+ -!-+8$:%&:'*< $%!&'()%) !!!! ?5?-4+ "# $% #"% .#+$;#(:9)*; ,*+,- ,, ./+%- ../+*- ,0,+%- .#+);*1#"+;:9)#" ,0 //+2- ,. .3+%- *,%+*- 0.3+2- -#=!?-7-6 .,,+/- ,0 .%+,- 33+3- .%.+,- 4+5&:)*" .,33+3- ,0%+6- 33+3- 33+3- #*+*#'(+() !!!! ?5?-4 ,%% ,3 ,3 *9(:;)#" 33+3- ,%/+.- 33+3- 33+3- 7*88#" 33+3- 33+3- 33+3- 33+3- ;&(9# 33+3- %6+,- 33+3- 33+3- ,%-(*) !!!! ?5?-4 , % , , *9(:;)#" ,,33+3- ,*3+3- 33+3- 33+3- ;&(9# 33+3- 33+3- 33+3- 33+3- !"#$% &'()*+,- !"# ./.,"0,12##344! 5.436.789:8+; 1.#3.,4!&<= &4./>.,?. .,7!988)"*; &4./>.,?. .,7#9$%9&+; "$#$"%&#&' !!!! >!>.4 '%% -( -( +8)9:)"! ((*(+ %,*-+ ((*(+ ((*(+ -+.."! ((*(+ %- ,/*/+ ((*(+ ((*(+ :%)0" -- -12*2+ 3-1*%+ /% /%(*(+ '% '%(*(+ ()*&$' ! ! ! ! >!>.4 - % - - +8)9:)"! ((*(+ %-((*(+ ((*(+ ((*(+ :%)0" --((*(+ -/(*(+ -4 -4((*(+ -2 -2((*(+ Figura F.8: Tablas para la comparación de imágenes NO frontales 72 F. Resultados empleados en la comparación Figura F.9: Las 8 primeras Imágenes de prueba NO frontales 73 F. Resultados empleados en la comparación Figura F.10: Las 6 últimas Imágenes de prueba NO frontales 74