PDF de programación - Técnicas de inteligencia artificial - Visión Artificial

Técnicas de inteligencia artificial

Visión Artificial
Segmentación

Indice
 Introducción
 Algoritmo de las K-medias
 Mean-Shift
 Segmentación basada en regiones

Introducción
 La segmentación de imágenes es el proceso de

extraer zonas de la imagen con el mismo color/nivel
de gris/textura para identificarlas automáticamente

Algoritmo de las K-medias
 Encuentra las medias de las distribuciones
(clusters) (sirve para cualquier problema de
aprendizaje)

 Es necesario conocer el número de distribuciones

(clusters) distintas existentes

Algoritmo de las K-medias
1)Inicialización: se buscan k puntos (medias)
2)Hacer

2)Cálculo de las nuevas medias
3)Hasta que no haya cambios

1)Pertenencia: para cada punto, se encuentra la

distribución (cluster) más cercana (el k más cercano)

Inicialización
 Para elegir la inicialización, podemos:
Asignar las medias de manera aleatoria.
Redistribuir las medias de manera uniforme
Usar alguna heurística (por ejemplo, en secuencias de

imágenes, usar las medias resultado anteriores)

Cálculo de la pertenencia
 Dependerá del problema:

media y varianza

−(x−μ)2

)

Distancia euclídea: el k más cercano
Probabilidad de pertenencia a un cluster: usando su

P(x)=

1

√2 π σ 2 exp(

σ 2

Cálculo de las nuevas medias
 Para cada cluster, recalcular su media (y varianza,

si es el caso), usando todos los puntos que
pertenecen a ese cluster
Si es distancia euclídea:

μcluster=

xi

n

Si es probabilidad:

μcluster=

1
n ∑

i=1

p( xi) xi

n

∑

i=1
n

∑

i=1

p ( xi)

K-medias para segmentación de imágenes
 Imágenes de gris: se usan los valores de gris, no las

Usar directamente los valores R,G,B
Convertir a H,S,B y usar la componente H

posiciones de los píxeles.

 Imágenes de color:

K=2 63ms

K=4 353ms

K=8 1100ms

(probabilidad K=4 112ms

Características de las K-medias
 Es necesario indicar K
 Una mala inicialización puede llevar más tiempo
 Puede no encontrar la solución más óptima
 En su modo probabilístico:

Se puede aplicar a cualquier tipo de distribución

(texturas)

Se pueden usar distintas medidas de distancia a

distribución (Mahalanobis, Kullback-Leiber)

 Se conoce también como: segmentación EM, Fuzzy

K-means

Método de Mean-Shift
 Método iterativo no paramétrico que puede ser usado

para clustering, segmentación, etc.

 Encuentra las modas de unas distribuciones, pero sin

necesitar saber cuántas modas tenemos

 Para ello, define una región alrededor de ese punto y
encuentra su media, cambiando la situación de la media
actual a la nueva (shift). Repite el proceso hasta que
converja

 Considera que el espacio de datos es una función de

densidad de probabilidad muestreada

 Para cada punto del conjunto de datos, encuentra la

moda más cercana

Ejemplo

Region of
interest
Center of

mass

Mean Shift

vector

Ejemplo

Region of
interest
Center of

mass

Mean Shift

vector

Ejemplo

Region of
interest
Center of

mass

Mean Shift

vector

Ejemplo

Region of
interest
Center of

mass

Mean Shift

vector

Ejemplo

Region of
interest
Center of

mass

Ascensión de colina (hill-climbing)
 Se ejecuta para cada punto del espacio de entrada
 Cada punto convergerá a su moda más cercana

¿Cómo se calcula la media? Kernels
 Kernels:

Kernel es una función que satisface: y
Puede ser cualquier función, p.e. Gaussiana

 Existe una manera de calcular la estimación de
densidad de probabilidad del kernel (ventana de
Parzen)

n

f (x)=

1
nhd ∑

i=1

K(∥ x− xi
h ∥2)

donde h es el ancho de banda (ancho del dominio
de búsqueda) y d es el número de dimensiones de
los datos

¿Cómo se calcula la media? Descenso gradiente
 Podemos usar un descenso por gradiente para ir

encontrando el cambio de la media

 Calculamos el gradiente:
K(∥ x− xi
h ∥2)
1
nhd ∑
nh d +2(∑
x K '(∥x− xi
h ∥2)=

( x− xi) K '(∥ x− xi

f (x)=

i=1

i=1

2

n

n

n

n

h ∥2)−∑

i =1

h ∥2))
xi K '(∥x− xi

∇ f ( x)=

2
nh d +2 ∑
 Haciendo

i=1

g (x)=− K ' (x )

∇ f ( x)= 2

n

nh d +2(∑

i=1

xi g(∥x− xi

h ∥2)−x∑

i =1

n

g(∥x −xi

h ∥2))= 2

nh d+ 2∑

i =1

n

g(∥ x− xi

i=1

h ∥2)(∑

n

n

xi g(∥x −xi
h ∥2)
g(∥x− xi
h ∥2)
∑

i=1

− x)

¿Cómo se calcula la media? Descenso gradiente
 Igualamos a cero para encontrar el máximo:

∇ f ( x)= 2

n

nh d +2 ∑

i=1

g(∥ x− xi

− x)=0

n

n

i =1

i =1

h ∥2)(∑

xi g(∥ x− xi
h ∥2)
g(∥x −xi
h ∥2)
∑
xi g(∥ x− xi
h ∥2)
g(∥ x− xi
h ∥2)
∑

− x)

i =1

n

i =1

m(x )=(∑

n

 m(x) es el valor de cambio de media (mean-shift)

que hay que hacer en cada iteración

Algoritmo Mean-shift
 Este algoritmo es iterativo
 En el caso de imágenes, para cada punto:

1)Tenemos el valor del pixel en la primera iteración, x0
2)Calculamos el valor de m(x)
3)Sumamos el valor de m(x) a x y volvemos al paso 2 hasta

que converja

n

y t+1= yt+m( y t)= yt+(∑

i=1

n

∑

i=1

y0= x
xi g(∥ yt− xi
h ∥2)
g(∥ yt− xi
h ∥2)

n

i =1

− y t)=(∑

n

∑

i=1

xi g(∥ yt−xi
h ∥2)
g(∥ y t− xi

h ∥2))

Ejemplos

Pruebas con distinta h: 3, 6, 12

Comparación con el K-medias
 Mean-shift no necesita inicializar el número de

clusters

outliers

banda h

 K-medias asume una determinada forma de las
distribuciones mientras que Mean-shift permite tener
distintos tipos de distribuciones (cambiando el
núcleo)

 K-medias es muy sensible a la inicialización y a

 K-medias tiene una menor complejidad (más rápido)
 Mean-shift es sensible a la elección del ancho de

Segmentación basada en regiones
 El objetivo es encontrar regiones de la imagen

homogéneas según algún criterio

 Hay dos maneras:

Crecimiento de regiones (region growing): empezamos con
regiones pequeñas (semillas) y las hacemos crecer o bien las
mezclamos, usando un criterio de similaridad

Partición de regiones (region splitting): empezamos con
regiones grandes (incluso toda la imagen) y las vamos
dividiendo usando un criterio de homogeneidad
 Existen métodos que combinan las dos maneras

Crecimiento de regiones

Computer Vision, Graphics and Image Processing. V. 29 (1). 1985

 Haralick and Saphiro “Image segmentation techniques”
 Asume que una región es un conjunto de píxeles

conectados

 Sea R una región de N píxeles

μ=

σ2=∑

I (xi)

1
N ∑
x i∈R
( I ( xi)−μ)2

x i∈ R

 Tenemos que definir un test de similaridad para
saber si un nuevo píxel y, adyacente a algún píxel
de R, se puede añadir a la región

Crecimiento de regiones: test de similaridad
 Podemos definir el siguiente test:

Calculamos T:

T =√[ (N −1)N

(N +1)

( y −μ)2

σ2

]

Si T es lo suficientemente pequeño, añadimos y a R

 Si se añade, debemos actualizar la media y

varianza:

μnueva=

N μ+ y
(N +1)

2 =σ2+( y −μ nueva)2+ N (μ nueva−μ)2
σnueva

 Si no se añade, empezamos a calcular una nueva

región con dicho píxel

 Sin embargo, es mejor lanzar un conjunto de

“semillas”, es decir, lanzar varios puntos de partida

 Para ello, se puede hacer lo siguiente:

Crecimiento de regiones: semillas
 El método anterior lo podemos hacer empezando

por cualquier píxel de la imagen

Se aplica un detector de aristas
Los puntos cuyo valor de magnitud de gradiente estén
próximos a cero, serán “valles”, es decir, puntos dentro
de regiones

Usaremos esos puntos para hacer una “inundación” del
valle (los usamos como “semillas” del método anterior)

Partición de regiones
 Este proceso es el inverso del anterior
 Partimos una única región (toda la imagen) y

 Conlleva una complejidad adicional, al tener que

manejar alguna estructura de datos adicional

usamos algún criterio de homogeneidad para partir
la región
Si se cumple el criterio, no se sigue dividiendo
Si no se cumple, se divide

 Se puede usar el histograma para dicho criterio:
ver si existen “valles”, que pueden servir a su vez
para dividir la región en otras más pequeñas.