PDF de programación - Segmentación de imágenes a color basada en el algoritmo de GRABCUT

SEGMENTACIÓN
DE IMÁGENES A
COLOR BASADA EN
EL ALGORITMO DE
GRABCUT

Esmitt Ramírez J.

email: [email protected]

Escuela de Computación, Centro de Computación Gráfica,

Universidad Central de Venezuela,

Caracas, Venezuela 1020-A

David Martínez R.

email: [email protected]

Escuela de Computación, Centro de Computación Gráfica,

Universidad Central de Venezuela,

Caracas, Venezuela 1020-A

Rhadamés Carmona S.

email: [email protected]

Escuela de Computación, Centro de Computación Gráfica,

Universidad Central de Venezuela,

Caracas, Venezuela 1020-A

Fecha de Recepción: 13 de septiembre de 2011

Fecha de Aceptación: 15 de abril de 2012

RESUMEN


La segmentación de imágenes es un campo de in-
vestigación relevante en el procesamiento de imágenes.
Muchos algoritmos avanzados han sido desarrollados
para separar en una imagen a color, una región de interés
de su fondo (snakes, live-wire, entre otros). Sin embargo,
los resultados obtenidos no son satisfactorios en muchos
casos. Métodos más precisos se basan en representar
la imagen como un grafo y separarla en dos sub-grafos
que representen la región de interés (foreground) y el
fondo (background). El algoritmo GrabCut pertenece
a esta categoría. En este trabajo presentamos los fun-
damentos teóricos y la implementación detallada del
algoritmo Grabcut con algunas mejoras no presentadas
en su versión original. Particularmente, los cálculos del
N-Link, T-Link y corte mínimo fueron modificados. Estos
cambios permiten obtener mejores resultados en los
píxeles de la frontera entre el foreground y background,
así como acelerar el algoritmo de corte mínimo. Nuestra
implementación muestra buenos resultados para las
imágenes de prueba utilizadas.

Palabras Clave: segmentación de imágenes, grabcut,
flujo máximo, corte mínimo, modelos mixtos gaussianos

21

revista de ingeniería COLOR IMAGES
SEGMENTATION BASED
ALGORITHM GRABCUT

ABSTRACT

Image segmentation is a relevant research field in
image processing. Many advanced algorithms have
been developed to separate an interest region of its
background on color images (snakes, live-wire and
others). However, the obtained results are not satisfactory
in many cases. More accurate approaches are based
on representing the image as a graph and separate
it into two sub-graphs representing foreground and
background. The GrabCut algorithm falls in this category.
In this paper we present the theoretical background and
a detailed implementation of the GrabCut algorithm with
some improvements not presented in the original version.
Particularly the N-Link, T-Link and min-cut calculations
were modified. These changes improve the results on
foreground and background edge pixels and also speed
up the min-cut algorithm. Our implementation shows
good results for the test images used.

Keywords: image segmentation, grabcut, max-flow,

min-cut, gaussian mixture models

22

Esmitt Ramírez J. - David Martínez R. - Rhadamés Carmona S.tekhné 15 1. INTRODUCCIÓN

El tratamiento y utilización de imágenes digitales en
el campo de la fotografía ha evolucionado de manera
acelerada. La transición de cámaras analógicas a cá-
maras digitales ha permitido que las fotografías puedan
ser representadas y tratadas en un formato digital de
manera sencilla y eficiente. Esto ha permitido que las
imágenes digitales sean utilizadas para un gran número
de aplicaciones, creando un interés en el público en
general que desea integrar más las tecnologías en sus
tareas cotidianas.

En los últimos años, la utilización de técnicas de
segmentación ha sido un área de amplio estudio por
la comunidad científica. La segmentación consiste en
identificar y extraer zonas de interés dentro de una ima-
gen. Existen diversas herramientas de segmentación que
pueden resultar muy útiles para diversas aplicaciones,
e.g. detección de vehículos en cámaras de seguridad,
extracción de objetos en fotografías para efectos es-
peciales en cine y televisión, etc. Sin embargo, la seg-
mentación de imágenes no es un problema sencillo ya
que las técnicas pueden funcionar muy bien para una
aplicación específica, y no dar los resultados más ade-
cuados para otra. Una alternativa a dicho problema es
realizar la segmentación de forma manual, la cual resulta
lenta, tediosa y susceptible al error humano.

Actualmente existen diversas técnicas totalmente
automáticas, pero en ciertos casos no dan resultados
muy precisos. Por otro lado, las técnicas semiautomá-
ticas utilizan sólo una pequeña interacción del usuario
y el resto del trabajo es realizado por el computador.
Recientemente, se han desarrollado diversas técnicas
semiautomáticas como la técnica de Tijeras Inteligentes
[1] y GraphCut [2], las cuales convierten el problema de
segmentación de imágenes en un problema de grafos.
En esta categoría, Rother et al. [3] introducen el algoritmo
de GrabCut, el cual sólo requiere una pequeña interac-
ción del usuario ofreciendo resultados de alta calidad en
un tiempo aceptable.

En este trabajo se presenta una implementación
eficiente y un estudio detallado de la técnica GrabCut
mostrando los resultados de su aplicación. También, se
introducen cambios al trabajo original presentado por
Rother et al. [3], particularmente en el cálculo de los N-
Link, T-Link y el algoritmo de corte mínimo en un grafo.
El objetivo de este trabajo es obtener un cálculo rápido y
una mejor separación de la región de interés (foreground)
del fondo (background). La motivación de esta investi-
gación radicó principalmente en segmentar fotografías

de productos industriales, ya que es una tarea común
en empresas privadas para mercadear sus productos.
El documento está organizado de la siguiente ma-
nera: la Sección 2 describe los trabajos previos en la
segmentación de imágenes de color. Luego, la Sección
3 describe la técnica de GrabCut implementada en este
trabajo junto a diversos conceptos teóricos. La Sección
4 explica los detalles de la implementación de nuestra
solución. Los experimentos y resultados son mostrados
en la Sección 5. Finalmente, conclusiones y trabajos
futuros se muestran en la Sección 6.

2. TRABAJOS PREVIOS

La segmentación de imágenes busca separar o
agrupar una imagen en diferentes partes o secciones.
La forma más simple de segmentación es la técnica ba-
sada en umbral (thresholding) [5]. Un umbral es un valor
definido donde para cada píxel de la imagen, se realiza
una comparación. Si el píxel se encuentra por debajo del
umbral entonces el píxel es marcado como background;
de lo contrario es marcado como foreground. La técni-
ca de thresholding es muy básica y funciona bien para
segmentaciones simples.

Muchos paquetes gráficos proveen mecanismos de
segmentación basado en un umbral. Un ejemplo de ellos
es la herramienta varita mágica (magic wand), incluida
en Photoshop [6], que permite seleccionar uno o varios
píxeles semillas y asignar un nivel de tolerancia. Así, la
segmentación se efectúa al comparar todos los píxeles
con el nivel de tolerancia. El uso de esta herramienta
resulta sencillo para el usuario.

Sin embargo, en algunas oportunidades se requiere
de técnicas más avanzadas que permitan realizar una
segmentación más precisa. Entre estas técnicas, se
encuentra la denominada Lazo Magnético o Live-Wire,
la cual emplea programación dinámica para resolver un
problema de búsqueda en un grafo 2D para encontrar
los bordes de una región. En dicha técnica, los píxeles de
la imagen son representados como nodos de un grafo,
y existen arcos ponderados que son definidos en base
a una función de costo. El objetivo es obtener el camino
de costo mínimo entre un nodo inicial y un nodo final.

Mortensen y Barrett [1] desarrollaron un enfoque ba-
sado en Live-Wire creando una herramienta interactiva
denominada Tijeras Inteligentes (Intelligent Scissors).
Cuando un usuario mueve el ratón cerca del borde en
una imagen, el lazo se ajusta automáticamente a éste.
El algoritmo selecciona de forma óptima el borde más

23

Segmentación de imágenes a color basada en el algoritmo de GRABCUTrevista de ingeniería cercano. Posteriormente, Mortensen y Barrett desarrollan
una versión mejorada de las Tijeras Inteligentes, ver [7].
Otra de las técnicas avanzadas para la segmentación
es la basada en minimización de energía. La técnica más
conocida de esta clasificación es el snake. Un snake es un
spline que minimiza energía guiado por condiciones de
fuerzas externas internas e influenciadas por la fuerza de
los bordes de la imagen, quien la mueve hacia las líneas y
bordes. La implementación clásica de snake fue propuesta
por Kass et al. [8], los cuales reducen el problema a una
forma matricial. Este trabajo dio pie al inicio de diversos
algoritmos basados en funciones de energía.

El uso de grafos para resolver problemas de minimiza-
ción de energía tomó relevancia gracias al trabajo de Boykov
y Kolmogorov [9]. Diversos problemas eran reformulados
para ser resueltos como un problema de minimización de
energía, en lugar de la forma convencional empleando
programación dinámica. Recientemente, se ha empleado
técnicas basadas en el corte del grafo para ello, y en mu-
chos de ellos el grafo era construido especialmente para
resolver el problema de minimización de energía [10].

Boykov y Jolly [2] introducen una técnica denominada
GraphCut, donde la imagen se representa como un grafo
y se utiliza un algoritmo de corte mínimo/flujo máximo para
dividir el grafo. Primeramente, los píxeles son nodos del
grafo y los arcos son ponderados definiendo una función
de costo la cual posee información de los bordes. Luego,
se emplea un algoritmo de corte mínimo/flujo máximo para
segmentar la imagen por una función de minimización. Esta
técnica está bien de