PDF de programación - Clasificación y búsqueda de imágenes usando características visuales

Clasificación y búsqueda de

imágenes usando características

visuales

Antonio Nicolás Pina

Universidad de Murcia

Facultad de Informática

Proyecto Fin de Carrera

Dirigido por

Ginés García Mateos

Junio de 2010

Resumen

En este proyecto se aborda el análisis, diseño e implementación de una aplicación
para la clasificación y búsqueda automática de imágenes no segmentadas, permi-
tiendo una rápida búsqueda por contenido sobre una base de datos que puede ser
arbitrariamente grande. Para ello, se han aplicado dos tipos de técnicas de compa-
ración: basadas en color y basadas en puntos característicos (features).

El primero de los métodos basados en color que se ha probado es el matching ,
en el que la imagen de entrada se compara píxel a píxel con cada imagen de la
base de datos dentro de un espacio de color multicanal. Para acelerar el proceso y
aumentar la robustez de la comparación, se reducen todas las imágenes a un tamaño
prefijado y se comparan con ese menor tamaño, aumentando así la coincidencia entre
imágenes muy similares que, a una mayor escala, tendrían una gran diferencia entre
ambas.

La segunda de las técnicas basadas en color que se ha implementado es el uso
de histogramas de color, en los que se obtiene un resumen de las cantidades de
color que cada imagen contiene, y la comparación se realiza sobre estos resúmenes,
en lugar de hacerlo sobre los píxeles de la imagen. Al hacer las comparaciones entre
imágenes sobre la cantidad de color que contienen y no sobre sus píxeles, se obtiene
una cierta invarianza a los objetos que aparecen en la escena independientemente de
su posición, centrándose sólo en el color que poseen, en cualquiera de los espacios
de color que existen, lo que puede resultar interesante para algunas aplicaciones.

De entre los métodos basados en features se ha optado por utilizar SIFT (Scale
Invariant Feature Transform), que permite describir objetos de una escena no seg-
mentada con invarianza a la posición, escala y rotación. Una característica SIFT se
define como el punto de máxima respuesta del operador diferencia de Gaussianas
sobre un espacio de escala. Un espacio de escala es una pirámide de escalas de la
imagen de entrada, calculada aplicando el suavizado de Gauss un número determi-
nado de veces. Sobre la pirámide de escalas, se calculan unas imágenes de salida
como la diferencia de los niveles de suavizado adyacentes. Finalmente, sobre estas
imágenes de salida, una vez refinadas, se tiene como resultado unos puntos signifi-
cativos, que serán los máximos locales de las diferencias de Gaussianas en ciertos
valores de escala.

Además, se ha utilizado otro método de extracción de características, inspirado en
SIFT, llamado SURF (Speeded Up Robust Features). SURF promete una obtención
de características tan adecuada como SIFT pero con un menor coste computacional.
Debido a la gran necesidad de proceso y de memoria que los métodos basados
en características requieren, se ha tenido que definir un método de clasificación que
haga más eficiente la búsqueda, permitiendo así una mejor escalabilidad del sistema.
De entre los métodos de clasificación que existen, los más adecuados son aquellos
con estructura arbórea, ya que permiten obtener tiempos de búsqueda sublineales.

iii

De entre éstos, se ha implementado un árbol de clusters de características, en el
que cada nodo es dividido en nodos hijos mediante el algoritmo de k-medias.

Para medir la eficiencia de cada uno de los métodos anteriores, se han creado dos
bases de datos de imágenes de prueba, que permitan realizar comparaciones
fiables sobre la bondad de cada técnica en un entorno reducido y controlado. La
primera de las bases de datos de prueba contiene 100 imágenes, distribuidas en 20
categorías, con un alto grado de similitud entre las imágenes de cada categoría,
de forma que sea más sencillo para los métodos obtener un buen porcentaje de
acierto, y así simular una base de datos real, en la que la inmensa cantidad de
imágenes almacenada hace que muchas de ellas sean muy similares. La segunda
base de datos contiene 50 imágenes en 10 categorías, con una mayor dificultad; esto
es, con un menor parecido entre las imágenes de cada categoría, por lo que el método
se verá obligado a hacer una mejor descripción de los elementos relevantes si quiere
superar correctamente la prueba. Así, con los dos tipos de pruebas, se podrá ver
qué método es más adecuado en cada situación.

Los resultados que se han obtenido para los métodos basados en color han
sido muy buenos, tanto sobre la base de datos de imágenes simples como sobre la
realista. Esto es debido a la similitud de colores que el mismo objeto tiene indepen-
dientemente de cual sea la escena en la que se encuentra, siempre que su tamaño
relativo a la escena lo haga suficientemente relevante.

En cambio, con los métodos basados en features, la fiabilidad ha sido ligera-
mente inferior que en los métodos de color, debido principalmente a la variación
de pose que los objetos tienen entre imágenes, así como a la dificultad de obtener
buenos comparadores de features en un entorno complejo y realista. Además, estos
métodos han demostrado ser mucho más lentos que los basados en color, por lo
que su uso queda muy limitado.

Además, el árbol de clasificación utilizado para acelerar las búsquedas ha compli-
cado más el proceso de comparación de features, empeorando en algunos casos el
resultado final, ya que cuando se consulta en el árbol se obtiene una lista de features
sin ningún orden o relación aparente. Por otro lado, en el método de clasificación
básico, en el que se tiene una lista global de features, es más sencillo obtener las
características relacionadas de una foto y establecer una biyección entre ambas
fotografías, facilitando así la obtención de buenos resultados. Por ello, podemos con-
cluir que aunque el árbol acelera en gran medida las consultas respecto a tener una
lista global de features, su utilización no ha aportado mejoras a la búsqueda, ya
que el porcentaje de aciertos es menor, debido a esa dificultad de combinar las
features.

Agradecimientos

Al principio, no creí que me fuera a dedicar a esto. Y es que la informática y los
ordenadores llegaron a mi vida algo más tarde que a la gente de mi generación. El
ajustado presupuesto familiar y los hermanos fuera de casa hicieron que un orde-
nador se viera como un lujo más que como la herramienta que hoy en día es, ¡y ya
estábamos en el siglo XXI!

Sin embargo, un día llegó. No olvidaré aquel AMD K6-II que, con tanto esfuerzo
y pago aplazado, mis padres me regalaron por navidad. Aquel fue el dia en que mi
vida empezó a cambiar, y me condujo por unos caminos que ni me había planteado.
Tal fue mi pasión que, cuando un día, casi por sorpresa, dije que iba a estudiar
informática, a nadie de mi familia le extrañó mucho. Ahora me doy cuenta que, sin
ellos, nada de esto hubiera sido posible.

Porque sin el cariño y la comprensión de mis padres, ni los consejos de mi hermana
Jose, no podría haber aguantado los malos días, por eso les quiero dedicar este
proyecto. Tampoco me puedo olvidar de mi prima Isabel, esa persona especial que
me hace volver a tener fé en la humanidad, ni del resto de mi familia, que me han
escuchado cuando lo he necesitado.

También quiero agradecer el esfuerzo a mis amigos, a algunos por su apoyo moral,
y a otros por su colaboración, porque no sería justo que acabara sin mencionar a
Daniel, Miriam, Fran, Juan y al resto de mis followers, porque leer mi timeline me
hace un poquito más feliz, gracias a todos.

Finalmente, quiero agradecer su esfuerzo y dedicación a Ginés, a Alberto y Diego,
algunos de esos pocos profesores buenos de la facultad, de los que disfrutan con su
trabajo y que contagian su pasión a los alumnos. Sólo unas pocas personas tienen
todo mi respeto y admiración, y estos profesores, sin duda, son unos buenos ejemplos
de ello.

v

Índice general

1. Introducción

1.1. Antecedentes históricos . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1.1. Buscadores de imágenes basados en metadatos . . . . . . . . .
1.1.2. Buscadores de imágenes basados en contenido . . . . . . . . .
. . . . . . . . . . . . . . . . . .
1.2. Aplicaciones del problema estudiado
1.3. Estructura del documento . . . . . . . . . . . . . . . . . . . . . . . .

1
2
2
4
6
7

2. Objetivos y metodología de trabajo

2.1. Objetivos

9
9
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1. Características más importantes . . . . . . . . . . . . . . . . .
9
2.1.2. Otras características deseables . . . . . . . . . . . . . . . . . . 10
2.2. Entorno de programación . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.2.1. Programación del núcleo de la aplicación . . . . . . . . . . . . 11
2.2.2. Programación del interface web . . . . . . . . . . . . . . . . . 12
2.3. Base de datos de pruebas . . . . . . . . . . . . . . . . . . . . . . . . . 13
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.4. Equipo de pruebas

3. Estado del arte

3.1. Principales buscadores comerciales

17
. . . . . . . . . . . . . . . . . . . 17
3.1.1. Google Images . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.1.2. TinEye . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
3.1.3. MiPai
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.2. Técnicas más usadas actualmente . . . . . . . . . . . . . . . . . . . . 21
. . . . . . . . . . . . . . . . . . . . . . . 21
3.2.1. Detección de bordes
. . . . . . . . . . . . . . . . . . . . 24
3.2.2. Técnicas basadas en color
3.2.3. Características SIFT y SURF . . . . . . . . . . . . . . . . . . 25

4. Arquitectura del sistema

27
4.1. Escalabilidad del sistema . . . . . . . . . . . . . . . . . . . . . . . . . 27
4.1.1. Balanceo de carga . . . . . . . . . . . . . . . . . . . . .