**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Grammar-Based Tree Compression

2004

Report or working paper

Report or working paper

Abstract

Grammar-based compression means to find a small grammar that generates a given object. Such a grammar reveals the structure of the object (according to the grammar formalism used); the main advantage of this compression method is that the resulting grammar can often be used in further computations without prior decompression. A linear time bottom-up algorithm is presented which transforms a tree into a particular context-free tree grammar. For common XML documents the algorithm performs well, compressing the tree structure to about 5 per cent of the original size. The validation of an XML document against an XML type can be done without decompression, in linear time w.r.t. the size of the grammar (for a fixed type). While the involved grammars can be double exponentially smaller than the represented trees, testing them for equivalence can be done in polynomial space w.r.t. the sum of their sizes.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related publications (11)

Loading

Loading

Loading

Related concepts (16)

Grammar

In linguistics, the grammar of a natural language is its set of structural rules on speakers' or writers' usage and creation of clauses, phrases, and words. The term can also refer to the study of su

Tree

In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, including only woody plants

Context-free grammar

In formal language theory, a context-free grammar (CFG) is a formal grammar whose production rules
can be applied to a nonterminal symbol regardless of its context.
In particular, in a context-free

Digital images are becoming increasingly successful thanks to the development and the facilitated access to systems permitting their generation (i.e. camera, scanner, imaging software, etc). A digital image basically corresponds to a 2D discrete set of regularly spaced samples, called pixels, where each pixel contains the light intensity information (e.g., luminance, chrominance) of a very localized spatial region of the image. In the case of natural images, pixel values are acquired through one or several arrays of MOS semiconductors (Charge Couple Devices, CCDs), each generating an electrical information proportional to the incoming light intensity. The initial finalities of digital images were the storage on a dedicated medium (e.g., camera's memory, computer's hard drive, CDROM), eventual transmissions, and final display on a screen or printing. With such a narrow scope, the principal goal of image processing and coding tools was to face storage and transmission bandwidth limitations thanks to efficient compression algorithms reducing the image representation size. However, with recent developments in computing, algorithmic and telecommunication domains, many new applications (i.e. web-publishing, remote browsing etc.) have arisen. They generally require additional and enhanced features (i.e. progressive decoding, random-access, region of interest support, robustness to transmission errors, etc.) and have motivated the creation of a new generation of coding algorithms which, besides their good compression performance, present many other useful features. Hence, digital images are almost never represented as a simple set of pixel values (i.e. raw representation) but, instead, under a specific compact way (i.e. compressed or coded representation), chosen according to features it brings to the considered application. A compressed version of an image is obtained by removing as much spatial, visual and statistical redundancies as possible, thanks to appropriate coding methods, while keeping an acceptable visual quality. Noting that natural images have most of their energy concentrated in low frequency components, recent coding algorithms generally first decompose the image into a specific frequency domain DCT, DWT, etc). The goal is to obtain a representation, where few coefficients are sufficient for reconstructing the image with a good quality. The precision of transformed coefficients is then generally reduced by quantization in order to make them more compressible by an entropy coder, aiming at removing statistical redundancies of quantization indexes. The ultimate compressed representation, called codestream, is usually obtained by a rate-allocation process that tries to achieve the best trade-off between the compression ratio and the reconstructed image quality. JPEG 2000, the new still image coding standard developed by the Joint Photographic Experts Group JPEG), is based on these state-of-the-art compression techniques, but is also designed to fulfill many requirements of recent applications. It only normalizes the decoding algorithm and consequently let some liberty for designing encoders optimized for some specific features or for building extensions that take profit from its compressed domain specifics. The success of the JPEG 2000 standard will not only depend on its intrinsic performance, but also on its ability to comply with specific demands of actual and future imaging applications. Thus, among the major concerns of image content providers are the security of the transmission over networks and of the image itself: with current facilities to instantly access on-line digital libraries from anywhere in the world, to perfectly copy and to easily modify the content of an image, solutions must be found in order to permit, at one hand, Intellectual Property Right (IPR) protection and image integrity verification and, at the other hand, the development of dedicated tools favoring exchange and purchase of images over communication networks. It is worth pointing out that some cryptographic-based solutions to these problems already exist. However, they need to be adapted to the digital image and its compressed domain representation in order to take full advantage from their specifics and to avoid restraining fields of applications. The JPEG 2000 coding algorithm is mainly based on Discrete Wavelet Transform (DWT), embedded scalar quantization and adaptive arithmetic coding. From a terminology point of view, this means that compressed domain representation can indifferently refer to either wavelet coefficients, or quantized wavelet coefficients, or bit streams (i.e. entropy coded group of quantization indexes) or the codestream (i.e. aggregation of bit streams and headers containing necessary decoding information). The choice of the appropriate compressed domain actually depends on the considered application. The quality of a JPEG 2000 image, at a given compression ratio, mainly depends on the rate-allocation procedure used at the encoder side. Such a procedure applies on entropy coded quantization indexes and favors groups of quantization indexes (i.e. code-blocks) offering the best rate-distortion trade-offs. However, this does not necessary correspond to the most interesting part of the image, from an end-observer point of view. Hence, the standard provides with ways to define Regions Of Interest (ROI) which are prioritized during the encoding process in order to exhibit a higher quality than the rest (i.e. background) at any decoding time. This feature applies either in the quantized wavelet domain or at the bit stream level, but its parameters are generally not very explicit for a standard end-user and only provide with a rough control of the decoded ROI quality. Consequently, the first objective of this thesis is to create and also extend compressed domain tools for controlling the quality of a JPEG 2000 ROI. In the meantime, several image processing techniques, such as watermarking, are applied directly in the spatial domain or in a specific transform space defined from the spatial domain. However, since digital images are preferably available under a compressed/encoded format, which we assume to be JPEG 2000 in this thesis, their implementation first imply decompressing the image, then apply the considered processing task and finally re-encode the resulting image. Such a scheme has two main drawbacks: First, it generally implies time and complexity overheads compared to equivalent methods (if they exist) in the JPEG 2000 compressed domain. Such effects become important when the scheme is repeatedly applied on multiple images. Second, since encoding and decoding operations are generally lossy, the introduced distortion can become non negligible whenever several processing tasks are repeated on a same image. These observations lead to the second objective of this thesis, which is to adapt or create a watermarking algorithm dedicated to the JPEG 2000 compressed domain. Finally, there are imaging algorithms, such as authentication and access control, that already exist and could be directly applied to JPEG 2000 images but, because they do not take into account the coding algorithm specifics, they either decrease compression performance or remove useful features of the encoded representation (scalability, random access, etc). This leads to the third objective of this thesis, which is to adapt, create and combine authentication and access control algorithms with JPEG 2000 coding and decoding. Thus, the common goal of the three objectives described above is the deep integration of selected processing and security algorithms into a JPEG 2000 codec in order to provide with minimum complexity, JPEG 2000 compliant codestreams and an unified framework for many imaging applications.

The invention of Fountain codes is a major advance in the field of error correcting codes. The goal of this work is to study and develop algorithms for source and channel coding using a family of Fountain codes known as Raptor codes. From an asymptotic point of view, the best currently known sum-product decoding algorithm for non binary alphabets has a high complexity that limits its use in practice. For binary channels, sum-product decoding algorithms have been extensively studied and are known to perform well. In the first part of this work, we develop a decoding algorithm for binary codes on non-binary channels based on a combination of sum-product and maximum-likelihood decoding. We apply this algorithm to Raptor codes on both symmetric and non-symmetric channels. Our algorithm shows the best performance in terms of complexity and error rate per symbol for blocks of finite length for symmetric channels. Then, we examine the performance of Raptor codes under sum-product decoding when the transmission is taking place on piecewise stationary memoryless channels and on channels with memory corrupted by noise. We develop algorithms for joint estimation and detection while simultaneously employing expectation maximization to estimate the noise, and sum-product algorithm to correct errors. We also develop a hard decision algorithm for Raptor codes on piecewise stationary memoryless channels. Finally, we generalize our joint LT estimation-decoding algorithms for Markov-modulated channels. In the third part of this work, we develop compression algorithms using Raptor codes. More specifically we introduce a lossless text compression algorithm, obtaining in this way competitive results compared to the existing classical approaches. Moreover, we propose distributed source coding algorithms based on the paradigm proposed by Slepian and Wolf.

Reconstructing complex curvilinear structures such as neural circuits, road networks, and blood vessels is a key challenge in many scientific and engineering fields. It has a broad range of applications, from the delineation of micrometer-sized neurons in micrographs to the detection of Earth-sized solar filaments in telescope images. Modern data acquisition systems can produce very large volumes of such imagery in a short period of time. However, despite the abundance of available imagery and the ever-growing demand driven by the applications, existing reconstruction techniques are not robust to noisy and complex data, and require extensive manual intervention that is both time-consuming and tedious. In this thesis, we propose semi-and fully-automated approaches to overcome these limitations. To this end, we first present a novel filtering method that enhances irregular curvilinear structures in noisy image stacks. Unlike earlier approaches that rely on over-simplistic shape models for the structures and that work only on gray-scale images, ours exploits the color information and allows for the arbitrarily-shaped structures that are prevalent in biological imagery. We build a complete semi-automated reconstruction system based on this filtering approach and use it to collect highly accurate delineations from a wide range of datasets. We then propose a novel probabilistic algorithm to automate reconstruction, which uses these delineations as training data to compute, at each image pixel, the likelihood that the pixel is on the centerline of a curvilinear structure. Our algorithm first builds a graph of potential paths using these likelihoods and then seeks to find the tree that best explains the image data and that has spatially smooth branches. In contrast to other graph-based approaches that first span all the vertices and then prune some of the spurious branches using a heuristic procedure, ours selects an appropriate subset of the vertices to be spanned by optimizing a global objective function that explicitly models spurious branches, and combines the data likelihood with a geometric prior. A major limitation common to all graph-based approaches, including this one, is that they model the curvilinear networks as tree structures, which does not apply to many interesting networks such as roads and blood vessels. Furthermore, they rely on heuristic optimization algorithms, which do not provide optimality guarantees. Finally, the data terms in their objective functions are relatively local and have very little informative value. To address these limitations, we propose a new supervised Bayesian approach, which uses path classifiers trained on global appearance and path geometry features, and a Mixed Integer Programming formulation to guarantee optimality of the resulting solutions. Unlike all previous approaches, ours explicitly models the fact that the networks may be cyclic and allows graph vertices to be used more than once, subject to structural and topological constraints. We demonstrate the effectiveness of our approaches on a variety of challenging gray-scale and color datasets including aerial images of road networks and micrographs of neural arbors, and show that they outperform state-of-the-art techniques.