The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
A standard way of implementing Huffman's optimal code construction algorithm is by using a sorted sequence of frequencies. Using only partial order may speed up the code construction, which is important in some applications, at the cost of possibly increasing the size of the encoded file.
Abstract Researchers have proposed using hardware data compression units within the memory hierarchies of microprocessors in order to improve performance, energy efficiency, and functionality. However, most past work, and in particular work on cache compression, has made unsubstantiated assumptions about the performance, power consumption, and area overheads of the required compression hardware. We...
We consider a setting relevant to the design of storage systems in which a list of defective storage blocks, as determined at manufacture time, is stored in a high-speed system controller memory to enable the efficient bypassing of defective blocks in a transparent manner, external to the system. Conventionally, such lists have been compressed losslessly to save on the cost of the controller memory...
The past few years have witnessed several exciting results on compressed representation of a string T that supports efficient pattern matching, and the space complexity has been reduced to |T| Hk (T) + o (|T| log sigma) bits, where Hk(T) denotes the kth-order empirical entropy of T, and sigma is the size of the alphabet. In this paper we study compressed representation for another classical problem...
Saturated patterns with don't care like those emerged in biosequence motif discovery have proven a valuable notion also in the design of lossless and lossy compression of sequence data. In independent endeavors, the peculiarities inherent to the compression of tables have been examined, leading to compression schemata advantageously hinged on a prudent rearrangement of columns. The present paper introduces...
In order to maximize coding efficiency the coding algorithm must ensure the probability of encoding a sequence of n quantized symbols at a rate smaller than R is maximized (i.e. there is no need to increase the quantization step size). This optimization problem is different from the one solved by algorithms like Huffman coding in which it is assumed that a large sequence of symbols are being coded...
Burrows-Wheeler Transform (BWT) is used as the main part in block compression which has a good balance of speed and compression ratio. Suffix arrays are used in the coding phase of BWT and we focus on creating them for an alphabet larger than 256 symbols. The motivation for this work has been software project XBW-an application for compression of large XML files using word- and syllable-based BWT...
Rate allocation in the JPEG2000 image compression algorithm is performed by the EBCOT algorithm, measures file size and distortion, defined as mean square error (MSE). Since MSE correlates only mediocre to visual quality, more advanced metrics like the M-SSIM have been proposed. One exploitable effect of the human visual system is that of visual masking: If a structure of a fixed amplitude is overlayed...
A low complexity multiple description (MD) coding method is proposed to generate M descriptions. Consider the MD coding of a stationary correlated source. We first fictitiously partition the source into sample blocks of size M, i.e., M polyphases. Each description encodes all input samples, but with a variable bit rate that depends on the indices of the sample and the description. A special DPCM encoder...
Summary form only given. Objective quality assessment of lossy image compression codecs have become an important part of the recent call of the JPEG committee for advanced image coding. We evaluated JPEG with Huffman and arithmetic coding option, a visual and PSNR optimal JPEG2000 version, H.264/AVC and the recently proposed HDPhoto format by Microsoft. For objective evaluation, we use a color version...
Re-pair is a dictionary-based compression method invented in 1999 by J. Larsson and A. Moffat [Off-line dictionary-based compression. Proc. IEEE, 88(11):1722-1732, 2000], lacking up to now an efficiency analysis. We show that re-pair compresses a sequence T[1,n] over an alphabet of size sigma to at most 2nHk + o(n log sigma) bits, for any k = o(logsigma n), where Hk is either the classical information-theory...
We consider symmetric multiple description coding for the Gaussian source, and provide upper and lower bounds for the individual description rate-distortion function. One of the main contributions of this work is a novel lower bound on the sum rate under symmetric distortion constraints, which yields a lower bound on the individual rate for the symmetric case. Two upper bounds are derived, the first...
The design of optimal multiple description scalar quantizers was pioneered by Vaishampayan with a generalization of Lloyd's algorithm, which alternatively optimizes the decoder, respectively the encoder, while the other component is fixed. We propose an algorithm which speeds up the encoder optimization step from O(N2) to O(N log N) time complexity, where N is the number of cells in the central partition.
Recent advances in compressed data structures have led to the new concept of self-indexing; it is possible to represent a sequence of symbols compressed in a form that enables fast queries on the content of the sequence. This paper studies different analogies of self-indexing on images. First, we show that a key ingredient of many self-indexes for sequences, namely the wavelet tree, can be used to...
This paper investigates the design and application of the optimal filter banks for a prediction-compensated multiple description coding (PC-MDC) scheme, where the coefficients in each subband are split into two descriptions. Each description also includes the prediction residuals of the data in the other description. The optimal designs of orthogonal and biorthogonal filter banks with multiple-level...
In this paper, we derive bounds on the structural similarity (SSIM) index as a function of quantization rate for fixed-rate uniform quantization of image discrete cosine transform (DCT) coefficients under the high rate assumption. The space domain SSIM index is first expressed in terms of the DCT coefficients of the space domain vectors. The transform domain SSIM Index is then used to derive bounds...
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.