PDF de programación - Optimización de algoritmos para procesado de imágenes con GPUs

MÁSTER UNIVERSITARIO EN INGENIERÍA INFORMÁTICA



UNIVERSIDAD POLITÉCNICA DE MADRID

E.T.S. INGENIEROS INFORMÁTICOS



OPTIMIZACIÓN DE ALGORITMOS PARA

PROCESADO DE IMÁGENES CON GPUs



TRABAJO FIN DE MÁSTER



AUTOR

José Jaime González Itúrbide



TUTOR

Estíbaliz Martínez Izquierdo



OPTIMIZACIÓN DE ALGORITMOS PARA PROCESADO DE IMÁGENES CON GPUs



ii



OPTIMIZACIÓN DE ALGORITMOS PARA PROCESADO DE IMÁGENES CON GPUs



RESUMEN

El objetivo de este proyecto es evaluar la mejora de rendimiento que aporta la paralelización de
algoritmos de procesamiento de imágenes, para su ejecución en una tarjeta gráfica. Para ello, una vez
seleccionados los algoritmos a estudio, fueron desarrollados en lenguaje C++ bajo el paradigma
secuencial.



A continuación, tomando como base estas implementaciones, se paralelizaron siguiendo las directivas
de la tecnología CUDA (Compute Unified Device Architecture) desarrollada por NVIDIA.



Posteriormente, se desarrolló un interfaz gráfico de usuario en Visual C#, para una utilización más
sencilla de la herramienta.



Por último, se midió el rendimiento de cada uno de los algoritmos, en términos de tiempo de ejecución
paralela y speedup, mediante el procesamiento de una serie de imágenes de distintos tamaños.



iii

OPTIMIZACIÓN DE ALGORITMOS PARA PROCESADO DE IMÁGENES CON GPUs



iv



OPTIMIZACIÓN DE ALGORITMOS PARA PROCESADO DE IMÁGENES CON GPUs



SUMMARY

The aim of this Project is to evaluate the performance improvement provided by the parallelization

of image processing algorithms, which will be executed on a graphics processing unit. In order to do

this, once the algorithms to study were selected, each of them was developed in C++ under sequential

paradigm.



Then, based on these implementations, these algorithms were implemented using the compute unified

device architecture (CUDA) programming model provided by NVIDIA.



After that, a graphical user interface (GUI) was developed to increase application’s usability.



Finally, performance of each algorithm was measured in terms of parallel execution time and speedup

by processing a set of images of different sizes.



v

OPTIMIZACIÓN DE ALGORITMOS PARA PROCESADO DE IMÁGENES CON GPUs



vi



OPTIMIZACIÓN DE ALGORITMOS PARA PROCESADO DE IMÁGENES CON GPUs


Tabla de contenido
1.

INTRODUCCIÓN ................................................................................................. 1

2. ESTADO DEL ARTE ............................................................................................ 3

2.1. FUNDAMENTOS TEÓRICOS ...................................................................... 3

2.1.1. TELEDETECCIÓN ................................................................................. 3

2.1.2.

IMAGEN DIGITAL ................................................................................ 4

2.2. FUNDAMENTOS TECNOLÓGICOS ............................................................ 7

2.2.1. MICROSOFT VISUAL STUDIO 2010 ................................................... 7

2.2.2. C/C++ ...................................................................................................... 7

2.2.3. VISUAL C# ............................................................................................. 8

2.2.4. DRAG AND DROP ................................................................................. 8

2.2.5. CUDA ..................................................................................................... 9

3. DESARROLLO .................................................................................................. 19

3.1. DESCRIPCIÓN DE LA HERRAMIENTA ................................................... 19

3.2.

INSTRUCCIONES DE USO ........................................................................ 20

3.3. ALGORITMOS IMPLEMENTADOS .......................................................... 21

3.3.1. ALGORITMO DE RECONOCIMIENTO DE ZONAS (ARZ) .............. 22

3.3.2. ALGORITMO DE CALIBRACIÓN ABSOLUTA (ACA) ..................... 25

3.3.3. ALGORITMO FILTRO DE MEDIANA................................................ 28

3.4. CAMPOS DE APLICACIÓN ....................................................................... 31

4. RESULTADOS ................................................................................................... 33

4.1. ALGORITMO DE RECONOCIMIENTO DE ZONAS (ARZ) ..................... 35

4.2. ALGORITMO DE CALIBRACIÓN ABSOLUTA (ACA) ............................ 36

4.3. COMPARACIÓN ENTRE ALGORITMOS ................................................. 37

4.4. ALGORITMO DE FILTRO DE MEDIANA................................................. 39

5. CONCLUSIONES .............................................................................................. 43

6. LÍNEAS FUTURAS............................................................................................ 45

7. REFERENCIAS .................................................................................................. 47



vii

OPTIMIZACIÓN DE ALGORITMOS PARA PROCESADO DE IMÁGENES CON GPUs



viii



OPTIMIZACIÓN DE ALGORITMOS PARA PROCESADO DE IMÁGENES CON GPUs



LISTADO DE FIGURAS

Figura 1. Definición de teledetección. Fuente: uncoma .................................................................... 3

Figura 2. Gráfico vectorial vs Imagen matricial. Fuente: Wikipedia ¡Error! Marcador no definido.

Figura 3. Aplicaciones de cómputo en GPU. Fuente: NVIDIA ........................................................ 9

Figura 4. Operaciones de coma flotante por segundo para CPU y GPU. Fuente: NVIDIA ............. 10

Figura 5. Ancho de banda de memoria para CPU y GPU. Fuente: NVIDIA ................................... 11

Figura 6. Ejecución de un ejemplo del SDK de CUDA. Fuente: Propia ......................................... 13

Figura 7. Ejemplo de función kernel. Fuente: NVIDIA.................................................................. 14

Figura 8. Grid de bloques de threads. Fuente: NVIDIA ................................................................. 15

Figura 9. Ejemplo de código para sumar dos matrices. Fuente: NVIDIA ....................................... 16

Figura 10. Jerarquía de memoria en CUDA. Fuente: NVIDIA ....................................................... 16

Figura 11. Proceso de ejecución de una aplicación CUDA. Fuente: NVIDIA ................................ 17

Figura 12. Pantalla principal de la herramienta. Fuente: Propia...................................................... 19

Figura 13. Ejemplo de ejecución de la herramienta. Fuente: Propia ............................................... 20

Figura 14. Ejemplo de imagen de entrada ...................................................................................... 21

Figura 15. Interfaz de selección de parámetros para el algoritmo de reconocimiento de zonas. Fuente:

Propia ........................................................................................................................................... 22

Figura 16. Ejemplo de imagen de salida del algoritmo de reconocimiento de zonas. Fuente: Propia

..................................................................................................................................................... 23

Figura 17. Fragmento de código secuencial del algoritmo de reconocimiento de zonas. Fuente: Propia

..................................................................................................................................................... 24

Figura 18. Fragmento de código paralelo del algoritmo de reconocimiento de zonas. Fuente: Propia

..................................................................................................................................................... 24

Figura 19. Interfaz de selección de parámetros para el algoritmo de calibración absoluta. Fuente:

Propia ........................................................................................................................................... 25

Figura 20. Ejemplo de imagen de salida del algoritmo de calibración absoluta. Fuente: Propia ...... 26

Figura 21. Fragmento de código secuencial del algoritmo de calibración absoluta. Fuente: Propia 27

Figura 22. Fragmento de código paralelo del algoritmo de calibración absoluta. Fuente: Propia .... 27

Figura 23. Interfaz de selección de parámetros para el algoritmo filtro de mediana. Fuente: Propia 28

Figura 24. Fragmento de código secuencial del algoritmo filtro de mediana. Fuente: Propia .......... 30

Figura 25. Fragmento de código paralelo del algoritmo filtro de mediana. Fuente: Propia ............. 30

Figura 26. Primera imagen sobre la que se aplican los algoritmos. Fuente: bitpalast.net ................ 33

Figura 27. Imagen dos sobre la que se han aplicado los algoritmos. Fuente: zeiss.es ...................... 33



ix

OPTIMIZACIÓN DE ALGORITMOS PARA PROCESADO DE IMÁGENES CON GPUs


Figura 28. Imagen 3 sobre la que se han aplicado los algoritmos ................................................... 34

Figura 29. Tamaño vs Tiempo de procesamiento (ARZ). Fuente: Propia ....................................... 35

Figura 30. Tamaño VS Tiempo de procesamiento (ACA). Fuente: Propia ..................................... 36

Figura 31. Tamaño VS Tiempo de procesamiento. Fuente: Propia ................................................. 37

Figura 32. Speedup. Fuente: Propia ............................................................................................... 38

Figura 33. Imagen 1400x719. Tamaño ventana VS Tiempo de procesamiento .............................. 39

Figura 34. Imagen 4256x2832. Tamaño ventana