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