Reconocimiento de Formas Introducción José Martínez Sotoca Dept. Lenguajes y Sistemas Informáticos Universidad Jaume I E-12071 Castellón (España) http://www.vision.uji.es/~sotoca/docencia.html

Temario del Curso 1. Introducción. • • •

2.

Técnicas paramétricas. • • • • • •

3.

¿Qué es el reconocimiento de formas (RF)? Configuración de un sistema RF. Taxonomia de problemas RF. Introducción a la probabilidad. Teoría de la decisión de Bayes. Estimación del error. Funciones discriminantes. La función de densidad de probabilidad normal. Estimadores de densidad de probabilidad.

Técnicas no paramétricas. • • • •

Ventanas de Parzen. Regla de los k-vecinos mas próximos. Vecindad envolvente. Selección de prototipos: Edición y condensado.

2

Temario del Curso 4.

Aprendizaje no supervisado. • • •

Análisis de agrupamientos. Validación del agrupamiento. Aproximación difusa.

5. Técnicas de reducción de la dimensionalidad. • • • •

6.

Estrategias de búsqueda. Función criterio: error de clasificación, separación entre clases, medidas de dependencia y medidas de información. Ponderación de características. Extracción de características.

Análisis Sintáctico. • • •

Modelos de Markov. Algoritmo de Viterbi. Ejemplo de un traductor automático. 3

Bibliografía Básica •

R.O. Duda and P.E. Hart; Pattern Classification and Scene Analysis, John Wiley & Sons, 1973.

•

K. Fukunaga; Statistical Pattern Recognition, Academic Press, 1990.

•

L. Devroye, L. Györfi and G. Lugosi; A Probabilistic Theory of Pattern Recognition, Springer-Verlag, 1996.

•

P.A. Devijver and J. Kittler; Pattern Recognition: A Statistical Approach, Prentice-Hall, 1982.

•

Curso de Reconocimiento de Formas de Francisco José Cortijo Bon. http://www-etsi2.ugr.es/depar/ccia/rf/www/

•

MIT’s OpenCourseWare. Course of Machine Learning from Department of Electrical Engineering and Computer Science.

4

Artículos: •

Reconocimiento de Formas: – A.K. Jain, R.P.W. Duin, J.Mao. “Statistical Pattern Recognition: A Review”

•

Bayes: – F. Dellaert. “The Expectation Maximization Algorithm”. – L. Verteegen. “The simple bayesian classifier as a classification algorithm”. – M.A.T. Figueiredo, A.K.Jain. “Unsupervised Learning of Finite Mixture Models”.

•

Reducción de prototipos: – J.S. Sánchez, F. Pla, F.J. Ferri. “Prototype selection for the nearest neighbour rule through proximity graphs” – B.V. Dasarathy, J.S. Sánchez, S. Townsend. “Nearest Neighbour Editing and Condensing ToolsSynergy Explotation”. – M. Lozano, J.S. Sánchez, F. Pla. “Reducing Training Sets by NCN-based Exploratory Procedures”. – M. Lozano, J.M. Sotoca, J.S. Sánchez, F. Pla. “An Adaptive Condensing Algorithm Based on Mixtures of Gaussians.

5

•

Clustering: – K. Rose. “Deterministic Annealing for Clustering, Compression, Classification, Regression, and Related Optimization Problems”. – G. Karypis, E. Han, V. Kumar. “CHAMALEON: A Hierarchical Clustering Algorithm Using Dynamic Modelling”. – S. Guha, R. Rastogi, K. Shim. “CURE: An Efficient Clustering Algorithm for Large Databases”.

•

Reducción de características: – D. Wettschereck, D.W. Aha, T. Mohri. “A Review and Empirical Evaluation of Feature Weighting Methods for a Class of Lazy Learning Algorithms”. – J.M. Sotoca, J.S. Sánchez, F. Pla. “Attribute Relevance in Multiclass Data Sets Using the Naive Bayes Rule”. – I. Kononenko. “Estimating Attributes: Analysis and Extensions of RELIEF”. – R. Kohavi, G.H. John. “Wrappers for Feature Subset Selection”.

6

Qué es el Reconocimiento de Formas ? El Reconocimiento de Formas (RF) es una área multidisciplinar que comprende diversos campos, como – Matemáticas, Informática, Estadística, Física, etc.

teniendo aplicaciones en muy variados aspectos: – Biología, Medicina, Visión por Ordenador, Psicología, Inteligencia Artificial, Economía, Ingeniería, etc.

7

• Objetos: Representaciones abstractas de fenómenos físicos. • Necesidad de automatizar los procesos de clasificación • Descriptores: Se trabaja más con la información abstracta.

Antes de decidir una acción es necesario reconocer y clasificar la información.

8

Sistema humano • El reconocimiento de formas es un atributo básico de los seres vivos. – Reconocimiento sensorial. – Reconocimiento abstracto: ideas, conceptos.

• El reconocimiento en el hombre es un problema Psicofísico. • El sistema nervioso humano recibe 109 bits/seg de información sensorial. • El sistema de visión es la principal fuente de información. • Sensores de distinta naturaleza => características diferentes.

9

Sistema humano •

• • • 1. 2.

A nivel informático un objeto tiene una estructura de registro. – Valores numéricos. – Atributos subjetivos (color, tacto, finalidad del objeto). La caracterización depende del sujeto. La experiencia juega un papel fundamental en el Reconocimiento. Ej. Diagnóstico en medicina. El estudio de problemas RF implica: Estudio de los mecanismos de Reconocimiento de los seres vivos: Psicología, Fisiología, Biología. Desarrollo de teoría y técnicas para realizar tareas de Reconocimiento en una aplicación determinada: Ciencias de la Computación, Ingeniería.

10

Objetivo del RF Asignar un objeto o fenómeno físico (patrón, en general) a una clase o categoría.

Sistema de RF: regla de decisión automática que transforma medidas sobre un modelo en asignaciones a clases.

11

Conceptos Generales • Modelo: representación de un patrón. • Características o atributos: medidas que dan lugar a las representaciones. • Espacio de representación o de características: conjunto de todas las representaciones posibles para un cierto problema. Por tanto, se corresponde con el universo de trabajo sobre el que debe operar el sistema de RF. 12

Fases de Diseño de un Sistema de RF •

Sensor: – Proporciona una representación de los elementos del universo de estudio. – La sensibilidad del sensor determina el buen funcionamiento de todo el sistema. – No siempre es posible utilizar el sensor más adecuado.

•

Preproceso: – Modificar la representación inicial para poder resaltar las características relevantes: Filtraje, Realce, Cambio de espacio, etc. – No hay cambio de naturaleza del espacio de representación: Continuo -> discreto. – No suele existir mucho conocimiento que dirija el preproceso. 13

•

Extracción de Características: – Extraer la información que puede permitir la discriminación. – Eliminar información redundante e irrelevante. – Reducir la dimensionalidad del problema.

•

Toma de decisiones: clasificación. – Asignar los “objetos” percibidos (con pertenencia desconocida) a la clase adecuada.

14

Representación de Patrones • Muchas variaciones de un patrón pueden ser reconocidas como pertenecientes a una misma clase.

15

Bases del reconocimiento de Patrones

Sensor(s)

...

Patron

x1 x2 x3

X

Resultado (etiqueta clase)

Clasificador(s)

xn

16

Interpretación vs. Clasificación • La interpretación generaliza más el proceso de reconocimiento. • La interpretación de los datos consiste en poner de manifiesto las relaciones relevantes dentro de la estructura de descriptores de los datos. • El proceso de Reconocimiento suele muchas veces ir guiado por un conocimiento a priori del problema. Se establece un modelo y la interpretación debe ser consistente con el modelo. • La complejidad del proceso de Reconocimiento depende del tipo de interpretación de se desee realizar. • Los resultados de la interpretación pueden entenderse como mensajes semánticos dentro de un posible conjunto de posibles mensajes que constituyen el universo semántico. 17

• La interpretación se suele considerar como un simple proceso de clasificación. La salida del proceso puede ser una etiqueta que identifique la asignación a un objeto desconocido. • Cuando el universo semántico es muy grande no se puede especificar el mensaje semántico por lo que sólo se puede alcanzar un nivel de comprensión. • En proceso complejos como es el lenguaje natural se alcanzan diversos niveles de representación del sistema: – Nivel léxico. – Nivel sintáctico. – Nivel semántico.

18

Aprendizaje • La interpretación depende del modelo establecido por el sistema. • Establecer un modelo es un aspecto muy importante en el RF. • El proceso de aprendizaje permite establecer ese modelo: establecer los parámetros del modelo o adquirir conocimiento sobre el problema. • Tipos de aprendizaje: – Recopilar conocimiento (deductivo) humano sobre el problema. (Sistemas expertos). – Adquirir (inductivamente) el conocimiento a partir de ejemplos específicos. Ej. Inferencia gramatical, estimación de parámetros.

19

• El aprendizaje se puede realizar en una fase previa al reconocimiento (“diseño del clasificador”) o continuar durante el proceso de reconocimiento (Aprendizaje continuo). • Un objetivo del Aprendizaje puede ser la determinación del conjunto de descriptores “óptimo”. Este proceso se llama selección de características. • La selección de características se suele llevar a cabo mediante técnicas estadísticas y puede requerir conocimiento profundo de la naturaleza del problema.

20

Aproximaciones al RF • Reconocimiento estadístico o geométrico de formas. • Reconocimiento sintáctico o estructural de formas. • Correspondencia de modelos (template matching). • Redes neuronales.

21

Aproximación Estadística • Basado en la Teoría de la Decisión. • Representar los patrones mediante vectores de características. • Establecer fronteras de decisión en el espacio de representación que permitan separar patrones pertenecientes a clases distintas: funciones discriminantes. • Localizar en qué “región” se encuentra el patrón a clasificar. 22

Aproximación Sintáctica • Representar los patrones mediante una estructura jerárquica: relaciones entre primitivas. • Analogía entre la estructura de los patrones y la sintaxis de un lenguaje. – Patrones = sentencias del lenguaje – Primitivas = alfabeto del lenguaje – Sentencias generadas según una gramática

• Comprobar si el patrón (sentencia) puede generarse mediante las primitivas (alfabeto) a partir de las reglas gramaticales. 23

• Ejemplos: reconocimiento de caras, huellas digitales, caracteres chinos, reconocimiento automático del habla. • Descripción estructural mediante representaciones jerárquicas. (árboles) • La teoría de lenguajes formales es una herramienta muy útil para la aproximación sintáctica. • Aprendizaje mediante técnicas de inferencia gramatical.

24

Sistema de RF Estadístico (REF) Fase de Entrenamiento

Fase de Clasificación

Conjunto de entrenamiento

Conjunto de test

Preproceso

Preproceso

Extracción / Selección de características

Medición de características

Aprendizaje

Clasificación 25

Formulación de un Problema de Clasificación en REF • Dado un patrón x ∈ E, el problema de la clasificación consistirá en determinar, en base a un vector de d características x = (x1, x2, ..., xd), a cuál de las c clases Ω = {ω1, ω2, ..., ωc} diferentes del problema pertenece dicho patrón.

δ : E → Ω, δ(x) = ωi i = 1, ..., c

26

Funciones Discriminantes • Podemos expresar el clasificador δ en términos de c funciones discriminantes, Di(x):

δ(x) = ωi ⇔ Di(x) > Dj(x) ∇j≠i

i, j = 1, ..., c

• Por tanto, el clasificador asigna x a la clase cuya función discriminante Di(x) asociada sea mayor. 27

Fronteras de Decisión • Existen zonas del espacio de características donde Di(x) = Dj(x), es decir, particiones que podrían pertenecer con la misma probabilidad a más de una clase: fronteras de decisión.

28

Taxonomía del REF (1) Aproximación paramétrica • Conocimiento a priori de la forma de las distribuciones de probabilidad de cada clase sobre el espacio de representación. • Las fronteras de decisión están definidas por dichas distribuciones.

Aproximación no paramétrica • El único conocimiento a priori se refiere al inducido a partir de un conjunto de muestras (conjunto de entrenamiento) de las que se conoce su clase. • Las fronteras de decisión están definidas por dichas muestras. 29

Taxonomía del REF (2) Aprendizaje supervisado

Aprendizaje no supervisado

• Se dispone de un conjunto de muestras etiquetadas (con una etiqueta de clase).

• Se dispone de un conjunto de muestras sin etiquetar. • El número de clases puede ser también desconocido.

Clasificación por criterios de vecindad

Clustering 30

Ejemplo de un Sistema REF • Problema: En una cinta transportadora, se pretende distinguir (es decir, clasificar) entre dos tipos diferentes de frutas: naranjas y fresas.

Clases del problema: naranjas, fresas.

31

Ejemplo de un Sistema REF • Selección de características: – Perímetro de la fruta. – Intensidad del color en la banda del rojo (escalado entre 0 y 1).

32

Ejemplo de un Sistema REF Naranja Intensidad Rojo

Fresa

Perímetro

Representación de los patrones en el espacio de características. 33

Ejemplo de un Sistema REF Función discriminante (fd)

Intensidad Rojo

Representación de la frontera de decisión.

Perímetro

La función discriminante divide el espacio de representación en dos semiplanos, cada uno correspondiente a una clase. 34

Intensidad Rojo

Ejemplo de un Sistema REF

Perímetro

Naranja mal clasificada

Clasificación de un nuevo patrón. 35

Varias aplicaciones reales • • • • •

Diagnosis médico. Reconocimiento en tiempo real. Robótica. OCR y Análisis Digital de Caracteres. Biométrica: Caras y reconocimiento del iris, huellas dactilares.

36

Mas... • • • • •

Cartografía. Vigilancia y monotorización de Vídeo. Minería de texto y páginas web. Análisis financiero. Análisis de texto.

37

...y más todavía • • • • •

Análisis de datos por satélite. Clasificación de estilos musicales. Clasificación de cromosomas. Control de calidad industrial. Etc.

38

Clasificación de frutos en líneas de selección eVis. Enginyeria Visual

El sistema general ENCODER ENCODER

CONTROL CONTROL

LINEA LINEADE DE TRANSPORTE TRANSPORTE

LAN ENTORNO ENTORNO USUARIO USUARIO

MÓDULOS MÓDULOS VISIÓN VISIÓN

MÓDULOS MÓDULOS SALIDAS SALIDAS

CAN

MÓDULOS MÓDULOS PESO PESO

40

Módulo de visión MÓDULO DE VISION CÁMARA CÁMARA

• Arquitectura sistema empotrado basado en PC • Sin entorno de usuario • Comunicaciones CAN/LAN

DIGITALIZADOR

PCI BUS INTERFAZ LAN

RAM

PROCESADOR

INTERFAZ CAN

LAN

CAN

ENTORNO ENTORNO USUARIO USUARIO

CONTROL CONTROL

41

Adquisición de imagen • Cámaras RGB + IR: – barrido progresivo – reset asíncrono

• Cúpula de ilumnación: – iluminación difusa

42

Maquina de clasificación de Frutas.

43

Capacidades del sistema • Clases de color: hasta 12 (definidas por el usuario). – Hasta 8 etiquetas de color (definidas por el usuario).

• Estimación de tamaño: ±1 mm • Velocidad de proceso: – Pentium II a 450 MHz – 15 frutos/segundo – dos líneas al mismo tiempo

• Trabajando en varias centrales hortofrutícolas en España.

44

Un sistema de monotorización de tráfico

45

Inspección de paquetes de salchichas

46

Un sistema telerobotizado basado en la Web

47