Reconocimiento de FormasReconocimiento de Formas

IntroducciónIntroducciónJosé Martínez Sotoca

Dept. Lenguajes y Sistemas InformáticosUniversidad Jaume I

E-12071 Castellón (España)http://www.vision.uji.es/~sotoca/docencia.html

2

Temario del Curso1. Introducción.

• ¿Qué es el reconocimiento de formas (RF)?• Configuración de un sistema RF.• Taxonomia de problemas RF.

2. Técnicas paramétricas.• 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.

3. 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.

3

Temario del Curso4. Aprendizaje no supervisado.

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

5. Técnicas de reducción de la dimensionalidad.• 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.

6. Análisis Sintáctico.• Modelos de Markov.• Algoritmo de Viterbi.• Ejemplo de un traductor automático.

4

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.

5

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 Tools-Synergy 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.

6

• Clustering:

– K. Rose. “Deterministic Annealing for Clustering, Compression, Classification, Regression, andRelated 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”.

7

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.

8

• 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.

9

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.

10

Sistema humano• 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:1. Estudio de los mecanismos de Reconocimiento de los seres vivos:

Psicología, Fisiología, Biología.2. Desarrollo de teoría y técnicas para realizar tareas de Reconocimiento en

una aplicación determinada: Ciencias de la Computación, Ingeniería.

11

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.

12

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.

13

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.

14

• 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.

15

Representación de Patrones

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

16

Bases del reconocimiento de Patrones

Patron Sensor(s)

x1x2x3

xn

. . . Clasificador(s)

Resultado(etiqueta clase)X

17

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 delos 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.

18

• 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.

19

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.

20

• 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.

21

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.

22

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.

23

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.

24

• 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.

25

Sistema de RF Estadístico (REF)Fase de Entrenamiento Fase de Clasificación

Conjunto de entrenamiento

Extracción / Selecciónde características

Aprendizaje

Conjunto de test

Preproceso

Medición decaracterísticas

Clasificación

Preproceso

26

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 dcaracterí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

27

Funciones Discriminantes

• Podemos expresar el clasificador δ en términos de cfunciones 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.

28

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.

29

Taxonomía del REF (1)

Aproximaciónparamétrica

Aproximaciónno 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.

• 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.

30

Taxonomía del REF (2)

Aprendizajesupervisado

Aprendizajeno supervisado

• Se dispone de un conjunto de muestras sin etiquetar.

• El número de clases puede ser también desconocido.

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

Clasificación por criterios de vecindad Clustering

31

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.

32

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).

33

Ejemplo de un Sistema REF

Perímetro

Inte

nsid

ad R

ojo

NaranjaFresa

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

34

Ejemplo de un Sistema REF

Perímetro

Inte

nsid

ad R

ojo

Función discriminante (fd)

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

Representación de

la frontera de decisión.

35

Ejemplo de un Sistema REF

Naranja malclasificada

Perímetro

Inte

nsid

ad R

ojo

Clasificación de un nuevo patrón.

36

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.

37

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.

38

...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.

Clasificación de frutos en líneas de selección

eVis. Enginyeria Visual

40

El sistema generalCONTROLCONTROL

ENTORNOUSUARIO

ENTORNOUSUARIO

ENCODERENCODER

LINEA DETRANSPORTE

LINEA DETRANSPORTE

MÓDULOSSALIDAS

MÓDULOSSALIDAS

MÓDULOSPESO

MÓDULOSPESO

MÓDULOSVISIÓN

MÓDULOSVISIÓN

LAN

CAN

41

Módulo de visiónMÓDULO DE VISION

• Arquitectura sistema empotrado basado en PC

• Sin entorno de usuario• Comunicaciones

CAN/LAN

CÁMARACÁMARA DIGITALIZADOR RAM

PROCESADOR

INTERFAZLAN

INTERFAZCAN

ENTORNOUSUARIO

ENTORNOUSUARIO CONTROLCONTROL

PCI BUS

LAN CAN

42

Adquisición de imagen• Cámaras RGB + IR:

– barrido progresivo– reset asíncrono

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

43

Maquina de clasificación de Frutas.

44

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.

45

Un sistema de monotorización de tráfico

46

Inspección de paquetes de salchichas

47

Un sistema telerobotizado basado en la Web