112082 - J. Neira – Universidad de Zaragoza
Lección 4: Reconocimiento basado en descriptores
1. Introducción2. Clasificación Bayesiana3. Clasificación por distancias4. Árboles de decisión5. Otros métodos6. Conclusiones
212082 - J. Neira – Universidad de Zaragoza
1. Introducción
• Reconocimiento basado en descriptores: propiedades globales invariantes, objetos completamente visibles
» Área» Perímetro» No. de Euler» Elongación» ...
• Más sencillo, menos robusto
• Reconocimiento Geométrico:propiedades locales
» Vértices» Aristas» Círculos» Esquinas» ...
• Más complejo, más robusto
• Reconocimiento 2D: etiquetado de regiones correspondientes a objetos 2D en la imagen.
312082 - J. Neira – Universidad de Zaragoza
Esquema generalAprendizaje:• Tomar varias imágenes de cada
objeto, y calcular sus descripto-res
Explotación:• Calcular de los descriptores de
cada objeto en la imagen
• Comparar con los valores esti-mados de los descriptores de los objetos conocidos
Notación:
• n objetos conocidos (clases):
• m descriptores utilizados:
• N muestras del descriptor j de la clase i:
Dada una muestra x, ¿a qué clase ωi corresponde?
Dada una muestra x, ¿a qué clase ωi corresponde?
¿se trata de un objeto desconocido?
¿se trata de un objeto desconocido?
Diferentes métodos usan diferentes técnicas para
efectuar esta comparación
Diferentes métodos usan diferentes técnicas para
efectuar esta comparación
412082 - J. Neira – Universidad de Zaragoza
2. Clasificación Bayesiana• Los descriptores se consideran
variables aleatorias.
• Modelo probabilístico de cada clase:
• Probabilidad a priori de cada clase:
• Se calcula la probabilidad de que la muestra provenga de la obser-vación de cada clase utilizando la regla de Bayes.
512082 - J. Neira – Universidad de Zaragoza
Clasificación Bayesiana• Regla de Bayes:
• Distribuye la probabilidad entre todas las clases:
• Decidimos ωi si:
612082 - J. Neira – Universidad de Zaragoza
Clasificación Bayesiana• Influencia de P(ωi): • Influencia de p(x/ωi):
712082 - J. Neira – Universidad de Zaragoza
Descriptores• Ejemplo: el área • En ausencia de más informa-
ción, caracterizamos un des-criptor por medio de una distri-bución Gaussiana:1727
16831766192418861914203819651967199921392089214621582460
N=15
0
1
2
3
4
5
6
1700 1800 1900 2000 2100 2200 2500
812082 - J. Neira – Universidad de Zaragoza
Descriptores• Media muestral: valor repre-
sentativo:
• Varianza muestral: dispersión o variabilidad
500 1000 1500 2000 2500 3000 35000
1
2
3
4
5
6
7
8
9x 10-3
1 J 7 4 Z U 3 G 2 H A
Area
?
?
912082 - J. Neira – Universidad de Zaragoza
Independencia de los descriptores• Independientes: • Linealmente correlados
0
5
10
15
20
25
30
0 5 10 15 20 25 300
5
10
15
20
25
30
0 5 10 15 20 25 30
descriptor 1
desc
ripto
r 2
desc
ripto
r 2
descriptor 1
Los descriptores independientes permiten discriminar mejor entre clases.
1012082 - J. Neira – Universidad de Zaragoza
Clasificación Bayesiana• Suponiendo Gaussianidad e independencia estadística:
• Método iterativo:
• Se itera hasta que el objeto más probable supere un umbral (puede no ser necesario calcular todos los descriptores).
Are
a
Perím
RM
ax
RM
in M1
M2
M3
M4
M5
M6
M7
0,00,10,20,30,40,50,60,70,80,91,0
1112082 - J. Neira – Universidad de Zaragoza
Medición secuencial de descriptores• Suponiendo que:
• El área no es un parámetro discriminante en este caso:
• El perímetro si lo es:
r
b
b
l
l
¿En qué orden calcular los descriptores?¿En qué orden calcular los descriptores?
1212082 - J. Neira – Universidad de Zaragoza
Medición secuencial de descriptores• Poder discriminante del parámetro k entre las clases ωi y ωj:
• Ejemplo:
Círculo GranCir CirTruncadGranCir 63.47
CirTruncad 1.94 102.64CirSaliente 153.58 2.20 220.13
J-Div ergencia
142 152 162 172 182 1920
0,02
0,04
0,06
0,08
0,1
0,12
0,14
0,16
0,18
Perímetro
CirTruncado
Circulo
CirSaliente
GranCir
Are
a
Perím
RM
ax
RM
in M1
M2
M3
M4
M5
M6
M70,0
0,10,20,30,40,50,60,70,80,91,0
En orden prefijado
0,00,10,20,30,40,50,60,70,80,91,0
Circulo CirTruncado
Según su J-divergencia
Are
a
M1
M3
M5
M2
M4
M6
RM
in
Mer
im M7
RM
ax
1312082 - J. Neira – Universidad de Zaragoza
Tratamiento de objetos desconocidos
• Clase ω0 que representa al objeto desconocido:
• Distribución uniforme entre los valores mínimo y máximo del descriptor:
1412082 - J. Neira – Universidad de Zaragoza
• Teselación de Voronoi:
3. Distancias mínimas• Se calcula la distancia del
vector de descriptores a cada uno de los objetos conocidos.
• Distancia Euclidiana:
• Se escoge la clase con distancia mínima (vecino más próximo).
• La frontera de decisión entre dos clases estará dada por:
1512082 - J. Neira – Universidad de Zaragoza
Ejercicio• Dadas las siguientes muestras de los descriptores x1 y x2 de dos clases:
• Determinar la ecuación de la curva que representa la frontera de decisión entre las dos clases de acuerdo con la distancia Euclidiana, ygraficarla.
0
1
2
3
4
5
6
7
8
0 2 4 6 8 10
Clase 1Clase 2
Clase 1 Clase 2x1 x21 32 12 22 32 43 23 34 35 21 2
x1 x24 55 55 64 76 56 66 77 64 68 7
1612082 - J. Neira – Universidad de Zaragoza
• Equivalente a la clasificación Bayesiana cuando:
– Todas las clases son equiprobables a priori
– Todos los descriptores tienen la misma varianza
• Siempre se escoge una clase, o es necesario definir una dis-tancia máxima arbitraria.
Distancia Euclidiana• Interpretación clara sólo si x1 y
x2 tienen las mismas unidades– x1 = perímetro– x2 = área
• Sensible a cambios de escala (p.e. perímetro medido en mmo em cm).
1712082 - J. Neira – Universidad de Zaragoza
• m = 2:
• ω2: x1 menos preciso que x2(influye menos en D2).
• Puede contradecir a la distancia Euclidiana.
Distancias mínimas• Distancia de Mahalanobis:
• Distancia adimensional; conside-ra la imprecisión del descriptor (la varianza)
• Caso general, define una familia de elipses (ecuación de los pun-tos a distancia k de μ):
1812082 - J. Neira – Universidad de Zaragoza
Distancia de Mahalanobis• Test de hipótesis:
– μij: valor esperado– σij: desviación esperada– xj: valor observado
• H0: {x proviene de ωi }• α: nivel de confianza
• m = 2:
• Se escoge la clase de menor dis-tancia que pase este test de hipótesis.
• La detección de falsos positivos es más compleja (involucra al resto de las clases).
Tablas de Chi-cuadradom\ α 0.05 0.025 0.011 3.84 5.02 6.642 5.99 7.38 9.223 7.82 9.36 11.32
Una hipótesis correcta serárechazada con probabilidad α
(% de falsos negativos).
Una hipótesis correcta serárechazada con probabilidad α
(% de falsos negativos).
1912082 - J. Neira – Universidad de Zaragoza
Ejercicio• Dado un objeto caracterizado por m descriptores indepen-
dientes, y dada una muestra de cada descriptor:
• ¿Puede cada muestra ser estadísticamente compatible con el correspondiente descriptor, y sin embargo ser las mues-tras conjuntamente incompatibles con los descriptores del objeto?
• ¿Puede la muestra de algunos descriptores ser estadística-mente incompatible con el correspondiente descriptor del objeto, y sin embargo ser las muestras conjuntamente com-patibles con los descriptores del objeto?
2012082 - J. Neira – Universidad de Zaragoza
Euclidiana .vs. Mahalanobis• m = 1: • Euclidiana .vs. Mahalanobis
500 1000 1500 2000 2500 3000 3500
medida
Distancia Euclidiana
aceptadarechazada
500 1000 1500 2000 2500 3000 3500
3.84
Intervalo de aceptación
2112082 - J. Neira – Universidad de Zaragoza
Distinguibilidad entre objetos
• Distancia entre dos clases:
• Permite evaluar el potencial de un conjunto de descrip-tores
Si la hipótesis es aceptable, las clases ωi y ωk son indistinguiblesSi la hipótesis es aceptable, las clases ωi y ωk son indistinguibles
500 1000 1500 2000 2500 3000 35000
1
2
3
4
5
6
7
8
9x 10
-3
1 J 7 4 Z U 3 G 2 H A
Area
2212082 - J. Neira – Universidad de Zaragoza
Número de muestras• La varianza σ2 no está
definida para N=1• Si N es pequeño, tiende a
ser optimista (subestima la varianza)
• σ20: estimación a priori de
la varianza (p. e. el cuadrado del 1% del valor del descriptor)
• Para N grande, tiende a la varianza clásica
0
50
100
150
200
250
0 5 10 15 20Muestras
Des
v. E
st.
σ2
σ2N
2312082 - J. Neira – Universidad de Zaragoza
4. Árboles de Decisión• Secuencia de preguntas condi-
cionadas a la respuesta de la pregunta anterior.
• Método no métrico (no se basa en mediciones de distancias).
• Ventajas:– Interpretabilidad– Puede incluir descriptores no
numéricos– Permite incorporar conocimiento
de expertos
• CART (Classification andRegression Trees): dados un conjunto de muestras de mdescriptores de n clases:
– División recursiva de las muestras de acuerdo con un descriptor.
1. ¿qué factor de división usar?2. ¿qué descriptor consultar en un
nodo?3. ¿cuándo detener la división?4. ¿cómo optimizar un árbol
(hacerlo más pequeño, más simple)?
5. ¿qué hacer con nodos impuros?6. ¿cómo manejar información no
disponible?
Perímetro >9?
NO SI
NO SI NO SIArea>6?
Perímetro >8?
Nº Agujeros >0?
NO SI
2412082 - J. Neira – Universidad de Zaragoza
Árboles de decisión• Importancia de la selección de los descriptores
• Desventajas:– Un error en un descriptor puede impedir reconocer el
objeto correctamente.– Siempre escoge una clase (o hay que introducir el objeto
desconocido en muchos sitios).
2512082 - J. Neira – Universidad de Zaragoza
5. Otros Métodos• Métodos paramétricos
(los anteriores): estimación de los parámetros de la función p(x/ωi) que caracte-riza a cada clase y que se supone conocida.
• Métodos NO paramétricos:
– Estimación de la función de probabilidad:
– Estimación de la probabilidad a posteriori:
• Probabilidad a posteriori:Dada una ventana Valrededor de x, que incluye k muestras, ki de las cuales pertenecen a ωi:
2612082 - J. Neira – Universidad de Zaragoza
El vecino más próximo• Dadas N muestras de m
descriptores de n clases:
• Dados m descriptores del objeto a identificar:
• Escoger la clase ωi tal que:
• Usar teselación de Voronoi
• Método subóptimo: tasa de errores mayor que la Clasificación Bayesiana.
¡La tasa de erroresno es más del doble!¡La tasa de errores
no es más del doble!
2712082 - J. Neira – Universidad de Zaragoza
Los k vecinos más próximos• Escoger la clase ωi más
fre-cuente en los k vecinos más próximos a x.
• Los empates se pueden evitar aumentando k (n=2, kimpar).
• Para n, m y N grande, es computacionalmente costo-so.
• Distancias parciales:
• Se abandona el cálculo de la distancia a una muestra cuan-do la distancia parcial es mayor que la distancia total al k-ésimo vecino.
2812082 - J. Neira – Universidad de Zaragoza
6. Conclusiones• Métodos de complejidad lineal• Descriptores invariantes en 2D
OK
!Solapamiento!
!Visibilidad parcial!
Reconocimiento geométrico