Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
SegmentacionDominio de imagen
Leccion 02.2
Dr. Pablo Alvarado Moya
MP6127 Vision por ComputadoraPrograma de Maestrıa en Electronica
Enfasis en Procesamiento Digital de SenalesEscuela de Ingenierıa Electronica
Tecnologico de Costa Rica
II Cuatrimestre 2019
P. Alvarado Segmentacion: dominio de imagen 1 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Contenido
1 Segmentacion a nivel de imagen
2 Metodos basados en espacios de caracterısticasUmbralizacionHistogramasAglomeracion
3 Metodos basados en el dominio de imagen
P. Alvarado Segmentacion: dominio de imagen 2 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Segmentacion a nivel deimagen
P. Alvarado Segmentacion: dominio de imagen 3 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Homogeneidad
En el nivel de imagen no hay concepto de objeto
Base: Criterio de homogeneidad o uniformidad
Supuesto: objetos se componen de superficies homogeneas
P. Alvarado Segmentacion: dominio de imagen 4 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Segmentacion basada en imagen
La segmentacion basada en imagen se define
en terminos de un predicado de homogeneidad HI , y
un predicado de adyacencia A
P. Alvarado Segmentacion: dominio de imagen 5 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Definicion
Definicion (Segmentacion basada en imagen)
La segmentacion basada en imagen SI de una imagen I es unaparticion de I que satisface para cada region Ri ∈ SI ,HI (Ri ) = verdadero, y HI (Ri ∪Rj) = falso paraA(Ri ,Rj) = verdadero.
P. Alvarado Segmentacion: dominio de imagen 6 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Condiciones
La condicion H(Ri ∪Rj) = falso previene sobre-segmentacion.
Cada metodo provee una implementacion particular de H.
Cada metodo impone restricciones adicionales para una region(p.ej. H actua sobre regiones conexas).
P. Alvarado Segmentacion: dominio de imagen 7 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Metodos de segmentacion a nivel de imagenClasificacion
Segmentacion a nivel de imagen
Espacio de caracterısticas Dominio de imagen Hıbrido
Umbralizacion
Aglomeracion
Basado en area
Basado en bordes
C+I
Regularizacion
Etiquetado consistente
Algunos autores incluyen metodos basados en fısica, queconsideran proceso de formacion de imagen
Informacion adicional ⇒ nivel de superficies
P. Alvarado Segmentacion: dominio de imagen 8 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Espacios de caracterısticas
P. Alvarado Segmentacion: dominio de imagen 9 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Metodos basados en espacios de caracterısticas
Sean los pıxeles ei =⟨
pi,ci
⟩de la imagen
Metodos basados en caracterısticas solo usan c
Recordar c indica color, textura, bordicidad, etc.
P. Alvarado Segmentacion: dominio de imagen 10 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Ejemplos
Umbralizacion
Algoritmo de OtsuUmbral adaptativo
Maximos de histogramas
Aglomeracion
k-medias (k-means)Desplazamiento de media (mean-shift)
P. Alvarado Segmentacion: dominio de imagen 11 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Umbralizacion
Imagen se parte en clases fondo y objeto
Todos los pıxeles e =⟨p,c⟩
con c < t se asignan al fondo
De otro modo se asignan al objeto
t es el umbral (threshold)
El usuario lo puede proveer directamente
Se puede calcular:
Un porcentaje de pıxeles debe pertenecer al objeto/fondoUsar estadısticos para determinar el umbral (µ, σ)
P. Alvarado Segmentacion: dominio de imagen 12 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Algoritmo de Otsu (1)Ejemplo de umbralizacion
1 Calcular histograma y correspondientes probabilidades
2 Inicialice ωi (t = 0) y µi (t = 0) con
ω0(t) =t−1∑j=0
p(j) µ0 =t−1∑j=0
p(j)j
ω1(t) =max∑j=t
p(j) µ1(t) =max∑j=t
p(j)j
P. Alvarado Segmentacion: dominio de imagen 13 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Algoritmo de Otsu (2)Ejemplo de umbralizacion
3 Para t=1 hasta maximo valor de intensidad
1 Actualice ωi y µi
2 Calcule σ2b(t)
σ2b(t) = ω0(t)ω1(t)[µ1(t)− µ0(t)]2
4 Umbral corresponde al t con maximo σ2b(t)
P. Alvarado Segmentacion: dominio de imagen 14 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Ejemplo
Ver ejemplo ltilib-2/examples/thresholding
P. Alvarado Segmentacion: dominio de imagen 15 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Analisis con Histogramas
0
2000
4000
6000
8000
10000
0 0.2 0.4 0.6 0.8 1
Num
ber
of P
ixels
Intensity
Intensity Histogram
0
2000
4000
6000
8000
10000
R Y G C B M
Num
ber
of P
ixels
Hue
Hue Histogram
RY
GC
BM
0 0.2 0.4 0.6 0.8 1H
ue
Intensity
Histogram Cells
P. Alvarado Segmentacion: dominio de imagen 16 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Aglomeracion
Aglomeracion (clustering) es un proceso de clasificacion nosupervisado
Busca agrupar objetos/observaciones similares
Ejemplos de metodos:k-medias: k indica cuantos conglomerados
Se usa en cuantificacion de coloresCuantificacion junto a filtro mediana se usa como segmentador
desplazamiento de media: que tan grandes
P. Alvarado Segmentacion: dominio de imagen 17 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Ejemplo de aglomeracion
RY
GC
BM
0 0.2 0.4 0.6 0.8 1
Hue
Intensity
Clusters
RY
GC
BM
0 0.2 0.4 0.6 0.8 1
Hue
Intensity
Clusters
P. Alvarado Segmentacion: dominio de imagen 18 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Aglomeracion con k-medias
Dado el conjunto de observaciones (x1, x2, . . . , xn)
k-medias busca asignar las observaciones a los conjuntosS = {S1, . . . ,Sk} de modo que se minimice la suma dedistancias cuadradas a la media µ
ide cada conglomerado Si
arg mınS
k∑i=1
∑xj∈Si
‖xj − µi‖2
Algoritmo alterna entre un paso de asignacion y otro deactualizacion
P. Alvarado Segmentacion: dominio de imagen 19 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Algoritmo de k-medias
1 Inicialice las k medias m1,m2, . . . ,mk
2 Asigne cada observacion a media mas cercana:
S(t)i =
{xp : ‖xp −m
(t)i ‖ ≤ ‖xp −m
(t)j ‖,∀1 ≤ j ≤ k
}3 Actualice las medias
m(t+1)i =
1
S(t)i
∑xj∈S
(t)i
xj
4 Repita hasta que no haya cambios
http://youtu.be/74rv4snLl70
http://youtu.be/zaKjh2N8jN4
P. Alvarado Segmentacion: dominio de imagen 20 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Aglomeracion por desplazamiento de medias (1)Mean-shift
Propuesto por D. Comaniciu and P. Meer alrededor de 1998
Se basa en desplazamiento de medias para encontrar modosde maxima densidad en espacios multidimensionales y lascorrespondientes vertientes de atraccion
Dadas n observaciones c1 . . . cn en un espacio d-dimensionalIRd , la estimacion de densidad con kernel K (·) de ancho h enel punto c es
f (c) =1
nhd
n∑i=1
K
(c− cih
).
P. Alvarado Segmentacion: dominio de imagen 21 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Aglomeracion por desplazamiento de medias (2)Mean-shift
Conglomerados estan en maximos de f (c), i.e. ∇f (c) = 0.
El procedimiento de desplazamiento de medias permiteencontrar esos maximos sin calcular explıcitamente f o sugradiente.
Solo se requieren las derivadas del kernel K (c)
P. Alvarado Segmentacion: dominio de imagen 22 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Aglomeracion por desplazamiento de medias (3)Mean-shift
Se usan kernels de la forma K (c) = αk(‖c‖2), con constantede normalizacion α y perfil k(x)
Perfil de Epanechnikov:
kE (x) =
{1− x 0 ≤ 1
0 x > 1(1)
asintoticamente minimiza el error cuadratico medio entredensidad real y su estimacion.
P. Alvarado Segmentacion: dominio de imagen 23 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Aglomeracion por desplazamiento de medias (4)Mean-shift
Perfil normal:
kN(x) = exp
(−1
2x
)(2)
engendra el kernel normal
KN(c) = (2π)−d/2 exp
(−1
2‖c‖2
)(3)
que se prefiere por ser derivable aun en cero
P. Alvarado Segmentacion: dominio de imagen 24 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Calculo de densidad (1)
El calculo de la densidad usa la funcion g(x) = −k ′(x), quedefine a un nuevo kernel G (c):
G (c) = βg(‖c‖2
)(4)
con constante de normalizacion β.
Con el perfil de Epanechnikov se obtiene la esfera unitariad-dimensional
GN(c) = −βk ′N(‖c‖2) manteine la forma de KN(c).
P. Alvarado Segmentacion: dominio de imagen 25 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Calculo de densidad (2)
El valor medio de los puntos en una ventana delimitada porG (c) y centrada en c es
µh,G
(c) =
∑ni=1 cig
(∥∥∥ c−cih
∥∥∥2)
∑ni=1 g
(∥∥∥ c−cih
∥∥∥2) . (5)
El vector de desplazamiento de media se define como
mh,G (c) = µh,G
(c)− c . (6)
que apunta siempre hacia la direccion de maximo incrementode densidad.
P. Alvarado Segmentacion: dominio de imagen 26 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Algoritmo de desplazamiento de medias (1)
Los modos se encuentran iterativamente
Primero, el kernel se coloca en un punto c arbitrario delespacio de caracterısticas
Luego se calcula el vector de desplazamiento mh,G (c) y setraslada la ventana G (c).
En la nueva posicion se recalcula el vector de desplazamiento,que actua sobre el kernel, y se repite el proceso
La ruta trazada desde c hasta el modo de densidad se expresacon la secuencia de puntos st :
s0 = c
st+1 = µh,G
(st)(7)
P. Alvarado Segmentacion: dominio de imagen 27 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Algoritmo de desplazamiento de medias (2)
Para perfiles k(x) monotonicamente decrecientes este procesoiterativo converge a un modo de la funcion de densidadestimada f (c)
P. Alvarado Segmentacion: dominio de imagen 28 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Algoritmo de desplazamiento de medias (3)
0
0.2
0.4
0.6
0.8
1
0 0.2 0.4 0.6 0.8 1
Fe
atu
re 2
Feature 1
0
0.2
0.4
0.6
0.8
1
0 0.2 0.4 0.6 0.8 1F
ea
ture
2
Feature 1
0
0.2
0.4
0.6
0.8
1
0 0.2 0.4 0.6 0.8 1
Fe
atu
re 2
Feature 1
Procedimiento de desplazamiento de medias con 56 puntos y ancho de banda h = 0,1 con un kernel
normal. Se usaron seis iteraciones por punto aproximadamente
P. Alvarado Segmentacion: dominio de imagen 29 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Algoritmo de desplazamiento de medias (4)
Cada conglomerado se forma agrupando los puntos que tienenrutas hacia el mismo modo.
Puesto que una imagen tiene miles de pıxeles, el espacio decaracterısticas se cuantifica para reducir el volumen de datos.
Se usan otras tecnicas para busqueda multidimensional paraencontrar los puntos que cubre el kernel
Comaniciu y Meer usan una combinacion de espacio y colorCIE L∗u∗v∗ como caracterıstica
Khp ,hc (p,c) =C
h2ph
dc
k
(∥∥∥∥ p
hp
∥∥∥∥2)k
(∥∥∥∥ c
hc
∥∥∥∥2)
(8)
P. Alvarado Segmentacion: dominio de imagen 30 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
UmbralizacionHistogramasAglomeracion
Ejemplo
Original Mean-shift filter Segmentation
Anchos de banda utilizados hp = 15 pixels y hc = 5 unidades de color. Imagen de 442 × 424 pıxeles tomo 240
segundos con un Intel Pentium 4 (2.8 GHz).
P. Alvarado Segmentacion: dominio de imagen 31 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Metodos basados enel dominio de imagen
P. Alvarado Segmentacion: dominio de imagen 32 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Metodos basados en el dominio de imagen
Sean los pıxeles e =⟨p,c⟩
de la imagen
Estos metodos usan valores de c en vecindades
Dos grupos1 Basados en area: similitud de caracterısticas2 Basados en bordes: discontinuidades
Hay metodos hıbridos
P. Alvarado Segmentacion: dominio de imagen 33 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Metodos basados en area
Dos principios
Crecimiento de region (region growing)Division y fusion (split-and-merge)
Crean regiones con borde menos ruidoso que metodos deaglomeracion
P. Alvarado Segmentacion: dominio de imagen 34 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Metodos basados en areaCrecimiento de region
Utiliza semillas
P. Alvarado Segmentacion: dominio de imagen 35 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Metodos basados en areaDivision y fusion con Quadtrees
P. Alvarado Segmentacion: dominio de imagen 36 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Metodos basados en bordes
Parten de estimaciones de bordicidad
Contornos Activos
Divisorias (Watersheds)
P. Alvarado Segmentacion: dominio de imagen 37 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Ejemplo: Divisorias (Watersheds) (1)
Las divisorias son un operador morfologico planteado porDigabel and Lantuejoul 1977
Divisoria es en topografıa la linea que divide cuencashidrograficas.
x
y
x
y
P. Alvarado Segmentacion: dominio de imagen 38 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Ejemplo: Divisorias (Watersheds) (2)
En 1991 algoritmo de inmersion de Vincent y Soille las llevana la practica (eficiente para imagenes enteras)
P. Alvarado Segmentacion: dominio de imagen 39 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Ejemplo: Divisorias (Watersheds) (3)
En 1999 De Smet and Piret proponen el algoritmo de lluviapara imagenes en punto flotante.
P. Alvarado Segmentacion: dominio de imagen 40 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Ejemplo: Divisorias (Watersheds) (4)
El algoritmo de lluvia detecta cuencas, mientras que elalgoritmo de inmersion detecta divisorias.
P. Alvarado Segmentacion: dominio de imagen 41 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Sobresegmentacion (1)
El mayor problema de las divisorias es la sobresegmentacion
Posible solucion:
Edge−preserving smoothing
Watershed Transform
Region Merging
Color Contrast Gradient
Adaptive Flood Level
P. Alvarado Segmentacion: dominio de imagen 42 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Sobresegmentacion (2)
Ejemplo de inundacion inicial para reducir ruido
Flood
Level
P. Alvarado Segmentacion: dominio de imagen 43 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Sobresegmentacion (3)
Sensibilidad a nivel de inundacionl = 1,56 % l = 3,14 %
572 Regions 275 Regions
1973 Regions 898 Regions
Filtro de mediana de 5 × 5. Niveles de inundacion iniciales de 1,6 % y 3,1 % del valor maximo de magnitud
de gradiente
P. Alvarado Segmentacion: dominio de imagen 44 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Resumen
1 Segmentacion a nivel de imagen
2 Metodos basados en espacios de caracterısticasUmbralizacionHistogramasAglomeracion
3 Metodos basados en el dominio de imagen
P. Alvarado Segmentacion: dominio de imagen 45 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Tarea 2
1 Revisar con detalle artıculo de Comaniciu y Meer sobremean-shift
2 Revisar artıculo de watersheds
3 Montar un tablero de ajedrez simple (hoja impresa sobre tablao carton duro)
4 Hacer un programa en C++ usando la LTI-Lib-2, la OpenCVo una combinacion de ambas, para segmentar con mean-shifty con watersheds las imagenes del tablero en diferentesposiciones.
5 Integre a sus pruebas el algoritmo de segmentacion CWAGM(solo en la LTI-Lib-2
P. Alvarado Segmentacion: dominio de imagen 46 / 47
Segmentacion a nivel de imagenMetodos basados en espacios de caracterısticas
Metodos basados en el dominio de imagen
Este documento ha sido elaborado con software libre incluyendo LATEX, Beamer, GNUPlot, GNU/Octave, XFig,Inkscape, LTI-Lib-2, GNU-Make, Kazam, Xournal y Subversion en GNU/Linux
Este trabajo se encuentra bajo una Licencia Creative Commons Atribucion-NoComercial-LicenciarIgual 3.0 Unpor-ted. Para ver una copia de esta Licencia, visite http://creativecommons.org/licenses/by-nc-sa/3.0/ o envıeuna carta a Creative Commons, 444 Castro Street, Suite 900, Mountain View, California, 94041, USA.
© 2017 Pablo Alvarado-Moya Escuela de Ingenierıa Electronica Instituto Tecnologico de Costa Rica
P. Alvarado Segmentacion: dominio de imagen 47 / 47