Recuperación Basada en
Contenido
M. Andrea Rodríguez Tastets
DIIC - Universidad de Concepción
http://www.inf.udec.cl/~andrea
Búsqueda por contenido

Es una metodología de recuperación de información basada en el
contenido con respecto al dominio de aplicación del proceso de
recuperación. Usa un análisis y procesamiento digital para general
descriptores (meta-data) a partir de los datos. Los méritos
principales de sistemas basados en el contenido son:



Soporta el procesamiento de consultas visuales (o audio)
La consulta es intuitiva y amistosa al usuario
La generación de los descriptores es automática, siendo
objetiva y consistente.
Media

Definición: Media se refiera a todo medio de
comunicación. Multimedia entonces, se refiere a
la combinación de medios de comunicación, tales
como imágenes, video, gráficos, señales de
audio, texto, símbolos, etc. Desde una
perspectiva
de
computación,
información
multimedial puede ser representada usando
estructuras de datos o clases de objetos.
CBR

CBR puede ser clasificada en tres categorias,
correspondiendo a auto-asociación, heteroasociación, y combinación de las dos primeras.
Estos tres tipos de recuperación son: búsqueda
dentro de una clase de objetos, navegación
entre clases de objetos, correspondencia
parcial de objetos complejos.
CBR versus Clasificación

Un área relacionada a CBR es el reconocimiento de
patrones, clasificación de patrones ya que ambas
disciplinas usan descriptores y medidas de similitud.
Clasificación de patrones particiona el espacio de
descriptores en subespacios, posiblemente disjuntos
para clases de patrones distintos. En CBR, por otro lado,
lo central en el objeto. La similaridad tiene un rol
principal y no cumple sólo la función de entrenamiento
que apoya la clasificación, si no que es objetivo final.
CBR versus Clasificación
C las ifi cac i—n
Recuperac i—n p or S imil ar idad
F u nci—n d iscr imi n ad o ra
Entrenamiento
F un ci—n de S im ilar idad
Aprendizaje
Se lecc i—n de Descr ip to res
Medida de Separabilida
d
Se lecc i—n de Descr ip to res
Medida de Relatividad
C o n jun to d e Med idas de Descr ip to res
Mu ltim ed ia
O bjeto s
Recuperación de Imágenes

Búsqueda por histogramas: La imagen es
caracterizada por el histograma de colores. El
histograma entrega la relativa cantidad de
color sin considerar la localización, forma y
textura de los objetos.
Recuperación de Imágenes

Búsqueda por color layout: Las imágenes son divididas
en bloques y el color promedio a cada bloque es
almacenado. Cada búsqueda basada en color layout es
sensitiva a rotación y cambio de tamaño porque las
imágenes son caracterizadas por propiedades locales.
La similitud entre imágenes ese basa en comparar la
signatura de ellas. Textura y forma no son
consideradas y está limitada a la representación de
imágenes en términos de niveles de intensidad.
Recuperación de Imágenes

Búsqueda basada en regiones: Los objetos en las
imágenes son obtenidos a partir de un proceso de
segmentación. A cada objeto se le pueden agregar
color, textura, localización o una combinación de ellos.
Búsqueda de
Configuraciones
¿Existe
en la Base de Datos?
Consulta
Consulta
Una consulta Q es un conjunto de n
variables con un conjunto de m ≤ n(n-1)/2
restricciones.
Base de Datos de Imágenes
Base de Datos Espacial
QuickTime™ and a
GIF decompressor
are needed to see this picture.
Satisfacción de Restricciones
•
•
•
•
Dado un conjunto de variables {x1…xn}
Un dominio discreto y finito por cada
variable {D1…Dm}
Un conjunto {Rk} de restricciones definidas
sobre un dominio de variables
RjDi1x…Dij
Encontrar una asignación de variables tal
que las restricciones sean satisfechas
Restricciones: Topologías
Restricciones: Métrica
Restricciones: Métrica
Restricciones: Métrica
Restricciones: Métrica
Restricciones: Orientación
Problema: Comparar
?
Descripción Contenido
Caracterización MBR
D
C
A
B
Area
Diagonal
Caracterización de MBRs
D
C
A
B
Area
Diagonal
Real  Fárea (MBR)
Real  Fdiagonal (MBR)
Caracterización de pares de MBRs
A B
A
B
C
C D
D
MBR  Funión (MBR, MBR)
MBR  Fintersección (MBR, MBR)
Caracterización de pares de MBRs
A
d
exterior
B
C
D
d interior
Real  F d_exterior (MBR, MBR)
Real  F d_interior (MBR, MBR)
Indice de Contenido
F ( A, B ) 
a rea ( A )  2 a re a ( A  B )
a rea ( A)

dista n ce (A,  B )
diagonal (A )
Indice de Contenido
Indexación
•
Evitar la revisión exhaustiva de una base de datos.
•
Dado n objetos en la base de datos y m
restricciones en la consulta, la revisión exhaustiva
implica m permutaciones de n objetos O(nm), con n
>>>> m.
Indexación
•
Indexación espacial:
1.
Indexación sobre objetos
2.
Indexación sobre relaciones
Condición de Búsqueda
•Una
restricción entre variables de una consulta
R(vi,vj) será satisfecha por la restricción entre
instancias en la base de datos R(ui,uj) si:
d (R (v i , v j ), R (ui , u j ))   (R (v i , v j ))
d (R (v j , v i ), R (u j , ui ))   (R (v j , v i ))
Condición de Búsqueda
 (R (v i , v j ))  ab s (1  ab s (R(v i , v j )))  a,
a  1 .0
Preprocesamiento
•
Eliminar restricciones
•
Ordenar restricciones
Eliminación de Restricciones
•
Relaciones entre objetos cercanos
•
Satisfacción de consistencia
basada en la composición de
relaciones
Composición
R ; S (oi, ok) |
 oj tal que (oi, oj) R y (oj, ok)  S
A dentro B; B dentro CA dentro C
Composición
Composición
;
Composición
;
disjoint
disjoint
meet
overlap
coveredBy
inside
covers
contains
equal
meet
overlap
coveredBy
inside
covers
contains
equal
Grafo de Consistencia
 i R 'ii  R ii  eq u al
i , j | i  j R 'ij  R ij
 i , j R '' ij  R ' ij  R ' j i
n
 i , j R ' ' ' ij   R ' ' ik ; R' ' k j
ka
Grafo de Consistencia
Una relación es derivable si es
el único resultado de la
intersección de composiciones
usando todos los caminos en el
grafo de configuración
Eliminación de restricciones
•
El grafo resultante es único
•
Ej:
Existen ~2.245.000 consultas
consistentes con 5 objetos, lo que
significa 25 relaciones posibles. De
ellas, se pueden derivar 16 relaciones
en promedio
Algoritmos de Búsqueda
D (Q , S ) 
•
Forward-Checking Strategy
•
Similitud:

v i Q , u j S
F m (v k , v l )  Fm (uk , u l )  Fm (vl , v k )  Fm (u l , uk )
2
2
Algoritmos de Búsqueda
•
Determinísticos:
•
•
Basado en permutaciones
Algoritmos heurísticos:
•
•
Hill Climbing
Genéticos
Descargar

Bases de Espaciales Andrea Rodríguez Tastets Universidad de