Search

We present and evaluate a novel idea for scalable lossy colour image coding with Matching Pursuit (MP) performed in a transform domain. The idea is to exploit correlations in RGB colour space between image subbands after wavelet transformation rather than in the spatial domain. We propose a simple quantisation and coding scheme of colour MP decomposition based on Run Length Encoding (RLE) which can achieve comparable performance to JPEG 2000 even though the latter utilises careful data modelling at the coding stage. Thus, the obtained image representation has the potential to outperform JPEG 2000 with a more sophisticated coding algorithm.

Text based pictures called text art or ASCII art can be noise in text processing and display of text, though they enrich expression in Web pages, email text and so on. With text art extraction methods, which detect text art areas in a given text data, we can ignore text arts in a given text data or replace them with other strings. We proposed a text art extraction method with Run Length Encoding in our previous work. We, however, have not considered how to deal with whitespaces in text arts. In this paper, we propose three whitespace normalization methods in our text art extraction method, and compare them by an experiment. According to the results of the experiment, the best method in the three is a method which replaces each wide width whitespace with two narrow width whitespaces. It improves the average of F-measure of the precision and the recall by about 4%.

We present and evaluate a novel idea for scalable lossy colour image coding with Matching Pursuit (MP) performed in a transform domain. The idea is to exploit correlations in RGB colour space between image subbands after wavelet transformation rather than in the spatial domain. We propose a simple quantisation and coding scheme of colour MP decomposition based on Run Length Encoding (RLE) which can achieve comparable performance to JPEG 2000 even though the latter utilises careful data modelling at the coding stage. Thus, the obtained image representation has the potential to outperform JPEG 2000 with a more sophisticated coding algorithm.

This paper deals with the CBIR of old printed graphics (of XVI° and XVII° centuries) like the headpieces, the pictures and the ornamental letters. These graphical parts are previously segmented from digitized old books in order to constitute image databases for the historians. Today, large databases exist and involves to use automatic retrieval tools able to process large amounts of data. For this purpose, we have developed a fast retrieval system based on a Run Length Encoding (RLE) of images. We use the RLE in an image comparison algorithm using two steps: one of image centering and then a distance computation. Our centering step allows to solve the shifting problems usually met between the segmented images. We present experiments and results about our system concerning the processing time and the retrieval precision.

This paper presents a pipeline algorithm for MPI_Reduce that uses a Run Length Encoding(RLE) scheme to improve the global reduction of sparse floating-point data. The RLE scheme is directly incorporated into the reduction process and causes only low overheads in the worst case. The high throughput of the RLE scheme allows performance improvements when using high performance interconnects, too. Random sample data and sparse vector data from a parallel FEM application is used to demonstrate the performance of the new reduction algorithm for an HPC Cluster with InfiniBand interconnects.

We present a method to speed up the dynamic program algorithms used for solving the HMM decoding and training problems for discrete time-independent HMMs. We discuss the application of our method to Viterbi's decoding and training algorithms [21], as well as to the forward-backward and Baum-Welch [4] algorithms. Our approach is based on identifying repeated substrings in the observed input sequence. We describe three algorithms based alternatively on byte pair encoding (BPE) [19], run length encoding (RLE) and Lempel-Ziv (LZ78) parsing [22]. Compared to Viterbi's algorithm, we achieve a speedup of Ω(r) using BPE, a speedup of Ω(r/log r ) using RLE, and a speedup of Ω(log n/k) using LZ78, where k is the number of hidden states, n is the length of the observed sequence and r is its compression ratio (under each compression scheme). Our experimental results demonstrate that our new algorithms are indeed faster in practice. Furthermore, unlike Viterbi's algorithm, our algorithms are highly parallelizable.

We raise the question of approximating the compressibility of a string with respect to a fixed compression scheme, in sublinear time. We study this question in detail for two popular lossless compression schemes: run-length encoding (RLE) and Lempel-Ziv (LZ), and present sublinear algorithms for approximating compressibility with respect to both schemes. We also give several lower bounds that show that our algorithms for both schemes cannot be improved significantly. Our investigation of LZ yields results whose interest goes beyond the initial questions we set out to study. In particular, we prove combinatorial structural lemmas that relate the compressibility of a string with respect to Lempel-Ziv to the number of distinct short substrings contained in it. In addition, we show that approximating the compressibility with respect to LZ is related to approximating the support size of a distribution.

This study proposes a data hiding method based on run length encoding. This proposed method uses the location of accumulated run length values, where the cover data run length are compared with the secret data run length. The run length matching (RLM) method uses the run length table which is constructed from the cover and secret data. The experimental results demonstrated that the RLM has advantages with respect to different types of data and run length encoding value match.

A succinet full-text self-index is a data structure built on a text T = t1t2...tn, which takes little space (ideally close to that of the compressed text), permits efficient search for the occurrences of a pattern P = p1p2...pm in T, and is able to reproduce any text substring, so the self-index replaces the text.Several remarkable self-indexes have been developed in recent years. Many of those take space proportional to nH0 or nHk bits, where Hk is the kth order empirical entropy of T. The time to count how many times does P occur in T ranges from O(m) to O(m log n).In this paper we present a new self-index, called RLFM index for "run-length FM-index", that counts the occurrences of P in T in O(m) time when the alphabet size is σ = O(polylog(n)). The RLFM index requires nHklogσ + O(n) bits of space, for any k ≤ αlogσn and constant 0 < α < 1. Previous indexes that achieve O(m) counting time either require more than nH0 bits of space or require that σ = O(1). We also show that the RLFM index can be enhanced to locate occurrences in the text and display text substrings in time independent of σ.In addition, we prove a close relationship between the kth order entropy of the text and some regularities that show up in their suffix arrays and in the Burrows-Wheeler transform of T. This relationship is of independent interest and permits bounding the space occupancy of the RLFM index, as well as that of other existing compressed indexes.Finally, we present some practical considerations in order to implement the RLFM index. We empirically compare our index against the best existing implementations and show that it is practical and competitive against those. In passing, we obtain a competitive implementation of an existing theoretical proposal that can be seen as a simplified RLFM index, and explore other practical ideas such as Huffman-shaped wavelet trees.

This paper deals with the implementation of 3D wavelets techniques for compression of medical images, specifically in the MRI modality. We show that at the same compression rate a lower loss of information can be obtained by using fully 3D wavelets as compared to iterated 2D methods. An adaptive thresholding step is performed in each sub-band and a simple Run Length Encoding (RLE) method for compression is finally used. A reconstruction algorithm is then implemented and a comparison study of the reconstructed image is then proposed, showing the high performance of the proposed algorithm.

C code for an accurate projector/backprojector for Positron Emission Tomography (PET) image reconstruction has been developed. Iterative PET image reconstruction methods are supported by a projection/backprojection step built inside of any of such algorithms. It is not surprising that a more precise modeling of the forward process of the measurement will yield better results when solving the inverse problem of image reconstruction. Among the factors that can be include in this forward model are γ-ray scatter contributions, attenuation, positron range, photon non-collinearity, crystal characteristics. Currently, we only include the geometric tube of response (TOR) modeling for a generic multi-ring scanner device. The elements in the transition matrix are calculated by a high statistics Monte Carlo simulation, taking advantage of the inherent symmetries and then the nonzero elements stored in a run length encoding incremental fashion. The resulting projector/backprojector is a voxel driven implementation. We show some preliminary results for 3D ML-EM reconstructions on synthetic phantom simulated data.

Methods such as splat hierarchies, indexing and lists have been presented by the research society in recently years, to accelerate the splatting, a popular volume rendering algorithm. In this paper, a run length encoding (RLE) accelerated, pre-classification and pre-shade sheet buffer volume splatting algorithm is presented, which can enhance the speed of splatting without trading off image quality. This new technique saves rendering time by employing RLE mechanism so that only voxels of interest are processed in splatting. RLE based data structures are defined to exploit spatial coherence of volume and intermediate rendering images. A fast and accurate sheet buffer splatting method is used in the rendering process, which accelerates the splatting by traversing both the voxel scanline and the image scanline in sheet buffer simultaneously. Experiments practice proves that RLE can efficiently skip over transparent voxels in splatting and high speedup can be obtained by using the proposed algorithm.

We examine the technique of run-length encoding in combination with data order, where our attention is focused on good performance of image operations such as, e.g., rotation, reflection, and zooming. To this end we develop a new type of data order that supports these operations well and allows to perform them on a variant of a double-queue automaton directly on the compressed data stream. Because of its shape we call this data order shamrock or S-order. To confirm our theoretical results on S-order we have performed some experiments on sample data using various data orderings that appear in the literature.