Histogram Equalization

Germán Alejandre Campos

Alejandro Fortes Hidalgo
Problema a resolver
La idea de la realización de este proyecto la sacamos del pdf de las propuestas de proyecto
del Racó. En el que la idea era:

1.​ Generar el histograma de la imagen.

2.​ A partir del histograma, en función de los valores máximos y mínimos, una tabla
de traducción.
3.​ Ecualizar la imagen.

Primero tenemos que saber que es un histograma de una imagen. Este es una
representación gráfica de la distribución de los distintos tonos de una imagen
que puede sernos útil para la exposición de nuestras fotos o para corregir los colores.

El eje horizontal representa los diferentes tonos de gris desde el negro puro hasta el
blanco puro.

El eje vertical representa el número de píxeles que contiene la imagen para cada tono
representado en el eje horizontal.

No hay un histograma igual, pero como regla general se considera que una imagen tiene
un buen contraste si su histograma se extiende ocupando todo el rango de tonos. En

2
cambio en las más oscuras, el histograma se verá fuertemente desplazado a la izquierda, y
en las más iluminadas, se verá desplazado al lado derecho.

A parte, tenemos la posibilidad de realizar un análisis más detallado debido a que es

posible por su composición de tres canales de color RGB que podremos analizar
mediante el histograma de canales de color, del cual obtendremos 3 histogramas
distintos, uno para cada color.

Sabiendo ya lo que es un histograma, vamos a ver lo que es hacer la ecualización de

este.

La ecualización de un histograma es una técnica de procesamiento de imágenes

utilizada para mejorar el contraste de las imágenes. Esto se logra mediante la
distribución efectiva de los valores de intensidad más frecuentes, es decir, estirando el
rango de intensidad de la imagen.

Este método generalmente aumenta el contraste global de las imágenes cuando sus datos
utilizables están representados por valores de contraste cercanos. Esto permite que las
áreas de menor contraste local obtengan un mayor contraste.

Para el histograma de color, no se podría aplicar esta técnica por separado a los
componentes rojo, verde y azul de la imagen, ya que conduce a cambios dramáticos en el

3
balance de color de la imagen. Sin embargo, si la imagen se convierte primero a otro
espacio de color, como el HSL/HSV, el algoritmo se podría aplicar al canal de
luminancia o valor sin generar cambios en el tono y la saturación de la imagen.

A partir de esta introducción sobre lo que es la “Histogram Equalization”, nos pusimos

en marcha para la búsqueda de un código válido para nuestro proyecto.

Hicimos una búsqueda exhaustiva de los posibles códigos para utilizar como base del
proyecto, de los cuales los finalistas fueron:

●​ [Link]
/Digital_Image_Processing_Codes/Assignment_5/Histogram%20Equalisation

●​ [Link]

●​ [Link]

Finalmente nos quedamos con el tercero debido a su facilidad y entendimiento del

código, ya que vimos que podíamos realizar una buena traducción a CUDA. Este sigue
los siguientes pasos para la ecualización:

-​ Obtiene la imagen e inicializa las variables necesarias para el algoritmo.

-​ Crea el histograma para los valores de los pixeles.

4
 -​ Encuentra los valores normalizados utilizando una función “cumulative mass”.
-​ Finalmente, se consigue la imagen ecualizada y se escribe en un archivo .bmp.

Por definición, la función “cumulative mass” es la probabilidad de que una determinada

variable aleatoria X puede llevar un valor hasta una cierta constante y la parte de “mass”
es para mostrar que estamos discutiendo sobre una variable aleatoria discreta.

A partir de aquí, fuimos probando y buscando información de los códigos y librerías

que nos harían falta para la paralelización y la obtención de la imagen.

Para la Lectura/Escritura de Imágenes en ficheros jpg y bmp utilizamos el código

proporcionado en el racó el 7 de Mayo de 2020, en el que nos dáis un “[Link]”
(librerías stb_image y stb_image_write).

A partir de ahí, la búsqueda de funciones e información de CUDA para poder traducir

el código ha sido exhaustiva, en el que hemos tenido que mirar la documentación
directamente de NVIDIA “CUDA Toolkit Documentation”.

-​ [Link]
nctions

En el que también aparece información sobre las funciones atómicas que tan necesarias
han sido para nuestro código.

Finalmente, la comunicación con nuestro propio profesor de laboratorio, que con los
meetings y las respuestas mediante correo, nos han ayudado a resolver muchos bugs y
errores.

5
Implementaciones realizadas y descripción
Nuestra versión principal del código es:
...

6
El cual tiene 3 fors:

-​ El primer for calcula la cantidad de apariciones de cada píxel en la imagen

original para crear un histograma.
-​ El segundo for es el más completo, ya que contiene 2 fors y se puede paralelizar
de maneras distintas. Éste es el encargado de calcular la probabilidad de aparición
de cada color en la imagen (función “cumulative mass”).
-​ El tercer for se encarga de generar la imagen de salida.

La idea principal de las diferentes implementaciones era cambiar la cantidad de threads

que se le pasan al principio y que cada iteración contenga un thread para ver cómo le
afectaba esto al código, como también tener versiones diferentes en el segundo for, una
dejando que lo que hay dentro de este lo haga la GPU y otra versión paralelizando todo
el for.

Pero, debido a todas las complicaciones que nos encontramos con la realización de estas
versiones, decidimos hacer otro tipo de versiones añadiendo unas cuantas más:

-​ La primera versión de nuestro código se basa en una distribución por filas (dim1)
y se hace la misma distribución de threads y bloques para todos los kernel.

-​ En la segunda versión pasamos de una distribución de únicamente filas, por una

distribución de filas y columnas (dim 2) y además, se personaliza el dimBlock y el
dimGrid de cada kernel.

-​ La tercera versión cuenta con una utilización directa de memoria pinned, que
permite ahorrarnos el paso de conversión de memoria paginada => pinned. Ésto
supondrá una mejora notable en las imágenes más grandes. También hicimos
variables del device las variables histogram y transfer_function en vez de
declararlas en el host para luego ser transferidas. Además, quitamos el if del
segundo kernel, ya que éste no era necesario.

7
-​ Y finalmente, la cuarta y última versión, sería la utilización de multi-GPU. Este
ha sido el más costoso y que más trabajo nos ha llevado. Suponemos que rendirá
mejor en imágenes muy grandes, ya que dividimos la carga de trabajo en 4.

8
Análisis del rendimiento obtenido
Aquí vamos a hacer un análisis de los resultados obtenidos con los tiempos y el ancho de
banda para así poder ver y comprobar de primera mano las mejoras realizadas al código y
como la GPU reacciona a estas. No incluimos los GFLOPS ya que nuestro programa no
utiliza en ningún momento operaciones de coma flotante.

Para todas las ejecuciones, hemos utilizado dos tipos de imágenes. Una de tamaño
pequeño ([Link]) y otra de tamaño grande (cé[Link]) para así ver el
comportamiento de cada versión hacia la cantidad de píxeles de cada imágen. Para cada
versión, se ha ejecutado 3 veces y hemos cogido como resultado la media de estas 3
ejecuciones.

​ [Link] (Original)​ ​ ​ ​ [Link] (Ecualizada)

[Link] (Original)​ ​ ​ ​ [Link] (Ecualizada)

9
Primero vamos a obtener los datos del código secuencial sin traducir a CUDA, el código
que venía directamente en Github.

Imagen Iteración Tiempo (ms)

1 1,036
[Link] 2 1,151

3 1,122

Media 1.103

Imagen Iteración Tiempo (ms)

1 12,120
[Link] 2 13, 080

3 13, 074

Media 12,758

Seguidamente vamos a analizar las versiones realizadas. El tiempo mostrado es el tiempo

total que tarda la aplicación en ejecutarse (datos + kernel), mientras que el ancho de
banda es la media entre el ancho de banda al enviar la imagen y el ancho de banda al
recibirla.

Para la versión 1, en la que realizamos una distribución por filas:

10
 Imagen Iteración Tiempo (ms) Ancho de banda (GB/s)
1 0,707 9,423
[Link] 2 0,707 9,416
3 0,708 9,404
Media 0,707 9,414

Imagen Iteración Tiempo (ms) Ancho de banda (GB/s)

1 23,841 1,719
[Link] 2 22,928 1,785
3 22,584 1,544
Media 23,117 1,682

Para la versión 2, en la que realizamos una distribución elemento a elemento (1x1):

Imagen Iteración Tiempo (ms) Ancho de banda (GB/s)

1 0,497 9,453
[Link] 2 0,517 9,443
3 0,507 9,393
Media 0,507 9,429

11
 Imagen Iteración Tiempo (ms) Ancho de banda (GB/s)
1 19,656 1,642
[Link] 2 17,864 1,875
3 18,890 1,732
Media 18,803 1,749

Para la versión 3, en la que pasamos a utilizar memoria pinned e implementamos más

optimizaciones:

Imagen Iteración Tiempo (ms) Ancho de banda (GB/s)

1 0,557 9, 435
[Link] 2 0,573 7, 768
3 0,567 9, 429
Media 0,572 8,877

Imagen Iteración Tiempo (ms) Ancho de banda (GB/s)

1 8,014 9,727
[Link] 2 8,004 9,810
3 8,000 9,722
Media 8,006 9,753

12
Por último, la versión 4, donde se utilizaba más de una GPU:

Imagen Iteración Tiempo (ms) Ancho de banda (GB/s)

1 0,811 30,228
[Link] 2 0,932 30,462
3 0,811 30,492
Media 0,851 30,394

Imagen Iteración Tiempo (ms) Ancho de banda (GB/s)

1 3,441 37,069
[Link] 2 3,483 36,599
3 3,421 36,986
Media 3,448 36,884

Vamos a resumir ésta información en los siguientes gráficos:

13
Como hemos visto, en las primeras 2 versiones, se ha reducido bastante el tiempo de
ejecución en lo que se refiere a la imagen de tamaño pequeño ([Link]) pero
empeoraba bastante en la imagen grande (Cé[Link]).

14
La diferencia la notamos cuando analizamos los resultados de la versión 3 donde se
puede apreciar una mejora importante en el tiempo y en el ancho de banda de la imagen
grande (cé[Link]). Aquí podemos notar que la memoria pinned hace un trabajo
espléndido y es una solución muy válida. El speedup se reduce un poco en imágenes
pequeñas ([Link]), pero creemos que merece la pena utilizar memoria pinned.

Y finalmente llegamos a la versión 4 que ha logrado muy buenos resultados,

consiguiendo una mejora muy notable en imágenes grandes. No obstante, podemos ver
que en imágenes pequeñas no merece la pena, ya que paralelizar la imagen en varias
tarjetas gráficas implica un overhead que no recuperamos. La implementación de
multi-GPU ha sido costosa de conseguir pero los resultados obtenidos valen mucho la
pena debido a las mejoras obtenidas.

15
Anexo
Algunas de los enlaces utilizados para algunas explicaciones sobre los histogramas y la
ecualización, como también para entender mejor el código. A parte de estos enlaces, se
han utilizado, como es de esperar, tanto los PowerPoints de teoría como las prácticas de
laboratorio:

-​ [Link]
tograma%20es%20una%20representaci%C3%B3n,distintos%20tonos%20de%20u
na%20imagen.&text=El%20eje%20vertical%20representa%20el,representado%20
en%20el%20eje%20horizontal.

-​ [Link]
en_digital.pdf?sequence=1

-​ [Link]
Histogram%20Equalization%20is%20a%20computer,intensity%20range%20of%
20the%20image.

-​ [Link]
y%20definition%2C%20the%20cumulative%20mass,function%20is%20a%20gen
eral%20one.

16