Search results for "data compression"
showing 10 items of 99 documents
Compression-based classification of biological sequences and structures via the Universal Similarity Metric: experimental assessment.
2007
Abstract Background Similarity of sequences is a key mathematical notion for Classification and Phylogenetic studies in Biology. It is currently primarily handled using alignments. However, the alignment methods seem inadequate for post-genomic studies since they do not scale well with data set size and they seem to be confined only to genomic and proteomic sequences. Therefore, alignment-free similarity measures are actively pursued. Among those, USM (Universal Similarity Metric) has gained prominence. It is based on the deep theory of Kolmogorov Complexity and universality is its most novel striking feature. Since it can only be approximated via data compression, USM is a methodology rath…
Dictionary-symbolwise flexible parsing
2012
AbstractLinear-time optimal parsing algorithms are rare in the dictionary-based branch of the data compression theory. A recent result is the Flexible Parsing algorithm of Matias and Sahinalp (1999) that works when the dictionary is prefix closed and the encoding of dictionary pointers has a constant cost. We present the Dictionary-Symbolwise Flexible Parsing algorithm that is optimal for prefix-closed dictionaries and any symbolwise compressor under some natural hypothesis. In the case of LZ78-like algorithms with variable costs and any, linear as usual, symbolwise compressor we show how to implement our parsing algorithm in linear time. In the case of LZ77-like dictionaries and any symbol…
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…
The impact of irreversible image data compression on post-processing algorithms in computed tomography
2020
PURPOSE: We aimed to evaluate the influence of irreversible image compression at varying levels on image post-processing algorithms (3D volume rendering of angiographs, computer-assisted detection of lung nodules, segmentation and volumetry of liver lesions, and automated evaluation of functional cardiac imaging) in computed tomography (CT). METHODS: Uncompressed CT image data (30 angiographs of the lower limbs, 38 lung exams, 20 liver exams and 30 cardiac exams) were anonymized and subsequently compressed using the JPEG2000 algorithm with compression ratios of 8:1, 10:1, and 15:1. Volume renderings of CT angiographies obtained from compressed and uncompressed data were compared using objec…
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…
Improving Karhunen-Loeve based transform coding by using square isometries
2002
We propose, for an image compression system based on the Karhunen-Loeve transform implemented by neural networks, to take into consideration the 8 square isometries of an image block. The proper isometry applied puts the 8*8 square image block in a standard position, before applying the image block as input to the neural network architecture. The standard position is defined based on the variance of its four 4*4 sub-blocks (quadro partitioned) and brings the sub-block having the greatest variance in a specific corner and in another specific adjoining corner the sub-block having the second variance (if this is not possible the third is considered). The use of this "preprocessing" phase was e…
A Digital Watermarking Algorithm Based on Quantization of the DCT: Application on Medical Imaging
2013
International audience; The objective of this paper is to elaborate a new watermarking algorithm applied to the medical imaging. This algorithm must be invisible, robust and has a rate, relatively high, integrating data. The proposed method uses the standard JPEG compression for the integration of medical data. The insertion block is inserted just after the quantization phase. To control identification and eventually the correction (if possible) of the inserted data, we use a series of turbocodes to recover the inserted data, after application of several attacks. The simulation studies are applied on MRI medicals images.
LoRa-Based Sensor Node Energy Consumption with Data Compression
2021
In this paper simple temporal compression algorithms' efficiency to reduce LoRa-based sensor node energy consumption has been evaluated and measured. It is known that radio transmission is the most energy consuming operation in a wireless sensor node. In this paper three lightweight compression algorithms are implemented in an embedded LoRa platform to compress sensor data in on-line mode and the overall energy consumption is measured. Energy consumption is compared to the situation without implementing any compression algorithm. The results show that a simple compression algorithm is an effective method to improve the battery powered sensor node lifetime. Despite the radio transmission's h…
Block Sorting-Based Transformations on Words: Beyond the Magic BWT
2018
The Burrows-Wheeler Transform (BWT) is a word transformation introduced in 1994 for Data Compression and later results have contributed to make it a fundamental tool for the design of self-indexing compressed data structures. The Alternating Burrows-Wheeler Transform (ABWT) is a more recent transformation, studied in the context of Combinatorics on Words, that works in a similar way, using an alternating lexicographical order instead of the usual one. In this paper we study a more general class of block sorting-based transformations. The transformations in this new class prove to be interesting combinatorial tools that offer new research perspectives. In particular, we show that all the tra…
Parallel Construction and Query of Index Data Structures for Pattern Matching on Square Matrices
1999
AbstractWe describe fast parallel algorithms for building index data structures that can be used to gather various statistics on square matrices. The main data structure is the Lsuffix tree, which is a generalization of the classical suffix tree for strings. Given ann×ntext matrixA, we build our data structures inO(logn) time withn2processors on a CRCW PRAM, so that we can quickly processAin parallel as follows: (i) report some statistical information aboutA, e.g., find the largest repeated square submatrices that appear at least twice inAor determine, for each position inA, the smallest submatrix that occurs only there; (ii) given, on-line, anm×mpattern matrixPAT, check whether it occurs i…