Proyecto 2 - Descriptores de Color PDF

Preview

Summary

Download Proyecto 2 - Descriptores de Color PDF

Description

SISTEMA DE INDEXACIÓN DE IMAGEN CON DESCRIPTORES DEL ESTÁNDAR MPEG-7 Atenea Gamarra y Javier de la Rica Universidad Politécnica de Cataluña, Barcelona

RESUMEN El objetivo del proyecto es plantear las bases para crear un sistema de recuperación y/o identificación de un conjunto de imágenes similares dada una imagen en concreto (o un conjunto de imágenes). Para ello se sigue un criterio de similitud a partir de una base de datos de 2000 imágenes, en este caso, para posteriormente implementar dicho sistema. El criterio que se utilizará durante la realización de dicho programa será en función del tiempo de ejecución, el número de descriptores y la calidad de los resultados obtenidos, mejorándolos dentro de lo posible.

1. INTRODUCCIÓN El estándar ISO/IEC MPEG-7 consiste en una representación estándar de la información audiovisual que posibilita la descripción del contenido multimedia. Éste fue creado con el objetivo principal de llevar a cabo una gestión de los contenidos audiovisuales mediante distintas herramientas, que posibilitan una descripción deparada de los contenidos pero que guarda relación con ésta. La parte del estándar que interesa para llevar a cabo el sistema propuesto es el que describe imágenes fijas mediante descriptores perceptuales. El objetivo del sistema propuesto es implementar una mejora de las prestaciones del sistema descrito como el algoritmo de procesado de imágenes en niveles de gris, mediante el uso de algún descriptor del estándar MPEG-7. El color es una característica visual importante tanto para la visión humana como para el procesado computacional. La extracción de los descriptores y su uso en el estudio de similitud de imágenes están fuera del alcance de los componentes de la normativa del estándar. Aun así, una extracción eficiente y las correlaciones son técnicas indispensables para un sistema práctico. Éstos descriptores son característicos debido a varios factores. Las características más importantes son, por ejemplo, su habilidad para caracterizar la similitud de color perceptual, su baja complejidad de las técnicas de extracción y correlaciones asociadas, el tamaño de las descripciones codificadas, que desempeñan un papel importante en la indexación y transmisión de los descriptores a través de redes con ancho de banda limitado, y su escalabilidad e interoperabilidad. En concreto se van a estudiar un total de cuatro descriptores con el objetivo de poder compararlos entre ellos y poder escoger uno. Primeramente se hará un paso intermedio entre los histogramas de niveles de gris y los descriptores como pueden ser los histogramas de color en el espacio RGB, con el objetivo de observar el resultado y compararlo con el resultado obtenido mediante los descriptores, pudiendo ver así la diferencia entre una metodología y otra y la necesidad y mejora de los descriptores de color. Por un lado se estudiará el Color Structure Descriptor (CSD), basado en histogramas de colores y de estructura con el objetivo de identificar distribuciones de color localizadas mediante un elemento estructurante pequeño.

Seguidamente se estudiará también el Color Layout Descriptor, que captura la disposición espacial de la representación de colores en una cuadrícula superpuesta sobre una región o imagen. Su representación se basa en los coeficientes de la transformada discreta del coseno (DCT). Aun con todo esto, es necesario hacer una breve introducción a los espacios de color, ya que algunos de los descriptores utilizados hacen uso de un cambio de espacio. En este sentido se podrá observar el espacio de color RGB, el espacio de color HSV y el espacio de color HMMD.

2. ESPACIOS DE COLOR Para llevar a cabo el sistema en mente se debe hacer una breve introducción a los espacios de color, ya que la selección del espacio de color variará según el descriptor que se desee implementar. El espacio de color se define como un modelo de representación del color con respecto a los valores de intensidad. La dimensionalidad del espacio de color puede estar comprendida entre una hasta cuatro dimensiones, siendo los espacios más representativos y utilizados los formados por tres componentes o canales de color. Los espacios de color especificados en el estándar MPEG-7 y por tanto los utilizados en el presente proyecto son el RGB (Red, Green, Blue), YCbCr, HSV (Hue, Saturation, Value) y el HMMD (Hue, Max, Min, Diff).

2.1. Espacio de color RGB El primer método seleccionado para el sistema es el análisis del sistema sin ningún descriptor. En su lugar, se ha decidido evaluar el sistema únicamente con los histogramas de color en el espacio de color RGB. El histograma de color representa la frecuencia de aparición de una de las intensidades de color presentes en la imagen mediante la contabilidad de los píxeles que comparten dichos valores de intensidad de color. Éste histograma está compuesto por distintos rangos que representan un valor, o conjuntos de valores de intensidad de color. Éste espacio de color se define por un cubo, formado por los colores primarios Rojo, Verde y Azul con valores entre [0, 1], y cuya mezcla proporcionada resulta en el color deseado. El sistema RGB utiliza las coordenadas cartesianas, teniendo en consideración que la diagonal formada por los vértices (0,0,0) negro y (1,1,1) blanco, representa la escala de grises.

Figura 2.1. Representación del espacio de color RGB.

2.2. Espacio de color HSV El espacio de color HSV se define por un cilindro y consiste en los valores Hue, Saturation y Value. Hue se representa con el ángulo de 0 a 360º especificando una familia de color u otra. Por otro lado, Saturation especifica cuan puro un color es, y finalmente Value especifica cuan brillante u oscuro es el color.

Figura 2.2. Representación del espacio de color HSV.

Éste espacio de color está asociado con los descriptores Scalable Color Descriptor (SCD) y Group of Frames Histogram Descriptor. Para dichos descriptores, el espacio HSV es uniformemente cuantificado en 256 bins y 16 niveles para H(Hue).

Tabla 2.1. Tabla de partición uniforme del espacio de color HSV para los diferentes coeficientes ss.

2.3. Espacio de color HMMD El espacio de color HMMD es más cercano perceptualmente a un color uniforme. Éste espacio se limita mediante un doble cono con los componentes Max, Min, Diff y Sum. Como se puede observar en la Figura 2.2, por un lado el valor de Hue es como en el espacio HSV, identificando la familia de color. Por otro lado, el valor Max especifica la cantidad de negro presente. De forma parecida el valor de Min especifica la cantidad de blanco presente. Finalmente, el valor de Diff especifica la proximidad de un color dado a un color puro, mientras que el valor de Sum especifica el brillo del color.

Figura 2.2.Representación del espacio de color HMMD mediante un doble cono.

De manera contraria al espacio de color HSV, el presente espacio de color descrite una cuantificación no uniforme, de manera que cada cuantificación se define mediante cinco subespacios dividiendo el intervalo del eje Diff de [0, 255] de la manera siguiente: [0, 6), [6, 20), [20, 60), [60, 110), [110, 255). Paralelamente, se lleva a cabo una segmentación de los rangos Hue y Sum en intervalos uniformes tal y como se especifica en la siguiente tabla:

Tabla 2.2. Cuantificación del subespacio HMMD para cada una de las cuatro particiones del espacio.

3. SISTEMA Como se ha mencionado anteriormente, el sistema se ha implementado el mismo sistema mediante distintos descriptores de color. Primeramente se estudiará el descriptor Color Structure Descriptor (CSD), siguiéndolo del Color Layout Descriptor (CLD) […]. Todos los sistemas, independientemente del descriptor utilizado, se basan en cuatro algoritmos. El primer algoritmo se encarga de calcular las características necesarias dependiendo del descriptor escogido, devolviendo entre otras cosas las imágenes en el espacio de color correspondiente, de ser necesario. A continuación, el segundo algoritmo se encarga de medir la similitud entre las imágenes correspondientes. En éste segundo algoritmo se ha decidido utilizar como método de diferenciación el Mean Absolute Error, ya que el en sistema anterior con los histogramas de niveles de gris fue con el que mejores resultados se obtuvieron. Finalmente el tercer algoritmo devuelve una lista ordenada de las imágenes más similares a la lista de imágenes propuesta por el usuario. Por defecto, el número de imágenes que aparecen en la lista de cada imagen query es 10, aunque éste valor se puede cambiar por cualquier otro valor deseado. El último algoritmo se utilizará para evaluar el sistema mediante la curva de Precision y Recall y poder así comparar los sistemas implementados con los descriptores de color propuestos.

3.1. Sistema con histogramas de color RGB Este sistema se implementa con el propósito de encontrar un punto intermedio entre el sistema de histogramas de niveles gris utilizado en la primera parte de este proyecto y los sistemas de indexación de imagen con descriptores del estándar MPEG-7 propuesto, con el objetivo de comprobar la necesidad de uso de éstos.

3.1.1.

Algoritmo 1. Cálculo de los histogramas de color

El primer sistema se basa en un algoritmo que calcula el histograma de cada una de las imágenes de la base de datos. Para cada una de las imágenes de la base de datos se calcula tres histogramas, cada uno correspondiente a los colores primarios del espacio de color RGB, y se guarda en una matriz de MxN, donde N es el número de imágenes de la base de datos, es decir 2000, y M el número de filas. En este caso, son necesarias dos filas, ya que en una se guarda el nombre de la imagen y en la segunda el histograma correspondiente. Como se ha mencionado, el primer paso es calcular los histogramas R, G y B para cada una de las imágenes, para posteriormente sumarlos en un único histograma RGB.

Figura 3.1. Histogramas de color R, G y B respectivamente de la imagen original.

3.1.2.

Algoritmo 2. Cálculo similitud entre dos histogramas.

El segundo algoritmo se debe encargar de medir la similitud entre los histogramas de color de dos imágenes. Se deben leer en un primer momento las imágenes introducidas en un fichero de texto input.txt en formato ‘.jpg’. Seguidamente se almacena la información de cada imagen y se realiza dicha comaparación con el Mean Absolute Error (MAE).

(3.1)

Por otra parte, los histogramas R, G y B correspondientes a cada una de las imágenes, se juntan en un mismo histograma para obtener un promediado en el que queda la diferencia de cada una de las componentes representada.

Figura 3.2. Histograma RGB de la imagen original (Promedio de los tres histogramas R, G y B).

3.1.3.

Algoritmo 3. Comparación histograma imagen dada con base de datos.

El presente algoritmo debe calcular el histograma de cada imagen query del fichero de entrada, escogidas por el propio usuario, y medir la similitud entre el histograma correspondiente de cada imagen y los histogramas de la base de datos completa empleando el algoritmo anterior. Éste algoritmo devuelve en la salida una lista ordenada guardada en un fichero output.txt de las imágenes más similares a la lista de imágenes propuesta por el usuario. Por defecto, el número de imágenes que aparecen en la lista de cada imagen query es 10. Aun así, éste valor puede ser cambiado en el código por cualquier otro valor deseado.

3.2. Color Structure Descriptor (CSD) El Color Structure Descriptor se basa en un histograma de color modificado para tener en cuenta la distribución de cada color cuantificado dentro de las imágenes, capturando así tanto el contenido de color como la información sobre la estructura del contenido. Al contrario que el histograma de color, el presente descriptor puede distinguir entre dos imágenes en las que se presenta la misma cantidad de un color determinado pero las estructuras de los grupos de píxeles con el color correspondiente es diferente en ambas imágenes. El primer paso que se debe llevar a cabo es transformar el espacio de color RGB de las imágenes originales al espacio de color HMMD. Para ello será necesario pasar primero las imágenes al espacio de color HSV, ya que como se ha mencionado anteriormente, el espacio de color HMMD no deja de ser una extensión del HSV. Para este primer paso se ha implementado la función rgb2hmmd.m en Matlab, al que se le pasa la imagen de entrada en el espacio de color RGB y devuelve la misma imagen en HMMD. El código y la explicación más detallada de la función implementada se puede observar posteriormente en el anexo. A continuación, se procede a cuantificar las imágenes mediante una cuantificación no uniforme en el espacio HMMD. Como se ha mencionado anteriormente, el espacio HMMD se puede definir en tres dimensiones usando las variables Sum, Diff y Hue. Se realizan un total de cuatro cuantificaciones no uniformes definidas por el estándar MPEG7 partiendo el espacio en 256, 128, 64 y 32 respectivamente. Cada cuantificación se define mediante cinco subespacios. Por ejemplo, para un intervalo de [0, 255] se separa en los cinco subintervalos siguientes: [0,6), [6,20), [20,60) [60,110), [110, 255). De esta forma se obtiene una partición del espacio HMMD partiendo los rangos de Hue y Sum en intervalos uniformes, que se pueden observar en la Tabla 2.2. Mediante dicho algoritmo se va creando un mapa de color que posteriormente servirá para extraer las características El siguiente paso se basa en la extracción de características de color y posición mediante un elemento estructurante. Ésta información adicional sobre la estructura del color le caracteriza como un descriptor sensible a ciertas características de la imagen, en especial aquellas a las que el histograma de color, sin dicha información de estructura, no llega a caracterizar. La extracción de características para formar dicho histograma se basa en el deslizar píxel a píxel un elemento estructurante pequeño, de 4x4 o 8x8 píxeles, por cada una de las imágenes de la base de datos. Éste recorrido por los píxeles de cada imagen es complejo y lento, ya que tiene que extraer las características de cada uno de los píxeles para todas las imágenes de la base de datos.

En la Figura 3.3 se puede observar un ejemplo de un elemento estructurante de 4x4 deslizándose por la imagen correspondiente, y la extracción de las características tanto de color como de estructura por acumulación de valores. En cada posición, el histograma de estructura se actualiza en base a los colores presentes en el elemento estructurante. En la posición actual de la figura, se presentan cuatro colores en el elemento estructurante. Así pues, cada uno de los cuatro correspondientes bins del histograma de estructura se incrementa una unidad. En general, para cualquier posición, el incremento en el histograma de estructura va en función del color presente en el elemento estructurante, así que el valor final del histograma queda determinado por el número de posiciones en los que el elemento estructurante contiene el color.

Figura 3.3. Acumulación del histograma de estructura. El algoritmo de este desplazamiento y acumulación, y por tanto generación del histograma de estructura se ha realizado en una función llamada extract_csd.m. Un estudio sobre la función se puede encontrar posteriormente en el apartado correspondiente del anexo.

3.3. Color Layout Descriptor (CLD) El descriptor Color Layout Descriptor fue diseñado para capturar la distribución espacial del color en una imagen. La representación se basa en los coeficientes de la Transformada Discreta del Coseno (DCT) sobre los valores de las componentes Y, Cb y Cr de la imagen. Esta representación se caracteriza por presentar una resolución invariante respecto del tamaño de la imagen y al mismo tiempo muy compacta. La creación del descriptor se lleva a cabo mediante un proceso dividido en las cuatro etapas que se pueden observar a continuación: División de la imagen: En la primera etapa se debe dividir la imagen original mediante una rejilla en diferentes bloques o regiones. En concreto, se divide la imagen en 64 bloques para garantizar la invariabilidad de la resolución o su escalado. En este sentido, en la entrada se tiene una imagen MxN, y en la salida de la etapa se debe obtener una imagen dividida en 64 bloques M/8xN/8. Ésta división se ha llevado a cabo mediante una función llamada partition.m que se puede observar en el anexo.

Figura 3.4. División de una imagen de entrada en 64 bloques (8x8). Selección del color más representativo: Para cada uno de los bloques de la cuadrícula anterior se selecciona un único color como representante de cada bloque. Aunque para ésta estapa se puede utilizar cualquier método para seleccionar dicho color más representativo, el estándar recomienda el uso de la media de los colores de los píxeles en un mismo bloque, ya que es el proceso más simple y se obtiene una exactitud suficiente de la descripción. Los resultados se guardan en una imagen de 8x8, teniendo así una imagen en la entrada de la etapa de M/8xN/8 y una imagen 8x8 en la salida. Este paso se realiza en una función matlab llamada color_selection.m. Se puede observar la explicación de dicha función en el anexo. Transformada DCT: Una vez se obtiene el icono de la imagen se procede a efectuar la Transformada Discreta del Coseno – tras una transformación al espacio de color YCbCr formado por la luminancia Y, y la crominancia azul y roja Cb y Cr respectiamen te– de cada una de las componentes de color, obteniendo así los coeficientes de la DCT en tres grupos de 64 coeficientes. Para el cálculo de los coeficientes de la DCT de una matriz 2D se hace uso de la siguiente fórmula:

(3.1)

Donde (i,j) denotan las coordenadas de la matriz de color, (u,v) representan las coordenadas en el dominio transformado y Aij hace referencia a la intensidad del píxel en la posición ( i,j) de la matriz de entrada. Exploración en zigzag: En esta cuarta y última etapa se realiza una exploración en zigzag de los coeficientes de la DCT de las tres componentes YCbCr obtenidos en la etapa anterior tras haber realizado una cuantificación previa de los mismos. El motivo de este trazado tiene que ver con la ubicación de las componentes de baja frecuencia de la imagen, localizadas en la parte superior izquierda de la matriz transformada, lo que significa que la energía de la imagen se concentra en dicha localización. La manera de proceder con respecto al seguimiento del trazado se puede observar en la Figura 3.algo, cuyo comienzo se sitúa en la parte superior izquierda de la matriz, para terminar en la diagonal opuesta. El descriptor Color Layout Descriptor se compone por lo tanto de tres vectores de características que contienen los diferentes coeficientes de luminancia y crominancia representados según el orden del recorrido en zigzag.

Figura 3.5. Recorrido en zigzag de una matriz NxN.

Figura 3.6. Diagrama de bloques del algoritmo completo del CLD. La función correspondiente al análisis en zigzag se describe en el anexo como una función llamada zigzag.m.

La comparación entre descriptores tiene como objetivo evaluar el grado de similitud entre dos imágenes mediante el cálculo de la distancia entre ellos. En el presente descriptor, la función de comparación es una suma ponderada de diferencias cuadráticas entre las componentes de ambos descriptores, representada por la siguiente fórmula:

(3.2) Donde (i,j,k) representan los coeficientes de las diferentes componentes ( Y,Cb,Cr) respectivamente, y ωiY, ωjCb, ωkCr son los pesos elegidos para establecer las contribuciones de cada componente en la métrica. Estos valores pueden variar dependiendo del rendimiento en el proceso de comparación o de la importancia que se quiera dar a una u otra componente.

3.4. Scalable Color Descriptor (SCD) El descriptor Scalable Color Descriptor representa los colores que hay en la imagen mediante un histograma de color HSV (explicado anteriormente el punto 2.2.) codificado mediante un...