Indexación Comprimida de Imágenes

Abstract

El continuo aumento de los volúmenes de información almacenada digitalmente ha fomentado el desarrollo de técnicas para brindar acceso y búsqueda de manera eficiente a los datos. En particular, el manejo de grandes colecciones de imágenes es un problema de gran interés. Un enfoque es tratar las imágenes como secuencias de texto bidimensional. En este contexto, han sido planteadas recientemente dos estructuras de autoindexación para colecciones de imágenes, basadas en extender autoíndices de texto unidimensional. Estas estructuras almacenan la colección en espacio proporcional al requerido para almacenar la colección comprimida, permitiendo a la vez el acceso directo a cualquier parte de la colección y la búsqueda eficiente de patrones en ella. Dos tipos de autoíndices para secuencias de texto son el Arreglo de Sufijos Comprimido y el Índice FM, y en ellos se basan las soluciones para imágenes.

Este trabajo se centra en la implementación de esos dos autoíndices para imágenes. Se implementaron distintas variantes para ambas estructuras buscando la mejor manera de adaptarlas a secuencias bidimensionales, y mejorando significativamente varios de los algoritmos originales. Finalmente se diseñaron y ejecutaron experimentos para comparar las distintas variantes de ambos índices, tanto en términos de espacio requerido por las estructuras, como de tiempo en responder las consultas de acceso y búsqueda de patrones. Las estructuras basadas en el Arreglo de Sufijos Comprimido resultaron mejores en cuanto a tiempo, mientras que aquellas basadas en el Índice FM resultaron mejores en términos de espacio requerido, cuando el rango de colores es pequeño. Por ejemplo, con el Arreglo de Sufijos Comprimido somos capaces de almacenar una colección utilizando un 80% del espacio que requeriría la representación plana, pudiendo dar acceso a cualquier subimagen a una velocidad aproximada de 1 megapixel por segundo. Con esta estructura somos capaces de contar las ocurrencias de un patrón a una velocidad aproximada de 0,5 megapixeles por segundo, y podemos localizar la posición de cada ocurrencia en menos de 0,1 milisegundo. Sobre colecciones con un rango de color más pequeño, utilizando el Índice FM podemos alcanzar niveles de compresión del 50 %, pudiendo llegar al 25% si aceptamos pérdida de información. Con esta estructura podemos acceder a cualquier subimagen y realizar la búsqueda de patrones a una velocidad de 0,1 megapixel por segundo.