Dissertationen zum Thema „Compactación y compresión de datos“

En los últimos años, los esquemas de compresión de imágenes basados en la transformada de Wavelet han ido remplazando a los esquemas clásicos basados en la transformada de Fourier, ya que son más eficientes y ofrecen una mayor posibilidad de análisis debido a su naturaleza multiresolución[1]. La compresión de imágenes actualmente juega un papel muy importante en el desarrollo de equipos portátiles o de telecomunicaciones, ya que estos buscan almacenar grandes volúmenes de información en el menor espacio posible o transmitir información a altas velocidades. Por lo tanto, esto implica migrar de la solución software originalmente concebida, hacia su implementación en procesadores de aplicación específica (hardware), la cual ofrece una mayor flexibilidad y la posibilidad de procesar los datos en tiempo real. Este trabajo presenta la implementación de una versión optimizada del algoritmo de codificación/decodificación SPIHT (Set Partitioning In Hierarchical Trees) sobre un arreglo de puertas programables por campo (FPGA), para lograr una reducción considerable del tiempo de procesamiento. Para ello, se propone una metodología de diseño digital Top-Down capaz de adaptar el estado del arte de un algoritmo específico a su equivalente en hardware programable. Los resultados de las pruebas experimentales demuestran que el diseño alcanza un reducido tiempo de procesamiento, logrando codificar una imagen transformada al dominio Wavelet de 256x256 píxeles en 50 milisegundos y realizar la decodificación de las misma en menos de un milisegundo. Además posee un bajo consumo de recursos, ocupando un 27% del FPGA Stratix EP1S25F1020C5 de Altera para dicha configuración. El sistema esta configurado para comunicarse con una interfaz de usuario visual para la transferencia de imágenes y visualización de resultados por la PC a través del Bus PCI.
Tesis

El comportamiento a corto plazo de las propiedades físicas de un Vertisol, bajo sistemas de labranza tradicional y de conservación, en la zona de producción de maíz (Zea mays L.) del Valle Toluca-Atlacomulco, aún no ha sido reportado. Adicionalmente, se considera que se requieren de mediciones de laboratorio adicionales que puedan imitar las condiciones de campo, y que resulten sensibles, confiables y apropiadas para monitorear cambios en la compactación y otras propiedades físicas del suelo mientras se reduce el muestreo destructivo en campo. Esta investigación se planteó como objetivos: utilizar las pruebas de compresión uniaxial, resistencia a la penetración y fuerza de corte en una máquina universal de prueba, para evaluar la respuesta de un Vertisol en términos de dureza, cohesividad y adhesividad cuando es compactado por tránsito rodado en tres sistemas de labranza: tradicional (LT), mínima (LM) y cero (LC) y; evaluar el efecto de los sistemas de labranza sobre la compactación de un Vertisol y el rendimiento de maíz. El estado de la compactación se caracterizó mediante la medición de la densidad aparente, resistencia a la penetración, mediante el índice de cono, y, velocidad media de infiltración del agua en cada ciclo de cultivo del periodo de estudio. Los ensayos en la máquina universal de prueba resultaron suficientemente sensibles para detectar diferencias en las propiedades físicas del suelo de los diferentes sistemas de labranza. Los mayores valores de rendimiento fueron obtenidos en LM. El análisis de las distintas variables no permitió determinar, en el corto plazo, tendencias claras en el incremento o remediación de los parámetros de compactación del Vertisol bajo los diversos sistemas de labranza.

El almacenamiento digital de la información debe abordar tanto el problema de la incorporación de datos al sistema como su recuperación, y debe hacer un catálogo acorde con las consultas que sobre ellos quiera hacerse. El espacio ocupado para el almacenamiento y el tiempo necesario para ingresar la información, y para recuperala, depende directamente de la estructura utilizada en el repositorio. De este modo, cuando nos referimos a información que ya cuenta cion un grado de estructuración, la indexación debe ser coherente con la estructuta formal de la misma, para favorecer así la consulta. En el presente estudio se aborda el problema de la compresión estática de información semi-estructurada combinada con una indezación tendiente a soportar uin conjunto de consultas sobre los datos, con un fuerte énfasis en el almacenamiento en memoria secundaria. El ámbito de desarrollo de la aplicación propuesta se enmarca dentro de la documentación XML y su lenguaje de consulta XQuery. El modelo utilizado en la implementación está basado en la propuestas desarrolladas por Baeza-Yates y Navarro en Proximal Nodes. La implementación corresponde a un desarrollo posterior de un procesador destinado a soportar consultas en el lenguaje XPath desarrollado por Manuel Ortega como memoria de Ingeniería. El desarrollo de la capa de almacenamiento del prototipo actual se enfoca en la resolución de problemas en tres áreas: recuperación del archivo fuente, consulta eficiente sobre la estructura del documento, y búsqueda de texto en lenguaje natural. Las estructuras diseñadas adhieren a técnicas recientes en el área de la compresión y de recuperación de la información en XML. El resultado de esta memoria es un autoíndice XML con gran desempeño en colecciones de tamaño pequeño y mediano, con capacidad de abordar colecciones de gran tamaño con resucesos limitados de memoria principal, y con un gran potencial de adaptación para colecciones en un nuevo contexto dinámico. El prototipo presenta un desempeño altamente competitivo con las alternativas existentes en el estado del arte.

El algoritmo de clasificación kNN (k-nearest neighbors) es uno de los métodos de clasificación no paramétrico más utilizados, sin embargo, está limitado debido al consumo de memoria relacionado con el tamaño del conjunto de datos, lo que hace poco práctica su aplicación a grandes volúmenes de datos. La investigación descrita en esta tesis fue motivada por la necesidad de una representación óptima de datos categóricos que puedan ser fácilmente incorporados en los algoritmos de aprendizaje automático que permiten un análisis y explotación inteligente de grandes volúmenes de datos. En esta tesis se propone el uso de un esquema de compresión a nivel de bits para comprimir el conjunto de datos de entrenamiento (training dataset) antes de entrenar un modelo de aprendizaje automático. Para utilizar el conjunto de datos, se propuso una descompresión en tiempo real que permite el uso del conjunto de datos sin necesidad de una descompresión completa. Para facilitar la incorporación del método de compresión propuesto en los frameworks de aprendizaje automático existentes, el método propuesto está alineado con el estándar Basic Linear Algebra Subprograms - BLAS de nivel 1 que define los bloques de construcción básicos en forma de funciones algebraicas. En particular, en esta tesis se propone el uso del algoritmo kNN para trabajar con datos categóricos comprimidos. El método propuesto permite mantener los datos comprimidos en memoria, con lo que se reduce drásticamente el consumo de memoria.

En la actualidad con el continuo avance de la tecnología informática se han generado diversos entornos de trabajo en la mayoría de campos de la vida cotidiana como ingeniería, medicina, educación, arquitectura, administración, entretenimiento, etc. en donde se hace uso de una gran cantidad de contenido audiovisual, lo cual ha generado un aumento desmesurado en el almacenamiento y transmisión digital de dichos contenidos. En el siguiente trabajo de investigación se presenta una solución para el problema del alto costo de almacenamiento digital de las imágenes. Esta solución está basada en la aplicación de un método de compresión muy utilizado en el procesamiento de imágenes: el clustering o agrupamiento, en donde se hace uso del algoritmo de colonia de hormigas, con la finalidad de reducir el tamaño de la paleta de colores utilizada para representar una imagen; y con ello reducir el tamaño de almacenamiento de la imagen sin que ello afecte la visualización de la misma por parte de la persona. Los resultados obtenidos después de realizar diversas pruebas con el algoritmo de colonia de hormigas diseñado en esta investigación fueron que el tamaño de las imágenes se redujo en un 66.41% con respecto a su peso inicial y además la percepción visual de las imágenes generadas no fue afectada drásticamente.
Trabajo de suficiencia profesional

En los últimos años el avance tecnológico, en lo que se refiere a la transmisión de video en alta definición con gran resolución, viene en auge, pero mostrando una baja calidad de video en una serie de cuadros por segundo utilizando más ancho de banda y a la vez menos frecuencia de transmisión. Esto quiere decir mayor pérdida de información por dato enviado, y otorgando prioridad a los objetos en movimiento e imágenes en 3D pero olvidando la calidad y fidelidad de la misma. Esta necesidad motivó el desarrollo de esta investigación para encontrar una solución equitativa y progresiva a la baja calidad de video, pero basado en el análisis de los estándares que dieron origen a la compresión. Pues este estudio conlleva a realizar un tratamiento de las principales técnicas de procesamiento de información dentro de los estándares de compresión MPEG-4 y H.264, con una investigación exhaustiva utilizando gráficas, diagramas y esquemas que justifiquen los resultados obtenidos, así como también simulaciones del rendimiento mediante el manejo de un software de computación científica.
Tesis

Doctor en Ciencias, Mención Computación
Document Retrieval (DR) aims at efficiently retrieving the documents from a collection that are relevant to user queries. A challenging variant arises when the documents are arbitrary strings and the collection is large. This scenario arises in DNA or protein sequence collections, software repositories, multimedia sequences, East Asian languages, and others. Several DR compressed data structures have been developed to face this challenge, offering different space/time complexities. However, in practice the proposals with the best time performance require too much extra space. This thesis innovates in three aspects: (1) we build on Lempel-Ziv 1978 (LZ78) compres- sion, instead of suffix arrays, to build DR indices; (2) we build on Lempel-Ziv 1977 (LZ77) compression to handle highly repetitive collections; (3) we start the study of approximate answers in this DR scenario, which is common in DR on natural language texts. In this aspect, our main contribution is a new approach to DR based on LZ78 data compression, offering structures to solve the two most fundamental problems in the DR field: Document Listing (DL) and Top-k Retrieval. Our novel indices offer a competitive space/time tradeoff for both situations. Besides, our proposals are also capable of retrieving approximate answers, saving a lot of space and/or time compared with any structure that returns the full answer for any of these problems. Our second main contribution is the design of a structure for indexing highly repetitive text collections that solves the DL problem, which is built on the LZ77 parsing. This is the first attempt to solve DR problems using LZ77 data compression, which is the best compression scheme for such collections. On the other hand, we improve on basic data structures used, among others, in DR. We present an alternative design to the best theoretical Range Minimum Queries solution, maintaining its good complexities in space usage and query time. We obtain a simpler formula that leads to the fastest and most compact practical implementation to date. We also implemented various promising theoretical proposals for compressed suffix ar- rays, for which no previous implementations existed. Finally, we design and implement a compressed text index for highly repetitive collections that solves pattern matching, which is based on the LZ77 compression, and which is the basis for our LZ77-based DR index.
Document Retrieval (DR) apunta a la recuperación eficiente de documentos relevantes de una colección, para las consultas del usuario. Una variante que surge como desafío es cuando los documentos provienen de una gran colección de textos arbitrarios. Este escenario ocurre con colecciones de secuencias de ADN o proteínas, repositorios de software, secuencias multimedia e idiomas del Lejano Oriente, entre otros entornos. Varias estructuras de datos comprimidas para DR han sido desarrolladas a fin de hacer frente a este desafío, ofreciendo diferentes complejidades en tiempo/espacio. Sin embargo, en la práctica las propuestas con el mejor rendimiento en tiempo, requieren a su vez de demasiado espacio extra. Esta tesis innova tres aspectos: (1) construímos índices para DR en base a la compresión Lempel-Ziv 1978 (LZ78) en lugar de arreglos de sufíjos; (2) manipulamos colecciones altamente repetitivas en base a la compresión Lempel-Ziv 1977 (LZ77); (3) comenzamos a estudiar cómo entregar respuestas aproximadas en dicho escenario de DR, lo cual es una práctica común en textos de lenguaje natural. Nuestra principal contribución es un nuevo enfoque para DR basado en la compresión de datos LZ78, ofreciendo estructuras que resuelven los dos problemas fundamentales del campo de DR: Document Listing (DL) y Top-k Retrieval. Nuestros nuevos índices ofrecen desempeño competitivo en tiempo/espacio en ambos casos. Además nuestras propuestas también entregan respuestas aproximadas, ahorrando considerable espacio y/o tiempo comparado con cualquier otra estructura que entregue una respuesta completa a alguno de estos problemas. También diseñamos una estructura que indexa colecciones de texto altamente repetitivo y resuelve el problema de DL, basada en la compresión LZ77. Este el primer intento dirigido a resolver un problema de DR utilizando compresión de datos LZ77, que además es el mejor esquema de compresión para dichas colecciones. Por otro lado, realizamos mejoras sobre estructuras de datos básicas utilizadas en DR. Presentamos un diseño alternativo a la mejor solución teórica para Range Minimum Queries, manteniendo sus buenas complejidades en términos de espacio utilizado y tiempo de consulta. Logramos una fórmula más sencilla obteniendo como resultado la implementación más rápida y compacta conocida hasta hoy. Además implementamos varias propuestas teóricas promisorias para el arreglo de sufijos, de las cuales no existen implementaciones previas. Finalmente, diseñamos e implementamos un índice de texto comprimido para colecciones altamente repetitivas que resuelve el pattern matching, el cual se basa en la compresión LZ77, y que además es la base para nuestro índice sobre el LZ77 para DR.
This work has been partially funded by Conicyt Ph.D Scholarship Chile; Fondecyt Grant 1-140976; Millennium Nucleus for Information and Coordination in Networks, and Basal Center for Biotechnology and Bioengineering

No autorizado por el autor para ser publicada a texto completo
La cantidad de datos disponibles crece de forma dramática cada día. Esto trae consigo la necesidad de poder manejar éstos datos de forma adecuada, de manera de poder acceder a estos de forma eficiente y al mismo tiempo ahorrar espacio de almacenamiento. En particular, para manejar grandes cantidades de texto una herramienta clave son los índices de texto, y en el contexto de este trabajo los índices comprimidos, los cuales no sólo responden consultas de forma rápida sino que también almacenan sus datos y el texto en forma eficiente. El objetivo general del presente trabajo fue desarrollar un índice comprimido basado en listas de ocurrencias de los q-gramas del texto y comprimir este último. Se desea comparar la eficacia de este índice con los auto-índices ya desarrollados en el sitio Pizza&Chili (http://pizzachili.dcc.uchile.cl). Un índice invertido de q-gramas permite encontrar patrones en un texto. Para tal efecto las consultas se dividen en dos etapas. En la primera etapa se seleccionan las regiones del texto (llamadas bloques) donde ocurren todos los q-gramas del patrón y por lo tanto éste podría encontrarse. En la segunda etapa se verifica si efectivamente el patrón se encuentra en los bloques que fueron seleccionados. Además es necesario almacenar el texto de forma independiente. En la implementación realizada se mantiene el texto dividido en bloques comprimidos, los cuales se almacenan en memoria secundaria. Esto permite utilizar menos espacio y acceder a los bloques individualmente. Se implementaron diversos algoritmos para comprimir el índice y realizar consultas. Además se diseñaron y ejecutaron experimentos para medir el rendimiento de las distintas variantes obtenidas al combinar los diferentes algoritmos. En base a los resultados obtenidos se seleccionaron los algoritmos que presentaron mejor rendimiento tanto en velocidad como en niveles de compresión alcanzados. De la misma forma se implementaron y midieron experimentalmente alternativas para comprimir y buscar en el texto. Finalmente se comparó el rendimiento de las variantes seleccionadas del índice frente a los índices competitivos presentes en el sitio Pizza&Chili. Los resultados indican que el índice tiene un rendimiento competitivo para búsquedas de patrones pequeños.

Magíster en Ciencias, Mención Computación
Las estructuras de datos compactas ofrecen funcionalidad y acceso a los datos usando poco espacio. En una estructura de datos plana se conservan los datos en su forma original y se busca minimizar el espacio extra usado para proveer la funcionalidad, mientras que en una estructura comprimida además se recodifican los datos para comprimirlos. En esta tesis se estudian estructuras de datos compactas para secuencias de bits (bitmaps) que proveen las operaciones rank y select: rankb(B,i) cuenta el número de bits b ∈ {0,1} en B[1..i] y selectb(B,i) retorna la posición de la i-ésima ocurrencia de b en B. En teoría ambas consultas se pueden responder en tiempo constante, pero la implementación práctica de estas soluciones no siempre es directa o con buenos resultados empíricos. Las estructuras de datos con un enfoque más práctico, usualmente no óptimas en teoría, pueden tener mejor desempeño que implementaciones directas de soluciones teóricamente óptimas. Esto es particularmente notorio para la operación select. Además, las implementaciones más eficientes para rank son deficientes para select, y viceversa. En esta tesis se definen nuevas estructuras de datos prácticas para mejorar el desempeño de las operaciones de rank y select, basadas en dos ideas principales. La primera consiste en, a diferencia de las técnicas actuales, que usan estructuras separadas para rank y select, reutilizar cada estructura también para acelerar la otra operación. La segunda idea es simular en tiempo de consulta una tabla de resultados precomputados en vez de almacenarla, lo que permite utilizar tablas universales mucho mayores que las que sería posible almacenar. Los resultados experimentales muestran que la primera idea, aplicada a estructuras planas, utiliza sólo 3% de espacio sobre el bitmap y ofrece tiempos similares a estructuras que usan mucho más espacio, para ambas operaciones. En estructuras de datos comprimidas se pueden combinar ambas ideas, obteniendo un espacio extra de menos de 7 % sobre el bitmap comprimido y manteniendo, para ambas operaciones, tiempos similares o mejores que las estructuras actuales (que usan 27 % de espacio extra).

Magíster en Ciencias, Mención Computación
La estructura de la Web se puede modelar como un grafo, donde las páginas son los nodos y los hipervínculos las aristas. Estos grafos Web son ampliamente utilizados para diversas tareas de análisis de la Web, tales como el cálculo de Page-Rank o la detección de spam en la Web, entre otras. Una de las limitantes que se presentan al trabajar con estos grafos es su tamaño, por ejemplo, el 2005 se calculó que la Web pública y estática tenía 11.5 mil millones de nodos, y unas 15 aristas por nodo, lo que requiere más de 600 GB para su representación plana. De aquí surge la motivación de este trabajo, que consiste en la creación de estructuras de datos comprimidas para representar grafos de la Web. Una estructura comprimida busca almacenar la mayor cantidad de datos en el menor espacio posible, ya sea en memoria principal o en disco, soportando las consultas de interés sin la necesidad de descomprimir la estructura en su totalidad. La principal ventaja de estas estructuras es que se puede evitar mantener la información en disco o se disminuye la cantidad de transferencias necesarias. Esto es de vital importancia dado que el disco puede llegar a ser un millón de veces más lento que la memoria principal. Entre los resultados más importantes de este trabajo se presenta una estructura comprimida para grafos de la Web que mejora el estado del arte, ofreciendo el mejor compromiso espacio-tiempo conocido para recuperar listas de adyacencia. Además se muestra cómo extender esta estructura para soportar consultas más complejas, como vecinos reversos, manteniendo los requerimientos de espacio. Como productos agregados se incluyen resultados experimentales y propuestas para el problema de Rank y Select sobre secuencias generales, incluyendo estructuras no implementadas antes. Los resultados derivan en mejoras inmediatas para índices comprimidos para texto, en los cuales se reduce el espacio utilizado por los mejores índices existentes, a veces incluso sin penalización en el tiempo de búsqueda. Además se presenta un algoritmo aproximado para comprimir utilizando el método Re-Pair cuando la memoria principal es limitada. También se obtienen resultados en estructuras comprimidas para relaciones binarias, presentándose una nueva propuesta que, además de utilizar espacio proporcional a la entropía de la relación binaria, permite dinamizar la estructura, vale decir, aceptar inserciones y borrados de pares en la relación.

Ingeniero Civil en Computación
El árbol de sufijos es una de las estructuras más importantes que se han creado para el manejo de cadenas de caracteres. Esta estructura permite encontrar eficientemente las ocurrencias de un patrón, en tiempo proporcional al largo del patrón. Adicionalmente soporta operaciones para resolver problemas complejos sobre una secuencia. Esta estructura tiene muchas aplicaciones en variadas áreas de la investigación , destacándose en la bioinformática, donde los recientes avances tecnológicos han permitido recolectar grandes colecciones de secuencias de ADN. La implementación clásica se vuelve impracticable para grandes volúmenes de información dado que ocupan demasiado espacio, que siempre muchas veces mayor que el texto mismo. Luego, no pueden ser almacenados en memoria principal, lo que en la práctica significa un aumento importante del tiempo de respuesta. Este problema es la principal motivación por la cual se buscan nuevas representaciones comprimidas de esta estructura, dando lugar a los árboles de sufijos comprimidos. Estos contienen la misma información que los árboles de sufijos pero ocupan un espacio considerablemente menor. Existen variadas propuestas teóricas para representar un árbol de sufijos comprimido, que ofrecen espacios y tiempos diferentes. En la práctica, dos estructuras destacan por sobre las demás. La primera fue propuesta por Sadakane e implementada por Välimäki et al. Esta estructura soporta la mayoría de las operaciones de navegación en tiempo constante, pero en la práctica requiere entre 25 y 35 bits por símbolo. La segunda fue propuesta por Fischer et al. e implementada por Cánovas, incorporando variantes y nuevas ideas para todas las estructuras que componen el árbol de sufijos comprimido propuesto por ellos. Una de estas variantes resulta ser superior a la implementación de Sadakane tanto en espacio como en tiempo, utilizando alrededor de 8 a 12 bits por símbolo. Dado que secuencias de ADN relacionadas son altamente similares, por ejemplo dos genomas humanos son muy parecidos, las colecciones pueden ser tratadas como un gran texto que contiene cadenas altamente similares. En este trabajo se propone e implementa una nueva variante del árbol de sufijos comprimido de Fischer et al, optimizada para textos altamente repetitivos. Se reemplazan y/o modifican cada una de las estructuras que componen el árbol por nuevas que presentan mayor compresión en textos repetitivos. El resultado más importante consiste en crear una nueva estructura inspirada en una técnica de compresión basada en gramáticas, aplicable al árbol de sufijos comprimido, que con poco espacio extra acelera considerablemente las operaciones sobre el árbol. Finalmente, la variante se compara experimentalmente sobre textos altamente repetitivos y resulta ser superior a la implementación de Cánovas, tanto en tiempo como en espacio, ocupando entre 3 a 6 bits por símbolo.
Este trabajo ha sido parcialmente financiado por el Instituto Milenio de Dinámica Celular y Biotecnología (ICDB) y el proyecto Fondecyt 1-080019

IASI (Infrared Atmospheric Sounding Interferometer) es un espectrómetro basado en la transformada de Fourier diseñado para medir radiación infrarroja emitida por La Tierra. A partir de estas mediciones se generan datos con una precisión y resolución espectral sin precedentes. Esta información es útil para obtener perfiles de temperatura y humedad, así como concentraciones de gases traza, que son esenciales para la comprensión y monitorización del clima y para realizar previsiones atmosféricas. La alta resolución espectral, espacial y temporal de los datos producidos por el instrumento implica generar productos con un tamaño considerablemente grande, lo que demanda el uso de técnicas de compresión eficientes para mejorar tanto las capacidades de transmisión como las de almacenamiento. En esta tesis se realiza un exhaustivo análisis de la compresión de datos IASI y se proporcionan recomendaciones para generar datos reconstruidos útiles para el usuario final. En este análisis se utilizan datos IASI transmitidos a las estaciones de recepción (productos IASI L0) y datos destinados a usuarios finales que son distribuidos a centros de predicción numérica y a la comunidad científica en general (productos IASI L1C). Para comprender mejor la naturaleza de los datos capturados por el instrumento se analizan las estadísiticas de la información y el rendimiento de varias técnicas de compresión en datos IASI L0. Se estudia la entropía de orden-0 y las entropías contextuales de orden-1, orden-2 y orden-3. Este estudio revela que el tamaño de los datos se podría reducir considerablemente explotando la entropía de orden-0. Ganancias más significativas se podrían conseguir si se utilizaran modelos contextuales. También se investiga el rendimiento de varias técnicas de compresión sin pérdida. Los resultados experimentales sugieren que se puede alcanzar un ratio de compresión de 2,6:1, lo que implica que sería posible transmitir más datos manteniendo la tasa de transmisión original o, como alternativa, la tasa de transmisión del instrumento se podría reducir. También se realiza un exhaustivo análisis de la compresión de datos IASI L1C donde se evalúa el rendimiento de varias transformadas espectrales y técnicas de compresión. La experimentación abarca compresión sin pérdida, compresión casi sin pérdida y compresión con pérdida sobre una amplia gama de productos IASI-A e IASI-B. Para compresión sin pérdida es posible conseguir ratios de compresión superiores a 2,5:1. Para compresión casi sin pérdida y compresión con pérdida se pueden alcanzar ratios de compresión mayores a la vez que se producen espectros reconstruidos de calidad. Aunque la compresión casi sin pérdida y la compresión con pérdida producen ratios de compresión altos, la utilidad de los espectros reconstruidos se puede ver comprometida ya que cierta información es eliminada durante la etapa de compresión. En consecuencia, se estudia el impacto de la compresión casi sin pérdida y la compresión con pérdida en aplicaciones de usuario final. Concretamente, se evalúa el impacto de la compresión en datos IASI L1C cuando algoritmos estadísticos se utilizan posteriormente para predecir información física a partir de los espectros reconstruidos. Los resultados experimentales muestran que el uso de espectros reconstruidos puede conseguir resultados de predicción competitivos, mejorando incluso los resultados que se obtienen cuando se utilizan datos sin comprimir. A partir del análisis previo se estudia el origen de los beneficios que produce la compresión obteniendo dos observaciones principales. Por un lado, la compresión produce eliminación de ruido y filtrado de la señal lo que beneficia a los métodos de predicción. Por otro lado, la compresión es una forma indirecta de producir regularización espectral y espacial entre píxeles vecinos lo que beneficia a algoritmos que trabajan a nivel de píxel.
The Infrared Atmospheric Sounding Interferometer (IASI) is a Fourier Transform Spectrometer implemented on the MetOp satellite series. The instrument is intended to measure infrared radiation emitted from the Earth. IASI produces data with unprecedented accuracy and spectral resolution. Notably, the sounder harvests spectral information to derive temperature and moisture profiles, as well as concentrations of trace gases, essential for the understanding of weather, for climate monitoring, and for atmospheric forecasts. The large spectral, spatial, and temporal resolution of the data collected by the instrument involves generating products with a considerably large size, about 16 Gigabytes per day by each of the IASI-A and IASI-B instruments currently operated. The amount of data produced by IASI demands efficient compression techniques to improve both the transmission and the storage capabilities. This thesis supplies a comprehensive analysis of IASI data compression and provides effective recommendations to produce useful reconstructed spectra. The study analyzes data at different processing stages. Specifically, we use data transmitted by the instrument to the reception stations (IASI L0 products) and end-user data disseminated to the Numerical Weather Prediction (NWP) centres and the scientific community (IASI L1C products). In order to better understand the nature of the data collected by the instrument, we analyze the information statistics and the compression performance of several coding strategies and techniques on IASI L0 data. The order-0 entropy and the order-1, order-2, and order-3 context-based entropies are analyzed in several IASI L0 products. This study reveals that the size of the data could be considerably reduced by exploiting the order-0 entropy. More significant gains could be achieved if contextual models were used. We also investigate the performance of several state-of-the-art lossless compression techniques. Experimental results suggest that a compression ratio of 2.6:1 can be achieved, which involves that more data could be transmitted at the original transmission rate or, alternatively, the transmission rate of the instrument could be further decreased. A comprehensive study of IASI L1C data compression is performed as well. Several state-of-the-art spectral transforms and compression techniques are evaluated on IASI L1C spectra. Extensive experiments, which embrace lossless, near-lossless, and lossy compression, are carried out over a wide range of IASI-A and IASI-B orbits. For lossless compression, compression ratios over 2.5:1 can be achieved. For near-lossless and lossy compression, higher compression ratios can be achieved, while producing useful reconstructed spectra. Even though near-lossless and lossy compression produce higher compression ratios compared to lossless compression, the usefulness of the reconstructed spectra may be compromised because some information is removed during the compression stage. Therefore, we investigate the impact of near-lossless and lossy compression on end-user applications. Specifically, the impact of compression on IASI L1C data is evaluated when statistical retrieval algorithms are later used to retrieve physical information. Experimental results reveal that the reconstructed spectra can enable competitive retrieval performance, improving the results achieved for the uncompressed data, even at high compression ratios. We extend the previous study to a real scenario, where spectra from different disjoint orbits are used in the retrieval stage. Experimental results suggest that the benefits produced by compression are still significant. We also investigate the origin of these benefits. On the one hand, results illustrate that compression performs signal filtering and denoising, which benefits the retrieval methods. On the other hand, compression is an indirect way to produce spectral and spatial regularization, which helps pixel-wise statistical algorithms.

Los datos hiperespectrales capturados por teledetección cuentan con cientos o miles de componentes espectrales de similares longitudes de onda. Almacenarlos y transmitirlos conlleva una demanda excesiva en ancho de banda y memoria, ya de por sí bastante limitados, que pueden dar lugar a descartar información ya capturada o a dejar de capturarla. Para paliar estas limitaciones, se aplican algoritmos de compresión. Además, la tecnología de los sensores evoluciona continuamente, pudiéndose adquirir datos con mayores dimensiones. De ahí que, para no penalizar el funcionamiento y rendimiento de futuras misiones espaciales, se necesitan desarrollar métodos de compresión más competitivos. Regression Wavelet Analysis (RWA) es el método de compresión sin pérdidas más eficiente en relación a la complejidad computacional y al rendimiento de codificación. RWA se describe como una transformada espectral sin pérdida seguida de JPEG 2000. Ésta aplica un nivel de descomposición de la transformada discreta de onda Haar y una regresión. Hay varios modelos de regresión (Maximum, Restricted y Parsimonious) y variantes (solo para Maximum). Inicialmente, nos centramos en aumentar el rendimiento de codificación y/o reducir la complejidad computacional de RWA para diseñar técnicas de compresión más competitivas. Primero, investigamos en profundidad la influencia que tiene el reemplazar el filtro de RWA por transformadas más eficientes en cuanto a la compactación de energía. Para ello, redefinimos el modelo Restricted, reduciendo el tiempo de ejecución, incrementando el ratio de compresión, y preservando un cierto grado de escalabilidad por componente. Además, mostramos que las variantes de regresión se pueden aplicar a todos los modelos de regresión, disminuyendo así su complejidad computacional sin apenas penalizar el rendimiento de codificación. Nuestras nuevas configuraciones proporcionan ratios de compresión mayores o bastante competitivos con respecto a otras técnicas de menor y mayor complejidad. Tras ello, describimos el impacto que tiene el aplicar un esquema de pesos predictivo (PWS) en el rendimiento de compresión cuando se decodifica de forma progresiva desde con-pérdida hasta sin-pérdida (PLL). La aplicación de estos pesos a todos los modelos de regresión y variantes de RWA con JPEG 2000 (PWS-RWA + JPEG 2000) mejora los resultados del esquema original (RWA + JPEG 2000). Por otro lado, vemos que un mejor rendimiento de la codificación no implica necesariamente mejores clasificaciones. De hecho, en comparación con otras técnicas que recuperan la escena con mayor calidad, PWS-RWA + JPEG 2000 provee de mejores clasificaciones cuando la distorsión en la recuperación es elevada. Para obtener una implementación de más baja complejidad computacional, presentamos resultados de RWA acompañada de un codificador que se puede ejecutar a bordo. Además, con un sencillo criterio de decisión conseguimos tasas de bits más bajas, mejorando al esquema original y otras técnicas de compresión sin pérdidas al obtener ganancias de codificación promedio entre 0,10 y 1,35 bits-por-píxel-por-componente. Finalmente, presentamos la primera técnica de compresión sin-pérdida/casi-sin-pérdida basada en un sistema piramidal que aplica regresión. Para ello, ampliamos RWA introduciendo cuantización y un algoritmo de retroalimentación para controlar independientemente el error de cuantificación en cada nivel de descomposición, al mismo tiempo que preservamos la complejidad computacional. Proporcionamos también una ecuación que limita el máximo error en valor absoluto admisible en la reconstrucción. A su vez, evitamos probar la gran cantidad de combinaciones posibles de pasos de cuantificación mediante el desarrollo de un esquema de asignación de pasos. Nuestra propuesta, llamada NLRWA, logra obtener un rendimiento de codificación muy competitivo y recuperar la escena con mayor fidelidad. Por último, cuando el codificador por entropía se basa en planos de bits, NLRWA puede proporcionar una compresión progresiva desde con-pérdida hasta sin-pérdida/casi-sin-pérdida y cierto grado de integrabilidad.
Remote sensing hyperspectral data have hundreds or thousands of spectral components from very similar wavelengths. To store and transmit it entails excessive demands on bandwidth and on on-board memory resources, which are already strongly restricted. This leads to stop capturing data or to discard some of the already recorded information without further processing. To alleviate these limitations, data compression techniques are applied. Besides, sensors' technology is continuously evolving, acquiring higher dimensional data. Consequently, in order to not jeopardize future space mission's performance, more competitive compression methods are required. Regression Wavelet Analysis (RWA) is the state-of-the-art lossless compression method regarding the trade-off between computational complexity and coding performance. RWA is introduced as a lossless spectral transform followed by JPEG 2000. It applies a Haar Discrete Wavelet Transform (DWT) decomposition and sequentially a regression operation. Several regression models (Maximum, Restricted and Parsimonious) and variants (only for the Maximum model) have been proposed. With the motivation of outperforming the latest compression techniques for remote sensing data, we began focusing on improving the coding performance and/or the computational complexity of RWA. First, we conducted an exhaustive research of the influence of replacing the underlying wavelet filter of RWA by more competitive Integer Wavelet Transforms (in terms of energy compaction). To this end, we reformulated the Restricted model, reducing the execution time, increasing the compression ratio, and preserving some degree of component-scalability. Besides, we showed that the regression variants are also feasible to apply to other models, decreasing their computational complexity while scarcely penalizing the coding performance. As compared to other lowest- and highest-complex techniques, our new configurations provide, respectively, better or similar compression ratios. After gaining a comprehensive understanding of the behavior of each operation block, we described the impact of applying a Predictive Weighting Scheme (PWS) in the Progressive Lossy-to-Lossless (PLL) compression performance. PLL decoding is possible thanks to the use of the rate control system of JPEG 2000. Applying this PWS to all the regression models and variants of RWA coupled by JPEG 2000 (PWS-RWA + JPEG 2000) produces superior outcomes, even for multi-class digital classification. From experimentation, we concluded that improved coding performance does not necessarily entail better classification outcomes. Indeed, in comparison with other widespread techniques that obtain better rate-distortion results, PWS-RWA + JPEG 2000 yields better classification outcomes when the distortion in the recovered scene is high. Moreover, the weighted framework presents far more stable classification versus bitrate trade-off. JPEG 2000 may be too computationally expensive for on-board computation. In order to obtain a cheaper implementation, we render results for RWA followed by another coder amenable for on-board operation. This framework includes the operation of a smart and simple criterion aiming at the lowest bitrates. This final pipeline outperforms the original RWA + JPEG 2000 and other state-of-the-art lossless techniques by obtaining average coding gains between 0.10 to 1.35 bits-per-pixel-per-component. Finally, we present the first lossless/near-lossless compression technique based on regression in a pyramidal multiresolution scheme. It expands RWA by introducing quantization and a feedback loop to control independently the quantization error in each decomposition level, while preserving the computational complexity. To this end, we provide a mathematical formulation that limits the maximum admissible absolute error in reconstruction. Moreover, we tackle the inconvenience of proving the huge number of possible quantization steps combinations by establishing a quantization steps-allocation definition. Our approach, named NLRWA, attains competitive coding performance and superior scene's quality retrieval. In addition, when coupled with a bitplane entropy encoder, NLRWA supports progressive lossy-to-lossless/near-lossless compression and some degree of embeddedness.

Tesis (Lic. en Ciencias de la Computación)--Universidad Nacional de Córdoba. Facultad de Matemática, Astronomía y Física, 2010.
En este trabajo nos concentramos en dos problemas íntimamente relacionados, por un lado atacamos el problema de la inferencia de gramáticas libres de contexto de tamaño mínimo y por otro, analizamos cómo es que estas pueden ser usadas para el descubrimiento de patrones. El estudio del problema de la gramática mínima es de importancia en el área de compresión de datos. Aún mas, algunos autores afirman, basandose en datos empíricos y en el principio de Descripción Mínima, que éstas pueden ser usadas para el descubrimiento de patrones.
Rafael Carrascosa.

Tesis (Lic. en Ciencias de la Computación)--Universidad Nacional de Córdoba, Facultad de Matemática, Astronomía, Física y Computación, 2017.
Las imágenes satelitales son cada vez de mayor tamaño, de tal manera que hoy en dı́a hablar en términos de gigabytes ya es normal. A la hora de generar productos que formen un mosaico también nos encontramos con grandes volúmenes lo cual no solo dificulta el procesamiento sino también la transferencia o distribución de los mismos hacia los usuarios. Finalmente, también tenemos el problema del manejo de los datos tanto a bordo de la plataforma del satélite como de su bajada a tierra. En esta tesis, se desarrollará e implementará un algoritmo de compresión con pérdida orientado a resolver esta problemática, utilizando la Transformada Discreta de Wavelets y la codificación Huffman.
Satellite images are increasing in size, to the point where speaking in the order of Gigabytes is normal. We also find big volumes of data when generating products such as mosaics, which makes both their processing and their transfer to end users more difficult. Finally, we also have large volumes of data in both the satellites themselves and in their transfer back to Earth. In this thesis, we design and implement a lossy compression algorithm targeted to solve this topic, making use of the Discrete Wavelet Transform and the Huffman coding.