PDF de programación - clMeanShift: Paralelización del algoritmo de segmentación Mean Shift utilizando OpenCL

<<>>

clMeanShift: Paralelización del algoritmo de segmentación Mean Shift utilizando OpenCLgráfica de visualizaciones

estrellaestrellaestrellaestrellaestrella(1)
Actualizado el 21 de Marzo del 2018 (Publicado el 9 de Diciembre del 2017)
269 visualizaciones desde el 9 de Diciembre del 2017
16,8 MB
101 paginas
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 Articial

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, Planicación y Control

Autor: Eduardo Martín Gaspar

Director: Doctor Mariano Rincón Zamorano

Departamento de Inteligencia Articial

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 Antrió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
  • Links de descarga
http://lwp-l.com/pdf7807

Comentarios de: clMeanShift: Paralelización del algoritmo de segmentación Mean Shift utilizando OpenCL (1)

Imágen de perfil
9 de Diciembre del 2017
estrellaestrellaestrellaestrellaestrella
buen trabajo es gratificante leer buenas enseñanzas
Responder

Comentar...

Nombre
Correo (no se visualiza en la web)
Valoración
Comentarios
Es necesario revisar y aceptar las políticas de privacidad