Search results for "COMPRESSION"
showing 10 items of 774 documents
The Engineering of a Compression Boosting Library: Theory vs Practice in BWT Compression
2006
Data Compression is one of the most challenging arenas both for algorithm design and engineering. This is particularly true for Burrows and Wheeler Compression a technique that is important in itself and for the design of compressed indexes. There has been considerable debate on how to design and engineer compression algorithms based on the BWT paradigm. In particular, Move-to-Front Encoding is generally believed to be an "inefficient " part of the Burrows-Wheeler compression process. However, only recently two theoretically superior alternatives to Move-to-Front have been proposed, namely Compression Boosting and Wavelet Trees. The main contribution of this paper is to provide the first ex…
From First Principles to the Burrows and Wheeler Transform and Beyond, via Combinatorial Optimization
2007
AbstractWe introduce a combinatorial optimization framework that naturally induces a class of optimal word permutations with respect to a suitably defined cost function taking into account various measures of relatedness between words. The Burrows and Wheeler transform (bwt) (cf. [M. Burrows, D. Wheeler, A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation, 1994]), and its analog for labelled trees (cf. [P. Ferragina, F. Luccio, G. Manzini, S. Muthukrishnan, Structuring labeled trees for optimal succinctness, and beyond, in: Proc. of the 45th Annual IEEE Symposium on Foundations of Computer Science, 2005, pp. 198–207]), are special cases i…
Statistical Modeling of Huffman Tables Coding
2005
An innovative algorithm for automatic generation of Huffman coding tables for semantic classes of digital images is presented. Collecting statistics over a large dataset of corresponding images, we generated Huffman tables for three images classes: landscape, portrait and document. Comparisons between the new tables and the JPEG standard coding tables, using also different quality settings, have shown the effectiveness of the proposed strategy in terms of final bit size (e.g. compression ratio).
Lossless coding of hyperspectral images with principal polynomial analysis
2014
The transform in image coding aims to remove redundancy among data coefficients so that they can be independently coded, and to capture most of the image information in few coefficients. While the second goal ensures that discarding coefficients will not lead to large errors, the first goal ensures that simple (point-wise) coding schemes can be applied to the retained coefficients with optimal results. Principal Component Analysis (PCA) provides the best independence and data compaction for Gaussian sources. Yet, non-linear generalizations of PCA may provide better performance for more realistic non-Gaussian sources. Principal Polynomial Analysis (PPA) generalizes PCA by removing the non-li…
Optimal Partitions of Strings: A New Class of Burrows-Wheeler Compression Algorithms
2003
The Burrows-Wheeler transform [1] is one of the mainstays of lossless data compression. In most cases, its output is fed to Move to Front or other variations of symbol ranking compression. One of the main open problems [2] is to establish whether Move to Front, or more in general symbol ranking compression, is an essential part of the compression process. We settle this question positively by providing a new class of Burrows-Wheeler algorithms that use optimal partitions of strings, rather than symbol ranking, for the additional step. Our technique is a quite surprising specialization to strings of partitioning techniques devised by Buchsbaum et al. [3] for two-dimensional table compression…
Optimized adiabatic passage with dephasing
2008
We study adiabatic population transfer with dephasing in two-level models driven by a chirped driving field. We show that the population transfer is maximized when the dynamics follows specific ellipses as trajectories in the parameter space. We determine the optimal parameters and estimate the losses in a closed form. These estimates show a similar robustness as for the standard lossless adiabatic processes with respect to variations of the parameters.
Efficient image compression using directionlets
2007
Directionlets are built as basis functions of critically sampled perfect-reconstruction transforms with directional vanishing moments imposed along different directions. We combine the directionlets with the space-frequency quantization (SFQ) image compression method, originally based on the standard two-dimensional wavelet transform. We show that our new compression method outperforms the standard SFQ as well as the state-of-the-art image compression methods, such as SPIHT and JPEG-2000, in terms of the quality of compressed images, especially in a low-rate compression regime. We also show that the order of computational complexity remains the same, as compared to the complexity of the sta…
Image compression based on a multi-directional map-dependent algorithm
2007
Abstract This work is devoted to the construction of a new multi-directional edge-adapted compression algorithm for images. It is based on a multi-scale transform that is performed in two steps: a detection step producing a map of edges and a prediction/multi-resolution step which takes into account the information given by the map. A short analysis of the multi-scale transform is performed and an estimate of the error associated to the largest coefficients for a piecewise regular function with Lipschitz edges is provided. Comparisons between this map-dependent algorithm and different classical algorithms are given.
Performance and Implementation Modeling of Gated Linear Networks on FPGA for Lossless Image Compression
2020
Over recent years, imaging systems have seen explosive increase in resolution. These trends present a challenge for resource-constrained embedded imaging devices. Efficient image compression is essential to reduce bandwidth consumption and to increase the capability of on-board storage. Especially, for imaging systems where information loss is not allowed, for example, in medical, military and remote sensing imaging systems. This paper explores the use of Gated Linear Networks (GLNs) for development of embedded lossless compression systems. GLNs have proved themselves via PAQ archiver series, that have been ranked among the top across several lossless compression benchmarks. We propose an a…
A robust and efficient method for obtaining the complex modes in inhomogeneously filled waveguides
2003
In this paper, we present a computational simulation of the complex wave propagation in inhomogeneously filled waveguides with lossless and lossy dielectrics. We use a biorthonormal-basis method as a numerical technique. The behavior of complex modes in different waveguides whose characterization with other methods involves some difficulties is analyzed. © 2003 Wiley Periodicals, Inc. Microwave Opt Technol Lett 37: 218–222, 2003; Published online in Wiley InterScience (www.interscience.wiley.com). DOI 10.1002/mop.10875