clMeanShift:
Paralelización y parametrización
del algoritmo Mean Shift
utilizando OpenCL
TRABAJO FIN DE MASTER
Autor: Eduardo Martín Gaspar
Director: Doctor Mariano Rincón Zamorano
Departamento de Inteligencia Arti cial
Escuela Técnica Superior de Ingenieria Informática
Universidad Nacional de Estudios a Distancia
Curso 2010-2011
clMeanShift:
Paralelización y parametrización
del algoritmo Mean Shift
utilizando OpenCL
Trabajo Fin de Master
Máster Universitario en I.A. Avanzada: Fundamentos, Métodos y Aplicaciones
Especialidad de Sistemas Inteligentes de Diagnóstico, Plani cación y Control
Autor: Eduardo Martín Gaspar
Director: Doctor Mariano Rincón Zamorano
Departamento de Inteligencia Arti cial
Escuela Técnica Superior de Ingenieria Informática
Universidad Nacional de Estudios a Distancia
Curso 2010-2011
La única posibilidad de descubrir
los límites de lo posible es
aventurarse un poco más allá de ellos,
hacia lo imposible.
Sir Arthur C. Clarke
Agradecimientos
El agradecimiento
es la memoria del corazón.
J. B. Massieu
Tras cuatro años, el presente trabajo constituye el último peldaño para completar mis estudios de Post-
grado. Por ello, quiero aprovechar la oportunidad para dar las gracias a todas aquellas personas que me han
ayudado durante estos últimos años, y durante toda mi vida.
En primer lugar, me gustaría dar las gracias al Doctor Mariano Rincón por ofrecerme la oportunidad de
realizar este Trabajo Fin de Master, cuyo desarrollo a combinado varios de los campos que más me apasionan
de la Informática, además de por toda la ayuda que me ha prestado.
Del mismo modo, quisiera agradecer a mis Padres y a mi hermana, por todos estos años en los que
siempre han estado ahí cuando más los he necesitado, apoyándome en los momentos más difíciles y, sobre
todo, animándome a continuar estudiando día a día.
A mis amigos de toda la vida, quisiera darles las gracias por todos los grandes momentos que hemos
pasado juntos, y por todos aquellos que están por venir.
Y nalmente, y no por ello menos importante, me gustaría agradecer a Marta por todo este tiempo que
estamos pasando juntos, y sobre todo, por su apoyo, paciencia y comprensión durante este último año.
A todos ellos, gracias.
vii
Índice
Agradecimientos
1. Introducción
1.1. Aportaciones del Trabajo Fin de Master . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2. Planteamiento del Problema
2.1. El algoritmo Mean Shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
vii
1
3
4
6
2.2. Objetivos
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
10
3. Estado del Arte
3.1. Mean Shift. Optimización el proceso. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Paralelización de Algoritmos.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.1. El Modelo de Programación de OpenCL . . . . . . . . . . . . . . . . . . . . . . . . . .
3.3. Paralelización del Algoritmo Mean Shift . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4. clMeanShift
4.1. Aspectos Generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Proceso de Filtrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.1. Preprocesado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.2. Creación de la Cuadrícula Uniforme Tridimensional
. . . . . . . . . . . . . . . . . . .
4.2.3. Bucle Mean Shift
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2.4. Postprocesado
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3. Proceso de Etiquetado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5. Detalles de la Implementación
5.1. Ocupación del Procesador . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.2. Gestión de Memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5.3. Rendimiento de las instrucciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
12
14
18
21
25
25
28
28
31
35
39
40
45
46
47
50
viii
Índice
6. Resultados Experimentales
6.1. Entorno de simulación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2. Evaluación del Proceso de Filtrado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.1. Proceso de ltrado para imágenes 2D . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.2. Proceso de ltrado para imágenes 3D . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.3. Evaluación del Proceso de Etiquetado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7. Conclusiones
I Apéndices
A. clMeanShift. Manual de Usuario.
A.1. Operaciones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
A.2. Tipos de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Bibliografía
ix
53
53
56
56
69
73
79
82
83
83
85
87
Índice de guras
2.1. Ejemplos de imágenes por Resonancia Magnética 2D y 3D.
. . . . . . . . . . . . . . . . . . .
2.2.
Imagen por Resonancia Magnética 4D. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.3. Ejemplo Espacio de Características (Extraída de [8]). . . . . . . . . . . . . . . . . . . . . . . .
2.4. Evolución proceso Mean Shift (Figura extraída de [35]).
. . . . . . . . . . . . . . . . . . . . .
2.5. Aplicación del ltrado Mean Shift sobre información de escala de grises (Imagen extraída de
[8]).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.1. GPU. Arquitectura clásica. Proceso.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. GPU. Arquitectura con capacidad para Lenguajes de Shading.
. . . . . . . . . . . . . . . . .
3.3. GPU. Ejemplo aplicación Shaders.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.4. CPU y GPU. Filosofías de diseño (Extraído de [23])) . . . . . . . . . . . . . . . . . . . . . . .
3.5. CPU ((cid:78)) y GPU((cid:4)). Evolución de la capacidad de procesamiento en GFLOPS. (Extraído de
[23]) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.6. Arquitectura OpenCL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.7. Ejemplos NDRange . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.8. OpenCL. Modelo de Memoria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.9. KdTree tridimensional
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1. Organización interna puntos imagen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.2. Ejemplo Segmentación Mean Shift . Imagen 2D . . . . . . . . . . . . . . . . . . . . . . . . . .
4.3. Proceso de Filtrado.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.4. Preprocesado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.5. Preprocesado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.6. Cuadrícula Uniforme Tridimensional. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.7. Creación Cuadrícula Tridimensional Uniforme . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.8. Cuadrícula 3D. Asignación de los puntos en las celdas de la cuadrícula. . . . . . . . . . . . . .
4.9. Cuadrícula 3D. Ordenación lista de pares.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
5
6
7
8
15
15
16
17
17
19
20
20
23
26
27
29
29
30
32
32
33
34
x
Índice de figuras
4.10. Cuadrícula 3D. Obtención límites celdas. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.11. Intercambio de bucles para la paralelización del algoritmo . . . . . . . . . . . . . . . . . . . .
4.12. Bucle Mean Shift .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.13. Elementos que participan en el proceso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.14. Postproceso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.15. Topología de nodos. Ejemplo en imagen 2D. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.16. Etiquetado. Inicialización.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.17. Etiquetado. Construcción de la Lista de Equivalencia.
. . . . . . . . . . . . . . . . . . . . . .
4.18. Etiquetado. Redución Lista de Equivalencia. . . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.19. Etiquetado. Asignación Lista de Equivalencia sobre puntos imagen. . . . . . . . . . . . . . . .
4.20. Algoritmo de Etiquetado. Proceso de ejecución de los núcleos. . . . . . . . . . . . . . . . . . .
5.1. Transferencia Memoria An trión Dispositivo OpenCL . . . . . . . . . . . . . . . . . . . . .
5.2. Ejemplos de patrones de acceso a información de 4 Bytes.
. . . . . . . . . . . . . . . . . . . .
5.3. Desenrrollado de bucles.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.1.
Imágenes de prueba 2D.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
6.2.
Imagen de prueba 3D. MRI 3D. Tamaño 192 x 192 x 160 . . . . . . . . . . . . . . . . . . . .
6.3. Aplicación ltrado Mean Shift sobre imagen Mandril. h = (hs, hr).
. . . . . . . . . . . . . . .
6.4. Aplicación ltrado Mean Shift sobre imagen Lenna. h = (hs, hr).
. . . . . . . . . . . . . . . .
6.5. Aplicación ltrado Mean Shift sobre imagen MRI 2D. h = (hs, hr).
. . . . . . . . . . . . . . .
6.6. Comparativ
Crear cuenta
Comentarios de: clMeanShift: Paralelización del algoritmo de segmentación Mean Shift utilizando OpenCL (1)