ECUALIZACIÓN DE HISTOGRAMA ADAPTIVO CON INTERPOLACIÓN

Introducción

En un blog anterior publiqué una técnica bien conocida en el campo del procesamiento de imágenes digitales para mejorar el bajo contraste que presentan algunas imágenes. Esta técnica consiste en la ecualización del histograma de las imágenes.

En este blog abordaré una expansión de la técnica anterior que se denomina: Ecualización de Histograma Adaptivo. Generalmente, esta técnica presenta una mayor carga computacional debido a que realiza el cálculo de varios histogramas locales de partes o bloques de la imagen. Entonces, para reducir la carga computacional se emplea la interpolación de los pixeles de la imagen ecualizada.

Antecedentes

Varios autores y artículos sugieren varios métodos para aplicar la ecualización de histograma adaptivo, entre los más relevantes se pueden citar los siguientes:

 1. Gonzalez, Woods, en la Pag. 161 de "Digital Image Processing" 3ra. edición, explica el procesamiento de histograma local usado para mejorar el bajo contraste de algunas zonas de una imagen que no se pueden mejorar usando la ecualización del histograma global.

Básicamente, lo que se busca es mejorar zonas o partes específicas de las imágenes que tienen bajo contraste, las cuales no pueden ser mejoradas usando la ecualización de histograma global.

Por ejemplo, se tiene la siguiente imagen que presenta sólo una pequeña parte con bajo contraste:

Suponiendo que las demás partes de la imagen tienen una distribución uniforme de intensidades de gris, entonces esta imagen probablemente tenga el siguiente histograma:

De este histograma se deriva su CDF (función de densidad acumulativa) y la transformación lineal correspondiente que probablemente sea como se muestra a continuación:

Aquí vemos con claridad que los pixeles de la zona de la imagen antigua con baja intensidad se mapean hacia la nueva imagen también con baja intensidad, no logrando ninguna mejora de contraste en esa zona. Para lograr mejorar el contraste en esa zona se usa la ecualización adaptiva.

Según el libro de gonzalez, se realiza el siguiente procedimiento para la ecualización adaptiva:

• Se selecciona una vecindad alrededor del pixel central, que se quiere ecualizar. Esta vecindad es por lo general simétrica e impar. Ej. 3x3, 7x7.
• Se calcula el histograma y su correspondiente transformación lineal de la vecindad.
• Se aplica esa transformación lineal al pixel central. Luego se efectúa estos pasos con cada uno de los pixeles de la imagen.

Lógicamente, la carga computacional aumenta mientras más grande sea la vecindad de los pixeles. para aliviar o reducir esta carga computacional se emplea la interpolación.

  

2.  En wikipedia https://en.wikipedia.org/wiki/Adaptive_histogram_equalization se plantea un procedimiento similar al descrito en el antecedente 1 (abreviado como AHE). Allí también se plantea un método de interpolación donde sólo se ecualizan ciertos pixeles y los demás son calculados a través de la interpolación.

El cálculo de los pixeles faltantes se realiza a través de 3 formas deacuerdo a la ubicación de los pixeles dentro de la imagen. En la siguiente figura se muestra dicha ubicación:

 

Fuente: https://en.wikipedia.org/wiki/Adaptive_histogram_equalization

En ls figura, los pixeles negros son calculados por medio de la ecualización adaptiva. A partir de ellos se calculan los demás pixeles de la imagen. Si un pixel está ubicado en la zona azul entonces se aplica la interpolación bilineal, si el pixel esta en la zona verde entonces se aplica la interpolación lineal, y finalmente si el pixel esta en la zona roja entonces se aplica la transformación lineal correspondiente a ese bloque o vecindad.

3. El sitio web de Sujin Philip http://www.cs.utah.edu/~sujin/courses/reports/cs6640/project2/ahe.html prueba experimentalmente la descripción del método del paper "Adaptive Histogram Equalization and its Variations" de Pizer. Allí se listan 8 pasos a seguir  para cumplir la ecualización del histograma con interpolación.

En la misma página no se describe como se realiza el cálculo de los pixeles en los bordes de la imagen, pero se asume que el procedimiento es el mismo que en el antecedente 2 (Página de Wikipedia)

Finalmente se obseva que en los cálculos efectuados en el presente experimento, el tamaño de la vecindad de pixeles es siempre mayor que el tamaño de la rejilla de los pixeles mapeados.

Procedimiento

Aquí propongo un procedimiento alternativo para calcular la imagen ecualizada usando interpolación.  Este método evita el cálculo de los pixeles interpolados en los bordes o esquinas  de la imagen ecualizada.

Este proceso se realiza  desfasando la rejilla de los antecedentes 2 y 3, de tal manera que el centro de la rejilla superior derecha (primer centro) coincida con el primer pixel de la imagen. En la siguiente gráfica se observa lo descrito:

En la anterior figura se observa que los pixeles calculados con interpolación bilineal son los de la parte de color magenta. Una vez que se interpolan todos los pixeles de la zona se pasa a la siguiente zona con los 4 pixeles más cercanos y asi sucesivamente hasta completar toda la imagen.

Es importante notar que en los casos que el tamaño de la imagen no sea múltiplo del tamaño de la rejilla se tendrán que aumentar  pixeles adicionales en las partes inferior y derecha de la imagen para que se puedan calcular todos los pixeles interpolados.

Este método permite usar un sólo algoritmo para todos los bloques similares al bloque de color magenta de la figura; a diferencia que el metodo de Wikipedia y del paper de Pizer, donde se requiere implementar 3 algoritmos (2 para los pixeles de los bordes y uno para los pixeles centrales).

La fórmula de la interpolación bilineal empleada la tomé de la siguiente página: http://www.ajdesigner.com/phpinterpolation/bilinear_interpolation_equation.php, donde también se pueden encontrar muchas otras fórmulas útiles.

Donde:

P:          Es el valor del pixel calculado por interpolación.
Qij:       Son los valores de píxeles ecualizados (4 extremos más cercanos).
xi e yi:  Son las coordenadas de los 4 pixeles extremos más cercanos.
x e y:    Es la coordenada del futuro pixel interpolado.

Algoritmo

El algoritmo (desarrollado en MATLAB) es el siguiente:

% Calculo de los pixeles interpolados steps=3;       %tamaño de la rejilla x1=1; x2=steps+1; y1=1; y2=steps+1; %constantes de la ecuacion de interpolacion I_end=[];   I_lin=[]; for X=1:steps:Filas     for Y=1:steps:Columnas                Q = Y_ecu_less(X:X+steps,Y:Y+steps); %selección del enésimo bloque         for xn = 1:steps             for yn = 1:steps                 if xn == 1 && yn == 1                     %el primer pixel del bloque es compensado x S^2                     %Como es el pixel ecualizado se mantiene inalterado                     P(xn,yn)=Q(1,1)*steps^2;                 else                     %formula de interpolacion para los demas pixeles del bloque                     P(xn,yn)=(x2-xn)*(y2-yn)*Q(1,1)+(xn-x1)*(y2-yn)*Q(end,1)...                         +(x2-xn)*(yn-y1)*Q(1,end)+(xn-x1)*(yn-y1)*Q(end,end);                 end             end         end         P = P/steps^2;      %completamos la formula en el bloque calculado         I_lin=[I_lin P];    %ordenamos los bloques en un vector fila     end     I_end=[I_end; I_lin];   %apilamos las filas en una columna     I_lin=[];               %borramos la linea pasada end % recorte del final de la imagen I_end=I_end(1:end-dx+1,1:end-dy+1); figure imshow(uint8(I_end));

Aquí solo se describe el algoritmo de interpolación, para obtener el algorimo completo de ecualización adaptiva mas interpolación, veamos la anterior entrada del blog: Ecualización de imágenes.

 Los pasos del algoritmo son los siguientes:

1. Se recorre a la imagen por cada uno de los pixeles ecualizados.
2. En cada pixel ecualizado se escoge el bloque correspondiente a los 3 pixeles más cercanos al pixel ecualizado.
3. Se interpolan los valores de los pixeles que pertenecen al bloque.
4. Cada bloque interpolado se ordena en un vector fila.
5. Cada vector fila se ordena, uno debajo del otro, en una matriz bidimensional que será la imagen con los valores interpolados.

Resultados

Se comparan dos variables cuando se obtienen las imágenes ecualizadas: el tiempo de ejecución y la calidad subjetiva de las imágenes.

Imagen 1 (Auto deportivo)

Ecualización sin interpolación
window = 33
time = 49.2 seg

Ecualización usando interpolación
window = 33
grid = 2
time = 13.4 seg

window = 33
grid = 3
time = 6.2 seg

window = 33
grid = 4
time = 4.0  seg

Imagen 2 (People)

Ecualización sin interpolación
window = 33
time = 80.8 seg

Ecualización usando interpolación
window = 33
grid = 2
time = 21.2 seg

window = 33
grid = 3
time = 10.0 seg

window = 33
grid = 4
time = 6.02 seg

Conclusiones

•  Como era de esperarse, se observa una reducción significativa en el tiempo cuando se emplea la interpolación. Sin embargo, también se observa una pequeña degradación en la calidad de las imágenes cuando se incrementa la rejilla de interpolación (ver imágenes).

• En ambas imágenes, la reducción del tiempo de procesamiento cuando se pasa de ecualización sin interpolación a ecualización con interpolación (rejilla = 2) es de 72% a 73 %. Reducciones de tiempo menos considerables se registran cunado la rejilla aumenta de tamaño a 3 ó 4. Por lo tanto el método descrito aquí funciona bien para rejillas de interpolación pequeñas (de orden 2 ó 3).

Referencias

1. S. M. Pizer, E. P. Amburn, J. D. Austin, et al.: Adaptive Histogram Equalization and Its Variations. Computer Vision, Graphics, and Image Processing 39 (1987) 355-368.
2. Digital Image Processing 3rd Edition  by Rafael C. Gonzalez, Richard E. Woods p. 161-162.
3. https://en.wikipedia.org/wiki/Adaptive_histogram_equalization
4. http://www.cs.utah.edu/~sujin/courses/reports/cs6640/project2/ahe.html