Universidad
publicado en noviembre 2006
clasificación automática de fotografías

Proyecto de Taller de Mineria de Datos


El proyecto permite realizar una primera aproximación al uso de un software de minería de datos. Para ello, se abordará el problema de clasificar imágenes, a partir de información estadística sobre sus colores.



Introducción:

El presente proyecto corresponde a la realización de un proyecto de data-mining, que busca tener una primera experiencia práctica en el uso de herramientas de minado de datos. Para ello, se trabajará utilizando la herramienta Weka, un software hecho en Java, de licencia open source. El problema a abordar, consiste en estudiar la factibilidad de realizar un clasificador de imágenes (fotografías), a partir de información extraída de cada una de éstas, tratando de clasificar cada imagen en una de cuatro categorías pre definidas. Se compararán algoritmos de clasificicación, y se expondrán los resultados al final del trabajo.


Problema: (business understanding)

En la actualidad, el manejo de imágenes se ha hecho cada vez más masivo, a partir de la popularización de los medios fotográficos (cámaras digitales), así como de la difusión de éstas a través de internet. La cantidad de imágenes que existen disponibles, cada día crece más, y surge la necesidad de encontrar formas de extraer algún tipo de semántica, más alla del sólo uso de metadatos (la solución más utilizada hoy en día).

Lo que se quisiera tener, es un medio de catalogar imágenes, lo que permitiría poder realizar agrupaciones, clasificaciones de éstas, para poder realizar mejores búsquedas, tanto en sitios web, como en repositorios privados (por ejemplo, una colección particular de imágenes de algun usuario).

Si bien esta meta podría ser un tanto ambiciosa, se quiere realizar una primera aproximación al problema. Para ello, se propone la siguiente idea: cada imagen será transformada a un conjunto de atributos, extraídos de la información de los colores que la componen. En particular, se utilizará información estadística acerca de las cuatro componentes de color del colorspace CMYK, ampliamente utilizado en la impresión de imágenes.


Herramientas disponibles

Se desea utilizar una herramienta de minería de datos, para realizar el estudio de las imágenes. Entre las opciones disponibles, se revisaron diversas alternativas en el campo del software open source. Entre los programas disponibles, se pueden mencionar los siguientes:
  • Gnome-data-mining
  • Knime
  • Weka Siute de algoritmos de aprendizaje, implementado en Java, desarrollada por la universidad de Waikato.

  • Pentaho Software de BI, el cual recientemente ha adquirido a Weka como base para los algoritmos utilizados.
  • Yale Framework de minería de datos, el cual utiliza los algoritmos de Weka, a través de una interfaz para el análisis.

    De estas alternativas, se ha seleccionado el software Weka, dado que es quizás la más completa de las opciones, sin caer en la complejidad de Pentaho o Yale. La interfaz que provee es suficiente para los propósitos del proyecto a desarrollar. Además, es el software con mejor documentación disponible en la red. Entre sus principales características, se puede mencionar: - gran cantidad de algoritmos de aprendizaje, herramientas de preprocesado y métodos de evaluación. - interfaces gráficas para la realización de análisis y experimentos. - ambiente para la comparación de algoritmos.

    Además de la herramienta de minado de datos, se recurrirá al lenguaje Perl, y al programa ImageMagick (de linux), dedicada al procesamiento avanzado de imágenes, utilizando linea de comandos. Estas serán las herramientas que se usarán para el pre-procesado de los datos (las fotografías).


    Datos disponibles (data understanding)

    Para realizar la experiencia, se dispuso de una colección de 200 fotografías (parte de la colección personal del autor), las cuales fueron separadas en cuatro grupos, según las categorías definidas para el experimento: {nocturnas, urbanas, gente, paisajes}. Las imágenes fueron elegidas de manera que fueran lo más representativas posibles de cada una de sus categorías. El propósito es que el modelo logre capturar el concepto de la clasificación automática, tratando de emular la metodología utilizada por las personas.

    La 'ídea'' es la siguiente: cada categoría debiera presentar ciertas dominantes de color, o intensidad de color (incluído el negro). Según una primera aproximación, se podría esperar lo siguiente:

    - nocturnas: dominante negra, con partes claramente amarillas (provenientes de fuentes lumínicas de tungsteno). - urbanas: en general, luminosas, con presencia mayoritaria de color gris. - gente: presencia de color ''piel'', además de menor luminosidad, ya que las fotografías son en general más ''cerradas''. - paisajes: fotografías luminosas, con gran parte de la imagen en azul/celeste (el cielo), y muchas veces, verde.

    Las colecciones de imágenes utilizadas, fueron las siguientes:")
  • nocturnas
  • urbanas
  • gente
  • paisajes


    Pre-procesamiento de los datos: reducción dimensional (data preparation)

    El problema de análisis de imágenes, presenta un primer gran problema: cada instancia (imagen) corresponde, en teoría, a un vector de 3*n componentes, con n el número de pixels de la imagen (esto para el caso de una imagen de 24 bits, en el modelo clásico RGB de representación de imágenes en formato digital). Claramente, realizar la tarea de clasificación sobre vectores de esta dimensión, es un problema irrealizable en la práctica.

    La solución que existe para estos casos, es la de aplicar una reducción dimensional, es decir, proyectar cada ejemplar de la entrada (la señal de entrada), en un espacio de menor dimensionalidad. Para esto, existen básicamente dos alternativas: selección de características o extracción de características. El primero caso, corresponde a elegir algunas de las componentes del vector de entrada. Sin embargo, este caso no es aplicable, ya que la dimensión seguiría siendo inmanejable. La segunda opción, es la que será utilizada en este caso, para lo cual se recurrirá a indicadores estadísticos de cada imagen.

    El espacio de color de una imagen, corresponde al modelo utilizado en su representación: RGB, CMYK, HSV, entre otros. Una primera aproximación sería utilizar el espacio RGB (el colorspace natural en dispositivos digitales: {red, green, blue}). Sin embargo, se elegirá realizar una transformación de las imágenes, al espacio CMYK {cyan, magenta, yellow, black}. El motivo de esta elección se basa en la posibilidad de contar con al componente negro de manera explícita, lo cual permitirá entender de mejor manera los patrones de las imágenes.

    Esta transformación se realizará utilizando un programa en perl, que realizará la transformación del espacio de color. A continuación, el mismo programa obtendrá el conjunto de datos a utilizar, a través de la aplicación ImageMagick (identify), la cual permite extraer la información que será utilizada. Finalmente, se obtendrá para cada archivo de imagen, los siguientes valores: - componente C (cyan) : media y desviación standard - componente M (magenta) : media y desviación standard - componente Y (yellow) : media y desviación standard - componente K (black) : media y desviación standard

    Esto arrojará un vector de 8 componentes, lo cual corresponderá a la reducción dimensional buscada.

    El programa de preprocesamiento, será ejecutado por separado para cada uno de los cuatro grupos de imágenes (en directorios diferentes). De esta manera, se agregará en cada caso la clase a la cual pertenece cada imagen. Finalmente, se dispondrá de cuatro archivos de texto con el siguiente formato:
        {c-mean, c-sd, m-mean, m-sd, y-mean, y-sd, k-mean, k-sd, clase}
        200.36,56.4659,216.558,43.2201,230.792,33.534,199.839,56.1583,nocturna
        167.537,19.3646,163.186,19.3659,161.588,22.5161,155.203,21.8438,gente
        100.051,75.8246,93.5235,69.124,109.475,86.9608,90.9557,69.4633,paisaje
    
    Estos archivos serán combinados, para producir finalmente un conjunto de datos (parcialmente mezclados), que constuirán la entrada al sistema (un archivo de tipo arff, de Weka).

    El archivo de entrada, finalmente utilizado, fue el siguiente:

    fotos.arff


    Implementación del modelo: Weka (modeling)

    A continuación, se mostrará el proceso seguido para implementar diversos modelos de clasificación, utilizando el software elegido.

    Dentro de las opciones principales del software, están el Experimenter (enfocado a análisis estadístico de grandes conjuntos de datos), el KnowledgeFlow (una herramienta fundamentalmente gráfica, para construir esquemas de experimentación usando la GUI provista), y el Explorer. Esta última es la opción elegida, por que se adecua perfectamente a las necesidades del proyecto: cargar un archivo de datos, y desarrollar alguna de las tareas disponibles, utilizando uno de varios algoritmos.



    Las tareas disponibles en el sistema, son las siguientes:

    - preprocesado Permite aplicar filtros a los datos de entrada, realizar discretización, normalizar datos, etc. - clasificación Utilizando un clasificador, se puede realizar una clasificación de las instancias del conjunto de entrada. - clustering La tarea de clasificación no supervisada sobre conjuntos de datos. - asociación Para encontrar asociaciones entre atributos. - selección de atributos El proceso de selección de atributos utilizado para encontrar aquellos campos de mayor preponderancia en la elección de categorías. - visualización de datos Muestra gráficos en dos dimensiones, para cada combinación de pares de atributos.

    La tarea a abordar es la de clasificación. Para ello, en primer lugar se hará la carga de datos a través de un archivo .arff definido previamente (generado por el programa en perl mencionado anteriormente). Esta archivo se compone de 200 registros, divididos en cuatro grupos de 50 elementos. Los datos fueron mezclados para evitar cualquier partición desafortunada al momento de dividir los conjuntos de datos. Una vez cargados los datos, se tiene la siguiente pantalla:

    La siguiente etapa, es seleccionar los algoritmos de clasificación a utilizar. Se elegirá un algoritmo de cada una de tres familias distintas disponibles en el software: Redes Bayesianas, MultilayerPerceptron y el Arbol de Decision J48.

    Redes Bayesianas: El primer conjunto de algoritmos corresponde a los algoritmos que utilizan el principio de Bayes. Entre éstos, se eligió el uso de una Red Bayesiana para realizar la clasificación, utilizando un estimador simple (el utilizado para construir la tabla de probabilidad condicional), y un algoritmo de búsqueda local K2.



    Red Neuronal: Dentro de las funciones matemáticas disponibles, se eligió utilizar una red neuronal basada en el perceptrón multicapa. Se utilizó el modelo básico propuesto por el software, con un número de neuronas en la capa oculta igual a (nro.atributos/nro.classes)/2 = (8+4)/2 = 6. Lo que se tiene entonces, es una red con la siguiente representación.



    Arbol de Decisión: Dentro de los algoritmos que aprenden utilizando árboles de decisión, se eligió el algoritmo clásico de aprendizaje, llamado J48. Una representación de éste es la siguiente (después de ejecutado el modelo):



    Una vez elegido el algoritmo a utilizar, se debe seleccionar el modo de entrenamiento: básicamente, se trata de determinar la forma en que se distribuirán los conjuntos de aprendizaje y de testing. El método elegido, fué el de validación cruzada, utilizando un número de particiones de 10 (la validación cruzada consiste en: dado un número n se divide los datos en n partes y por cada parte, se construye el clasificador con las n-1 partes restantes y se prueba con esa).. esto para cada una de las n particiones.


    Resultados

    Una vez implementados los diferentes modelos, se obtuvieron los resultados de su ejecución.



    Redes Bayesianas:
    === Classifier model (full training set) ===
    Bayes Network Classifier
    not using ADTree
    

    Time taken to build model: 0.02 seconds

    === Stratified cross-validation === Correctly Classified Instances 124 62 % Incorrectly Classified Instances 76 38 %

    === Detailed Accuracy By Class ===

    Precision Class 0.553 paisaje 0.386 urbana 0.98 nocturna 0.578 gente

    === Confusion Matrix ===
    abcd<-- classified as
    261905| a = paisaje
    1422014| b = urbana
    00500| c = nocturna
    716126| d = gente

    Red Neuronal:
    === Classifier model (full training set) ===
    

    Time taken to build model: 11.03 seconds

    === Stratified cross-validation === Correctly Classified Instances 149 74.5 % Incorrectly Classified Instances 51 25.5 %

    === Detailed Accuracy By Class ===

    Precision Class 0.619 paisaje 0.629 urbana 0.98 nocturna 0.75 gente

    === Confusion Matrix ===
    abcd<-- classified as
    39902| a = paisaje
    1822010| b = urbana
    00491| c = nocturna
    64139| d = gente

    Arbol de Decisión:
    === Classifier model (full training set) ===
    J48 pruned tree
    

    Number of Leaves : 22 Size of the tree : 43

    Time taken to build model: 0.08 seconds

    === Stratified cross-validation === Correctly Classified Instances 130 65 % Incorrectly Classified Instances 70 35 %

    === Detailed Accuracy By Class === Precision Class 0.571 paisaje 0.477 urbana 0.962 nocturna 0.564 gente

    === Confusion Matrix ===
    abcd<-- classified as
    2814 0 8 | a = paisaje
    13 21 0 16 | b = urbana
    0 0 50 0 | c = nocturna
    892 31 | d = gente




    output-bayes
    output-perceptron
    output-j48



    Conclusiones (evaluation)

    De los resultados obtenidos en la ejecución de los diferentes modelos, se analizaron algunos indicadores de la salida obtenida en cada caso. Concretamente, se utilizó como medio de comparación, los indicadores de correctitud de instancias clasificadas, el detalle de precisión de clasificación por clases, y la matriz de confusión de cada caso.

    De estas observaciones, se puede concluir que el algoritmo que mejor comportamiento tuvo, fue el de Redes Neuronales (el perceptrón multicapa), el cual arrojó un 75% de instancias correctamente clasificadas, versus un 65% y un 62% de los otros dos casos. A su vez, de la observación de la precisión por categorías, se puede comprobar un hecho esperable quizas: la categoría 'ñocturna'', es lejos la que presenta mejores índices. Esto se debería a la fuerte presencia de la componente Black en esta clase de imágenes. A su vez, el peor indicador de precisión se observó en el caso de la categoriía 'úrbana''. Esto puede ser debido a que esta clase de fotogrfías es quizás la de mayor variabilidad: se esperaba encontrar una tendencia hacia la tonalidad gris, sin embargo, los resultados demuetran que el esquema planteado (basado en CMYK) no fue suficiente para realizar la clasificación de esta categoría.

    En general, se observa que existe efectivamente una cierta correlación entre los atributos planteados y las clases propuestas. Sin embargo, el resultado sería insuficiente si se toma en cuenta que los ejemplos presentados al sistema, ya eran casos relativamente 'íntencionados''. Existe a su vez un gran conjunto de imágenes cuya clasificación resulta difusa incluso para los humanos. La idea del proyecto era al menos aproximarse a la presencia de patrones en las imágenes, a partir de los datos estadísticos de su espacio de color CMYK.

    Como alternativa, para un siguiente intento en esta dirección, sería interesante utilizar otra alternativa para la extracción de características. Por ejemplo, obtener la cantidad de puntos presentes, para cada uno de un conjunto de colores de una paleta predefinida. La tarea sería catalogar a priori, cada pixel de la imagen, asignándola a una cierta clase (color), y de esta manera, contabilizar la cantidad de color presente en la imagen, para cada componente de la paleta propuesta.


  • 0 comentarios

    no hay comentarios.



    nombre *

    e-mail *

    web

    2 x 4 = *





    Mi paso por la Universidad de Chile marca la etapa más importante de mi vida. Primero fue arquitectura en la FAU, luego fueron 8 años de ingeniería, en Beauchef: más de 60 ramos, largas horas de estudio, controles, tareas, cátedras, ayudantías... largas horas de chess en la chacra y computadores en el cec, en el dcc... Aquí he reunido algunos de los proyectos que realicé durante la carrera de ingeniería civil en computación.