Reconocimiento automático de patentes, en ambientes no controlados Tesis de licenciatura de Ariel Hernán Curiale Departamento de Computación Facultad de Ciencias Exactas y Naturales - UBA Directora: Marta Mejail 7 de junio de 2009

Resumen En este trabajo se propone un algoritmo capaz de resolver el problema conocido en la bibliografía como Reconocimiento automático de patentes, o en inglés Automatic License Plate Recognition (ALPR). El problema consiste en encontrar la posición de la patente dentro de la imagen y extraer sus caracteres. De esta forma se puede identificar automáticamente el vehículo. El problema de ALPR tiene una gran cantidad de desafíos a resolver. Algunos de ellos son: La iluminación no controlada de la imagen. El brillo de las luces de los automóviles. El ambiente no controlado del fondo. Las condiciones climáticas que modifican la calidad de la imagen. La distorsión de la patente generada por el ángulo en que se capturó la imagen. La oclusión parcial o total de la patente. La oclusión parcial o total de algún caracter. La localización de la patente dentro de la imagen que en muchos casos depende del tipo de vehículo. El reconocimiento óptico de los caracteres. Para resolver el problema de ALPR se lo divide en varias etapas, cada una con un propósito específico. Estas etapas son: Adquisición de la imagen: Se utiliza una cámara infrarroja para superar el inconveniente de capturar imágenes de noche y se usa una sola imagen por vehículo. Pre-procesamiento: Se realiza una ecualización del histograma. Segmentación 3

• Primer etapa de segmentación: En esta etapa se aplica la técnica de Top Hat, se ecualiza el histograma de la imagen resultante y se la binariza. Luego se utiliza la transformada de Fourier discreta en una ventana de 32 píxeles y se filtran todos los píxeles que no se encuentran dentro de los máximos valores. Para encontrar los objetos resultantes se utiliza el algoritmo de Pavlidis de seguimiento de contorno, y para resolver el posible problema de fragmentación, se utiliza un algoritmo de clustering. • Filtrado de patentes falsamente detectadas: Se expanden los clusters para garantizar que alguno de ellos contenga la patente y se aplica nuevamente el algoritmo de FFT para descartar los objetos falsamente identificados. Luego se reajusta el tamaño de los clusters según sus proyecciones verticales y horizontales. Reconocimiento óptico de la patente • Segmentación de los caracteres: Se utiliza un algoritmo morfológico de adelgazamiento, se arman las regiones con el algoritmo de Pavlidis y se filtran las regiones que no se corresponden con las dimensiones de un caracter. • Reconocimiento óptico de los caracteres: Se aplica el OCR a cada uno de los caracteres. El OCR se implementó mediante una red neuronal del tipo perceptrón multicapa compuesta por dos capas de 256 y 10 neuronas cada una. Filtrado de patentes falsamente detectadas.

Abstract In this work a new algorithm capable of solving the problem known in the bibliography as Automatic License Plate Recognition (ALPR) is proposed. The problem is to find the position of the license plate within the image and to extract their characters. In this way the vehicle can be identified automatically. The problem of ALPR has many challenges to solve. Some of them are: The uncontrolled illumination of the image. The brightness of the lights of the vehicles. The uncontrolled environment of the background. The climatic conditions that modify the quality of the image. The distortion of the license plate generated by the angle in which the image was captured. The partial or total occlusion of the license plate. The partial or total occlusion of some characters. The location of the license plate within the image that in many cases depends on the type of the vehicle. The optical character recognition. To solve the problem of ALPR it is divided in several stages, each of them with a specific purpose. This stages are: Capture of the image: An infrared camera is used to overcome the disadvantages of capturing images at night. A single image per vehicle is used. Pre-processing: A histogram equalization is done. Segmentation • First stage of segmentation: In this stage the Top Hat technique is applied, the histogram is equalized and binarized. Then a Discrete Fourier Transform is used in a window of 32 pixels and all the pixels that are not within the maximum values are filtered. To find the resulting objects the Pavlidis algorithm for contour tracking is used, and to solve the possible problem of fragmentation , a clustering algorithm is employed. 5

6

Ariel Hernán Curiale

• Filtered of falsely detected license plates: The clusters are expanded to guarentee that one of them contain the license plate and the FFT algorithm is applied again to dismiss the falsely identified objects. Then the size of the clusters are reajusted according to their horizontal and vertical projections. License plate optical recognition • Characters segmentation: A morphological algorithm of thinning is used, the regions are made with the Pavlidis algorithm and the ones that don’t correspond with the dimension of a character are filtered. • Optical character recognition: The OCR is applied to each character. The OCR was implemented by means of a multi-layer perceptrons neural network, composed of two layers with 256 and 10 neurons each one. Filtered of falsely detected license plates.

8

Ariel Hernán Curiale

Índice de Contenidos 1. Introducción 1.1. Pre-procesamiento de una imagen . . . . . . . . 1.1.1. Ecualización del histograma . . . . . . . 1.2. Segmentación de Imágenes . . . . . . . . . . . . 1.2.1. Filtrado en el dominio de las frecuencias 1.2.2. Umbralización . . . . . . . . . . . . . . 1.2.3. Morfología Matemática . . . . . . . . . 1.2.4. Thinning o adelgazamiento . . . . . . . . 1.3. Identificación de los Caracteres . . . . . . . . . . 1.3.1. Redes Neuronales Artificiales . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

2. El método de ALPR propuesto 2.1. Adquisición de la imagen y selección . . . . . . . . . . . 2.2. Pre-procesamiento . . . . . . . . . . . . . . . . . . . . . 2.2.1. Conversión de la imagen en color a niveles de gris 2.3. Segmentación . . . . . . . . . . . . . . . . . . . . . . . . 2.3.1. Buscando la patente . . . . . . . . . . . . . . . . 2.3.2. Filtrado de patentes falsamente detectadas . . . . . 2.4. Segmentación de los caracteres . . . . . . . . . . . . . . . 2.5. Reconocimiento de los caracteres . . . . . . . . . . . . . . 2.6. Análisis sintáctico . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

17 20 20 24 24 26 29 39 42 43

. . . . . . . . .

53 55 57 57 58 65 70 71 71 72

3. Resultados 73 3.1. Algunas mediciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4. Conclusión 85 4.1. Trabajos a futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 A. Métodos fallidos para resolver el problema de ALPR 91 A.1. Roberts - Binarización - Proyecciones horizontales y verticales . . . . . . . . . . 91 A.2. Top Hat + Seguimiento de contorno . . . . . . . . . . . . . . . . . . . . . . . . 95 9

10

ÍNDICE DE CONTENIDOS

Ariel Hernán Curiale

B. Otros métodos de OCR 97 B.1. Modelos Ocultos de Markov . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 B.2. Distancia de Hausdorff . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 B.3. Template Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 C. Algoritmos C.1. Algoritmos utilizados en los Modelos Ocultos de Markov . . . . . . . . C.1.1. Nomenclatura . . . . . . . . . . . . . . . . . . . . . . . . . . . C.1.2. Algoritmo Forward . . . . . . . . . . . . . . . . . . . . . . . . C.1.3. Algoritmo Backward . . . . . . . . . . . . . . . . . . . . . . . C.1.4. Algoritmo Viterbi . . . . . . . . . . . . . . . . . . . . . . . . . C.1.5. Algoritmo Backward - Forward para entrenamiento de un HMM C.2. Algoritmo BackPropagation usado en redes neuronales . . . . . . . . . C.3. Algoritmo de seguimiento de contornos . . . . . . . . . . . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

. . . . . . . .

105 105 105 105 106 106 106 107 109

Índice de tablas 1.1. Ejemplos de redes neuronales monocapa . . . . . . . . . . . . . . . . . . . . . . 45 1.2. Ejemplos de redes neuronales feedforward . . . . . . . . . . . . . . . . . . . . . 46 B.1. Uso de la distancia de Housdorff para el reconocimiento óptico de caracteres. . . 101 C.1. Nomenclatura utilizada en los Modelos Ocultos de Markov . . . . . . . . . . . . 105

11

Índice de Figuras 1.1. 1.2. 1.3. 1.4. 1.5. 1.6. 1.7. 1.8. 1.9. 1.10. 1.11. 1.12. 1.13. 1.14. 1.15. 1.16. 1.17. 1.18.

Etapas involucradas en el reconocimiento automático de patentes . . . . . . . . Histograma de cuatro tipos básicos de imágenes . . . . . . . . . . . . . . . . . Ejemplo de una convolución . . . . . . . . . . . . . . . . . . . . . . . . . . . Ejemplo del problema de la convolución . . . . . . . . . . . . . . . . . . . . . Histograma de una imagen que se pueden dividir con un umbral simple . . . . Ejemplo de una umbralización simple con un umbral T = 126 . . . . . . . . . En la Figura b) se puede observar el resultado de dilatar al objeto X con el elemento estructurante Y. Imagen extraída de [1] . . . . . . . . . . . . . . . . . . Ejemplo de una dilatación en una imagen binaria utilizando un elemento estructurante de 3x3 píxeles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Resultado de erosionar al objeto X con el elemento estructurante Y. Imagen extraída de [1] . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ejemplo de una erosión en una imagen binaria utilizando un elemento estructurante de 2x2 píxeles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Ejemplo de una dilatación en una imagen en escala de grises. . . . . . . . . . . Ejemplo de una erosión en una imagen en escala de grises. . . . . . . . . . . . Ejemplo de una apertura y cierre sobre una imagen en escala de grises. . . . . . Ejemplo de aplicar el filtro Top Hat sobre una imagen en escala de grises. . . . Ejemplo del número de conectividad para un píxel. . . . . . . . . . . . . . . . Ejemplo de conexión en redes neuronales artificiales . . . . . . . . . . . . . . Modo de aprendizaje supervisado en una red neuronal artificial . . . . . . . . . Modo de aprendizaje no supervisado en una red neuronal artificial . . . . . . .

2.1. 2.2. 2.3. 2.4.

Diagrama de actividad del método utilizado para resolver el problema de ALPR Imágenes de muestra con las que se trabaja . . . . . . . . . . . . . . . . . . . Ejemplo de la conversión a escala de grises de una imagen color . . . . . . . . Ejemplo detallado de algunos resultados intermedios de la primer etapa de segmentación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.5. Ejemplo detallado de algunos resultados intermedios de la primer etapa de segmentación. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.6. Ejemplo de la primer etapa de segmentación aplicando el método de FFT en una ventana de 32 píxeles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

. . . . . .

19 21 27 27 28 29

. 33 . 33 . 33 . . . . . . . . .

34 36 37 38 40 41 45 47 47

. 54 . 56 . 58 . 59 . 60 . 62

14

ÍNDICE DE FIGURAS

Ariel Hernán Curiale

2.7. Ejemplo de la primer etapa de segmentación aplicando el método de FFT en una ventana de 32 píxeles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.8. Se muestra el resultado de aplicar la FFT a cada píxel de la imagen puesto en forma vertical para las líneas 40,145 y la que contiene algunos píxeles pertenecientes a la patente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.9. Ejemplo de una superposición espacial de dos regiones en la cual una es un caracter válido . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.10. Ejemplo de fusión de diferentes regiones . . . . . . . . . . . . . . . . . . . . . 2.11. Contorno de seis caracteres utilizando el método de seguimiento de contornos . 2.12. Orden tomado para el seguimiento de contorno . . . . . . . . . . . . . . . . . 2.13. Ejemplo de los paso más importantes para segmentar los caracteres de la patente detectada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1. Ejemplo de la segmentación de la patente utilizando el método propuesto en el paper New Methods For Automatic Reading of VLP’s[2] . . . . . . . . . . . . . 3.2. Ejemplo de la segmentación de nuestro método utilizando la imagen del paper New Methods For Automatic Reading of VLP’s[2] . . . . . . . . . . . . . . . . 3.3. Ejemplo de una mala segmentación utilizando el método propuesto en el paper New Methods For Automatic Reading of VLP’s[2] . . . . . . . . . . . . . . . . 3.4. Otro ejemplo de una mala segmentación utilizando el método propuesto en el paper New Methods For Automatic Reading of VLP’s[2] . . . . . . . . . . . . . 3.5. Tiempos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.6. Ejemplo de una mala segmentación de los caracteres . . . . . . . . . . . . . . 3.7. Ejemplo del conjunto de imágenes analizado . . . . . . . . . . . . . . . . . . . 3.8. Ejemplo de una imagen tratada con nuestro método . . . . . . . . . . . . . . . 3.9. Ejemplo de una mala segmentación . . . . . . . . . . . . . . . . . . . . . . .

. 63

. 64 . . . .

66 67 67 68

. 72 . 75 . 76 . 77 . . . . . .

78 79 80 81 82 83

A.1. Ejemplo de la aplicación del filtro de Roberts y la proyección vertical de sus componentes en blanco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 A.2. Ejemplo de la aplicación del filtro de Roberts y la proyección horizontal de sus componentes en blanco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 A.3. Ejemplo de la aplicación del filtro de Roberts y la proyección vertical de sus componentes en blanco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 B.1. Ejemplo del Modelo de Markov discreto de dos estados . . . . . . . . . . . . . . 98 B.2. Grupos conflictivos de letras . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102 B.3. Disposición de la correlación cruzada . . . . . . . . . . . . . . . . . . . . . . . 103

16

CAPÍTULO 0 ÍNDICE DE FIGURAS

Ariel Hernán Curiale

1

Introducción En este trabajo se investigó el problema denominado Reconocimiento automático de patentes, o en inglés Automatic License Plate Recognition (ALPR) y se desarrolló un software que automatiza el reconocimiento de las patentes de los vehículos dentro de una imagen. Actualmente existen muchas técnicas, algunas de las cuales se pueden encontrar en la bibliografía [3], [4], [5], [2], [6], [7], [8], [9], [10], [11], [12], [13], [14] y [15] entre otros. El problema de ALPR tiene una gran cantidad de desafíos a resolver. Algunos de ellos son: La iluminación no controlada de la imagen. El brillo de las luces de los automóviles. El ambiente no controlado del fondo. Las condiciones climáticas que modifican la calidad de la imagen. La distorsión de la patente generada por el ángulo en que se capturó la imagen. La oclusión parcial o total de la patente. La oclusión parcial o total de algún caracter. La localización de la patente dentro de la imagen que en muchos casos depende del tipo de vehículo. El reconocimiento óptico de los caracteres. 17

18

CAPÍTULO 1 Introducción

Ariel Hernán Curiale

El primer problema que se abordó fue el brillo en la imagen provocado por las luces de los automóviles de noche. Para resolverlo se tomaron las imágenes con una cámara infrarroja, y se pre-procesaron ecualizando el histograma. De este modo se logró obtener imágenes aptas para los métodos de segmentación utilizados. Para localizar la patente se utilizó una técnica llamada Top Hat junto con un algoritmo basado en las transformadas de Fourier y el algoritmo de Pavlidis para agrupar las regiones. Con estas técnicas se logra localizar la patente y eliminar satisfactoriamente el fondo de la imagen. La mayoría de los métodos propuestos en la bibliografía son dependientes de la iluminación, el tamaño de la imagen y del tipo de patente. En [2] se intenta resolver el problema de la localización a través de la técnica morfológica Top Hat, mientras que en [10] se utiliza una técnica de detección de bordes junto con un filtrado dependiente de la forma de la patente coreana. También se utilizan técnicas basadas en el análisis de las proyecciones horizontales y verticales de los gradientes de la imagen. En la bibliografía se divide este problema en tres etapas: Pre-procesamiento de la imagen completa Segmentación de la patente Identificación de los caracteres (Optical character recognition, OCR) Existen diferentes técnicas para cada etapa en particular, en este trabajo sólo se mencionan las más apropiadas para el problema y las que se utilizaron en el método propuesto. Pre-procesamiento: • Ecualización del Histograma. Segmentación: • Umbralización. • Morfología Matemática. • Filtrado en el dominio de las frecuencias. • Adelgazamiento (Thinning). Identificación de caracteres: • Modelos ocultos de Markov [4]. • Distancia de Hausdorff [2]. • Template Matching [7]. • Redes Neuronales.

Ariel Hernán Curiale

1.0

19

En la etapa de pre-procesamiento se aplican una serie de técnicas con el objetivo de detectar, normalizar y realzar los números de la matrícula. Luego se utilizan técnicas de segmentación y filtrado de falsos positivos para poder diferenciar la patente y los caracteres de la imagen. Finalmente se extraen los caracteres de la patente y se procede al reconocimiento óptico de los caracteres. En la Figura 1.1 se puede observar un esquema con las etapas mencionadas anteriormente.

Figura 1.1: Etapas involucradas en el reconocimiento automático de patentes

El objetivo de este trabajo consiste en resolver el problema de ALPR desarrollando un software capaz de automatizar el reconocimiento de las patentes de los vehículos dentro de una imagen. Asimismo, se buscó independizarse del posicionamiento de la patente, la tipografía, el tamaño y el color de los caracteres. Para la construcción del OCR se decidió utilizar una red neuronal. Sin embargo, se explicaron algunos métodos existentes en la bibliografía que se pueden encontrar en el apéndice B y en [4], [2], [10]. El objetivo de esta tesis no es el análisis y desarrollo del OCR, igualmente se detalla el método utilizado. La tesis se desarrolló de la siguiente manera: La Introducción describe el problema a resolver y las etapas de un ALPR. En el Capítulo 2 se desarrolla la metodología propuesta para resolver el problema de ALPR y en el Capítulo 3 se introduce el método utilizado en el paper de Martín, García y Alba [2], se exponen los resultados de compararlo con el método propuesto y los resultados del método propuesto. En el Capítulo 4 se plantean las conclusiones y luego se da a conocer la bibliografía consultada. En el apéndice A se detallan algunas técnicas que se implementaron

20

CAPÍTULO 1 Introducción

Ariel Hernán Curiale

para intentar resolver APLR que fueron descartadas. En el apéndice B se exponen otras técnicas de OCR, y finalmente en el apéndice C se encuentran los pseudocódigos y algoritmos.

1.1.

Pre-procesamiento de una imagen

El principal objetivo de esta etapa es mejorar la imagen a analizar, con el fin de lograr que sea más apta para resolver el problema. Si bien una técnica puede ser adecuada para mejorar imágenes de rayos x, puede ser inadecuada para una imagen satelital; por esto el pre-procesamiento es completamente dependiente de lo que se quiere lograr con la imagen. Supongamos que la imagen con la que se trabaja es muy oscura, contiene mucho ruido o algunos objetos casi no se perciben. Esto imposibilita el tratamiento directo de la imagen y es necesario mejorarla. Existen varias metodologías para mejorar una imagen, por ejemplo se puede querer quitar el ruido o simplemente desaturar la imagen. Una técnica muy útil para resaltar algunos objetos perdidos dentro de la imagen es la ecualización del histograma.

1.1.1.

Ecualización del histograma

Antes de desarrollar la técnica de ecualización del histograma vamos a introducir la noción del histograma de una imagen. Definición 1.1.1. El histograma de una imagen digital con niveles de gris que van de [0, L − 1] es una función discreta de la forma: h(lk ) =

nk n

, k ∈ [0, L − 1]

(1.1)

Donde lk es el k-ésimo nivel de gris, nk es el número de píxeles de la imagen con ese nivel de gris, n es el número total de píxeles de la imagen y k ∈ [0, L − 1]. Intuitivamente se puede decir que la función h(x) da una idea de la probabilidad que tiene un determinado nivel de gris de aparecer dentro de la imagen. A su vez representa una descripción global de la apariencia de la imagen. En la Figura 1.2 se pueden observar cuatro histogramas proveyendo distinta información sobre la imagen. En el histograma de la Figura 1.2a se muestra que la mayoría de los píxeles están en el sector más oscuro de la escala de grises, ocurriendo lo contrario en la Figura 1.2b. El histograma que se ve en la Figura 1.2c por otra parte muestra que todos los píxeles tienen un valor similar de gris dando una idea de que la imagen tendrá un bajo contraste. Se puede decir lo contrario de la imagen cuyo histograma corresponde a la Figura 1.2d, ya que los niveles de gris están muy dispersos.

Ariel Hernán Curiale

1.1

Pre-procesamiento de una imagen

21

(a) Histograma de una imagen oscura

(b) Histograma de una imagen brillante

(c) Histograma de una imagen con bajo contraste

(d) Histograma de una imagen con alto contraste

Figura 1.2: Histograma de cuatro tipos básicos de imágenes

Esta información es muy útil tanto para entender la imagen a grandes rasgos como para mejorarla. Uno de los métodos más comunes para mejorar la imagen con la información del histograma, se conoce como ecualización del histograma. Al ecualizar el histograma se busca aumentar el contraste de la imagen de la mejor forma. Esto se logra transformando la imagen para que su histograma tenga una distribución uniforme, es decir, se busca que la probabilidad que tiene un determinado nivel de gris en aparecer en la imagen sea la misma para todo el rango de valores de grises. Esta redistribución de los niveles de gris genera un incremento en el rango dinámico, aumentando el contraste de la imagen. Para lograr esto se puede considerar a r como una variable que represente los niveles de gris de la imagen normalizada en el intervalo [0, 1] y para cada r ∈ [0, 1] se utilice la siguiente función

22

CAPÍTULO 1 Introducción

Ariel Hernán Curiale

de transformación: s = T (r)

(1.2)

generando un nuevo nivel de gris s para cada valor del píxel r. Para lograr ecualizar el histograma, es necesario que la función de transformación que se elija preserve el orden entre los niveles de gris y garantice la coherencia de los valores resultantes: T (r) es monótona creciente en el intervalo 0 ≤ r ≤ 1 y es de valor único. 0 ≤ T (r) ≤ 1 para 0 ≤ r ≤ 1. A su vez existe la función de transformación inversa: r = T −1 (s) 0 ≤ s ≤ 1

(1.3)

Donde T −1 (s) también satisface las condiciones anteriores pero respecto a s. Si se consideran los niveles de gris de una imagen como variables aleatorias continuas en el intervalo [0, 1] entonces se podrá, caracterizar a los niveles de gris y su transformada por sus respectivas funciones probabilísticas de densidad pr (r) y ps (s). Si pr (r) y T (r) son conocidas y T −1 (s) verifica las condiciones anteriores, entonces la función de densidad de los niveles de gris transformados quedará determinada por la ecuación: h dr i (1.4) ps (s) = pr (r) ds r=T −1 (s) En particular, si la función de transformación T es la función de distribución acumulada del histograma, entonces se obtiene como resultado una función de distribución uniforme para los valores de sus transformadas. La función de distribución acumulada del histograma es: Z r 0

pr (x)dx

0≤r≤1

(1.5)

Entonces la función para la transformación de la imagen de la ecuación (1.2), quedará de la siguiente forma: Z r

s = T (r) = 0

pr (x)dx

0≤r≤1

(1.6)

Se puede observar que la ecuación (1.6) satisface las propiedades impuestas sobre la función de transformación. Esto se debe a que la función acumulada crece monótonamente en el intervalo [0, 1]. Por otro lado la derivada de s con respecto a r es: ds = pr (r) dr

(1.7)

1.1

Ariel Hernán Curiale

Pre-procesamiento de una imagen

Al sustituir este resultado en la ecuación (1.4) se obtiene: h 1 i ps (s) = pr (r) pr (r) r=T −1 (s) h i ps (s) = 1 −1 (s)

r=T

23

(1.8)

0≤s≤1

ps (s) = 1

Este resultado demuestra que la función de distribución es uniforme en el intervalo de definición de la variable transformada s. Cabe destacar que este resultado es independiente de la función de transformación inversa T −1 , la cual no siempre es fácil de calcular. Para poder aplicar estos conceptos en imágenes digitales, se necesita expresar los resultados anteriores de forma discreta. La probabilidad que tiene un determinado nivel de gris k en aparecer en la imagen es:

Pr (rk ) =

nk n

0 ≤ rk ≤ 1

y

k = 0, 1, . . . , L − 1

(1.9)

Donde: L es el número de niveles de gris Pr (rk ) es la probabilidad del k-ésimo nivel de gris nk es el número de veces que este aparece n es la cantidad total de píxeles Mientras que la forma discreta de la ecuación (1.6) es: k

sk = T (rk ) =

∑ Pr (r j )

0 ≤ rk ≤ 1

y

k = 0, 1, . . . , L − 1

(1.10)

j=0

Si se sustituye la ecuación (1.9) en la ecuación (1.10) se obtiene: k

sk = T (rk ) =

nj j=0 n

∑

(1.11)

De esta forma se puede observar que tanto T (rk ) como T −1 (sk ) cumplen con las propiedades mencionadas anteriormente, obteniendo la misma conclusión que para el caso continuo.

24

CAPÍTULO 1 Introducción

1.2.

Ariel Hernán Curiale

Segmentación de Imágenes

Se trata de un proceso que permite separar a la imagen tal que, todos los elementos pertenecientes al mismo conjunto comparten las mismas propiedades que se tomaron como criterio de separación. Según Sonka [16], consiste en dividir una imagen en partes que tengan una fuerte correlación con los objetos o áreas del mundo real contenidos en la imagen. Para poder reconocer los caracteres dentro de la patente primero se debe aislar la patente del resto de la imagen. Los métodos utilizados están basados en: Filtrado en el dominio de las frecuencias. Umbralización Morfología Matemática.

1.2.1.

Filtrado en el dominio de las frecuencias

En la metodología propuesta, se utilizan algunas características particulares de la imagen en el dominio de las frecuencias para segmentar la patente dentro de la imagen. Para obtener las frecuencias de un objeto dentro de la imagen se aplica la transformada de Fourier. Transformadas de Fourier Es posible interpretar una imagen como una función de dos variables en un plano y una forma de investigar sus propiedades consiste en descomponerla en una combinación lineal de funciones ortonormales. Es por esto que se puede utilizar la transformada de Fourier como una descomposición lineal de la imagen. Se tienen que cumplir varias condiciones para poder hablar de la existencia de la transformada de Fourier y su inversa. Sin embargo en el procesamiento de imágenes es razonable asumir que existen. Definición 1.2.1. La transformada de Fourier de una función f (x, y) queda definida por la siguiente integral: Z ∞Z ∞

F(u, v) =

f (x, y)e−2πi(xu+yv) dxdy,

(1.12)

−∞ −∞

con (u, v) ∈ Dominio de las frecuencias. Definición 1.2.2. La transformada inversa de Fourier de una función F(u, v) queda definida por la siguiente integral: Z ∞Z ∞

f (x, y) = −∞ −∞

F(u, v)e2πi(xu+yv) dudv

(1.13)

1.2

Ariel Hernán Curiale

Segmentación de Imágenes

25

Donde (x, y) denota las coordenadas de la imagen, mientras que las coordenadas (u, v) son las frecuencias espaciales. Si se analiza la ecuación 1.13 se puede interpretar la función f (x, y) como una combinación lineal de e2πi(xu+yv) , donde las componentes reales e imaginarias son las funciones seno y coseno, mientras que F(u, v) es el peso que representa la influencia de e2πi(xu+yv) para una frecuencia determinada u, v. Transformada discreta de Fourier o Discrete Fourier Transform (DFT) Para poder utilizar la transformada de Fourier con funciones discretas se necesita definir la transformada discreta de Fourier. Definición 1.2.3. Sean x0 , . . . , xn−1 números complejos. La transformada discreta de Fourier (DFT) se define como: n−1

fj =

∑ xk e

−2πi n

jk

(1.14)

k=0

Esta definición sirve para calcular la transformada DFT para una secuencia de valores de una sola dimensión. La transformada DFT para un arreglo multidimensional donde n = (n1 , . . . , nd ) y k = (k1 , . . . , kd ) un vector de d dimensiones cuyos índices están entre 0 y N − 1, con N − 1 = (N1 − 1, N2 − 1, . . . , Nd − 1) está definida por: N−1

fk =

∑ e−2πik(n/N)xn

(1.15)

n=0

Donde la división n/N = (n1 /N1 , . . . , nd /Nd ) Trasnformada rápida de Fourier o Fast Fourier Transform (FFT) La transformada rápida de Fourier o FFT es un algoritmo que permite calcular la DFTcon un número menor de operaciones aritméticas. Para calcular la DFT de N números complejos se necesitan realizar O(N 2 ) operaciones aritméticas, mientras que la FFT computa el mismo resultado en tan sólo O(N log N). Para reducir la cantidad de operaciones se procede a separar las muestras en pares e impares calculando para cada una de ellas la FFT. De esta forma se calculan dos FFT con un tamaño de N/2 elementos y se tienen N multiplicaciones complejas. A continuación se puede ver un pseudocódigo del algoritmo. complejo *FFT(complejo *c, orden k) If k==0 ret[0] = c[0] Else cp = pares(c, k)

26

CAPÍTULO 1 Introducción

Ariel Hernán Curiale

ci tp ti de

= impares(c, k) =FFT(cp, k-1) =FFT(ci, k-1) j=0 a 2^k-1 ret[j] = tp[j%2^(k-1)] + exp(-2*PI*j/2^k) * ti[j%2^(k-1)] return ret Convolución Definición 1.2.4. La convolución de dos funciones unidimensionales f (x) y g(x), se define como la función que queda determinada por la siguiente integral, que se denotará ( f ∗ g)(x). ( f ∗ g)(x) =

Z ∞ −∞

f (α)g(x − α)dα

(1.16)

Es posible extender la definición 1.2.4 a funciones bidimensionales de la siguiente forma: ( f ∗ g)(x, y) =

Z ∞Z ∞ −∞ −∞

f (µ, ν)g(x − µ, y − ν)dµdν

(1.17)

En el caso de utilizar funciones discretas es necesario modificar la ecuación 1.17 de la siguiente forma: ∞

( f ∗ g)(x, y) =

∞

∑ ∑

f ( j, i)g(x − j, y − i)

(1.18)

j=−∞ i=−∞

Al trabajar con imágenes o señales discretas, es posible interpretar la convolución como la suma ponderada de los píxeles en la vecindad del píxel tomado como referencia. Es común utilizar una matriz de tamaño NxN con N impar, ya que permite elegir fácilmente un punto central que será el valor del píxel de salida. La convolución gráficamente consiste en deslizar la reversa de la matriz o ventana por toda la imagen computando las sumas ponderadas con los valores de la matriz. En la Figura 1.3 se puede observar este proceso. Un problema común ocurre al centrar la matriz de convolución sobre los bordes de la imagen como se muestra en la Figura 1.4.

1.2.2.

Umbralización

Si se tiene una imagen compuesta por objetos muy claros sobre un fondo oscuro, ésta tendrá asociado un histograma como el de la Figura 1.5. Se puede deducir que es posible separar los niveles de gris en al menos dos grupos, donde cada grupo va a representar un tipo de objeto y uno de ellos corresponderá al fondo. Una forma simple de distinguir entre los objetos y el fondo, es elegir un umbral T que los separe. Para determinar si un punto (x, y) forma parte del objeto a distinguir, se observa su nivel de gris f (x, y) y si es superior al valor seleccionado como umbral T , entonces se dirá que este

Ariel Hernán Curiale

1.2

Segmentación de Imágenes

Figura 1.3: Ejemplo de una convolución

Figura 1.4: Ejemplo del problema de la convolución

27

28

CAPÍTULO 1 Introducción

Ariel Hernán Curiale

Figura 1.5: Histograma de una imagen que se pueden dividir con un umbral simple

punto pertenece al objeto. Y en el caso contrario pertenecerá al fondo de la imagen. Por otro lado si se busca segmentar varios objetos, se deberían considerar varios umbrales. Por ejemplo si se quieren distinguir dos objetos del fondo, será necesario establecer dos umbrales T1 y T2 , donde cada punto (x, y) pertenece al objeto O1 si T1 < f (x, y) < T2 , al objeto O2 si f (x, y) ≥ T2 y el resto de los puntos que son inferiores o iguales al nivel de T1 pertenecen al fondo. Este tipo de umbralización se denomina Umbralización multinivel y el proceso para obtener buenos umbrales (T1 y T2 ) suele ser complejo. Se puede entender a la umbralización como una operación que realiza comprobaciones frente a una función T : T = T [x, y, p(x, y), f (x, y)] (1.19) Donde f (x, y) es el nivel de gris del punto (x, y) y p(x, y) representa una propiedad local de este punto. Por ejemplo se puede tomar una vecindad y calcular el nivel de gris promedio. Definición 1.2.5. Una imagen g está umbralizada según el umbral T si para todo píxel f (x, y) se cumple que:  1 si f (x, y) > T g(x, y) = (1.20) 0 si f (x, y) ≤ T De esta forma aquellos píxeles en 1 (o con cualquier otro nivel de intensidad) pertenecen al objeto de la imagen, mientras que los píxeles en cero pertenecerán al fondo. En particular si el nivel de intensidad es marcado con 1 y 0, se está frente a la binarización de la imagen. Observando la definición 1.2.5 y la ecuación 1.19, se pueden categorizar tres tipos de umbralización dependiendo de las variables que intervengan en la fórmula: Global: si la función que determina el umbral (T ) sólo depende del nivel de gris del punto en cuestión, f (x, y). Local: si depende de f (x, y) y p(x, y). Dinámico: si depende de las coordenadas espaciales del punto en cuestión (x, y) y además de f (x, y) y de p(x, y).

1.2

Ariel Hernán Curiale

Segmentación de Imágenes

29

Uno de los grandes problemas de la umbralización es la iluminación. Si las condiciones de iluminación no se encuentran controladas, se torna imposible aplicar algún tipo de discriminante. Esto dificulta la selección de un buen umbral para segmentar los objetos, ya que los mismos comienzan a mezclarse. La forma más simple de umbralizar una imagen, y en particular la que se utilizó en este trabajo consiste en dividir el histograma en dos, utilizando un umbral único T . Luego se escanea la imagen para poder separar los elementos que pertenecen al fondo. En la Figura 1.6 se puede ver un ejemplo donde la función que determina el nivel de gris de la imagen umbralizada es:  1 si f (x, y) > 126 (1.21) g(x, y) = 0 si f (x, y) ≤ 126 Donde 126 es el nivel del umbral seleccionado.

(a) Imagen original

(b) Umbralización simple con T = 126

(c) Histograma y nivel de umbralización de la Figura 1.6a

Figura 1.6: Ejemplo de una umbralización simple con un umbral T = 126

Se puede ver que la dificultad de esta técnica es la selección de un buen umbral.

1.2.3.

Morfología Matemática

Un poco de historia La descripción básica de la Morfología Matemática está sustentada en la teoría de conjuntos y las primeras personas que incursionaron en este tema fueron Minkowski [17], [18] y Hadwiger [19],[20]. Esta metodología recién toma un gran impulso con las reformulaciones de Matheron [21], [22] y Serra [23] , las cuales posteriormente se dieron a conocer bajo el nombre de Morfología Matemática. Una de las características principales es que se trata de una técnica no lineal para el tratamiento de señales.

30

CAPÍTULO 1 Introducción

Ariel Hernán Curiale

La mayor parte de esta teoría ha sido desarrollada en el Centre de Morphologie Mathématique (CMM) de l’Ecole des Mines de París. Actualmente el alcance del procesamiento morfológico es tan amplio como el propio procesamiento de imágenes. En el procesamiento morfológico se pueden encontrar aplicaciones tales como la segmentación, restauración, detección de bordes, aumento de contraste, análisis de texturas, compresión, etc. En las obras [21], [22] y [23] se pueden hallar en mayor detalle los conceptos básicos de la Morfología Matemática y la teoría de conjuntos que trataremos a continuación.

Nociones sobre teoría de conjuntos Definición 1.2.6. El complemento de un conjunto X, incluido en un conjunto Y (conjunto de referencia) se define como: X c = {p | p ∈ / X ∧ p ∈ Y}

(1.22)

Definición 1.2.7. Se dirá que el conjunto no vacío X, tiene un orden parcial, si existe una relación binaria ≤ en X que cumple con las siguientes propiedades: x ≤ x (reflexiva) x ≤ y, y ≤ x, implica que x = y (antisimétrica) x ≤ y, y ≤ z, implica que x ≤ z (transitiva) Para cualquier x, y, z ∈ X. Un conjunto con una relación de este tipo será un conjunto que posee un orden parcial y se denotará como (X, ≤). El conjunto poseerá un orden total si todos los elementos que lo componen son comparables, es decir: x ≤ y o y ≤ x, para cualquier par (x, y) ∈ X. Definición 1.2.8. Se puede considerar a una imagen binaria como una función de la siguiente forma: f : R2 → {0, 1} Definición 1.2.9. Una imagen en escala de grises I está definida por el mapeo de un subconjunto limitado DI ⊂ R2 en R. Donde DI es el dominio de la imagen I. Esto significa que se cumple: I : DI ⊂ R2 → R

con p ∈ DI y I(p) ∈ R

Definición 1.2.10. Se define al operador o transformación binaria ψ como un mapeo de P (R2 ) en P (R2 ):

1.2

Ariel Hernán Curiale

Segmentación de Imágenes

31

ψ : P (R2 ) → P (R2 ) Donde: P (R2 ) es partes de R2 . Es decir el operador o transformación ψ toma una imagen binaria (en escala de grises) y la transforma en otra imagen binaria (en escala de grises). Definición 1.2.11. Se puede decir que ψ es una transformación extensiva si y sólo si para todo conjunto X, X ⊆ ψ(X). De forma análoga se dice que ψ es una transformación antiextensiva si y sólo si, para todo conjunto X, ψ(X) ⊆ X. Definición 1.2.12. Se puede decir que ψ es una transformación incremental si y sólo si preserva la relación de inclusión de la siguiente forma: X ⊆ Y ⇒ ψ(X) ⊆ ψ(Y )

(1.23)

Definición 1.2.13. Se puede decir que ψ es una transformación idempotente si el resultado de aplicarla una vez es el mismo que aplicarla una serie de veces. ∀X, ψ(ψ(X)) = ψ(X) 0

(1.24) 0

Definición 1.2.14. Si se considera ψ otro operador, entonces se puede decir que ψ y ψ son 0 duales, si el complemento de aplicar ψ al conjunto X da el mismo resultado que aplicar el ψ al complemento de X. Esto es: 0

ψ(X)c = ψ (X c )

(1.25)

En esta definición se entiende a X c como R2 \ X, la cual es una extensión de la definición 1.2.6. Para extender esta definición a una imagen con escala de grises se utiliza la definición de orden parcial 1.2.7. De esta manera se puede definir el complemento de una función f : R2 → R como − f . Operadores básicos de la morfología en el caso binario Los operadores básicos morfológicos se definen en función de un elemento estructurante. Se puede decir que un elemento estructurante es un conjunto particular B ⊂ R2 que usualmente es pequeño y de una forma simple (un cuadrado, rectángulo, círculo, etc). Definición 1.2.15. Se define a Bx como la translación del elemento B por x de la siguiente forma: Bx = {b + x | b ∈ B} con x ∈ R2

(1.26)

32

CAPÍTULO 1 Introducción

Ariel Hernán Curiale

El centro del elemento estructurante es un concepto importante ya que éste es el que define la orientación de la translación. Aplicando estos conceptos se pueden definir los operadores básicos de la morfología matemática. Estos operadores se conocen con el nombre de erosión y dilatación. Como sus nombres lo indican, estos operadores consisten en adelgazar o engrosar una región en la imagen binaria dependiendo de las características del elemento estructurante. Definición 1.2.16. La dilatación de un conjunto X ⊂ R2 por un elemento estructurante B, el que se denota δB (X), es el conjunto de puntos x ∈ R2 tal que la translación de B por x tiene una intersección no vacía con el conjunto X. δB (X) = {x ∈ R2 | X ∩ Bx 6= φ}

(1.27)

Otra forma de definir la dilatación es utilizando la suma de Minkowski [17], como se muestra en la definición 1.2.17. Definición 1.2.17. Sean X e Y dos conjuntos pertenecientes al conjunto Z. Para todo elemento x ∈ X e y ∈ Y , es posible hacer corresponder una suma algebraica x + y. De esta manera se forma un nuevo conjunto denominado adición de Minkowski, denotado por X ⊕Y : X ⊕Y = {x + y | x ∈ X, y ∈ Y }

(1.28)

ˇ Se puede probar que la dilatación de X por B, es igual a la suma de Minkowski de X ⊕ B, donde Bˇ es el conjunto transpuesto de B, es decir Bˇ se obtiene al rotar 180◦ a B. Bˇ = {−b | b ∈ B}

(1.29)

Muchos autores definen la dilatación como la suma de Minkowski omitiendo la rotación del elemento estructurante, esto se debe a que en la mayoría de los casos el elemento estructurante ˇ B es simétrico respecto al origen, con lo cual B = B. El efecto de una dilatación puede observarse en la Figura 1.7 donde un elemento estructurante Y de forma de disco circular aumenta al objeto X. Otro ejemplo de una dilatación se puede ver en la Figura 1.8, en donde se aplica a la imagen una dilatación con un elemento estructurante cuadrado de 3x3 píxeles. Definición 1.2.18. La erosión de un conjunto X ⊂ R2 por un elemento estructurante B, que se denotará εB (X), es el conjunto de puntos x ∈ R2 tal que la translación de B por x queda completamente incluida en el conjunto X: εB (X) = {x ∈ R2 | Bx ⊂ X}

(1.30)

1.2

Ariel Hernán Curiale

Segmentación de Imágenes

33

Figura 1.7: En la Figura b) se puede observar el resultado de dilatar al objeto X con el elemento estructurante Y. Imagen extraída de [1]

(a) Imagen Original

(b) Imagen luego de dilatar

Figura 1.8: Ejemplo de una dilatación en una imagen binaria utilizando un elemento estructurante de 3x3 píxeles.

De forma análoga se puede definir la erosión en función de la sustracción de Minkowski. Definición 1.2.19. La erosión expresada en función de la sustracción de Minkowski se define de la siguiente manera: ˇ x − b ∈ X} εB (X) = X Bˇ = {x ∈ R2 | ∀b ∈ B,

(1.31)

Dicho de otra forma la erosión de un conjunto X por un elemento estructurante B, es el conjunto de puntos de X tal que al trasladar el elemento estructurante B por los puntos de Xquedan completamente incluidos en el conjunto original. El efecto de una erosión se puede observar en la Figura 1.9, donde un elemento estructurante Y de forma de disco circular hace desaparecer los elementos de menor tamaño que él. Otro ejemplo se puede observar en la Figura 1.10, donde se erosiona una patente con un elemento estructurante cuadrado de 2x2 píxeles.

Figura 1.9: Resultado de erosionar al objeto X con el elemento estructurante Y. Imagen extraída de [1]

34

CAPÍTULO 1 Introducción

Ariel Hernán Curiale

(a) Imagen Original

(b) Imagen luego de erosionar

Figura 1.10: Ejemplo de una erosión en una imagen binaria utilizando un elemento estructurante de 2x2 píxeles.

Intuitivamente se puede ver que la dilatación completa los huecos existentes en la imagen y la erosión los agranda. La forma en la que se completan o agrandan depende del objeto estructurante que se utilice a la hora de hacer la dilatación o erosión. Las siguientes propiedades resultan interesantes para desarrollar algoritmos más eficientes a la hora de computar la erosión o dilatación: 1. La erosión y dilatación son operadores incrementales. X ⊆ Y ⇒ εB (X) ⊆ εB (Y ) ∧ δB (X) ⊆ δB (Y )

(1.32)

2. La erosión y dilatación son operaciones duales. εB (X) = [δB (X c )]c δB (X) = [εB (X c )]c

(1.33) (1.34)

3. Cuando el elemento estructurante contiene un centro se puede decir que la erosión por B es anti-extensiva y que la dilatación es extensiva. ~o ∈ B ⇒ εB (X) ⊆ X ∧ X ⊆ δB (X)

(1.35)

4. La unión es distributiva respecto de la dilatación pero no respecto de la erosión. δB (X ∪Y ) = δB (X) ∪ δB (Y ) εB (X ∪Y ) 6= εB (X) ∪ εB (Y )

(1.36) (1.37)

5. La intersección es distributiva respecto de la erosión pero no respecto de la dilatación. εB (X ∩Y ) = εB (X) ∩ εB (Y ) δB (X ∩Y ) 6= δB (X) ∩ δB (Y )

(1.38) (1.39) (1.40)

6. Combinación del elemento estructurante. δB1 ⊕B2 (X) εB1 ⊕B2 (X) δB1 ∪B2 (X) εB1 ∪B2 (X)

= = = =

δB1 (δB2 (X)) = δB2 (δB1 (X)) εB1 (εB2 (X)) = εB2 (εB1 (X)) δB1 (X) ∪ δB2 (X) εB1 (X) ∩ εB2 (X)

(1.41) (1.42) (1.43) (1.44)

Ariel Hernán Curiale

1.2

Segmentación de Imágenes

35

Extensión de la dilatación y la erosión a imágenes en escala de grises En la ecuación (1.32) se comentó que la erosión y la dilatación eran operadores incrementales. Por esto es posible extender la definición de estos operadores a imágenes en escala de grises. Es necesario definir el operador de umbralización para extender las definiciones de los operadores morfológicos antes mencionados. Definición 1.2.20. Sea I una imagen en escala de grises. Definimos Th al operador de umbralización para el nivel h de la siguiente forma: Th (I) = {p ∈ DI | I(p) ≥ h}

(1.45)

Si se tiene un operador binario incremental morfológico ψ, entonces se puede extender este operador a la escala de grises de la siguiente forma: ψ(I)(p) = sup{h | p ∈ ψ(Th (I))}

(1.46)

Se puede pensar que la forma de aplicar un operador morfológico binario en una imagen en escala de grises, es aplicar el operador morfológico ψ en todas las capas determinadas al umbralizar en todo el rango de gris y quedarse con el mínimo valor del conjunto que lo acota superiormente. Para un análisis más exhaustivo de este tema (threshold decomposition o threshold superposition) ver [24]. Con este principio se extiende la definición de la erosión y dilatación de la siguiente forma: Definición 1.2.21. La dilatación y erosión de una imagen I en escala de grises, respecto de un elemento estructurante B para el píxel x ∈ DI está dada por la siguiente ecuación: δB (I)(x) = sup{I(p) | p ∈ Bx } εB (I)(x) = in f {I(p) | p ∈ Bx }

(1.47) (1.48)

En [25] se presenta en detalle la generalización de los operadores morfológicos a imágenes en escala de grises con la noción de umbral. Una forma de entender las ecuaciones (1.47) y (1.48) puede ser la siguiente: Recordando la definición de la dilatación en la ecuación (1.27), y teniendo en cuenta al conjunto de píxeles resultantes de aplicar la umbralización, se necesita tener el máximo valor que toma el píxel en la imagen al ser trasladado por B para tener la dilatación de la imagen. O sea el resultado en cada punto de la imagen es el mayor valor que éste puede tomar dentro del elemento estructurante B. De este análisis se puede observar que al realizar una dilatación se ponderan aquellos elementos más claros por sobre los más oscuros. Esto se puede ver en la Figura 1.11. De forma análoga en la erosión se buscan los valores más pequeños de la imagen. En la figura 1.12 se puede observar un ejemplo.

36

CAPÍTULO 1 Introducción

Ariel Hernán Curiale

(a) Imagen original

(b) Imagen luego de aplicar una dilatación con un elemento estructurante de 3x3

Figura 1.11: Ejemplo de una dilatación en una imagen en escala de grises.

Apertura y cierre (Opening and Closing) La apertura y el cierre son los operadores más utilizados en morfología matemática. Se debe tener en cuenta que las siguientes definiciones sólo son válidas para el caso de imágenes binarias. Definición 1.2.22. Se define al operador de Apertura de un conjunto X con un elemento estructurante B como: γB (X) = δBˇ (εB (X))

(1.49)

El cual se nota: X ◦ B Definición 1.2.23. Se define al operador de Cierre de un conjunto X con un elemento estructurante B como: φB (X) = εBˇ (δB (X))

(1.50)

El cual se nota: X B Gracias a la propiedad incremental definida en la ecuación (1.32), se puede extender las definiciones 1.2.22 y 1.2.23 a imágenes en escalas de grises manteniendo la misma notación. En [25] se presenta detalladamente la generalización de los operadores morfológicos a imágenes de escala de grises, utilizando la noción de umbral. La apertura y el cierre son independientes del origen del elemento estructurante. Esto se debe a que en la apertura la erosión se corresponde con una intersección de translaciones y la dilatación que le sigue se corresponde con una unión de las translaciones en dirección opuesta. Para el operador de cierre ocurre algo similar. El tamaño y la forma del elemento estructurante es fundamental porque determina los objetos de la imagen a eliminar. Al elegir un elemento estructurante demasiado grande se eliminan formas no deseadas, pero a la vez se afectan notablemente los demás objetos dentro de la imagen.

1.2

Ariel Hernán Curiale

Segmentación de Imágenes

37

(a) Imagen Original

(b) Imagen luego de aplicar una erosión con un elemento estructurante de 3x3

Figura 1.12: Ejemplo de una erosión en una imagen en escala de grises.

Los tamaños pequeños serán los óptimos cuando se quiera conservar los detalles de la imagen. El efecto de realizar una apertura y un cierre se puede ver en las Figuras 1.13. Algunas propiedades de los operadores de Apertura y Cierre 1. La apertura y el cierre son operadores duales respecto a la complementación. γB (X) = φB (X c )c

(1.51)

Esto se puede demostrar de la siguiente forma: φB (X c )c = εBˇ (δB (X c ))c = εBˇ (εB (X)c )c = (δBˇ (εB (X))c )c = δBˇ (εB (X)) = γB (X) (1.52) 2. La erosión de una apertura es igual a la erosión de la imagen. Lo mismo ocurre para la dilatación y el cierre. εB (δB (εB (X))) = εB (X) δB (εB (δB (X))) = δB (X)

(1.53) (1.54)

3. Las operaciones de apertura y cierre son transformaciones crecientes e idempotentes. Creciente: Sea f ≤ g ⇒ γB ( f ) ≤ γB (g) Sea f ≤ g ⇒ φB ( f ) ≤ φB (g) Donde f y g son dos imágenes en escala de grises.

(1.55) (1.56)

38

CAPÍTULO 1 Introducción

(a) Imagen Original

Ariel Hernán Curiale

(b) Imagen luego de aplicar una apertura a la imagen original

(c) Imagen luego de aplicar un cierre a la imagen original

Figura 1.13: Ejemplo de una apertura y cierre sobre una imagen en escala de grises.

Idempotencia: Por las propiedades (1.53) y (1.54) se puede demostrar la idempotencia en la apertura y el cierre con un elemento estructurante simétrico Bˇ = B. γB (γB (X)) = δBˇ (εB (δBˇ (εB (X)))) = δBˇ (εB (X)) = γB (X) φB (φB (X)) = εBˇ (δB (εBˇ (δB (X)))) = εBˇ (δB (X)) = φB (X)

(1.57) (1.58)

1.2

Ariel Hernán Curiale

Segmentación de Imágenes

39

Top Hat Una gran variedad de filtros pueden ser creados a partir del uso de los operadores morfológicos de apertura y cierre. Según Serra [23], un filtro morfológico es cualquier transformación no lineal en un retículo completo, creciente e idempotente. El requerimiento de creciente es fundamental para asegurar la conservación del orden del retículo después del filtrado. De todos los filtros existentes se hará hincapié en uno de ellos, el cual es muy utilizado para la segmentación de objetos. Este filtro es conocido como Top Hat y fue propuesto originalmente por Mayer en 1978 [26]. Este filtro consiste en recuperar los objetos de la imagen que fueron eliminados por la apertura y cierre. Estos objetos serán muy dependientes del elemento estructurante seleccionado. Este filtro es una poderosa herramienta para separar los objetos con más brillo o los más oscuros de la imagen. Formalmente se puede definir al filtro Top Hat de la siguiente manera: Definición 1.2.24. Sea I una imagen en escala de grises, se define a la transformación Top Hat respecto a la apertura γ, de la siguiente forma: T Hγ (I) = I − γ(I)

(1.59)

Se puede ver al Top Hat como el residuo entre la identidad y la apertura morfológica. Al igual que la apertura, el Top Hat es una operación antiextensiva e idempotente, pero no creciente. Este filtro también es conocido como Top Hat por apertura o Top Hat blanco, debido a que destaca los objetos más claros de la imagen. Una operación dual al Top Hat por apertura es el Top Hat por cierre o Top Hat Negro. Definición 1.2.25. Sea I una imagen en escala de grises, se define a la transformación Top Hat respecto al cierre φ, de la siguiente forma: T Hφ (I) = φ(I) − I

(1.60)

Este filtro se utiliza para extraer los objetos oscuros de la imagen. En la Figura 1.14 se observa un ejemplo de este filtro. Según la definición del filtro Top Hat 1.2.24, si se resta la imagen 1.14a a la resultante de aplicarle una apertura 1.14b, se obtiene como resultado la imagen 1.14c. Esta imagen se puede binarizar fácilmente, como se observar en la Figura 1.14d.

1.2.4.

Thinning o adelgazamiento

El thinning o adelgazamiento es otro tipo de operación morfológica que permite adelgazar los objetos a un píxel de ancho. Lo interesante de esta operación es que preserva la topología

40

CAPÍTULO 1 Introducción

Ariel Hernán Curiale

(a) Imagen Original

(b) Imagen luego de aplicar una apertura

(c) Imagen luego de aplicar el filtro Top Hat a la imagen original (b − a)

(d) Imagen luego binarizar el resultado de aplicar el filtro Top Hat a la imagen original

Figura 1.14: Ejemplo de aplicar el filtro Top Hat sobre una imagen en escala de grises.

respetando la conectividad. Antes de continuar es necesario definir el concepto del número de conectividad de un píxel y de endpoint. Definición 1.2.26. El número de conectividad de un píxel en la vecindad S, es una medida que permite tener una noción de cuantos objetos están conectados a un píxel particular. Cn =

∑ Nk − (Nk ∗ Nk+1 ∗ Nk+2)

(1.61)

k∈S

Donde: Nk es el valor de uno de los ocho píxeles vecinos (que puede ser 1 o 0). N0 es el del píxel central y N1 es el valor del píxel a la derecha del píxel central y el resto de los píxeles están numerados en el sentido horario. En la Figura 1.15 se ilustra el número de conectividad, donde a) representa a una conectividad de 0. b) representa una conectividad de 1 y el píxel central puede ser borrado sin afectar la

1.2

Ariel Hernán Curiale

Segmentación de Imágenes

41

conectividad de la izquierda y la derecha. c) representa un número de conectividad = 2, el borrar el píxel central desconectará ambos lados. d) representa un número de conectividad = 3, y e) representa un número de conectividad = 4.

Figura 1.15: Ejemplo del número de conectividad para un píxel.

Definición 1.2.27. Se considera a un píxel como endpoint, si está conectado sólo a un píxel. Es decir si un píxel blanco sólo tiene a uno de sus ocho vecinos en blanco. Un algoritmo posible para realizar esta operación sobre imágenes binarias es el siguiente: Para producir el adelgazamiento se tomarán cuatro tipo de casos a analizar. Estos casos quedan determinados por las siguientes plantillas: T1 x 0 x x 1 x x 1 x

T2 x x x 0 1 1 x x x

T3 x 1 x x 1 x x 0 x

T4 x x x 1 1 0 x x x

A continuación se describen los pasos a seguir para realizar el adelgazamiento. 1. Primero se busca la posición (i, j) de un píxel en la imagen que esté en 1 (porque la imagen es binaria), comenzando de izquierda a derecha y de arriba hacia abajo 1 , que coincida con la plantilla T1. El objetivo de este paso es encontrar todos los píxeles de la parte superior del objeto analizado. 2. Si el píxel central no es un endpoint, y tiene un número de conectividad = 1 según la definición 1.2.26, entonces debe ser borrado. 3. Se repite el paso 1 y 2 para todos los píxeles que concuerdan con la plantilla T1. 4. Una vez que se examinó toda la imagen en busca de los píxeles que concuerdan con la plantilla T1, se repiten los pasos del 1 al 3 para el resto de las plantillas. El objetivo de la plantilla T1, es identificar a aquellos píxeles de la parte superior en la imagen al moverse de izquierda a derecha y de arriba hacia abajo. En el caso de T2, se buscan aquellos píxeles del lado izquierdo del objeto al moverse de abajo hacia arriba y de 1 El

sentido de la búsqueda de los píxeles para compararlos con T1, T2, T3 o T4 es dependiente de la plantilla.

42

CAPÍTULO 1 Introducción

Ariel Hernán Curiale

izquierda a derecha. Mientras que en T3 se identifican los elementos del fondo del objeto moviéndose de derecha a izquierda y de arriba hacia abajo. Por último en T4 se obtienen aquellos píxeles de la parte derecha moviéndose de arriba hacia abajo y de derecha a izquierda. 5. Como último paso se ponen en negro todos los píxeles a borrar.

1.3.

Identificación de los Caracteres

Comúnmente la identificación de caracteres en una imagen está relacionada o asociada al Optical Character Recognition o simplemente OCR. El OCR es un mecanismo que convierte los caracteres alfanuméricos impresos o mecanografiados en archivos legibles por máquina sin necesidad de digitarlos. El reconocimiento de caracteres suele utilizarse para digitalizar libros o formularios rellenos a mano, pero en este caso se necesita para identificar los caracteres de la patente. El OCR consta de tres etapas: Pre-procesamiento de la imagen. Segmentación de los caracteres. Reconocimiento o identificación del caracter. Existe una gran cantidad de metodologías disponibles que resuelven el problema del reconocimiento óptico. No todas ellas se pueden aplicar al problema de ALPR, debido a que las condiciones de los caracteres y el fondo son muy diferentes a los encontrados en un libro. En el apéndice B se detallan tres metodologías utilizadas en la bibliografía para resolver el problema de reconocimiento óptico de los caracteres. Estas metodologías son: Modelos Ocultos de Markov [4] Distancia de Hausdorff [2] Template Matching [10] El objetivo de esta tesis no es el análisis y desarrollo del OCR, igualmente se detalla a continuación el método utilizado.

Ariel Hernán Curiale

1.3.1.

1.3

Identificación de los Caracteres

43

Redes Neuronales Artificiales

Introducción Las redes neuronales reproducen el comportamiento de los sistemas nerviosos biológicos. Estos sistemas están constituidos por un conjunto de neuronas conectadas entre sí. Se podría interpretar las redes neuronales como máquinas que modelan la forma que el sistema nervioso de un ser vivo realiza una tarea determinada. Cada neurona recibe como entrada un conjunto de señales discretas o continuas, las cuales pondera o integra para transmitir el resultado a las neuronas conectadas a ella. Cada conexión entre dos neuronas tiene un valor asociado que determina el peso de esa transición. A este valor se lo denomina peso sináptico. Estos pesos tienen la mayor parte del conocimiento de la red neuronal sobre una determinada tarea. El principal método de aprendizaje consiste en modificar los pesos de la red neuronal. Otro método podría ser mediante la modificación del número de neuronas o la forma en que se conectan. El primer modelo sobre las redes neuronales fue planteado por McCulloch y Pitts [27]. Este trabajo también introdujo la teoría de autómatas finitos como modelo computacional. Pero unos años después Kleene (1956) [28] reformuló estos resultados introduciendo una notación más compacta y general, definiendo el concepto de expresión regular. A partir de esta reformulación el campo de las redes neuronales y la teoría de lenguajes comenzaron a separarse. La teoría de lenguajes relegó a las redes neuronales que a comienzo de los ochenta volvieron a tomar impulso. Algunas características que poseen las redes neuronales son las siguientes: Son fácilmente paralelizables. Poseen una gran capacidad de generalización. Pueden ser lineales y no lineales, esto es importante al momento de modelizar sistemas generados mediante reglas no lineales. Las redes neuronales son capaces de adaptarse fácilmente a los cambios del ambiente. Son tolerantes a fallas, ya que un desperfecto en un sector de la red sólo la afecta parcialmente. Cada neurona está compuesta por cinco elementos: Un conjunto de n señales de entrada que proveen a la neurona los datos del entorno. Estos datos pueden ser externos a la red neuronal o provenir de otras neuronas vecinas. Un conjunto de sinapsis wi j , caracterizada cada una por un peso. Un sesgo w j cuya presencia aumenta o disminuye la entrada y modifica la capacidad de procesamiento de la neurona.

44

CAPÍTULO 1 Introducción

Ariel Hernán Curiale

Un sumador o integrador el cual suma las señales de entrada ponderadas con su respectivo peso y sesgo. Una función de activación que suele limitar la amplitud de salida. Normalmente todas las neuronas usan la misma función de activación. Para poder definir el nuevo valor de activación que tiene una neurona, primero es necesario contar con las entradas de activación multiplicadas por sus respectivos pesos. n

ini =

∑ wi j a j + wi

(1.62)

j=1

Donde a j es la entrada que recibe la neurona i y wi es el sesgo. El valor de activación de la neurona i se obtiene aplicando la función de activación g. ! n

ai = g (ini ) = g

∑ wi j a j + wi

(1.63)

j=1

De aquí en más, se tomará al sesgo de una neurona como un peso más de la red, considerando de la misma forma a wi j como a w j . La función de activación es la que define realmente la salida de una neurona. Las más comunes son: 1. Función Identidad. gI (x) = x

(1.64)

2. Función Escalón o Función de Heaviside.  gE (x) =

1 x≥0 0 x= alto. Entonces toda región que no tenga esta proporción entre su alto y ancho será descartada. 3. La cantidad de píxeles que tiene un caracter en la frontera está relacionada con el área del mismo. La altura de un caracter tiene que ser menor a la mitad de la cantidad de píxeles que tiene en la frontera una región para ser considerada un caracter válido. 4. Se eliminan como posibles caracteres a las regiones demasiado pequeñas que cumplían las condiciones anteriores. Una región debe tener al menos 20 píxeles en la frontera para ser considerada como un caracter.

Ariel Hernán Curiale

2.3

Segmentación

69

Clusters Se puede definir a un cluster como el conjunto de regiones cuya distancia entre sí es relativamente pequeña. De esta forma se define el concepto de regiones conectadas como dos regiones cuya separación entre sí es relativamente pequeña. Para determinar si dos regiones están conectadas se utiliza el siguiente procedimiento: 1. En base al centro de las regiones analizadas se calcula la distancia euclidiana entre ambas regiones la cual se notará como dist. 2. Se calcula el tamaño de las regiones tomando para cada una los cuatro píxeles (x1 , y1 ), (x2 , y2 ), (x1 , y2 ), (x2 , y1 ) que encierran la totalidad de la región, con la siguiente ecuación p (x1 − x2 )2 + (y1 − y2 )2 . 3. Se consideran dos regiones cercanas si: dist < 1,5 ∗ min(tam1 ,tam2 ) donde tam1 ,tam2 son los tamaños respectivos de las regiones. 4. Si las regiones están cerca pertenecen al mismo cluster. Otra distancia que se podría haber tomado es dist = miny∈Ri ,x∈R j {d(x, y)} donde Ri y R j son las dos regiones a las cuales se le quiere calcular la distancia y d(x, y) es la distancia euclidiana. Pero se decidió utilizar solamente la distancia euclidiana entre los centros de las dos regiones, porque al tomar la distancia desde el centro el ancho de forma implícita fue significativo. De esta forma se puede determinar cuando dos regiones están conectadas, y se puede determinar cuando una región cualquiera r tiene que unirse a un cluster Cx . Entonces se dice que r ∈ Cx si ∃r0 ∈ Cx tal que r0 , r son componentes conectadas. Criterio de expansión de un cluster No se puede garantizar que la patente esté dentro de un cluster, pero se puede asegurar que al menos un píxel perteneciente a la patente sobrevivió al proceso de segmentación y por consiguiente está dentro de algún cluster. Es posible que el único píxel perteneciente a la patente sea el que se encuentre en una de las cuatro esquinas. Entonces si se expande el cluster en el ancho promedio de una patente para cada lado (izquierda y derecha) y se hace lo mismo para el alto, se puede garantizar que en un cluster estará la patente. Para que se logre este objetivo es necesario expandir los clusters con el siguiente criterio: Cada cluster se expande en 80 píxeles para la derecha y la izquierda. Luego se expande en 25 píxeles para arriba y para abajo. Al realizar esta expansión en todos los clusters el tamaño de cada uno aumenta notablemente y es necesario procesar nuevamente a cada uno de los clusters para poder segmentar los caracteres de forma óptima.

70

CAPÍTULO 2 El método de ALPR propuesto

2.3.2.

Ariel Hernán Curiale

Filtrado de patentes falsamente detectadas

Una vez que se obtienen los clusters expandidos, se necesita filtrar a aquellos que no contienen la patente. Antes de filtrar los clusters, se ajusta el tamaño de cada uno con el objetivo de compararlos y determinar cual de ellos contiene a la patente. En el mejor de los casos el cluster que tiene la patente puede ser reducido al tamaño exacto de la patente. Esto no siempre es posible pero se intenta ajustar al tamaño de la patente más cercano . Una vez que se ajustaron los tamaños de los clusters se está en condición de filtrar aquellos que no contienen a la patente. Todo este proceso involucra los siguiente pasos: 1. Se recorta de la imagen original la región de interés. Se trabaja con la imagen original porque la imagen pre-procesada sufrió un desgaste importante. 2. La imagen es convertida a NTSC. 3. Se le aplica el método Top Hat a la imagen del punto anterior. 4. Se ecualiza el histograma. 5. Se la binariza con un umbral del 95 %2 . 6. Se aplica el algoritmo modificado de FFT comentado en la sección 2.3 7. Se calcula para cada cluster el valor máximo de la transformada FFT en los índices 6, 7 y 8. El primer filtro consiste en descartar a todos los clusters que están por debajo del valor máximo en unos 200. Este número es el que mejor se ajustó a las muestras trabajadas. 8. Luego se ajustan los clusters resultantes del paso anterior con el objetivo de encerrar mejor a la patente. Para esto se toman las imágenes resultantes del paso 5 y se proyectan todos los píxeles sobre el eje horizontal y el vertical. 9. Con el top Hat se consigue eliminar el recuadro de la patente y otros objetos que están dentro de la región que no tienen relación alguna con un caracter. Si se interpreta el resultado de la proyección horizontal, se sabe que la patente comienza en el primer pico de píxeles en blanco. De esta forma se logra encerrar correctamente la patente, modificando el tamaño del cluster. Se realiza un proceso similar para ajustar el alto del cluster, pero se considera la proyección vertical en este caso. 10. Una vez que se ajustó correctamente el tamaño de los clusters, se filtran aquellos que no cumplan que el ancho sobre el alto sea menor que 0,9. Este valor se obtuvo experimentalmente y permite eliminar los clusters que no contienen la misma forma que la patente. 2 Quedando

en blanco aquellos píxeles que están en el 5 % más claros.

Ariel Hernán Curiale

2.4.

2.5

Segmentación de los caracteres

71

Segmentación de los caracteres

Una vez que se filtró la mayor cantidad de patentes falsamente detectadas, se procede a segmentar los caracteres. En esta subetapa se asume que todo cluster analizado contiene a la patente. Para segmentar los caracteres de la patente se aplicó el siguiente algoritmo: 1. Se recorta de la imagen original la región de la patente. 2. La imagen es convertida a NTSC. 3. Se ecualiza el histograma. 4. Se aplica el método Top Hat. 5. Se binariza la imagen con un umbral del 95 %3 6. Se le aplica un thinning a la imagen 4 . 7. Se arman las regiones de la patente utilizando el algoritmo de Pavlidis. 8. Se filtran las regiones que no se corresponden con un caracter, de la siguiente forma: a) Se eliminan todas las regiones que no cuenten con al menos 10 píxeles de alto, por ser demasiado pequeñas para considerarlas un caracter válido. b) Se calcula la altura promedio de las regiones resultantes del paso anterior y se eliminan las regiones que son menores a la mitad de la altura del caracter promedio. c) Para eliminar las regiones muy altas, se ordenan las regiones por su alto, se toma la región media y se procede a descartar toda región cuya altura es mayor en al menos la mitad de la altura de la región media. En la Figura 2.13 se pueden observar algunos pasos intermedios del algoritmo anterior.

2.5.

Reconocimiento de los caracteres

Una vez segmentados los caracteres de la patente se procede a analizar a cada uno de ellos con una red neuronal. Para analizar un caracter con la red neuronal se necesita binarizar el caracter y normalizar a un tamaño de 16x16 píxeles. Éste es el patrón de entrada de la red. La arquitectura de la red neuronal es del tipo perceptrón multicapa de dos capas compuestas por 256 y 10 neuronas cada una. Como salida, la red neuronal devuelve un vector de 10 valores (uno por cada neurona de la capa 3 Quedando 4 Para

en blanco solamente aquellos píxeles que están en el 5 % de los más claros. más información sobre thinning ver la sección 1.2.4.

72

CAPÍTULO 2 El método de ALPR propuesto

(a) La patente convertida a NTSC y ecualizado el histograma

(c) Luego de binarizar y realizar un adelgazamiento a la patente de la Figura 2.13b

Ariel Hernán Curiale

(b) Luego de realizar el Top Hat

(d) Luego de segmentar y filtrar los caracteres

Figura 2.13: Ejemplo de los paso más importantes para segmentar los caracteres de la patente detectada

de salida) que determinan el valor de cada bit correspondiente a un caracter. El objetivo de este trabajo no está centrado en el estudio del reconocimiento de los caracteres, es por esto que no se hace mucho énfasis en el método seleccionado para el reconocimiento, ni sobre los problemas que pueden desprenderse como los mínimos locales, evaluar el tiempo de entrenamiento y mejorar el tiempo de procesamiento, entre otros. La red neuronal se entrenó con un conjunto de 600 caracteres los cuales no provenían del conjunto de imágenes con las que se trabajó. Esto generó un gran deterioro en el rendimiento del reconocimiento. Como el objetivo de este trabajo está centrado en la segmentación y no el reconocimiento, esta etapa no se modificó. Según el resultado obtenido por la red neuronal se va a determinar si es un caracter válido o no y cual es el caracter.

2.6.

Análisis sintáctico

En esta etapa se verifica la composición sintáctica de la patente. Se considera una patente bien formada si está compuesta por tres letras primero seguida de tres números. Toda detección que no cumpla esta regla es descartada.

3

Resultados En este capítulo se introduce el método propuesto en el paper New Methods For Automatic Reading of VLP’s [2], se lo compara con el método propuesto en el Capítulo 2 y se detallan algunas mediciones. Se optó por implementar el método propuesto en el paper New Methods For Automatic Reading of VLP’s[2] por ser un método basado en la morfología matemática para la segmentación de la patente, técnica que fue utilizada en el método propuesto en el Capítulo 2. Esta metodología asume que los caracteres de las patentes son oscuros y están sobre un fondo mucho más claro. La misma se divide en tres etapas: Primero se busca segmentar la patente, luego se procede a segmentar los caracteres y por último se reconocen los caracteres segmentados. En la primer etapa de pre-procesamiento y segmentación se realizan una serie de aperturas, cierres y diferencias de la siguiente forma: Primero se realiza un Black Top Hat (debido a que la patente está compuesta por letras oscuras sobre un fondo claro. Se puede realizar un White Top Hat en caso contrario). El resultado de este proceso se ve en la Figura 3.1c. Para esto se hace un cierre con un elemento estructurante que no entre en la letra más ancha. Al aplicar el cierre se borronean los caracteres como se observa en la Figura 3.1b. Luego se realiza la diferencia con la imagen original obteniendo el Black Top Hat. Al resultado anterior se le aplica una apertura con un elemento estructurante horizontal cuyo tamaño es mayor que el máximo espacio entre los caracteres. Este resultado se puede observar en la Figura 3.1d. Hasta el momento no es posible segmentar correctamente la patente y es necesario aplicar otra apertura con el objetivo de filtrar la mayor cantidad de objetos no deseados. Esta nueva apertura 73

74

CAPÍTULO 3 Resultados

Ariel Hernán Curiale

se realiza con un elemento estructurante vertical del tamaño del menor caracter. El resultado se puede observar en la Figura 3.1e. A continuación se busca eliminar la patente mediante otra apertura, para esto se utiliza un elemento estructurante mayor que el alto de los caracteres cuyo resultado se puede ver en la Figura 3.1f. Una vez que se tienen estas dos imágenes (3.1e y la 3.1f) se procede a realizar la resta entre ellas observándose el resultado en la Figura 3.1g. Por último para obtener solamente la patente, se realiza una apertura con un elemento estructurante horizontal cuyo ancho es menor que el mínimo caracter. Luego de tener la patente segmentada, se procede a segmentar los caracteres utilizando la proyección vertical de la patente.

3.0

Ariel Hernán Curiale

(a) La imagen original

(b) El resultado de aplicar un cierre con un ES que no entra en el ancho de las letras

(c) El resultado de aplicar un Black Top Hat

(d) Luego de aplicar un cierre con un ES Horizontal mayor que el máximo espacio entre los caracteres

(e) Después de filtrar algunos objetos no deseados con una apertura cuyo ES vertical es menor que el alto de los caracteres

(f) Se elimina la patente al aplicar una apertura con un ES mayor que el alto de los caracteres

(g) El resultado de realizar la resta entre la Figura 3.1e y la 3.1f

(h) La patente final se obtiene realizando una apertura con un ES horizontal cuyo ancho es menor que el mínimo caracter

75

Figura 3.1: Ejemplo de la segmentación de la patente utilizando el método propuesto en el paper New Methods For Automatic Reading of VLP’s[2]

76

CAPÍTULO 3 Resultados

Ariel Hernán Curiale

Algunos problemas de este método Uno de los mayores problemas de este método es la dependencia sobre el tamaño de los caracteres y las condiciones de la patente. El método propuesto en este trabajo de tesis resultó ser más robusto a estas variaciones. En las Figuras 3.3 y 3.4 se muestra como falla este método con otras imágenes al detectar una gran cantidad de patentes. Una de las causas de la falla es la dificultad que existe en ajustar correctamente el tamaño de los diferentes elementos estructurantes aplicados. Además se puede observar en la Figura 3.2, como el método propuesto en el Capítulo 2 reconoce de forma exitosa la imagen que utilizó en [2].

(a) Imagen Original

(b) Luego de aplicar el método propuesto en este trabajo

(c) Luego de filtrar la patente del resto de la imagen

Figura 3.2: Ejemplo de la segmentación de nuestro método utilizando la imagen del paper New Methods For Automatic Reading of VLP’s[2]

Ambos métodos son dependientes del color de los caracteres, pero se puede corregir realizando independientemente los métodos para los caracteres claros como los oscuros. El problema de armar un método más genérico es el incremento de los tiempos computacionales. El porcentaje de aciertos del método propuesto en este trabajo con el conjunto de imágenes con el que se contaba, es ampliamente superior al método propuesto en [2]. Esto se debe a la gran dependencia sobre el tamaño de la patente, que dificultó una buena selección de elementos estructurantes para el conjunto de imágenes de prueba. Por este motivo no se realiza una comparación de los tiempos de procesamiento entre ambos métodos, ni los porcentajes de acierto.

3.1

Ariel Hernán Curiale

(a) El resultado de aplicar un White Top Hat

(b) Luego de aplicar un cierre con un ES Horizontal mayor que el máximo espacio entre los caracteres

(c) Luego de filtrar algunos objetos no deseados con una apertura cuyo ES vertical es menor que el alto de los caracteres

(d) Se elimina la patente al aplicar una apertura con un ES mayor que el alto de los caracteres

77

(e) El resultado de realizar la resta entre la Figura 3.3c y la 3.3d

Figura 3.3: Ejemplo de una mala segmentación utilizando el método propuesto en el paper New Methods For Automatic Reading of VLP’s[2]

78

CAPÍTULO 3 Resultados

Ariel Hernán Curiale

(a) El resultado de aplicar un White Top Hat

(b) Luego de aplicar un cierre con un ES Horizontal mayor que el máximo espacio entre los caracteres

(c) Luego de filtrar algunos objetos no deseados con una apertura cuyo ES vertical es menor que el alto de los caracteres

(d) Se elimina la patente al aplicar una apertura con un ES mayor que el alto de los caracteres

(e) El resultado de realizar la resta entre la Figura 3.4c y la 3.4d

Figura 3.4: Otro ejemplo de una mala segmentación utilizando el método propuesto en el paper New Methods For Automatic Reading of VLP’s[2]

3.1

Ariel Hernán Curiale

Algunas mediciones

79

Figura 3.5: Tiempos

3.1.

Algunas mediciones

El conjunto de prueba está constituido por un total de 116 imágenes y el objetivo de las mediciones es determinar la calidad de la detección y el desempeño temporal del método propuesto. Los resultados obtenidos de la calidad de las distintas segmentaciones del conjunto de 116 imágenes fueron:

Calidad en la segmentación de la patente Calidad de la segmentación de los caracteres

Ok 99 imágenes 82 imágenes

Error 17 34

% de detecciones correctas 85 % 70,69 %

Además se analizó el tiempo promedio necesario para segmentar y visualizar los diferentes caracteres de la patente. En la Figura 3.5 se muestra el gráfico correspondiente a las mediciones tomadas del conjunto de imágenes de prueba. En el eje y se puede ver el tiempo de procesamiento del método propuesto por cada imagen y en el eje x se encuentras las 116 imágenes analizadas. Los outlayers o valores que sobresalen se corresponden con las imágenes en las que el proceso de segmentación falló. El tiempo promedio que se desprende de las mediciones es de 6 segundos. Este tiempo es aproximado dependiendo de la carga del CPU y el hardware utilizado. En este tiempo está contemplado la renderización de la patente segmentada y los caracteres. En la Figura 3.8 se observa que el sistema genera en memoria tres imágenes además de la imagen original. El conjunto de muestras está formado por dos tipos de imágenes. Las primeras se tomaron con una cámara digital debido a que en ese momento no se contaba con las cámaras definitivas. Y el segundo grupo de imágenes fue tomado por la cámara infrarroja que se instaló en el lugar. En la Figura 3.7a se observa una imagen tomada por la cámara digital y en la Figura 3.7b se puede observar una imagen tomada con la cámara infrarroja. Algunos resultados erróneos se pueden observar en la Figura 3.6 y la 3.9.

80

CAPÍTULO 3 Resultados

(a)

Ariel Hernán Curiale

(b)

Figura 3.6: Ejemplo de una mala segmentación de los caracteres

(c)

3.1

Ariel Hernán Curiale

Algunas mediciones

(a) Imagen tomada con una cámara digital

(b) Imagen tomada con una cámara infrarroja

Figura 3.7: Ejemplo del conjunto de imágenes analizado

81

82

CAPÍTULO 3 Resultados

Ariel Hernán Curiale

(a) Imagen con la segmentación de la patente

(b) Imagen de la patente

(c) Imagen de la patente

Figura 3.8: Ejemplo de una imagen tratada con nuestro método

3.1

Ariel Hernán Curiale

(a)

(b)

(c)

Figura 3.9: Ejemplo de una mala segmentación

Algunas mediciones

83

84

CAPÍTULO 3 Resultados

Ariel Hernán Curiale

4

Conclusión En este trabajo se buscó encontrar un método que realice la menor cantidad de suposiciones sobre el tipo de imagen a trabajar. Es por esto que al resolver el problema de ALPR se buscó desarrollar e implementar un método que sea independiente de las siguientes características: El tamaño de las patentes. El tipo de patente, la cual depende del país al que pertenezca. El tamaño de los caracteres de la patente. El posicionamiento que tiene la patente dentro de la imagen. Los colores de los caracteres y/o el fondo. El método propuesto no es completamente independiente del tamaño de la patente debido a que por cuestiones de desempeño, se priorizó el buen rendimiento del método sacrificando una mayor independencia. Pero se lograron cumplir las demás características mencionadas anteriormente. Una vez que se aplicó el método propuesto en el Capítulo 2 al conjunto de imágenes de prueba, se generaron los resultados previamente expuestos y se concluyó lo siguiente: 1. La solución propuesta puede trabajar con imágenes de una mala calidad dando resultados aceptables en la segmentación de la patente y de los caracteres. 2. El método que se utilizó para el reconocimiento de los caracteres no es un buen método para el reconocimiento de los caracteres en las imágenes utilizadas. 3. Es más robusto que el método presentado en el Capítulo 3. 85

86

Conclusión

Ariel Hernán Curiale

4. El método propuesto es independiente de la localización de la patente dentro de la imagen. 5. Es independiente del tipo de patente y de la tipografía de la misma. Se encontraron los siguientes inconvenientes: No se pudo independizar el tamaño de la patente en el método propuesto, ya que fue utilizado (como se comentó en la sección 2.3) para determinar el tamaño de la región de interés al aplicar la transformada de Fourier para mejorar el rendimiento del método. El método Top Hat es sensible a las grandes variaciones en el tamaño de la patente. Aún así, hemos logrado incrementar el rango de detección a niveles aceptables, por este motivo se puede decir que no es completamente dependiente del tamaño de la patente.

4.1.

Trabajos a futuro

Algunas puntos a trabajar son: La calidad del reconocimiento óptico de los caracteres. Para esto se puede buscar otro método o mejorar el entrenamiento de la red neuronal. Contemplar el problema de la inclinación de los caracteres en la patente. Considerar la oclusión de la patente de forma parcial e intentar mejorar el rendimiento del método al trabajar con imágenes cuyas patentes no se encuentren en buen estado.

Bibliografía [1] Francisco Gabriel Ortiz Zamora, “Procesamiento morfológico de imagenes en color. aplicación a la reconstrucción geodésica,” M.S. thesis, Universidad de Alicante, Mayo, 2002. [2] José Luis Alba Fernando Martín, Maite García, “New methods for automatic reading of vlp’s,” Signal Processing, Pattern Recognition and Applications, IASTED, Heraklion (Grecia), pp. 115–121, Jul. 25 2002. [3] Kuo-Ming Hung Ching-Tang Hsieh, Yu-Shan Juan, “Multiple license plate detection for complex backgroud,” Advanced Information Networking and Applications, 2005. AINA 2005. 19th International Conference, vol. Vol. 2, pp. 382–392, March. 28-30 2005. [4] Vinh Phuoc-Viet Hoang Duc Dan, Le Hong Du, “Building an automatic vehicle license-plate recognition system,” in proceedings of 3rd International Conference on Computer Science - Recherche, Innovation and Vision du Futur (RIVF2005), Cantho, Vietnam, , no. 59-63, Feb. 21-24 2005. [5] Zheng Ma Feng Yang, “Vehicle license plate location based on histogramming and mathematical morphology,” Fourth IEEE Workshop on Automatic Identification Advanced Technologies (AutoID’05), pp. 89–94, 2005. [6] Nadeem A. Khan Hans A. Hegt, Ron J. Dela Haye, “A high performance license plate recognition system,” Systems, Man, and Cybernetics, 1998. 1998 IEEE International Conference, vol. Vol 5, pp. 4357–4362, Oct. 11-14 1998. [7] Morten Porsborg Køhler Allan Weber Mikkelsen Jens Mejdahl Pedersen Henrik Hansen, Anders Wang Kristensen and Michael Trangeled, “Automatic recognition of license plates,” 2002. [8] Pavol Federl J.R. Parker, “An approach to license plate recognition,” The Laboratory For Computer Vision, University of Calgary, Oct. 01 1996. 87

88

BIBLIOGRAFÍA

Ariel Hernán Curiale

[9] J. W. V. Miller M. Shridhar, “Recognition of license plate image: Issues and perspective,” Document Analysis and Recognition, 1999. ICDAR ’99. Proceedings of the Fifth International Conference, pp. 17–20, Sep. 20-22 1999. [10] Deak Kim Mei Yu, “An approach to korean license plate recognition based on vertical edge matching,” Systems, Man, and Cybernetics, 2000 IEEE International Conference, vol. Vol 4, pp. 2975– 2980, 2000. [11] Hsi-Jian Lee Shen-Zheng Wang, “Detection and recognition of license plate characters with different appearances,” Intelligent Transportation Systems, 2003. Proceedings. 2003 IEEE, vol. Vol. 2, pp. 979– 984, Oct. 12-15 2003. [12] Osamu Katai Hiroshi Kawakami Takayuki Shiose Shigueo Nomura, Keiji Yamanaka, “A novel adaptive morphological approach for degraded character image segmentation,” Pattern recognition ISSN 0031-3203 CODEN PTNRA8, vol. Vol. 38, no. 11, pp. 1961–1975, 2005. [13] Yun-Chung Sei-wan Chen Shyang-Lih Chang, Li-Shien Chen, “Automatic license plate recognition,” Intelligent Transportation Systems, IEEE Transactions, vol. Vol. 5, pp. 42–53, Mar. 2004. [14] Georgi Gluhchev Vladimir Shapiro, “Multinational license plate recognition system: Segmentation and clasification,” Pattern Recognition, 2004. ICPR 2004. Proceedings of the 17th International Conference, vol. Vol. 4, pp. 352–355, Aug. 23-26 2004. [15] Lina J. Karam Yassin M. Y. Hassan, “Morphology text extraction from images,” Image Processing, IEEE Transactions, vol. Vol. 9, pp. 1978–1983, Nov. 11 2000. [16] Roger Boyle JMilan Sonka, Vaclav Hlavac, “Image Processing, Analysis, and Machine Vision”, PSW Publishing, 1998. [17] H. Minkowsky, “Allgemeine lehrs atze uber knovexe polyeder nachr,” Nachr. Ges. Wiss. Gottingen, pp. 198–219, 1897. [18] H. Minkowsky, “Uber die begriffe l ange, oberf ache und volumen,” Jahresbericht der Deutschen Mathematiker Vereinigung, vol. Vol. 9, pp. 115–121, 1901. [19] H. Hadwiger, “Vorlesungen über Inhalt, Oberfläche und Isoporimetrie”, Springer, 1957. [20] H. Hadwiger,

Ariel Hernán Curiale

BIBLIOGRAFÍA

89

“Normale köper im euklidischen raum und ihre topologishen und metrischen eigenschaften,” Math. Zeitschr, vol. Vol. 71, pp. 124–149, 1959. [21] G. Matheron, “Eléments pour une Théorie des Milieux Poreux”, Masson, Paris, 1967. [22] G. Matheron, “Random Sets and Integral Geometry”, John Wiley and Sons. New York, 1975. [23] J. Serra, “Image Analysis and Mathematical Morphology”, Academic Press, Inc. Orlando, FL, USA, 1981. [24] R. D. Ziff P. Maragos, “Threshold superposition in morphological image analysis systems,” IEEE Transactions on Pattern Analysis and Machine Intelligence, vol. Vol. 12, no. No. 5, pp. 498–504, May. 1990. [25] S. Sternberg, “Grayscale morphology,” Computer Vision, Graphics, and Image Processing, vol. vol. 35, no. No. 3, pp. 333–355, Sep.1986. [26] F. Meyer, “Contrast feature extraction”, In J-L Chermant, editor, Quantitative Analysis of Microstructures in Material Science, Biology and Medicine, Riederer Verlag, Stuttgart, Germany, 1978. Special issues of Practical Metalography. [27] W.H Pitts W.S MacCulloch, “A logical calculus of the ideas immanent in nervous activity,” Bulletin of Mathematical Biophysics, vol. Vol. 5, pp. 115–133, 1943. [28] S.C Kleene, “Representation of events in nerve nets and finite automata,” M.S. thesis, Princeton University Press, 1956. [29] J.D Ulman J.E Hopcroft, “Introduction to automata theory, language and computation”, Addison-Wesley, 1979. [30] M.E Hoff G. Widrow, “Adaptive switching circuits,” In Institute of Radio Engineers, Western Electronic Show and Convention, vol. Vol. 4, pp. 96–104, 1960. [31] Azpitarte Llobet Rafael,

90

BIBLIOGRAFÍA

Ariel Hernán Curiale

“Aportaciones al diagnostico de cancer asistido por ordenador,” M.S. thesis, Universidad Politécnica de Valencia, Departamento de Sistemas Informáticos y Computación, Jul. 2006. [32] Lawrence R. Rabiner, “A tutorial of hidden markov models and selected applications in speech recognition,” Proceedings of the IEEE, vol. 77, pp. 257–286, Feb. 1989. [33] M.P Dubuisson, “A modified hausdorff distance for object matching,” Pattern Recognition, 1994. Vol. 1 - Conference A: Computer Vision and Image Processing., Proceedings of the 12th IAPR International Conference, vol. Vol. 1, pp. 566–568, Oct. 9-13 1994. [34] B. H. Juang L. R. Rabiner, “Fundamentals of Speech Recognition”, Prentice-Hall, 1993. [35] Laird N. M. Dempster A. P. and Rubin D. B., “Maximum likelihood from incomplete data via the em algorithm,” Journal of the Royal Statistical Society. Series B (Methodological), vol. Vol. 39, no. No. 1, pp. 1–38, 1977.

A

Métodos fallidos para resolver el problema de ALPR Introducción En este capítulo se exponen dos técnicas que fallaron al resolver el problema de ALPR, pero que inicialmente parecían resolver el problema de una forma muy sencilla.

A.1.

Roberts - Binarización - Proyecciones horizontales y verticales

Para resolver el problema de ALPR primero se estudiaron las características del objeto a segmentar dentro de la imagen. De este estudio se observó que los caracteres dentro de la patente tienen un alto contraste respecto al fondo y que la frecuencia con que cambian es muy alta. Esta idea llevó a aplicar un filtro espacial para la detección de bordes denominado Roberts. Este método pertenece a la familia de los filtros comúnmente llamados detectores de bordes y como su nombre lo indica resaltan los bordes de la imagen. En particular se resaltarán los bordes de los caracteres. Lamentablemente la patente del automóvil no es el único objeto dentro de la imagen que cuenta con estas características, dificultando seriamente la localización de la patente y haciendo que la imagen en su totalidad contenga una gran cantidad de cambios bruscos de intensidad. Del conjunto de muestras con las que se trabajó se observó un determinado patrón en las proyeccio91

92

MÉTODOS FALLIDOS PARA RESOLVER EL PROBLEMA DE ALPR

(a) El resultado de aplicar el filtro de Roberts y luego binarizar la imagen

Ariel Hernán Curiale

(b) Proyección vertical de la imagen de la Figura A.2a

(c) La imagen original y la A.1b superpuestas

Figura A.1: Ejemplo de la aplicación del filtro de Roberts y la proyección vertical de sus componentes en blanco

nes horizontales y verticales de los píxeles. En un principio se pensó que se podría utilizar este concepto para poder segmentar correctamente la patente. En algunas imágenes como puede ser la Figura A.1 el resultado de la proyección horizontal permite diferenciar fácilmente un umbral para segmentar horizontalmente la patente. Pero para segmentarla completamente es necesario realizar la proyección vertical y tratar de encontrar un umbral en esta proyección. En la Figura A.2 se puede observar esto. En algunas imágenes como la A.1 esta metodología parece ser eficaz para segmentar la patente, pero lamentablemente se pueden ver imágenes como A.3 donde no es simple detectar la patente. Se tuvo que descartar esta metodología debido a su alto nivel de errores cometidos al segmentar la patente. Lo bueno de esta metodología fue la velocidad de procesamiento.

Ariel Hernán Curiale

Roberts - Binarización - Proyecciones horizontales y verticales

(a) El resultado de aplicar el filtro de Roberts y luego binarizar

93

(b) Proyección horizontal de la imagen que se le aplicó el filtro de Roberts y se la binarizó

(c) La imagen original y la A.2b superpuestas

Figura A.2: Ejemplo de la aplicación del filtro de Roberts y la proyección horizontal de sus componentes en blanco

94

MÉTODOS FALLIDOS PARA RESOLVER EL PROBLEMA DE ALPR

Ariel Hernán Curiale

(a) El resultado de aplicar el filtro de Roberts y luego binarizar

(b) Proyección vertical de la imagen que se le aplicó el filtro de Roberts y se la binarizó

(c) Las imágenes original y A.3b superpuestas

(d) Proyección horizontal de la imagen que se le aplicó el filtro de Roberts y se la binarizó

(e) La imagen original y la A.3d superpuestas

Figura A.3: Ejemplo de la aplicación del filtro de Roberts y la proyección vertical de sus componentes en blanco

Ariel Hernán Curiale

A.2.

Top Hat + Seguimiento de contorno

95

Top Hat + Seguimiento de contorno

Una de las fallas más grandes de la técnica anterior fue la mala segmentación y/o localización de la patente. Al no ser aprovechadas las características de la patente correctamente fue imposible segmentarla. Descartada la técnica anterior, se buscó un método que pueda aprovechar mejor las características de la patente. Esta vez la morfología matemática parecía ofrecer una gran cantidad de variantes para resolver el problema. De todas ellas, la técnica que mejor se ajustó se la conoce como Top Hat. Esta técnica utiliza las características del elemento estructurante para filtrar aquellos objetos dentro de la imagen que no tienen las mismas características. De esta forma se puede segmentar mejor la patente. Por las características de la patente y las imágenes con que se trabajaron, existen demasiados objetos que estructuralmente se corresponden con la patente. Por esto luego de aplicar el Top Hat a la imagen fue necesario detectar cual de todos los objetos es realmente la patente. El algoritmo que se utilizó para identificar a los objetos resultantes es el seguimiento de contornos. El objetivo de este algoritmo se basa en determinar la posición exacta de la patente dentro de la imagen. Para una mejor explicación sobre este algoritmo se puede consultar el apéndice C.3. Con el primer conjunto de imágenes con las que se trabajó, esta técnica funcionaba correctamente. Una vez que se aplicaba el algoritmo de Top Hat sólo bastaba con identificar a cada uno de los objetos para filtrar fácilmente la patente del resto de los objetos. El problema de esta técnica surgió al usar el segundo conjunto de muestras que provenían directamente de las capturadas por las cámaras infrarrojas. La calidad de las imágenes fue muy pobre, por esto la técnica por sí sola no funcionó. La gran cantidad de falsos positivos dificultó el filtrado de la patente. Por este motivo se descartó esta opción como un método válido para resolver el problema de ALPR. Pero no fue completamente inútil, porque pudo ser empleada en el método propuesto para filtrar grandes porciones de la imagen que seguramente no se correspondían con la patente.

96

MÉTODOS FALLIDOS PARA RESOLVER EL PROBLEMA DE ALPR

Ariel Hernán Curiale

B

Otros métodos de OCR B.1.

Modelos Ocultos de Markov

Habitualmente los modelos de Markov se utilizan para el reconocimiento del habla, pero también se puede utilizar esta idea para el reconocimiento de formas. Por ejemplo en el trabajo de [31] se los utiliza para el reconocimiento de formas en imágenes para diagnosticar cáncer. Se puede interpretar al Modelo Oculto de Markov o Hidden Markov Model (HMM) como una máquina de estados finitos, en la cual interactúan entre sí dos procesos estocásticos bien definidos. Uno de ellos permanece oculto y de ahí el nombre del modelo, mientras que el otro produce la secuencia de observaciones (para mayor información ver referencia [32]). El proceso oculto involucra un conjunto de estados conectados entre sí por medio de transiciones que están ponderadas con probabilidades. Mientras que el proceso observable está constituido por un conjunto de observaciones de salida. Cada una de éstas puede ser emitida por cualquiera de los estados según la función de probabilidad asociada al estado. A continuación se muestra un ejemplo que esclarece lo mencionado anteriormente: Se tiene un juego de cartas que consta de dos mazos independientes y lo único importante del juego es ver si el número de la carta que se saca en cada instancia es par o impar. Cada mazo está constituido por seis cartas y la función de probabilidad para sacar una carta par o impar, es la siguiente: P(impar|M1 ) = 2/3 P(impar|M2 ) = 1/6 P(par|M1 ) = 1/3 P(par|M2 ) = 5/6 97

98

Ariel Hernán Curiale

OTROS MÉTODOS DE OCR

Donde M1 y M2 son los respectivos mazos. Bajo estas condiciones se sacan 6 cartas. Esta secuencia de cartas se denomina Secuencia de observaciones de salida. La forma de sacar las cartas en este juego queda determinada de la siguiente forma: La primer carta se retira del primer mazo, es decir responde a la siguiente función de probabilidad: P(t0 |M1 ) = 1 P(t0 |M2 ) = 0 t0 : es la primer carta ti : i − sima carta Para el resto de las cartas, se van a utilizar los dos mazos, teniendo en cuenta la siguiente función de probabilidad: P(M1 ,ti ,ti+1 |M1 ) = 0,8 P(M1 ,ti ,ti+1 |M2 ) = 0,2 P(M2 ,ti ,ti+1 |M1 ) = 0,4 P(M2 ,ti ,ti+1 |M2 ) = 0,6 Es decir el mazo del cual se retira la próxima carta depende del mazo del cual se extrajo la última carta. Otra forma de entender esta notación puede ser la siguiente: si se tiene P(Mk ,ti ,ti+1 |Mh ), podemos decir que ésta es la probabilidad de retirar una carta del mazo Mh habiendo retirado anteriormente una carta del mazo Mk , donde h y k son los respectivos mazos. Después de sacar una carta y ver si es par o impar, se devuelve al mazo del cual se extrajo. Con esto se busca no alterar las probabilidades a lo largo del juego. Este proceso se puede representar mediante una máquina de estados finitos, donde el conjunto de estados representa a un mazo, y cada estado muestra una carta cada vez que es visitado. Esto se puede observar en la figura B.1.

Figura B.1: Ejemplo del Modelo de Markov discreto de dos estados

Si se tiene la siguiente mano:

Ariel Hernán Curiale

Modelos Ocultos de Markov

0,8

0,8

0,2

0,6

99

0,4

M1 → M1 → M1 → M2 → M2 → M1 ⇓ ⇓ ⇓ ⇓ ⇓ ⇓ Secuencia de observacion ´ : impar impar par par par impar Secuencia de estados :

Esta secuencia de observación puede ser generada por cualquier estado del modelo anterior o por una conjunción de ellos. Esto se debe a la naturaleza probabilística de cada uno de los estados. No se sabe cual es la secuencia de estados que generó esa salida, por ello se dice que la misma permanece oculta. En este ejemplo la secuencia de estados que determina de que mazo se extraen las cartas, no se puede saber. En función de la naturaleza de las observaciones existen dos modelos de HMM: Se tiene un HMM discreto si la secuencia de observación es discreta. Un ejemplo es el caso del juego mencionado anteriormente o el reconocimiento de caracteres. El modelo de Markov siempre será discreto si está formado por una secuencia de observación donde sus elementos pertenecen a un alfabeto determinado y finito. Se tiene un HMM continuo si las observaciones pertenecen a un dominio continuo. Para mayor información sobre este tema se puede consultar la referencia [32]. Según Rabiner existen tres cuestiones básicas de interés al plantear este modelo: ¿ Cuál es la probabilidad de la secuencia de observación dado un modelo, es decir P(o1 , o2 , . . . , on |M) ? ¿ Cuál es la secuencia de estados que maximiza la probabilidad de una salida observada ? Dado un conjunto de observaciones de entrenamiento ¿ Cómo aprende el modelo los parámetros óptimos que describe lo mejor posible dicho conjunto de observaciones ? Para responder estas preguntas es que se diseñaron los siguientes algoritmos: Algoritmo "Forward": la finalidad de este algoritmo es calcular de forma eficiente, la probabilidad de que una secuencia de observaciones sea emitida por un modelo HMM en particular. Algoritmo "Forward - Backward": es utilizado para el aprendizaje de un HMM. Algoritmo "Viterbi": obtiene el camino más probable en un HMM dada una secuencia de observación. Es una variante del algoritmo de Forward, en el cual se reemplaza una sumatoria por un valor máximo.

100

Ariel Hernán Curiale

OTROS MÉTODOS DE OCR

Estos algoritmos se pueden encontrar en el apéndice C.1. Una forma de utilizar este modelo en el reconocimiento de los caracteres de la patente de un automóvil puede encontrarse en el paper de la referencia [4]. En dicho modelo primero se normalizan todos los posibles caracteres a un tamaño de 50x50 píxeles ( que se denota foreground_pixels en la fórmula). Luego se procede a extraer un vector de características de 196 posiciones de la siguiente forma: Se recorre el caracter (de 50x50) con una ventana de 9x9 píxeles (la cual se denotará en la fórmula como Sk ) de izquierda a derecha y de arriba hacia abajo solamente superponiendo esta ventana en dos tercios de su tamaño, obtenemos 196 movimientos. Para cada uno de estos 196 movimientos se obtiene un resultado mediante la siguiente fórmula:

fk =

∑(i, j)∈Sk f oreground p ixels(i, j) widthk xHeightk

(B.1)

Una vez recorrido todo el caracter se cuenta con un vector de características de 196 posiciones. Esta secuencia de características será utilizada en el HMM como la secuencia de observación para buscar cual de todas las clases de caracteres se ajusta mejor, y poder determinar a qué caracter corresponde la imagen examinada. Los caracteres están divididos en 36 clases, donde 26 son para las letras (A, ..., Z) y 10 para los números (0,...,9).

B.2.

Distancia de Hausdorff

Se necesita introducir el concepto de espacio compacto antes de definir la distancia de Hausdorff. Definición B.2.1. Un conjunto K de un espacio topológico R se dice compacto si todo cubrimiento por abierto tiene un subcubrimiento finito; es decir, si para todo {Vi }i∈I tal que Vi es abierto y ∪i∈IVi ⊃ K, existe F ⊂ I finito tal que ∪i∈F Vi ⊃ K. A continuación se define la distancia de Hausdorff. Definición B.2.2. Sean X e Y dos conjuntos de un espacio compacto métrico M . Se define la Distancia de Hausdorff dH (X,Y ) como el mínimo número r tal que alguna r-vecindad cerrada de X contiene a Y y alguna r-vecindad cerrada de Y contiene a X.

dH (X,Y ) = m´ax{sup ´ınf ||x − y||, sup ´ınf ||x − y||} x∈X y∈Y

y∈Y x∈X

(B.2) (B.3)

Donde: ||x − y|| denota la distancia en M

Ariel Hernán Curiale

Distancia de Hausdorff

101

Se puede entender esta definición desde el punto de vista morfológico de la siguiente forma: La distancia de Hausdorff es el m´ax{R1 , R2 }, donde el radio R1 se calcula al dilatar el objeto X de manera que se logre cubrir completamente el objeto Y . Mientras que para el cálculo de R2 se prosigue de forma análoga, pero en este caso se dilata el objeto Y hasta lograr cubrir el objeto X. Se puede utilizar esta distancia para comparar dos imágenes binarias o conjuntos de píxeles. La misma cuenta con todas las propiedades matemáticas de una métrica y determina una relación entre el caracter observado y el tomado como referencia. Dubuisson en [33] prueba que la distancia de Hausdorff no se comporta bien en presencia del ruido. Al estar basada en el máximo de las distancias, la presencia de ruidos puede arrojar resultados erróneos. Por esto Martín, Garcia y Alba en [2] proponen una modificación de esta distancia, la cual llaman MHD ("Modified Housdorff Distance") para la detección de los caracteres en la patente de los automóviles. MHD(X,Y ) = m´ax{mhd(X,Y ), mhd(Y, X)} donde: mhd(X,Y ) =

1 ın ||a − b|| ∑ m´ b∈Y |X| a∈X

(B.4) (B.5)

En dicho paper [2] separan en 34 clases los caracteres, 26 para las letras y 10 para los números. Pero consideran al 0 igual que la O y no utilizan la Q. Para determinar a qué caracter se corresponde la imagen examinada, computan la MHD para todos los caracteres segmentados y todas las imágenes de prototipo descartando a todos los caracteres que no sean los tres más cercanos. Por ejemplo si la patente es PO-4198-AF obtienen la siguiente tabla B.1. Donde R1, R2 y R3 son los tres resultados más cercanos a la menor distancia de Housdorff encontrada, mientras que H1, H2 y H3 son las distancias de Housdorff.

P O 4 1 9 8 A F

R1 P O 4 1 9 8 A F

H1 .172 .170 .253 .187 .214 .168 .211 .230

R2 F D A Y S B W P

H2 .567 .273 .428 .600 .297 .194 .423 .469

R3 D B 6 W B 6 4 7

H3 .677 .393 .597 .681 .341 .305 .434 .584

Tabla B.1: Uso de la distancia de Housdorff para el reconocimiento óptico de caracteres.

Luego dividen la imagen en bloques dependiendo del máximo espacio entre los caracteres, generando tres bloques. El primer bloque es PO, el otro es 4198 y por último AF.

102

OTROS MÉTODOS DE OCR

Ariel Hernán Curiale

Para cada bloque calculan el número de votos que tiene para determinar si contiene letras o números. Por ejemplo el primer bloque tiene un voto para ser letras, porque el 0 o la O no cuenta. El segundo tiene cuatro votos para ser números y el tercero dos votos para ser letras. Si el bloque tiene la mitad más uno de votos positivos de ser de algún tipo, automáticamente lo fijan. De esta forma el bloque PO queda indefinido, 4198 es numérico y AF es de letras. Eliminando las no concordancias de la tabla, por ejemplo, borran la Y y la W de la línea que corresponde con el 1. Luego seleccionan de la tabla la menor distancia para todos los caracteres, menos los conflictivos (0,O). El resultado que queda es P-4198AF. Para los casos conflictivos se computa nuevamente la MHD, pero solamente se los compara con dos o tres de los prototipos conflictivos. En este caso no se toma la imagen completa (el caracter), si no, se toma el cuarto de ella que más información tiene para cada caso. Para determinar el cuarto se utiliza la Figura B.2. Según la figura el O y la D están en el cuarto superior izquierdo.

Figura B.2: Grupos conflictivos de letras

De esta forma logran obtener el resultado de PO4198AF para todos los caracteres de la patente.

B.3.

Template Matching

El objetivo de este método consiste en comparar dos imágenes y determinar cuán parecidas son. La forma más común de realizar esta comparación es utilizando la correlación cruzada. Algunas desventajas de la correlación cruzada son el brillo, los diferentes tamaños y deformaciones entre la imagen original y la tomada como referencia. Se pueden mejorar estos problemas normalizando la correlación cruzada, a costa de una pérdida en el rendimiento del algoritmo que la calcula. Para reconocer los caracteres en una imagen se realiza el siguiente procedimiento: Se calcula la correlación entre la imagen y todos los caracteres de referencia. Luego se determina el caracter que está en la imagen asociándolo al caracter de referencia con el cual tuvo mayor correlación. La correlación cruzada, está basada en la distancia euclidiana al cuadrado: d 2f ,t (u, v) =

∑ ∑[ f (x, y)2 − 2 f (x, y) ∗ t(x − u, y − v) + t(x − u, y − v)2] x

y

(B.6)

Ariel Hernán Curiale

Template Matching

103

El valor obtenido de la ecuación B.6, representa la correlación del píxel (u, v) en la imagen. Esto se puede ver en la figura B.3.

Figura B.3: Disposición de la correlación cruzada

Si se examina en detalle los componentes de la ecuación B.6 se observa que el término

∑ ∑ t(x − u, y − v)2 x

y

es constante y representa la suma al cuadrado de los píxeles dentro de la plantilla. Y además si la intensidad de la imagen es similar, se podría ver al siguiente término como constante también.

∑ ∑ f (x, y)2 x

(B.7)

y

De esta forma se define la correlación cruzada de la siguiente forma: C(u, v) =

∑ ∑ f (x, y) ∗ t(x − u, y − v) x

(B.8)

y

Se necesita normalizar esta correlación, ya que es dependiente del tamaño de la plantilla. La expresión para calcular la correlación cruzada normalizada es: ϕ(u, v) = q

∑x ∑y [ f (x, y) − fu,v ][t(x − u, y − v) − t]

(B.9)

∑x ∑y [ f (x, y) − fu,v ]2 ∑x ∑y [t(x − u, y − v) − t]2

Donde fu,v es el valor de los píxeles de la imagen cubiertos por la plantilla y t es el valor de la plantilla.

104

OTROS MÉTODOS DE OCR

Ariel Hernán Curiale

El valor de ϕ se encuentra entre −1 y 1, donde el valor de −1 o 1 significan que existe una coincidencia y el valor de 0 se obtiene cuando no existe coincidencia. En el paper “An approach to Korean License Plate Recognition Based on Vertical Edge Matching” [10], se utilizan este método para determinar a qué caracter corresponde la imagen examinada. Primero se separan los caracteres en cuatro conjuntos de templates y se compara la imagen desconocida con estos templates buscando la menor distancia entre todos para determinar el caracter que se corresponde con la imagen examinada.

C

Algoritmos C.1.

Algoritmos utilizados en los Modelos Ocultos de Markov

C.1.1.

Nomenclatura

M

Es el conjuntos de parámetros que definen al HMM. Q Es el conjunto de estados de M : Q = q0 , . . . , qn N Es el número de estados excluyendo al estado inicial: N = |Q| − 1 x Es una secuencia de observación T Es el número de vectores de x xt Es un elemento de la secuencia x en el tiempo t: xt ∈ Rd 1 6 t 6 T ai j Es la probabilidad de transición del estado qi al q j bi (x) Es la probabilidad de emitir el signo xt en el estado qi Tabla C.1: Nomenclatura utilizada en los Modelos Ocultos de Markov

C.1.2.

Algoritmo Forward

Sea α j (t) con 0 ≤ j ≤ N, la densidad de probabilidad de que un proceso de Markov se encuentre en el estado q j en el tiempo t, y haya emitido la secuencia de observación x = x1 , . . . , xt . Es decir α j (t) = P(x1 x2 . . . xt , q j ). Esta probabilidad se puede expresar de la siguiente forma: ( ah0 j b j (x1 ) t =1 i α j (t) = N−1 ∑i=1 αi (t − 1)ai j b j (xt ) 1 < t ≤ T 105

106

Ariel Hernán Curiale

ALGORITMOS

Con la condición de α0 (1) = 1. La probabilidad de que la secuencia x sea emitida por el modelo M en términos de α j (t) es: N−1

P(x|M ) = P(x1 x2 . . . xT |M ) = αN (T ) =

∑ αi(T )aiN

i=1

C.1.3.

Algoritmo Backward

Sea βi (t) con 0 ≤ i ≤ N, la densidad de probabilidad de que un proceso de Markov vaya a emitir la secuencia de observación x = xt+1 , xt+2 , . . . , xT , sabiendo que en el instante t se encontraba en el estado qi . Es decir βi (t) = P(xt+1 xt+2 . . . xT , qi ). Esta probabilidad se puede expresar de la siguiente forma:  βi (t) =

aiN b j (x1 ) t =T N−1 ∑ j=1 ai j b j (xt+1 )β j (t + 1) 1 ≤ t < T

Con la condición de βN (T ) = 1. La probabilidad de que la secuencia x sea emitida por el modelo M en términos de βi (t) es: N−1

P(x|M ) = P(x1 x2 . . . xT |M ) = β0 (1) =

∑ a0 j b j (x1)β j (1)

j=1

C.1.4.

Algoritmo Viterbi

Este algoritmo es una variante del de Forward en el que se reemplaza una sumatoria por un máximo, de la siguiente forma:  vit j (t) =

a 0 j b j (x1 ) t =1  mxi∈[1,N−1] viti (t − 1)ai j b j (xt ) 1 ≤ t ≤ T

Con la condición de vit0 (1) = 1. La probabilidad de Viterbi de la secuencia x es: N−1

vitN (T ) = mxi∈[1,N−1] viti (T )aiN ≤

∑ αi(T )aiN = αN (T )

i=1

C.1.5.

Algoritmo Backward - Forward para entrenamiento de un HMM

Este algoritmo también se lo llama "Baum - Welch"[34], el cual puede ajustar a partir de un conjunto de muestras de entrenamiento todos los parámetros que define un HMM. Este algoritmo se puede ver como una instancia del algoritmo EM (.Expectation - Maximization") [35] y tiene garantizada su convergencia a un máximo local.

Ariel Hernán Curiale

Algoritmo BackPropagation usado en redes neuronales

107

Sea E = X r = (x1r , . . . , xTr r ) : xkr ∈ X para1 ≤ k ≤ T 1 ≤ r ≤ R un conjunto de R muestras, utilizadas para estimar los parámetros de un HMM simple. La formula básica para la reestimación de las probabilidades a0i j

=

Tr −1 r r )βr (t + 1) αi (t)ai j b j (xt+1 ∑Rr=1 P1r ∑t=1 j T

r αri (t)βrj (t) ∑Rr=1 P1r ∑t=1

(C.1)

donde 0 < i < N, 0 < j < N y Pr = P(X r ) es la probabilidad total de la r-ésima muestra del conjunto E. Las transiciones del estado inicial y final son reestimadas de la siguiente forma: a00 j = a0iN

C.2.

=

1 R 1 r ∑ Pr α j (1)βrj (1) R r=1

∑Rr=1 P1r αri (T )βri (T ) T αr (t)βr (t) ∑Rr=1 P1r ∑t=1 i i

Algoritmo BackPropagation usado en redes neuronales

Paso 1 Se inicializan los pesos de la red con valores pequeños aleatorios. Paso 2 Se presenta un patrón de entrada y se especifica la salida deseada que debe generar la red. Paso 3 Se calcula la salida actual de la red. Para ello se presentan los valores de entrada en las entradas de la red y se va calculando la salida que presenta cada capa hasta llegar a la capa de salida. Los pasos a seguir son: Se calculan las entradas netas para las neuronas ocultas procedentes de las neuronas de entrada. Para una neurona j oculta N

red hp j = ∑ whji y pi + θhj i=1

en donde el índice h se refiere a magnitudes de la capa oculta; el subíndice p, al p-ésimo vector de entrenamiento, y j a la j-ésima neurona oculta. El término θ puede ser opcional, ya que actúa como una entrada más. Se calculan las salidas de las neuronas ocultas y pi = f jh (red hp j ) Se realizan los mismos cálculos para obtener las salidas de las neuronas de salida N

red 0p j = ∑ w0ji y pi + θ0j i=1

y pi = f j0 (red 0p j )

108

Ariel Hernán Curiale

ALGORITMOS

Paso 4 Se calculan los términos de error para todas las neuronas. Si la neurona k es una neurona de la capa de salida, el valor de la delta es 0

γ0pk = (d pk − y pk ) fk0 (red 0j ) La función f debe ser derivable. Ésta puede ser cualquiera de las descriptas en 1.3.1, en la página 44. Si se selecciona la función sigmoidal, la derivada es: 0

fk0 = fk0 (1 − fk0 ) = y pk (1 − y pk ) y los términos del error para las neuronas de salida γ0pk = (d pk − y pk )y pk (1 − y pk ) mientras que para las neuronas que no son de salida tenemos 0

γhp j = f jh (red hp j ) ∑ γ0pk w0ji k

Donde se ve que el error de las capas ocultas dependen de todos los términos de error de la capa de salida, y de ahí el nombre de propagación hacia atrás. Paso 5 Se actualizan los pesos: para ello se utiliza un algoritmo recursivo, comenzando por las neuronas de salida y trabajando hacia atrás hasta llegar a la capa de entrada, ajustando los pesos de la siguiente forma: Para los pesos de las neuronas de la capa de salida ∆w ji = yi ∗ y j 0 ∆w ji (t + 1) = αγ0pk y p j Para los pesos de las neuronas de la capa oculta whji (t + 1) = whji (t) + ∆whji (t + 1) ∆whji (t + 1) = αγhpk y p j En ambos casos, para acelerar el proceso de aprendizaje se puede añadir un término de momento. Paso 6 El proceso se repite hasta que el término de error Ep =

1 M 2 ∑ γ pk 2 k=1

resulta aceptablemente pequeño para cada uno de los patrones aprendidos.

Ariel Hernán Curiale

C.3.

Algoritmo de seguimiento de contornos

109

Algoritmo de seguimiento de contornos

/* Se recorre toda la imagen de Izquierda a derecha y de Arriba hacia abajo * Se toma el primer píxel del contorno para la primer región de la imagen * */

mientras el píxel actual (x,y) esta en blanco pixelInicial = (x,y) pixelActual = pixelInicial /* Inicializo el píxel actual */ /* * Se buscan todos los píxeles de esta región, es * decir se va a seguir el contorno agregandolos a reg * */ dpa = 0; dps = direccionPixelSiguiente(dpa,pixelInicial,r); pixel_siguiente = siguientePixel(dps,pixelInicial); reg.addPixel(pixelInicial); dpa = dps; mientras pixelInicial != pixel_siguiente reg.addPixel(pixel_siguiente); /* Hasta acá dpa es la dirección del píxel actual */ dpa = direccionPixelSiguiente(dpa,pixel_siguiente,r); /* Ahora dpa es la dirección del píxel que sigue al siguiente */ pixel_siguiente = siguientePixel(dpa,pixel_siguiente); fin /* * Finalmente cuando se tienen todos los píxeles del contorno * Se pinta toda la región con negro así no se vuelve a contar * */ r = reg.marcarRegion(r); si la región cumple con las propiedades que tiene que tener un posible caracter l si no la descarto. fin

110

ALGORITMOS

Ariel Hernán Curiale

Funciones auxiliares direccionPixelSiguiente(dpa, pixelActual) invert = {{0,4},{1,5},{2,6},{3,7},{4,0},{5,1},{6,2},{7,3}}; dps = (invert[dpa][1] +1) %8; para (int i = 0; i< 7; i++) x = (int)pixelActual.getX(); y = (int)pixelActual.getY(); dependiendo del valor de ((dps + i) % 8) si es 0: x++; fin; si es 1: x++; y--; fin; si es 2: y--; fin; si es 3: x--; y--; fin; si es 4: x--; fin; si es 5: x--; y++; fin; si es 6: y++; fin; si es 7: x++; y++; fin; fin si estoy dentro de la imagen /* (x >= 0 && x < ancho && y >= 0 && si el píxel x,y es blanco return (dps + i) % 8; fin si fin para return invert[dpa][1];

siguientePixel(dps, pixelAcutal) x = pixelAcutal.getX(); y = pixelAcutal.getY(); dependiendo del valor de dps si es 0: x++; fin; si es 1: x++; y--; fin; si es 2: y--;

y < alto) */

Ariel Hernán Curiale

si si

si si si

fin; es 3: x--; y--; fin; es 4: x--; fin; es 5: x--; y++; fin; es 6: y++; fin; es 7: x++; y++; fin;

fin return (x,y);

Algoritmo de seguimiento de contornos

111