Segmentaci´on de im´agenes y teor´ıa de grafos
Transcript of Segmentaci´on de im´agenes y teor´ıa de grafos
PROYECTO FIN DE CARRERA
Segmentacion de imagenes
y teorıa de grafos
Susana Ma Rodrıguez Lazaro
Julio de 2012
Departamento proponente: Matematica Aplicada
Tutores: Carmen Tobar Puente
Pedro M. Gonzalez Manchon
Autor: Vo Bo del tutor coordinador:
Susana Ma Rodrıguez Lazaro Carmen Tobar Puente
Indice
Introduccion I
1. Imagen, Segmentacion y Energıa 1
1.1. ¿Que es una imagen? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. ¿Que significa segmentar una imagen? . . . . . . . . . . . . . . . . . . . . 1
1.3. Energıas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.4. ¿Que tiene que ver segmentar con el concepto de energıa? . . . . . . . . . . 2
1.5. Algunos ejemplos de energıas razonables . . . . . . . . . . . . . . . . . . . 3
2. Grafos 7
2.1. ¿Que es un grafo? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2. Caminos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3. Grafos dirigidos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.4. Capacidades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.5. Redes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.6. Corte de una red . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.7. Coste de un corte. Corte mınimo . . . . . . . . . . . . . . . . . . . . . . . 10
2.8. Flujo en una red . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.9. El valor de un flujo. Flujo maximo . . . . . . . . . . . . . . . . . . . . . . 11
2.10. El coste del mınimo corte es el valor del flujo maximo . . . . . . . . . . . . 13
2.11. ¿Que es una red residual? . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3. Relacion entre Energıas y Grafos 15
3.1. Imagen y grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2. Segmentacion binaria y corte de un grafo . . . . . . . . . . . . . . . . . . . 15
3.3. Energıas representables por un grafo . . . . . . . . . . . . . . . . . . . . . 16
3.4. ¿Como son las energıas que se pueden representar por grafos? . . . . . . . 17
3.4.1. Terminos Vp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.4.2. Terminos Vp,q . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.4.3. Energıas de la tabla 1 . . . . . . . . . . . . . . . . . . . . . . . . . 22
4. El algoritmo de Boykov/Kolmogorov 25
4.1. Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.2. Inputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
4.3. Outputs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.4. Definiciones involucradas en el algoritmo . . . . . . . . . . . . . . . . . . . 26
4.4.1. Arboles S y T . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.4.2. Nodos libres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.4.3. Nodos activos y pasivos . . . . . . . . . . . . . . . . . . . . . . . . 27
4.4.4. Etapas del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . 28
4.4.5. Final del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
4.5. Orden de recorrido de nodos y arcos . . . . . . . . . . . . . . . . . . . . . . 29
4.5.1. Orden de recorrido de los nodos . . . . . . . . . . . . . . . . . . . . 29
4.5.2. Orden de recorrido de los arcos . . . . . . . . . . . . . . . . . . . . 29
4.6. Proceso del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
4.6.1. Resultado del algoritmo . . . . . . . . . . . . . . . . . . . . . . . . 39
5. Aplicacion: segmentacion de imagenes 41
5.1. Terminos dependientes de una variable . . . . . . . . . . . . . . . . . . . . 41
5.2. Terminos dependientes de dos variables . . . . . . . . . . . . . . . . . . . . 42
5.3. Ejemplo practico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
6. Conclusiones 45
Referencias 47
Introduccion
En la siguiente figura podemos ver la imagen de dos hıgados, uno sano y otro enfermo.
Figura 1: Un hıgado sano y un hıgado en el que se aprecia un tumor
Estas imagenes, y la problematica que conlleva el procesamiento de imagenes en gene-
ral, y medicas en particular, es el origen de nuestro proyecto. En la imagen de la derecha se
aprecia un hıgado alterado, y serıa importante resaltar esta alteracion mediante algun tipo
de software, que pudiese delimitar con claridad la zona alterada, es decir, segmentarla.
La segmentacion es una tecnica de tratamiento digital de imagenes que permite la
separacion de las diferentes partes de una imagen que pertenecen o pueden pertenecer a
una misma estructura. Es parte del tratamiento y procesamiento general de imagenes. En
el caso de las imagenes medicas relacionadas con el hıgado, es por ejemplo importante
poder segmentar un hıgado sano para poder calcular su volumen, un requisito necesario
antes de una donacion de un paciente sano, en el que prima donar y al mismo tiempo
conservar un volumen de hıgado suficiente.
La segmentacion es la consecucion de dos tareas que son complementarias: el re-
conocimiento y la delineacion. El reconocimiento es la ubicacion del objeto a sepa-
rar. La delineacion es la determinacion de la extension del objeto y su diferenciacion del
resto de la imagen.
El objetivo es encontrar metodos de segmentacion que sean capaces de delinear los
objetos de forma precisa y tan eficiente como lo podrıa hacer un radiologo experto, y
hacerlo de modo automatico, sin la intervencion de este.
Existen diferentes formas a partir de las cuales se puede obtener una segmentacion
de una imagen (ecuaciones en derivadas parciales, geometrıa diferencial, etc). En nuestro
proyecto usamos como referencia el algoritmo desarrollado por Yuri Boykov y Vladimir
Kolmogorov, basado en la teorıa de grafos.
Una funcion de energıa es basicamente un modo de evaluar las distintas segmentaciones
que podrıamos realizar. Un problema difıcil consiste en encontrar esta funcion de energıa,
que intentarıa evaluar distintos aspectos de la imagen. Una energıa razonable deberıa
asignar bajos valores de energıa a buenas segmentaciones del hıgado, y altos valores de
energıa a segmentaciones malas. Idealmente, nuestra energıa deberıa asignar el menor de
los valores a la mejor de las segmentaciones.
En este proyecto, en cambio, partimos de una funcion de energıa razonable, que asumi-
mos ya dada. Es entonces cuando aparece un segundo problema, clave en la segmentacion;
se trata de un problema de minimizacion, consistente en encontrar la segmentacion con
menor nivel de energıa.
Este problema puede expresarse en terminos de grafos, cuando la energıa es de tipo
submodular. Sin tratar de ser precisos por el momento, basicamente se construye un grafo
que tiene por vertices a los pıxeles de la imagen, junto con otros dos vertices terminales
(s y t), y se asigna una capacidad (un valor positivo) a cada arista del grafo. Las seg-
mentaciones binarias de la imagen (que distinguen en general objeto y fondo, hıgado de
lo no hıgado, o un tumor dentro de un hıgado), se corresponden entonces con los cortes
del grafo, es decir, una particion de los vertices de este que agrupa unos con el vertice
terminal s (fuente) y el resto con el vertice terminal t (sumidero). El coste de un corte del
grafo se calcula sumando las capacidades de las aristas cuyos extremos se han agrupado,
uno con s, el otro con t.
Si las capacidades han sido asignadas adecuadamente (cosa que es solo posible cuando
la energıa es de tipo submodular), se verifica entonces que, salvo una constante, la energıa
de una segmentacion de la imagen se corresponde con el coste del corte correspondiente
en el grafo. En resumen, para energıas de tipo submodular, y al menos de modo teorico,
podemos decir que el problema de encontrar la mejor segmentacion se reduce al problema
de encontrar el corte con menor coste de un grafo con capacidades.
Lo interesante de este asunto es el hecho de que esto puede hacerse mediante al-
goritmos, en tiempo polinomial. La razon es que, de acuerdo con el Teorema de Ford
ii
y Fulkerson, esto equivale a encontrar el flujo maximo, un problema para el que ya se
conocıan algoritmos de resolucion en tiempo polinomial. Para entender la idea fundamen-
tal de esta comparacion, uno imagina las aristas del grafo como tuberıas, y entonces la
capacidad de esta arista mide en realidad la capacidad de dicha tuberıa. El flujo maximo
es el valor del caudal mayor que podemos hacer circular entre la fuente s y el sumidero t.
Este proyecto se centra en un algoritmo concreto, que calcula el flujo maximo (y por
tanto el coste mınimo del corte, y por ende la segmentacion de la imagen con menor
energıa), debido a Boykov y Kolmogorov.
El objetivo del proyecto ha sido doble. Por un lado se ha estudiado en profundidad el
artıculo [3], tratando de reproducir de un modo claro, preciso y asequible, las ideas que
contiene. La primera seccion trata de detallar, paso a paso, la relacion entre el problema
original, la segmentacion de una imagen, y como se refleja esto en el problema de corte
mınimo de un grafo con capacidades. En concreto presentamos una sencilla hoja de calculo
en el que se discuten tres funciones de energıa distintas, usadas para evaluar las dieciseis
posibles segmentaciones de una imagen con cuatro pıxeles. En la exposicion se han recorri-
do todos los conceptos involucrados, explicandolos con detenimiento, y poniendo sencillos
ejemplos de todos ellos.
El segundo objetivo ha sido el estudio detenido del algoritmo de Boykov y Kolmogorov,
con el que se han realizado ademas una serie de pruebas, que se incluyen en una seccion
final del proyecto.
Despues de explicar las distintas etapas del algoritmo, se presento un ejemplo sencillo
de grafo, en el que se sigue paso a paso la obtencion del maximo flujo y el mınimo corte.
Por ultimo se obtiene la segmentacion de una imagen usando las tecnicas estudiadas.
Se usan las energıas propuestas por Boykov. Se ha implementado desde MATLAB usando
el codigo fuente C++ facilitado por Boykov y disponible en la web.
iii
1. Imagen, Segmentacion y Energıa
1.1. ¿Que es una imagen?
Una pantalla Ω esta formada por pıxeles p. La imagen I la constituyen estos pıxeles p
junto con un nivel de gris Ip para cada pıxel. Formalmente una imagen I es una aplicacion
(asignacion)
I : Ω ⊂ R2 → [0, 1]
p → Ip
El valor Ip es la intensidad de gris en el pıxel p. Por ejemplo, una imagen 3 x 3, constituida
por 9 pıxeles, serıa la siguiente:
0.9 0.9 0.8
0.8 0 0
0.7 0 0
Se verıa aproximadamente una imagen ası:
1.2. ¿Que significa segmentar una imagen?
Imaginemos por ejemplo la imagen diagnostica del hıgado de un paciente. En esta
imagen queremos reconocer el hıgado y un posible tumor. Podrıamos reconocer el hıgado
en negro, el tumor en rojo y el fondo en blanco, para lo que necesitarıamos 3 etiquetas:
L = 0, 1, 2 = negro, blanco, rojo
Una segmentacion f se define como una aplicacion
2 Proyecto Fin de Carrera
f : Ω ⊂ R2 → L
donde L = 0, 1, 2, ...n es el conjunto de etiquetas.
En nuestro proyecto trabajaremos exclusivamente con segmentaciones binarias. Una
segmentacion binaria se define como una aplicacion:
f : Ω ⊂ R2 → 0, 1
y se nota por fp ∈ 0, 1 al valor de la segmentacion en el pıxel p. Es decir,
f : Ω ⊂ R2 → 0, 1
p → fp
El conjunto de posibles segmentaciones de una imagen se denota por LΩ. Ası, en una
imagen 2 x 2 constituıda por 4 pıxeles, si a cada pıxel le asignamos una etiqueta que
puede ser 0 o 1, el numero de segmentaciones posibles sera 24 = 16. Si tenemos N pıxeles,
el numero de posibles segmentaciones sera 2N .
1.3. Energıas
Una energıa es una aplicacion
E : LΩ → R
f → E(f)
Es decir, una energıa asigna a cada posible segmentacion f un valor numerico E(f).
1.4. ¿Que tiene que ver segmentar con el concepto de energıa?
Disponer de una energıa es disponer de un modo de evaluar la calidad de las seg-
mentaciones. Para ello entendemos que una segmentacion es mejor cuanta menor energıa
asociada tiene, e idealmente la mejor segmentacion se corresponde con aquella que tiene
menor energıa asociada. Se trata pues de:
1. Encontrar una energıa adecuada para evaluar las posibles segmentaciones.
2. Una vez que tenemos una energıa E, que se acepta como buena para evaluar las
posibles segmentaciones, habrıa que encontrar la segmentacion f0 con menor energıa,
es decir, tal que
E(f0) ≤ E(f)
para cualquier otra segmentacion f .
Segmentacion de imagenes y teorıa de grafos 3
En el sentido del punto 2, podemos decir que la segmentacion de imagenes es un
problema de optimizacion de energıas.
1.5. Algunos ejemplos de energıas razonables
Vamos a desarrollar un ejemplo sencillo a partir de una imagen, formada por 4 pıxeles,
con los siguientes valores de intensidad:
0.51 0.48
1 1
Compararemos tres energıas distintas, para lo que utilizamos de soporte para nuestro
ejemplo un archivo Excel, en el que representamos:
Las 16 posibles segmentaciones.
Energıa 1. El valor de la energıa para cada segmentacion f depende exclusivamente
de la diferencia entre la intensidad Ip de cada pıxel y el valor de la etiqueta fp
asignada al mismo. Con precision,
E(f) =∑
p
Vp(fp) siendo Vp(fp) = |fp − Ip|
donde p recorre el conjunto de los pıxeles. Se penaliza en este caso que la etiqueta
sea muy distinta del nivel de gris del pıxel. En nuestro ejemplo, el valor de la energıa
para la segmentacion numero 3 es el mas bajo, ası que la tercera segmentacion serıa
la mejor.
Energıa 2. El valor de la energıa para cada segmentacion f tiene en cuenta la vecin-
dad de cada pıxel.Un sistema de vecindad a 4 es aquel en el que consideramos que
cada pıxel tiene 4 vecinos, a saber, derecha, izquierda, arriba y abajo.
E(f) =∑
p,q
Vp,q(fp, fq) siendo Vp,q(fp, fq) = | |fp − fq| − |Ip − Iq| |
donde p, q van recorriendo las posibles parejas de pıxeles vecinos, significando esto
que ambos estan uno a la derecha del otro, o uno encima del otro. En nuestro
ejemplo, el valor de la energıa para las segmentaciones 7 y 8 es el mas bajo, ası que
cualquiera de estas dos segmentaciones es optima.
4 Proyecto Fin de Carrera
Cuadro 1: Comparativa de tres energıasSegmentaciones Energıa 1 Energıa 2 Energıa 3
1 11 1 1 1,01 1,04 2,05
1 12 0 1 2,01 2,06 4,07
1 03 1 1 0,97 1,45 2,42
0 14 1 1 1,03 2 3,03
1 15 1 0 2,01 2 4,01
0 16 0 1 2,03 2,98 5,01
0 07 1 1 0,99 1,02 2,01
1 18 0 0 3,01 1,02 4,03
1 09 1 0 1,97 2,98 4,95
0 110 1 0 2,03 2,96 4,99
1 011 0 1 1,97 2,96 4,93
0 012 0 1 1,99 2 3,99
1 013 0 0 2,97 2 4,97
0 114 0 0 3,03 1,94 4,97
0 015 1 0 1,99 2,06 4,05
0 016 0 0 2,99 1,04 4,03
Segmentacion de imagenes y teorıa de grafos 5
Energıa 3. El valor de la energıa para cada segmentacion f se obtiene como suma
de las dos energıas anteriores:
E(f) =∑
p
Vp(fp) +∑
p,q
Vp,q(fp, fq)
En nuestro ejemplo, el valor de la energıa para la segmentacion 7 es el mas bajo.
Segmentacion de imagenes y teorıa de grafos 7
2. Grafos
2.1. ¿Que es un grafo?
Un grafo es un par G = (V, E) de conjuntos tal que cada elemento de E es un
subconjunto formado por dos elementos de V.
Los elementos de V son los vertices o nodos del grafo.
Los elementos de E son las aristas.
La arista p,q normalmente se denota por pq (o qp). Dos vertices p, q ∈ V son adyacentes
o vecinos en G si pq ∈ E.
1
3
2
4
56
7
Figura 2: V = 1, 2, 3, 4, 5, 6, 7 y E = 1, 2, 2, 4, 4, 5, 4, 6, 4, 7, 6, 7.
2.2. Caminos
Dado un grafo (V, E), un camino es un nuevo grafo P = (V ′, E ′) con
V ′ = x0, x1, ..., xk ⊂ V y E ′ = x0x1, x1x2, ..., xk−1xk ⊂ E,
donde los xi son todos distintos.
Se dice que los vertices x0 y xk estan unidos por el camino P , o que son los vertices
terminales de P . La longitud del camino es su numero de aristas. Un camino se nota por
sus vertices, es decir, P = x0x1...xk.
8 Proyecto Fin de Carrera
1
3
2
4
56
7
Figura 3: Camino P = 12467.
2.3. Grafos dirigidos
Un grafo dirigido es un par G = (V, E) de conjuntos tal que los elementos de E son
pares ordenados del conjunto de vertices V , es decir, E ⊂ V ×V . Intuitivamente, un grafo
dirigido es un grafo en el que se ha establecido una direccion en cada arista. En un grafo
dirigido las aristas se notan como pares ordenados, es decir, por (p,q), significando esto
que la arista esta dirigida de p a q.
1
3
2
4
56
7
Figura 4: V = 1, 2, 3, 4, 5, 6, 7 y E = (1, 2), (2, 1), (2, 4), (5, 4), (4, 6), (7, 4), (6, 7).
2.4. Capacidades
Una funcion de capacidades de un grafo G = (V, E) es una aplicacion
c : E → R+ ∪ +∞
O sea, a cada arista e ∈ E se le asigna una capacidad no negativa c(e). Una interpretacion
de esto podrıa considerar a las aristas como tuberıas, y la capacidad podrıa medir el area
de la seccion trasversal de cada tuberıa.
Segmentacion de imagenes y teorıa de grafos 9
2.5. Redes
Una red es un grafo con capacidades. Mas formalmente, es un grafo dirigido G = (V, E)
al que se le anaden dos vertices fijos s,t ∈ V y una funcion de capacidades
c : E → R+ ∪ +∞
Se nota por (G, s, t, c).
Los vertices s y t se denominan fuente y sumidero respectivamente y nos referimos
a ellos como los vertices terminales. En una red se distinguen dos tipos de aristas: las
aristas terminales y las no terminales.
Arista terminal: uno de sus vertices es un vertice terminal, s o t.
Arista no terminal: ninguno de sus vertices es terminal.
s
0
1
2
3
4
t
5
3
7
1
3
3
1
2
6
5
2
9
Figura 5: Ejemplo de una red.
Aunque grafo y red son conceptos distintos, en muchas ocasiones, cuando no hay lugar
a dudas, se habla de grafo en lugar de red.
2.6. Corte de una red
Un corte en una red (G, s, t, c) consiste en separar todos los vertices en dos subcon-
juntos, S y T, de modo que:
V = S ∪ T
S ∩ T = ∅
s ∈ S
t ∈ T
10 Proyecto Fin de Carrera
Los cortes de una red se notan indicando los dos subconjuntos S y T . Escribimos
entonces C = (S, T ).
En la Figura 6 se muestra el corte en la red anterior definido por S = s, 0, 1 y
T = t, 2, 3, 4. Para indicar el corte utilizamos una lınea discontinua que pasa por encima
de las aristas dirigidas con primer vertice en S y segundo vertice en T.
s
0
1
2
3
4
t
5
3
7
1
3
3
1
2
6
5
2
9
Figura 6: Corte en una red definido por S = s, 0, 1 y T = t, 2, 3, 4.
El numero de cortes de una red con N vertices no terminales es 2N . En el ejemplo de
la Figura 6 hay 25 = 32 posibles cortes.
2.7. Coste de un corte. Corte mınimo
Se denomina coste del corte C = (S, T ) a
|C| = c(S, T ) =∑
p∈S,q∈T
c(p, q),
es decir, es la suma de las capacidades de las aristas orientadas (p, q) donde p ∈ S y q ∈ T.
Por ejemplo, el coste del corte de la Figura 6 es
3 + 1 + 2 + 1 + 3 = 10.
En una red, hablaremos de corte mınimo para referirnos al corte con menor coste,
de entre todos los posibles cortes. Como se vera posteriormente, el corte mınimo del grafo
de la Figura 5 es el definido por S = s, 0, 1 y T = t, 2, 3, 4 representado en la Figura
6.
2.8. Flujo en una red
Un flujo en una red (G, s, t, c) es una funcion
F : E → [0, +∞)
Segmentacion de imagenes y teorıa de grafos 11
verificando las siguientes condiciones:
El flujo que pasa por cada arista e tiene que ser menor o igual que su capacidad:
F (e) ≤ c(e) para toda arista e.
Para todo vertice x, el flujo entrante coincide con el flujo saliente (vease la Figura
7):∑
y
F (y, x) =∑
z
F (x, z) para todo vertice x.
x
Figura 7: Aristas entrantes y salientes del vertice x.
Ya hemos mencionado como visualizar una red en terminos de un sistema de tuberıas,
donde la capacidad de una arista serıa el caudal maximo que soporta la tuberıa. Igualmente
pude pensarse en un entramado de autopistas, con capacidades en funcion del numero de
carriles. Podrıamos hablar ası del flujo de vehıculos, y del flujo maximo de vehıculos que
soporta el trafico en dichas autopistas.
En la Figura 8 se representa un flujo sobre el grafo anterior. En cada arista aparecen
dos valores separados por una barra a/b, que indican el flujo a y la capacidad b de la
arista correspondiente. Por supuesto, debe ser a < b.
2.9. El valor de un flujo. Flujo maximo
Se denomina valor total de un flujo F al flujo saliente de la fuente, que coincide con
el flujo entrante al sumidero:
F (s, V ) =∑
x∈V
F (s, x) =∑
x∈V
F (x, t) = F (V, t).
12 Proyecto Fin de Carrera
s
0
1
2
3
4
t
3/5
2/3
4/7
1/1
0/3
3/3
1/1
2/2
3/6
2/5
2/2
7/9
Figura 8: Flujo en una red.
El valor de un flujo F se denota por |F |. Por ejemplo, el valor del flujo representado
en la Figura 8 es nueve.
En una red, hablaremos de flujo maximo cuando el valor de este sea maximo pasa
esa red. Puede haber muchos flujos maximos, que tendran todos en comun su valor de
flujo.
En el ejemplo de red mostrado en la Figura 9, esta representado un flujo maximo. Su
valor de flujo es 10.
s
0
1
2
3
4
t
3/5
3/3
4/7
1/1
0/3
3/3
1/1
2/2
4/6
2/5
2/2
8/9
Figura 9: Flujo maximo en una red.
Al considerar la analogıa entre una red y un sistema de tuberıas, donde las capacidades
de las aristas se corresponden con el caudal maximo de fluido que puede circular por la
correspondiente tuberıa, ¿cual es la mayor cantidad de fluido que podemos transportar
desde la fuente al sumidero respetando las restricciones que marcan las capacidades? Este
es el problema consistente en encontrar el flujo maximo (max-flow). El valor de este flujo
serıa la cantidad de flujo que puede entrar por el nodo fuente y salir por el nodo sumidero.
Segmentacion de imagenes y teorıa de grafos 13
2.10. El coste del mınimo corte es el valor del flujo maximo
El Teorema de Ford y Fulkerson establece que el problema de maximo flujo en un
grafo es equivalente al problema de mınimo corte: el coste del corte mınimo coincide con
el valor del flujo maximo.
Se han desarrollado algoritmos conocidos como min-cut/max-flow de resolucion en
tiempo polinomial. Uno de ellos, debido a Boykov y Kolmogorov [3], se estudia posterior-
mente.
2.11. ¿Que es una red residual?
Si una red esta definida por (G, s, t, c), y F es un flujo en la red, se define la red
residual asociada como (GF , s, t, cF), donde:
1. GF es un grafo, denominado grafo residual, definido como GF = (V, EF ), siendo
EF = V × V.
2. cF es la capacidad residual en una arista (p, q) y se define como el maximo flujo
adicional que puede ir de p a q usando las aristas (p, q) y (q, p).
En la Figura 10 se muestra la red residual para el flujo definido en la Figura 8.
s
0
1
2
3
4
t
2
1
3
0
1
3
1
2 0
1
0
23
3
32
0
2
Figura 10: Red residual para el flujo definido en la Figura 8.
Segmentacion de imagenes y teorıa de grafos 15
3. Relacion entre Energıas y Grafos
3.1. Imagen y grafo
Una pantalla Ω esta formada por pıxeles p. La imagen I la constituyen estos pıxeles p
junto con un nivel de gris para cada pıxel Ip.
I1 I2 I3
I4 I5 I6
I7 I8 I9
A partir de la imagen I construimos un grafo G = (V, E), considerando cada pıxel de
la imagen como un nodo o vertice del grafo, y anadiendo dos vertices extra s y t, ası que
V = Ω ∪ s, t.
s
t
v1 v2 v3
v4 v5 v6
v7 v8 v9
Figura 11: Vertices del grafo asociado a una imagen formada por 9 pıxeles.
Recordar que s y t son los llamados vertices terminales. Se distinguen dos tipos de
aristas: las aristas terminales y las no terminales.
Arista terminal o t-link: uno de sus extremos es un vertice terminal s o t.
Arista no terminal o n-link: ninguno de sus extremos es un vertice terminal.
3.2. Segmentacion binaria y corte de un grafo
Las segmentaciones binarias de la imagen se corresponden exactamente con los cortes
del grafo (hay un corte por cada segmentacion y viceversa).
16 Proyecto Fin de Carrera
s
t
v1 v2 v3
v4 v5 v6
v7 v8 v9
Figura 12: Grafo asociado a una imagen. Se han omitido alguna de las aristas t-link.
Toda segmentacion binaria f , define un corte C(S, T ) en el grafo de modo que, si vi
es el vertice correspondiente al pıxel pi, tenemos
f(pi) = 1 ⇔ vi ∈ T
f(pi) = 0 ⇔ vi ∈ S
Dada una segmentacion f , el corte correspondiente se denota por Cf . Recıprocamente, si
C es un corte, la segmentacion correspondiente se denota por fC. Esquematicamente:
Segmentacion f ⇔ Corte Cf
Corte C ⇔ Segmentacion fC
Ası, por ejemplo, dada la imagen I definida anteriormente, una segmentacion de la
misma puede ser
0 0 0
0 1 0
1 1 1
que se corresponde con el corte en el grafo de la Figura 13.
El numero de posibles segmentaciones de la imagen I es 2N , siendo N el numero de
pıxeles. Este es el mismo numero de cortes posibles en el grafo.
3.3. Energıas representables por un grafo
Dadas una imagen I y una energıa E
E : 0, 1N → R,
Segmentacion de imagenes y teorıa de grafos 17
s
t
v1 v2 v3
v4 v5 v6
v7 v8 v9
Figura 13: Corte en el grafo correspondiente al ejemplo de segmentacion.
construimos una red (G, s, t, c). La funcion de capacidades debe definirse de modo que,
para cualquier segmentacion f ∈ 0, 1N , el valor de la energıa E(f) coincida con el coste
del corte correspondient Cf , salvo una constante. O sea,
E(f) = K + |Cf |.
Es decir, es lo mismo calcular la energıa de una segmentacion que calcular el coste del
corte correspondiente, salvo el valor de esta constante.
Como ejemplo, consideremos una imagen con dos pıxeles
I1 I2
y la energıa definida por la tabla
p1\p2 0 1
0 10 14
1 8 9
Veamos que esta energıa esta representada por el grafo de la Figura 14.
La tabla 2 demuestra que el grafo representa a la energıa, siendo 0 el valor de la
constante K de la definicion.
Los cuatro posibles cortes del grafo estan representados en la Figura 15.
3.4. ¿Como son las energıas que se pueden representar por grafos?
Las energıas que se utilizan en la segmentacion de imagenes son de la forma∑
p
Vp(fp) +∑
p,q
Vp,q(fp, fq).
18 Proyecto Fin de Carrera
s
t
4 5
1
2
8 2
v1 v2
Figura 14: Grafo que representa la energıa anterior.
E(f) Segmentacion Corte |C|
10 (0,0) S = s, 1, 2, T = t 10
14 (0,1) S = s, 1, T = t, 2 14
8 (1,0) S = s, 2, T = 1, t 8
9 (1,1) S = s, T = t, 1, 2 9
Cuadro 2: Energıa de una segmentacion y el coste del corte correspondiente.
s
t
4 5
1
2
8 2
v1 v2
C1
C2
C3
C4
Figura 15: Cortes en el grafo de la Figura 14.
Los terminos Vp indican la preferencia de etiqueta del pıxel p y estan basados en la
intensidad. Los terminos Vp,q indican la interaccion entre pıxeles vecinos [2], [1].
Si cada uno de los terminos de la energıa puede representarse por grafos, la energıa
vendra representada por el grafo con capacidades igual a la suma de las capacidades
parciales.
Segmentacion de imagenes y teorıa de grafos 19
3.4.1. Terminos Vp
Los terminos dependientes de un unico pıxel, Vp, son siempre representables por grafos.
Solo se tienen aristas t-link, siendo sus capacidades (Figura 19)
c(s, p) = max0, Vp(1) − Vp(0),
c(p, t) = max0, Vp(0) − Vp(1).
s
t
p
maxVp(1) − Vp(0), 0
maxVp(0) − Vp(1), 0
Figura 16: Grafo asociado al termino de la energıa Vp.
En efecto:
Si Vp(1) ≤ Vp(0),
• El coste del corte definido por los conjuntos S = s y T = t, p es 0. El
valor de la energıa para la segmentacion correspondiente a este corte (fp = 1)
es Vp(1).
• El coste del corte definido por los conjuntos S = s, p y T = t es Vp(0) −
Vp(1). El valor de la energıa para la segmentacion correspondiente a este corte
(fp = 0) es Vp(0).
Entonces, Vp(f) = K + |Cf | para toda segmentacion con K = Vp(1)).
Si Vp(1) ≥ Vp(0),
• El coste del corte definido por los conjuntos S = s y T = t, p es Vp(1) −
Vp(0) . El valor de la energıa para la segmentacion correspondiente a este corte
(fp = 1) es Vp(1).
• El coste del corte definido por los conjuntos S = s, p y T = t es 0. El
valor de la energıa para la segmentacion correspondiente a este corte (fp = 0)
es Vp(0).
20 Proyecto Fin de Carrera
Entonces, Vp(f) = K + |Cf | para toda segmentacion con K = Vp(0).
3.4.2. Terminos Vp,q
Los terminos de la energıa dependientes de dos pıxeles, Vp,q, no siempre son representa-
bles por grafos. Kolmogorov y Zabih [4] estudian las condiciones que deben cumplir estos
terminos para ser representables, demostrando que la condicion necesaria y suficiente es
que sea submodular. Esto se traduce en
V (0, 0) + V (1, 1) ≤ V (0, 1) + V (1, 0).
Una forma sencilla de comprobarlo es escribir la energıa Vp,q de la forma
Vp,q(fp, fq) = a0 + apfp + aqfq + afpfq.
Los coeficientes a0, ap, aq y a se obtienen de las ecuaciones
V (0, 0) = a0
V (0, 1) = a0 + aq
V (1, 0) = a0 + ap
V (1, 1) = a0 + ap + aq + a,
de donde se obtiene
a0 = V (0, 0)aq = V (0, 1) − V (0, 0)ap = V (1, 0) − V (0, 0)a = V (1, 1) + V (0, 0) − V (0, 1) − V (1, 0).
s
t
p q−a
−a
Figura 17: Representacion por un grafo del termino afpfq, con a ≤ 0.
Los terminos apfp y aqfq de Vp,q dependen cada uno de ellos de un solo pıxel y, como
se ha visto, se pueden representar por grafos con aristas t-link. El termino que depende
Segmentacion de imagenes y teorıa de grafos 21
de los dos pıxeles, afpfq, es representable por grafos si y solo si a ≤ 0, con capacidades
(vease la Figura 17 en la pagina anterior):
c(p, q) = −a, c(q, t) = −a.
Observar que la condicion
a = V (1, 1) + V (0, 0) − V (0, 1) − V (1, 0) ≤ 0
es equivalente a la condicion de submodularidad.
Ejemplo
Consideramos la energıa definida para una imagen con dos pıxeles vista al inicio de la
seccion:
p\q 0 1
0 10 14
1 8 9
Al ser a = −3 ≤ 0, es una funcion submodular y por lo tanto representable por grafos.
Siguiendo el procedimiento descrito, un grafo lo podemos obtener de la siguiente forma.
Se tiene:
a0 = E(0, 0) = 10,ap = E(1, 0) − E(0, 0) = −2,aq = E(0, 1) − E(0, 0) = 4,a = −3.
Luego,
E(fp, fq) = 10 − 2fp + 4fq − 3fpfq.
Al ser a = −3 ≤ 0, cada uno de los terminos se puede representar por un grafo, siendo
la suma de todos ellos un grafo que representa a la energıa E (Figura 18).
En la tabla 3 puede comprobarse esta afirmacion. La constante K de la definicion de
energıa representable por grafos es K = 5.
22 Proyecto Fin de Carrera
E(fi) Segmentacion Corte |C|
10 (0,0) S = s, 1, 2, T = t 5
14 (0,1) S = s, 1, T = t, 2 9
8 (1,0) S = s, 2, T = 1, t 3
9 (1,1) S = s, T = t, 1, 2 4
Cuadro 3: Segmentaciones de una imagen y cortes del grafo.
s
t
p
2
+
s
t
p
4
+
s
t
p q3
3
=
s
t
p1 p2
4
3
32
Figura 18: Construccion del grafo asociado a la energıa.
3.4.3. Energıas de la tabla 1
En la primera seccion comparamos tres energıas diferentes:
Segmentacion de imagenes y teorıa de grafos 23
Energıa 1: los terminos
Vp(fp) = |fp − Ip|
siempre son representables por grafos, al ser terminos que dependen de un solo pıxel.
s
t
p
Vp(1) = 1 − Ip
Vp(0) = Ip
Figura 19: Grafo asociado al termino de la energıa Vp(fp) = |fp − Ip|.
Energıa 2: los terminos
Vpq(fp, fq) = | |fp − fq| − |Ip − Iq||
no son siempre representables por grafos. La energıa esta definida por
p\q 0 1
0 |Ip − Iq| 1 − |Ip − Iq|
1 1 − |Ip − Iq| 1 − |Ip − Iq|
La condicion de submodularidad, imprescindible para que una energıa sea repre-
sentable por grafos, es:
a = V (1, 1) + V (0, 0) − V (0, 1) − V (1, 0) ≤ 0
En nuestro caso,
a = 4|Ip − Iq| − 2 ≤ 0
con lo que, para que la energıa sea representable por un grafo tiene que cumplir que
|Ip − Iq| ≤1
2,
24 Proyecto Fin de Carrera
para todo par de pıxeles vecinos p y q. Como esta condicion no se cumple siempre,
la energıa 2 no es represtable por grafos y no podemos utilizar la tecnica de mınimo
corte presentada.
Energıa 3: no es representable por grafos por no serlo la energıa 2.
Segmentacion de imagenes y teorıa de grafos 25
4. El algoritmo de Boykov/Kolmogorov
4.1. Objetivo
La segmentacion de imagenes se basa en la optimizacion de una funcion de coste o
energıa. Cuando estas energıas pueden representarse mediante grafos, cada segmentacion
de la imagen se corresponde con una particion del conjunto de vertices del grafo, siendo la
particion o corte de coste mınimo la que minimiza la energıa, y por lo tanto proporciona
la segmentacion buscada.
Los algoritmos de particion s/t de grafos, como el desarrollado por Boykoy/Kolmogorov
objeto de nuestro estudio, proporcionan una segmentacion binaria de la imagen, es decir,
la separacion objeto/fondo. Estos algoritmos buscan el corte de coste mınimo, a traves
del maximo flujo.
Vamos a tratar de explicar el algoritmo desarrollado por Yuri Boykov y Vladimir
Kolmogorov basandonos en su artıculo de referencia [3], usando como hilo conductor el
grafo de la Figura 20:
s
0
1
2
3
4
t
5
3
7
1
3
3
1
2
6
5
2
9
Figura 20: Grafo ejemplo.
4.2. Inputs
Matriz B de capacidades de las aristas t-link.
26 Proyecto Fin de Carrera
B s t
0 5
1 7
2 3
3 2
4 9
Matriz A de capacidades de las aristas n-link.
A 0 1 2 3 4
0 3 3
1 1 1 2
2 6
3 5
4
4.3. Outputs
Valor de Flujo maximo.
Corte con coste mınimo: etiquetado de cada nodo (0 o 1).
4.4. Definiciones involucradas en el algoritmo
4.4.1. Arboles S y T
Segun la terminologıa basica del algoritmo de Boykov, en un grafo, se mantienen dos
arboles no superpuestos S y T , con raıces en los nodos s y t.
En la Figura 21 el arbol S esta formado por el nodo raız s y los nodos 0, 1 y 2 y
tanto los nodos como las aristas que lo componen estan resaltados en rojo. El arbol T
esta formado por el nodo raız t y los nodos 3,4. Tanto los nodos como las aristas que lo
componen estan resaltados en color verde.
En el arbol S, el sentido de la arista va de padre a hijo. En el arbol T , el sentido de
la arista va de hijo a padre (para seguir lo marcado por el grafo).
Segmentacion de imagenes y teorıa de grafos 27
s
0
1
2
3
4
t
5
3
7
1
3
3
1
2
6
5
2
9
Figura 21: Arboles S (en rojo) y T (en verde) en el grafo.
4.4.2. Nodos libres
Todos los nodos del grafo que no estan en los arboles S y T son llamados nodos libres.
En la figura el nodo 1 es un nodo libre.
s
0
1
2
3
4
t
5
3
7
1
3
3
1
2
6
5
2
9
Figura 22: Arboles S (en rojo) y T (en verde) y nodos libres (en negro).
4.4.3. Nodos activos y pasivos
Los nodos que forman parte de un arbol pueden ser activos o pasivos. Los nodos
activos representan el borde exterior en cada arbol, son los nodos por los que el arbol
puede crecer. Los nodos pasivos representan la cara interna, por ellos el arbol no puede
crecer.
De ahora en adelante si los nodos de un arbol son activos estan representados por un
cırculo de puntos del color del arbol al que pertenecen.
En la Figura 23, el arbol S esta formado por los vertices s, 0, 1, 2, en el que el nodo
1 es un nodo activo, mientras que los nodos s, 0 y 2 son nodos pasivos. En el arbol T , los
nodos 3 y 4 son activos.
28 Proyecto Fin de Carrera
s
0
1
2
3
4
t
5
3
7
1
3
3
1
2
6
5
2
9
Figura 23: Nodos activos y pasivos.
4.4.4. Etapas del algoritmo
El algoritmo iterativamente repite las siguientes tres etapas:
Etapa de Crecimiento: Se realizan las siguientes acciones:
Los arboles S y T se expanden. Los nodos activos exploran nodos vecinos a traves
de aristas de capacidad positiva con el objetivo de anadirlos a los arboles S o T .
Solamente se anaden cuando los nodos explorados son nodos libres, pasando a con-
vertirse en nodos activos cuando se incorporan al arbol S o T . Cuando todos los
nodos vecinos de un nodo activo son explorados, dicho nodo activo se convierte en
pasivo.
La etapa de crecimiento termina cuando, en nuestra exploracion de nodos veci-
nos, encontramos un arco cuyo nodo origen pertenece al arbol S y el nodo destino
pertenece al arbol T , formando un camino de s a t.
Etapa de Camino: se parte del camino encontrado en la etapa de crecimiento ante-
rior. En esta etapa pasamos la mayor cantidad de flujo a traves del camino encontrado.
Algunas aristas pueden llegar a estar saturadas, por lo que algunos nodos pueden llegar
a estar huerfanos, dando lugar a la ultima fase de nuestro algoritmo y que comentamos a
continuacion, la adopcion.
Etapa de Adopcion: se intenta encontrar otro padre valido para cada huerfano
dentro de los arboles originales de busqueda S o T al que pertenecıa el nodo antes de
quedarse huerfano. Los nuevos padres deben pertenecer a los mismos arboles de busqueda
S o T del huerfano. Ası mismo el padre debe estar conectado a traves de un arco no
saturado. Si no es posible encontrar un nuevo padre, se declara nodo libre. Se declaran
todos los nodos hijos como libres. La etapa termina cuando no quedan huerfanos, y por
tanto, las estructuras de los arboles S y T se restauran.
Segmentacion de imagenes y teorıa de grafos 29
Despues de completar la etapa de adopcion el algoritmo vuelve a la etapa de crecimiento,
y repite estas etapas iterativamente.
4.4.5. Final del algoritmo
El algorimo termina cuando los arboles S y T no pueden crecer mas, es decir, no tienen
nodos activos. Los arboles estan separados por aristas saturadas.
Esto conlleva que se alcanza el flujo maximo. El correspondiente mınimo corte lo
definen los nodos de los arboles S y T . Si quedan nodos libres, es decir, si algun vertice
del grafo no esta en alguno de los arboles, el coste mınimo se alcanza para mas de un
corte. En este caso el algoritmo asocia la etiqueta 0 a todos los nodos libres.
4.5. Orden de recorrido de nodos y arcos
Tomando como punto de partida las matrices A y B definidas anteriormente vamos a
aclarar en que orden se van a recorrer los nodos, y estando en cada nodo en que orden se
recorren los arcos que tienen como origen dicho nodo.
4.5.1. Orden de recorrido de los nodos
1. Todos los nodos activos pertenecientes al arbol S: se recorren los nodos activos
pertenecientes al arbol S segun el orden determinado por la matriz B.
2. Todos los nodos activos pertenecientes al arbol T : se recorren los nodos activos
pertenecientes al arbol T segun el orden determinado por la matriz B.
4.5.2. Orden de recorrido de los arcos
Para cada nodo activo se recorren todos los arcos cuyo origen sea dicho nodo en el
orden determinado de la siguiente forma. Tomamos como base la matriz A. Para cada
columna de dicha matriz, si existen elementos de dicha columna con valor distinto de 0, se
forma el arco de origen el ındice de la fila del correspondiente elemento y como destino el
ındice de la columna que estamos recorriendo. Ası por ejemplo, en la matriz A de nuestro
ejemplo, si recorremos la columna 1, tenemos como elemento distinto de cero la capacidad
3 correspondiente al arco a01. Una vez recorridas todas las columnas de esta matriz A se
recuperan los arcos siguiendo el metodo LIFO (ultimo en entrar, primero en salir).
30 Proyecto Fin de Carrera
4.6. Proceso del algoritmo
El ejemplo que explicamos es el reflejado en la imagen 20:
1. Situacion Inicial:
Arboles S = s, T = t
Nodos libres 0, 1, 2, 3, 4.
Nodos activos en S: s, nodos activos en T : t
Nodos pasivos en S: , nodos pasivos en T :
2. Etapa de crecimiento: se recorre el arbol S. Como el nodo s es activo, el arbol S
crece por el nodo s anadiendo los nodos 0,1 y 2 que pasan a ser activos e hijos de s.
El nodo s pasa a ser pasivo.
Se recorre el arbol T . Como el nodo t es activo, el arbol T crece por el nodo t
anadiendo los nodos 3 y 4 que pasan a ser activos e hijos de t. El nodo t pasa a ser
pasivo. Se tiene la siguiente situacion, que queda reflejada en la Figura 24.
Arboles S = s, 0, 1, 2, T = t, 3, 4
Nodos libres .
Nodos activos en S: 0, 1, 2, nodos activos en T : 3, 4
Nodos pasivos en S: s, nodos pasivos en T : t
ARBOL NODO PADRE TIPO TR_CAP ARCO R_CAP
S 0 TERMINAL ACTIVO 5 a03 3
a01 3
S 1 TERMINAL ACTIVO 7 a14 2
a13 1
a12 1
S 2 TERMINAL ACTIVO 3 a24 6
T 3 TERMINAL ACTIVO -2 a34 5
T 4 TERMINAL ACTIVO -9 -
3. Etapa de crecimiento: se empieza a recorrer el arbol S por el nodo 0. A traves
del arco a03 (con capacidad positiva de valor 3) llegamos al nodo 3. Como el nodo
3 pertenece al arbol T hemos encontrado un camino. Este camino queda definido
yendo de padre a hijo por el arbol S, desde el nodo terminal s hasta el nodo 0, y
de hijo a padre por el arbol T , desde el nodo 3 hasta el nodo terminal t. Es decir,
el camino encontrado que une los arboles de busqueda es:
s5
−→ 03
−→ 32
−→ t
Segmentacion de imagenes y teorıa de grafos 31
s
0
1
2
3
4
t
5
3
7
1
3
3
1
2
6
5
2
9
Figura 24: Etapa crecimiento.
En la Figura 25 se muestra la situacion actual de los arboles en el grafo y el camino
de s a t encontrado.
s
0
1
2
3
4
t
5
3
7
1
3
3
1
2
6
5
2
9
Figura 25: Camino s5
−→ 03
−→ 32
−→ t.
4. Etapa camino: el flujo maximo que es posible pasar de S a T a traves de este
camino tiene el valor 2. Se disminuye 2 del valor de las capacidades iniciales y se
crea el grafo residual, que serıa el mostrado en la imagen 26.
s
0
1
2
3
4
t
3
3
7
1
3
1
2 1
2
6
5
0
9
Figura 26: Grafo Residual (etapa 4).
5. Etapa adopcion: despues de la etapa camino la capacidad de la arista que une
el nodo raız t con el nodo 3 es 0. Esto quiere decir que no es posible pasar flujo
32 Proyecto Fin de Carrera
desde el nodo raız t al nodo 3 a traves de la arista inicial que los unıa. El nodo 3
es huerfano, dando paso a la fase de adopcion. En esta fase de adopcion se intenta
encontrar un nuevo padre para el nodo 3 dentro del mismo arbol de busqueda T , y
en nuestro ejemplo el nuevo padre es el nodo 4.
La situacion de los nodos y arcos despues de la fase adopcion es la siguiente:
Arboles S = s, 0, 1, 2, T = t, 3, 4
Nodos libres .
Nodos activos en S: 0, 1, 2, nodos activos en T : 3, 4
Nodos pasivos en S: s, nodos pasivos en T : t
ARBOL NODO PADRE TIPO TR_CAP ARCO R_CAP
S 0 TERMINAL ACTIVO 3 a03 1
a01 3
S 1 TERMINAL ACTIVO 7 a14 2
a13 1
a12 1
S 2 TERMINAL ACTIVO 3 a24 6
3 4 ACTIVO 0 a34 5
a30 2
T 4 TERMINAL ACTIVO -9 -
El arbol T mantiene los mismos nodos que en el paso anterior, pero el padre del
nodo 3 ahora es 4, no t como antes. En la Figura 27 se muestra la situacion actual
del grafo.
s
0
1
2
3
4
t
3
3
7
1
3
1
2 1
2
6
5
0
9
Figura 27: Etapa adopcion (etapa 5).
6. Etapa crecimiento: se continua recorriendo el arbol S por el nodo 0. Se comienza
de nuevo el recorrido a traves del arco a03 (con capacidad positiva de valor 1) y
llegamos al nodo 3. Como el nodo 3 pertenece al arbol T hemos encontrado de
nuevo un camino. Este camino queda definido yendo de padre a hijo por el arbol S,
desde el nodo terminal s hasta el nodo 0, y de hijo a padre por el arbol T , desde el
Segmentacion de imagenes y teorıa de grafos 33
nodo 3 hasta el nodo terminal t. Es decir, el camino encontrado que une los arboles
de busqueda es:
s3
−→ 01
−→ 35
−→ 49
−→ t
7. Etapa camino: el flujo maximo que es posible pasar de S a T tiene el valor 1.
Se disminuye 1 del valor de las capacidades iniciales y se obtiene el grafo residual
mostrado en la Figura 28. El valor del flujo total es 3.
No quedan nodos huerfanos, por lo que no hay etapa de adopcion.
s
0
1
2
3
4
t
2
3
7
1
3
0
3 1
2
6
41
0
8
Figura 28: Grafo residual (etapa 7).
La situacion de los nodos y arcos es la siguiente:
Arboles S = s, 0, 1, 2, T = t, 3, 4
Nodos libres .
Nodos activos en S: 0, 1, 2, nodos activos en T : 3, 4
Nodos pasivos en S: s, nodos pasivos en T : s
ARBOL NODO PADRE TIPO TR_CAP ARCO R_CAP
S 0 TERMINAL PASIVO 2 a03 0
a01 3
S 1 TERMINAL ACTIVO 7 a14 2
a13 1
a12 1
S 2 TERMINAL ACTIVO 3 a24 6
3 4 ACTIVO 0 a34 4
a30 3
T 4 TERMINAL ACTIVO -8 a43 1
T
8. Etapa crecimiento: se sigue recorriendo el arbol S por el nodo 0. Se empieza de
nuevo por el arco a03. Como la capacidad del arco a03 es 0 no tiene lugar ninguna
accion.
34 Proyecto Fin de Carrera
9. Etapa crecimiento: se continua el recorrido por los arcos con origen el nodo 0. En
este caso se recorre el arco a01. Como el nodo 1 pertenece al arbol S no tiene lugar
ninguna accion. El nodo 0 pasa a pasivo.
10. Etapa crecimiento: se sigue recorriendo el arbol S por el nodo 1. A traves del
arco a14 (con capacidad positiva de valor 2) llegamos al nodo 4. Como el nodo 4
pertenece al arbol T hemos encontrado un camino como en casos anteriores que une
los arboles de busqueda S y T y es:
s7
−→ 12
−→ 48
−→ t
11. Etapa camino: el flujo maximo que es posible pasar de S a T tiene el valor 2. Se
disminuye 2 del valor de las capacidades iniciales y se obtiene el grafo residual de la
Figura 29. El valor total del flujo es 5.
s
0
1
2
3
4
t
2
3
5
1
3
0
3 1
0
26
41
0
6
Figura 29: Grafo residual (etapa 11).
No quedan nodos huerfanos por lo que no hay etapa de adopcion. La situacion de
los nodos y arcos es la siguiente:
Arboles S = s, 0, 1, 2, T = t, 3, 4
Nodos libres .
Nodos activos en S: 1, 2, nodos activos en T : 3, 4
Nodos pasivos en S: 0, nodos pasivos en T :
Segmentacion de imagenes y teorıa de grafos 35
ARBOL NODO PADRE TIPO TR_CAP ARCO R_CAP
S 0 TERMINAL PASIVO 2 a03 0
a01 3
S 1 TERMINAL ACTIVO 5 a14 0
a13 1
a12 1
S 2 TERMINAL ACTIVO 3 a24 6
T 3 4 ACTIVO 0 a34 4
a30 3
T 4 TERMINAL ACTIVO -6 a43 1
a41 2
12. Etapa crecimiento: se continua recorriendo el grafo por el nodo 1 a traves del
arco a14. Como la capacidad es 0 no hace nada.
13. Etapa crecimiento: se continua recorriendo el grafo por el nodo 1 a traves del
arco a13 (con capacidad positiva de valor 1) y llegamos al nodo 3. Como el nodo 3
pertenece al arbol T hemos encontrado de nuevo un camino que une los arboles de
busqueda S y T . Es
s5
−→ 11
−→ 34
−→ 46
−→ t
14. Etapa camino: El flujo maximo que es posible pasar de S a T tiene el valor 1. Se
disminuye 1 del valor de las capacidades iniciales y se obtiene el grafo residual de la
Figura 30. El valor del flujo total es 6.
s
0
1
2
3
4
t
2
3
4
1
3
0
3 0
1
0
26
32
0
5
Figura 30: Grafo residual (etapa 14).
No quedan huerfanos, por lo que no hay etapa de adopcion y se pasa a la etapa de
crecimiento. La situacion de los nodos y arcos es la siguiente.
Arboles S = s, 0, 1, 2, T = t, 3, 4
Nodos libres .
Nodos activos en S: 1, 2, nodos activos en T : 3, 4
Nodos pasivos en S: s, 0, nodos pasivos en T : t
36 Proyecto Fin de Carrera
ARBOL NODO PADRE TIPO TR_CAP ARCO R_CAP
S 0 TERMINAL PASIVO 2 a03 0
a01 3
S 1 TERMINAL ACTIVO 4 a14 0
a13 0
a12 1
S 2 TERMINAL ACTIVO 3 a24 6
T 3 4 ACTIVO 0 a34 3
a30 3
a31 1
T 4 TERMINAL ACTIVO -5 a43 2
a41 2
15. Etapa crecimiento: se ha terminado de recorrer el nodo 1 y pasa a ser pasivo. Se
continua recorriendo el arbol S por el nodo 2 a traves del arco a24 (con capacidad
positiva de valor 6) y llegamos al nodo 4. Como el nodo 4 pertenece al arbol T
hemos encontrado de nuevo un camino que une los arboles de busqueda S y T . Es
s3
−→ 26
−→ 45
−→ t
16. Etapa camino: el flujo maximo que es posible pasar de S a T tiene el valor 3. Se
disminuye 3 del valor de las capacidades iniciales y se obtiene el grafo residual de la
Figura 31. El flujo total es 9.
s
0
1
2
3
4
t
2
0
4
1
3
0
3 0
1
0
23
3
32
0
2
Figura 31: Grafo residual (etapa 16)
17. Etapa adopcion: El nodo 2 es huerfano y se intenta encontrar un nuevo padre para
el nodo 2 dentro del arbol de busqueda S. El nuevo padre es el nodo 1. La situacion
de los nodos y arcos despues de la fase de adopcion es la siguiente y se muestra en
la Figura 32:
Arboles S = s, 0, 1, 2, T = t, 3, 4
Nodos libres .
Segmentacion de imagenes y teorıa de grafos 37
Nodos activos en S: 2, nodos activos en T : 3, 4
Nodos pasivos en S: s, 0, 1, nodos pasivos en T : t
ARBOL NODO PADRE TIPO TR_CAP ARCO R_CAP
S 0 TERMINAL PASIVO 2 a03 0
a01 3
S 1 TERMINAL PASIVO 4 a14 0
a13 0
a12 1
S 2 1 ACTIVO 0 a24 3
T 3 4 ACTIVO 0 a34 3
a30 3
a31 1
T 4 TERMINAL ACTIVO -2 a43 2
a41 2
a42 3
s
0
1
2
3
4
t
2
0
4
1
3
0
3 0
1
0
23
3
32
0
2
Figura 32: Grafo residual y arboles S y T (etapa 17)
18. Etapa crecimiento: se continua recorriendo el arbol S por el nodo 2 a traves del
arco a24 (con capacidad positiva de valor 6) y llegamos al nodo 4. Como el nodo 4
pertenece al arbol T hemos encontrado de nuevo un camino que une los arboles de
busqueda S y T . Es
s4
−→ 11
−→ 23
−→ 42
−→ t
19. Etapa camino: El flujo maximo que es posible pasar de S a T tiene el valor 1. Se
disminuye 1 del valor de las capacidades iniciales y se obtiene el grafo residual de la
Figura 33. El valor del flujo total es 10.
20. Etapa adopcion: El nodo 2 es huerfano y se intenta encontrar un nuevo padre
para el nodo 2 dentro del arbol de busqueda S. No se encuentra padre para el nodo
2 con lo que se convierte en nodo libre. (Figura 34)
38 Proyecto Fin de Carrera
s
0
1
2
3
4
t
2
0
3
0
1
3
0
3 0
1
0
22
4
32
0
1
Figura 33: Grafo residual (etapa 19).
s
0
1
2
3
4
t
2
0
3
0
1
3
0
3 0
1
0
22
4
32
0
1
Figura 34: Grafo residual (etapa 20).
21. Etapa crecimiento: se ha terminado de recorrer el arbol S. Se empieza a recorrer
el arbol T desde el nodo 3, comenzando por el arco a34. Llega al nodo 4, pertenece
a T y no hace nada.
22. Etapa crecimiento: se continua recorriendo desde el nodo 3 por el arco a30. Tiene
capacidad 0 con lo que no hace nada. El nodo 3 pasa a pasivo.
23. Etapa crecimiento: se recorre el arbol T desde el nodo 4, comenzando por el arco
a43. Llega al nodo 3, pertenece a T con lo que no hace nada.
24. Etapa crecimiento: se continua recorriendo el arbol T desde el nodo 4, comenzando
por el arco a42. Llega al nodo 2, que como es un nodo libre pasa al arbol T , como
nodo activo.
25. Etapa crecimiento: se ha terminado de recorrer el nodo 4, por lo que pasa a ser
pasivo. A partir del nodo 2 no puede crecer mas el arbol T , por lo que pasa a ser
nodo pasivo.
26. El algoritmo termina al no quedar nodos activos. La situacion final puede verse en
la Figura 35.
Segmentacion de imagenes y teorıa de grafos 39
s
0
1
2
3
4
t
2
0
3
0
1
3
0
3 0
1
0
22
4
32
0
1
Figura 35: Grafo residual y situacion final.
4.6.1. Resultado del algoritmo
Los arboles S y T dan el corte mınimo
Arboles S = s, 0, 1, T = t, 2, 3, 4
Nodos libres .
Nodos activos en S: , nodos activos en T :
Corte mınimo:
• nodos en S (etiqueta 0): vertices 0, 1
• nodos en T (etiqueta 1): vertices 2, 3, 4
El flujo maximo tiene un valor de 10, que es el coste del corte mınimo que se muestra
en la Figura 36.
s
0
1
2
3
4
t
5
3
7
1
3
3
1
2
6
5
2
9
Figura 36: Corte mınimo en el grafo con coste 10.
Segmentacion de imagenes y teorıa de grafos 41
5. Aplicacion: segmentacion de imagenes
En esta seccion comprobamos experimentalmente el algoritmo min-cut/max-flow es-
tudiado, aplicandolo a la segmentacion de imagenes.
El primer paso es, dada la imagen a segmentar, definir una energıa apropiada, es
decir, una energıa para la que la buena segmentacion de la imagen tenga valor mınimo.
Para poder utilizar las tecnicas de corte de grafos y el algoritmo presentado, esta energıa
debe de ser representable por grafos, y por lo tanto submodular. A continuacion, debe
encontrarse un grafo que represente la energıa. Este grafo queda definido por las matrices
de capacidades de las aristas t-link y de las aristas n−link. La salida del algoritmo nos da
la segmentacion de la imagen.
Utilizamos energıas que son suma de terminos dependientes de un pıxel y de terminos
dependientes de dos pıxeles y estan representadas como
E(f) =∑
p
Vp(fp) +∑
p,q
Vp,q(fp, fq).
Los terminos dependientes de un pıxel, basados en la intensidad del pıxel, miden lo que
se desvıa esta intensidad de las intensidades media del fondo y del objeto. Los segundos
terminos penalizan las discontinuidades entre pıxeles vecinos.
Utilizaremos las energıas propuestas en [2].
5.1. Terminos dependientes de una variable
El termino Vp mide como la etiqueta asignada al pıxel p se aproxima a la intensidad
observada Ip. Se puede medir estimando la probabilidad de que el pıxel p, con intensi-
dad dada Ip se etiquete como 0 (objeto) o 1 (fondo), P (Ip|0) y P (Ip|1) respectivamente.
Conocidas estas probabilidades, se consideran los terminos de la energıa:
Vp(fp) = − ln(P (Ip|fp)) con fp ∈ 0, 1.
Para estimar estas probabilidades, Boykov et al. [2] y [1] proponen marcar manual-
mente unas semillas en la imagen a segmentar. Estas semillas se corresponden con dos
subconjuntos O y B de pıxeles que son parte del objeto y del fondo respectivamente.
Se usan las intensidades de los pıxeles de estas semillas para obtener histogramas para
el objeto y para el fondo de la imagen, que permiten obtener P (Ip|0) y P (Ip|1).
Estas probabilidades pueden estimarse automaticamente, utilizando tecnicas que per-
miten obtener los histogramas del objeto y del fondo de la imagen.
42 Proyecto Fin de Carrera
5.2. Terminos dependientes de dos variables
Normalmente se trabaja con vecindad a cuatro o a ocho, es decir, cada pıxel interac-
ciona con los cuatro pıxeles mas proximos a el (arriba, abajo, izquierda y derecha) o con
ocho (los cuatro anteriores y los cuatro en diagonal).
Los terminos dependientes de dos variables son terminos de regularizacion de la ima-
gen, que penalizan las discontinuidades entre pıxeles vecinos. Utilizamos la denominada
energıa de Potts, que viene definida por:
Vpq(fp, fq) = Bpqδfp 6=fq=
Bpq si fp 6= fq
0 si fp = fq,
siendo
Bpq ∝ exp
(
−|Ip − Iq|2
2σ2
)
,
donde σ es un parametro que debe estimarse. Cuando las intensidades de los pıxeles son
muy diferentes, o sea |Ip − Iq| > σ, el valor de Bpq es pequeno. Sin embargo, cuando las
intensidades son similares, o sea |Ip−Iq| < σ, entonces el valor de Bpq es muy grande. Esto
coincide con lo que queremos: si dos pıxeles vecinos tienen intensidades muy distintas, uno
es objeto y otro es fondo, y por lo tanto la energıa debe ser pequena.
Mencionar finalmente que las energıas de Potts son siempre representables por grafos.
5.3. Ejemplo practico
Para ver una aplicacion practica de segmentacion de imagenes interactiva, usando el
algoritmo de maximo flujo tal y como esta descrito en el artıculo [2], presentamos un
ejemplo sencillo en el que partimos de una imagen de unas monedas (vease la Figura 37).
Esta imagen se encuentra en los directorios predeterminados de MATLAB. Para la
implementacion del algoritmo de Boykov hemos usado la librerıa desarrollada en C++ que
el mismo proporciona en el siguiente enlace: http://pub.ist.ac.at/ vnk/software.html. Esta
librerıa devuelve el maximo flujo y el etiquetado que corresponde a cada pıxel de la imagen.
Se implementa en el proyecto de MATLAB copiando toda la estructura de directorios de
la misma en el directorio principal de nuestro proyecto MATLAB, y podemos acceder a
ella desde MATLAB a traves de la ejecucion del siguiente codigo:
mex -g maxflowmex.cpp maxflow-v3.01/graph.cpp maxflow-v3.01/maxflow.cpp
Segmentacion de imagenes y teorıa de grafos 43
Figura 37: Imagen a segmentar.
La ejecucion de este codigo genera un fichero llamado maxflowmex.cpp que, de
forma informal, digamos que es el enlace entre el codigo MATLAB y el codigo C++ de
la librerıa.
La generacion de este fichero maxflowmex.cpp nos ha sido de vital importancia para
el desarrollo del ejemplo del algoritmo mostrado en este proyecto, ya que nos ha abierto la
posibilidad de explorar el codigo fuente de la librerıa C ++ usando la ejecucion en modo
DEBUG desde MATLAB.
Seleccionamos manualmente un conjunto de pıxeles O de la imagen, que con seguridad
se encuentran en el objeto. Hacemos lo mismo para el fondo, seleccionando un conjunto B.
A estos pıxeles se les llama semillas [2]. Como resultado obtenemos la segmentacion de la
Figura 38.
44 Proyecto Fin de Carrera
Figura 38: Imagen segmentada.
Segmentacion de imagenes y teorıa de grafos 45
6. Conclusiones
Los objetivos de este proyecto han sido dos. Por un lado, estudiar la relacion entre
la segmentacion de una imagen y la obtencion del mınimo corte en una red. Por otro,
estudiar el algoritmo de min-cut/max-flow presentado por Boykov y Kolmogorov.
Se han presentado los distintos conceptos relativos a la segmentacion de una imagen
por minimizacion de una energıa, ası como los conceptos necesarios sobre grafos. Partiendo
de una energıa adecuada, que hemos supuesto dada, se ha relacionado segmentacion de
la imagen con corte de un grafo. Ası, el mınimo de la energıa, que nos proporciona la
segmentacion buscada, se corresponde con el coste de mınimo corte en el grafo, siempre
que la energıa sea submodular. Encontrar el corte de coste mınimo equivale a encontrar
el flujo de valor maximo, que puede ser calculado, en tiempo polinomial, mediante el
algoritmo min-cut/max-flow estudiado.
Para el desarrollo del ejemplo del algoritmo mostrado en este proyecto ha sido de
mucha importancia MATLAB y la generacion del fichero llamado maxflowmex.cpp, ya
que ha sido el enlace entre el codigo fuente de MATLAB y el codigo fuente C++ de la
propia librerıa, pudiendo seguir (con la ejecucion en modo DEBUG) las diferentes etapas
del algoritmo y los resultados arrojados por el mismo para el ejemplo propuesto.
Segmentacion de imagenes y teorıa de grafos 47
Referencias
[1] Boykov, Y. y Funka-Lea, G.: Graph Cuts and Efficient N-D Image Segmentation.
International Journal of Computer Vision 70(2),pp.109-131 2006.
[2] Boykov, Y. y Jolly, M-P.: Interactive Graph Cuts for Optimal Boundary & Region
Segmentation of Objects in N-D Images. International Conference on Computer Vi-
sion, vol. I, pp.105-112, 2001.
[3] Boykov, Y. y Kolmogorov, V.: An Experimental Comparison of Min-Cut/Max-Flow
Algorithms for Energy Minimization in Computer Vision IEEE. Transactions on
Pattern Analysis and Machine Intelligence. September 2004.
[4] Kolmogorov, V. y Boykov, Y.: What metrics can be approximated by geo-cuts, or
global optimization of length/area and flux. In: Computer Vision, 2005. ICCV 2005.
Tenth IEEE International Conference on. Volume 1., IEEE (2005), pp. 564-571.