PDF de programación - Optimización de algoritmos de procesado de imagen en sistemas microprocesadores empleando el lenguaje de programación específico HALIDE

UNIVERSITAT POLITÈCNICA DE VALÈNCIA

E S C U E L A P O L I T E C N I C A S U P E R I O R D E G A N D I A



G r a d o e n I n g . S i s t . d e T e l e c o m . , S o n i d o e I m a g e n



“Optimización de algoritmos de

procesado de imagen en sistemas
microprocesadores empleando el

lenguaje de programación específico

HALIDE”



TRABAJO FINAL DE GRADO

Autor:
VICENTE ORTIZ GONZÁLEZ

Tutor:
DR. ALFONO MARTÍNEZ GARCÍA

Tutor externo:
DR. FERNANDO DE LA TORRE
(CARNEGIE MELLON UNIVERSITY)

GANDIA, 2015







ii





A Pepe Medina.

iii





iv

Resumen

Actualmente la optimización de algoritmos para el procesamiento de imágenes en
sistemas microprocesadores requieren un alto coste de recursos humanos, siendo
necesario profesionales altamente cualificados ya que es fundamental tener un buen
conocimiento del funcionamiento de los sistemas microprocesadores así como de las
funciones intrínsecas específicas de sus respectivas arquitecturas. Este elevado coste
no puede ser asumido por pequeñas compañías o grupos de investigación con un
número reducido de recursos humanos para ser competitiva en este sector. En este
contexto surge el lenguaje de programación específico HALIDE desarrollado en el
Massachusetts Institute of Technology (MIT) en 2012 para facilitar la codificación
eficiente de algoritmos de procesado de imagen utilizando el lenguaje de
programación C++. Actualmente permite compilaciones para arquitecturas x86-64 con
el uso de SSE, ARMv7 con el uso de NEON, CUDA y OpenCL. Esto permitirá reducir
el coste de recursos humanos necesarios para los desarrollos de dichos algoritmos.

Palabras clave: visión artificial HALIDE C++ microprocesadores



Abstract

Currently the optimization of algorithms for image processing in microprocessor
systems require a high cost of human resources, highly qualified professionals still
necessary because it is essential to have a good knowledge about microprocessor
systems as well as the use of intrinsic function for each architecture. This high cost
can not be assumed by small companies, or research groups with a small number of
human resources, in order to be competitive in this sector. In this context were we find
HALIDE, an specific programming language developed at the Massachusetts Institute
of Technology (MIT) in 2012 to facilitate the efficient coding of image processing
algorithms using the C ++ programming language. Currently HALIDE allows builds for
x86-64 architectures using the SSE extensions, ARMv7 with NEON, CUDA and
OpenCL. This language aims to reduce the cost of human resources required for the
development of such algorithms.

Keywords: computer vision HALIDE C++ microprocessor

v





vi

Índice de contenidos



Capítulo 1. Introducción al trabajo final de grado ______________________________ 1

1. Contexto __________________________________________________________ 1
1.1 Lugar de desarrollo ________________________________________________________ 1
1.2 Programa PROMOE _______________________________________________________ 1
1.3 Human Sensing Laboratory _________________________________________________ 2

2. Definición del problema a resolver ____________________________________ 2
2.1 Punto de partida __________________________________________________________ 2
2.2 Contextos de aplicación ____________________________________________________ 3
2.3 Procesos de optimización ___________________________________________________ 3
2.4 Definición de la tecnología utilizada en el proyecto _______________________________ 5
2.5 Planteamiento del problema _________________________________________________ 6
2.6 Objetivos del trabajo final de grado ___________________________________________ 6
2.7 Estructura de la memoria del trabajo final de grado _______________________________ 7

Capítulo 2. Técnicas de eliminación de ruido basadas en métodos variacionales ___ 8

1. Rudin, Osher y Fatemi (ROF) _________________________________________ 8
1.1 Planteamiento Bayesiano ___________________________________________________ 8
1.1.1 Máximo a posteriori ___________________________________________________ 9
1.1.2 Adaptación a diferentes modelos de ruido _________________________________ 10
1.2 Métodos resolutivos ______________________________________________________ 10

Capítulo 3. Sistemas microprocesadores ____________________________________ 11

1. Aspectos técnicos a tener en cuenta en la programación ________________ 11
1.1 Paralelismo _____________________________________________________________ 11
1.1.1 A nivel de hilo _______________________________________________________ 11
1.1.2 A nivel de datos _____________________________________________________ 11
1.2 Memoria volátil __________________________________________________________ 12
1.3
Instrucciones por segundo (IPS)_____________________________________________ 12

2. Relación entre las prestaciones del sistema en el procesado de imágenes __ 12
2.1 Esquema de cálculo en la raíz: Sobrecarga de la memoria primaria _________________ 12
2.2 Esquema de cálculo insertado: Sobrecarga del núcleo ___________________________ 13
2.3 Esquema de cálculo paralelizado: Opción de compromiso ________________________ 14

Capítulo 4. Actuales herramientas de codificación ____________________________ 15

1. Librerías de visión artificial _________________________________________ 15

2. Librerías de álgebra lineal ___________________________________________ 16
2.1 Evaluación de prestaciones ________________________________________________ 17

3. Otras herramientas para una implementación optimizada ________________ 17

Capítulo 5. Lenguaje de programación específico HALIDE _____________________ 18

1. Lenguaje embebido en C++ _________________________________________ 18

2. Estructura básica del programa ______________________________________ 19

3. Definición del algoritmo ____________________________________________ 19
3.1 Primitivas del lenguaje ____________________________________________________ 19

4. Definición del esquema _____________________________________________ 20
4.1 Esquemas de evaluación de una función ______________________________________ 20
4.1.1 Orden por defecto ___________________________________________________ 21

vii



4.1.2 Reordenación de variables_____________________________________________ 21
4.1.3 División de variables _________________________________________________ 22
4.1.4 Fusión de variables __________________________________________________ 22
4.1.5 Evaluación en mosaico _______________________________________________ 22
4.1.6 Evaluación en vectores _______________________________________________ 23
4.1.7 Desenrollar un bucle _________________________________________________ 24
4.1.8 Paralelizado ________________________________________________________ 24
4.2 Esquema de cálculo multi-etapas ____________________________________________ 25
4.2.1 Orden por defecto ___________________________________________________ 25
4.2.2 Evaluación en el inicio ________________________________________________ 26
4.2.3 Evaluación por filas __________________________________________________ 26
4.2.4 Evaluación por filas con búfer externo ____________________________________ 27
4.2.5 Evaluación por columnas con buffer externo _______________________________ 28
4.2.6 Rendimiento de cada esquema _________________________________________ 28

5. Modos de compilación _____________________________________________ 29
5.1.1 Compilación en tiempo de ejecución _____________________________________ 29
5.1.2 Compilación estática _________________________________________________ 29

Capítulo 6. Sistemas microprocesadores embebidos basados en distribuciones
Android/Linux __________________________________________________________ 30

1.

Introducción ______________________________________________________ 30

2. Android y Linux ___________________________________________________ 30

3. Modificaciones en el núcleo Vanilla ___________________________________ 31
3.1 Términos de licencia ______________________________________________________ 31

4. Entorno de usuario ________________________________________________ 32

5. Conclusiones relativas al proceso de optimización ______________________ 32

Capítulo 7. Desarrollo del modelo de referencia del algoritmo ___________________ 33

1. Descripción y simplificación del algoritmo _____________________________ 33

2. Simulación y resultados ____________________________________________ 33

Capítulo 8. Implementación del algoritmo mediante el uso de las técnicas habituales 35

1. Objetivo __________________________________________________________ 35

2.3

2. Uso de librerías ___________________________________________________ 36
2.1 Estructura de ficheros y proceso de compilación ________________________________ 36
Implementación con librería OpenCV _________________________________________ 37
2.2
2.2.1 Codificación ________________________________________________________ 37
2.2.2 Evaluación en GNU/Linux con arquitectura x86-64 __________________________ 37
2.2.3 Evaluación en Android/Linux con arquitectura ARMv7 _______________________ 38
2.2.4 Valoraciones ________________________________________________________ 38
Implementación con librerías OpenCV y Eigen _________________________________ 39
2.3.1 Codificación ________________________________________________________ 39
2.3.2 Evaluación en GNU/Linux con arquitectura x86-64 __________________________ 40
2.3.3 Ev