PDF de programación - 3D GrabCut: Una segmentación de volúmenes basada en la técnica GrabCut utilizando la GPU

3D GrabCut: Una segmentación de volúmenes basada en la

técnica GrabCut utilizando la GPU

Pablo Temoche1, Esmitt Ramírez1, Rhadamés Carmona1

1Centro de Computación Gráfica, Universidad Central de Venezuela. {pablo.temoche | esmitt.ramirez | rhadames.carmona}@ciens.ucv.ve

RESUMEN

La segmentación de imágenes consiste en obtener una región de interés dentro de un espacio más amplio. Grab-
Cut es una técnica reciente de segmentación 2D que obtiene excelentes resultados. Esta se basa en representar la
imagen como un grafo de flujo, y luego aplicar un algoritmo de corte mínimo en el grafo y separar la imagen de fondo
(background) y la región de interés (foreground). Este artículo presenta un enfoque novedoso para segmentar volúmenes
basado en GrabCut empleando un esquema de algoritmo paralelo que se ejecuta en la GPU denominado 3D GrabCut.
El grafo es creado completamente en la GPU y se ejecuta sobre la arquitectura CUDA de NVIDIA R. Las pruebas
demuestran excelentes resultados con los volúmenes de prueba, arrojando tiempos inferiores que su ejecución en la
CPU y una separación adecuada background/foreground.

ABSTRACT

The image segmentation consists in obtaining a region of interest within a larger area. GrabCut is a recent tech-
nique of 2D segmentation which presents excellent results. This is based on representing the image as a flow network,
and then apply a minimum cut algorithm on the graph and separate the background image (background) and the region
of interest (foreground). This article presents a novel volume segmentation approach based on GrabCut. It implements
a parallel algorithm on the GPU called 3D GrabCut. The graph is created entirely on the GPU and runs on NVIDIA’s
CUDA architecture R. Tests show excellent results with test volumes, reducing the computing time with an adequate
separation background/foreground.
Palabras claves: segmentación de volúmenes, GPU, GrabCut, max-flow/min-cut.

1. Introducción
El proceso de extraer ciertas zonas de interés de una imagen,
se conoce como segmentación. La segmentación de imá-
genes consiste en separar una imagen en al menos dos re-
giones con características diferentes. Cada región debe ser
homogénea con respecto a ciertos criterios de similitud. En
el caso de imágenes 3D, a dicho proceso se le conoce como
segmentación de volúmenes.

Las

técnicas empleadas para la segmentación de
volúmenes aplican algoritmos que requieren de un tiempo de
procesamiento considerable [Ban08, PRH10]. Dicho proce-
samiento generalmente se realiza como una etapa previa al
manejo del volumen, siendo dependiente de su tamaño y ca-
racterísticas.

Recientemente, una serie de algoritmos en la GPU
(Graphics Processing Unit) han sido desarrollados con el
objetivo de explotar su paralelismo y conseguir los mis-
mos resultados que los algoritmos convencionales en la CPU
(Central Processing Unit) pero en menor tiempo. Este cre-
cimiento se debe principalmente a la facilidad de adquisi-
ción de un hardware gráfico y a la cantidad de herramientas
de programación existentes. Un ejemplo notable se observa

con la arquitectura CUDA desarrollada por NVIDIA Corpo-
ration [NVI11], la cual provee un entorno de desarrollo de
algoritmos que se ejecutan en los núcleos (cores) de la GPU.

Como parte de los algoritmos que son implementados en
la GPU para mejorar los tiempos de obtención sus resulta-
dos, se encuentra la segmentación de volúmenes. En este tra-
bajo, se plantea un algoritmo basado en GrabCut [RKB04]
para la segmentación de volúmenes en la GPU empleando
la arquitectura de CUDA. La idea principal, es seleccionar
una región de interés dentro del volumen a estudiar, luego
aplicar una versión modificada del algoritmo de GrabCut y
así obtener 2 sub-volúmenes: foreground (zona de interés) y
background (resto del volumen).

Este trabajo presenta un enfoque novedoso para la seg-
mentación en volúmenes basados en el algoritmo de Grab-
Cut. El algoritmo construye un grafo con peso basado en
los vóxeles del volumen y su color asociado de acuerdo a
una función de transferencia. También se construye un algo-
ritmo paralelo de Push-Relabel ejecutado y almacenado en el
hardware gráfico. Al mismo tiempo, se presenta un esquema
para el tratamiento de hilos inactivos en la GPU. Por último,
se estudian los resultados obtenidos y son comparados con

una implementación en la CPU del mismo algoritmo en su
versión secuencial.

La siguiente sección presenta una introducción a la teoría
de grafos asociada con la segmentación de imágenes em-
pleada en nuestra propuesta. En la sección 3 se explican to-
dos los detalles de nuestra propuesta basada en el algoritmo
de GrabCut para la segmentación de volúmenes. La sección
4 muestra las pruebas y resultados aplicados con el fin de
comprobar la eficacia de nuestra propuesta: resultados vi-
suales, tiempo de ejecución y consumo de memoria (tanto
en la CPU como en la GPU). Finalmente, la sección 5 mues-
tra las conclusiones y trabajos futuros.

2. Segmentación como un problema de grafos
El problema de segmentación de imágenes puede verse
como un problema de grafos, al asociar a cada píxel un nodo
del grafo. Boykov y Kolmogorov [BK04] plantean un en-
foque para la minimización de energía empleando grafos.
La minimización de energía dentro de un grafo permite se-
parar componentes que tengan algún tipo de relación bajo un
cierto criterio (e.g. color, gradiente, etc.).

Recientemente, se han empleado técnicas basadas en di-
vidir una imagen, representada como un grafo, en dos o más
sub-grafos, donde cada uno de ellos representa un subcon-
junto de este. Entre los algoritmos existentes para dividir un
grafo, se encuentra el corte de un grafo.

2.1. Corte de un grafo
Sea G = (V,A) un grafo dirigido que posee un conjunto de
nodos y un conjunto de aristas que enlazan dichos nodos. El
corte de un grafo consiste en eliminar un conjunto de aristas
A, con el fin de obtener dos grafos disjuntos G1 y G2 tal que
G = G1 ∪ G2. El peso w del corte de un grafo es la suma de
todos los pesos de las aristas eliminadas, w = ∑we. Por otro
lado, el corte mínimo es el corte con el menor peso de todos
los posibles cortes en el grafo.

De acuerdo con el

teorema de max-flow/min-cut
[CLRS01], el corte mínimo en un grafo puede ser obtenido
utilizando el algoritmo max-flow. Un algoritmo de max-flow
consiste en determinar la máxima capacidad de flujo que
puede ingresar a través de un nodo fuente (source) e ir hacia
un nodo destino (target). En el algoritmo, las aristas satu-
radas (aristas con we = 0) son eliminadas por el algoritmo
para obtener el corte mínimo. Entre los algoritmos más em-
pleados para calcular el corte mínimo están los propuestos
por Ford y Fulkerson [FF62] y el enfoque de Goldberg y
Tarjan [GT88] llamado Push-Relabel.

Boykov y Jolly [BJ01] proponen una técnica denominada
GraphCut, donde la imagen se representa como un grafo y se
divide el grafo con un algoritmo de max-flow/min-cut. Pos-
teriormente, Rother et al. [RKB04] introducen un enfoque
novedoso llamado GrabCut, el cual se divide un grafo en dos
regiones: background y foreground empleando una función
de energía basada en similitud de los colores. Este enfoque
emplea unas funciones de minimización de energía de forma
eficiente utilizando un algoritmo de corte mínimo.

La siguiente sección muestra nuestro enfoque, 3D Grab-
Cut, basado en la propuesta de Rother et al. [RKB04], apli-
cando modificaciones sobre el cálculo de los valores del
grafo para ser usado en un volumen.

3. 3D GrabCut

GrabCut es un algoritmo iterativo compuesto de varias eta-
pas que combina valores estadísticos y el enfoque de Graph-
Cut [BJ01] con el fin de segmentar una imagen. En GrabCut,
los datos de entrada son seleccionados por el usuario al se-
leccionar una región a segmentar dentro de la imagen origi-
nal utilizando un rectángulo. En la Figura 1a se presenta un
ejemplo, donde el usuario dibuja un rectángulo de color rojo
que representa la región donde se encuentra el objeto a ex-
traer. La Figura 1b muestra el resultado obtenido después de
aplicar el algoritmo de GrabCut.

(a) Imagen original con el área selec-
cionada por el usuario

(b) Imagen seg-
mentada

Figura 1: Segmentación de una imagen empleando la técnica
de GrabCut. Imagen extraída de [RKB04].

Nuestra propuesta denominada 3D GrabCut, el proceso de
segmentación se realiza sobre un espacio tridimensional. Por
ello, el usuario debe seleccionar un cubo o sub-volumen en
vez de utilizar un rectángulo, para seleccionar el objeto de
interés.

El algoritmo de 3D GrabCut crea un grafo de flujo en re-
des [CLRS01] donde cada vóxel representa a un nodo del
grafo. Cada nodo es enlazado con sus vecinos utilizando
aristas dirigidas con peso, denominadas N-Links. El número
de vecinos posibles puede ser de máximo 26 (todos los vó-
xeles que están a distancia 1). En el grafo de flujo en redes,
existen 2 nodos especiales: fuente s y destino t. El nodo s está
conectado con cada vóxel que pertenece al sub-volumen de
selección (foreground). Igualmente, el nodo t está conectado
con cada vóxel fuera de la selección (background).

Cada nodo del grafo está conectado con una arista con
peso a la fuente y por medio de otra al destino. Estas aris-
tas son denominadas T-Links, y su peso es calculado emple-
ando los modelos mixtos gaussianos (GMM) [CCSS01] para
los grupos foreground y background. En nuestro enfoque, un
GMM está formado por 5 componentes para el foreground y
5 componentes para el background.

Un componente perteneciente a un GMM es derivado de
las estadísticas de color en cada región de la imagen. Con
el fin de separar los componentes que contengan a un grupo
de vóxeles con características de color similares, se buscan
los de menor valor en su varianza. Existen diversos méto-
dos para realizar esta búsqueda. En 3D GrabCut, se empleó
la técnica de cuantización de color descrita por Orchad y
Bouman [OB91].

Luego de calcular los pesos de los T-Links, siguiendo el
esquema de GrabCut, se aplica