Implementação de Algoritmo de Seguimento de Objetos em FPGA

Vista previa del material en texto

TECNOLÓGICO NACIONAL DE MÉXICO
Instituto Tecnológico de La Paz
INSTITUTO TECNOLÓGICO DE LA PAZ
DIVISIÓN DE ESTUDIOS DE POSGRADO E INVESTIGACIÓN
MAESTŔIA EN SISTEMAS COMPUTACIONALES
IMPLEMENTACIÓN DE UN ALGORITMO DE
SEGUIMIENTO DE OBJETOS EN FPGA
QUE PARA OBTENER EL GRADO DE
MAESTRO EN SISTEMAS COMPUTACIONALES
PRESENTA:
JOSUÉ BENJAMÍN PALAFOX HERNÁNDEZ
DIRECTOR DE TESIS:
DR. SAÚL MART́INEZ D́IAZ
LA PAZ, BAJA CALIFORNIA SUR, MÉXICO, DICIEMBRE 2017.
Blvd. Forjadores de B. C. S. #4720, Col. 8 de Oct. 1era. Sección C. P. 23080
La Paz, B.C.S. Conmutador (612) 121-04-24, Fax: (612) 121-12-95
www.itlp.edu.mx
Dedicatoria
A mis padres por todo el apoyo que me han dado.
i
Agradecimientos
A Dios, porque todas las cosas provienen de Él.
A Nohemı́, por entenderme y tolerarme durante este tiempo de crecimiento.
A Pablo, por estar atento y alentarme a seguir adelante.
A mis profesores, por compartirme de su conocimiento y experiencia.
ii
Resumen
El seguimiento de objetos es un área importante en el campo de visión computacional,
con aplicaciones en la vigilancia, monitoreo de tráfico, veh́ıculos autónomos, e interacción con
computadoras. Para utilizar algoritmos de seguimiento en tiempo real se debe disminuir el
tiempo de ejecución de las operaciones de procesamiento de imágenes.
El método de seguimiento de objetos TLD (“Tracking-Learning-Detection”) de Z. Kalal, es
de interés debido a que combina el seguimiento tradicional y la detección de objetos utilizando
un modelo de aprendizaje con el cual se crea el modelo del objeto a partir de la primera imagen, y
lo actualiza conforme se obtiene más cuadros. Dentro del método TLD, uno de los elementos que
consume el mayor tiempo de procesamiento es la aplicación de un filtro gaussiano de suavizado,
por lo que se eligió como la función para acelerar utilizando una FPGA (“Field Programmable
Gate Array”).
En este trabajo se implementaron las funciones para trabajar con imágenes de mapa de bits
en tarjetas micro SD desde un microcontrolador, aśı como diferentes algoritmos de procesamiento
de imágenes. Finalmente, al realizar el diseño en FPGA, se disminuyó el tiempo de procesamiento
del filtrado en un 91.50 % de su implementación original en un microcontrolador.
iii
Abstract
Object tracking is an important area in computer vision with applications in surveillance,
traffic control, autonomous vehicles, and human-computer interaction. In order to use object
tracking algorithms in real time applications, the runtime of image processing operations must
be diminished.
An object tracking method of interest is Tracking-Learning-Detection developed by Z. Kalal,
due to the combination of traditional object tracking and object detection using a learning model
which creates the object model from the first image and update it as more frames are obtained.
Within this method, one of the tasks that use most of the processing time is the employment
of a gaussian filter for smoothing, which was selected to accelerate using a Field Programmable
Gate Array (FPGA).
In this work the functions that deal with bitmap images in micro SD cards from the mi-
crocontroller were implemented, as well as different image processing algorithms. In the end,
the FPGA design diminished the runtime of the smoothing filter in 91.50 % from its original
implementation in a microcontroller.
iv
Índice general
1. Introducción 1
1.1. Descripción del problema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2. Justificación . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
1.3. Hipótesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.4.1. Objetivos especificos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.5. Limitaciones y alcances . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2. Marco teórico 10
2.1. Procesamiento de imágenes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.2. Seguimiento de objetos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.3. Aceleración de algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.4. Field programmable gate array . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3. Metodoloǵıa 31
3.1. Propuesta de solución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2. Desarrollo de software . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
3.3. Desarrollo en FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
4. Resultados y conclusiones 47
4.1. Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
4.3. Trabajo futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
v
ÍNDICE GENERAL vi
A. Código fuente PC 51
A.1. conf.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
A.2. img.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
A.3. img.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
A.4. bmp.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
A.5. bmp.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
A.5.1. main.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
B. Código fuente microcontrolador 96
B.1. bmp.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
B.2. bmp.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
B.3. dma.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
B.4. dma.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
B.5. gaussian module.h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
B.6. gaussian module.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 117
B.7. main.c . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
C. Código fuente FPGA 124
C.1. gaussian filter 9x9 1 5.vhd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124
C.2. cubic hermite.vhd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129
C.3. bicubic interpolation.vhd . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131
C.4. gaussian filter.cpp . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134
C.5. Diseño de bloques en Vivado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
Bibliograf́ıa 138
Índice de figuras
1.1. Luz visible . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2. El ojo humano y su respuesta a la luz. . . . . . . . . . . . . . . . . . . . . . . . 2
1.3. Imagen digital . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4. Mejora de contraste por modificación del histograma. . . . . . . . . . . . . . . . 5
1.5. Operaciones sobre vecinos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.6. Complejidad computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.1. Comparación de una resonancia magnética de un cerebro humano con su negativo. 11
2.2. Transformación gamma a una toma aérea. . . . . . . . . . . . . . . . . . . . . . 12
2.3. Transformación logaŕıtmica para resaltar regiones oscuras. . . . . . . . . . . . . 12
2.4. Corrección del contraste por estiramiento del histograma. . . . . . . . . . . . . . 13
2.5. Corrección del contraste por ecualización del histograma. . . . . . . . . . . . . . 14
2.6. Umbralizaciónde una imagen. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.7. Acotamiento y amplificación de un rango valores de intensidad. . . . . . . . . . 16
2.8. Operaciones sobre vecinos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.9. Filtros de suavizado. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
2.10. Efecto de un filtro de suavizado en el gradiente de la imagen. . . . . . . . . . . . 19
2.11. Filtros de realce. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.12. Filtros Laplacianos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.13. Desplazamiento de la región de interés de acuerdo a Lucas-Kanade. . . . . . . . 23
2.14. Taxonomı́a de Flynn . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.15. Compuertas lógicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
2.16. FPGAs y CLBs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
vii
ÍNDICE DE FIGURAS viii
3.1. Perfil del programa del método de seguimiento TLD. . . . . . . . . . . . . . . . 32
3.2. Comparación de métodos de interpolación . . . . . . . . . . . . . . . . . . . . . 36
3.3. Conexión con interfaz SPI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4. Sistemas de archivos en microcontroladores . . . . . . . . . . . . . . . . . . . . . 39
3.5. Transacciones en las interfaces AXI4-Full y AXI4-Lite. . . . . . . . . . . . . . . 41
3.6. Comparación procesamiento secuencial y segmentado (“pipelining”) . . . . . . . 42
3.7. Convolución en FPGA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.8. Procesamiento de datos con y sin buffer en imágenes. . . . . . . . . . . . . . . . 45
3.9. Comunicación entre microcontrolador y módulo AXI4-Stream . . . . . . . . . . 46
4.1. Comparación de tiempos de ejecución . . . . . . . . . . . . . . . . . . . . . . . . 49
C.1. Diseño de bloques en Vivado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137
Caṕıtulo 1
Introducción
La visión nos permite recibir y utilizar una gran cantidad de información; este proceso
comienza con la luz. La luz se refleja o pasa a través de objetos y llega a los ojos. Nuestros ojos
perciben solo una porción del espectro electromagnético, la figura 1.1 nos muestra en dónde
se ubica esta fracción. La luz visible se encuentra en una longitud de onda entre 400 y 650
nanómetros [1].
Rayos gamma Rayos x Ultravioleta Infrarojo Microondas Radio
400nm 700nm
10-12
Longitud de
onda (m)
10-10 10-8 10-6 10-4 10-2 1 102 104
Figura 1.1: Espectro electromagnético y las longitudes de onda visibles por el ojo humano.
En el ojo humano el iris controla el tamaño de la pupila y regula la cantidad de luz que pasa
por el cristalino para llegar a la retina la cual traduce la luz a señales nerviosas y las manda al
cerebro por el nervio óptico, en la figura 1.2a se aprecian los componentes básicos del ojo. La
retina contiene células sensibles a la luz, bastones y conos. Los bastones son muy sensibles y
responden a niveles bajos de iluminación, mientras que los conos son menos sensibles y solo se
activan con luz brillante. Existen 3 tipos de conos los cuales responden óptimamente a diferentes
longitudes de onda y son responsables de nuestra visión a color [1], la respuesta de las células
fotorreceptoras se puede ver en la imagen 1.2b.
1
CAPÍTULO 1. INTRODUCCIÓN 2
(a) Estructura básica del ojo humano.
100
80
60
40
20
Conos
azules
420 nm
Bastones
500 nm 531 nm 558 nm
400 500
Longitud de onda (nm)
Po
rc
en
ta
je
 d
e 
re
sp
ue
st
a 
m
ax
im
a
600 700
Conos
verdes
Conos
rojos
(b) Respuesta de las células fotorreceptoras a dife-
rentes longitudes de onda.
Figura 1.2: El ojo humano y su respuesta a la luz.
Finalmente es en nuestro cerebro donde se lleva a cabo el procesamiento de las señales en-
viadas por la retina. Este procesamiento está compuesto de varias etapas [2]. En las primeras
etapas ocurren tareas como separar figuras del fondo, detectar bordes y caracteŕısticas básicas,
tales como color, orientación o movimiento. En las etapas intermedias la información se combina
en una representación temporal del objeto. En las últimas etapas se lleva a cabo el reconoci-
miento e identificación visual del objeto al hacer coincidir la representación temporal con figuras
anteriores del objeto guardadas en nuestra memoria visual de largo plazo. Las primeras etapas
son automáticas y dependen de las señales del ojo, mientras que las últimas etapas se basan
más en nuestro conocimiento. Este es el proceso que se lleva a cabo para que nosotros podamos
percibir los objetos e interpretar las imágenes de nuestro entorno.
La visión computacional consiste en proveer a las computadoras de la habilidad para adquirir,
analizar y entender imágenes. Las imágenes son la estructura básica de datos en la visión
computacional. Una imagen puede ser definida como una función bidimensional f(x, y) donde x
y y son coordenadas espaciales y el valor de f es la intensidad de la imagen en un punto (x, y). La
diferencia entre una imagen análoga y una imagen digital es que los valores x, y y f son continuos
en la imagen análoga, mientras que en la imagen digital son discretos. La imagen digital, al ser
discreta, tiene un numero finito de elementos, llamados pixeles, los cuales están ordenados en m
filas y n columnas. La figura 1.3 muestra la representación de una imagen digital en forma de
CAPÍTULO 1. INTRODUCCIÓN 3
un arreglo rectangular. La cantidad de pixeles en una imagen se refiere a la resolución espacial,
mientras que los diferentes valores que puede tener cada pixel es la resolución tonal o profundidad
de color. La resolución tonal depende de la cantidad de bits utilizados para guardar el valor de
cada pixel. Usualmente se usan 8 bits para imágenes monocromáticas, conocidas también como
imágenes en escala de grises, y 24 bits para imágenes a color o imágenes de color verdadero
(truecolor). Con 8 bits obtenemos 256 diferentes niveles de intensidad. Con 24 bits se pueden
representar más de 16 millones de colores a partir de la combinación de colores rojo, verde y azul
(modelo RGB), utilizando 8 bits por cada canal. Los canales de una imagen pueden representar
colores u otro tipo de información dependiendo del modelo de color.
columnas
�l
as
y
x0
1
m
n
M-1
N-10 1
44 69 111 152 181 180 171 170
46 79 122 163 185 177 174 180
49 89 136 176 195 189 187 189
57 101 150 189 208 210 194 176
79 130 169 194 205 210 205 190
87 131 160 176 177 186 194 199
74 104 124 134 133 141 156 175
54 71 83 91 94 98 113 134
Figura 1.3: Representación de una imagen digital en filas y columnas.
Los modelos de color más comunes son el RGB (“red”, “green” y “blue”), CMYK (“cyan”,
“magenta”, “yellow” y “key”), HSV o HSB (“hue”, “saturation” y “value” o “brighness”) y YUV
(“Y” contiene la luminosidad de la imagen, “U” y “V” proveen información acerca del color de
la imagen). El modelo RGB es un modelo aditivo basado en nuestra percepción de color; suma
o combina los colores rojo, verde y azul en diferentes proporciones para formar otros colores.
El modelo RGB es utilizado mayormente en dispositivos electrónicos como monitores, pantallas
y cámaras digitales. El modelo CMYK es un modelo sustractivo aplicando la absorción de luz;
la luz reflejada por un objeto es la luz que no se absorbe. Los colores cian, magenta y amarillo
funcionan como filtros que absorben los colores rojo, verde y azul respectivamente. El modelo
CAPÍTULO 1. INTRODUCCIÓN 4
CMYK se utiliza principalmente en la imprenta y originalmente no utilizaba el color negro, sin
embargo, en la práctica no se obteńıa un verdadero color negro, por lo que se agregó como un
cuarto color. El modelo HSV tiene tres componentes, matiz, saturación, y valor. El matiz nos
indica elcolor, la saturación se refiere a la pureza del color o que tan mezclado está con la
luz blanca, y el valor describe el brillo del color o luminancia. El modelo HSV proviene de una
transformación del modelo RGB con la idea de separar los componentes de un color espećıfico
de manera que fuera práctico para la interpretación humana. El modelo YUV fue desarrollado
como un modelo de color para televisión basado en el modelo RGB. “Y” es la señal luma que
proporciona el brillo; provee una imagen en escala de grises a partir de una suma ponderada de
los colores rojo, verde y azul en una proporción aproximada a la sensibilidad del ojo humano.
“U” y “V” son señales de color o crominancia y son proporcionales a las diferencias entre el
color azul y la señal luma, y, entre el color rojo y la señal luma respectivamente. Una de las
razones por la cual el modelo YUV es importante es debido a que la ecuación para calcular la
señal luma se utiliza comúnmente para obtener una imagen en escala de grises a partir de una
imagen RGB, como se muestra en la ecuación 1.1.
Y = 0.299R + 0.587G+ 0.114B (1.1)
En visión computacional es común utilizar imágenes en escala de grises ya que disminuye la
complejidad y requiere menos tiempo para procesarla. Una imagen en escala de grises contiene
menos información que una imagen a color, sin embargo, la mayor parte de la información
relacionada a las caracteŕısticas visuales como regiones y esquinas se mantiene.
Para obtener una imagen digital existen diferentes tecnoloǵıas. Los dispositivos más comunes
convierten la intensidad de luz que se refleja sobre ellos en señales eléctricas las cuales son
digitalizadas, de igual modo se puede utilizar otro tipo de radiación electromagnética tal como
rayos x, ultrasonido o calor. Independientemente del dispositivo, la formación de una imagen
digital ocurre cuando un sensor registra la radiación que interactúa con objetos f́ısicos y produce
un arreglo de muestras.
Una vez obtenida la imagen digital es común aplicarle operaciones para modificarla, ya sea
que se mejore la imagen para consumo humano, o, que se preparare para que facilite la extracción
CAPÍTULO 1. INTRODUCCIÓN 5
de información. La aplicación de estas operaciones se conoce como procesamiento de imágenes.
Algunas operaciones producen nuevas imágenes, mientras que otras producen representaciones
o descriptores no visuales. Estás operaciones aplican funciones sobre pixeles individuales o sobre
grupos de pixeles contiguos llamados vecinos. Entre las operaciones que se realizan sobre pixeles
individuales están: obtener el negativo de una imagen, en la cual se calcula el complemento de
cada pixel; estirar el histograma, donde se ampĺıa el rango de valores de la imagen; y ecualizar
el histograma, utilizado para distribuir uniformemente la frecuencia de los valores de la imagen.
La figura 1.4 muestra el cambio que se realiza sobre el histograma para mejorar el contraste de
la imagen.
(a) Imagen original con bajo contraste. (b) Imagen al estirar el histograma.
0 50 100 150 200 250 300
0
0.5
1
1.5
2
2.5
104
(c) Histograma original.
0 50 100 150 200 250 300
0
0.5
1
1.5
2
2.5
104
(d) Histograma estirado.
Figura 1.4: Mejora de contraste por modificación del histograma.
Otras operaciones se realizan sobre un pixel y los pixeles a su alrededor, llamados vecinos. La
forma más común de operaciones sobre grupos de pixeles es la aplicación de filtros. El filtrado
de imágenes requiere de dos imágenes; una se considera la entrada o imagen, y la otra se conoce
CAPÍTULO 1. INTRODUCCIÓN 6
como filtro o núcleo. La idea del filtrado de imágenes es recorrer el núcleo por toda la imagen,
conforme se va moviendo se produce una nueva imagen cuyos pixeles son calculados a partir de
los pixeles dentro del filtro. Si el valor calculado se obtiene con una función lineal de los valores
del filtro, entonces se trata de un filtro lineal. Las operaciones con filtros se utilizan comúnmente
para detectar esquinas, remover el ruido en imágenes e intensificar detalles. En la figura 1.5 se
representa visualmente la aplicación de un filtro lineal.
Núcleo
Pixeles
vecinos
Imagen de entrada Pixel procesándose 
Producto del núcleo con
el area sobre la imagen
Pixel de salida Imagen de salida
Suma de los
productos
Figura 1.5: Representación del filtrado lineal.
El ĺımite entre el procesamiento de imágenes y el análisis de imágenes no es muy claro,
sin embargo, podemos considerar diferentes niveles de procesamiento; bajo, medio y alto. El
nivel bajo incluye operaciones que reducen el ruido, mejoran el contraste o hacen más ńıtida la
imagen. Este nivel produce por lo general una imagen de salida. En el nivel medio encontramos
la segmentación, descripción de objetos y reconocimiento de objetos. Del mismo modo que el
nivel bajo, se obtiene una imagen de salida, pero también entrega atributos extráıdos de la
imagen tales como contornos u objetos etiquetados. El nivel alto está normalmente asociado a
funciones de la vista humana, donde no tan solo se reconocen objetos, sino que se determina o
entiende lo que sucede en la imagen.
CAPÍTULO 1. INTRODUCCIÓN 7
El problema de seguimiento de objetos se encuentra entre el nivel medio y alto del pro-
cesamiento de imágenes; obtenemos una imagen de salida y además extraemos caracteŕısticas
de la identificación de objetos. El propósito del seguimiento de objetos es identificar un ob-
jeto determinado en una secuencia de imágenes. Los cambios en la secuencia nos proveen de
caracteŕısticas para detectar objetos que se están moviendo y para estimar su trayectoria. El
movimiento en la secuencia nos puede revelar la forma de un objeto, la velocidad o su función.
Sus aplicaciones se encuentran en la vigilancia y seguridad, monitoreo de tráfico, navegación
de veh́ıculos e interacción entre humano y computadora. El seguimiento de objetos no es una
tarea sencilla. Entre sus dificultades se encuentran que el objeto salga de la vista de la cámara
o se oculte, que haya movimientos abruptos, que cambie de apariencia, que se confunda con el
fondo de la imagen, que cambie su tamaño, que haya cambios de iluminación, que las imágenes
estén borrosas o con algún otro tipo de ruido, que se requiera mantener la cantidad de cuadros
por segundo (procesar en tiempo real) en la secuencia.
Esta tesis tiene como interés disminuir el tiempo de procesamiento de un algoritmo de
seguimiento de objetos.
1.1. Descripción del problema
Al escribir un programa se debe tener en cuenta los recursos que va a utilizar. Los recur-
sos principales a considerar son el tiempo y la memoria. Estos dos recursos son independientes
y de acuerdo con la situación se puede elegir optimizar uno en lugar del otro. El recurso a
elegir depende de la aplicación y del sistema en el cual se va a implementar. La complejidad
computacional se refiere al análisis de la cantidad de recursos que se requieren para ejecutar un
algoritmo y lo clasifica dependiendo de su eficiencia computacional. La eficiencia de un algo-
ritmo cuantifica el número de operaciones básicas que se realizan en relación a la cantidad de
información que se está procesando. La notación para describir la cantidad máxima de recursos
que utiliza un algoritmo se conoce como “Big-O”. La notación “Big-O” se representa como
O(f(n)) donde f es la función que describe la tasa de crecimiento de recursos dependiendo del
tamaño de la entrada n. En la figura 1.6 se hace una comparación de diferentes complejida-
des computacionales considerando crecimiento constante O(1), logaritmico O(log(n)), log-lineal
CAPÍTULO 1. INTRODUCCIÓN 8
O(nlog(n)), polinomial O(n2), exponencial O(2n), y, factorial O(n!).
Número de elementos
N
úm
er
o 
de
 o
pe
ra
ci
on
es
E�ciencia
O(1)
O(log n)
O(n)
O(n log n)
O(n2)O(2
n)O(n!)
+
-
Figura 1.6: Comparación de diferentes complejidades computacionales.El procesamiento de imágenes debe su complejidad a la cantidad de datos requeridos para
representar una imagen y al número de operaciones que se deben ejecutar sobre ella. Por ejem-
plo, un algoritmo de un filtro lineal cuadrado de tamaño m que recorre una imagen cuadrada
de tamaño n tiene una complejidad computacional de O(m2n2), lo cual hace muy lenta la im-
plementación. Si además el tamaño del filtro tiende a n su complejidad se acerca a O(n4) lo
que se traduce en una operación muy lenta. Para lograr utilizar un algoritmo de seguimiento de
objetos en tiempo real debemos disminuir el tiempo que toma en procesar la información.
1.2. Justificación
La alta complejidad computacional de los algoritmos utilizados en visión computacional,
aunado al constante incremento del tamaño de las imágenes, genera el interés de encontrar nue-
vos y eficientes métodos para realizar las tareas de procesamiento de imágenes. Los dispositivos
electrónicos comunes como cámaras digitales, teléfonos inteligentes y televisiones generan y uti-
lizan imágenes de varios millones de pixeles. Para procesar esta información en tiempo real se
CAPÍTULO 1. INTRODUCCIÓN 9
requiere disminuir el tiempo que tardan en ejecutarse las operaciones sobre las imágenes. Una
solución prometedora es el empleo de FPGAs (arreglo de compuertas programable en campo,
por “Field Programmable Gate Array”), las cuales son conocidas por su poder de procesamien-
to. Una FPGA es una arquitectura programable que nos permite crear aplicaciones de hardware
dedicadas y configurables.
1.3. Hipótesis
Es posible disminuir el tiempo de procesamiento de un método de seguimiento de objetos al
implementar partes del algoritmo en una FPGA.
1.4. Objetivos
Implementar un método de seguimiento de objetos en una FPGA.
1.4.1. Objetivos especificos
Elegir un método de seguimiento de objetos. Implementar el método en C/C++. Acelerar
parte de la aplicación utilizando la FPGA. Comparar los tiempos de ejecución con y sin FPGA.
1.5. Limitaciones y alcances
Se implementará el método “Tracking-Learning-Detection” [3] (TLD) propuesto por Z. Ka-
lal. Se utilizará la FPGA modelo Zybo de la marca Xilinx. La comparación de tiempos de
ejecución se hará con la misma secuencia de imágenes sobre la tarjeta Zybo con y sin el módulo
en la FPGA.
Caṕıtulo 2
Marco teórico
2.1. Procesamiento de imágenes
El procesamiento de imágenes aplica operaciones y algoritmos sobre imágenes con dos
propósitos principales, mejorar una imagen u obtener caracteŕısticas de ella. Esto se lleva a
cabo a través de algoritmos que realizan modificaciones sobre la imagen en diferentes domi-
nios. El dominio espacial es el más común, sin embargo, al utilizar transformaciones tales como
la transformada de coseno discreta (DCT, por “Discrete Cosine Transform”), la transforma-
da discreta de Fourier (DFT, por “Discrete Fourier Transform”), o la transformada discreta
de ond́ıculas (DWT, por “Discrete Wavelet Transform”), se puede operar en el dominio de la
frecuencia.
En el dominio espacial las operaciones se aplican directamente sobre los pixeles. Estas modi-
ficaciones se pueden realizar sobre los pixeles de manera independiente o sobre un vecindario de
pixeles. Las primeras se realizan a través de operaciones sobre puntos, mientras que las últimas
hacen uso de filtros espaciales. Entre las operaciones sobre puntos más comunes están:
Obtener el negativo
Transformaciones gamma
Transformaciones logaŕıtmicas
Cambios sobre el histograma
Umbralización (“thresholding”)
10
CAPÍTULO 2. MARCO TEÓRICO 11
Acotamiento (“clamping”)
La operación de negativo produce el equivalente al negativo de una fotograf́ıa y se utiliza
para resaltar detalles blancos o claros que se encuentran sobre regiones oscuras, cuando estas
últimas son las dominantes. La ecuación 2.1 muestra como para calcular el negativo de una
imagen, donde r es el pixel de entrada, L es el número de niveles de intensidad y s es el pixel
de salida. En la figura 2.1 se aprecia esta transformación.
s = L− 1− r (2.1)
(a) Resonancia magnética de un ce-
rebro humano.
(b) Negativo de la imagen.
Figura 2.1: Comparación de una resonancia magnética de un cerebro humano con su negativo.
Los sensores de los dispositivos para capturar, imprimir o mostrar imágenes responden de
manera similar a las funciones de potencia. Este efecto puede producir imágenes muy oscuras o
muy claras. Para solucionar este problema se utiliza la corrección gamma; llamada aśı debido a
que el exponente en la función de potencia se conoce como gamma. Antes de imprimir la imagen
o mostrarla en un monitor se debe realizar esta corrección, para que en la salida se obtenga una
imagen lo más parecida a la original. De forma similar, podŕıa ser necesario aplicar la corrección
después de capturar una imagen. Para hacer una transformación gamma se utiliza la ecuación
2.2, donde c y γ son constantes positivas. La figura 2.2 muestra una toma aérea brillante a la
cual se le aplica la corrección gamma para mejorar el contraste.
s = crγ (2.2)
CAPÍTULO 2. MARCO TEÓRICO 12
(a) Vista aérea de una ciudad. (b) Corrección gamma γ = 1.50 y
c = 1.
Figura 2.2: Transformación gamma a una toma aérea.
La transformación logaŕıtmica nos permite aumentar el rango de valores de intensidad para
pixeles oscuros y comprime el rango de valores para pixeles claros en una imagen; al aplicar la
función inversa del logaritmo se produce el efecto opuesto. Esta transformación se utiliza para
resaltar detalles que se encuentran en áreas oscuras de la imagen, tal como se muestra en la
figura 2.3. La forma para calcular la transformación logaŕıtmica se muestra en la ecuación 2.3,
donde c es una constante positiva y b es la base del logaritmo.
s = c logb(1 + r) (2.3)
(a) Fotograf́ıa con poca exposición
de luz.
(b) Transformación logaŕıtmica con
c = 2.5 y b = 2.
Figura 2.3: Transformación logaŕıtmica para resaltar regiones oscuras.
El histograma de una imagen nos da la frecuencia de las intensidades. Con el histograma
se pueden apreciar propiedades como el brillo y el contraste. Dentro de las operaciones que
hay para la modificación del histograma encontramos el estiramiento y la ecualización. Estas
transformaciones se utilizan cuando la imagen tiene bajo contraste, ya sea porque no se tuvo una
CAPÍTULO 2. MARCO TEÓRICO 13
buena iluminación, por una mala configuración del dispositivo de captura, o debido al sensor.
El estiramiento del histograma expande el rango de niveles de intensidad de una imagen. La
forma de realizar esta operación se muestra en la ecuación 2.4, donde a es el valor mı́nimo y b es
el valor máximo que puede tomar un pixel (0 y 255 en el caso de imágenes de 8 bits), y donde c
es el valor mı́nimo y d es el valor máximo de intensidad que toman los pixeles en la imagen. En
ocasiones se encuentran valores at́ıpicos los cuales reducen la efectividad de la operación, por
ejemplo, si c = 0 y d = 255 la imagen no se modifica.
s = (r − c)
(
b− a
d− c
)
+ a (2.4)
(a) Vista aérea de una ciudad. (b) Imagen al estirar el histograma.
0 50 100 150 200 250
0
2
4
6
8
10
12
14
16
104
(c) Histograma original.
0 50 100 150 200 250
0
2
4
6
8
10
12
14
16
104
(d) Histograma estirado.
Figura 2.4: Corrección del contraste por estiramiento del histograma.
La finalidad de ecualizar el histograma es obtener un histograma uniforme. El histograma
nos da la cantidad de pixeles nk con intensidad rk dentro de un rango de niveles [0, L−1], donde
L es el número de posibles niveles de intensidad en la imagen. La probabilidad de ocurrencia
pr de un nivel de intensidad rk en una imagen se obtiene con la ecuación 2.5, donde MN es
CAPÍTULO 2. MARCO TEÓRICO 14
el número total de pixeles en la imagen. Para obtener un histograma ecualizado se utiliza la
ecuación 2.6, de la cual obtenemos un nuevo valor de intensidadsk por cada valor original rk,
en la imagen de salida se intercambia el valor original de cada pixel por su nueva intensidad.
pr(rk) =
nk
MN
, 0 ≤ k ≤ L− 1 (2.5)
sk = (L− 1)
k∑
j=0
pr(rj)
=
L− 1
MN
k∑
j=0
nk, 0 ≤ k ≤ L− 1 (2.6)
(a) Vista aérea de una ciudad. (b) Imagen al ecualizar el histogra-
ma.
0 50 100 150 200 250
0
2
4
6
8
10
12
14
16
104
(c) Histograma original.
0 50 100 150 200 250
0
2
4
6
8
10
12
14
16
104
(d) Histograma ecualizado.
Figura 2.5: Corrección del contraste por ecualización del histograma.
La umbralización (“thresholding”) convierte una imagen en escala de grises a una imagen
binaria. Una imagen binaria solo tiene dos valores, 0 y 1. Los valores de los pixeles menores al
umbral se hacen 0, mientras que aquellos mayores los vuelve 1. La ecuación 2.7 muestra como
CAPÍTULO 2. MARCO TEÓRICO 15
obtener una imagen binaria a partir de un umbral t.
s =
 0 si r < t1 si r ≥ t (2.7)
Con el método de Otsu [4] se selecciona de manera automática el valor del umbral. Este
método busca minimizar la varianza σw
2 dentro de cada grupo de pixeles de acuerdo a la
ecuación 2.8, haciendo una búsqueda para cada valor posible del umbral t.
σw
2(t) = ω0(t)σ0
2(t) + ω1(t)σ1
2(t) (2.8)
donde,
ω0(t) =
k−1∑
i=0
pi ω1(t) =
L−1∑
i=k
pi
σ0
2(t) =
k−1∑
i=0
[i− µ0(t)]2
pi
ω0(t)
σ1
2(t) =
L−1∑
i=k
[i− µ1(t)]2
pi
ω1(t)
µ0
2(t) =
k−1∑
i=0
i pi
ω0(t)
µ1
2(t) =
L−1∑
i=k
i pi
ω1(t)
(a) Imagen de una estatuilla. (b) Imagen umbralizada con
t = 128.
(c) Imagen umbralizada con el
método de Otsu.
Figura 2.6: Umbralización de una imagen.
El proceso de acotamiento (“clamping”) limita el rango de valores de intensidad de una
CAPÍTULO 2. MARCO TEÓRICO 16
imagen, utilizando la ecuación 2.9, donde a es el limite inferior, y b es el limite superior del
rango que se desea mostrar. Esta operación sirve para visualizar solo una región de valores de
intensidad.
s =

a si r < a
r si a ≤ r ≤ b
b si r > b
(2.9)
Una modificación del acotamiento amplifica un rango de valores de intensidad para utilizar
todos los posibles valores. Los valores fuera del rango se vuelven negros cuando son menores
y blancos para los que son mayores, mientras que a aquellos dentro del rango se les aplica un
estiramiento lineal de acuerdo a la ecuación 2.10 para cubrir todo el rango posible de valores de
intensidad.
s =

0 si r < a
(L− 1) r−a
b−a si a ≤ r ≤ b
L− 1 si r > b
(2.10)
(a) Imagen de una estatuilla. (b) Imagen acotada con a = 50
y b = 150.
(c) Amplificación de un rango
de intensidad a = 50 y b = 150.
Figura 2.7: Acotamiento y amplificación de un rango valores de intensidad.
A diferencia de las operaciones sobre puntos las cuales trabajan con los pixeles de manera
CAPÍTULO 2. MARCO TEÓRICO 17
individual, el filtrado espacial requiere de un vecindario para realizar una operación. Los vecinos
mas comunes para un pixel (x, y) son los 4 pixeles (“4-connected”) dados por (x±1, y) y (x, y±1),
aśı como los 8 pixeles (“8-connected”) descritos por (x ± 1, y ± 1). De igual modo, se pueden
utilizar otros tamaños; un vecindario es por lo general un pequeño rectángulo con centro en
(x, y).
El termino de filtrado se toma del procesamiento de señales en donde se trabajan con
frecuencias. Los filtros en el procesamiento de señales dejan pasar o rechazan (filtran) ciertos
componentes de una señal. Se puede obtener un resultado equivalente de estos filtros del dominio
de la frecuencia trabajando directamente con la imagen usando filtros espaciales.
El filtrado espacial consiste de un vecindario y de una operación predefinida que se aplica
en los pixeles delimitados por el vecindario. Si la operación que se realiza sobre los pixeles es
lineal se trata de un filtro espacial lineal, de lo contrario el filtro es no-lineal. La ecuación 2.11
muestra como se realiza el filtrado espacial lineal de una imagen de tamaño M ×N y filtro de
tamaño m× n. Para cada punto (x, y) en la imagen, el resultado g(x, y) del filtrado, es la suma
de productos de los coeficientes del filtro w y los pixeles de la imagen f que abarca el filtro. La
figura 2.8 muestra cómo se realiza el filtrado espacial.
g(x, y) =
a∑
s=−a
b∑
t=−b
w(s, t)f(x+ s, y + t) (2.11)
donde,
a =
m− 1
2
, b =
n− 1
2
Dentro del filtrado espacial lineal encontramos la correlación y la convolución. La diferencia es
que en la convolución el filtro se rota 180◦. La ecuación 2.12 describe la operación de correlación,
la cual aplica la misma operación que en la ecuación 2.11. La convolución se muestra en la
ecuación 2.13, en donde se hacen cambios de signo a consecuencia de la rotación.
w(x, y) ◦ f(x, y) =
a∑
s=−a
b∑
t=−b
w(s, t)f(x+ s, y + t) (2.12)
w(x, y) ∗ f(x, y) =
a∑
s=−a
b∑
t=−b
w(s, t)f(x− s, y − t) (2.13)
Usar la correlación o convolución para realizar el filtrado espacial es cuestión de preferencia
CAPÍTULO 2. MARCO TEÓRICO 18
Núcleo
Pixeles
vecinos
Imagen de entrada Pixel procesándose 
Producto del núcleo con
el area sobre la imagen
Pixel de salida Imagen de salida
Suma de los
productos
Figura 2.8: Representación del filtrado lineal.
[5], ya que se pueden intercambiar las ecuaciones 2.12 y 2.13 haciendo una rotación al filtro. Lo
importante es usar un filtro con su operación correcta.
Para generar un filtro de tamaño m × n se requiere especificar mn coeficientes. Estos co-
eficientes se seleccionan dependiendo de la finalidad del filtro, considerando que únicamente
implementan una suma de productos. Entre los filtros mas comunes encontramos los filtros de
suavizado (“smoothing”) y de realce (“sharpening”).
Los filtros de suavizado, o filtros pasa bajas, más utilizados son los de promedio, los cuales
calculan el promedio de la vecindad de m × n pixeles. Aqúı se encuentran los filtros de caja
(“box”) o promedio ponderado, en la figura 2.9 se aprecia un ejemplo de los coeficientes para
ambos núcleos. En estos filtros el valor obtenido se normaliza con una constante de valor igual
a la suma de los coeficientes, la principal diferencia es que en el promedio ponderado se le da
mas importancia a los pixeles cercanos al centro.
Dentro de los filtros de suavizado también se encuentra el filtro gaussiano, el cual obtiene
sus coeficientes a partir de la función gaussiana, mostrada en la ecuación 2.14. Este filtro se
utiliza para quitar las frecuencias altas en una imagen, las cuales se traducen en cambios rápidos
en los valores de los pixeles, con la finalidad de encontrar más fácilmente caracteŕısticas en la
CAPÍTULO 2. MARCO TEÓRICO 19
1 1
111
1
1 1
1
9
1
x
(a) Filtro de caja de 3×3.
4 2
121
2
1 2
1
16
1
x
(b) Filtro de promedio
ponderado de 3× 3.
Figura 2.9: Filtros de suavizado.
imagen. En la figura 2.10 se hace una comparación de una imagen con ruido contra esa misma
imagen después aplicar un filtro gaussiano; al analizar el gradiente de la imagen, en 2.10f se
puede identificar más fácilmente el limite entre las regiones negra y blanca que en 2.10c.
G(x, y) =
1√
2πσ2
e−
x2+y2
2σ2 (2.14)
(a) Imagen f1(x, y)
con ruido.
0 100 200 300 400 500 600
0
50
100
150
200
250
(b) Valores de la imagen f1(x, y),
en y = 0.
0 100 200 300 400 500 600
-200
-150
-100
-50
0
50
100
150
200
250
(c) Valores de la derivada parcial
∂
∂xf1(x, y), en y = 0.
(d) Imagen f2(x, y),
resultado de un filtro
de suavizado.
0 100 200 300 400 500 600
0
50
100
150
200
250
(e) Valores de la imagen suavizada
f2(x, y), en y = 0.
0 100 200 300 400 500 600
0
50
100
150
200
250
(f) Valores de la derivada parcial
∂
∂xf2(x, y), en y = 0.
Figura 2.10: Efecto de un filtro de suavizado en el gradiente de la imagen.
CAPÍTULO 2. MARCO TEÓRICO 20
Un filtro no lineal de suavizado es el filtro de mediana, el cual remplaza el valor del pixel por
la mediana de los valores del vecindario. Este filtro es útil cuando se tienen imágenes con ruido
impulsivo, tambiénconocido como ruido de sal y pimienta (“salt and pepper”) por introducir
pixeles blancos y negros en la imagen.
La finalidad de los filtros de realce, o pasa altas, es intensificar transiciones en la intensidad
de los pixeles. Estos filtros comúnmente utilizan la primer y segunda derivada de las imágenes.
La derivada de una función digital se basa en la diferencia de los valores de la función. En
una imagen digital estos cambios se miden entre pixeles adyacentes, al ser una función de dos
variables se utilizan derivadas parciales. La ecuación 2.15 muestra la primer derivada parcial y
2.16 la segunda derivada parcial de una imagen f(x, y).
∂f
∂x
= f(x+ 1, y)− f(x, y), ∂f
∂y
= f(x, y + 1)− f(x, y) (2.15)
∂2f
∂x2
= f(x+ 1, y) + f(x− 1, y)− 2f(x, y), ∂
2f
∂y2
= f(x, y + 1) + f(x, y − 1)− 2f(x, y)
(2.16)
Entre los filtros de realce encontramos el filtro Roberts y el filtro Sobel los cuales utilizan el
gradiente (no lineal), y el filtro Laplaciano el cual utiliza la segunda derivada. Para calcular el
gradiente de una imagen se utiliza la primer derivada, como se muestra en la ecuación 2.17.
∇f = grad(f) =
 gx
gy
 =
 ∂f∂x
∂f
∂y
 (2.17)
El gradiente nos da la dirección de la mayor tasa de cambio de f en el punto (x, y), y su
magnitud M(x, y) se puede calcular con la ecuación 2.18.
M(x, y) = mag(∇f) =
√
g2x + g
2
y (2.18)
En el caso del operador Roberts, se hace una aproximación al gradiente utilizando diferencias
cruzadas como se muestra en la ecuación 2.19, el cual produce un filtro de tamaño par (2× 2)
a diferencia del operador Sobel que usa un vecindario de (3 × 3), el cual también emplea una
aproximación al gradiente y le da mas importancia al punto medio. Las ecuaciones 2.20 y 2.21
CAPÍTULO 2. MARCO TEÓRICO 21
muestra como se aproxima el gradiente con el filtro Sobel. En la figura 2.11 se muestran los
coeficientes obtenidos para los operadores Roberts y Sobel a partir de sus ecuaciones.
gx = f(x+ 1, y + 1)− f(x, y), gy = f(x, y + 1)− f(x+ 1, y) (2.19)
gx =
∂f
∂x
= (f(x−1, y+1)+2f(x, y+1)+f(x+1, y+1))−(f(x−1, y−1)+2f(x, y−1)+f(x+1, y−1))
(2.20)
gy =
∂f
∂y
= (f(x+1, y−1)+2f(x+1, y)+f(x+1, y+1))−(f(x−1, y−1)+2f(x−1, y)+f(x−1, y+1))
(2.21)
-1 0
0 1
-10
1 0
(a) Filtro Roberts de realce.
0 0
-1-2-1
0
1 2 1
0 2
10-1
-2
-1 0 1
(b) Filtro Sobel de realce.
Figura 2.11: Filtros de realce.
Para obtener el Laplaciano de una función de dos variable, como es el caso de una imagen,
se utiliza la ecuación 2.22 y 2.23. Los coeficientes del filtro Laplaciano se muestran en la figura
2.12.
∇2f = ∂
2f
∂x2
+
∂2f
∂y2
∇2f = f(x, y − 1) + f(x− 1, y) + f(x+ 1, y) + f(x, y + 1)− 4f(x, y) (2.22)
∇2f =f(x− 1, y − 1) + f(x, y − 1) + f(x+ 1, y − 1) + f(x− 1, y) + f(x+ 1, y)
+ f(x− 1, y + 1) + f(x, y + 1) + f(x+ 1, y + 1)− 8f(x, y) (2.23)
CAPÍTULO 2. MARCO TEÓRICO 22
-4 1
010
1
0 1 0
(a) Filtro Laplaciano
sin diagonales.
-8 1
111
1
1 1 1
(b) Filtro Laplaciano
con diagonales.
Figura 2.12: Filtros Laplacianos.
2.2. Seguimiento de objetos
El seguimiento de objetos consiste en determinar la ubicación de objetos de interés en una
secuencia de imágenes. Se requiere que el seguimiento sea preciso para que sus aplicaciones
funcionen de manera correcta. Sin embargo, no es trivial desarrollar e implementar métodos
de seguimiento de objetos. Las dificultades se generan desde la adquisición de la imagen, en el
entorno, e incluso por el mismo objeto.
Los problemas en la adquisición de la imagen pueden ser debido a una baja resolución de
la cámara, las imágenes obtenidas sean borrosas, se introduzca ruido en la imagen, o que el
objeto salga del área de visión de la cámara. Las dificultades relacionadas al entorno pueden
ser causadas por cambios en la iluminación, poco contraste entre el objeto y el fondo, o porque
existen lugares donde el objeto se puede ocultar. Finalmente, el objeto puede cambiar de forma
o apariencia durante la secuencia, lo cual introduce más retos a la tarea de seguimiento.
Estas dificultades hacen que los métodos de seguimiento propuestos traten de simplificar
el problema haciendo suposiciones sobre caracteŕısticas de la secuencia de imágenes. Estas su-
posiciones pueden ser respecto a la cámara, las condiciones del entorno, o al movimiento y
caracteŕısticas del objeto. Entre los métodos más comunes de seguimiento de objetos están los
modelos basados en puntos, contornos, figuras geométricas y flujo óptico.
Los modelos basados en puntos representan al objeto con uno o varios puntos, y estiman el
desplazamiento del objeto en base a ellos. El método de Lucas-Kanade [6] considera dos funciones
f(x, y) y g(x, y), las cuales representan los valores de los pixeles en cualquier posición (x, y)
CAPÍTULO 2. MARCO TEÓRICO 23
dentro de dos imágenes. El objetivo es buscar un desplazamiento h que minimice la diferencia
entre las funciones f(x+hx, y+hy) y g(x, y) las cuales contienen la región de interés (el objeto a
seguir), la figura 2.13a muestra el desplazamiento en una dimensión y la figura 2.13b presenta su
representación en dos dimensiones. Para buscar este desplazamiento se utiliza el gradiente de la
imagen, el cual nos indica la dirección de cambio de la intensidad de los pixeles. La ecuación 2.24
muestra cómo se calcula el desplazamiento h para una dimensión. Este método funciona bien
con desplazamientos cortos, sin embargo, para desplazamientos largos se recomienda suavizar
la imagen con la desventaja de una menor eficacia.
h
G(x) - F(x)
G(x) F(x)
x
(a) Desplazamiento h en una dimensión.
f(x,y)
h
Región de interés
g(x,y)
(b) Desplazamiento de la región de interés.
Figura 2.13: Desplazamiento de la región de interés de acuerdo a Lucas-Kanade.
h =
∑
x F
′(x)[G(x)− F (x)]∑
x F
′(x)2
(2.24)
Shi-Tomasi [7] propone la utilización de puntos calculados a partir de los eigenvalores de la
imagen, y provee un método para medir la diferencia (“disimilitud”) entre las regiones de interés
original y estimada. A diferencia del detector de esquinas de Harris [8], el cual utiliza también
eigenvalores, el método de Shi-Tomasi propone considerar un valor mı́nimo en los cambios de
intensidad para que los puntos obtenidos se utilicen en el seguimiento.
En los métodos de flujo óptico, el movimiento aparente se calcula a partir del desplazamiento
de los patrones de intensidad de la imagen. Las discontinuidades en el flujo óptico ayudan a
segmentar regiones que pertenecen a diferentes objetos. Estos métodos tienen dificultades cuan-
CAPÍTULO 2. MARCO TEÓRICO 24
do los desplazamientos del objeto son grandes, se encuentran puntos que no cambian con sus
vecinos, o existen variaciones de luz que se interpretan de manera incorrecta como movimiento.
Debido a que el flujo óptico está basado comúnmente en el gradiente de la imagen, se utilizan
filtros pasa baja antes de hacer el seguimiento para evitar un cálculo incorrecto por las varia-
ciones de intensidad. El método de Horn [9], para reducir algunos de los problemas del flujo
óptico, considera que la intensidad de los pixeles dentro del objeto es constante, y que estos se
desplazan en la misma dirección.
Los métodos anteriores se basan en la estimación del movimiento y requieren saber la ubica-
ción del objeto en el cuadro anterior para continuar el seguimiento. Sin embargo, comúnmente
fallan cuando el objeto se oculta o sale del área de visión de la cámara, y aunque el objeto no
salga de vista, pueden divergir. Como alternativa se utiliza la detección de objetos.
Al utilizar detección de objetos en el seguimiento se hace la búsqueda del objeto en cada
imagen de la secuencia. A diferencia de los métodos de seguimiento tradicionales, no fallan
cuando el objeto no es visible en la imagen, al presentar desplazamientos muy grandes, y no
requieren la posición del objeto en la imagen previa. Sin embargo, requieren que la apariencia o
las caracteŕısticas delobjeto de interés se conozcan antes de empezar el seguimiento. Además,
debido a que el modelo permanece constante durante toda la secuencia, si el objeto cambia su
forma o apariencia suelen fallar.
El método “Tracking-Learning-Detection” (TLD) [3] propone utilizar seguimiento de obje-
tos basado en Lucas-Kanade junto con la detección de objetos en cascada [10] para cubrir las
desventajas de ambos, aplicando un modelo de aprendizaje para ir entrenando el detector con-
forme se obtienen más imágenes (en ĺınea). Su desventaja es la complejidad computacional del
detector; su autor reportó que el método trabaja en tiempo real únicamente en imágenes QVGA
y se recomienda buscar maneras de acelerar los algoritmos para poder mantener el tiempo de
procesamiento con imágenes más grandes.
2.3. Aceleración de algoritmos
La mayoŕıa de los algoritmos y operaciones en el procesamiento de imágenes consumen
mucho tiempo y son computacionalmente complejas. Por esta razón se buscan diferentes formas
CAPÍTULO 2. MARCO TEÓRICO 25
de acelerar los algoritmos para mejorar su tiempo de ejecución. Para poder mejorar la eficiencia
de un algoritmo se debe entender cómo se ejecutan las aplicaciones en una computadora.
Tradicionalmente los programas corren de manera serial. Un programa se divide en un con-
junto de instrucciones, y las instrucciones se ejecutan en un solo procesador, una operación por
cada ciclo de reloj. De modo que si queremos disminuir el tiempo de procesamiento se debe
incrementar la frecuencia del reloj, o buscar un algoritmo más eficiente para realizar la misma
tarea. No siempre existen algoritmos más eficientes que puedan resolver el problema, y se opta
por incrementar la frecuencia. Sin embargo, existe un ĺımite para aumentar la frecuencia del
reloj de los procesadores. Por esta razón, como alternativa, los fabricantes se han inclinado por
añadir más núcleos de procesamiento en el mismo chip. Para maximizar el uso de este tipo de
procesadores se deben diseñar programas que utilicen todos los núcleos, es decir, implementar
cómputo paralelo.
El cómputo paralelo utiliza múltiples elementos de procesamiento simultáneamente para
ejecutar un programa. La tarea a realizar se divide en partes que se puedan resolver concu-
rrentemente, y cada parte se divide a su vez en instrucciones de modo que cada elemento de
procesamiento pueda ejecutar las instrucciones de las diferentes partes al mismo tiempo. El
cómputo paralelo no solo nos permite ahorrar tiempo, sino que nos da la capacidad de resolver
problemas más grandes y complejos, los cuales seŕıan imprácticos tratar de solucionar con un
solo elemento de procesamiento.
La arquitectura de las computadoras paralelas mantiene el diseño básico de von Neumann.
Esta arquitectura se compone de cuatro componentes principales: memoria, unidad de control,
unidad aritmético lógica, y las entradas y salidas. La unidad de control y la unidad aritmético
lógica componen la unidad central de procesamiento (CPU). En la memoria se almacenan tanto
las instrucciones del programa como los datos que se usan. Las instrucciones son un tipo de
datos que le indican a la computadora qué operación realizar. Los datos son información que
utiliza el programa. La unidad de control obtiene instrucciones y datos de la memoria. Esta
coordina las operaciones que se tienen que realizar en la unidad aritmético lógica, y controla
las entradas y salidas. Las operaciones aritméticas básicas se realizan en la unidad aritmético
lógica. Finalmente las entradas y salidas se utilizan para comunicarse con el usuario.
CAPÍTULO 2. MARCO TEÓRICO 26
La diferencia entre las computadoras seriales y las paralelas es que, las últimas no están limi-
tadas a una sola CPU. Para clasificar el tipo de computadora podemos recurrir a la taxonomı́a
de Flynn, la cual se muestra en la figura 2.14. La taxonomı́a de Flynn se basa en el número de
instrucciones y datos concurrentes que puede procesar. Existen cuatro clasificaciones:
1. Una instrucción, un dato (SISD).
Son las únicas computadoras seriales en la clasificación. Ejecutan una sola instrucción y
un dato en cada ciclo de reloj. Aqúı se ubican los tipos de computadoras más antiguas
con un solo procesador o núcleo.
2. Una instrucción, múltiples datos (SIMD).
Todos los elementos de procesamiento ejecutan la misma instrucción sobre datos distintos.
Las unidades de procesamiento gráfico (GPUs) entran en esta categoŕıa.
3. Múltiples instrucciones, un dato (MISD).
En esta clasificación se trabaja el mismo dato con diferentes instrucciones. Estas compu-
tadoras no son comunes. Se puede utilizar donde se requiere redundancia y tolerancia a
errores.
4. Múltiples instrucciones, múltiples datos (MIMD).
Cada elemento de procesamiento puede ejecutar diferentes instrucciones sobre diferentes
datos. Este es el tipo de computadora paralela más común. Las computadoras conectadas
en red (clústeres) y computadoras con varios procesadores o núcleos entran aqúı.
Paralelizar aplicaciones secuenciales es dif́ıcil [11], no tan solo se necesita utilizar un equipo
con capacidad de cómputo paralelo, se requiere analizar el problema e identificar si es posible
diseñar o modificar un programa para que trabaje concurrentemente. A pesar de sus dificul-
tades, el computo paralelo tiene aplicaciones en la renderización de imágenes, codificación y
decodificación de v́ıdeo [12], simulaciones en f́ısica de part́ıculas [13] y cinética qúımica [14], la
transformada discreta de Fourier [15], y en operaciones criptográficas [16] por nombrar algunas.
Una alternativa a las plataformas tradicionales para el cómputo paralelo tales como las uni-
dades de procesamiento gráfico de propósito general (GPGPUs) y los procesadores multinúcleo
CAPÍTULO 2. MARCO TEÓRICO 27
Elemento de procesamiento
MIMDSIMD
SISD MISD
InstruccionesInstrucciones
D
at
os
D
at
os
D
at
os
D
at
os
InstruccionesInstrucciones
Figura 2.14: Taxonomı́a de Flynn.
son las FPGAs.
2.4. Field programmable gate array
Todos los dispositivos digitales se basan en una representación binaria de la información.
Todo se encuentra en uno de dos niveles lógicos, cero y uno. F́ısicamente esta representación
binaria se hace eligiendo dos niveles de voltaje: un nivel, definido como tierra, es el cero, y el
otro nivel, conocido como voltaje o Vcc, se utiliza como uno. Para emplear estos dos niveles
de voltajes en circuitos digitales se utilizan transistores. Los transistores se emplean como in-
terruptores, o como amplificadores. Su función como interruptores es de gran importancia en
los dispositivos digitales dado que todas las operaciones lógicas binarias se pueden realizar con
ellos. Esta caracteŕıstica fue lo que llevó al desarrollo de las compuertas lógicas digitales. Entre
CAPÍTULO 2. MARCO TEÓRICO 28
las compuertas lógicas básicas encontramos las puertas NOT (negación), OR (suma lógica) y
AND (producto lógico); la puerta XOR (OR-EXCLUSIVA) se forma a partir de las básicas, y,
las puertas NAND, NOR y XNOR son el complemento de la AND, OR y XOR respectivamen-
te. Adicionalmente podemos considerar el BUFFER (variable lógica) como otra compuerta la
cual realiza la función booleana de igualdad. Cada compuerta lógica tiene una tabla de verdad
asociada, la cual relaciona los valores de la salida con el valor de las entradas. En la figura 2.15
podemos ver el śımbolo de las puertas lógicas básicas, su función lógica y sus tablas de verdad.
Las compuertas lógicas son la base de todos los dispositivos digitales.
XOR
OR
AND
NOT A O
B
A
O
B
A
O
BUFFER A O
A B O
0 0 0
0 1 0
1 0 0
1 1 1 
A B O
0 0 0
0 1 1
1 0 1
1 1 1 
A B O
0 0 0
0 1 1
1 0 1
1 1 0 
A O
0 1
1 0
A O
0 0
1 1
Nombre Simbolo Función lógica Tabla de verdad
O = AB
O = A + B
O = A + B
O = A
O
O = A
B
A
O
Figura2.15: Compuertas lógicas.
Las FPGAs son un arreglo de compuertas lógicas programables. Surgieron por la necesidad
de hacer modificaciones sobre las tarjetas de circuitos integrados después de haberse fabricado.
Los cambios se deb́ıan a errores en el diseño, actualización de los estándares, o modificaciones en
las especificaciones del sistema. Después de realizar las correcciones se deb́ıan volver a fabricar las
CAPÍTULO 2. MARCO TEÓRICO 29
tarjetas de circuitos, por lo que desarrollar sistemas espećıficos que cambiaban frecuentemente
dejó de ser práctico. Los procesadores programables, tales como microcontroladores, provéıan
cierta libertad para hacer cambios o correcciones en el sistema después de su producción. Sin
embargo, las conexiones entre los componentes permanećıan fijas. En la búsqueda de desarrollar
dispositivos con conexiones programables surgió el concepto de lógica programable en campo
(“Field programmable logic”) y más adelante las FPGAs.
Los microcontroladores son reconfigurables y compactos, sin embargo, se tiene un conjunto
definido de instrucciones por lo que el diseño de software se debe adaptar correspondientemente.
No aśı en una FPGA, donde se puede hacer cualquier diseño dentro de los ĺımites de su tamaño;
los limites dependen principalmente de la cantidad de elementos que contiene la FPGA para
configurar.
Los elementos básicos de las FPGAs son los bloques lógicos configurables (CLB). Los bloques
lógicos contienen multiplexores, flip flops, y tablas de búsqueda (LUT). Estos tres elementos
se basan en compuertas lógicas. Los multiplexores se pueden considerar como conmutadores,
tienen varias entradas de la cual se selecciona una para la salida. Los flip flops se utilizan como
elementos de memoria (registros) y almacenan un solo bit. Las tablas de búsqueda implementan
tablas de verdad para un conjunto de entradas; los valores de salida se guardan en registros
y el valor de salida se selecciona con multiplexores. Adicionalmente las FPGAs pueden contar
con bloques de memoria (BRAM) y elementos de procesamiento digital de señales (DSP). Los
bloques de memoria nos permiten guardar más cantidad de información que con tablas de
búsqueda o flip flops, pero su número se encuentra limitado en la FPGA. Los DSPs son bloques
lógicos dedicados para operaciones lógicas y aritméticas. Entre las operaciones que nos permiten
hacer los DSPs están la multiplicación y adición de números binarios directamente sin tener que
implementar diseños complejos. Todos los componentes de una FPGA tienen una interconexión
programable a través de interruptores. Estos recursos de interconexión ocupan gran parte de
la FPGA [17] y sirven también para comunicar con elementos fuera de la FPGA a través de
bloques de entradas y salidas (IOBs). La figura 2.16a nos muestra la estructura básica de una
FPGA, y la figura 2.16b .
En las FPGAs trabajamos con áreas de bloques lógicos y debido a la gran cantidad de
CAPÍTULO 2. MARCO TEÓRICO 30
Bloques lógicos con�gurables
Bloques de entradas y salidas
Recursos de interconexión
(a) Estructura de una FPGA.
in1
in2
sel
out
Multiplexor
clock
/write
d
q
Flip �op
LUT
0/1
0/1
sel
out
in1
in2
multiplexor
�ip �op
(b) Elementos básicos de los CLBs.
Figura 2.16: FPGAs y CLBs.
bloques que poseen y su capacidad de interconexión se pueden crear aplicaciones paralelas en
hardware.
Para programar una FPGA se utilizan comúnmente lenguajes de descripción de hardware
(HDL). Los dos lenguajes mas conocidos son VHDL(“VHSIC Hardware Description Langua-
ge”, donde VHSIC está por “Very High Speed Integrated Circuit”) y Verilog (de la unión de
“Verification” y “Logic”). Estos lenguajes se usan para representar la operación, estructura y
conexión de circuitos electrónicos digitales, describiendo como se manipulan y mueven los da-
tos entre los diferentes elementos. También se encuentran lenguajes con un nivel más alto de
abstracción conocidos como HLS (“High Level Synthesis”) donde se pueden utilizar lenguajes
de programación como C o C++ para describir los algoritmos que se desean implementar junto
con directivas (“pragma”) que indican como procesar ciertas partes del código, y esto se traduce
a un lenguaje HDL.
Caṕıtulo 3
Metodoloǵıa
3.1. Propuesta de solución
El primer paso consistió en seleccionar el método de seguimiento de objetos. Se eligió el
método de “Tracking-Learning-Detection” (TLD) de Z. Kalal. El método TLD tiene potencial
porque combina el seguimiento tradicional y la detección de objetos, los cuales usualmente se
emplean de manera independiente. Además, la detección de objetos puede ser utilizada sin un
modelo de objeto previo al seguimiento, debido a que cuenta con aprendizaje en ĺınea. La parte
de aprendizaje inicializa al detector creando un modelo del objeto en base a la primera imagen,
al cual va actualizando conforme se obtienen más cuadros. Sin embargo, su principal desventaja
es el alto costo computacional. El detector tiene que hacer una búsqueda en cada imagen de
la secuencia, por toda la imagen, para todas las apariencias del objeto observadas en cuadros
anteriores. Por esta razón no es eficiente al utilizar imágenes de gran resolución.
Para acelerar este método se debe analizar y entender las partes donde se consume el mayor
tiempo de procesamiento. Una ventaja de este método es que su autor desarrolló una implemen-
tación en MATLAB. A partir de esta implementación podemos hacer un perfil (“profiling”) del
programa midiendo el tiempo de ejecución de las diferentes rutinas, y de este modo determinar
las partes con potencial para realizar una aceleración. Se realizó el perfil del algoritmo y la figura
3.1 muestra los datos obtenidos. Las dos partes individuales que consumen el mayor tiempo de
procesamiento son el redimensionamiento de imágenes y el suavizado de la imagen, utilizando
12.64 % y 11.54 % del tiempo total respectivamente. La función de redimensionamiento ocupa
31
CAPÍTULO 3. METODOLOGÍA 32
67.26%
19.80%
12.45%
0.49% Método TLD
Mostrar imagen
Inicialización
Otros
(a) Porcentajes de tiempos de ejecución principales.
69.38%
17.16%
7.09%
3.30%
2.61%
0.46% Detección
Suavizar imagen
Seguimiento
Aprendizaje
Obtener imagen
Otros
(b) Porcentajes de tiempos de ejecución del método
TLD.
66.38%
27.09%
3.51%
2.03%
0.99% Evaluar patrones
Redimensionar imagen
Clasi�cador NN
Obtener patrones
Otros
(c) Porcentajes de tiempos de la detección de obje-
tos.
Figura 3.1: Perfil del programa del método de seguimiento TLD.
27.09 % de la tarea de detección, ver figura 3.1c, la cual a su vez toma 69.38 % del método TLD,
ver figura 3.1b, mientras que el suavizado de imágenes emplea 17.16 % del método TLD. Este
último hace uso del 67.26 % del tiempo total de ejecución, ver figura 3.1a, consiguiendo de esta
manera los porcentajes de ejecución de 12.64 % y 11.54 % antes mencionados.
La siguiente etapa fue elegir la plataforma para realizar la aceleración de los algoritmos. Se
eligió la tarjeta Zybo de la marca Xilinx debido a que contiene una FPGA y un microcontrolador,
además se consideró su portabilidad y precio. La ventaja de la tarjeta Zybo es que se pueden
dividir labores. Las tareas de comunicación y las partes secuenciales del método de seguimiento
pueden ser ejecutadas en el microcontrolador, y las partes de cómputo intensivo se pueden
CAPÍTULO 3. METODOLOGÍA 33
acelerar en la FPGA. Por tal razón se decidió hacer el desarrollo de software en lenguaje C, y
utilizar un lenguaje de descripción de hardware (HDL) o de śıntesis de alto nivel (HLS) para la
FPGA.
3.2. Desarrollo de software
Las secciones del desarrollo de software se concentraron en:
Leer y guardar una imagen.
Aplicar un filtro de convolución gaussiano.
Realizar redimensionamiento de la imagen.
Para leer y guardar la imagen se estudiaron los formatos más comunesde imágenes; jpeg
(“Joint Photographic Experst Group”), bmp (“Bitmap”), y png (“Portable Network Grap-
hics”). Debido a que la implementación en software se hizo en bajo nivel sin libreŕıas de visión
computacional, se optó por el formato bmp por ser el de menor complejidad.
Primero, se propusieron dos estructuras, img t y filter t, para almacenar la información
relacionada a las imágenes y a los filtros respectivamente durante la ejecución del programa.
Estas estructuras se muestran en el anexo A.2.
Las funciones img load bmp y img save bmp se desarrollaron para poder leer y guardar
imágenes en el formato de mapa de bits. Los anexos A.4 y A.5 están dedicados a la implementa-
ción de estás dos funciones. La lectura de un archivo bmp nos da el ancho y largo de la imagen,
el número de bits por pixel y un arreglo con los valores de los pixeles. El número de bits es
importante para distinguir entre imágenes a color e imágenes en escala de grises.
Las imágenes a color se convierten a escala de grises en la función img rgb to gray utilizando
la ecuación para la obtención de la señal luma, Y = 0.299R + 0.587G + 0.114B, descrita en el
caṕıtulo 1. En el anexo A.3 se encuentra el código de esta función. La conversión a escala de
grises es necesaria ya que estas imágenes requieren menos tiempo para procesarse, sin perder
información de regiones y esquinas durante la conversión.
Después de contar con la capacidad de leer y escribir imágenes, se abordó el problema del
filtro de convolución gaussiano, el cual se divide en dos partes. La primera consiste en obtener
CAPÍTULO 3. METODOLOGÍA 34
los coeficientes para el filtro o núcleo, la segunda trata directamente con la aplicación del filtro
lineal sobre la imagen.
Para calcular los coeficientes del núcleo se utiliza la función gaussiana. Las ecuaciones 3.1 y
3.2 muestran la función gaussiana G(x) y G(x, y) para una y dos dimensiones respectivamente
con media µ = 0 y varianza σ2.
G(x) =
1√
2πσ2
e−
x2
2σ2 (3.1)
G(x, y) =
1√
2πσ2
e−
x2+y2
2σ2 (3.2)
Las funciones gaussian filter 1D y gaussian filter 2D calculan los coeficientes para un
filtro a partir de la función gaussiana, con tamaño y desviación estándar σ como parámetros.
Estas funciones se describen en el anexo A.3.
Una vez obtenidos los coeficientes para el núcleo, se requiere aplicar el filtro lineal de convo-
lución. El filtrado lineal de convolución en una dimensión se define en la ecuación 3.3, mientras
que 3.4 muestra el filtrado en dos dimensiones.
y[n] = x[n] ∗ h[n] =
∞∑
k=−∞
x[k] · h[n− k] (3.3)
y[m,n] = x[m,n] ∗ h[m,n] =
∞∑
j=−∞
∞∑
i=−∞
x[i, j] · h[m− i, n− j] (3.4)
Donde x[m,n] es la imagen y h[m,n] es el filtro. Dado que la convolución es conmutativa,
la ecuación 3.4 se puede reescribir como 3.5.
y[m,n] = h[m,n] ∗ x[m,n] =
∞∑
j=−∞
∞∑
i=−∞
h[i, j] · x[m− i, n− j] (3.5)
Al estudiar el filtrado lineal de convolución se encontró que la operación de filtrado se puede
separar si un filtro de dos dimensiones se logra representar como el producto de dos filtros de
una dimensión. La separación de un filtro se muestra en la ecuación 3.6.
h[m,n] = h1[m] · h2[n] (3.6)
CAPÍTULO 3. METODOLOGÍA 35
Al sustituir la ecuación 3.6 en 3.5 y desarrollar obtenemos 3.7. En esta última ecuación se
está realizando el filtrado de la imagen x en una dimensión con el filtro h1, y con el resultado
se realiza de nuevo la operación con el filtro h2. De acuerdo a la ecuación 3.3, en 3.7 se realizan
dos operaciones de convolución lineal. Debido a que la convolución es asociativa, el orden de los
filtros no afecta al resultado.
y[m,n] = h[m,n] ∗ x[m,n] =
∞∑
j=−∞
∞∑
i=−∞
h[i, j] · x[m− i, n− j]
=
∞∑
j=−∞
∞∑
i=−∞
h1[i] · h2[j] · x[m− i, n− j]
=
∞∑
j=−∞
h2[j] ·
[
∞∑
i=−∞
h1[i] · x[m− i, n− j]
]
(3.7)
Al hacer esta separación se reduce la complejidad computacional del filtrado. De la ecuación
3.4 se determina que la operación de convolución toma mn multiplicaciones y sumas para cada
elemento x[i, j], mientras que en la ecuación 3.7 se reduce a m + n multiplicaciones y sumas
para cada elemento x[i, j]. En el programa se desarrollaron los dos tipos de convolución en las
funciones img convolution single pass y img convolution double pass. En el anexo A.3 se
encuentra el código de ambas funciones.
La tercera etapa del desarrollo fue implementar el redimensionamiento de imágenes. El
tamaño de una imagen se puede cambiar con diferentes métodos. Los tres métodos más comunes
son la interpolación bicúbica, bilineal, y por los vecinos más cercanos (“nearest-neighbors”). La
figura 3.2 muestra una comparación entre los tres métodos de interpolación.
El método de los vecinos más cercanos es el más rápido de los tres, pero no es tan exacto
como los otros dos. Para cada pixel de la imagen de salida se selecciona el más cercano de los
cuatro vecinos posibles en relación a su posición sobre la imagen original.
El método de interpolación bilineal es el producto de dos funciones lineales. En la ecuación
3.8 se muestra cómo se calcula la interpolación bilineal. Este método entrega mejores resulta-
dos a comparación del método de los vecinos más cercanos, sin embargo, son necesarias más
CAPÍTULO 3. METODOLOGÍA 36
Lineal Cúbica
2D vecinos
más cercanos
Bilineal Bicúbica
1D vecinos
más cercanos
Figura 3.2: Comparación de métodos de interpolación.
operaciones.
f(x, y) =
1∑
i=0
1∑
j=0
aijx
iyi = a00 + a10x+ a01y + a1xy (3.8)
donde,
a00 = f(0, 0),
a10 = f(1, 0)− f(0, 0),
a01 = f(0, 1)− f(0, 0),
a11 = f(1, 1) + f(0, 0)− f(1, 0)− f(0, 1)
Finalmente, el método de interpolación bicúbica [18] es el de mayor complejidad computacio-
nal, pero reconstruye con mayor exactitud la imagen original. Este método requiere 16 vecinos
para calcular un pixel de salida, a diferencia de los dos métodos anteriores que solo requieren 4.
La forma de realizar la interpolación cúbica se muestra en la ecuación 3.9, esta se debe aplicar
horizontal y verticalmente para calcular la interpolación bicúbica.
CAPÍTULO 3. METODOLOGÍA 37
f(x) = f(n+ u) = INT CUB(pn−1, pn, pn+1, pn+2)
=
1
2
[
1 u u2 u3
]

0 2 0 0
−1 0 1 0
2 −5 4 −1
−1 3 −3 1


pn−1
pn
pn+1
pn+2

f(x) =
1
2
((−pn−1+3pn−3pn+1+pn+2)u3+(2pn−1−5pn+4pn+1−pn+2)u2+(−pn−1+pn+1)u+2pn)
(3.9)
donde,
x = n+ u,∀ n ∈ Z
n = bxc
u = x− n = x− bxc, 0 ≤ u < 1
pn−1 = f(n− 1)
pn = f(n)
pn+1 = f(n+ 1)
pn+2 = f(n+ 2)
Los tres métodos de redimensionamiento se implementaron en el programa en las funciones
img resize bicubic, img resize bilinear, y img resize nearest, las cuales se encuentran
en el anexo A.3.
En la PC la lectura y escritura de archivos se da de manera natural debido a que cuenta
con un sistema operativo, el cual se encarga de comunicarse con el disco duro. Sin embargo,
en un microcontrolador se debe implementar y utilizar un sistema de archivos para trabajar
con medios de almacenamiento. Por lo que, al portar el código de la PC al microcontrolador de
la Zybo, se tuvo la necesidad de agregar la habilidad de lectura y escritura. En particular se
requiere utilizar una tarjeta micro SD (“Secure Digital”), en donde se van a leer y escribir las
CAPÍTULO 3. METODOLOGÍA 38
imágenes.
La mayoŕıa de las tarjetas de memoria de la familia SD se utilizan con el sistema de archivos
FAT (“File Allocation Table”). Las tarjetas no implementan un sistema de archivos por si
mismas, sino que soportan diferentes interfaces de comunicación. Comúnmente se utiliza la
interfaz SPI (“Serial Peripheral Interface bus”). La interfaz de comunicación SPI es śıncrona,
de tipo maestro-esclavo; un solo maestro, con soporte para múltiples esclavos. Esta interfaz
cuenta con una señal para el reloj (SCLK, por “Serial Clock”), una para la transmisión de datos
(MOSI, por “Master Out, Slave In”), otra para la recepción de datos (MISO, por “Master In,Slave Out”), y una para indicar con qué dispositivo se desea comunicar (SS, por “Slave Select”).
La figura 3.3 muestra una conexión t́ıpica con esta interfaz.
SPI
Master
SCLK
MOSI
MISO
SS1
SS2
SS3
SPI
Slave
SCLK
MOSI
MISO
SS
SPI
Slave
SCLK
MOSI
MISO
SS
SPI
Slave
SCLK
MOSI
MISO
SS
Figura 3.3: Conexión con interfaz SPI.
El sistema de archivos FAT se construye sobre la interfaz de comunicación. Para reducir el
tiempo de desarrollo se buscó una implementación del sistema de archivos FAT. Se encontró un
módulo diseñado en C que implementa este sistema de archivos llamado FatFs. Sin embargo,
requiere de la interfaz de comunicación con los medios de almacenamiento. El kit de desarro-
llo de software (SDK) de Xilinx cuenta con una interfaz para tarjetas SD y sobre ella, una
versión del módulo FatFs. De este modo se continuó con la migración del código de la PC al
CAPÍTULO 3. METODOLOGÍA 39
microcontrolador. En la figura 3.4 se aprecia el proceso común para desarrollar aplicaciones en
microcontroladores o sistemas embebidos con el módulo FatFs.
Aplicación
del usuario Módulo FatFs Capa de comunicación con disco I/O Medio
Aplicación �.c
�.h diskio.h
integer.h�con�g.h
device.h
mmc.c spi.c
MMC/SD
SPI
spi_xchg()disk_read()f_open()
call
include
Figura 3.4: Sistemas de archivos en microcontroladores.
Dentro de las modificaciones que se realizaron están las funciones de lectura y escritura de
los archivos bmp, las cuales se adaptaron para utilizar las funciones del módulo FatFs. También
se agregó la función para comunicación con el módulo en la FPGA con el accesso a memoria
directo. La adaptación del código se encuentra en el anexo B, mientras que el funcionamiento
del acceso a memoria directo se describe la sección 3.3.
3.3. Desarrollo en FPGA
Se eligió hacer el desarrollo de los módulos utilizando el lenguaje VHDL debido a que permite
trabajar en un nivel de abstracción mayor que los diseños a nivel de compuertas lógicas, y con
un mayor control que con śıntesis de alto nivel. El desarrollo en la FPGA se dividió en cuatro
partes:
Comunicación con el microcontrolador.
Representación de números reales.
Implementación del filtro de convolución.
Implementación de la interpolación bicúbica.
CAPÍTULO 3. METODOLOGÍA 40
Existen diferentes maneras de comunicar la FPGA con el microcontrolador. Entre las di-
ferentes opciones se encuentran los protocolos de comunicación AXI4: AXI4-Full, AXI4-Lite y
AXI4-Stream. Estas interfaces provienen de la arquitectura de bus avanzada para microcon-
trolador (AMBA, por “Advanced Microcontroller Bus Architecture”) en su cuarta generación:
interfaz extensible avanzada (AXI4, por “Advanced eXtensible Interface”). La interfaz AXI4 es
un estándar abierto diseñado para conectar y administrar bloques dentro de diseños en sistemas
en chip (SoC, por “System on a chip”), al cual pertenece la tarjeta Zybo.
La comunicación con AXI4 se realiza entre maestro-esclavo, el maestro inicia una transacción
y el esclavo responde. Una transacción se refiere a la transferencia de datos de un punto a otro.
Para AXI4-Full y AXI4-Lite existen 5 canales que conectan al maestro con el esclavo: respuesta
de escritura (“write response channel”), escritura de dirección (“write address channel”), escri-
tura de datos (“write data channel”), lectura de dirección (“read address channel”), y lectura
de datos (“read address channel”). La figura 3.5a muestra los canales y las transacciones entre
maestro y esclavo con el protocolo AXI4-Full.
La interfaz AXI4-Lite es un subconjunto del protocolo AXI4-Full, creada para simplificar la
comunicación, de manera que el diseño y la validación de los módulos requirieran menos tiempo
para su desarrollo. La principal diferencia entre las dos interfaces es que en la AXI4-Lite las
transacciones tienen un tamaño de ráfaga (“burst”) de 1; solo se puede transferir 1 dato por
cada transacción. Mientras que en AXI4-Full se pueden mandar hasta 256 datos por transacción,
con el costo de una mayor complejidad para la interfaz. La diferencia entre la comunicación con
AXI4-Full y AXI4-Lite se puede apreciar en la figura 3.5.
Por otro lado, la interfaz AXI4-Stream solo cuenta con un canal que se utiliza para datos
(“data channel”). No cuenta con canal para indicar la dirección sobre la cual se van a escribir los
datos, ni canal para indicar el resultado de la escritura, ademas la comunicación solo se da desde
el maestro hacia el esclavo. Sin embargo, no tiene ĺımite para el tamaño de las transferencias.
La arquitectura del protocolo AXI4-Stream se muestra en la figura 3.5c.
De las tres interfaces AXI4 se eligió la interfaz AXI-Lite por su simplicidad.
El siguiente paso es representar números reales en la FPGA. Tanto el filtro gaussiano como la
interpolación bicúbica requieren utilizar números reales para calcular el resultado. Los números
reales se representan digitalmente a través números con punto flotante o punto fijo. El instituto
de ingenieros eléctricos y electrónicos (IEEE, por “Institute of Electrical and Electronics Engi-
CAPÍTULO 3. METODOLOGÍA 41
Master
interface
Slave
interface
Address
and
control
Read
data
Read
data
... Read
data
Read address channel
Read data channel
AXI4-Full Read
Write
response
Address
and
control
Master
interface
Slave
interface
Write
data
Write
data
... Write
data
Write data channel
Write address channel
Write response channel
AXI4-Full Write
(a) Transacciones con la interfaz AXI4-Full.
Master
interface
Slave
interface
Address
and
control
Read
data
Read address channel
Read data channel
AXI4-Lite Read
Write
response
Address
and
control
Master
interface
Slave
interface
Write
data
Write data channel
Write address channel
Write response channel
AXI4-Lite Write
(b) Transacciones con la interfaz AXI4-Lite.
Master
interface
Slave
interfaceData
...Data Data
Data channel
AXI4-Stream Data Transfer
(c) Transferencia de datos con el protocolo AXI4-
Stream.
Figura 3.5: Transacciones en las interfaces AXI4-Full y AXI4-Lite.
CAPÍTULO 3. METODOLOGÍA 42
neers”) especifican diferentes precisiones para números de punto flotante, basadas en la notación
cient́ıfica. Entre las más comunes está el formato de precisión sencilla (“Single-precision floating-
point format”) y el formato de precisión doble (“Double-precision floating-point format”). El
formato de precisión sencilla utiliza 32 bits: 1 bit para el signo, 8 bits para el exponente, y 23
bits para la mantisa; esto provee de 6 a 9 cifras significativas. Mientras que la precisión doble
utiliza 64 bits: 1 bit para el signo, 11 bits para el exponente, y 52 bits para la mantisa; lo cual
nos proporciona de 15 a 17 cifras significativas. Los números de punto flotante nos permiten re-
presentar un rango de números mayor que con punto fijo, a expensas de una mayor complejidad.
En los números de punto fijo, se debe conocer el rango y la precisión deseada para determinar el
número de bits necesarios y la ubicación de estos en relación al punto ráız (decimal o binario).
Los números enteros se pueden considerar un caso especial del formato con punto fijo, eligiendo
el punto en la posición cero. Para desarrollar las operaciones de filtrado y redimensionamiento
se eligió utilizar números con punto fijo, ya que se conoce de antemano los valores y la precisión
que se requieren, ademas de que su implementación es menos compleja.
El propósito de utilizar una FPGA para las operaciones en imágenes es crear aplicaciones
que trabajen concurrentemente los datos. Secuencialmente, el tiempo que se tarda en procesar
una imagen es aproximadamente igual al tiempo que se tarda en procesar un pixel multiplicado
por el número de pixeles. Si segmentamos la tarea (“pipelining”), no disminuimos el tiempo que
tarda en procesarse un pixel pero incrementamos el número de pixeles que se pueden procesar
concurrentemente.