PDF de programación - Aceleración de algoritmos mediante hardware reconfigurable: biblioteca de procesamiento de imágenes para system generator

Página Legal

Aceleración de algoritmos mediante hardware reconfigurable: biblioteca de procesamiento de
imágenes para system generator. – La Habana : Instituto Superior Politécnico José Antonio
Echeverría (CUJAE), 2012. – Tesis (Maestría).

Dewey: 004 - Ciencia de los computadores.
Registro No.: Maestria1131 CUJAE.

(cc) Luis Manuel Garcés Socarrás, 2012.
Licencia: Creative Commons de tipo Reconocimiento, Sin Obra Derivada.
En acceso perpetuo: http://www.e-libro.com/titulos

Instituto Superior Politécnico "José Antonio Echeverría"

Departamento de Automática y Computación

Tesis para la obtención del grado de Máster en Sistemas Digitales

Aceleración de Algoritmos Mediante Hardware Reconfigurable:

Biblioteca de Procesamiento de Imágenes para System Generator

Ing. Luis Manuel Garcés Socarrás

Tutores

Dr. Santiago Sánchez Solano

Dra. Piedad Brox Jiménez

Dr. Alejandro José Cabrera Sarmiento

La Habana, 2011

Agradecimientos

Agradezco a mi familia por darme la oportunidad de superarme, sobre todo
cuando las condiciones atentaron contra ello,
a mi esposa por siempre haber estado ahí y ser la solución a mis problemas,
a mi madre por enseñarme la importancia de seguir adelante,
a mi padre por ser mi meta a seguir y a su esposa por toda la ayuda prestada,
a mis hermanos que aunque lejos nos llevamos en el corazón.
Agradezco además, a mis tutores, Alejandro, por confiar en mí, a Santi por su
ayuda incondicional, y a Piedad porque siempre ha estado ahí con una
solución viable.
A la AECID por financiar parcialmente esta investigación1,
a mis amigos, que aunque no los mencione con miedo a olvidar alguno, saben
que los aprecio mucho,
a mis estudiantes, pasados, presentes y futuros, que harán de mí un mejor
profesional,
a mis compañeros de trabajo de la CUJAE, anteriores profesores y amigos,
que me enseñaron parte de lo que sé y a buscar soluciones en lo más
recóndito,
al resto del personal de IMSE, amigos todos, cuya ayuda fue necesaria para
que esos cuatro meses se sintieran como en casa.
And last, but not the least, I also want to acknowledge Erla and Iain. You
know you will always be in my heart.
A todos muchas gracias.
El Autor.

1Este trabajo ha sido parcialmente financiado por los proyectos PCI D/024124/09 y D/030769/10
de la Agencia Española de Cooperación Internacional para el Desarrollo (MAEC-AECID). URL:
http://www.imse-cnm.csic.es/fortin/

Dedicatoria

"A mi madre, cuya enfermedad no le permitió estar aquí con nosotros"

Resumen

L A presente tesis, titulada "Aceleración de Algoritmos Mediante Hardware Reconfigurable:
Biblioteca de Procesamiento de Imágenes para System Generator", desarrolla una biblioteca
de procesado de imágenes para el flujo de diseño basado en modelos de System Generator.
Este flujo permite la implementación de sistemas de procesado de una manera sencilla y
efectiva. El diseño de la biblioteca se basa en el paralelismo de ejecución de los algoritmos
de convolución de imágenes y de ordenamiento de píxeles, potenciando la implementación
de estos sistemas en arreglos de compuertas programables (FPGA). Además, ésta utiliza
métodos de optimización de los algoritmos de procesado desde la parametrización de las
versiones genéricas hasta el uso de filtros específicos.
Por último, la efectividad de los bloques de la biblioteca de procesado es comprobada
utilizando un sistema de procesado para segmentación de imágenes con XSGImgLib.

Abstract

T HIS thesis, entitled "Acceleration of Algorithms with Reconfigurable Hardware: System
Generator’s Image Processing Library", develops an image processing library for the System
Generator’s model design flow. This flow allows the implementation of processing systems in
a simple and effective way. The design of the library is based on the parallelism of execution
of the images’ convolution and ranking pixels algorithms, improving the implementation of
these algorithms using Field Programmable Gate Arrays (FPGAs). This library also develops
optimization methods for generic processing algorithms and specific filters.
Finally, the effectiveness of the library blocks is tested using image’s segmentation proces-
sing system with XSGImgLib.

Índice general

Introducción

Arreglos de compuertas programables . . . . . . . . . . . . . . . . . . . . . . .
Herramientas de diseño electrónico automatizado . . . . . . . . . . . . . . . . .
Procesamiento de digital de imágenes utilizando FPGA . . . . . . . . . . . . . .
Diseño teórico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Problema científico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Composición del trabajo . . . . . . . . . . . . . . . . . . . . . . . . . . .

Capítulo 1 Procesamiento digital de imágenes

Introducción al procesamiento digital de imágenes

1.1.
. . . . . . . . . . . . .
1.2. Tipos de imágenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3. Procesamiento digital de imágenes
. . . . . . . . . . . . . . . . . . . . .
1.3.1. Arquitecturas de procesamiento de imágenes para sistemas autóno-
. . . . . . . . . . . . . . . . . . . . . . . . .
1.3.2. Procesamiento de imágenes con System Generator . . . . . . . . .
1.3.3. Diseño de sistemas de procesado de imágenes con XSG . . . . . .

mos reconfigurables

Capítulo 2 Filtros de procesado lineal

2.1. Fundamento matemático . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2. Arquitecturas hardware de procesado lineal
. . . . . . . . . . . . . . . . .
2.2.1. Convolución genérica no simétrica . . . . . . . . . . . . . . . . . .
2.2.2. Convolución genérica simétrica . . . . . . . . . . . . . . . . . . .
2.2.3. Convolución genérica normalizada
. . . . . . . . . . . . . . . . .
2.2.4. Diseño de filtros específicos . . . . . . . . . . . . . . . . . . . . .

i

1
1
2
3
3
4
4
5

6
6
7
9

9
13
16

23
23
26
26
30
31
33

Índice general

2.3. Parametrización de los bloques de convolución genéricos . . . . . . . . . .
2.3.1. Selección del kernel de convolución . . . . . . . . . . . . . . . . .
2.3.2. Optimización en área o velocidad . . . . . . . . . . . . . . . . . .
2.3.3. Normalización de las operaciones
. . . . . . . . . . . . . . . . . .
2.4. Comparación de arquitecturas . . . . . . . . . . . . . . . . . . . . . . . .
2.4.1. Convolución no simétrica y simétrica . . . . . . . . . . . . . . . .
2.4.2. Convolución genérica y específica . . . . . . . . . . . . . . . . . .
2.4.3. Convolución de la biblioteca XSGImgLib y de System Generator . .

Capítulo 3 Filtros de procesado no lineal

3.1. Principio de operación . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2. Arquitecturas hardware de procesado no lineal
. . . . . . . . . . . . . . .
3.2.1. Filtro genérico de ordenamiento . . . . . . . . . . . . . . . . . . .
3.2.2. Filtro específico de mediana . . . . . . . . . . . . . . . . . . . . .
3.2.3. Bloque de umbralización . . . . . . . . . . . . . . . . . . . . . . .
3.3. Comparación de arquitecturas . . . . . . . . . . . . . . . . . . . . . . . .
3.3.1. Filtros genéricos y específicos . . . . . . . . . . . . . . . . . . . .
3.3.2. Filtros de la biblioteca XSGImgLib y sistema de procesado utilizando
VHDL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Capítulo 4 Operadores morfológicos y bloques de control

4.1. Operadores morfológicos . . . . . . . . . . . . . . . . . . . . . . . . . . .
4.1.1. Fundamento matemático
. . . . . . . . . . . . . . . . . . . . . .
4.1.2. Arquitecturas hardware de procesamiento morfológico . . . . . . .
4.2. Paleta de control de la biblioteca XSGImgLib . . . . . . . . . . . . . . . .
4.2.1. Almacenadores de línea . . . . . . . . . . . . . . . . . . . . . . .
4.2.2. Registros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Capítulo 5 Procesado de imágenes utilizando XSGImgLib

. . . . . . . . . . . . . . . . . . . . . . . . .
5.1. Segmentación de imágenes
5.2. Segmentación de imágenes utilizando XSGImgLib . . . . . . . . . . . . . .
5.2.1. Eliminación de ruido . . . . . . . . . . . . . . . . . . . . . . . . .
5.2.2. Detección de bordes y umbralización . . . . . . . . . . . . . . . .
5.2.3. Suavizado de la imagen . . . . . . . . . . . . . . . . . . . . . . .
5.2.4. Operaciones morfológicas
. . . . . . . . . . . . . . . . . . . . . .

44
44
46
46
48
48
48
49

51
51
54
55
59
60
61
62

62

65
65
66
72
77
78
79

81
81
82
84
85
85
86

Biblioteca de procesado XSGImgLib

ii

Garcés Socarrás, Luis M.

Índice general

Conclusiones

Recomendaciones

Bibliografía

88

90

91

Anexos

96
Anexo 1: Componentes de la biblioteca XSGImgLib . . . . . . . . . . . . . . . .
96
Anexo 2: Núcleos de convolución de procesado lineal . . . . . . . . . . . . . . . 100
Anexo 3: Bloques básicos utilizados . . . . . . . . . . . . . . . . . . . . . . . . 101
Anexo 4: Elementos estructurales . . . . . . . . . . . . . . . . . . . . . . . . . 113
Anexo 5: Latencia de los bloques de procesado . . . . . . . . . . . . . . . . . . 114
Anexo 6: Consumo de recursos
. . . . . . . . . . . . . . . . . . . . . . . . . . 115
Anexo 7: Comparación de arquitecturas . . . . . . . . . . . . . . . . . . . . . . 123

Nomenclatura

130

Biblioteca de procesado XSGImgLib

iii

Garcés Socarrás, Luis M.

Índice de figuras

lución.

2.3. Convolución no simétrica.
2.4. Efectos de la latencia en el procesado.
2.5. Convolución simétrica.
2.6.

. . . . . . . . . . . . . . . . . . . . .
1.1. Representación de una imagen [9].
. . . . . . . . . . . . . . . . .
1.2. Modelos de representación de una imagen.
. . . . . . . . . . . . . . . . . . . . . .
1.3. Tipos de procesado de imágenes.
1.4. Clasificación de las técnicas de procesado de imágenes.
. . . . . . . . . .
1.5. Flujo de diseño con System Generator [33]. . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
1.6. Sistema de procesado de imágenes con XSG.
1.7. Co-simulación hardware de un sistema de procesado.
. . . . . . . . . . .
2.1. Resultado de la aplicación de difere