In this paper, we focus on the general relay channel. We investigate the application of the estimate-and-forward (EAF) relaying scheme to different scenarios. Specifically, we study assignments of the auxiliary random variable that always satisfy the feasibility constraints. We then consider the Gaussian relay channel with coded modulation, where we show that a three-level quantization outperforms the Gaussian quantization commonly used to evaluate the achievable EAF rates in this scenario. Last, we consider the cooperative general broadcast scenario with a multistep conference between the receivers. We first apply EAF to obtain a general achievable rate region with a multistep conference. We then use an explicit assignment for the auxiliary random variables to obtain an explicit rate expression for the single common message case with a two-step conference.

In this paper we consider the multiple-relay channel. For this scenario there are two well known results: the decode-and- forward (DAF) result of [Xie and Kumar, 2005] and the estimate-and forward (EAF) result of [Kramer et al., 2005]. However, the EAF result does not lend itself to numerical evaluation due to the large number of parameters to be determined and the non-convex nature of the optimization problem for finding the maximum rate. Therefore, for a given channel we cannot tell what is the EAF rate while keeping the expressions in their general form. We propose a specific assignment for the EAF auxiliary variables that satisfy the feasibility constraints and allow us to obtain an explicit EAF-based rate expression. This expression can be easily computed, and compared against the DAF- based rate. We give an example of a channel where this EAF rate is superior to both the DAF and the point-to-point rates.

In this work we consider the Gaussian relay channel with coded modulation at the transmitter and an orthogonal relay- destination link. We investigate the application of the estimate-and- forward (EAF) scheme with different mappings at the relay to this scenario. We show that in certain situations a three-level quantization outperforms the Gaussian mapping, which is the common practice in this scenario. We conclude that for the coded modulation scenario Gaussian quantization is good at low source-relay SNR, decode-and- forward is superior at high source-relay SNR and at intermediate SNR, methods that combine elements of both schemes are superior to these individual assignments. Another observation is that as the source-relay SNR increases, the cardinality of the auxiliary random variable can be decreased.

In this paper, we consider the problem of rate/distortion with side information available only at the decoder. For the case of jointly Gaussian source X and side information Y, and mean-squared error distortion, Wyner proved in 1976 that the rate/distortion function for this problem is identical to the conditional rate/distortion function RX|Y, assuming the side information Y is available at the encoder. In this paper we construct a structured class of asymptotically optimal quantizers for this problem: under the assumption of high correlation between source X and side information Y, we show there exist quantizers within our class whose performance comes arbitrarily close to Wyner's bound. As an application illustrating the relevance of the high-correlation asymptotics, we also explore the use of these quantizers in the context of a problem of data compression for sensor networks, in a setup involving a large number of devices collecting highly correlated measurements within a confined area. An important feature of our formulation is that, although the per-node throughput of the network tends to zero as network size increases, so does the amount of information generated by each transmitter. This is a situation likely to be encountered often in practice, which allows us to cast under new-and more "optimistic"-light some negative results on the transport capacity of large-scale wireless networks

In this paper we consider the problem of using a network of sensor and actuator nodes, to synthesize a given desired wave field, in a given medium we refer to mis problem as the distributed wave field synthesis problem (dubbed dWFS). We formulate this problem as one of minimization of a quadratic function, subject to linear (and very sparse) constraints. This formulation results from a finite-element approximation of the underlying wave equation, which constraints the values that a field and the source that induces that field can take. We present a complete solution for a 1D vibration, although our solution method cart be readily extended to any number of dimensions. Numerical simulations are included

In this paper we consider the general broadcast channel with partially cooperating receivers having noiseless conference links of finite capacity between them. We present an explicit three-step conference scheme, which improves on the two-step scheme presented previously in [Dabora et al., ISIT 05]. The scheme achieves the full cooperation rate bounds at conference capacities that are less than the full cooperation capacities, i.e. C212|Y1) and C121|Y2). We also introduce a new relaying strategy for the general relay channel, which results in a rate increase for any non-degraded channel and does not require auxiliary random variables

We consider the multiterminal source coding problem with general discrete memoryless sources. In previous work, we developed new inner and outer bounds to its rate region, and gave an expression for the gap between them, which explicitly depends on the code maps. In this work, we first construct a class of codes for our problem, based on the method of backward channels used by Csiszár and Körner in their proof of the two-terminal rate/distortion theorem. Next, we show that for each one of the codes in this class, the gap between the inner and the outer bounds above does vanish. Finally, we present a summary of results obtained to date with this purely combinatorial approach, as well as a statement of what it would take to completely solve the problem following this line of attack.

Consider the following network communication setup, originating in a sensor networking application we refer to as the "sensor reachback" problem. We have a directed graph G=(V,E), where V={v/sub 0/v/sub 1/...v/sub n/} and E/spl sube/V/spl times/V. If (v/sub i/,v/sub j/)/spl isin/E, then node i can send messages to node j over a discrete memoryless channel (DMC) (X/sub ij/,p/sub ij/(y|x),Y/sub ij/), of capacity C/sub ij/. The channels are independent. Each node v/sub i/ gets to observe a source of information U/sub i/(i=0...M), with joint distribution p(U/sub 0/U/sub 1/...U/sub M/). Our goal is to solve an incast problem in G: nodes exchange messages with their neighbors, and after a finite number of communication rounds, one of the M+1 nodes (v/sub 0/ by convention) must have received enough information to reproduce the entire field of observations (U/sub 0/U/sub 1/...U/sub M/), with arbitrarily small probability of error. In this paper, we prove that such perfect reconstruction is possible if and only if H(U/sub s/ | U/sub S(c)/) < /spl Sigma//sub i/spl isin/S,j/spl isin/S(c)/ for all S/spl sube/{0...M},S/spl ne/O,0/spl isin/S(c). Our main finding is that in this setup, a general source/channel separation theorem holds, and that Shannon information behaves as a classical network flow, identical in nature to the flow of water in pipes. At first glance, it might seem surprising that separation holds in a fairly general network situation like the one we study. A closer look, however, reveals that the reason for this is that our model allows only for independent point-to-point channels between pairs of nodes, and not multiple-access and/or broadcast channels, for which separation is well known not to hold. This "information as flow" view provides an algorithmic interpretation for our results, among which perhaps the most important one is the optimality of implementing codes using a layered protocol stack.

We consider the problem of communicating over the general discrete memoryless broadcast channel (DMBC) with partially cooperating receivers. In our setup, receivers are able to exchange messages over noiseless conference links of finite capacities, prior to decoding the messages sent from the transmitter. In this paper, we formulate the general problem of broadcast with cooperation. We first find the capacity region for the case where the BC is physically degraded. Then, we give achievability results for the general broadcast channel, for both the two independent messages case and the single common message case

The problem of time synchronization in dense wireless networks is considered. Well-established synchronization techniques suffer from an inherent scalability problem in that synchronization errors grow with an increasing number of hops across the network. In this work, a model for communication in wireless networks is first developed, and then the model is used to define a new time synchronization mechanism. A salient feature of the proposed method is that, in the regime of asymptotically dense networks, it can average out all random errors and maintain global synchronization in the sense that all nodes in the multihop network can see identical timing signals. This is irrespective of the distance separating any two nodes.

Consider a directed graph, in which vertices represent sensor nodes, and edges represent a discrete memoryless channel of a given capacity over which two neighbors nodes can communicate. The channels are independent. Each node gets to observe one element of a set of discrete sources of information drawn i.i.d., according to some joint probability distribution. Our goal is to solve an incast problem in the given graph: nodes exchange messages with their neighbors, and after a finite number of communication rounds, one of the nodes (the data collector) must have received enough information to reproduce the entire set of observations, with arbitrarily small probability of error. In this paper, we give a complete characterization of the conditions on the sources and the channels under which such perfect reconstruction is possible. Close examination of our proof reveals that in this setup, Shannon information behaves as a classical flow, identical in nature to the flow of water in pipes. This "information as flow" view provides an algorithmic interpretation for our results, among which perhaps the most important one is the optimality of using a layered protocol stack

We consider the problem of communicating over the general discrete memoryless broadcast channel (BC) with partially cooperating receivers. In our setup, receivers are able to exchange messages over noiseless conference links of finite capacities, prior to decoding the messages sent from the transmitter. This problem comes up naturally in a sensor networking application, where a transmitter external to the sensor network wants to download data into the network, e.g., to configure the sensor array. In this paper, we extend the achievability results for the degraded broadcast channel derived in R. Dabora and S. Servetto (2004), to the general channel and present an upper bound on the rates

We consider the problem of reachback communication in wireless sensor networks: multiple sensors are deployed on a field, and they collect local measurements of some random process which then need to be encoded and reproduced at a remote location. In this paper we present the design of a distributed modulation scheme for reachback, dubbed dFSK (for distributed frequency shift keying). In dFSK, all nodes in the network first agree on a common stream of bits to send. Then, nodes listen to a few transmissions by other nodes to form an estimate of when to schedule their own transmissions. The aggregate waveform that results from superimposing a large number of these weak transmissions has a pre-specified set of zero-crossings. It is through the location of these zeros that information is conveyed to the far receiver. This mode of operation is analogous to that of standard FSK, where it is through spectral properties of the transmitted symbol (and hence closely related to the rate of its zero-crossings) that information is conveyed to the far receiver.

This paper describes the problem of communicating over broadcast channels (BCs) with partially cooperating receivers. In our setup receivers are able to exchange messages over conference links, prior to making their decisions. This problem comes up naturally in a sensor networking application, where a transmitter external to the sensor network wants to download data into the network to, e.g., configure the sensor array. We find the capacity region for the case where the BC is degraded. This region is a strict enlargement of the classical region for the degraded BC without cooperation in [T.M. Cover,(1998)].

We consider the problem of determining the maximum stable throughput in large-scale random networks under a fairness constraint. The networks are modeled as random unit-disk graphs, and the problem of throughput stability is formulated as one finding the maximum value of a multicommodity flow problem. In this paper, we construct upper and lower bounds on the value of that multicommodity flow problem which, together, provide a tight characterization of an optimal solution to within constants independent of network size. These results contain as a special case those of Gupta and Kumar for random networks, for which an entirely new derivation is provided, using only elementary counting and discrete probability tools.

The sensor broadcast problem: in our setup, sensors measure each one pixel of an image that unfolds over a field, and broadcast a rate constrained encoding of their measurements to every other sensor-the goal is for all sensors to form an estimate of the entire image is considered. In recent work, we proposed a protocol that uses wavelets to decorrelate sensor data, taking advantage of the compact support of the basis functions to keep costly inter-sensor communication at a minimum. In this paper, we prove an asymptotic optimally result for these protocols: the rate of growth for the traffic they generate is /spl Theta/(log(n/D)) (n nodes, total distortion D), matching exactly the rate of growth of the rate/distortion function. We thus close the gap between theory and practice for this new form of massively distributed (one pixel/sensor) image compression, by providing the first efficient and provably optimal algorithms to solve the sensor broadcast problem.

We consider the problem of determining rates of growth for the maximum stable throughput achievable in dense wireless networks. We formulate this problem as one of finding maximum flows on random unit-disk graphs. Equipped with the max-flow/min-cut theorem as our basic analysis tool, we obtain rates of growth under three models of communication: (a) omnidirectional transmissions; (b) "simple" directional transmissions, in which sending nodes generate a single beam aimed at a particular receiver; and (c) "complex " directional transmissions, in which sending nodes generate multiple beams aimed at multiple receivers. Our main finding is that an increase of \t 54 54 in maximum stable throughput is all that can be achieved by allowing arbitrarily complex signal processing (in the form of generation of directed beams) at the transmitters and receivers. We conclude therefore that neither directional antennas, nor the ability to communicate simultaneously with multiple nodes, can be expected in practice to effectively circumvent the constriction on capacity in dense networks that results from the geometric layout of nodes in space.

Summary from only given as follows. In its original formulation, multiple description (MD) coding is a multiuser lossy source coding problem, in which three decoders get to observe encodings of a single source generated by two senders. In general, the rate delivered to each of the decoders is not the same and, based on this, it has been argued that MD codes would be suitable for use as joint source/channel codes in a standard point-to-point problem: low-rate decoders would be used when there is loss of data, and high-rate decoders would be used when more data is available at the receiver. We present an alternative view on the use of MD codes as joint source/channel codes. We show how a channel naturally associated with the standard joint source/channel coding problem based on MDs is a non-ergodic channel that bears little resemblance to packet channels (i.e., those for which MD codes have been proposed in practice) and we propose a simple modification to the MD setup that deals with this. We also consider the problem of designing suitable codes and we show how the associated decoding problem is essentially equivalent to the problem of sequencing DNA strands. The full paper is available from http://www.lnt.e-technik.tu-muenchen.de/mitarbeiter/barros/, http://www.ace.cornell.edu/-servetto/publications/.

We consider the problem of distributing high-quality video signals over IP multicast in large local area networks (LANs), under realtime delay constraints, and with software-only processing. In a large LAN (such as the network of a university campus, or the network of a large company), the source of channel heterogeneity that the video communications system must cope with is not that of different bandwidth constraints available to each receiver, but it is essentially variations in the available CPU power that each receiver has in order to decode the incoming signal. We propose a new architecture for a video multicast system, present the design of the different components of this system, and show results obtained in a real implementation. Our feeds consist of video encoded at about 3 Mbits/sec and 16 frames/sec, capable of tolerating the loss of about 300 Kbits/sec worth of data. Decoding is performed on Linux PCs, and the quality of our reconstructed signals degrades gracefully with the speed of the CPU on which the receiver runs.

We consider a problem of broadcast communication in a multi-hop sensor network, in which samples of a random field are collected at each node of the network, and the goal is for all nodes to obtain an estimate of the entire field within a prescribed distortion value. The main idea we explore in this paper is that of jointly compressing the data generated by different nodes as this information travels over multiple hops, to eliminate correlations in the representation of the sampled field. Our main contributions are: (a) we obtain, using simple network flow concepts, conditions on the rate/distortion function of the random field, so as to guarantee that any node can obtain the measurements collected at every other node in the network, quantized to within any prescribed distortion value; and (b), we construct a large class of physically-motivated stochastic models for sensor data, for which we are able to prove that the joint rate/distortion function of all the data generated by the whole network grows slower than the bounds found in (a). A truly novel aspect of our work is the tight coupling between routing and source coding, explicitly formulated in a simple and analytically tractable model---to the best of our knowledge, this connection had not been studied before.

Multiple description (MD) coding is a source coding technique for information transmission over unreliable networks. In MD coding, the coder generates several different descriptions of the same signal and the decoder can produce a useful reconstruction of the source with any received subset of these descriptions. In this paper, we study the problem of MD coding of stationary Gaussian sources with memory. First, we compute an approximate MD rate distortion region for these sources, which we prove to be asymptotically tight at high rates. This region generalizes the MD rate distortion region of El Gamal and Cover (1982), and Ozarow (1980) for memoryless Gaussian sources. Then, we develop an algorithm for the design of optimal two-channel biorthogonal filter banks for MD coding of Gaussian sources. We show that optimal filters are obtained by allocating the redundancy over frequency with a reverse "water-filling" strategy. Finally, we present experimental results which show the effectiveness of our filter banks in the low complexity, low rate regime.

We consider the problem of designing codes for the problem of delay-constrained communication in packet networks. We show how good codes for this problem can be characterized as the solution of a pair of semidefinite programs plus a rank constraint. Using this characterization, we formulate the design problem as one of finding suitable graph embeddings into Euclidean space, for a certain family of graphs which represent constraints that these codes most satisfy. In the case of codes in dimension 1, our formulation results in a good approximation algorithm for the classical problem of graph bandwidth, which may be of independent interest.

The problem of designing a multiple-description vector quantizer with lattice codebook /spl Lambda/ is considered. A general solution is given to a labeling problem which plays a crucial role in the design of such quantizers. Numerical performance results are obtained for quantizers based on the lattices A/sub 2/ and Z/sup i/, i=1, 2, 4, 8, that make use of this labeling algorithm. The high-rate squared-error distortions for this family of L-dimensional vector quantizers are then analyzed for a memoryless source with probability density function (PDF) p and differential entropy h(p)

We consider the problem of designing systems for the transmission of video signals of the quality found in current television broadcasts, over high-speed segments of the public IP network. Our most important contribution is the definition of a network/coder interface for IP networks which gathers channel state information, and then sets parameters of the video coder to maximize the quality of the signal delivered to the receiver, while remaining fair to other data or video connections. This interface plays a role analogous to that of a Leaky Bucket controller, in that it specifies traffic shaping parameters which result in simultaneous good Quality-of-Service (QoS) for the source and good network performance. Since the network is not assumed to provide any form of QoS guarantee, fundamental to our construction is a hidden Markov model for the channel, based on which the interface solves a problem of optimal stochastic control, to decide how to configure the encoder. Other contributions are: a) modifications to the standard Internet transport protocol, to make it suitable for the transport of delay-constrained traffic and to gather channel state information, and b) the design of an error-resilient video coder. Experimental studies reveal that the proposed system is able to stream video signals of the quality of current TV-broadcasts, among hosts in wide-area networks connected to the experimental vBNS backbone.

We study the problem of multiple description (MD) coding of stationary Gaussian sources with memory. First, we compute an approximate rate distortion region for these sources, which we prove to be asymptotically tight at high rates: this region generalizes the standard MD rate distortion region for memoryless sources. Then we develop an algorithm for the design of optimal biorthogonal filter banks for MD coding. Finally. We present some experimental results, where we measure the deviation from optimality of our proposed system. For almost uncorrelated sources the gap between the performance of our proposed system and the ideal bounds is quite high, on the other hand for highly correlated sources this gap is reduced, due to the ability of our system to take advantage of the memory in the source. In this case, in realistic scenarios where finite complexity/delay is an issue, the subband coding approach is competitive with other approaches such as the decorrelating transform followed by MD scalar quantizers.

We consider the design of lattice vector quantizers for the problem of coding Gaussian sources with uncoded side information available only at the decoder. The design of such quantizers can be reduced to the problem of finding an appropriate sublattice of a given lattice codebook. We study the performance of the resulting quantizers in the limit as the encoding rate becomes high, and we evaluate these asymptotics for three lattices of interest: the hexagonal lattice A/sub 2/, the Gosset lattice E/sub 8/, and the Leech lattice /spl Lambda//sub 24/. We also verify these asymptotics numerically, via computer simulations based on the lattice A/sub 2/. Surprisingly, the lattice E/sub 8/ achieves the best performance of all cases considered.

We consider the problem of video multicast over networks that enforce fair bandwidth allocations in the routers. State-of-the-art layered IP multicast systems perform well for moderately sized sessions, but suffer from three basic problems that prevent their massive deployment: (a) lack of fairness among different multicast sessions, (b) lack of fairness to competing TCP flows, and (c) high complexity requirements to scale up to potentially large numbers of users and sessions. In this work we present an entirely different approach to the design of these systems, in which sources obliviously inject packets into the network (disregarding congestion), whereas routers obliviously drop the amount of bandwidth that exceeds the fair share of a flow (disregarding packet contents). We model our system as a broadcast channel, with receivers connected to the source via erasure channels of different capacities, and we design a video coder to operate in this environment. Our results suggest that a combination of fair queueing routers and appropriate coding is indeed able to overcome certain drawbacks of current IP multicast systems. Furthermore, we also find that such systems would benefit significantly from being able to re-encode the video signal at internal nodes of the multicast tree.

We consider the problem of coding images for transmission over error-prone channels. The impairments we target are transient channel shutdowns, as would occur in a packet network when a packet is lost, or in a wireless system during a deep fade: when data is delivered it is assumed to be error-free, but some of the data may never reach the receiver. The proposed algorithms are based on a combination of multiple description scalar quantizers with techniques successfully applied to the construction of some of the most efficient subband coders. A given image is encoded into multiple independent packets of roughly equal length. When packets are lost, the quality of the approximation computed at the receiver depends only on the number of packets received, but does not depend on exactly which packets are actually received. When compared with previously reported results on the performance of robust image coders based on multiple descriptions, on standard test images, our coders attain similar PSNR values using typically about 50-60% of the bit rate required by these other state-of-the-art coders, while at the same time providing significantly more freedom in the mechanism for allocation of redundancy among descriptions.

We consider the problem of designing a lattice-based multiple description vector quantizer for a two-channel diversity system. The design of such a quantizer can be reduced to the problem of assigning pair labels to points of a vector quantizer codebook. A general labeling procedure based on the structure of the lattice is presented, along with detailed results for the hexagonal lattice: algorithms, asymptotic performance, and numerical simulations. Asymptotically, when compared with the lattice Z, the resulting quantizer achieves the standard second-moment gain of the hexagonal lattice for the central distortion, and, surprisingly, achieves the two-dimensional sphere gain for the side distortion.

The problem of video transmission over IP networks is considered in this paper: we present the design of a complete system for the transmission of high-quality video signals over the public Internet. Our system involves: (1) modifications to the standard Internet transport protocol (TCP), to make it suitable for the transport of delay-constrained traffic, and to gather channel state information; (2) the design of an error-resilient video coder; and (3) the design of a controller which uses channel state information provided by the modified protocol, to configure the error-resilient coder accordingly. Experimental studies performed on certain high-speed segments of the public Internet reveal that the proposed system is able to deliver video signals at bit rates in the range of 4-9 Mbits/sec, not only within fast LANs but also, and more surprisingly, even between sites in the US and Europe. That is, over existing public IP channels, our proposed system can deliver video at TV-broadcast quality.

In this paper, an experimental study of the statistical properties of wavelet coefficients of image data is presented, as well as the design of two different morphology-based image coding algorithms that make use of these statistics. A salient feature of the proposed methods is that, by a simple change of quantizers, the same basic algorithm yields high performance embedded or fixed rate coders. Another important feature is that the shape information of morphological sets used in this coder is encoded implicitly by the values of wavelet coefficients, thus avoiding the use of explicit and rate expensive shape descriptors. These proposed algorithms, while achieving nearly the same objective performance of state-of-the-art zerotree based methods, are able to produce reconstructions of a somewhat superior perceptual quality, due to a property of joint compression and noise reduction they exhibit.

We study certain aspects of the problem of watermarking images, not for the classical example of ownership identification, but instead for embedding a unique identifier that can act as a "serial number" for the image in which it is embedded. In this context, two fundamental questions are: (a) what is the maximum number of different watermarks that can be distinguished reliably? and (b) what are good design techniques for watermarking methods to approximate that maximum? Under the assumption that attacks can be modeled as additive noise, we provide answers to both questions. To answer (a), we first show how the process of inserting a watermark is analogous to that of storing bits in certain devices, and then we compute the storage capacity of these devices. To answer (b), we present a specific design of a modulator to store information in those devices. Numerical simulations reveal that although strongly suboptimal in the number of bits they can effectively store in an image, simple and very low complexity modulator designs are able to pack enough bits in an image to be useful in practice.

We consider the problem of image coding for communication systems that use diversity to overcome channel impairments. We focus on the special case in which there are two channels of equal capacity between a transmitter and a receiver. Our designs are based on a combination of techniques successfully applied to the construction of some of the most efficient wavelet based image coding algorithms, with multiple description scalar quantizers (MDSQs). For a given image, we produce two bitstreams, to be transmitted over each channel. Should one of the channels fail, each individual description guarantees a minimum image quality specified by the user. However, if both descriptions arrive at destination, they are combined to produce a higher quality image than that achievable based on individual descriptions. We formulate a discrete optimization problem, whose solution gives parameters of the proposed encoder yielding optimal performance in an operational sense. Simulation results are presented.

Variable bit rate (VBR) transmission is widely regarded as the best solution for the transport of compressed image and video data, both in terms of network utilization and quality of data decoded at the receiver. However, significant problems remain unsolved to make this a viable approach. One of these problems is that of efficiently matching characteristics of the VBR source to those of the channel, in order to maximize end-to-end system performance. In this work, we propose a model for the channel based on which the source can make optimal decisions regarding bit allocation and rate control. This model consists of N queues, for each of which the source negotiates with the network statistical performance guarantees, consisting of allowable average transmission and packet loss rates. Based on such a channel description, the source determines how to allocate packets to each queue, to minimize the expected distortion of the images reconstructed at the receiver. A provably optimal algorithm for computing such bit allocations is the core of this work. Simulation results are presented.

Zerotree based algorithms represent the state of the art in wavelet based image coding. At a high level, these algorithms can be described as first sending a map of the locations of the zero coefficients (the set of zerotree symbols), and then sending the value of nonzero coefficients. However, the decision of what map to send is typically made using some simplifying assumption on the structure of the map, motivated by some empirically observed property of the data (e.g., that zero coefficients are likely to appear in tree structured sets). In this article, the map of the locations of the zero coefficients is optimally estimated as a hidden binary Markov random field (MRF). Algorithms are presented for the estimation of the hidden field given the observed wavelet coefficients, for encoding the field, and for encoding the data given the field estimate. Simulation results show a very competitive rate/distortion performance of the coding algorithm, equal or superior to any published zerotree based image coder: this fact provides conclusive empirical evidence that the proposed model is appropriate for the data.

Content based retrieval of image and video data from databases is a very challenging problem, whose interest is derived from the need of future databases to support efficient access to vast amounts of visual information. Typical queries to be performed in this context check attributes of objects present in image data, such as shape, color, relative locations, etc. Therefore, the way in which image data is represented plays a fundamental role in the efficient implementation of those queries. One possibility is to take the naive approach of storing images using standard compression techniques, storing image features (such as object shape descriptors, color histograms, etc.) as explicit side information, and whenever an image is involved in the evaluation of a query decoding it to full resolution; however, many more efficient techniques (in terms of storage and computational requirements) are possible. We propose a new image coding technique which combines a wavelet image representation, embedded coding of the wavelet coefficients, and segmentation of semantically meaningful objects in the wavelet domain, to generate a bitstream in which each object is encoded independently of every other object in the image, and without explicitly storing shape boundary information. Furthermore, since the representation of each object is fully embedded, applications may, independently for each object, specify the desired target bitrate and retrieve bits from the compressed bitstream.

Proposes an improved statistical characterization of the field of wavelet coefficients of natural images. Based on this characterization, the authors introduce morphological representation of wavelet data (MRWD), a novel coding framework for both image and video coding applications. MRWD departs from existing wavelet-based coders in its use of a radically different set of primitive operations-non-linear, morphological operations-for efficiently encoding the wavelet data field. Simulation results are very encouraging: a preliminary algorithm based on the morphological data structure is able to achieve about 0.5 dB of gain in SNR over Shapiro's (1993) state-of-the-art zerotree-based wavelet coder at a coding rate of 1 bpp for the "Lena" image.

In previous work, we introduced a new image representation for the field of wavelet coefficients (dubbed MRWD), based on morphological operators. This work extends the MRWD framework, by addressing the effective design of image coding algorithms. First, we design an encoder with the goal of being optimal in the operational rate-distortion sense. Second, based on the same (morphological) techniques, we design a successively refinable version of the single rate coder. Simulation results are reported.