Estudio de mtodos de indexacin yrecuperacin en bases de datos de

imgenes

Memoria presentada porJos Orlando Maldonado Bautista

Para optar al grado de Doctor enInformatica en la

Universidad del Pais Vasco

DirectorManuel Graa Romay

Departamento de Ciencias de la Computacin EInteligencia Artificial

Facultad de Informatica

UPV/EHU

San Sebastin, abril 2008

2

Resumen

La tesis aborda el problema del acceso a bases de datos de imgenes basadoen ndices calculados a partir del contenido de la propia imagen, cono-cido por sus siglas en ingls Content Based Image Retrieval (CBIR).Realiza una revisin del estado del arte en este tema. Se realiza tam-bin una revisin de los principales resultados y conceptos relativosa Bancos de Filtros de Gabor y Transformada Discreta en Wavelets,dos tcnicas de anlisis de la imagen muy extendidas y que son in-strumentales en una de las aplicaciones desarrolladas. La tesis contienedos casos especiales de sistemas CBIR. El primero es un sistema deindexacin de imgenes de papel reciclado. Adems de servir para elacceso basado en contenidos, esta indexacin puede ser utilizada parasistemas de control de calidad en la fabricacin de papel reciclado. Elsegundo caso de estos sistemas trata con imgenes hiperespectrales dereconocimiento remoto. Se propone una medida de similitud espectralbasada en los endmembers obtenidos mediante la aplicacin de Memo-rias Autoasociativas Morfolgicas para la deteccin de la independenciamorfolgica. Se proporcionan resultados experimentales de rendimientode la recuperacin calculados sobre bases de datos de imgenes sintti-cas.

3

4

Agradecimientos

Deseo agradecer en primer lugar a la Universidad del Pas Vasco y laUniversidad de Pamplona (Colombia), las cuales me han permitido iniciar yllevar a buen trmino mi formacin doctoral. A mi tutor y director de tesis,Dr. Don Manuel Graa Romay por su invaluable apoyo y colaboracindesde el comienzo de mi doctorado, as como por su paciencia e influenciaen todos los captulos de este proceso. Estoy seguro que su contagioso entu-siasmo por los procesos acadmicos y cientficos me han marcado una rutahacia nuevos y fructferos desafos. A los profesores de la Facultad de In-formtica y en especial del Departamento de Ciencias de la Computacine Inteligencia Artificial que de uno u otro modo han aportado a mi proce-so formativo. A los miembros del Grupo de Inteligencia Computacional, queconforman un caudal creciente de conocimiento presto a aportar al desarrollode todos sus miembros. A mis compaeros de Laboratorio: Elsa Fernndez,Abdel Moujahid, Maite Garca, Miguel Veganzones, Ramn Moreno, FlavioBanterla, Alexandre Savio e Ivn Villaverde, con quienes he departido grata-mente durante estos ms de cinco aos. Tambin un agradecimiento especiala la secretaria Administrativa del Dpto. CCIA, Doa Elena Bidondo, por suayuda y colaboracin desde el momento mismo de mi llegada.

A mi familia: mis padres Rosa Bautista y Jos Maldonado, hermanos,sobrinos y dems, que han estado conmigo en todo momento. Sin su respaldo,nada de esto habra sido posible. A mis amigos, que aqu me han dado apoyo,compaa y buenos momentos, y que en Colombia siempre me han animadopara continuar adelante, gracias por estar ah, a pesar de la distancia.

A cada una de las personas que de algn modo han contribuido para eldesarrollo y culminacin de esta tesis, mi ms sincero agradecimiento.

San Sebastin, Abril 21 de 2008.

5

6

ndice general

1. Introduccin 191.1. Motivacin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.1.1. Imgenes de papel reciclado . . . . . . . . . . . . . . . 201.1.2. Imgenes de reconocimento remoto . . . . . . . . . . . 21

1.2. Contribuciones ms relevantes . . . . . . . . . . . . . . . . . . 221.3. Objetivos de la tesis doctoral . . . . . . . . . . . . . . . . . . 231.4. Publicaciones realizadas . . . . . . . . . . . . . . . . . . . . . 241.5. Publicaciones submitidas . . . . . . . . . . . . . . . . . . . . . 251.6. Estructura de la memoria de la tesis . . . . . . . . . . . . . . 25

2. Recuperacin de imgenes basada en contenidos 292.1. Introduccin . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.2. Aspectos generales . . . . . . . . . . . . . . . . . . . . . . . . 322.3. Ejemplos de Sistemas CBIR . . . . . . . . . . . . . . . . . . . 352.4. Arquitectura de los sistemas CBIR . . . . . . . . . . . . . . . 362.5. Extraccin de caractersticas . . . . . . . . . . . . . . . . . . . 39

2.5.1. Caractersticas de Textura . . . . . . . . . . . . . . . . 392.5.2. Caractersticas de Color . . . . . . . . . . . . . . . . . 412.5.3. Caractersticas de formas . . . . . . . . . . . . . . . . . 422.5.4. Relaciones espaciales de regiones y puntos de inters . . 46

2.6. Mtricas y funciones de similitud . . . . . . . . . . . . . . . . 462.7. Mtodos de acceso y bsqueda en base de datos . . . . . . . . 492.8. Aprendizaje y realimentacin por relevancia . . . . . . . . . . 522.9. Evaluacin en los sistemas CBIR . . . . . . . . . . . . . . . . 532.10. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

7

8 NDICE GENERAL

3. Filtros de Gabor 593.1. La transformada de Gabor . . . . . . . . . . . . . . . . . . . . 603.2. Funciones de Gabor 2D . . . . . . . . . . . . . . . . . . . . . . 623.3. Bancos de Filtros de Gabor . . . . . . . . . . . . . . . . . . . 65

4. Anlisis Wavelet 694.1. Wavelets Continuas . . . . . . . . . . . . . . . . . . . . . . . . 69

4.1.1. Definicin de wavelet . . . . . . . . . . . . . . . . . . . 694.1.2. Ejemplos de wavelets . . . . . . . . . . . . . . . . . . . 70

4.1.2.1. Wavelet de Haar . . . . . . . . . . . . . . . . 704.1.2.2. Wavelet de Shannon . . . . . . . . . . . . . . 714.1.2.3. Wavelet de Morlet . . . . . . . . . . . . . . . 72

4.1.3. La Transformada Wavelet Continua . . . . . . . . . . . 724.1.3.1. Definicin . . . . . . . . . . . . . . . . . . . . 734.1.3.2. Transformada Wavelet Inversa . . . . . . . . . 744.1.3.3. Propiedades . . . . . . . . . . . . . . . . . . . 75

4.2. La Transformada Wavelet Discreta . . . . . . . . . . . . . . . 764.2.1. Anlisis Multiresolucin . . . . . . . . . . . . . . . . . 784.2.2. Bases de wavelets ortonormales en el anlisis multires-

olucin . . . . . . . . . . . . . . . . . . . . . . . . . . . 794.2.3. Algoritmo de descomposicin piramidal . . . . . . . . . 80

4.3. Transformada Wavelet en dos dimensiones . . . . . . . . . . . 83

5. Control de calidad del papel reciclado 875.1. Descripcin del problema . . . . . . . . . . . . . . . . . . . . . 885.2. Consideraciones metodolgicas . . . . . . . . . . . . . . . . . . 915.3. Adquisicin de las imgenes . . . . . . . . . . . . . . . . . . . 945.4. Etiquetado manual . . . . . . . . . . . . . . . . . . . . . . . . 955.5. Definicin de caractersticas . . . . . . . . . . . . . . . . . . . 99

5.5.1. Caractersticas basadas en Bancos del Filtros de Gabor 1005.5.2. Caractersticas basadas en coeficientes de la TWD . . . 101

5.6. Clasificacin automtica . . . . . . . . . . . . . . . . . . . . . 1025.6.1. Resultados con las caractersticas extradas mediante

BFG . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1035.6.2. Resultados con las caractersticas extradas mediante

coeficientes wavelet . . . . . . . . . . . . . . . . . . . . 1045.6.3. Conclusiones de la clasificacin . . . . . . . . . . . . . 108

5.7. Establecimiento de un ndice de abollado . . . . . . . . . . . . 108

NDICE GENERAL 9

5.7.1. Validacin por ordenacin de pares . . . . . . . . . . . 1115.8. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . 117

6. Sistema CBIR para imgenes hiperespectrales 1196.1. imgenes hiperespectrales . . . . . . . . . . . . . . . . . . . . 1196.2. Descomposicin espectral . . . . . . . . . . . . . . . . . . . . . 1206.3. Algoritmos de extraccin de endmembers . . . . . . . . . . . . 1236.4. Redes morfolgicas e independencia morfolgica . . . . . . . . 125

6.4.1. Breve revisin de fundamentos . . . . . . . . . . . . . . 1266.4.2. Algoritmo heurstico de induccin de endmembers . . . 128

6.5. Resultados de segmentacin . . . . . . . . . . . . . . . . . . . 1306.6. Distancia entre imgenes hiperespectrales . . . . . . . . . . . . 1376.7. Resultados sobre bases de datos de imgenes sintticas . . . . 138

6.7.1. Experimento 1 . . . . . . . . . . . . . . . . . . . . . . 1386.7.2. Experimento 2 . . . . . . . . . . . . . . . . . . . . . . 141

6.8. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145

7. Conclusiones y lneas de trabajo futuro 1477.1. Caracterizacin visual de la calidad del papel . . . . . . . . . . 1477.2. Sistemas CBIR de imgenes hiperespectrales . . . . . . . . . . 1487.3. Aplicaciones de Lattice Computing a CBIR . . . . . . . . . . 148

A. Ejemplos Ilustrativos 151A.1. Ejemplos ilustrativos sobre caractersticas de texturas basados

en BFG . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151A.2. Ejemplos ilustrativos sobre caractersticas de texturas basados

en la TWD . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159

Bibliografa 167

10 NDICE GENERAL

Lista de algoritmos

1. Algorithmo heurstico de induccin de los endmembers . . . 129

11

12 LISTA DE ALGORITMOS

ndice de figuras

2.1. Esquema de una consulta mediante ejemplo, en un sistemaCBIR. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.2. Agrupacin de funcionalidades en mdulos de un sistema CBIR 38

3.1. Filtro de Gabor en el dominio espacial. a) Partes real e imag-inaria de la sinusoidal compleja. b) Gausiana rotada sobre elorigen c) Mscaras formadas por las funciones sinusoidales reale imaginaria moduladas por la gausiana. . . . . . . . . . . . . 63

3.2. Elipse de puntos con respuesta igual a la mitad de la magnituden el dominio de la frecuencia . . . . . . . . . . . . . . . . . . 65

3.3. Recubrimiento del plano de Fourier por un Banco de Fil-tros de Gabor. a) Sin solapamiento en la respuesta de media-magnitud, b) Con solapamiento en la respuesta de magnitudmedia. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

4.1. Wavelet de Haar . . . . . . . . . . . . . . . . . . . . . . . . . 714.2. Funcin wavelet de Shanon . . . . . . . . . . . . . . . . . . . 724.3. Parte real de la Wavelet de Morlet . . . . . . . . . . . . . . . 734.4. Descomposicin del plano mediante la discretizacin por mue-

stro de la malla didica . . . . . . . . . . . . . . . . . . . . . . 774.5. Esquema para un nivel descomposicin multiresolucin de la

imagen mediante el algoritmo piramidal . . . . . . . . . . . . 844.6. Representacin de una imgen con tres niveles de descomposicin 854.7. Esquema para la reconstruccin de una imagen multiresolu-

cin mediante el algoritmo piramidal . . . . . . . . . . . . . . 86

5.1. Ejemplos de imagnes de papel reciclado con abollado. Lasimgenes han sido preprocesadas para mejorar el contraste. . . 92

13

14 NDICE DE FIGURAS

5.2. Histogramas generados con los valores obtenidos a partir de lafuncin discriminante de Fisher aplicada a los vectores gener-ados con el BFG sin solapamiento. . . . . . . . . . . . . . . . 113

5.3. Histogramas generados con los valores obtenidos a partir de lafuncin discriminante de Fisher aplicada a los vectores gener-ados con el BFG con solapamiento. . . . . . . . . . . . . . . . 114

5.4. Histogramas generados con los valores obtenidos a partir de lafuncin discriminante de Fisher aplicada a los vectores gener-ados mediante los coeficientes de la TWD con wavelet madreHaar en los niveles 1-3. . . . . . . . . . . . . . . . . . . . . . 115

5.5. Histogramas generados con los valores obtenidos a partir de lafuncin discriminante de Fisher aplicada a los vectores gener-ados mediante los coeficientes de la TWD con wavelet madreHaar en los niveles 4-6. . . . . . . . . . . . . . . . . . . . . . 116

6.1. Ilustracin de la captura de la imagen hiperespectral . . . . . 1216.2. Ilustracin del cubo de datos que constituye una imagen hipere-

spectral . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1216.3. Ilustracin de las causas de la mezcla lineal espectral . . . . . 1226.4. Endmembers encontrados por nuestro algoritmo heurstico basa-

do en independencia morfolgica sobre la imagen de Washing-ton D.C. Mall . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

6.5. Imgenes de abundancia calculadas usando los endmembersde la figura 6.4 . . . . . . . . . . . . . . . . . . . . . . . . . . 132

6.6. Indian Pines 1992, verdad del terreno . . . . . . . . . . . . . . 1346.7. Endmembers encontrados por el algoritmo heurstico de la sec-

cin 6.4.2 en la imagen Indian Pines . . . . . . . . . . . . . . . 1346.8. Abundancias calculadas usando los endmembers en la figura 6.71356.9. Resultado de la clasificacin supervisada presentada en [150, 149]1366.10. Espectros de repositorio de la USGS usados como endmembers

de la verdad del terreno en el primer experimento. . . . . . . . 1396.11. Un ejemplo de la interface de un sistema CBIR para imgenes

hiperespectrales: una consulta y sus imgenes ms cercanasdeacuerdo al conjunto de endmembers inducido. . . . . . . . . 141

6.12. Endmembers verdad del terreno utilizados para el segundoexperimento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

NDICE DE FIGURAS 15

6.13. Una instancia de las imgenes de abundancia generadas comocampos basados en polinomios de Legendre para una imagencon cinco endmembers. . . . . . . . . . . . . . . . . . . . . . 143

A.1. Imgenes construidas con orientacin y frecuencia espacial es-pecficas que han sido definidas para probar la respuesta decada filtro, las frecuencias en las barras de cada imagen sonde 1/4, 1/8, 1/16 y 1/32 ciclos/pixel, con orientaciones de 0,45 ,90 y 135 grados. . . . . . . . . . . . . . . . . . . . . . . . 152

A.2. BFG sintonizado con los parmetros F = 1/4, 1/8, 1/16, 1/32ciclos/pixel, y = 0o, 45o, 90o, 135o . . . . . . . . . . . . . . . 153

A.3. Respuestas del FG con parmetros = 0o, 45o, 90o, 135o, F =1/4 ciclos/pixel . . . . . . . . . . . . . . . . . . . . . . . . . . 154

A.4. Respuestas del FG con parmetros = 0o, 45o, 90o, 135o, F =1/8 ciclos/pixel. . . . . . . . . . . . . . . . . . . . . . . . . . . 155

A.5. Respuestas del FG con parmetros = 0o, 45o, 90o, 135o, F =1/16 ciclos/pixel. . . . . . . . . . . . . . . . . . . . . . . . . . 156

A.6. Respuestas del FG con parmetros = 0o, 45o, 90o, 135o, F =1/32 ciclos/pixel. . . . . . . . . . . . . . . . . . . . . . . . . . 157

A.7. Imgenes de texturas con incrementos en los detalles y lavariacin en la frecuencia espacial de los niveles de gris. . . . . 157

A.8. Norma del vector de caractersticas obtenido a partir de BFGpara cada una de las imgenes de la figura A.7. . . . . . . . . 158

A.9. Energa calculada para el primer nivel de descomposicin wavelet.160A.10.Energa calculada para el segundo nivel de descomposicin

wavelet. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161A.11.Energa calculada para el tercer nivel de descomposicin wavelet.162A.12.Energa calculada para el cuarto nivel de descomposicin wavelet.163A.13.Energa calculada para el quinto nivel de descomposicin wavelet.164A.14.Norma del vector de caractersticas basado en los coeficientes

de los detalles de la descomposicin wavelet, calculado paralas imgenes de la figura A.7 . . . . . . . . . . . . . . . . . . . 165

16 NDICE DE FIGURAS

ndice de cuadros

2.1. Mtricas utilizadas para calcular la similitud de caractersticasen sistemas CBIR . . . . . . . . . . . . . . . . . . . . . . . . . 47

4.1. Filtros paso bajo y paso alto para las trasformadas waveletdirecta e inversa . . . . . . . . . . . . . . . . . . . . . . . . . 85

5.1. Comparacin de la primera clasificacin realizada por difer-entes observadores, mediante mltiples matrices de confusin. 96

5.2. Comparacin de la segunda clasificacin realizada por difer-entes observadores, mediante mltiples matrices de confusin. 97

5.3. Comparacin de la primera y segunda clasificacin realizadapor los diferentes observadores, mediante mltiples matricesde confusin. . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

5.4. La tabla muestra la concordancia entre cada observador en laprimera evaluacin. . . . . . . . . . . . . . . . . . . . . . . . . 98

5.5. La tabla muestra la concordancia entre cada observador en lasegunda evaluacin. . . . . . . . . . . . . . . . . . . . . . . . . 98

5.6. La tabla muestra la concordancia entre cada observador en laprimera y la segunda evaluacin . . . . . . . . . . . . . . . . . 99

5.7. Resultados iniciales de la clasificacin con caractersticas basadasen BFG con y sin solapamiento en los campos receptivos. . . 104

5.8. Resultados de la clasificacin de los vectores de caractersticasbasados en BFG utilizando Weka. . . . . . . . . . . . . . . . . 104

5.9. Exito en la clasificacin mediante el algoritmo k-NN con difer-entes niveles de descomposicin y wavelets madre db1 a db4. . 105

5.10. Exito en la clasificacin mediante el algoritmo k-NN con difer-entes niveles de descomposicin y wavelets madre db5 a db8. . 106

17

18 NDICE DE CUADROS

5.11. Exito en la clasificacin mediante la red neuronal MLP condiferentes niveles de descomposicin y diferentes wavelets madre107

5.12. Resultados de la clasificacin de los vectores de caractersticasbasados en los coeficientes de la TWD mediante Weka. . . . . 108

5.13. Clasificacin mediante la norma de los vectores de caractersticas1095.14. Clasificacin mediante los componentes principales calculados

a cada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1105.15. Resultados de la clasificacin realizada sobre los valores obtenidos

mediante la aplicacin de la funcin discriminante de Fisher alos vectores de caractersticas basados en BFG y coeficienteswavelets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

5.16. Correspondencia entre el ndice de abollado basado en la fun-cin discriminante de Fisher y la apreciacin de los expertos. . 112

6.1. Resultados de relevancia en las respuestas a las consultas sobrela base de datos de 400 imgenes sintticas, usando la distanciadefinida en la ecuacin 6.8 . . . . . . . . . . . . . . . . . . . . 142

6.2. Resultados de relevancia basada en la distancia entre imgenesde abundancia para imgenes con abundancias generadas conpolinomios de Legendre 2D. . . . . . . . . . . . . . . . . . . . 145

Captulo1

Introduccin

Damos en este primer captulo una breve motivacin de los trabajos re-alizados. Indicamos las contribuciones que consideramos ms relevantes alestado del arte. Tras enumerar las publicaciones realizadas y en preparacin,presentamos la estructura de la tesis.

1.1. Motivacin

El rea temtica cubierta por esta tesis, el acceso a bases de datos deimgenes basado en contenidos (CBIR en ingls) es un campo frtil de apli-caciones y desarrollo de herramientas. Los primeros sistemas se dirigan acolecciones muy heterogneas, con pretensin de universalidad. La identifi-cacin del problema de la brecha semntica (semantic gap) di mayor valor alos sistemas con dominio de imgenes restringido. Se desarrollaron sistemaspara el acceso basado en contenidos a colecciones de imgenes de caras, deimgenes mdicas, de imgenes astronmicas, y un largo etctera. Estas apli-caciones se caracterizan porque el proceso de extraccin de caractersticases muy preciso y dirigido por la aplicacin, tambin la distancia empleadacomo medida de similitud est definida muy precisamente. As, los sistemasde CBIR de caras tempranos proponan la transformacin en componentesprincipales (PCA en ingls) como proceso de extraccin de caractersticas y ladistancia Eucldea como medida de disimilitud. Otro ejemplo: los sistemas deCBIR sobre colecciones de imgenes mdicas (i.e. MRI del cerebro) usan co-mo proceso de extraccin de caractersticas procesos de registro no lineal quemiden las deformaciones entre las imgenes. Sobre stas caractersticas lasmedidas de similitud pueden venir dadas, por ejemplo, por la transsformadaPCA del campo de deformacin y la distancia Eucldea sobre los vectores as

19

20 1.1. Motivacin

obtenidos. Los trabajos de esta tesis se enmarcan en esta tendencia, puestoque los dos sistemas propuestos tienen un dominio de definicin muy precisoy acotado, con procesos de extraccin de caractersticas especficos y medi-das de similitud o ndices bien definidas. El semantic gap produjo tambinconsiderables esfuerzos en la definicin de sistemas de realimentacin de lasconsultas que permitiran acotar la semntica implcita en la consulta, inter-actuando con el usuario. En nuestro trabajo no hemos tocado estos temas deninguna manera, puesto que al ser sistemas de semntica muy reducida notiene inters el modelado semntico.

1.1.1. Imgenes de papel reciclado

El primer problema tratado en esta tesis, la caracterizacin e indexacinde imgenes de papel reciclado con propsitos de control de calidad y reali-mentacin a los procesos de produccin expuesta en el captulo 5, surge porla solicitud de una empresa del sector (Echezarreta SA que luego pas a serPaperalia SA) que trataba de caracterizar la calidad del papel en trminosde un fenmeno que no est recogido en los estndares de calidad de papel: laformacin de ondulaciones y abolladuras en el papel al cabo de un tiempo dealmacenamiento o al pasar por condiciones especiales (ej. el recalentamientoen una fotocopiadora). Esta relacin se concret en dos proyectos, uno confinanciacin del Gobierno Vasco en el programa Universidad-Empresa, y otrocon financiacin del Ministerio de Ciencia y Tecnologa, en los cuales ha par-ticipado el doctorando. Parte de los resultados obtenidos es precisamente unsistema CBIR de gestin de las imgenes obtenidas por el departamento decalidad y que se instal en la empresa. Los trabajos tericos que se elaborarona raz de esta aplicacin son los que se describen con detalle en el captulo 5.

El problema del abollado es un excelente ejemplo de aplicacin de lastcnicas de caracterizacin de textura y nos ha dado la oportunidad de pro-fundizar sobre ellas. Entre las distintas aproximaciones, como las matricesde coocurrencia, escogimos las aproximaciones basadas en Filtros de Gabory Wavelets por que ofrecen la metodologa ms general y ms sistemtica.Las matrices de coocurrencia, por ejemplo, necesitan de bastantes intentosde prueba y error para fijar parmetros tales como la distancia entre pxelesconsiderada en cada tabla o las trasnformaciones adecuadas de la tabla paraobtener caractersticas discriminantes.

El problema del abollado, adems, tiene una caracterstica especfica, quese trata de caracterizar la textura global de la imagen. Esto se diferencia

1. Introduccin 21

mucho de las aplicaciones que realizan la segmentacin de la imagen basadaen texturas, puesto que la caracterizacin es local y homognea, mientras queen una imagen pueden convivir varias texturas y no es evidente como definirun abollado global, ni siquiera cualitativamente. Parte de las dificultadesencontradas se debe precisamente a la necesidad de inventar el mtodo deetiquetado de las imgenes.

1.1.2. Imgenes de reconocimento remoto

Hasta el momento, la literatura de sistemas CBIR para colecciones dereconocimiento remoto, que incluye las imgenes hiperespectrales, se basa enla extraccin de caractersticas espaciales. Sin embargo, los sensores de al-ta resolucin espectral dan informacin adicional que permitira caracterizarlas imgenes por los espectros de los elementos presentes en la escena, paradistiniguir imgenes con distribuciones espaciales similares de materiales dis-tintos que tienen respuesta similar en sensores de baja resolucin espectral(RGB o pancromtico). Es por ello que parece deseable definir ndices de lasimgenes basados en la informacin espectral. Tambin parece deseable queel proceso de indexacin sea eficiente, aplicable en un tiempo razonable y conrecursos razonables a un conjunto de imgenes relativamente grande.

Nuestro punto de partida ha sido el trabajo realizado en el grupo sobrela segmentacin no supervisada de imgenes hiperespectrales usando redesneuronales morfolgicas, ms precisamente Memorias Autoasociativas Mor-folgicas. Esta segmentacin se realiza mediante (1) la induccin de los end-members a partir de la imagen hiperespectral y (2) el clculo de las imgenesde abundancia, que nos dan la segmentacin deseada. Las tcnicas propuestasson no supervisadas y relativamente eficientes en trminos computacionales.Su mayor inconveniente radica en su componente aleatorio, esto es, distin-tas ejecuciones del mismo algoritmo pueden dar distintas segmentacionesy distintas caracterizaciones espectrales si se parte de condiciones iniciales(i.e. endmember inicial aleatorio). Si fijamos el proceso tomando siempre elmismo endmember inicial (i.e. el primer pixel) el proceso es completamentedeterminista.

La aplicacin al CBIR de imgenes hiperespectrales de estas tcnicassupone una extensin a un dominio de aplicacin nuevo y muy extenso.Adems supone la prueba de los algoritmos sobre un conjunto de datos am-plio (las imgenes sintticas ocupan medio terabyte en formato binario).

22 1.2. Contribuciones ms relevantes

1.2. Contribuciones ms relevantes

Las aportaciones ms relevantes de la presente tesis se encuentran enlos captulos 5 y 6. En ellos se realizan aplicaciones originales y se aportanmtodos y tcnicas novedosos. El captulo 2 proporciona una revisin delestado del arte en sistemas CBIR que trata de situar las contribuciones deesta tesis en su marco justo. Los captulos 3 y 4, y el apndice dado por elcaptulo 8, proporcionan una revisin de conceptos sobre Bancos de Filtrosde Gabor y Transformada Discreta en Wavelets que son imprescindibles parala comprensin completa del trabajo expuesto en el captulo 5, sin embargopueden considerarse desde un punto de vista didctico puesto que organizanlos conceptos de forma sinttica y muy accesible.

En el captulo 5 describimos la aplicacin de caractersticas de textura ala identificacin de la calidad de imgenes de papel reciclado. El fenmeno deinters es la aparicin de ondulaciones en la superficie del papel. A falta deun nombre estndar lo denominamos abollado. Esta aplicacin es comple-tamente nueva en la literatura conocida. Entre los precedentes, se encuentranaplicaciones de proceso de imgenes a nivel microscpico para tratar de deter-minar algunas propiedades del papel. Nuestras imgenes son macroscpicasy el tipo de estructuras que se buscan en las imgenes microscpicas no seencuentran en ellas. Tambin existen algunas aplicaciones de anlisis de im-genes para el estudio de fenmenos como el punto de ruptura del papel sujetoa traccin. En este caso el tipo de imgenes no tiene ninguna similitud conlas nuestras y las tcnicas de anlisis son radicalemente distintas. Por ltimo,algunos fenomenos de entintado del papel pueden ser similares en el aspec-to general de las imgenes, sin embargo la observacin detallada encuentrafuertes diferencias entre los tipos de imgenes que se producen en los doscasos.

La novedad del propio planteamiento del problema de cuantificacin visu-al del abollado, hace que tenga especial inters el proceso de etiquetado que serealiza de forma rigurosa por observadores humanos independientes y se es-tablecen las categoras mediante votacin. Encontramos resultados relevantessobre la concordancia de diversos observadores humanos de este fenmeno queson completamente novedosos. La seleccin de las caractersticas mediante larealizacin de procesos de clasificacin automtica supervisada da pie a ladefinicin del ndice de abollado que es la aportacin final del captulo. Estendice es validado mediante un proceso novedoso de comparacin por pares

1. Introduccin 23

de los valores del ndice y la observacin humana.En el captulo 6 presentamos nuestras ideas sobre la construccin de sis-

temas CBIR para imgenes hiperespectrales. En concreto, la extraccin deinformacin espectral para caracterizar las imgenes es infrecuente en la lit-eratura y cuando se hace se aplican soluciones triviales del tipo del espectromedio de la imagen, debido a la complejidad computacional y sensibilidad delos algoritmos de clustering que podran ser aplicados para obtener informa-cin ms detallada. Nuestra proposicin es relativamente eficiente desde elpunto de vista computacional puesto que implica slo un paso sobre la ima-gen y las operaciones que se realizan son computacionalmente ligeras. Por ellopensamos que puede ser aplicado a sistemas reales con grandes coleccionesde imgenes.

Nuestra aproximacin toma un punto de vista novedoso en el sentido deque en lugar de tratar de encontrar valores promedio como caracterizacindel contenido espectral de la imagen, lo que es habitual cuando se consideraun modelo de mezcla de gausianas, buscamos valores extremos que definen unrecubrimiento convexo de los datos (todos o gran parte de ellos). Este cambiode paradigma se debe a la adopcin del modelo de mezcla espectral (spectralmixing) que trata de modelar los pixeles a resolucin subpixel, buscando lacomposicin fraccional de los pixeles.

Desde el punto de vista computacional, el algoritmo propuesto para la ex-traccin de los endmembers es novedoso y forma parte de lo que podramosllamar Lattice Computing : una coleccin de mtodos computacionales basa-dos en operadores de retculos o en Teora de Retculos (Lattice Theory). Elalgoritmo est basado en un concepto novedoso: el de independencia mor-folgica (lattice independence en las nuevas tendencias de nomenclatura) yhace una utilizacin original de las Memorias Autoasociativas Morfolgicas.

Las bases de datos de imgenes sintticas pueden servir para la eval-uacin sistemtica de algoritmos de proceso y segmentacin de imgeneshiperespectrales. Existen pocos conjuntos de datos extensos accesibles paradichos procesos de evaluacin y ninguno tiene la complejidad del que hemosconstruido para la realizacin de los experimentos.

1.3. Objetivos de la tesis doctoral

En esta seccin vamos a enumerar los objetivos que persiguieron los tra-bajos de esta tesis doctoral. Algunos de ellos estn explcitos en la estructura

24 1.4. Publicaciones realizadas

de la propia memoria, otros han sido instrumentales para la realizacin delos trabajos y todos ellos marcan en alguna manera un hito o contribucin.Algunos son puramente formativos, no nos olvidemos que la tesis doctoral esun periodo formativo del investigador:

Revisin del estado del arte en sistemas CBIR.

Investigacin sobre procesos de extraccin de caractersticas de texturasen imgenes digitales.

Construccin de sistemas CBIR concretos: especializandose durante eltrabajo en las aplicaciones al control de calidad del papel reciclado y alas imgenes hiperespectrales.

Aplicacin de algoritmos de Lattice Computing a algn problema deinters prctico no trivial.

Construccin de una coleccin de imgenes hiperespectrales sintticasno trivial para validacin de algoritmos.

Experimentacin con algoritmos de clasificacin automtica en un do-minio realista de datos (e.g. imgenes de papel reciclado).

Prueba de la metodologa experimental en un dominio no trivial y re-alista (formacin).

Revisin de mtodos de segmentacin de imagen (Filtros de Gabor yWavelets) (formacin).

Revisin de tcnicas y algoritmos de Lattice Computing.

Transferencia de resultados a la empresa privada.

1.4. Publicaciones realizadas

Orlando Maldonado, David Vicente, Manuel Graa, CBIR IndexingHyperspectral Images. IGARSS 2005 IEEE Press, ISBN 0-7803-9051-2.

1. Introduccin 25

Orlando Maldonado, David Vicente, Manuel Graa, Alicia dAnjouContent based retrieval of hyperspectral images using AMM inducedendmembers inKnowledge-Based Intelligent Information and Engineer-ing Systems (KES 2005), Rajiv Khosla, Robert J. Howlett, and LakhmiC. Jain (Eds.) LNAI 3681 : 827-832 Springer Verlag ISBN 3-540-28894-5.

Manuel Graa, Orlando Maldonado, David Vicente Morphological in-dependence and hyperspectral image indexing in Mathematical Methodsin Pattern and Image Analysis, Jaakko T. Astola, Ioan Tabus, JuniorBarrera, (eds) SPIE vol. 5916 pp: 213-222 ISBN 0-8194-5921-6.

Jos Orlando Maldonado, David Vicente Herrera, Manuel Graa Ro-may. Visual texture characterization of recycled paper quality in Inno-vations in Hybrid Intellligent Systems, Advances in Soft Computing 44pp: 288- 295 Springer Verlag ISBN 978-3-540-74971-4

M. Graa, I. Villaverde, J. O. Maldonado, C. Hernandez Two LatticeComputing approaches for the unsupervised segmentation of Hyperspec-tral Images Neurocomputing, Accepted.

1.5. Publicaciones submitidas

J.O. Maldonado, M. Graa. Recycled paper visual indexing for qualitycontrol. Expert Systems with Applications. Under review.

1.6. Estructura de la memoria de la tesis

La presente memoria se estructura en los siguientes captulos:

En el captulo 2 se proporciona una revisin general de los principiosbsicos de los sistemas de recuperacin de imgenes basados en con-tenidos (CBIR). Tras una presentacin de los aspectos generales deestos sistemas y algo de historia, se presentan los principales sistemasencontrados en la literatura. Presentamos la arquitectura tpica de es-tos sistemas y desarrollamos en detalle cada uno de los elementos: lastcnicas de extraccin de caractersticas, las distintas medidas de simil-itud ms frecuentes en la literatura, los sistemas de organizacin de las

26 1.6. Estructura de la memoria de la tesis

bsquedas desarrollados a partir de los rboles de bsqueda, extendin-dolos a datos multivariante. Los procesos de retroalimentacin de labsqueda han cobrado protagonismo para solventar el problema de labrecha semntica y son presentados tambin. Por ltimo, dedicamosun tiempo a discutir los procesos y variables de observacin empleadosen la validacin de estos sistemas.

En el captulo 3 se introducen los Bancos de Filtros de Gabor (BFG),presentando su aplicacin para la caracterizacin de la textura. Latransformada de Gabor es la primera proposicin de una transformadacon localizacin espacial y frecuencial que permite disear de forma sis-temtica y elegante sistemas de filtros que explotan exhaustivamentela informacin en el espacio transformado de Fourier. En el apndicedamos algunos ejemplos didcticos de anlisis de seales mediane filtrosde Gabor. Los BFG han sido ampliamente utilizados para la caracter-izacin de la textura presente en las imgenes.

En el captulo 4 presentamos la Transformada Discreta de Wavelets(TDW). Dicha transformada ha sido introducida como un medio derealizar anlisis multiresolucin de las imgenes, que trata de efectuarla deteccin y anlisis de los objetos presentes en la imagen a distintasescalas. Presentamos el algoritmo de descomposicin piramidal tpicoy la trasformada en dos dimensiones que se utiliza en la imgenes. Unade las aplicaciones ms extendida de esta transformada es el anlisisde texturas y es de inters especial para nuestra aplicacin sobre lasimgenes de papel reciclado.

En el captulo 5 presentamos la aplicacin de tcnicas de indexacinde imgenes para la caracterizacin de la calidad del papel recicladoen trminos de la aparicin visual de un efecto que hemos denominadoabollado a falta de una caracterizacin apropiada en los estndaresactuales de calidad del papel. En este captulo realizamos en primerlugar unas consideraciones metodolgicas y describimos el etiquetadomanual realizado sobre las imgenes proporcionadas por una empresapapelera que originalmente propuso trabajar en este problema. Defin-imos las caractersticas de textura que vamos a utilizar, basadas enBancos de Filtros de Gabor y Transformada Discreta en Wavelets. Elobjetivo final es el establecimiento de un ndice dado por un valor es-calar que crezca monotonamente con el nivel de abollado percibido en

1. Introduccin 27

la imagen, para que pueda ser usado como una medida objetiva de lacalidad del papel. Para establecer la calidad de las caractersticas gener-adas realizamos un experimento de clasificacin supervisada probandouna batera de sistemas de construccin de clasificadores. Finalmente,proponemos un ndice de abollado con resultados de clasificacin com-parables a la observacin humana y con las propiedades deseadas.

En el captulo 6 presentamos nuestras ideas para la construccin desistemas CBIR para colecciones de imgenes hiperespectrales. Presen-tamos las imgenes hiperespectrales brevemente. La caracterizacin quebuscamos se basa en la descomposicin espectral de los pixeles. Paraesta operacin son crticos los sistemas de induccin de los endmembersen los que se basa dicha descomposicin espectral. Presentamos nue-stro algoritmo basado en la propiedad de independencia morfolgicadetectada mediante Redes Morfolgicas. Para ello hacemos una breverevisin de sus fundamentos. Presentamos la distancia entre imgenescalculada entre los conjuntos de endmembers que caracterizan a lasimgenes hiperespectrales en nuestra proposicin. Para validar nuestraproposicin realizamos experimentos de recuperacin sobre bases dedatos de imgenes sintticas.

En el captulo 7 presentamos lneas de trabajo futuro y nuestras con-clusiones sobre algunos aspectos de los temas tratados.

El captulo 8 contiene dos apndices que presentan de forma didcticael efecto de las transformadas de Gabor y de Wavelets.

28 1.6. Estructura de la memoria de la tesis

Captulo2

Recuperacin de imgenes basadaen contenidos

2.1. Introduccin

Desde que el hombre lleg a idear las representaciones grficas, estas sonuna rica fuente de expresin y comunicacin, sin embargo, nunca como hoylas imgenes han cobrado el protagonismo que ostentan en tantas reas delquehacer humano como las artes, los medios de comunicacin, la medicina,y la ciencia en general. El auge de los medios electrnicos y la informticahan permitido el aumento en la produccin y coleccin de imgenes digitalesde todo tipo. Se puede apreciar en la vida diaria que el uso domstico delas cmaras digitales y la fcil adquisicin de medios de soporte y almace-namiento masivo de informacin permiten generar y mantener colecciones deinformacin multimedial personal de gran tamao.

En otras reas ms especializadas como la medicina, las imgenes sonuna herramienta diagnstica cada vez ms frecuente en muy diversas modal-idades: resonancia magntica nuclear, PET, ultrasonidos, rayos X, etc.

En otras reas de las ciencias de la vida, el uso de imgenes es cada vezms frecuente para tareas como la monitorizacin de especies animales y veg-etales, incluyendo imgenes de reconocimiento remoto para monitorizacinde bosques, etc. Los microscopios electrnicos permiten capturar y contem-plar imgenes que muestran las caractersticas y comportamientos presentesen el mundo molecular y celular. En otros campos de la ciencia, por ejemploen Astronoma, se estn generando constantemente nuevas imgenes proce-dentes de telescopios de todo tipo, desde los grandes telescopios en rbita,hasta los observatorios ms locales.

29

30 2.1. Introduccin

Las tcnicas de teledeteccin, como las basadas en satlites proporcio-nan imgenes que son una rica fuente de informacin con aplicaciones en laagricultura, las ciencias forestales, la geologa o la seguridad entre otras.

La comunicacin a travs de Internet ha hecho posible que las imgenesgeneradas por muy diversas comunidades estn disponibles convirtindoseen una especie de gigantesco repositorio de informacin. En la actualidadsitios web dedicados a compartir informacin multimedia estn concentrandocantidades ingentes de esta informacin.

Son necesarios instrumentos de gestin y bsqueda en estas coleccionesde imgenes. Una de las aproximaciones ms elementales es proponer sis-temas para el manejo de colecciones de imgenes desarrollados a partir delos paradigmas convencionales orientados a documentos de texto. Las im-genes son etiquetadas o documentadas mediante el uso de palabras clave, quedescriben el contenido de la imagen. La recuperacin de imgenes en el sis-tema se realiza por medio de consultas textuales. El problema fundamental deesta aproximacin, es que las consultas textuales requieren la documentacino etiquetado previo de cada una de las imgenes que conforman el repositorio,lo que conlleva dos problemas bsicos [132]:

Es un trabajo tedioso y costoso que implica gran cantidad de tiempoen el proceso de documentacin o etiquetado de las imgenes

El etiquetado es siempre un proceso subjetivo que depende de la opininde la persona que lo hace. Por tanto, es fcil ver que, debido a la riquezaen informacin visual contenida en las imgenes, stas pueden tenermltiples interpretaciones y no es fcil poner cada detalle en forma detexto.

Para evitar estos problemas, Google ofrece el servicio de recuperacin deimgenes en web, basado en la informacin textual de la pgina en la cualest embebida la imagen. Obviamente la informacin contenida en la pginaweb puede dar lugar a muchas ambigedades debido a que la comunidad quecrea y mantiene esta informacin es heterognea y carece de control.

La alternativa a la bsqueda basada en anotaciones textuales, es realizarde forma automtica la indexacin de las imgenes mediante descriptores desu contenido calculados a partir de la propia imagen. Estos clculos estarnbasados en algoritmos de proceso de imagen digital y de visin por com-putador. Esta es la razn por la cual dichos sistemas se llaman sistemas derecuperacin basados en contenidos (CBIR, por sus siglas en ingls).

2. Recuperacin de imgenes basada en contenidos 31

Figura 2.1: Esquema de una consulta mediante ejemplo, en un sistema CBIR.

Los sistemas ms populares realizan las consulta-mediante-ejemplo (query-by-sample), en las que se presenta al sistema una imagen que contenga lascaractersticas visuales que deseamos buscar. Sobre sta, el sistema realiza elprocesamiento necesario para extraer los descriptores que forman el ndice dela imagen que llamaremos vector de caractersticas. Este vector es comparadocon los vectores de caractersticas de cada una de las imgenes que conformanla base de datos. La comparacin se realiza mediante una mtrica o funcinde similitud que permite recuperar una lista con el(los) elemento(s) que seaproximen mejor a la consulta realizada. La figura 2.1 ilustra el diagrama deflujo del proceso de consulta, que es la estructura bsica de un sistema derecuperacin basado en contenidos, de cuyos componentes hablaremos conmayor detalle en la seccin 2.3.

En este captulo haremos una revisin sobre los sistemas de recuperacinde imgenes basados en contenidos, abordando cada uno de los aspectosde su implementacin, los cuales constituyen por si mismos amplias lneasde investigacin. El captulo est organizado de la siguiente manera. En laseccin 2.2, comentaremos sobre algunos aspectos generales relacionados conlos sistemas CBIR, como el dominio de conocimiento y la semntica. En laseccin 2.3 enumeramos algunos de los sistemas ms conocidos y se hace unadescripcin de la arquitectura tpica de un sistema CBIR. La seccin 2.5 estdedicada al proceso de extraccin de caractersticas de la imagen, donde sehace referencia a los tipos habituales de caractersticas as como a las tcnicasdesarrolladas para su extraccin. En la seccin 2.6 hacemos una revisin delas diferentes mtricas definidas sobre los espacios de caractersticas y suimplementacin dentro de los sistemas CBIR. La seccin 2.7 est dedicada arevisar las tcnicas ms habituales para acceso rpido y eficiente a grandes

32 2.2. Aspectos generales

repositorios de datos. En la seccin 2.8 se analizan las herramientas quepretenden la realimentacin inteligente del proceso de consulta, las cualestienen cada vez ms importancia en los sistemas CBIR. Finalmente en laseccin 2.10 se ofrecen algunas conclusiones alcanzadas tras el proceso derevisin bibliogrfica que fue necesario para el desarrollo de este captulo.

2.2. Aspectos generales

Para el diseo y desarrollo de sistemas de recuperacin de imgenes basa-dos en contenidos, es importante tener en cuenta los requerimientos de cadagrupo de usuarios. Cabe preguntarse, qu buscan los usuarios, cmo lo bus-can y cmo juzgan lo que encuentran. Las respuestas a dichos interrogantesdemandan un conocimiento de las necesidades del usuario, que puede ser tanamplio como las reas en que stos desempean sus actividades.

Smeulders [142] habla de la importancia de tener en cuenta el contextosemntico de la imagen, a lo que llamaremos dominio de la imagen (imagedomain), para conseguir sistemas que lleguen a satisfacer las necesidades delusuario. En un dominio reducido, las imgenes presentan una variabilidadlimitada y son predecibles en sus aspectos ms relevantes, por lo cual es msfcil relacionar la interpretacin semntica de la imagen con sus caractersti-cas visuales primitivas. Ejemplos de colecciones de imgenes que definen undomino reducido son los catlogos litogrficos y las colecciones de imgenes derostros, con posicin, iluminacin y puntos de vista controlados. Por contra,en un dominio extenso, las imgenes se caracterzan por ser polismicas y susemntica puede ser descrita solo parcialmente. Ejemplos de imgenes extra-das de un dominio extenso, son las colecciones fotogrficas, o el conjunto delas imgenes disponibles en Internet. En este tipo de dominios, aspectos comola iluminacin, la oclusin y recorte de objetos, y el registro desde diferentespuntos de vista, son dificultades importantes, que deben tenerse en cuentaen el momento de disear sistemas de recuperacin. Estos aspectos tienenque ver con la brecha sensorial, que se refiere a la diferencia existente entreel objeto del mundo real y la informacin digital (computacional) capturadao registrada de la escena[142].

Para precisar los conceptos definimos semntica como la categorizacinde los objetos en funcin de algn criterio de similitud. De esta forma lasemntica de un usuario cuando realiza una bsqueda es la categora de ob-jetos que tiene en mente, la bsqueda que realiza debera estar guiada por

2. Recuperacin de imgenes basada en contenidos 33

la similitud que l tiene en mente. Por otro lado los algortmos de extraccinde caractersticas y la mtrica definida sobre este espacio de caractersticasinducen una cierta categorizacin que puede venir dada por el clustering delas imgenes. La falta de coincidencia entre estas dos categorizaciones esconocida como la brecha semntica. Usualmente el usuario no especifica deninguna manera su semntica por lo que la brecha semntica no es cuan-tificable ni formalizable. En dominios especializados (reducidos), la brechasemntica es usualmente pequea contrario a los dominios extensos, dondela brecha semntica es considerablemente mayor.

En [142] se identifican adems, tres tipos de bsqueda relacionados conlos intereses o propsitos del usuario al acceder a un sistema:

Las bsquedas por asociacin, que permiten a los usuarios realizar unaexploracin sobre la coleccin de imgenes, refinando de manera iterati-va la bsqueda. Estas son propias de colecciones generales de imgenesdel mundo real.

Las bsquedas especficas, en las cuales los usuarios buscan un elementoen particular, o una imagen que contenga un objeto como el que se hasuministrado en la imagen de ejemplo. Si el usuario tiene un objetivopreciso en mente, puede dar algunas de sus caractersticas e ir refinandola bsqueda hasta encontrar el objeto preciso. Estos sistemas puedenser adecuados para bsquedas en catlogos de arte, de componentesindustriales, etc.

Las bsquedas por categora, que permiten recuperar una imagen rep-resentativa de una clase o categora especfica. Pueden resultar tilessi se quiere introducir una imgen nueva al sistema, y es necesario es-tablecer a qu clase pertenece. Este tipo de sistemas puede encontrarseen entornos especializados, como catlogos de especies biolgicas.

Smeulders adems discute la necesidad de conocimiento a priori sobre el do-minio de las imgenes para salvar las diferencias semnticas y sensoriales.Este conocimiento se puede especificar mediante reglas de similitud sintcti-ca, reglas de similitud perceptual, condiciones fsicas y reglas topolgicas ygeomtricas.

Eakins [43] da ejemplos de posibles atributos que los usuarios puedenutilizar para recuperar imgenes, tales como:

34 2.2. Aspectos generales

la presencia de color, textura o forma particular, por ejemplo, un cuadri-latero rojo;

la presencia de un arreglo o un tipo especfico de objetos, por ejemplo,una bandada de pjaros; la descripcin de un evento particular, porejemplo, la entrega de premios a un deportista;

la presencia de individuos, lugares o eventos conocidos, como la torreEifel; emociones asociadas a una imagen, por ejempo alegra;

metadados, tal como la fecha de creacin de un fichero.

Exceptuando el primer tipo, cada posible consulta representa una abstraccinde mayor nivel a la anterior, que requiere de alguna entidad de conocimientoexterno para su validacin. As, Eakins hace una clasificacin de las consultasen tres niveles:

Nivel 1: Comprende recuperacin por caractersticas primitivas, comocolor, textura o forma.

Nivel 2: Comprende recuperacin por caractersticas derivadas (o lgi-cas), que implican algn tipo de inferencia lgica sobre la entidad, a suvez las divide en dos: recuperacin por objetos de un tipo dado (recu-perar imgenes con un coche) , o de un objeto o persona en particular(recuperar imgenes de la torre Eifel).

Nivel 3: Comprende la recuperacin por atributos abstractos, que re-quiere razonamiento de alto nivel sobre el significado y propsito de lasescenas descritas. Las divide en dos a su vez: recuperacin por even-tos o actividades conocidas (Encontrar imgenes con danzas folclricasrabes), y recuperacin por imgenes con contenido emocional o reli-gioso (recuperar imgenes que describan sufrimiento).

Podemos resaltar que la diferencia entre los niveles 1 y 2 est directamenterelacionada con la brecha semntica, con lo cual, los resultados en las con-sultas de los niveles 2 y 3 pueden satisfacer a los usuarios en sistemas con-trolados, con un estrecho dominio de la imagen.

2. Recuperacin de imgenes basada en contenidos 35

2.3. Ejemplos de Sistemas CBIR

La recuperacin de imgenes basada en contenidos o CBIR (por sus siglasen ingls Content based image retrieval) es una de las reas de investigacinms prolficas en los ltimos aos, muestra de ello es la gran cantidad de pub-licaciones que han sugido desde la dcada de 1980. Sin embargo, los avancesms significativos se registran a partir de la dcada siguiente. Dentro de lossistemas CBIR ms populares podemos citar el QBIC1 de IBM (Query ByImage Content) [48] y el Virage2 [64] que han evolucionado de tal manera quehan permitido su aplicacin en la gestin de video e informacin multimedia.La mayora de los sistemas desarrollados provienen de la academia y no hansido explotados comercialmente. Podemos mencionar algunos de los nombresms conocidos de sistemas o prototipos desarrollados en este mbito tal co-mo Chabot [115], Photobook 3[119] o Netra [99], que utilizan caractersticasde color y textura para describir el contenido de la imagen. Desde el iniciode la presente dcada, la produccin cientfica relacionada con los sistemasCBIR se ha llegado a incrementar de manera casi exponencial, como hancomprobado Datta et al., en [36]. Entre los sistemas desarrollados en estaltima dcada destaca el Blobworld [20], que no solo se fija en la extraccinde catactersticas por cada pixel, sino que efecta una segmentacin en re-giones teniendo en cuenta su ubicacin espacial y su tamao. QuickLook [27]es otro sistema que permite la recuperacin de informacin visual en bases dedatos extensas, teniendo en cuenta caractersticas del color y su distribucinespacial en la imagen, as como la forma por deteccin de bordes. En [89] sepresenta un sistema CBIR, que emplea informacin de la forma de los objetosen la imagen para recuperarla, mediante la extraccin de bordes. Un sistemadisponible y de libre distribucin con licencia GNU es el GIFT4[143] (GNUimage Finding Tool). En [85], [111], [44], [23], es posible encontrar ejemplosde otras propuestas de sistemas que implementan CBIR.

1http://wwwqbic.almaden.ibm.com/2http://www.virage.com3http://vismod.media.mit.edu/vismod/demos/photobook/4http://www.gnu.org/software/gift/

36 2.4. Arquitectura de los sistemas CBIR

2.4. Arquitectura de los sistemas CBIR

El abundante material escrito entorno a los sistemas CBIR en los ltimosaos ha sido recogido en varias revisiones exhaustivas. En [142], por ejemplo,se hace una revisin de las publicaciones realizadas hasta el ao 2000, y serepasan las arquitecturas propuestas. El anlisis revela que todos los mod-elos se ajustan a un marco para la implementacin que tiene los siguientescomponentes especficos:

clculo de caractersticas y anlisis sensorial,

un mdulo de interpretacin y dominio del conocimiento,

un mdulo de interaccin e interfaz de usuario,

y un mdulo de indexacin y almacenamiento.

Smeulders y sus colegas han concluido que en la mayora de las aproxima-ciones encontradas en la literatura se han limitado a proponer innovacionesde uno o dos de esos componentes. Sugieren, adems, que es necesario unmarco (framework) para sistemas CBIR que suministre una visin ms bal-anceada de los cuatro componentes constituyentes. El marco podra estarbasado en protocolos explcitos de comunicacin, que faciliten el dilogoentre cada uno de los mdulos.

Dentro de los sistemas propuestos en la presente dcada, en [91] encon-tramos un modelo de arquitectura tpico en el que existe un mdulo de con-sulta que realiza la extraccin de caractersticas (basadas en textura y color),un mdulo de bsqueda en la base de datos, y un mdulo que realiza un pro-ceso de realimentacin que afina la funcin de similitud con ayuda de lainteraccin del usuario, al igual que en [44], donde centran su atencin enun mdulo de entrenamiento de la funcin de similitud, para que identifiquelas imgenes relevantes en el dominio de imgenes mdicas. En [45] se adop-ta un enfoque similar, aunque la caracterizacin de las imgenes se basa enla descomposicin mediante quadtrees, y no tiene en cuenta ningn proce-so de realimentacin. En [26] se desarrolla un modelo que incluye un motorde razonamiento lgico, que mediante cierta descomposicin jerrquica dela imagen permite la comparacin mediante analogas. En [72] se proponeuna arquitectura de dos estados, refirindose con ello en una tcnica de

2. Recuperacin de imgenes basada en contenidos 37

bsqueda basada en dos vectores de caractersticas por imagen, que final-mente podramos encasillar en el marco clsico. Otras propuestas recientespueden ser encontradas en [77], [144], [112], todas ellas son de algn modoun caso particular del modelo general propuesto por [142].

Otra revisin de la bibliografa ha sido detallada en [107], la cual centrasu inters en las imgenes mdicas, pero tambin cita los sistemas clsicos.En ella se hace un anlisis de las necesidades y campos de aplicacin pre-sentes y futuros, llegando a proponer un sistema de recuperacin modularen el que se puedan cambiar fcilmente los vectores de caractersticas y sepuedan integrar con facilidad mdulos que implementen nuevas tcnicas derecuperacin, o mtodos eficientes de almacenamiento. Para la implementa-cion sera necesaria la definicin de mecanismos sencillos de plug-in paralos diferentes componentes. Una revisin del estado del arte reciente y mscompleta puede ser consultada en [36].

Podemos recoger las ideas expuestas hasta ahora aportando una estruc-tura general para un sistema CBIR. Si partimos de la figura 2.1 en la cualse aprecia el diagrama de flujo seguido en un proceso tpico de consulta me-diante ejemplos, podemos agrupar el sistema en mdulos, como se muestraen la figura 2.2, donde hemos aadido un mdulo de realimentacin. La granmayora de los sistemas encontrados tienen una arquitectura similar a sta,cuyos componentes pueden ser descritos por su funcionalidad de la siguientemanera:

La interfaz de usuario: debe permitir realizar las consultas y visualizarlos resultados de las mismas. En algunos casos incluso alimentar el sis-tema con nuevas imgenes o datos. Las consultas pueden ser realizadasmediante imgenes de ejemplo dadas al sistema, el diseo de grficos,esquemas o dibujos sobre un editor de imgenes que ejemplifiquen lascaracterticas grficas de la(s) imagen que se est(n) buscando, los datosnumricos que conforman el vector de caractersticas de la consulta ousando como imagen de ejemplo una extraida de la propia base de datosdel sistema CBIR.

El anlisis de imgenes: se encarga de realizar el procesamiento delas imgenes, su anlisis y extraccin de las caractersticas mediantetcnicas de visin. Aqu se calcula y cuantifica la informacin relativaal color, a las texturas, a los objetos o formas presentes, y a puntos deinters en la imagen a procesar. Estas operaciones se han de realizar

38 2.4. Arquitectura de los sistemas CBIR

Figura 2.2: Agrupacin de funcionalidades en mdulos de un sistema CBIR

tanto en las imgenes que conforman la la base de datos del sistemacomo sobre las imgenes de consulta.

La indexacin y almacenamiento: se encarga de generar, mantener yacceder a la estructura de almacenamiento de la informacin relativa alas imgenes contenidas en el sistema CBIR, esencialmente los vectoresde caractersticas. Un sistema CBIR contendr una cantidad enormede datos multidimensionales, por lo cual el tiempo de acceso requeridoresulta crtico. Para afrontar de manera eficiente y robusta este proble-ma, se utilizan tcnicas de gestin de datos multidimensionales, sobretodo las basadas en estructuras de tipo rbol como los R-tree.

Comparacin y funciones de similitud: Este es un aspecto fundamentalen los sistemas de recuperacin y est estrechamente relacionado con ladefinicin de los vectores de caractersticas. La mtricas o funciones desimilutid permiten comparar el vector de caractersticas de la consultacon los vectores de caractersticas de las imgenes almacenados en labase de datos del sistema, y establecer cul(es) es(son) ms cercana(s)o similar(es) a la consulta dada. Esta funcin puede ser la distancia

2. Recuperacin de imgenes basada en contenidos 39

Eucldea, o una funcin ms sofisticada segn el tipo de imagen sobreel que se est trabajando y la definicin de su vector de caractersticas.

La realimentacin o aprendizaje del sistema: Este es un aspecto queha venido tomando mayor relevancia a partir del artculo de revisinde Smeulders et al.[142]. Los expertos han observado que el sistemapuede ser ms eficiente si aprende de la interaccin con los usuarios.Con cada consulta realizada, el sistema establece las preferencias en losresultados de las consultas as como la satisfaccin ante esos mismosresultados. Con esta informacin el sistema puede modificar la funcinde similitud y/o la estructura de indexacin de los datos, para mejorarlos resultados en consultas posteriores. Con sto se pretende aproximarla semntica existente en la mente del usuario.

2.5. Extraccin de caractersticas

En este apartado describiremos los mtodos utilizados en el proceso deextraccin de caractersticas primitivas de la imagen, que es un aspecto claveen los sistemas CBIR y se apoya en las tcnicas de visin por ordenador.Los autores suelen distiguir entre dos tipos de caractersticas visuales: lasglobales, que pueden referirse al color o texturas presentes en toda la ima-gen y las locales, que estn definidas en reas especficas, y requieren unasegmentacin en regiones [43],[98].

2.5.1. Caractersticas de Textura

No hay un consenso general para una definicin formal o adecuada detextura, aunque podemos encontrar algunas definiciones como las siguientes:

En [117], se describe la textura como la repeticin de un patrn espacialbsico, cuya estructura puede ser determinista o estocstica;

Russ [133] la define como un descriptor de la variacin en la iluminacinlocal entre pxeles de una pequea vecindad.

El anlisis de texturas ha tomado un papel importante en reas como el anli-sis de imgenes mdicas, el reconocimiento remoto o la inspeccin industrial.Tambin ha sido tenido en cuenta a la hora de caracterizar las imgenes en

40 2.5. Extraccin de caractersticas

sistemas CBIR [142], [107], [98]. Los mtodos para anlisis de textura puedenser clasificados en cuatro categorias bsicas: mtodos estadsticos, mtodosestructurales, mtodos basados en modelos y mtodos basados en transfor-madas.

Los mtodos estadsticos. Una de las ms sencillas formas de comparartexturas es comparando sus estadsticos de primer orden, entendindoseestos como los que involucran pxeles simples. Se puede utilizar en estecaso el histograma normalizado de los niveles de gris de la imagen, queproporciona una estimacin de la funcin de densidad de los niveles degris, y comparar sus estadsticos como la media, mediana o varianza.Un mtodo de ms alto orden es la matriz de coocurrencias [65]: dadauna imagen f(x), su matriz de coocurrencias Md para un vector dedesplazamiento d se define como:

Md(i, j) = Card {(s, r) : r s = d, f (s) = i, f (r) = j} ,

donde r, s son posiciones de pxeles en la imgen. Es decir, cada posi-cinMd(i, j) de la matriz es el nmero de ocurrencias del par de nivelesde gris i y j que estn separados por el vector d. Sobre la matriz decoocurrencia se han definido un conjunto de descriptores como la en-erga, probabilidad mxima, entropa, correlacin, etc, utilizados paraprocesos de comparacin y clasificacin.

Mtodos estructurales. Los mtodos estructurales definen las texturascomo una composicin de elementos primitivos bien definidos, por ejem-plo, lineas paralelas regularmente espaciadas [12], concibiendo las tex-turas reales o naturales, como una distorsin de estas texturas ideales.Otros enfoques pueden considerar a las texturas como una coleccin deobjetos primitivos similares (pero no identicos) distribuidos con algnpatrn de repeticin. La caracterzacin de las texturas bajo este en-foque puede realizarse calculando propiedades estadsticas sobre estadistribucin de elementos, o las reglas de distorsin y/o ubicacin .

Mtodos basados en modelos. Estas tcnicas estiman los parmetros deun modelo sobre los pxeles de la imagen. Los parmetros del modelodescriben las cualidades de las texturas. Ejemplos de tales tcnicas sonlos modelos autoregresivos [137], los campos aleatorios de Markov [22]y los fractates [120].

2. Recuperacin de imgenes basada en contenidos 41

Mtodos basados en transformadas y procesado de seal. Se han apli-cado tcnicas habituales en el procesamiento de seales, que permitenanalizar la imagen, aplicando filtros para obtener caractersticas rela-cionadas con la orientacin o la magnitud de los componentes frecuen-ciales presentes en las texturas. Dentro de estos mtodos podemos en-contrar los que se aplican en el dominio espacial, mediante aplicacinde operadores de bordes como las mscaras Laplacianas o de Roberts[88], [116], y las basadas en momentos invariantes [70], [93]. Tambin sehan utilizado tcnicas aplicadas en el dominio de Fourier, que propor-cionan informacin sobre la potencia del espectro [106], o realizan unasegmentacin del plano transformado, discriminando los diferentes com-ponentes frecuenciales [162]. Debido a que la transformada de Fourierproporciona informacin slo en el dominio de la frecuencia, la trans-formada enventanada de Fourier, tambin llamada transformada deGabor, ha sido una alternativa que permite operar tanto en el dominioespacial como en el de Fourier [37], [156], [153]. El diseo de Bancosde Filtros de Gabor ha sido ampliamente aplicado a la clasificacin,segmentacin y recuperacin de imgenes texturadas [103], [166], [62].En el mismo sentido, la Transformada Discreta Wavelet [101] tambinha sido aplicada al anlisis de texturas, [157], [71], y especialmenteimplementada en prototipos de sistemas CBIR [91], [89], [138].

2.5.2. Caractersticas de Color

El color ha sido una de las caractersticas ms utilizadas en la recuperacinde imgenes. Un espacio de color es una representacin numrica mediante laque se puede especificar cualquier color. Por ejemplo, el espacio RGB, se basaen la representacin de un color como la suma de tres seales en las bandascromticas bsicas: El rojo, el verde y el azul (Red, Green, Blue). Por tanto,en una imagen con representacin del color en el espacio RGB, cada pxelcorresponde a un punto en un espacio tridimensional. Cada banda o compo-nente, toma valores dentro de un rango determinado por el mximo valor encada banda cromtica, As pues, es evidente que el poder de discriminacinen un espacio de color, es superior al que tenemos en la escala de grises.

La extraccin del histograma del color propuesta por Swain y Ballard[148], es una de las tcnicas ms utilizadas en los sistemas CBIR, en ella sedetermina la proporcin de pxeles de cada color en la imagen. El histogra-ma puede ser almacenado en la base de datos y en tiempo de bsqueda, el

42 2.5. Extraccin de caractersticas

usuario determina la proporcin de color deseado en las imgenes recuper-adas o enva una imagen de ejemplo para que su histograma sea extrado ycomparado con los almacenados en la base de datos. Mejoras en la tcnicadel histograma de color se han introducido en [146] que incluyen histogramasde color acumulativos. Otras aproximaciones buscan reducir la cantidad deespacio de almacenamiento requerida por los histogramas, como la propuestapor [118], que utiliza caractersticas que denomina momentos de cromatici-dad (chromaticity moments) que permiten capturar el contenido espectral dela imagen en una representacin compacta. La indexacin mediante Hashingde caractersticas de color (Color-card) invariantes a iluminacin y puntosde observacion son propuestas en [54]. La agrupacin por regiones de colores sugerida en [55], como alternativa al uso de histogramas.

Hay dos asuntos crticos que son abordados con frecuencia en la bibli-ografa. Por un lado, la variabilidad que se puede presentar durante el registrode una imagen, en trminos del punto de vista de la cmara, la iluminacin ola reflectancia, para lo cual Gevers y Smeulder [54], por ejemplo, proponen unconjunto de caractersticas invariantes a tales aspectos. Por otro lado se hapropuesto el uso de otros espacios de color, los cuales parecen correspondermejor a la percepcin humana de la similaridad entre colores. As, los es-pacios de color HSI y HSV (Matiz, saturacin, intensidad),(hue, saturation,instensity/value) son habitualmente utilizados [53], [170], [168], [35], [24], de-bido primero a que la intensidad puede ser separada de la informacin delcolor en la imagen, segundo a que las componentes intensidad y saturacinestn muy relacionadas con la percepcin humana del color, y tercero, por suspropiedades de invarianza frente a iluminacin y orientacin de la cmara,lo que lo hace adecuado para CBIR [142]. Otros espacios de color utilizadosen recuperacin de imgenes son el espacio CIE XYZ [118], CIELUV [55],el CIELAB [96], entre otros.

2.5.3. Caractersticas de formas

Aunque hay evidencia sicolgica de que los objetos son reconocidos primer-amente por su forma [13], la segmentacin automtica de los objetos en lasimgenes es un problema no solucionado. Incluso en dominios muy espec-ficos la segmentacin totalmente automatizada causa muchos problemas yno es fcil de realizar. El problema es considerablemente complejo cuandohablamos de imgenes del mundo real que pueden no tener un fondo ho-mogeneo, o en las cuales existen varios objetos que se solapan. La mayora

2. Recuperacin de imgenes basada en contenidos 43

de los sistemas CBIR que incluyen recuperacin mediante la caracterizacinde formas, muestran un buen rendimiento con imgenes que presentan obje-tos fcilmente identificables, que pueden ser aislados del resto de la imagen,condicin que no es habitual en la mayoria de las imgenes reales.

Para caracterizar las formas presentes en una imagen, podemos dividirlas tcnicas en tres categoras:

Las basadas en el contorno del objeto. En este caso es habitual calcularuna firma (una funcin 1D) del contorno de la imagen, que puede serusada directamente como caracterstica o sobre ella se pueden calcularotras caractersticas de dimensin inferior. [165], [167], [171] [154], [114],[4], [7].

Las basadas en mapas de bordes, que se aplican a imgenes en las quees muy difcil realizar una identificacin precisa de los objetos. Estosmapas de bordes no permiten obtener un contorno cerrado que defina elobjeto, pero son utilizados definiendo distancias apropiadas. [79], [169],[54], [112], [89].

Las basadas en regiones, donde las caractersticas se calculan como fun-cin de la regin en la imagen ocupada por el objeto y no directamentesobre la curva 2D que define el contorno. [20], [5], [173].

En el caso de procesado de imgenes basado en el contorno del objeto, en[165] y [167] se propone calcular los descriptores de Fourier sobre la firma delcontorno para caracterizar la imagen. Como firma se utiliza la distancia alcentroide, que viene dada por la expresin:

f (t) =

(x (t) xc)2 + (y (t) yc)2, (2.1)

donde (xc, yc) es el centroide de la imagen, t = 1,..N, es el ngulo del radiosobre el que estamos midiendo la distancia del contorno al centroide y vienedado por un muestreo uniforme entre 0 y 360 grados; as, el contorno delobjeto es digitalizado en N puntos. La distancia al centroide no est biendefinida para imgenes con objetos que tengan contornos no convexos. Latransformada discreta de Fourier de f (t), viene dada por la expresin:

44 2.5. Extraccin de caractersticas

F (u) =

(1

N

)N1t=0

f (t) ej2piutN ,

=

(1

N

)N1t=0

f (t) (cos (2piut/N) jsen (2piut/N)) . (2.2)

Dnde u = 0, ..., N2, y cada coeficiente F (u) es un descriptor de Fourier.

Para indexar la forma, Wong y sus colegas [165] toman la magnitud de latransformada, y la normalizan por el valor F (0):

|F (u)| =(

1

N

)(N1t=0

f (t) cos (2piut/N)

)2+

(N1t=0

f (t) sen (2piut/N)

)2,

DF =|F (u)||F (0)| , u = 1, 2, ...,

N

2. (2.3)

As obtenienen un conjunto de descriptores invariantes a traslaciones,escalado y rotacin. Un interesante estudio sobre la aplicacin de descriptoresde Fourier a diferentes firmas del contorno es realizado en [171].

Como ejemplos de otras aproximaciones podemos ver la propuesta deTrazegnies y sus colegas [154], quienes utilizan los modelos ocultos de Markovpara comparar las secuencias de esquinas obtenidas a partir del contorno. Losautores afirman que el mtodo es resistente al desplazamiento o prdida delas esquinas. En [114], se propone un mtodo para recuperar imgenes enconsultas donde el contorno es slo parcialmente visible. En [4], se proponela funcin de diferencia de giro; el contorno es submuestreado en N puntosque determinan una resolucin, y la informacin del ngulo entre cada parde segmentos que une dichos puntos es utilizada para caracterizar la imagen;para la comparacin se tiene en cuenta la correspondencia entre regiones delpolgono que son consideradas similares y el nmero de vrtices contenidosen dichas regiones. La funcin de giro y los descriptores de Fourier sobre elcontorno son utilizados por Antani y sus colegas en [7], para caracterizar elcontorno sobre imgenes de vrtebras tomadas mediante rayos X.

Respecto a las aproximaciones basadas en mapas de bordes, En [79] y[169] se propone el uso del histograma de direccin de bordes para repre-sentar informacin general de la forma en la imagen. En ambas propuestas,

2. Recuperacin de imgenes basada en contenidos 45

los bordes son extrados previamente con un operador de Canny; ya que es-ta aproximacin puede ser invariante a escalado y traslacin, pero no a larotacin, en [79] los autores proponen un suavizado del histograma para dis-minuir el efecto de la rotacin. En [54], se proponen histogramas de bordesinvariantes al color, con el fin de detectar objetos similares con independenciadel punto de vista registrado. En [112] se utiliza un histograma de cambiosde direccin del gradiente para representar la informacin global de la formacontenida en la imagen. En [89], se propone aplicar la Transformada DiscretaWavelet al mapa de bordes de la imagen, y utilizar los coeficientes normaliza-dos como representacin de la forma. En [38], se proponen tcnicas basadasen contornos activos o plantillas deformables, para calcular la similitud dela silueta proporcionada como consulta y el objeto presente en la imagen, lacual ha sido prepocesada para extraer sus bordes. El grado de concordan-cia entre la plantilla deformada y el objeto, asi como la energa requeridapara deformarla, son utilizadas para derivar la funcin de similitud. En [6]se propone una variacin de la transformada generalizada de Hough paracomparar la silueta dada como consulta con el mapa de bordes de la imagen,aprovechando la robustez de la transformada para la identificacin de objetosen imgenes no segmentadas.

En caso de las consultas basadas en regiones, en [20] se propone un mtodoque utiliza informacin del color y la textura para agrupar pxeles en regionessimilares y detectar objetos aislado, los cuales son indexados por cada regin.En [122] se utiliza una representacin de la forma basada en regiones, en laque tras una segmentacin previa, y la ubicacin del objeto de inters, seutiliza una rejilla de celdas cuadradas de tamao fijo que es ubicada sobre elobjeto para cubrirlo en su totalidad, se asigna uno a cada celda con al menos25% de pxeles pertenecientes al objeto de inters, y cero a las dems; sobreesta rejilla se calculan algunas propiedades geomtricas (mayor y menor eje,excentricidad, centro de gravedad, etc) que luego son almacenadas para surecuperacin; los autores proponen algunas transformaciones para invarianzaa escalado, traslacin y rotacin. En [173], se propone un sistema en el quese realiza una consulta introduciendo el dibujo a mano alzada de una silueta,y seleccionando el color y la textura del objeto deseado. El sistema buscaregiones candidatas mediante la informacin de color y textura previas, yluego trata de ajustar la silueta de entrada, mediante tcnicas de comparacinde plantillas deformables. Esta aproximacin, al igual que en [38], requierende un alto coste de procesamiento.

46 2.6. Mtricas y funciones de similitud

2.5.4. Relaciones espaciales de regiones y puntos de in-ters

Cuando se tienen caractersticas calculadas sobre diferentes entidades enuna imagen, las relaciones entre ellas tambin pueden ser usadas para pro-cesos de recuperacin. La informacin espacial es un aspecto utilizado, porejemplo, en sistemas de informacin geogrfica. Si se tiene en cuenta la es-tructura de la imagen, junto a las caractersticas visuales de las partes uobjetos dentro de sta, se pueden representar las relaciones espaciales, comopor ejemplo, algn tipo de orden jerrquico u otra relacin entre los objetos.

Entre las tcnicas utilizadas para realizar las bsquedas en coleccionesde imgenes usando informacin sobre las relaciones espaciales entre obje-tos, est la indexacin icnica formulada por Chang en [21], quien propusouna estructura para datos pictricos llamada 2D-String. Segn esta propues-ta, la informacin espacial contenida en una imagen del mundo real, puedeser representada mediante una matriz de caracteres, donde cada celda corre-sponde a un objeto en la imagen y la organizacin de la matriz viene dadapor la distribucin espacial de los objetos de la imagen. Modificaciones a losalgoritmos basados en dicha estructura son propuestos en [73], [32] y [92].En [159] Wang propone una tcnica similar, pero basada en los rectngulosenvolventes mnimos (MBR) para representar los objetos en cada imagen ymodelar la informacin espacial como las relaciones entre estos rectngulosenvolventes. En [35] se implementa un sistema CBIR que se basa en grafosde proximidad espacial, construidos sobre los objetos de la consulta y las re-giones de color detectadas en las imgenes. En [47], se propone un mtodo derecuperacin de imgenes basada en regiones, que comprende dos pasos prin-cipales: una segmentacin gruesa, basada en la cuantizacin del color en elespacio RGB y una descripcin fina de las regiones, considerando la distribu-cin del matiz. La informacin espacial es almacenada mediante un grafo deregiones adyacentes, en el que cada nodo contiene informacin relativa a laregiones (rea, distribucin de color, posicin, contornos).

2.6. Mtricas y funciones de similitud

Una vez definidas las caractersticas empleadas para describir cada ima-gen, stas se reunen en un vector o un conjunto de vectores de caractersticasque representarn a la imagen. Datta [36] ha llamado a esta representacin

2. Recuperacin de imgenes basada en contenidos 47

Nombre Expresin

Distancia Manhatan d (va, vb) =n

i=1 |va (i) vb (i)|

Distancia Ecucldea d (va, vb) =

(va vb)T (va vb)Distancia Minkowsky d (va, vb) = (

ni=1 (va (i) vb (i))p)1/p

Distancia Mahalanobis d (va, vb) =

(va vb)T 1 (va vb)Distancia Canberra d (va, vb) =

ni=1

|va(i)vb(i)||va(i)|+|vb(i)|

Distancia Chebyshev d (va, vb) = maxni,j=1 |va (i) vb (j)|

Cuadro 2.1: Mtricas utilizadas para calcular la similitud de caractersticasen sistemas CBIR

la firma de la imagen. Para realizar consultas, es necesario especificar unamedida de similitud, o mtrica que permita comparar imgenes y presentarlas respuestas en una lista ordenada. En el caso ms simple, si la imagen estrepresentada por un vector, se puede adoptar una mtrica conocida, e.g. ladistancia eucldea, como medida de similitud en el espacio de caractersticas,tal como se hace en [79], aunque algunos autores sostienen que no es unabuena aproximacin a la percepcin de similitud en los humanos [135]. Enlos casos ms complicados, el conjunto de caractersticas constituye un con-junto de datos heterogneos para los que no est definida una nica funcinde similitud.

Otras mtricas alternativas a la distancia euclidea, son la distancia deManhattan o city-block [27], al ser considerada estadsticamente ms robus-ta, as como la distancia de Mahalanobis [47]; la distancia de Canberra esutilizada para comparar caractersticas de textura en [83]; la distancia deChebyshev es utilizada en [94] para realizar la comparacin de vectores decaractersticas una vez que han sido proyectados en el espacio topolgicotangente al espacio de caractersticas de la imagen. La tabla 2.1 muestraun resumen de las mtricas o medidas de distancia mencionadas junto a susexpresiones.

En los sistemas desarrollados para colecciones de imgenes con dominioextenso, e. g. colecciones fotogrficas; las imgenes son representadas por

48 2.6. Mtricas y funciones de similitud

colecciones de caractersticas heterogneas, algunas de ellas expresadas enforma de vectores, grafos, etc. Esto es, se tienen distancias individuales entrevectores de caractersticas del mismo tipo, y una medida de similitud globalque combina las individuales. Esta ltima se obtiene dando diferentes pesos alas distancias calculadas sobre las caractersticas comunes. As, una definicinrecurrente de la medida de similitud (o disimilitud) general para dos imgenesI1 e I2, est dada por la expresin siguiente [27] :

D (I1, I2) =ni=1

widi (v1,i, v2,i) , (2.4)

donde di es la mtrica o distancia sobre la caracterstica i; v1,i, v2,i son losdatos extrados correspondientes a dicha caracterstica en cada imagen, y wi,es el peso asignado a esta caracterstica en la medida de similitud global.Esta definicin de la similitud global permite su refinamiento de acuerdo ala importancia que los usuarios pueden darle a cada caracterstica, medianteel proceso de realimentacin por relevancia que ser discutido ms adelante,y que es una de las tcnicas llamadas a reducir la brecha semntica [142].

Un trabajo interesante sobre las medidas de similitud, con referencias aestudios psicolgicos puede ser encontrado en [135]. Santini y Jain parten dela asuncin generalizada en la literatura de que la similitud entre imgenes(o disimilitud) es una distancia en algn espacio de caractersticas, que seasume como un espacio mtrico. Los autores hacen una distincin entre ladistancia percibida (calulada como una mtrica en el espacio formal) y ladistancia juzgada (la que es accesible experimentalmente) y posteriormenterealizan una comparacin entre distancia geomtrica con sus axiomas, y lasfunciones de similitud propuestas en la literatura.

Una de las conclusiones ms interesantes que presentan los autores serefiere a la verificacin de los cuatro axiomas de las mtricas sobre la distanciajuzgada:

Autosimilitud: A es tan parecido a A, como B es tan parecido a B.

Minimalidad: La distancia de A a A, es ms pequea que la distanciade A, a cualquier otra cosa.

Simetra: Distancia de A a B es igual a la distancia de B a A.

Desigualdad triangular: La distancia de A a B es menor o igual que lasuma de las distancias de A a C, y B a C.

2. Recuperacin de imgenes basada en contenidos 49

En los experimentos con sujetos humanos, los dos primeros son cuestionables,el segundo no se cumple y el cuarto no se puede comprobar.

De otro lado, para caractersticas especficas, se han definido mtricaspuntuales de comparacin. Cuando se extrae el histograma de color, porejemplo, la interseccin de los histogramas propuesta en por Swain y Ballard[148] es utilizada como funcin de similitud en gran cantidad de propuestas,aunque surgen otras alternativas como la distancia de Minkowsky [112] o loshistogramas acumulativos.

Otras medidas de similitud ms complejas pueden surgir, dependiendode la representacin que se haga de la imagen, como en [2], donde Ahmad yGrosky hacen una representacin jerrquica de la imagen mediante quadtrees,segn la distribucin de los puntos de inters encontrados en la imagen,-particularmente se usan las esquinas en esta propuesta-. Por tanto la com-paracin entre imgenes equivale a una comparacin entre rboles, con locual la funcin de similitud se asocia al peso obtenido de los nodos de cadarbol.

2.7. Mtodos de acceso y bsqueda en base dedatos

En las bases de datos de los sistema CBIR, normalmente cada imagenmantiene una relacin biunvoca con su vector de caractersticas que es elmismo que se utiliza para las operaciones de comparacin mediante la funcinde similitud y la posterior recuperacin. Si la base de datos es pequea, ya pesar de que el vector de caractersticas tenga una alta dimensionalidad,una bsqueda exhaustiva secuencial, da resultados aceptables respecto a larapidez de la consulta. Al crecer la base de datos, se hace necesario utilizarestructuras definidas sobre las bases de datos que permitan un acceso rpidoy no se deterioren con el aumento del tamao de la base de datos El uso deestructuras tpicas de acceso a datos de clave nica resulta ineficiente porla alta dimensionalidad de los vectores de caractersticas, de manera que losrboles binarios, los mtodos basados en B-trees, o tablas hashing, resultanpoco adecuados para los sistemas CBIR. Ya que estas estructuras se basan enla existencia de un orden total, que en general no se garantiza en los espaciosde alta dimensin.

Dentro de los tipos de consulta ms habituales que se pueden realizar en

50 2.7. Mtodos de acceso y bsqueda en base de datos

un sistema CBIR o en general en un sistema de datos multidimensionalesestn los siguientes: a) consultas exactas, que buscan un elemento especficoen la base de datos; b) Consultas por rango, que buscan elementos dentrode un rango determinado; c) Consultas del vecino ms cercano, en las quese busca el elemento ms cercano a un elemento particular dado dentro delespacio de caractersticas. Este ltimo tipo es el ms habitual en sistemasCBIR.

Cuando hablamos de bases de datos de alta dimensionalidad, las estruc-turas de rbol han demostrado ser la ms adecuadas para la gestin y larealizacin de consultas. Una de las propuestas pioneras es el R-tree [63],que es una estructura arborea balanceada, especial para datos bidimension-ales, habituales por ejemplo, en los sistemas de informacin geogrfica. Sueficiencia se basa en la ptima distribucin de una jerarqua de rectngulosenvolventes mnimos (Minimal boundary rectangle - MBR). En dicha estruc-tura los nodos hoja contienen un identificador del objeto al que apuntany el MBR que lo contiene. Los nodos internos representan una sucesin deregiones rectangulares minimales que cubren los nodos en el nivel inferior.Las regiones del mismo nivel pueden solaparse y su unin no necesariamentecubre todo el espacio.

Sin embargo, esta estructura inicialmente fue desarrollada para manejardatos en dos dimensiones, de manera que al aumentar la dimensin se pierdeeficiencia. Variantes del R-tree, eficientes para tres dimensiones, han sidopropuestas en la literatura, tal como el R+-tree [140], que maneja regionesdisjuntas y el R*-tree que optimiza los algoritmos cuando son usados en datosde ms de dos dimensiones y disminuye el solapamiento de los nodos, aunquecon un aumento en el coste de memoria y procesamiento en las operacionesde insercin de nodos. El R*-tree ha sido utilizado en el QBIC [48], dondela textura se representa por vectores en tres dimensiones, mientras que laforma se representa mediante un vector de 20 valores. Para la textura se hautilizado directamente el R*-tree, y para la forma se realiza una reduccinde la dimensionalidad mediante el clculo de los componentes principales,obteniendo vectores de dos o tres componentes, que son adecuados para sergestionados mediante dicha estructura.

Para poder gestionar datos en espacios de alta dimensin han surgidoalgunas propuestas basadas tambin en el R-tree tales como el TV-tree [97],que trata de utilizar en forma dinmica los vectores de caractersticas em-pleando solo aquellas caractersticas necesarias para discriminar los objetos;el X-tree [11] que aade un algoritmo de divisin de regiones que busca mini-

2. Recuperacin de imgenes basada en contenidos 51

mizar el solapamiento, adems de incluir supernodos con el fin de manteneruna estructura jerrquica tanto como sea posible; el Pyramid-tree [10] quegestiona pirmides en lugar de rectngulos, el SPY-TEC [90] que divide elespacio vectorial en hiperespeferas, etc. Una completa revisin sobre mtodosde acceso y gestin de datos espaciales puede ser consultada en [52].

Algunos autores han tratado de optimizar el proceso de consulta, combi-nando las estructuras de rbol con otro tipo de tcnicas como en [9], donde sepropone un mtodo que precalcula los resultados de una bsqueda del vecinoms cercano, mediante el clculo de las celdas de Voronoi de cada punto.La informacin obtenida es almacenada en una estructura de indexacin queposibilita un acceso eficiente posterior. La estructura tiene la ventaja de serdinmica y permitir su actualizacin. En [168], se propone un mtodo deindexacin, basado en la agrupacin (clustering) de los vectores de carac-tersticas de la base de datos, soportados por una estructura de rbol; paraoptimizar el acceso a los nodos hoja, que pueden corresponder a cluster convarios vectores, se usa una tcnica basada en la desigualdad tringular quereduce el nmero de comparaciones. En [2], se propone un mtodo de in-dexacin jerrquico, basado en el concepto de firmas de archivos (signaturesfiles) y la comparacin mediante quadtrees. Cada nivel de la jerarqua reduceel espacio de bsqueda, permitiendo un nivel de bsqueda ms refinado slopara las imgenes potencialmente relacionadas en la base de datos.

Otros, como Ciocca [27], han evitado emplear estructuras complejas, im-plementando un mtodo de filtrado bastante sencillo, que permite eludir lacomparacin secuencial de tems en la base de datos; su tcnica se basa enuna variante de la desigualdad triangular. El mtodo propone filtrar el nu-mero de imgenes que se van a comparar con una consulta Q, a travs de lacomparacin previa de todas las imgenes I de la base de datos con una(s)imagen(es) de referencia K dentro de la base, llamada clave, con lo cual sedetermina y guarda la distancia entre ellas. Basado en que la medida de simil-itud cumple con la desigualdad triangular d(I,Q) >= |d(I,K) d(Q,K) sepuede reducir de manera significativa el nmero de imgenes a comparar. En[49], se propone una tcnica que realiza un mapeo de los vectores de altadimensin al espacio 1D, para luego explotar las eficiencia en la bsquedaofrecida por el B+-tree.

52 2.8. Aprendizaje y realimentacin por relevancia

2.8. Aprendizaje y realimentacin por relevan-cia

Para mejorar el rendimient