Zero-error coding encompasses a variety of source and channel problems where the probability of error must be exactly zero. This condition is stricter than that of the vanishing error regime, where the error probability goes to zero as the code blocklength goes to infinity. In general, zero-error coding is an open combinatorial question. We investigate two unsolved zero-error problems: the source coding problem with side information and the channel coding problem. We focus our attention on families of independent problems for which the probability distribution decomposes into a product of probability distributions. A crucial step is the additivity property of the optimal rate, which does not always hold in the zero-error regime, unlike in the vanishing error regime. When the additivity holds, the concatenation of optimal codes is optimal. We derive a condition under which the additivity of the complementary graph entropyHfor the AND product of graphs and for the disjoint union of graphs are equivalent. Then we establish the connection with a recent result obtained by Wigderson and Zuiddam and by Schrijver, for the zero-error capacityC0. As a consequence, we provide new single-letter characterizations ofHandC0, for example when the graph is a product of perfect graphs, which is not perfect in general, and for the class of graphs obtained by the product of a perfect graphGwith the pentagon graphC5. By building on Haemers result forC0, we also show that the additivity ofHdoes not hold for the product of the Schläfli graph with its complementary graph.

DNA has emerged as a promising alternative for long-term data storage due to its high capacity, durability, and low-energy potential. However, storing data in DNA presents several challenges. First, it requires complex and costly biochemical processes, making efficient compression crucial to reducing DNA synthesis time and cost. Second, these processes are prone to errors that must be avoided and/or corrected. In particular, homopolymers (repetitions of the same nucleotide) are a well-known source of errors during the sequencing step. Avoiding such repetitions helps mitigate errors but introduces a constraint that may increase the data compression rate. In this paper, we propose two transcoding methods that address these two key challenges: reducing data rate and minimizing errors. The first method strictly enforces the error-minimization constraint by eliminating homopolymers of a certain length, at the cost of an increased data rate. In contrast, the second method accepts a slight increase in homopolymers. However, we show that these increases remain limited (2.14% increase in compression rate for the first method and 0.39% homopolymer rate for the second). These two approaches demonstrate that it is possible to efficiently constrain transcoding while balancing error minimization and compression performance.

Graph coarsening aims to diminish the size of a graph to lighten its memory footprint, and has numerous applications in graph signal processing and machine learning. It is usually defined using a reduction matrix and a lifting matrix, which, respectively, allows to project a graph signal from the original graph to the coarsened one and back. This results in a loss of information measured by the so-called Restricted Spectral Approximation (RSA). Most coarsening frameworks impose a fixed relationship between the reduction and lifting matrices, generally as pseudo-inverses of each other, and seek to define a coarsening that minimizes the RSA. In this paper, we remark that the roles of these two matrices are not entirely symmetric: indeed, putting constraints on the *lifting matrix alone* ensures the existence of important objects such as the coarsened graph's adjacency matrix or Laplacian. In light of this, in this paper, we introduce a more general notion of reduction matrix, that is *not* necessarily the pseudo-inverse of the lifting matrix. We establish a taxonomy of ``admissible'' families of reduction matrices, discuss the different properties that they must satisfy and whether they admit a closed-form description or not. We show that, for a *fixed* coarsening represented by a fixed lifting matrix, the RSA can be *further* reduced simply by modifying the reduction matrix. We explore different examples, including some based on a constrained optimization process of the RSA. Since this criterion has also been linked to the performance of Graph Neural Networks, we also illustrate the impact of this choices on different node classification tasks on coarsened graphs.

The rapid growth in video consumption has introduced significant challenges to modern streaming architectures. Over-the-Top (OTT) video delivery now predominantly relies on Adaptive Bitrate (ABR) streaming, which dynamically adjusts bitrate and resolution based on client-side constraints such as display capabilities and network bandwidth. This pipeline typically involves downsampling the original high-resolution content, encoding and transmitting it, followed by decoding and upsampling on the client side. Traditionally, these processing stages have been optimized in isolation, leading to suboptimal end-to-end rate-distortion (R-D) performance. The advent of deep learning has spurred interest in jointly optimizing the ABR pipeline using learned resampling methods. However, training such systems end-to-end remains challenging due to the non-differentiable nature of standard video codecs, which obstructs gradient-based optimization. Recent works have addressed this issue using differentiable proxy models, based either on deep neural networks or hybrid coding schemes with differentiable components such as soft quantization, to approximate the codec behavior. While differentiable proxy codecs have enabled progress in compression-aware learning, they remain approximations that may not fully capture the behavior of standard, non-differentiable codecs. To our knowledge, there is no prior evidence demonstrating the inefficiencies of using standard codecs during training. In this work, we introduce a novel framework that enables end-to-end training with real, non-differentiable codecs by leveraging data-driven surrogate gradients derived from actual compression errors. It facilitates the alignment between training objectives and deployment performance. Experimental results show a 5.19\% improvement in BD-BR (PSNR) compared to codec-agnostic training approaches, consistently across the entire rate-distortion convex hull spanning multiple downsampling ratios.

Image sensors used in real camera systems are equipped with colour filter arrays which sample the light rays in different spectral bands. Each colour channel can thus be obtained sep-arately by considering the corresponding colour filter. While existing compression solutions mostly assume that the captured raw data has been demosaicked prior to compression, in this paper, we describe an end-to-end trainable neural network for joint compression and demosaicking of satellite images. We first introduce a training loss combining a perceptual loss with the classical mean square error, which is shown to better preserve the high-frequency details present in satellite images. We then present a multi-loss balancing strategy which significantly improves the performance of the proposed joint demosaicking-compression solution.

We propose an empirical study to see whether learning with convolutional neural networks (CNNs) on entropy coded data is possible. First, we define spatial and semantic closeness, two key properties that we experimentally show to be necessary to guarantee the efficiency of the convolution. Then, we show that these properties are not satisfied by the data processed by an entropy coder. Despite this, our experimental results show that learning in such difficult conditions is still possible, and that the performance are far from a random guess. These results have been obtained thanks to the construction of CNN architectures designed for 1D data (one based on VGG, the other on ResNet). Finally, we propose some experiments that explain why CNN are still performing reasonably well on entropy coded data.

Learned image compression neural networks have difficulties adapting to certain satellite image characteristics, especially high frequencies that disappear at a high bit-rate in the blur generated in the reconstruction. To answer this problem we describe a joint end-to-end trainable neural network. It is separated into a general compression network and a smaller specialised network. We train a specialized network to compress the residual part of the image to best preserve the high-frequency details present in the satellite images. The proposed model achieves higher rate-distortion performance than current lossy image compression standards and also manages to retrieve details previously poorly reconstructed.

In the zero-error Slepian-Wolf source coding problem, the optimal rate is given by the complementary graph entropy $\bar H$ of the characteristic graph. It has no single-letter formula, except for perfect graphs, for the pentagon graph with uniform distribution G5, and for their disjoint union. We consider two particular instances, where the characteristic graphs respectively write as an AND product ∧, and as a disjoint union ⊔. We derive a structural result that equates $\bar H( \wedge )$ and $\bar H( \sqcup )$ up to a multiplicative constant, which has two consequences. First, we prove that the cases where $\bar H( \wedge )$ and $\bar H( \sqcup )$ can be linearized coincide. Second, we determine $\bar H$ in cases where it was unknown: products of perfect graphs; and G5∧ G when G is a perfect graph, using Tuncel et al.’s result for $\bar H({G_5} \sqcup G)$. The graphs in these cases are not perfect in general.

We study the zero-error source coding problem in which an encoder with Side Information (SI) g(Y) transmits source symbols X to a decoder. The decoder has SI Y and wants to recover f(X,Y) where f,g are deterministic. We exhibit a condition on the source distribution and g that we call "pairwise shared side information", such that the optimal rate has a single-letter expression. This condition is satisfied if every pair of source symbols "share" at least one SI symbol for all output of g; in the case f(X,Y) = X, the PX,Yand g that satisfy it, induce the worst optimal rate. More generally for all f, it has a practical interpretation, as Y models a request made by the encoder on an image X, and g(Y) corresponds to the type of request. It also has a graph-theoretical interpretation: under "pairwise shared side information" the characteristic graph can be written as a disjoint union of OR products. In the case where the source distribution is full-support, we provide an analytic expression for the optimal rate. We develop an example under "pairwise shared side information", and we show that the optimal coding scheme outperforms several strategies from the literature.

We study unsupervised Retinex decomposition for low light image enhancement. Being an underdetermined problem with infinite solutions, well-suited priors are required to reduce the solution space. In this paper, we analyze the characteristics of low-light images and their illumination component and identify a trivial solution not taken into consideration by the previous unsupervised state-of-the-art methods. The challenge comes from the fact that the trivial solution cannot be completely eliminated from the feasible set as it corresponds to the true solution when the low-light image contains a light source or an overexposed area. To address this issue, we propose a new regularization term which only remove absurd solutions and keep plausible ones in the set. To demonstrate the efficiency of the proposed prior, we conduct our experiments using deep image priors in a framework similar to the recent work RetinexDIP and an in-depth ablation study. Finally, we observe no more halo artefacts in the restored image. For all-but-one metrics, our unsupervised approach gives results as good as the supervised state-of-the-art indicating the potential of this framework for low-light image enhancement.

The promising compression efficiency improvement of Versatile Video Coding (VVC) compared to High Efficiency Video Coding (HEVC) [1] comes at the cost of a non-negligible encoder-side complexity. The largely increased complexity overhead is a possible obstacle towards its industrial implementation. Many papers have proposed acceleration methods for VVC. Still, a better understanding of VVC complexity, especially related to new partitions and coding tools, is desirable to help the design of new and better acceleration methods. For this purpose, statistical analyses have been conducted, with a focus on Coding Unit (CU) sizes and inter coding modes.

We describe an end-to-end trainable neural network for satel-lite image compression. The proposed approach builds upon an image compression scheme based on variational auto-encoders with a learned hyperprior that captures depen-dencies in the latent space for entropy coding. We explore this architecture in light of specificities of satellite imaging: processing constraints onboard the satellite (complexity and memory constraints) and quality needed in terms of reconstruction for the processing task on the ground. We explore data augmentation to improve the reconstruction of challenging image patterns. The proposed model outperforms the current standard of lossy image compression onboard satel-lite based on JPEG 2000, as well as the initial hyper-prior architecture designed for natural images.

State-of-the-art 2D image compression schemes rely on the power of convolutional neural networks (CNNs). Although CNNs offer promising perspectives for 2D image compression, extending such models to omnidirectional images is not straightforward. First, omnidirectional images have specific spatial and statistical properties that can not be fully captured by current CNN models. Second, basic mathematical operations composing a CNN architecture, e.g., translation and sampling, are not well-defined on the sphere. In this paper, we study the learning of representation models for omnidirectional images and propose to use the properties of HEALPix uniform sampling of the sphere to redefine the mathematical tools used in deep learning models for omnidirectional images. In particular, we: i) propose the definition of a new convolution operation on the sphere that keeps the high expressiveness and the low complexity of a classical 2D convolution; ii) adapt standard CNN techniques such as stride, iterative aggregation, and pixel shuffling to the spherical domain; and then iii) apply our new framework to the task of omnidirectional image compression. Our experiments show that our proposed on-the-sphere solution leads to a better compression gain that can save 13.7% of the bit rate compared to similar learned models applied to equirectangular images. Also, compared to learning models based on graph convolutional networks, our solution supports more expressive filters that can preserve high frequencies and provide a better perceptual quality of the compressed images. Such results demonstrate the efficiency of the proposed framework, which opens new research venues for other omnidirectional vision tasks to be effectively implemented on the sphere manifold.

On-the-sphere compression of omnidirectional videos is a very promising approach. First, it saves computational complexity as it avoids to project the sphere onto a 2D map, as classically done. Second, and more importantly, it allows to achieve a better rate-distortion tradeoff, since neither the visual data nor its domain of definition are distorted. In this paper, the on-the-sphere compression [1] for omnidirectional still images is extended to videos. We first propose a complete review of existing spherical motion models. Then we pro-pose a new one called tangent-linear+t. We finally propose a rate-distortion optimized algorithm to locally choose the best motion model for efficient motion estimation/compensation. For that purpose, we additionally propose a finer search pattern, called spherical-uniform, for the motion parameters, which leads to a more accurate block prediction. The novel algorithm leads to rate-distortion gains compared to methods based on a unique motion model.

Many video service providers take advantage of bitrate ladders in adaptive HTTP video streaming to account for different network states and user display specifications by providing bitrate/resolution pairs that best fit client's network conditions and display capabilities. These bitrate ladders, however, differ when using different codecs and thus the couples bitrate/resolution differ as well. In addition, bitrate ladders are based on previously available codecs (H.264/MPEG4-AVC, HEVC, etc.), i.e. codecs that are already in service, hence the introduction of new codecs e.g. Versatile Video Coding (VVC) requires re-analyzing these ladders. For that matter, we will analyze the evolution of the bitrate ladder when using VVC. We show how VVC impacts this ladder when compared to HEVC and H.264/AVC and in particular, that there is no need to switch to lower resolutions at the lower bitrates defined in the Call for Evidence on Transcoding for Network Distributed Video Coding (CfE).

In this paper, we propose a new interactive compression scheme for omnidirectional images. This requires two characteristics: efficient compression of data, to lower the storage cost, and random access ability to extract part of the compressed stream requested by the user (for reducing the transmission rate). For efficient compression, data needs to be predicted by a series of references that have been pre-defined and compressed. This contrasts with the spirit of random accessibility. We propose a solution for this problem based on incremental codes implemented by rate-adaptive channel codes. This scheme encodes the image while adapting to any user request and leads to an efficient coding that is flexible in extracting data depending on the available information at the decoder. Therefore, only the information that is needed to be displayed at the user's side is transmitted during the user's request, as if the request was already known at the encoder. The experimental results demonstrate that our coder obtains a better transmission rate than the state-of-the-art tile-based methods at a small cost in storage. Moreover, the transmission rate grows gradually with the size of the request and avoids a staircase effect, which shows the perfect suitability of our coder for interactive transmission.

The Deep Image Prior has been recently introduced to solve inverse problems in image processing with no need for training data other than the image itself. However, the original training algorithm of the Deep Image Prior constrains the reconstructed image to be on a manifold described by a convolutional neural network. For some problems, this neglects prior knowledge and can render certain regularizers ineffective. This work proposes an alternative approach that relaxes this constraint and fully exploits all prior knowledge. We evaluate our algorithm on the problem of reconstructing a high-resolution image from a downsampled version and observe a significant improvement over the original Deep Image Prior algorithm.

Data acquired over long periods of time like High Definition (HD) videos or records from a sensor over long time intervals, have to be efficiently compressed, to reduce their size. The compression has also to allow efficient access to random parts of the data upon request from the users. Efficient compression is usually achieved with prediction between data points at successive time instants. However, this creates dependencies between the compressed representations, which is contrary to the idea of random access. Prediction methods rely in particular on reference data points, used to predict other data points. The placement of these references balances compression efficiency and random access. Existing solutions to position the references use ad hoc methods. In this paper, we study this joint problem of compression efficiency and random access. We introduce the storage cost as a measure of the compression efficiency and the transmission cost for the random access ability. We express the reference placement problem that trades storage with transmission cost as an integer linear programming problem. Considering additional assumptions on the sources and coding methods reduces the complexity of the search space of the optimization problem. Moreover, we show that the classical periodic placement of the references is optimal, when the encoding costs of each data point are equal and when requests of successive data points are made. In this particular case, a closed-form expression of the optimal period is derived. Finally, the proposed optimal placement strategy is compared with an ad hoc method, where the references correspond to sources where the prediction does not help reducing significantly the encoding cost. The proposed optimal algorithm shows a bit saving of -20% with respect to the ad hoc method.

This paper describes a set of neural network architectures, called Prediction Neural Networks Set (PNNS), based on both fully-connected and convolutional neural networks, for intra image prediction. The choice of neural network for predicting a given image block depends on the block size, hence does not need to be signalled to the decoder. It is shown that, while fully-connected neural networks give good performance for small block sizes, convolutional neural networks provide better predictions in large blocks with complex textures. Thanks to the use of masks of random sizes during training, the neural networks of PNNS well adapt to the available context that may vary, depending on the position of the image block to be predicted. When integrating PNNS into a H.265 codec, PSNRrate performance gains going from 1:46% to 5:20% are obtained. These gains are on average 0:99% larger than those of prior neural network based methods. Unlike the H.265 intra prediction modes, which are each specialized in predicting a specific texture, the proposed PNNS can model a large set of complex textures.

Tone Mapping Operators (TMO) designed for videos can be classified into two categories. In a first approach, TMOs are temporal filtered to reduce temporal artifacts and provide a Standard Dynamic Range (SDR) content with improved temporal consistency. This however does not improve the SDR coding Rate Distortion (RD) performances. A second approach is to design the TMO with the goal of optimizing the SDR coding rate-distortion performances. This second category of methods may lead to SDR videos altering the artistic intent compared with the produced HDR content. In this paper, we combine the benefits of the two approaches by introducing new Weighted Prediction (WP) methods inside the HEVC SDR codec. As a first step, we demonstrate the interest of the WP methods compared to TMO optimized for RD performances. Then we present the newly introduced WP algorithm and WP modes. The WP algorithm consists in performing a global motion compensation between frames using an optical flow, and the new modes are based on non linear functions in contrast with the literature using only linear functions. The contribution of each novelty is studied independently and in a second time they are all put in competition to maximize the RD performances. Tests were made for HDR backward compatible compression but also for SDR compression only. In both cases, the proposed WP methods improve the RD performances while maintaining the SDR temporal coherency.

Immersive visual experience can be obtained by allowing the user to navigate in a 360-degree visual content. These contents are stored in high resolution and need a lot of space on the server to store them. The transmission depends on the user's request and only the spatial region which is requested by the user is transmitted to avoid wasting network bandwidth. Therefore, storage and transmission rates are both critical. Splitting the rates into storage and transmission has not been formally considered in the literature for evaluating 360-degree content compression algorithms. In this paper, we propose a framework to evaluate the coding efficiency of 360-degree content while discriminating between storage and transmission rate and taking into account user dependency. This brings the flexibility to compare different coding methods based on the storage capacity on the server and network bandwidth of users.

Omni-directional images are characterized by their high resolution (usually 8K) and therefore require high compression efficiency. Existing methods project the spherical content onto one or multiple planes and process the mapped content with classical 2D video coding algorithms. However, this projection induces sub-optimality. Indeed, after projection, the statistical properties of the pixels are modified, the connectivity between neighboring pixels on the sphere might be lost, and finally, the sampling is not uniform. Therefore, we propose to process uniformly distributed pixels directly on the sphere to achieve high compression efficiency. In particular, a scanning order and a prediction scheme are proposed to exploit, directly on the sphere, the statistical dependencies between the pixels. A Graph Fourier Transform is also applied to exploit local dependencies while taking into account the 3D geometry. Experimental results demonstrate that the proposed method provides up to 5.6% bitrate reduction and on average around 2% bitrate reduction over state-of-the-art methods.

A 3D mesh object is usually represented as a combination of several entities including geometrical information (i.e., the triangles and their position in space) and a texture atlas/map (i.e. a giant 2D image containing all the texture information that is mapped to the 3D object at the rendering stage). This atlas is usually compressed using a conventional 2D image coder, thus without taking into account the geometrical information. Moreover, the whole image is usually decoded even though only a subpart of the mesh is observed by a user. In this paper, we propose a novel approach to compress a texture atlas of a 3D model that enables random access during decoding, and nevertheless takes into account the correlation driven by the geometrical information. The experimental results demonstrate the benefits of the proposed coder.

In Sequential Massive Random Access (SMRA) [1, 2], a set of correlated sources is jointly encoded and stored on a server, and clients want to access to only a subset of the sources. Since the number of simultaneous clients can be huge, the server is only authorized to extract a bitstream from the stored data: no re-encoding can be performed before the transmission of a request. In this paper, we investigate the SMRA performance of lossy source coding of Gaussian sources with memory. In practical applications such as Free Viewpoint Television, this model permits to take into account not only inter but also intra correlation between sources. For this model, we provide the storage and transmission rates that are achievable for SMRA under some distortion constraint, and we consider two particular examples of Gaussian sources with memory.

This paper explores the problem of learning transforms for image compression via autoencoders. Usually, the rate-distortion performances of image compression are tuned by varying the quantization step size. In the case of autoencoders, this in principle would require learning one transform per rate-distortion point at a given quantization step size. Here, we show that comparable performances can be obtained with a unique learned transform. The different rate-distortion points are then reached by varying the quantization step size at test time. This approach saves a lot of training time.

A well-known result [1, Lemma 3.4] states that, without noise, it is better to overestimate the support of a sparse signal, since, if the estimated support includes the true support, the reconstruction is perfect. In this paper, we investigate whether this result holds also in the presence of noise. First, we derive the covariance matrix of the signal estimate when the observation matrix is Gaussian, generalizing existing results. Then, we show that, even in the noisy case, overestimating the support length is the preferred solution, as the error incurred by missing some signal components dominates the overall error variance. Finally, an upper bound of the estimated support length is provided to avoid excessive noise amplification.

This paper addresses the problem of image compression using sparse representations. We propose a variant of autoencoder called Stochastic Winner-Take-All Auto-Encoder (SWTA AE). “Winner-Take-All” means that image patches compete with one another when computing their sparse representation and “Stochastic” indicates that a stochastic hyperparameter rules this competition during training. Unlike auto-encoders, SWTA AE performs variable rate image compression for images of any size after a single training, which is fundamental for compression. For comparison, we also propose a variant of Orthogonal Matching Pursuit (OMP) called Winner-Take-All Orthogonal Matching Pursuit (WTA OMP). In terms of rate-distortion trade-off, SWTA AE outperforms auto-encoders but it is worse than WTA OMP. Besides, SWTA AE can compete with JPEG in terms of rate-distortion.

Interactive video communication has been recently proposed for multi-view videos. In this scheme, the server has to store the views as compact as possible, while being able to transmit them independently to the users, who are allowed to navigate interactively among the views, hence requesting a subset of them. To achieve this goal, the compression must be done using a model-based coding in which the correlation between the predicted view generated on the user side and the original view has to be modeled by a statistical distribution. In this paper we propose a framework for lossless fixed-length source coding to select a model among a candidate set of models that incurs the lowest extra rate cost to the system. Moreover, in cases where the depth image is available, we provide a method to estimate the correlation model.

This paper addresses the problem of designing a global tone mapping operator for rate distortion optimized backward compatible compression of high dynamic range (HDR) images. We address the problem of tone mapping design for two different use cases leading to two different minimization problems. The first problem considered is the minimization of the distortion on the reconstructed HDR signal under a rate constraint on the standard dynamic range (SDR) layer. The second problem remains the same minimization with an additional constraint to preserve a good quality for the SDR signal. Both the distortion and rate are expressed as a function of the spatial gradient in HDR images. Experiments show that the proposed rate and distortion models based on the HDR image gradient accurately predict the real image rate and distortion measures. Experimental results show that for the first minimization, the optimal rate-distortion performances are achieved, and that the second optimization yields the best tradeoff between rate-distortion performance and quality preservation of the SDR signal.

This paper addresses the problem of designing a global tone mapping operator for rate-distortion optimized backward compatible compression of HDR images. We consider a two layer coding scheme in which a base SDR layer is coded with HEVC, inverse tone mapped and subtracted from the input HDR signal to yield the enhancement HDR layer. The tone mapping curve design is formulated as the minimization of the distortion on the reconstructed HDR signal under the constraint of a total rate cost on both layers, while preserving a good quality for the SDR signal. We first demonstrate that the optimum tone mapping function only depends on the rate of the base SDR layer and that the minimization problem can be separated in two consecutive minimization steps. Experimental results show that the proposed tone mapping optimization yields the best trade-off between rate-distortion performance and quality preservation of the coded SDR.

We consider the problem of video compression with free viewpoint interactivity. It is well believed that allowing the user to choose its view will incur some loss in terms of compression efficiency. Here we derive the complete rate-storage region for universal lossless coding under the constraint of choosing the view at the receiver. This leads to a counterintuitive result: freely choosing its view at the receiver incurs a loss in terms of storage only and not in the transmission rate. The gain of the optimal scheme with respect to interactive schemes proposed so far is derived and a practical scheme that achieves this gain is proposed.

A sparse or compressible signal can be recovered from a certain number of noisy random projections, smaller than what dictated by classic Shannon/Nyquist theory. In this paper, we derive the closed-form expression of the mean square error performance of the oracle receiver, knowing the sparsity pattern of the signal. With respect to existing bounds, our result is exact and does not depend on a particular realization of the sensing matrix. Moreover, our result holds irrespective of whether the noise affecting the measurements is white or correlated. Numerical results show a perfect match between equations and simulations, confirming the validity of the result.

Gossip-based protocols have proven very efficient for disseminating high-bandwidth content such as video streams in a peer-to-peer fashion. However, for the protocols to work, nodes are required to collaborate by devoting a fraction of their upload bandwidth, a scarce resource for some of them, to forward the content they receive to other nodes. Consequently, such protocols suffer from freeriding, a common phenomenon on the Internet, which consists in selfishly benefiting from the system without contributing its fair share. Due to the dynamic nature and the inherent randomness of gossip protocols and to the high scalability requirements of video streaming systems, detecting freeriders is a difficult challenge. This paper presents LiFTinG, the first protocol for detecting freeriders, including colluding ones, in gossip-based content dissemination systems with asymmetric data exchanges. In addition, LiFTinG is still able to detect freeriders when network coding, a widely used technique to improve the efficiency of content dissemination, is used. LiFTinG relies on nodes to track abnormal behavior by cross-checking the history of their previous interactions and exploits the fact that nodes pick neighbors at random to prevent colluding nodes from mutually covering up their bad actions. We present a methodology for setting the parameters of LiFTinG to their optimal value, based on a theoretical analysis and we quantify theoretically the performance of LiFTinG. We derive, based on simulations, the optimal strategy of freeriders by taking into account, through a utility function, the benefit of freeriding and the probability of being detected. In addition to these simulations, we report on the deployment of LiFTinG on PlanetLab. In a 300-node system, where a stream of 674 kbps is broadcasted, LiFTinG incurs a maximum overhead of only 8% and provides good detection results: For instance, with 10% of freeriders decreasing their contribution by up to 30%, LiFTinG detects 86% of the freeriders after only 30 s and wrongfully expels only a few honest nodes (most of them actually being buggy).

We consider correlated and distributed sources without cooperation at the encoder. For these sources, we derive the best achievable performance in the rate-distortion sense of any distributed compressed sensing scheme, under the constraint of high-rate quantization. Moreover, under this model we derive a closed-form expression of the rate gain achieved by taking into account the correlation of the sources at the receiver and a closed-form expression of the average performance of the oracle receiver for independent and joint reconstruction. Finally, we show experimentally that the exploitation of the correlation between the sources performs close to optimal and that the only penalty is due to the missing knowledge of the sparsity support as in (non distributed) compressed sensing. Even if the derivation is performed in the large system regime, where signal and system parameters tend to infinity, numerical results show that the equations match simulations for parameter values of practical interest.

This paper considers the problem of lossless source coding with side information at the decoder, when the correlation model between the source and the side information is uncertain. Four parametrized models representing the correlation between the source and the side information are introduced. The uncertainty on the correlation appears through the lack of knowledge on the value of the parameters. For each model, we propose a practical coding scheme based on non-binary Low Density Parity Check Codes and able to deal with the parameter uncertainty. At the encoder, the choice of the coding rate results from an information theoretical analysis. Then we propose decoding algorithms that jointly estimate the source vector and the parameters. As the proposed decoder is based on the Expectation-Maximization algorithm, which is very sensitive to initialization, we also propose a method to produce first a coarse estimate of the parameters.

This paper presents a novel example-based single-image superresolution procedure that upscales to high-resolution (HR) a given low-resolution (LR) input image without relying on an external dictionary of image examples. The dictionary instead is built from the LR input image itself, by generating a double pyramid of recursively scaled, and subsequently interpolated, images, from which self-examples are extracted. The upscaling procedure is multipass, i.e., the output image is constructed by means of gradual increases, and consists in learning special linear mapping functions on this double pyramid, as many as the number of patches in the current image to upscale. More precisely, for each LR patch, similar self-examples are found, and, because of them, a linear function is learned to directly map it into its HR version. Iterative back projection is also employed to ensure consistency at each pass of the procedure. Extensive experiments and comparisons with other state-of-the-art methods, based both on external and internal dictionaries, show that our algorithm can produce visually pleasant upscalings, with sharp edges and well reconstructed details. Moreover, when considering objective metrics, such as Peak signal-to-noise ratio and Structural similarity, our method turns out to give the best performance.

This paper considers the problem of universal lossless source coding with side information at the decoder only. The correlation channel between the source and the side information is unknown and belongs to a class parametrized by some unknown parameter vector. A complete coding scheme is proposed that works well for any distribution in the class. At the encoder, the proposed scheme encompasses the determination of the coding rate and the design of the encoding process. Both contributions result from the information-theoretical compression bounds of universal lossless source coding with side information. Then a novel decoder is proposed that takes into account the available information regarding the class. The proposed scheme avoids the use of a feedback channel or the transmission of a learning sequence, which both would result in a rate increase at finite length.

This paper presents a new method to construct a dictionary for example-based super-resolution (SR) algorithms. Example-based SR relies on a dictionary of correspondences of low-resolution (LR) and high-resolution (HR) patches. Having a fixed, prebuilt, dictionary, allows to speed up the SR process; however, in order to perform well in most cases, we need to have big dictionaries with a large variety of patches. Moreover, LR and HR patches often are not coherent, i.e. local LR neighborhoods are not preserved in the HR space. Our designed dictionary learning method takes as input a large dictionary and gives as an output a dictionary with a “sustainable” size, yet presenting comparable or even better performance. It firstly consists of a partitioning process, done according to a joint k-means procedure, which enforces the coherence between LR and HR patches by discarding those pairs for which we do not find a common cluster. Secondly, the clustered dictionary is used to extract some salient patches that will form the output set.

This paper considers the problem of lossy source coding with side information at the decoder only, for Gaussian sources, when the joint statistics of the sources are partly unknown. We propose a practical universal coding scheme based on scalar quantization and nonbinary LDPC codes, which avoids the binarization of the quantized coefficients. We first explain how to choose the rate and to construct the LDPC coding matrix. Then, a decoding algorithm that jointly estimates the source sequence and the joint statistics of the sources is proposed. The proposed coding scheme suffers no loss compared to the practical coding scheme with same rate but known variance.

This paper presents a new nonnegative dictionary learning method, to decompose an input data matrix into a dictionary of nonnegative atoms, and a representation matrix with a strict ℓ0-sparsity constraint. This constraint makes each input vector representable by a limited combination of atoms. The proposed method consists of two steps which are alternatively iterated: a sparse coding and a dictionary update stage. As for the dictionary update, an original method is proposed, which we call K-WEB, as it involves the computation of k WEighted Barycenters. The so designed algorithm is shown to outperform other methods in the literature that address the same learning problem, in different applications, and both with synthetic and “real” data, i.e. coming from natural images.

This paper introduces an algorithm to build priors that help image completion to produce better and visually plausible results. The goal of the prior is to seamlessly reconstruct long edges, that exemplar-based inpainting fails to restore. The prior consists in locating the edges across the missing region, and separating the image in regions of relative similar textures. Unlike other techniques, our proposal does not use segmentation or inpainting to obtain the prior, providing a fast technique. Moreover, the technique does not rely on an image dependent threshold. Finally, we propose a scheduling for the synthesis of the missing region based on the prior and Criminisi's algorithm. The scheduling may be thought as a novel macro-filling order for exemplar-based synthesis. The results are comparable with recent and more complex proposals based on super-resolution or Photoshop. Finally, we emphasize that, our prior is not dedicated to our image completion algorithm, and can be used to drive other image completion or inpainting algorithms.

In this paper we present a super-resolution (SR) method for upscaling low-resolution (LR) video sequences, that relies on the presence of periodic high-resolution (HR) key frames, and validate it in the context of video compression. For a given LR intermediate frame, the HR details are retrieved patch-by-patch by taking sparse linear combinations of patches found in the neighbor key frames. The performance of the video SR algorithm is assessed in a scheme where only some key frames from an original HR sequence are directly encoded; the remaining intermediate frames are down-sampled to LR and encoded as well, with a possibly different quantization parameter. SR is then finally employed to upscale these frames. For comparison, we consider the best case where the whole original HR sequence is encoded. With respect to this case, our SR-based approach is shown to bring a certain gain for low bit-rates (consistent when all frames are encoded independently), i.e. when a poor encoding can actually benefit of the special processing of the intermediate frames, so proving that video SR can be an useful tool in realistic scenarios.

International audience

This paper describes a novel method for single-image super-resolution (SR) based on a neighbor embedding technique which uses Semi-Nonnegative Matrix Factorization (SNMF). Each low-resolution (LR) input patch is approximated by a linear combination of nearest neighbors taken from a dictionary. This dictionary stores low-resolution and corresponding high-resolution (HR) patches taken from natural images and is thus used to infer the HR details of the super-resolved image. The entire neighbor embedding procedure is carried out in a feature space. Features which are either the gradient values of the pixels or the mean-subtracted luminance values are extracted from the LR input patches, and from the LR and HR patches stored in the dictionary. The algorithm thus searches for the K nearest neighbors of the feature vector of the LR input patch and then computes the weights for approximating the input feature vector. The use of SNMF for computing the weights of the linear approximation is shown to have a more stable behavior than the use of LLE and lead to significantly higher PSNR values for the super-resolved images.

Unequal Erasure Protection (UEP) is an attractive approach to protect data flows that contain information of different priority levels. The various solutions that have been proposed can be classified into three families. The first one consists of specific, UEP-aware FEC codes, that map the information dependency within the code structure. It enables to design a specific solution, valid for a specific data flow, as in [3]. However, because this is a specific solution, its practical interest is also narrowed. In this work we focus on two additional solution families. One family implements UEP thanks to a dedicated packetization scheme, as it is the case with Priority Encoding Transmission (PET) [2], while the other family uses a dedicated signaling scheme, as is the case with the Generalized Object Encoding (GOE) [6]. These two solutions have the main benefit of being compatible with existing standardized Application Layer FEC (AL-FEC) schemes, which is a major practical benefit. Through a careful modeling of both proposals, we have demonstrated that the protection performance of both approaches are equivalent [7]. However additional key differences become apparent when considering such a practical metric as the peak memory consumption. Thanks to a modeling of the packet storage behavior at the receiver side, and by considering two major parameters, namely the channel loss probability and the permutation type, we show that the GOE scheme (without interleaver) requires a smaller memory storage than PET. This result is reversed if GOE uses a uniform interleaver.

This paper studies source and correlation models for distributed video coding (DVC). It first considers a two-state HMM, i.e., a Gilbert-Elliott process, to model the bit-planes produced by DVC schemes. A statistical analysis shows that this model allows us to accurately capture the memory present in the video bit-planes. The achievable rate bounds are derived for these ergodic sources, first assuming an additive binary symmetric correlation channel between the two sources. These bounds show that a rate gain can be achieved by exploiting the sources memory with the additive BSC model. A Slepian-Wolf decoding algorithm which jointly estimates the sources and the source model parameters is then described. Simulation results show that the additive correlation model does not always fit well with the correlation between the actual video bit-planes. This has led us to consider a second correlation model (the predictive model). The rate bounds are then derived for the predictive correlation model in the case of memory sources, showing that exploiting the source memory does not bring any rate gain and that the noise statistic is a sufficient statistic for the MAP decoder. We also evaluate the rate loss when the correlation model assumed by the decoder is not matched to the true one. An a posteriori estimation of the correlation channel has hence been added to the decoder in order to use the most appropriate correlation model for each bit-plane. The new decoding algorithm has been integrated in a DVC decoder, leading to a rate saving of up to 10.14% for the same PSNR, with respect to the case where the bit-planes are assumed to be memoryless uniform sources correlated with the SI via an additive channel model.

This paper proposes an automatic method for predicting the inter-observer visual congruency (IOVC). The IOVC reflects the congruence or the variability among different subjects looking at the same image. Predicting this congruence is of interest for image processing applications where the visual perception of a picture matters such as website design, advertisement, etc. This paper makes several new contributions. First, a computational model of the IOVC is proposed. This new model is a mixture of low-level visual features extracted from the input picture where model's parameters are learned by using a large eye-tracking database. Once the parameters have been learned, it can be used for any new picture. Second, regarding low-level visual feature extraction, we propose a new scheme to compute the depth of field of a picture. Finally, once the training and the feature extraction have been carried out, a score ranging from 0 (minimal congruency) to 1 (maximal congruency) is computed. A value of 1 indicates that observers would focus on the same locations and suggests that the picture presents strong locations of interest. A second database of eye movements is used to assess the performance of the proposed model. Results show that our IOVC criterion outperforms the Feature Congestion measure \cite{Rosenholtz2007}. To illustrate the interest of the proposed model, we have used it to automatically rank personalized photograph.

This paper addresses the problem of asymmetric distributed coding of correlated binary Hidden Markov Sources, modeled as a Gilbert-Elliott process. The model parameters are estimated with an estimation-decoding Expectation-Maximization algorithm. The rate gain obtained by accounting for the memory of the sources is first assessed theoretically. The method is then shown to improve the PSNR versus rate performance of a Distributed Video Coding system, based on Low-Density Parity-Check codes.

We consider the distributed compression of two (binary memoryless) correlated sources and propose a unique codec that can reach any point in the Slepian-Wolf region. In a previous method based on channel codes, the decoder multiply the compressed data by an inverse submatrix of the code. This multiplication presents two drawbacks. First, if turbo codes are used, the submatrix has no periodic structure s.t. the whole inverse has to be stored and no fast implementation exists for the multiplication. Second, this multiplication may lead to error propagation. In this paper, we propose a method that is both robust and fast.

We consider non-asymmetric distributed source coding (DSC) that achieves any point in the Slepian-Wolf (SW) region. We study the error propagation phenomena and propose a decoding algorithm which limits this phenomena. For the case of turbo-codes, design rules are derived in order for the decoder to recover the sources.

In this paper, we address the problem of optimization of the training sequence interval for MIMO (Multiple- Input Multiple-Output) flat fading channels when an iterative receiver composed of a likelihood generator and a Maximum A Posteriori (MAP) decoder is used. At each iteration of the receiver, the channel is estimated using the hard decisions on the transmitted symbols at the output of the decoder. The optimal length of the training interval is found by maximizing an effective signal-to-noise ratio (SNR) taking into account the data throughput loss due to the use of pilot symbols.

In this paper, we focus on the design of distributed source codes that can achieve any point in the Slepian-Wolf (SW) region and at the same time adapt to any correlation between the sources. A practical solution based on punctured accumulated LDPC codes extended to the non asymmetric case is described. The approach allows flexible rate allocation to the two sources with a gap of 0.0677 bits with respect to the minimum achievable rate.

We consider distributed linear transceivers for sending a second-order wide-sense stationary process observed by two noisy sensors over a Gaussian multiple-access channel (MAC). We derive the minimum mean-square error (MSE) distributed linear transceiver. The optimal linear transmitter exploits bandwidth expansion by repeating transmission and the transmitters at the two sensors are the same except for a constant factor. When the source is white, encoded transmission is the best linear code for any SNR. But for a colored source, whitening transmit filter is sub-optimal. In high SNR regime, the magnitude response of the optimal transmission filter is inversely proportional to fourth-root of the power spectrum of the process (while that for the whitening filler is inversely proportional to the square-root of the spectrum). In the special case of n single sensor with Gaussian source, we also quantify the performance loss of linear source-channel codes with respect to the Shannon limit.

In this paper, we consider the problem of maximum a posteriori (MAP) equalization of the received signal over a frequency selective channel when the channel is not perfectly known at the receiver. The derivation of the MAP criterion in this case leads to an expression for which no exact implementation exists in the literature. In this paper, we propose to solve the problem by using the expectation-maximization (EM) algorithm. The algorithm we propose has linear-time complexity per iteration. Simulations show that few iterations are required to reach the performance of the MAP equalizer with perfect channel knowledge.

We investigate the design of a wireless sensor network (WSN), where distributed source coding (DSC) for pairs of nodes is used. More precisely, we minimize the compression sum rate for noiseless channels and the sum power for noisy orthogonal channels in a context of pairwise DSC. In both cases, the minimization can be separated into a matching problem and a pairwise rate-power control problem (that admits a simple closed-form solution). Using this separation, we obtain an optimization procedure of polynomial (in the number of nodes in the network) complexity. Finally, we show that the overall optimization can be readily interpreted. For noiseless channels, the optimization matches close nodes whereas, for noisy channels, there is a tradeoff between matching close nodes and matching nodes with different distances to the sink. We provide examples of the proposed optimization method based on empirical measures. We show that the matching technique provides substantial gains in either storage capacity or power consumption for the WSN.

This paper proposes a semi-analytical method for predicting the performance degradation of a turbo-equalization scheme due to signal-to-noise ratio (SNR) estimation errors. In other words, sensitivity of turbo-equalization to an imperfect knowledge of the SNR (or, equivalently, channel noise variance) is analyzed. The considered turbo-equalizer uses the Wang and Poor's soft-in/soft-out (SISO) Minimum Mean Square Error (MMSE) / Interference Cancellation (IC) equalizer and a SISO convolutional decoder. The proposed method is applied to BPSK data modulation and single-user context but may be extended to the multi-user case. This paper shows that the equalizer behavior may be very reliably predicted totally by calculations (no simulations are needed) in the presence of imperfectly known SNR at the receiver. As far as the prediction of the decoder behavior is concerned, it requires simulations for only one independent input parameter. Long frames and perfect channel knowledge at the receiver are assumed in the paper.

In this paper, we present a low complexity code design for the 2-user Gaussian multiple access channels. In order to analyze this multiuser MAC decoder, we formulate density evolution (DE) and study the stability condition of the fixed point corresponding to zero BER.

We investigate the spectral efficiency achievable by random synchronous code-division multiple access (CDMA) with quaternary phase-shift keying (QPSK) modulation and binary error-control codes, in the large system limit where the number of users, the spreading factor, and the code block length go to infinity. For given codes, we maximize spectral efficiency assuming a minimum mean-square error (MMSE) successive stripping decoder for the cases of equal rate and equal power users. In both cases, the maximization of spectral efficiency can be formulated as a linear program and admits a simple closed-form solution that can be readily interpreted in terms of power and rate control. We provide examples of the proposed optimization methods based on off-the-shelf low-density parity-check (LDPC) codes and we investigate by simulation the performance of practical systems with finite code block length.

We optimize the random-like ensemble of irregular repeat-accumulate (IRA) codes for binary-input symmetric channels in the large block-length limit. Our optimization technique is based on approximating the evolution of the densities (DE) of the messages exchanged by the belief-propagation (BP) message-passing decoder by a one-dimensional dynamical system. In this way, the code ensemble optimization can be solved by linear programming. We propose four such DE approximation methods, and compare the performance of the obtained code ensembles over the binary-symmetric channel (BSC) and the binary-antipodal input additive white Gaussian noise channel (BIAWGNC). Our results clearly identify the best among the proposed methods and show that the IRA codes obtained by these methods are competitive with respect to the best known irregular low-density parity-check (LDPC) codes. In view of this and the very simple encoding structure of IRA codes, they emerge as attractive design choices.

We investigate a sub-optimal iterative receiver for joint equalization and decoding called a turbo-equalizer. We view the evolution of the error variance of the transmitted symbols through iterative processing, obtaining the convergence analysis. This allows us to predict the asymptotic performance (when the turbo-equalizer has converged) but also the trigger point observed in its performance.

Sub-optimal joint equalization and decoding is performed by iterated equalization and decoding. This processing is named turbo-equalization with reference to the turbo-decoding of serially concatenated codes. We propose to optimize the equalizer structure (an interference canceler) thanks to the training sequence available to estimate the channel impulse response. The interference canceler, optimized at each iteration, permits one to reduce the number of iterations needed to achieve a given performance. The gain is all the more important that the channel is hard to equalize.

A low-complexity and iterative receiver is proposed for the CDMA uplink, consisting of a low-complexity equalizer and single-user decoders. Iterations are used to feed the equalizer with more reliable data, which improves performance. This receiver called turbo-CDMA is aimed to eliminate MUI almost completely in the presence of multipath and to be robust to the near-far effect. Simulation results show that the performance approaches single-user performance at moderate and also low signal-to-noise ratios, even for a severe distortion channel.