Áreas

Las áreas actuales de investigación que se llevan a cabo dentro del grupo son las siguientes:

Imagen-Vídeo Digital

Imagen y vídeo digital es un área activa de investigación que atrae la atención de un número importante de grupos institucionales de investigación y departamentos de I+D de empresas y organizaciones a lo largo de todo el mundo.

El avance de las tecnologías, comunicaciones y las herramientas de difusión de contenidos ha provocado una expansión sin precedentes del uso de la imagen en nuestra actividad cotidiana. Y esta explosión en el uso que hacemos de la imagen (tanto fija como en movimiento) tiene en la web su principal vehículo de expansión.

Redes sociales, blogs, plataformas como Google Images o Youtube ponen a disposición de los usuarios herramientas que nos facilitan y a la vez fomentan su utilización. No es de extrañar que alrededor de la imagen se concentre una importantísima actividad investigadora a la búsqueda de soluciones a nuevos problemas que hace sólo unos pocos años ni siquiera nos habíamos planteado.

Es en este contexto donde GIM desarrolla su principal actividad investigadora. En esta sección encontrareis información relevante sobre esta actividad, pero antes de adentrarnos en ella, vamos a introducirnos con algo más de detalle, el contexto de nuestra actividad investigadora.

Multimedia Retrieval

¿Qué es Multimedia Information Retrieval?

La consulta de información multimedia mediante ejemplo (Multimedia Information Retrieval, MIR) es un sistema de búsqueda para recuperar información similar (vídeos, imágenes, sonido, etc.) basándose en su contenido. En el caso de que se trate de imágenes (Content-Based Image Retrieval, CBIR), las características a tratar se refieren según su contexto a colores, formas, texturas o cualquier otra información que pueda derivarse de la propia imagen.

La mayoría de las técnicas a utilizar en CBIR desde el punto de vista del procesamiento de la imagen parten del campo del Reconocimiento de Patrones y Análisis de Imagen, cuyo objetivo principal la clasificación de objetos en un número determinado de categorías o clases. Si trabajamos con vídeos (Content-Based Video Retrieval, CBVR) las técnicas pueden ser muy parecidas, incorporando además características como su movimiento, relaciones entre fotogramas, rapidez entre cambios de escenas, etc. (procesamiento de vídeo digital).

Todo ello no está reñido en absoluto con el tratamiento clásico de esta información en las bases de datos mediante metadatos (etiquetas) o información textual adicional que puede ser incorporada automáticamente (por ejemplo, fecha de la toma, características del dispositivo, parámetros de la toma, etc.) o manualmente (autor, etiquetas descriptivas del documento, etc.)

Para facilitar la recuperación de la información multimedia de forma efectiva (correcta) y eficiente (rápida) es preciso indexar los documentos. En el caso de colecciones muy voluminosas, contar con metadatos descriptivos suficientemente relevantes no resulta fácil y es aquí donde toman fuerza los sistemas automáticos de recuperación basados en el contenido, los cuales extraen -a partir del procesado del documento- información que permita caracterizarlo convenientemente. Este proceso automático se denomina extracción de características.

En este tipo de sistemas la subjetividad de la percepción humana condiciona enormemente el resultado de las consultas. De esta forma, la extracción de características automáticamente a través métodos computacionales debe tener muy en cuenta este factor humano. En ocasiones resulta bastante difícil obtener resultados similares computacionalmente y los que realmente desea el usuario. Esta discrepancia es lo que se conoce como vacío semántico. Las características computacionales no tiene ese alto contenido semántico que poseen las características preceptúales humanas. De ahí la razón de ser de los sistemas MIR.

Procesamiento MIR

Fases de procesamiento en MIR

Teniendo en cuenta una posible representación de un sistema MIR completo (figura 1), pasamos a continuación a una descripción breve de las diferentes fases, considerando como objeto patrón a una imagen, es decir como si dicho sistema fuese un CBIR.

Figura 1.- Representación de un sistema MIR

1. Imagen digital (objeto patrón): Una imagen digital es una representación bidimensional de una imagen utilizando bits (unos y ceros). Las imágenes digitales se pueden modificar mediante filtros, añadir o suprimir elementos, modificar su tamaño, etc. y almacenarse en un dispositivo de grabación de datos como por ejemplo un disco duro. La mayoría de formatos de imágenes digitales están compuestos por una cabecera que contiene atributos (dimensiones de la imagen, tipo de codificación, etc.), seguida de los datos de la imagen en sí misma. La estructura de los atributos y de los datos de la imagen es distinta en cada formato.

2. Preprocesado (opcional): En numerosas ocasiones, las imágenes digitales que sirven como punto de partida para realizar un análisis computacional, o una interpretación humana, presentan una cierta degradación en su calidad.

Por tanto es necesaria su mejora, por ejemplo mediante la eliminación de objetos indeseables dentro de la imagen, transformándola de tal forma que se mejore la eficiencia de las etapas de procesamiento posteriores (figura 2).

2.1. Procesamiento puntual o de píxel. Cuando el valor resultante sólo depende de su valor en el píxel correspondiente. Por ejemplo, el operador de transformación del contraste.

2.2. Procesamiento de grupo o filtrado local. Cuando el valor resultante depende de su vecindario. Por ejemplo, operaciones de convolución, operadores morfológicos, operadores de mediana, etc.

2.3. Procesamiento global. Cuando el valor resultante en un punto depende de una función dependiente de todos los puntos de la imagen. Por ejemplo, la transformada de Fourier, la de Wavelet, etc.

Figura 2.- Imagen preprocesada para resaltar sus bordes de la famosa foto de Lena

3. Extracción de características: Para los seres humanos la mayoría de las escenas son fáciles de interpretar y comprender, a pesar de que contienen mucha información. Para una computadora (software y hardware) las imágenes son conjuntos de píxeles.

La extracción de características es una transformación o cambio de la representación de una imagen. Normalmente del dominio espacial o frecuencial, al llamado dominio de las características que nos permitan discriminar las diferentes escenas u objetos.

4. Selección de características: Interesa seleccionar las características más importantes, reduciendo la dimensionalidad y manteniendo una alta capacidad discriminatoria.

No es rentable diseñar un sistema que requiera muchas características para poder diferenciar entre unas pocas muestras. Un sistema eficiente es el que con pocas características puede diferenciar con éxito un gran número de patrones.

5. Indexación de características: Seleccionadas las características que ayudan al sistema a diferenciar un número amplio de patrones estas características se indexan en una base de datos multidimensional (figura 3).

Indexar se refiere a la acción de registrar ordenadamente información para elaborar su índice con la finalidad de obtener resultados de forma sustancialmente más rápida y relevante al momento de realizar una búsqueda.

Una base de datos multidimensional es una estructura basada en dimensiones orientada a consultas complejas y alto rendimiento. En nuestro caso tendremos una clave o atributo de consulta por cada una de las características extraídas durante la fase de selección.

Figura 3.- Indexación multidimensional de imágenes

6. Aprendizaje (Machine Learning): Es un sistema capaz de clasificar un patrón desconocido patrón pregunta en una o varias clases preestablecidas. Estos sistemas siempre asumen que existe un conjunto de patrones muestra de los que se conoce la clase conjunto de entrenamiento que proporcionan información relevante al sistema para realizar la tarea de clasificación (figura 4).

6.1. El aprendizaje no supervisado se realiza a partir de un conjunto de patrones del que no se conoce su clase cierta. En ocasiones, ni siquiera se conoce el número de clases. Básicamente, se traduce en encontrar agrupamientos. El objetivo suele ser el de verificar la validez del conjunto de clases para una clasificación supervisada.

6.2. Un aprendizaje supervisado requiere disponer de un conjunto de patrones de los cuales se conoce su clase cierta. A este conjunto se le denomina conjunto de entrenamiento. Este tipo de entrenamiento se denomina entrenamiento supervisado y los clasificadores así obtenidos clasificadores supervisados.

Disponer de un conjunto de entrenamiento supone que alguien se ha preocupado de etiquetar los patrones de ese conjunto. Esta tarea la suele realizar un experto en el campo en el que se va a realizar el reconocimiento y generalmente viene impuesto.

Figura 4.- Búsqueda de las imágenes más parecidas a una dada

El conocimiento de los sistemas de percepción y de aprendizaje sería de gran ayuda para el diseño de sistemas computacionales que nos permitan realizar búsquedas de determinados patrones. Sin embargo, el sistema visual humano es demasiado complejo y, de momento, no existe ningún método que lo emule en su totalidad. Esto hace que los sistemas de procesamiento de información multimedia sean muy dependientes del problema a resolver.

Actividad

La actividad del grupo en MIR

Dentro de este contexto, el primer proyecto nacional del grupo (Ministerio de Educación y Ciencia) fue Imagina: Gestor de imágenes, titulado más concretamente Síntesis de Características de Medio/Alto Nivel Semático y Aplicación de Métodos de Indexación sobre Distancias en los Procesos de Búsqueda de Imágenes Basadas en Contenido (Ref. TIN2005-05939).

Fruto de este proyecto surgió el proyecto nacional (Ministerio de Ciencia e Innovación) que actualmente está en ejecución vManager: Gestor de vídeos, titulado De Qatris iManager a vManager. Estrategias para el almacenamiento y búsqueda en colecciones de documentos de video digital (Ref. TIN2008-03063). Las figuras 5, 6, 7 y 8 muestran imágenes de dichos proyectos.

Figura 5.- Logos de los proyectos Imagina (2005-2008) y vManager (2009-2011)

Figura 6.- División de un vídeo en escenas

Figura 7.- Diagrama de trabajo del proyecto vManager gestor de vídeos

Con el propósito de contribuir en este campo, nuestro grupo inició sus trabajos de investigación a finales de la década anterior, abordando proyectos de corto alcance que fueran dando sus frutos. Esto nos permitió avanzar en el conocimiento y dominio de las técnicas presentes en el área del almacenamiento y recuperación de documentos multimedia y más concretamente en colecciones de imágenes.

La madurez de los resultados obtenidos y el convencimiento de poder contribuir de manera real en el desarrollo de soluciones eficientes a la búsqueda por contenido en imágenes, nos empujó a crear en 2003 la empresa Sicubo S.L. (primera spin-off de la Universidad de Extremadura), como instrumento para facilitar la transferencia de resultados de investigación de nuestro grupo y con el objeto de explotar comercialmente los resultados derivados de nuestras investigaciones.

Otras empresas con las que colabora el grupo activamente son Dnovae Digital Media que trabaja en el campo del vídeo digital y Quota Solutions que trabaja con sistemas ERPs.

Figura 8.- Captura de pantalla de la aplicación vManager mostrando los resultados de una búsqueda por similitud

Información más detallada sobre la actividad investigadora de nuestro grupo puede encontrarse accediendo a la sección de investigación.

Resultados

Principales resultados

Como grupo perteneciente al sistema público de investigación, uno de los indicadores de nuestra actividad radica en las publicaciones. Sin embargo, además de la difusión pública del conocimiento, nuestro grupo mantiene una irrenunciable vocación práctica de transferencia de resultados, de modo que todos nuestros proyectos están sustentados por un espíritu de transferir, del modo más eficaz posible, nuestros resultados al tejido productivo. En tal sentido, las principales contribuciones del grupo se concretan en:

Qatris iManager. Aplicación CBIR de libre distribución diseñada y desarrollada en el seno del grupo de investigación GIM. Qatris iManager es una aplicación para la clasificación y búsqueda por contenido en colecciones de imágenes. La aplicación utiliza regresión logística bayesiana para clasificar automáticamente las imágenes que se añaden a la colección y facilita la búsqueda por similitud en tres espacios diferentes de color, textura y formas.

Adicionalmente permite localizar imágenes de acuerdo a un patrón de color y texturas dado por el usuario. Qatris iManager está en permanente evolución y puede ser descargado libremente para su utilización.

Qatris iCatalog

Qatris iCatalog. Aplicación comercial para facilitar la gestión documental de las empresas desarrollada por Sicubo S.L. Qatris iCatalog incorpora gran parte de los algoritmos de imagen digital desarrollados por GIM.

En particular algoritmos de extracción de características, detección de formas mediante contornos activos, indexación multidimensional, clasificación por regresión logística bayesiana, medidas de similitud semántica y otras.

Actualmente constituye la base de los paquetes Docugest y Contalink que comercializa en la actualidad SICUBO, S.L.

Además de lo anterior, un buen número de herramientas y aplicaciones experimentales están a disposición del visitante en el interior de nuestro sitio web. Las secciones de aplicaciones y descargas se mantienen permanente actualizadas con los últimos desarrollos del grupo.

Sistemas representativos

Otros sistemas representativos

En la recuperación de información multimedia, los sistemas CBIR han progresado significativamente en la primera década del siglo XXI. En esta segunda década es el turno para los sistemas CBVR de recuperación de vídeo.

Aquí dejamos una lista con ejemplos representativos de sistemas de recuperación basados en el contenido, donde el elemento central es la imagen fija. Es de esperar que esta lista comience en breve a incorporar sistemas basados en vídeo digital.

	Visual Geometry Group. División del grupo de investigación Robotics Research Group de la Universidad de Oxford cuya investigación se centra en reconocimiento visual de imágenes en movimiento como películas o series de televisión. En su página web se encuentran enlaces a sus diferentes investigaciones como: Reconocimiento de lenguajes de signos. Enlace. Reconocimiento de objetos. Enlace. Renombrar de forma automática personajes de televisión. Enlace. Errores visuales de continuidad en el cine. Enlace. Para leer otras investigaciones de este grupo pulsa aquí.
	Image, Processing & Retrieval. Trends. Interesantísimo blog del Dr. Savvas A. Chatzichristofis. Actualmente se encuentra en el Centro de Investigación y Tecnología Hellas (CE.R.T.H.). Su investigación se centra en la recuperación de imágenes, procesamiento de análisis de imágenes y reconocimiento de patrones. En su blog se encuentra dos aplicaciones: img(Rummager), esta aplicación puede ejecutar una búsqueda híbrida con la combinación de información de palabras clave y la similitud visual. img(Anaktisi), un nuevo conjunto de descriptores de función se presenta en un sistema de recuperación de imágenes. Estos descriptores han sido diseñados con especial atención a su tamaño y requisitos de almacenamiento sin comprometer su capacidad de discriminar. Estos descriptores incorporan información de color y textura en un histograma. Ambas aplicaciones han sido desarrolladas en C# y Microsoft .NET Framework 3.5, han sido desarrolladas en la Universidad Democritus de Thrace-Greece
	Tiltomo. Página web donde se prueban nuevos algoritmos de búsqueda, en base a color o textura, de imágenes. En la web tenemos la oportunidad de poder realizar consultas a su colección de imágenes. Tiene la opción de realizar consultas en base a: Búsqueda por tema (sujeto / color / textura). Búsqueda por color / textura. La colección de fotos usada son fotos de flickr, aproximadamente unas 140.000. Los algoritmos utilizados en la búsqueda son propietarios y privados.
	Idée es una compañía privada cuyo principal objetivo es el desarrollo de reconocimiento avanzado de imágenes y software de búsqueda visual. Ha desarrollado varios productos comerciales con éxito como la herramienta web TinEye. En su página web podemos encontrar dos demostraciones de lo que puede hacer su software de búsqueda de imágenes. Multicolour Search Lab, búsqueda de imágenes por color. Utiliza como colección de imágenes de flickr (10.000.000). Visual Search Lab, realiza una búsqueda de imágenes usando etiquetas con búsqueda visual. Utiliza alamy como colección de fotos.
	TinEye es un buscador de imágenes "inverso" que localiza de dónde procede una imagen, cómo se usa o si existen versiones modificadas de la misma. Utiliza las imágenes de la web como base de datos para comparar. Esta herramienta es muy útil para comprobar el origen de la imagen y si existen más versiones de esta porque esta indexando constantemente en la web (cerca de 2.000.000.000 de imágenes en su base de datos y creciendo constantemente). La forma de búsqueda es subir a su web la imagen a buscar o introducir la URL si la imagen se encuentra ya colgada en la web. Los principales navegadores tienen extensiones para utilizar TinEye de una forma mucho más sencilla. Es un software comercial y se puede usar con objetivos no lucrativos.
	xcavator.net es un buscador de imágenes profesionales. Las búsquedas son gratuitas pero si nos gusta una imagen encontrada en la web tendremos que pagarla para descargarla y usarla aunque algunas imágenes son libres. La búsqueda comienza escribiendo una o dos etiquetas, a continuación ya podemos elegir el color predominante de nuestra búsqueda o seleccionar una imagen y que se realiza otra búsqueda por similitud a esta.
	Incogna es un buscador de imágenes web, la principal diferencia con respecto a otros es que utiliza procesadores paralelos para acelerar las búsquedas. Utiliza GPU´s (Unidad de Procesamiento Gráfico) como hardware para realizar las consultas. Las consultas se pueden realizar escribiendo textualmente una o dos etiquetas o pinchando imágenes para una búsqueda de similitud.
	VIRaL es una aplicación desarrollada por el grupo de investigación IVA (Image and Video Analysis) perteneciente a la universidad de Atenas. La principal característica de VIRaL (Visual Image Retrieval and Localization) es que realiza consultas de imágenes por similitud y devuelve una estimación de la localización de la imagen. Utiliza para ello la característica de geolocalización de la imagen. Realiza búsquedas y las compara con imágenes que se encuentran en Google Maps, de esta manera puede reconocer y estimar la localización de la imagen. Esta herramienta utiliza como base de datos imágenes de flickr. Por ahora solo realiza búsquedas sobre ciudades europeas.
	ALIPR (Automatic Linguistic Indexing of Pictures Real-Time) es un sistema de indexación lingüística de imágenes en tiempo real automático. ALIPR enseña al ordenador a reconocer el contenido de las fotografías etiquetando de forma automática las imágenes. El enfoque básico ha sido tomar un gran número de fotos (60.000) para etiquetarlas manualmente con variedad de palabras clave que describen sus contenidos. A continuación se crea un modelo estadístico para enseñar al ordenador a reconocer patrones en el color y la textura de estas 100 fotos, así como para asignar esas palabras clave a nuevas fotos que puedan contener valores similares. Actualmente es capaz de etiquetar de forma automática usando 322 palabras de habla inglesa.
	imense es una empresa privada cuyo objetivo es la venta de software centrado en búsqueda de imágenes por contenido o por etiquetas. Ha desarrollado varias aplicaciones como búsqueda de imágenes (picturesearch), búsqueda por similitud (similarsearch) y autoetiquetado de imágenes (autotagger).
	imgSeek es un programa con licencia GPL y para un uso individual desde un ordenador personal. Puede buscar imágenes similares (por su contenido) a una dada o a un esbozo pintado por el usuario. También acepta búsquedas usando palabras clave. Esta herramienta utiliza la transformada de wavelet en el algoritmo de búsqueda de imágenes similares. Es similar a la transformada de Fourier, pero codifica la frecuencia y la información espacial de cada imagen cuando es indexada en la base de datos. En la aplicación se usa la transformada wavelet para mantener unos pocos coeficientes (20) para cada canal de color y extraer de ellos una firma muy pequeña ''para cada imagen". Debido a que la firma es tan pequeña permite una búsqueda muy rápida en la base de datos. Sin embargo, ha demostrado ser un método eficaz para discriminar las imágenes.
	Ikona es un software que utiliza la arquitectura cliente-servidor para la construcción de un sistema CBIR, diseñado e implementado por el equipo de investigación Imedia perteneciente a INRIA (Institut national de recherche en informatique et en automatique). La parte del servidor de este motor CBIR está escrito en C++ (por razones de velocidad) y la parte cliente está escrito en Java y que normalmente debería funcionar en cualquier arquitectura de computadora que admita Java Runtime Environment (JRE). De forma predeterminada, el servidor realiza "la recuperación por similitud visual", en respuesta a una pregunta, lo que significa que busca todas las imágenes en la base de datos y devuelve una lista de las imágenes similares visualmente a la imagen de la pregunta. Si una base de datos de imagenes ha sido anotada con palabras clave, el servidor puede usar estas palabras clave para una recuperación rápida. Este prototipo permite también consulta de la región y se ha basado en modo híbrido de recuperación de texto-imagen. En el modo región, el usuario puede seleccionar una parte de una imagen y el sistema de búsqueda de imágenes (o partes de imágenes) consultará la parte seleccionada en la base de datos.
	MI-File (Metric Inverted File for efficient and scalable similarity search, Fichero métrico invertido para la búsqueda de similitud eficiente y escalable) es un motor de búsqueda que utiliza la colección CoPhIR y tiene actualmente indexada 106 millones de imágenes. La idea propuesta para la consulta de imágenes es utilizar el espacio métrico. Si dos objetos están muy cercas en el espacio métrico la visión de estos dos objetos con respecto al mundo que les rodea también es similar. Esto implica que, si tenemos un conjunto de objetos de la base de datos y se ordenan de acuerdo a sus similitud, las ordenaciones obtenidas son también similares. Básicamente es que se puede aproximar la semejanza entre dos objetos arbitrarios, mediante la comparación de la ordenación. De acuerdo a su similitud con estos dos objetos con un grupo de objetos de referencia, en lugar de utilizar la función de la distancia real entre los dos objetos.
	MUVIS es un framework para la gestión (indexación, navegación, consulta, etc) de colecciones multimedia como audio y vídeo e imágenes fijas. Esta aplicación ha sido desarrollada por un equipo de investigación de la Universidad de Tampere, finlandia. MUVIS hospeda aplicaciones para audio en tiempo real y captura de vídeo, codificación, creación de bases de datos, la conversión multimedia, indexación y recuperación. Proporciona una interfaz bien definida para integrar de forma dinámica (en tiempo de ejecución), extracción de características visuales y auditivas. El framework de MUVIS esta formado por los siguientes componentes: Visual Feature Extraction (FeX): Características representada por la sucesión de números que corresponden al vector de características. La normalización es necesaria para cada vector de características para obtener la misma unidad de longitud. Esto es necesario para la fusión de varias funciones por interpolación ponderada durante una operación de consulta. Scheme Aural Feature Extraction (AFeX): Una implementación para lograr una solución robusta y genérica para indexación y recuperación de audio multimedia. El objetivo principal es la recuperación del audio basado en el contenido ("suena como"), esto es subjetivo para el juicio humano y la percepción auditiva. Scheme Spatial Segmentation (SEG): Estos módulos se utilizan para crear máscaras de segmentación (SM, Segmentation Masks) de una imagen o fotograma clave de un clip de vídeo. Cada SM contiene dos o más regiones segmentadas (segmentos), indicado por un único valor de 8 bits en la escala de grises (entre 0 y 255). Por lo tanto, como un límite práctico no puede haber un máximo de 256 segmentos en una imagen de SM. Cualquier módulo SEG es responsable de asignar diferentes (y únicos) valores en la escala de grises de los píxeles dentro de cada segmento. Scheme Shot Boundary Detection (SBD): Al igual que en el framework FeX, Shot Boundary Detection (SBD) framework está diseñado para integrar de forma dinámica cualquier algoritmo SBD en MUVIS con un dedicado SBD API. Cualquier módulo SBD por lo tanto puede ser utilizado para extraer las siguientes entidades de un vídeo en una base de datos MUVIS. SBD módulos se desarrollan principalmente y utilizado por la aplicación DbsEditor durante la indexación de los vídeos en una base de datos MUVIS. MUVIS contiene tres aplicaciones diseñadas para el sistema operativo Windows: AVDatabase: Base de datos de vídeo y audio en tiempo real. DbsEditor: Aplicación de gestión de base de datos. MBrowser: Navegador de consultas.
	PIRIA es el acrónimo del Programa para la Indexación de las imágenes de Investigación por Afinidad (Program for Indexing and Research Images by Affinity). Desarrollado en LIST (Laboratoire d' Intégration des Systèmes et des Technologies, Laboratorio de investigación aplicada en tecnologías de software intensivo), Francia. Es un motor de búsqueda de imágenes basada en contenido, esto significa que el contenido de la imagen (color, textura, formas ...) se analiza para buscar imágenes similares a una consulta de una imagen. Se utilizan varias características de los descriptores de color, la textura y la forma para crear un índice (o firma). La aplicación se encuentra alojada en la web, el visitante selecciona una imagen y acto seguido se devuelve la consulta. La consulta se puede distinguir si queremos realizar segun el color, la forma o la textura. La colección de fotos es la utilizada por el profesor J. Wang.
	RETIN permite crear de forma interactiva categorizaciones semánticas de imágenes en bases de datos generalistas. Desarrollado por ETIS (Equipes Traitement de l'Information et Systèmes, Equipos de Tratamiento de la Información y Sistemas) una unidad perteneciente a ENSEA, Francia. Inicie la búsqueda haciendo clic en una imagen (que dirige su fondo verde), a continuación, haga clic en el botón "actualizar". Imágenes relevantes se seleccionan haciendo clic en ellos (fondo verde), los irrelevantes haciendo doble clic (fondo rojo). Algunos iteraciones permitirá enriquecer la categoría, lo que muestran las imágenes que pertenecen a la misma categoría en la misma pantalla.
	SIMBA (Search IMages By Appearance, Búsqueda de IMágenes por Apariencia) es una aplicación para la consulta de imágenes. Ha sido desarrollada en la Universidad de Freiburg, Alemania. El enfoque se basa en características invariantes, es decir, características que no varían si la imagen es transformada por algún grupo de transformación. Schulz-Mirbach presentó un algoritmo para la construcción de invariantes características [Schulz-Mirbach: 1995], que es muy adecuado debido a su robustez ligero deformaciones topológicas e incluso al movimiento independiente de los objetos dentro de la imagen. La principal ventaja es que no requiere la extracción de objetos (segmentación), o puntos distintos (puntos clave) de la imagen, pero se puede aplicar directamente a los datos de la imagen original. Para mejorar la robustez del algoritmo en una aplicación de recuperación de imágenes - sobre todo para apoyar a las coincidencias parciales - se modificó para que la información local se conservará en las características finales. Así se construyó la función de histograma [Siggelkow, Burkhardt: 1998], que son muy similares a los histogramas de color pero tiene en cuenta las características extraídas de una zona local de cada píxel en lugar de usar sólo el valor del color de cada píxel. La información de textura se tiene en cuenta.
	VITALAS (Video & image Indexing and reTrievAl in the LArge Scale, Indexación y Recuperación en gran escala de Video e imagen) es el resultado de un proyecto europeo de investigación cuyo objetivo es proporcionar una solución avanzada para la indexación, búsqueda y acceso a gran escala de contenidos audiovisuales digitales. El logro de VITALAS se basa en el desarrollo de eficiente de métodos avanzados de la descripción del contenido informativo, aprendizaje robusto hacia la anotación automática de búsqueda y contenido interactivo. Los objetivos del sistema de VITALAS se basan en tres actividades básicas: Cross-media indexing and retrieval methods. Métodos eficaces de indexación cruzada se desarrolla a través de la anotación semiautomática de contenidos multimedia utilizando varios medios de comunicación. VITALAS pondrá técnicas probabilísticas para una adecuada recuperación. A diferencia de muchos enfoques desarrollados en otros proyectos en curso, VITALAS no tendrá en cuenta los métodos basados en ontologías, pero los métodos de aprendizaje automático junto con el desarrollo de nuevos métodos de información de la descripción del contenido. Interactivity and Context adapting. Adaptación del espacio de búsqueda en el perfil de usuario y proporcionar funcionalidades interactivas para el control de los resultados. Cartografías interactivo y vídeo de vista sintético debe permitir a los usuarios dar información, analizar y manipular los resultados de acuerdo a la tarea de ser alcanzado. Perfiles fuera de línea del usuario y la personalización en línea, se utilizará también para proporcionar una mejor experiencia del usuario para expresar su preferencia. Search scalability issue. Tecnología que permiten la búsqueda en bases de datos muy grandes y heterogéneos es uno de los desafíos principal. La validación del sistema se llevará a cabo sobre bases de datos real y vivo, de 10.000 horas de archivos de televisión y varias decenas de millones de imágenes. El proyecto VITALAS desarrolla nuevos funcionalidades y servicios tecnológicos teniendo en cuenta todos los medios de comunicación (visuales, textuales y audio) para facilitar el acceso a contenidos multimedia de grandes bases de datos. Las funcionalidades del sistema proporciona la base sistemas y tecnologías de multimedia intuitiva, servicios de búsqueda, en la actualidad se enfrenta a un fuerte cuello de botella tecnológico.
	Windsurf (Wavelet-based INDexing of ImageS Using Region Fragmentation, Indexación basada en wavelet de imágenes usando fragmentación de región) es un proyecto desarrollado por la Universidad de Bolonia, italia. Windsurf es un framework para el procesamiento eficiente de las consultas de imágenes basadas en contenido. Con especial hincapié en el paradigma basado en regiones, windsurf proporciona un entorno donde las diferentes alternativas del paradigma puede ser implementado. Esto permite que las implementaciones de estos se comparen sobre una base justa, desde el punto de vista de la eficacia y eficiencia. Windsurf aborda el problema de la recuperación de imágenes basada en regiones (RBIR), proporcionando técnicas eficientes para el procesamiento de consultas que se plantean en este contexto. Dado que el framework es ampliable, se puede aprovechar las técnicas de procesamiento de consultas en Windsurf por instancias del framework. Para ello, Windsurf proporciona una biblioteca de Java que incluye clases que pueden ser ampliables para realizar el modelo RBIR que se requiera. Está compuesto por cuatro módulos: Procesador de consultas, que se encarga de la resolución eficiente de las consultas. Extractor de características, que trata de la extracción de bajo nivel de características y segmentación de la imagen. Persistencia de las materias primas-los datos y características se garantiza por medio de los administradores de resumen (RD-manager y F-manager). Implementaciones concretas de los administradores incluyen el uso de archivos de texto y los DBMS relacionales. Índice de funciones (para acceder eficientemente a las características de bajo nivel) se genera a petición y se utiliza para la resolución de consultas, el framework permite el uso de diferentes tipos de índices, incluye el índice M-tree.
	Pixolution es una empresa privada ubicada en alemania donde han desarrollado varias aplicaciones para la gestión y búsqueda de imágenes. Su objetivo es reducir el tiempo necesario que el usuario dispone para discriminar en las búsquedas. Han desarrollado tres herramientas: Ordenación visual de imágenes. Con esta aplicación se pueden organizar grandes cantidades de imágenes según su parecido visual y mostrarse de manera rápida, de esta manera se puede procesar cientos de imágenes de un solo vistazo. Búsqueda visual de imágenes. Herramienta que encuentra rápidamente imágenes visualmente similares a una dada en archivos grandes. Además se pueden hacer búsquedas de imágenes por composición de color. Sugerencia de imágenes semánticamente similares. Durante el uso de nuestras tecnologías de búsqueda y ordenación el sistema aprende basándose en las relaciones entre imágenes y las acciones del usuario. Se pueden encontrar además de imágenes que son similares visualmente otras que guardan un parecido semántico. En este enlace se puede descargar y probar la herramienta ImageSorter, es un programa que permite ordenar visualmente de manera automática las fotos e imágenes del ordenador, así como realizar búsquedas. También se existe una herramienta con igual función que la anterior pero que busca imágenes por internet, pixolu es un prototipo que demuestra las posibilidades de un sistema de búsqueda de imágenes, en él se combina la búsqueda por palabras clave tradicional con la ordenación visual de las imágenes, la búsqueda por similitud visual así como el aprendizaje semiautomático de las relaciones semánticas entre imágenes.
	Gazopa es un servicio de búsqueda de imágenes similares en la web desarrollado por Hitachi. Los usuarios pueden buscar imágenes de la web usando como referencia la propia foto, bocetos realizados por el usuario, las imágenes que se encuentran en la web y palabras clave. GazoPa permite a los usuarios buscar una imagen similar de características tales como un color o una forma extraída de una imagen en sí misma. Utiliza características de la imagen para buscar otras imágenes similares, una amplia gama de imágenes se pueden recuperar de la web.

Indexación Multidimensional

Organización del espacio multidimensional

Las estructuras de indexación multidimensional juegan un papel esencial en múltiples y variadas aplicaciones tales como gráficos por ordenador, visión por computadora, geometría computacional, procesamiento de imágenes, sistemas de información geográfica, reconocimiento de patrones, gestión de documentos multimedia, biología computacional, etc. En la práctica totalidad de estos campos de aplicación, los datos (registros, objetos, documentos, etc) se pueden representar (en ocasiones, sólo aproximar) mediante puntos multidimensionales, donde cada dimensión representa un atributo diferente del dato en cuestión. En la mayoría de las mencionadas aplicaciones, el volúmen de datos resulta excesivo como para ser almacenados en memoria principal. En estos casos, la indexación multidimensional facilita el almacenamiento y la aceleración de los procesos de búsqueda. El objetivo de las técnicas de indexación multidimensional es por tanto minimizar el número de accesos a disco necesarios para dar respuesta a las consultas emitidas por el usuario.

Un aspecto relevante en el contexto que nos ocupa es el tipo de consulta que se procesa sobre estos datos. Por ejemplo, en una base de datos relacional que almacene información sobre los empleados, una consulta típica puede buscar empleados que vivan en una ciudad, o que se encuentren en un rango de edad, o una combinación de ellas. Pero imaginemos que los registros de la base de datos almacenaran una foto del empleado, ¿cómo se resolvería una consulta donde intervenga el atributo "foto"?. No resulta trivial responder a una consulta, "muéstrame el empleado correspondiente a esta imágen", sobre todo porque la imágen puede no ser exactamente la misma (diferentes condiciones lumínicas, diferente enfoque, diferentes colores, ...) que se tiene almacenada en la base de datos. Lo más usual en este contexto es responder a consultas por semejanza a un patrón dado. Por ejemplo tenemos una imágen patrón y buscamos en la base de datos una imágen similar a la del patrón. O tenemos un perfil concreto y buscamos objetos que encajen en dicho perfil. Hablamos entonces de consultas por similitud.

Transformación para la búsqueda

La forma usual de llevar a cabo una búsqueda por similitud consiste en transformar cada objeto de la base de datos en un punto multidimensional que capture las características que definen el objeto (denominado vector de características) y modelar la búsqueda como una recuperación de vecinos más cercanos (“nearest neighbor search” o “nn-search”) en el espacio multidimensional. De este modo, la similitud entre objetos se implementa normalmente a través de una distancia, de modo que objetos cercanos se consideran similares. En aplicaciones específicas tales como bases de datos espaciales, similitud y cercanía pueden considerarse sinónimos, de modo que la distancia euclídea es una elección oportuna para medir la similitud entre objetos. Sin embargo, en muchas otras aplicaciones, la elección de una distancia capaz de representar apropiadamente el concepto de similitud no es tan obvia. Diferentes funciones de similitud han sido examinadas con distinto grado de eficacia, pero siempre los resultados dependen fuertemente del dominio de aplicación. La elección de la función de similitud está directamente relacionada con la efectividad del proceso, es decir, con la calidad de la respuesta. Aunque el aspecto de la efectividad es obviamente crítico, cuando la colección de objetos es considerablemente grande (el escenario más usual) otro elemento definitivo de la búsqueda por similitud es la eficiencia del proceso, es decir el tiempo necesario (CPU y E/S) para ofrecer una respuesta satisfactoria a la consulta. La indexación multidimensional aborda este aspecto del problema.

División del espacio métrico

Una amplia colección de métodos de indexación multidimensionales han sido propuestos en las últimas dos décadas. Cuando la función de similitud es una métrica (positividad estricta, simetría y desigualdad triangular), una opción la constituyen los llamados índices métricos o basados en distancia, los cuales utilizan las propiedades de la distancia (fundamentalmente la desigualdad triangular) para filtrar objetos o regiones enteras del espacio. Entre este tipo de índices podemos categorizar aquellos que establecen una división del espacio en esferas y aquellos que dividen el espacio mediante hiperplanos. Entre los primeros podemos destacar el Vp-tree, o Vantage Point Tree, el mVP-tree o Multiple Vantage Point, y el M-tree o Metric Tree. Otro tipo de índices métricos se materializan mediante matrices que almacenan la distancia entre todos los puntos del espacio y puntos preseleccionados del espacio de búsqueda, tales como AESA y LAESA.

División del espacio basada en r-tree

Cuando la función de similitud no es una métrica, o bien varía con la colección de objetos residentes en la base de datos, los índices métricos son inaplicables. En este caso, una alternativa plausible son los índices basados en características. En esta categoría podemos distinguir entre métodos que agrupan los puntos de la colección mediante cajas de acotación (que pueden estar solapadas) como los derivados del R-tree, y métodos de acceso que llevan a cabo una partición del espacio de características mediante hiperplanos iso-orientados, como los basados en el kd-tree. Los métodos basados en el R-tree han demostrado un buen rendimiento en espacios de baja dimensionalidad (2 y 3 dimensiones). Sin embargo, en espacios de media y alta dimensionalidad, el solapamiento entre las cajas de acotación crece exponencialmente y la estructura se vuelve ineficiente. Múltiples propuestas basadas en esta estructura son el X-tree, TV-tree y otras que utilizan esferas de acotación para mejorar las consultas de similitud, como el SR-tree. Todas ellas abordan el problema de la alta dimensionalidad en este tipo de estructuras.

División del espacio basada en kd-tree

Las estructuras de indexación más conocidas basadas en el k-d-tree son el K-D-B-tree, LSD-treey hB-tree, los cuales han demostrado buen rendimiento en búsquedas por rango. Sin embargo sólo alguna de ellas implementa consultas por similitud. El árbol Q, estructura de indexación basada en el k-d-tree y desarrollada en el seno de nuestro grupo de investigación, ha demostrado buenos resultados de rendimiento en búsquedas por similitud con espacios de baja y media dimensionalidad (hasta 25 dimensiones).

Otra importante alternativa a los métodos anteriores son aquellos que tratan de acelerar las búsquedas por similitud en voluminosos espacios altamente dimensionales aportando soluciones aproximadas, esto es dando como respuesta objetos que con un cierto margen de error pueden considerarse los más próximos al patrón de búsqueda. El método (LHS) o hashing sensible a la localidad, representativo de esta clase ha demostrado buenos resultados en determinados contextos de aplicación.

Entre las líneas de investigación de nuestro grupo se encuentra ésta de la indexación multidimensional. En tal sentido dentro de nuestro grupo investigamos con diferentes estrategias para dar solución a problemas relacionados con la búsqueda por similitud, fundamentalmente en el contexto de colecciones voluminosas de documentos multimedia.

Enlaces de interés

A continuación se incluyen enlaces a recursos interesantes sobre indexación multidimensional:

The R-tree Portal. Uno de los mejores sitios con cantidad de recursos de programación sobre índices basados en el árbol R. Gracias a Yannis Theodoridis, de la Universidad de Pireo, Grecia.
MESSIF. Metric Similarity Search Implementation Framework. Proporciona un framework para la implementación y evaluación de índices métricos. Gracias a Michal Batko y David Novak, de Masaryk University en Brno, República Checa.
Metric Spaces Library. Biblioteca de programas de código abierto para indexación de espacios métricos.
Locality-Sensitive Hashing (LSH). Código y descripción del algoritmo LSH. Gracias a Piotr Indyk.
LAESA. Implementación del método Linear Approximation and Eliminating Search Algorithm. Departamento de lenguajes y sistemas informáticos. Gracias a Maria Luisa Micó. Universidad de Alicante.
Multidimensional Index Simulator. Biblioteca software con varios métodos de acceso multidimensional (KDB-trees, R-trees, the Pyramid Technique, …). El simulador se diseñó con un propósito académico. Gracias a Ratko Orlandic, Department of Computer Science Illinois Institute of Technology.
The GiST Indexing Project. Una biblioteca escrita en C++ que facilita la implementación de métodos de indexación multidimensional.
The M-tree project. Implementación y descripción del M-tree, una estructura de indexación basada en distancias. La implementación está basada en la biblioteca GIST.

Bibliografía recomendada

Foundations of Multidimensional	Foundations of Multidimensional and Metric Data Structures. Autor: Hanan Samet. Un excelente texto sobre métodos de acceso espaciales y multidimensionales en general. Imprescindible en la biblioteca del investigador.
Indexing Techniques for Advances Database systems	Indexing Techniques for Advances Database systems. Autores: Elisa Bertino y otros. Repasa las principales estructuras de indexación en función de las aplicaciones (datos espaciales, datos de imágenes, temporales, …). Un buen libro, pero le falta algo más de profundidad.
Advanced Database Indexing	Advanced database Indexing. Autores Yannis Manolopoulos, Yannis Theodoridis, Vassilis J. Tsotras. Revisión de estructuras de indexación de acuerdo a su campo de aplicación (imágenes, datos temporales, datos espacio-temporales, etc.). Buen número de referencias al final de cada capítulo.
Similarity Search	Similarity Search: The Metric Space Approach. Autores Pavel Zezula, Giuseppe Amato, Vlastislav Dohnal, Michal Batko. Buen libro sobre estructuras de indexación limitadas a índices métricos.

Computación de Altas Prestaciones

El objetivo de la Computación de Altas Prestaciones es poner al servicio de las aplicaciones científicas en los campos de la física, la ingeniería, la biología, etc. la capacidad de cómputo de computadores avanzados. El hardware disponible para estas aplicaciones comprende desde unos pocos procesadores compartiendo memoria hasta supercomputadores con cientos de miles de procesadores conectados por redes de alta capacidad y baja latencia.

Esta línea de investigación trata del estudio de los diferentes estándares, lenguajes, tecnologías y herramientas que proporcionan a las aplicaciones científicas el rendimiento, escalabilidad y fiabilidad que necesitan para ejecutar en plataformas supercomputador.

Dentro de esta línea de investigación se ha construido una implementación del estándar MPI (Message Passing Interface) en su versión 1.3, denominado AzequiaMPI. El estándar MPI permite construir aplicaciones que resuelven un problema en base a tareas que se comunican mediante paso de mensajes. Estas tareas pueden ejecutar en memoria compartida y/o distribuida. Las bibliotecas más conocidas que implementan el estándar MPI (MPICH2, Open MPI) construyen cada tarea MPI como un proceso, sin embargo, AzequiaMPI construye cada tarea como un hilo. Las ventajas de esta aproximación son un mayor rendimiento en la explotación de las emergentes arquitecturas multicore y un menor consumo de memoria.

HP Lusitania supercomputador

La biblioteca AzequiaMPI ha sido portada y ejecutada en diferentes plataformas, incluyendo el supercomputador Lusitania del CenitS (2x HP Integrity Superdome SX2000) y el supercomputador NEC SX-9 del HLRS (High Performance Supercomputing Center in Stuttgart), formado por 700 nodos Nehalem de 8 cores.

SMT310Q. 4 C6x cores conectados por SDB

El grupo GIM dispone de un computador con 32 cores (4 nodos nehalem de 8 cores) conectados por Infiniband y Ethernet, para desarrollo y evaluación.

AzequiaMPI surgió a partir de una primera implementación de MPI en arquitecturas multicomputador de Procesadores de Señal Digital, formada por DSPs C6000 de Texas Instruments conectados por la red propietaria Sundance Digital Bus (SDB) de Sundance Company.

Cluster TCP de FPGAs de Xilinx

El diseño modular de AzequiaMPI y el bajo consumo de memoria nos ha permitido portar la biblioteca AzequiaMPI a plataformas cluster FPGA de Xilinx conectadas mediante redes TCP/IP. Para construir esta plataforma reconfigurable de altas prestaciones se han utilizado procesadores software como Xilkernel o MicroBlaze, y actualmente se está portando a procesadores hardware PowerPC.

Base de Datos y XML

Versionado de Documentos XML

XML se ha convertido en el medio predominante para el intercambio de información en la Web, pero además, se utiliza para almacenar información de configuración (Apache, Eclipse, etc), documentos ofimáticos (OpenOffice, Microsoft Office) y también como mecanismo de almacenamiento de información semi-estructurada mediante las bases de datos nativas XML (XML Native Databases - XNDB).

Uno de los puntos más importante de nuestra investigación es la gestión de versiones de ddocumentos XML. Estos documentos como cualquier otra fuente de información varia a lo largo del tiempo y se hace necesario gestionar sus cambios para así poder consultar datos pretéritos o monitorizar dichos cambios.

Las soluciones más significativas son:

Técnicas clásicas de versionado como cvs o subversion, sin embargo su uso no es recomendable en documentos XML pues utilizan algoritmos de cálculo de diferencias a nivel textual, y por tanto estas herramientas no tienen en cuenta la estructura de anidamiento de estos documentos. Han surgido heerramientas de diferencias específicas para documentos XML denominadas delta XML pero tienen el problema de no permitir la validación XML de las versiones ni las consultas mediante estándares XML como XQuery o XPath.
Representación temporal que consiste en marcar temporalmente (timestamp) cada etiqueta del documento indicando en qué periodos de tiempo dicha etiqueta es válida. Debido a la naturaleza lineal del tiempo, estas soluciones carecen de soporte para versionado ramificado.

Nuestra solución, basada en versionstamp y denominada vDocXML, utiliza una notación similar a los sistemas tradicionales de versionado y representan la validez de cada etiqueta a partir del grafo de evolución. Para más información recomendamos los siguientes enlaces

Información de nuestra técnica: "Representing Versions in XML Documents using Versionstamp". ECDM 2006.
Gestión de versiones mediante nuestra técnica: "Managing Brach Versioning in Versioned/Temporal XML Documents". XSYM 2007 (VLDB Workshop).
Demo de dos implementaciones realizadas. Se ha realizado una implementación basada en un conjunto de módulos XQuery que pueden utilizarse tanto en procesadores XQuery como en bases de datos nativas XML con soporte a XQuery. Usanto estos modulos hemos extendido la base de datos eXist.
- vExist: Es una extensión del interfaz web de eXist para la gestión de versiones de documentos XML.
- vEditor: Aplicación AJAX para la gestión de versiones online.

Áreas

Log in