Reconocimiento de Formas
Contextualización
Temario del Curso
1.
Introducción.
•
•
•
2.
¿Qué es el reconocimiento de formas (RF)?
Configuración de un sistema RF.
Taxonomia de problemas RF.
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.
2
Temario del Curso
4.
Aprendizaje no supervisado.
•
•
•
5.
Técnicas de reducción de la dimensionalidad.
•
•
•
•
6.
Análisis de agrupamientos.
Validación del agrupamiento.
Aproximación difusa.
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.
Tema selecto
3
Bibliografía Básica
• Andrew R. Webb. Statistical Pattern Recognition. Second Edition, John Wiley
and Sons Ltd. 2002.
• 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, E. Pekalska, R.P. W. Duin. “Experimental study on
prototype optimization algorithms for prototype-based classification in vector spaces”.
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 Computador, 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
CONTROL
LINEA DE
TRANSPORTE
LAN
ENTORNO
USUARIO
MÓDULOS
SALIDAS
MÓDULOS
VISIÓN
CAN
MÓDULOS
PESO
40
Módulo de visión
MÓDULO DE VISION
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
USUARIO
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
Descargar

Reconocimiento Estadístico de Formas