We envision Artificial Intelligence marketplaces to be platforms where consumers, with very less data for a target task, can obtain a relevant model by accessing many private data sources with vast number of data samples. One of the key challenges is to construct a training dataset that matches a target task without compromising on privacy of the data sources. To this end, we consider the following distributed data summarizataion problem. Given K private source datasets denoted by $[D_i]_{i\in [K]}$ and a small target validation set $D_v$, which may involve a considerable covariate shift with respect to the sources, compute a summary dataset $D_s\subseteq \bigcup_{i\in [K]} D_i$ such that its statistical distance from the validation dataset $D_v$ is minimized. We use the popular Maximum Mean Discrepancy as the measure of statistical distance. The non-private problem has received considerable attention in prior art, for example in prototype selection (Kim et al., NIPS 2016). Our work is the first to obtain strong differential privacy guarantees while ensuring the quality guarantees of the non-private version. We study this problem in a Parsimonious Curator Privacy Model, where a trusted curator coordinates the summarization process while minimizing the amount of private information accessed. Our central result is a novel protocol that (a) ensures the curator does not access more than $O(K^{\frac{1}{3}}|D_s| + |D_v|)$ points (b) has formal privacy guarantees on the leakage of information between the data owners and (c) closely matches the best known non-private greedy algorithm. Our protocol uses two hash functions, one inspired by the Rahimi-Recht random features method and the second leverages state of the art differential privacy mechanisms. We introduce a novel ``noiseless'' differentially private auctioning protocol, which may be of independent interest. Apart from theoretical guarantees, we demonstrate the efficacy of our protocol using real-world datasets.

Recent business studies have shown that social technologies can significantly improve productivity within enterprises by improving access to information, ideas, and collaborators. A manifestation of the growing adoption of enterprise social technologies is the increasing use of enterprise virtual discussions to engage customers and employees. In this paper we present an enterprise discussion analysis system which seeks to enable rapid interactive inference of insights from virtual online enterprise discussions. Rapid understanding is facilitated by extracting a hierarchy of key concepts, which represent a multi-faceted thematic categorization of discussion content, and by identifying high-quality thematic exemplar comments. The concept hierarchy and exemplar comments are presented through an intuitive web user-interface which allows an analyst to quickly navigate through the main concepts and the most relevant comments extracted from the discussion. We present a preliminary validation of system efficacy through user surveys provided to test users.

Phase Change Memory (PCM) is a promising technology for building future main memory systems. A prominent characteristic of PCM is that it has write latency much higher than read latency. Servicing such slow writes causes significant contention for read requests. For our baseline PCM system, the slow writes increase the effective read latency by almost 2X, causing significant performance degradation. This paper alleviates the problem of slow writes by exploiting the fundamental property of PCM devices that writes are slow only in one direction (SET operation) and are almost as fast as reads in the other direction (RESET operation). Therefore, a write operation to a line in which all memory cells have been SET prior to the write, will incur much lower latency. We propose PreSET, an architectural technique that leverages this property to pro-actively SET all the bits in a given memory line well in advance of the anticipated write to that memory line. Our proposed design initiates a PreSET request for a memory line as soon as that line becomes dirty in the cache, thereby allowing a large window of time for the PreSET operation to complete. Our evaluations show that PreSET is more effective and incurs lower storage overhead than previously proposed write cancellation techniques. We also describe static and dynamic throttling schemes to limit the rate of PreSET operations. Our proposal reduces effective read latency from 982 cycles to 594 cycles and increases system performance by 34%, while improving the energy-delay-product by 25%.

This paper investigates compression of data encrypted with block ciphers, such as the Advanced Encryption Standard. It is shown that such data can be feasibly compressed without knowledge of the secret key. Block ciphers operating in various chaining modes are considered and it is shown how compression can be achieved without compromising security of the encryption scheme. Further, it is shown that there exists a fundamental limitation to the practical compressibility of block ciphers when no chaining is used between blocks. Some performance results for practical code constructions used to compress binary sources are presented.

We introduce a simple communication-theoretic model for phase-change memory (PCM), based on empirical observations. Our modeling effort is focused on capturing the effects of resistance drift, which is believed to be one of the major obstacles to achieving high bit/cell densities in PCM. The model is used to estimate how the information theoretic storage capacity of PCM evolves as the time gap between a write and its subsequent read widens. We use our model to evaluate the performance of simple modulation and detection schemes, also considering the use of trellis coded modulation (TCM). Our evaluation of these strategies shows that the use of TCM provides several benefits, including a significant increase in retention time, i.e., the expected maximum amount of storage time before which the stored data can be reliably retrieved.

We consider the problem of information storage in multilevel heterogeneous memories, where different cells can support different data level-sets. Such heterogeneity arises due to variability in the physical cell characteristics in emerging technologies such as Phase Change Memory (PCM) technology, which is our specific motivation. We show that the heterogeneous memory problem can be formulated in terms of the information-theoretic `Channel Coding with Side-Information at Transmitter' (CSIT) paradigm. We present a binary decomposition of the problem, and show that this decomposition allows for simple binary code constructions. We discuss one such code-construction based on binary Luby Transform (LT) code matrices. We present simulation results using cell variability data collected from a PCM test array, and show that the proposed approach can yield a significant advantage in storage capacity.

We present a class of algorithms for encoding data in memories with stuck cells. These algorithms rely on earlier code constructions termed cyclic Partitioned Linear Block Codes. For the corresponding q-ary BCH-like codes for u stucks in a codeword of length n, our encoding algorithm has complexity O((u logqn)2) Fqoperations, which we will show compares favorably to a generic approach based on Gaussian elimination. The computational complexity improvements are realized by taking advantage of the algebraic structure of cyclic codes for stucks. The algorithms are also applicable to cyclic codes for both stucks and errors.

The block erase requirement in NAND Flash devices leads to the need for garbage collection. Garbage collection results in write amplification, that is, to an increase in the number of physical page programming operations. Write amplification adversely impacts the limited lifetime of a NAND Flash device, and can add significant system overhead unless a large spare factor is maintained. This paper proposes a NAND Flash system which uses multi-write coding to reduce write amplification. Multi-write coding allows a NAND Flash page to be written more than once without requiring an intervening block erase. We present a novel two-write coding technique based on enumerative coding, which achieves linear coding rates with low computational complexity. The proposed technique also seeks to minimize memory wear by reducing the number of programmed cells per page write. We describe a system which uses lossless data compression in conjunction with multi-write coding, and show through simulations that the proposed system has significantly reduced write amplification and memory wear.

This paper investigates compression of encrypted data. It has been previously shown that data encrypted with Vernam's scheme, also known as the one-time pad, can be compressed without knowledge of the secret key, therefore this result can be applied to stream ciphers used in practice. However, it was not known how to compress data encrypted with non-stream ciphers. In this paper, we address the problem of compressing data encrypted with block ciphers, such as the advanced encryption standard (AES) used in conjunction with one of the commonly employed chaining modes. We show that such data can be feasibly compressed without knowledge of the key. We present performance results for practical code constructions used to compress binary sources.

In this paper we present a novel algorithm to speed up the inter mode decision process for the H.264/AVC encoding. The proposed inter mode decision scheme determines the best coding mode between P16×16 and P8×8 based on learning theoretic classification algorithms to discern between mode classes based on the evaluation of a simple set of features extracted from a motion compensated macroblock. We show that the proposed method can reduce the number of macroblocks for P8×8 mode testing by 80% on average, at the cost of only a small loss of 0.1 dB in compression performance.

We consider Slepian-Wolf code design based on low density parity-check (LDPC) coset codes. The density evolution formula for Slepian-Wolf coding is derived. An intimate connection between Slepian-Wolf coding and channel coding is then established. Specifically we show that, under density evolution, each Slepian-Wolf coding problem is equivalent to a channel coding problem for a binary-input output-symmetric channel.

This letter tackles the problem of reducing the complexity of H.264 decoding. Since deblocking accounts for a significant percentage of H.264 decoding time, our focus is on the H.264 in-loop deblocking filter. Observing that branch operations are costly and that in the deblocking process there are events with significantly high probability of occurrence, we regroup and simplify the branch operations. We apply the idea of Huffman tree optimization to speed up the boundary strength derivation and the true-edge detection by taking advantage of the biased statistical distribution. Our analyses and experiments show that the proposed techniques can reduce the deblocking computation time typically by a factor of more than seven times, while maintaining the bit-exact output.

In this paper, Slepian-Wolf coding with a mismatched decoding metric is studied. Two different dualities between Slepian-Wolf coding and channel coding under mismatched decoding are established. These two dualities provide a systematic framework for comparing linear Slepian-Wolf codes, nonlinear Slepian-Wolf codes, and variable-rate Slepian-Wolf codes. In contrast with the fact that linear codes suffice to achieve the Slepian-Wolf limit under matched decoding, the minimum rate achievable with nonlinear Slepian-Wolf codes under mismatched decoding can be strictly lower than that achievable with linear Slepian-Wolf codes.

In this paper, it is shown that each Slepian-Wolf coding problem is related to a dual channel coding problem in the sense that the sphere packing exponents, random coding exponents, and correct decoding exponents in these two problems are mirror-symmetrical to each other. This mirror symmetry is interpreted as a manifestation of the linear codebook-level duality between Slepian-Wolf coding and channel coding. Furthermore, this duality, in conjunction with a systematic analysis of the expurgated exponents, reveals that nonlinear Slepian-Wolf codes can strictly outperform linear Slepian-Wolf codes in terms of rate-error tradeoff at high rates. The linear codebook-level duality is also established for general sources and channels.

In this paper, the redundancy of both variable and fixed rate Slepian–Wolf coding is considered. Given any jointly memoryless source-side information pair$\{(X_i, Y_i)\}_{i=1}^{\infty}$with finite alphabet, the redundancy$R^n(\epsilon_n)$of variable rate Slepian–Wolf coding of$X_1^n$with decoder only side information$Y_1^n$depends on both the block length$n$and the decoding block error probability$\epsilon_n$, and is defined as the difference between the minimum average compression rate of order$n$variable rate Slepian–Wolf codes having the decoding block error probability less than or equal to$\epsilon_n$, and the conditional entropy$H(X\vert Y)$, where$H(X\vert Y)$is the conditional entropy rate of the source given the side information. The redundancy of fixed rate Slepian–Wolf coding of$X_1^n$with decoder only side information$Y_1^n$is defined similarly and denoted by$R^n_F(\epsilon_n)$. It is proved that under mild assumptions about$\epsilon_n,$$R^n(\epsilon_n) = d_v \sqrt{-\log\epsilon_n/n} + o(\sqrt{-\log \epsilon_n/n})$and$R^n_{F}(\epsilon_n) = d_f \sqrt{- \log \epsilon_n / n} + o(\sqrt{-\log \epsilon_n/n})$, where$d_f$and$d_v$are two constants completely determined by the joint distribution of the source-side information pair. Since$d_v$is generally smaller than$d_f$, our results show that variable rate Slepian–Wolf coding is indeed more efficient than fixed rate Slepian–Wolf coding.

Hybrid Wyner-Ziv coders which employ a combination of Wyner-Ziv coding and differential pulse code modulation (DPCM) encoding have recently gained popularity for applications such as video coding. In this paper we analyze the low-rate operational rate distortion performance of Wyner-Ziv coding using uniform scalar quantization, in the context of such hybrid coders. Motivated by video we consider the compression of a first-order Laplace-Markov source, and derive approximate analytical rate and distortion expressions which are accurate at low rates. We utilize the derived analytical expressions to address the problem of determining the optimal quantization interval ratio of the Wyner-Ziv and DPCM scalar quantizers, for a range of rates.

Lower and upper bounds on the reliability region of universal variable-rate Slepian-Wolf coding are derived.

The problem of secure collaboration between two agents, A and B, with limited mutual trust is considered. Specifically, we consider a formulation wherein agent A would like to share information with agent B but only if B has correlated information. Our solution is based on the principles of source coding with decoder-only side information. The key idea is that agent A can encode its information by using a Slepian-Wolf code at a rate which enables agent B to correctly decode only if the information which B has satisfies a conditional entropy constraint. Furthermore, our solution allows the two agents to interact and negotiate the rate on the fly. It is shown that such interaction not only reduces the transmission rate, but also allows secure collaboration to be established even when neither agent knows the joint statistics of their information. Finally, we demonstrate the utility of our solution in a simple medical imaging application.

Aiming at improving compression performance, we consider mode selection for Wyner-Ziv video compression where a block of pixels in a video frame, after discrete cosine transform(DCT), can be either encoded by using H.264 Intra mode or Wyner-Ziv(WZ) mode with side information processed at the decoder. Under the constraint of encoding complexity, an iterative algorithm is proposed to find the best partition of a video frame into these two modes in the sense of minimizing the overall compression rate. It is shown that the algorithm always converges. Experimental results on standard video test sequences show that by using the proposed algorithm for mode selection, one can achieve about 0.4dB gain for WZ-encoded frames over a WZ video compression system without intra mode at rate 0.2 bits per pixel. Furthermore, in all the experiments our algorithm converges in 3 iterations.

Slepian-Wolf coding with a mismatched decoding metric is studied. Two different dualities between Slepian-Wolf coding and channel coding under mismatched decoding are established. These two dualities provide a systematic framework for comparing linear Slepian-Wolf codes, nonlinear Slepian-Wolf codes, and variable-rate Slepian-Wolf codes. In contrast with the fact that linear codes suffice to achieve the Slepian-Wolf limit under matched decoding, the minimum rate achievable with linear Slepian-Wolf codes under mismatched decoding can be strictly higher than that achievable with nonlinear Slepian-Wolf codes.

Wyner-Ziv (WZ) coding has recently been proposed as a low encoding complexity alternative to traditional DPCM coding for compression of sources with memory, in particular, in applications like multimedia compression. The viability of this alternative approach clearly depends on the compression performance of WZ coding compared to that of DPCM coding. In an attempt to understand the performance gap between WZ coding and DPCM coding, this paper studies the operational rate-distortion performance of WZ coding, using uniform scalar quantization followed by perfect Slepian-Wolf coding, for compression of a Laplace-Markov (LM) source. It is shown that at low rates or for weakly correlated LM sources, WZ coding is indeed a competitive alternative to DPCM coding. However, at high rates the performance gap becomes non-negligible for strongly correlated LM sources. In order to reduce the gap at high rates, a hybrid approach that combines DPCM coding and WZ coding is further investigated. It is shown that the hybrid approach is indeed competitive to DPCM coding at all rates even for strongly correlated LM sources.

Wyner-Ziv coding has recently emerged as an alternative to conventional DPCM coding for compression of sources with memory, particularly in video compression. This paper studies the operational rate-distortion performance of Wyner-Ziv coding, using uniform scalar quantization followed by perfect Slepian-Wolf coding, for compression of a Laplace-Markov source. The performance gap of this technique relative to DPCM coding is characterized through derived rate-distortion expressions and numerical simulations.

Side information (SI) generation is one of the key components of a Wyner-Ziv coder. In this paper we present a novel multi-frame SI generation approach which uses adaptive temporal filtering to estimate the pixel values for SI and motion vector filtering for refinement. For temporal filtering, we derive the optimal mean squared error temporal filter when the noise can be evaluated, and propose a similarity weighted temporal filter when the knowledge of the noise is not available. The temporal filter adapts on the quality of the motion estimation. The quality of SI generation is further improved by using motion vector filtering to reduce the noise effect from motion estimation. Experimental results indicate that the proposed SI generation approach yields good performance in terms of SI quality and conditional entropy.

In-loop deblocking filter is identified as the most time consuming part for H.264 high profile decoders. This paper proposes an improved platform and encoder independent deblocking scheme for H.264 high profile codec speedup. Two key techniques are introduced in the proposed algorithm: a statistical analysis based hybrid boundary strength derivation scheme and a more efficient logic expression for the B-slice boundary strength derivation. Compared to previously proposed algorithms, significant computation can be saved, while maintaining the bit-exact output. The proposed techniques can be used in both standard conforming encoders and decoders.

This paper proposes a novel scheme to achieve deblocking speedup for H.264 high profile decoders. The proposed approach is to use statistics dependent decoding which takes advantage of the biased statistical distribution in video streams. Specifically, in the proposed scheme, Huffman tree structures are introduced for boundary strength derivation, and hierarchical true edge detection is applied in the boundary filtering process to reduce the computation. As a result, significant computation can be saved in the deblocking process, while bit-exact output is maintained. This platform and encoder independent scheme can be incorporated into both standard conforming encoders and decoders. Since deblocking accounts for a significant percentage of decoding time, the scheme is especially important for decoder implementations. The analyses and experiments show that the proposed scheme could reduce the deblocking computational load by a factor of more than three times.

We characterize the redundancy-error tradeoff in Slepian-Wolf coding. Similar results are derived for a class of cyclic-symmetric channels. Through the linear codebook-level duality between Slepian-Wolf coding and channel coding, we show that, in Slepian-Wolf coding, linear codes are optimal in terms of redundancy-error tradeoff at rate close to the Slepian-Wolf limit but suboptimal at high rate.

Let (X, Y) denote a pair of finite-valued random variables. In this paper we use two examples to show an inherent partial ordering relation among the set {Py\x: H(X\Y) = a} where {Py\x : H(X\Y) = a} denotes the channel from X to Y, and 0 lesplusmn les H(X) is a constant. Specifically, we consider the following cases: the channel from X to Y is either a binary symmetric channel (BSC) or a binary erasure channel (BEC). In each case, we characterize the redundancy of Slepian-Wolf coding of X with decoder only side information Y. It is thus revealed that for any binary X and 0 < a < H(X), under the condition that H(X\Y) = a the redundancy of the BSC case is strictly larger than that of the BEC case for a range of decoding error probabilities. Interestingly, our results also reveal that the redundancy of variable-rate Slepian-Wolf coding is generally better than that of fixed-rate Slepian-Wolf coding.

A rateless Slepian-Wolf coding (SWC) scheme based on rate adaptive low-density-parity-check (LDPC) codes is presented. We first motivate the application of punctured LDPC codes in SWC. A general rate adaptive LDPC framework is then described. The main idea is to adjust the puncturing ratio in the specified variable nodes for rate adaptivity while keeping the bipartite graph structure intact. As a complement, a repetition scheme is proposed for high rate SWC. The asymptotic performance of the proposed scheme is analyzed by density evolution (DE) with universal coding bounds and finite code length performance is verified by computer simulations.

The performance of a uniform-threshold scalar quantizer in Wyner-Ziv coding is investigated in this paper. To derive analytical expressions we assume the abstract correlation channel from the side information to the source to be encoded is memoryless, additive Laplacian. Furthermore, in order to focus our attention on the performance of the quantizer, the Wyner-Ziv coding scheme is assumed to encode the quantizer output by using perfect Slepian-Wolf coding. Analytical expressions for the operational rate-distortion function are obtained for this case. By evaluating these analytical expressions, we show that scalar quantization with a mid-tread uniform threshold quantizer, followed by perfect Slepian Wolf coding achieves performance which is close to the theoretical Wyner-Ziv rate-distortion bound at low rates

The low-rate (<;1 bits per sample) operational rate-distortion performance of uniform scalar quantizers for the memoryless Gaussian source is studied. Approximate analytical expressions for the operational rate-distortion function are derived, and the accuracy of the derived function is verified through simulation. It is shown that in the zero-rate limit the derived operational rate-distortion function is first-order optimal with respect to the Shannon lower bound. The derived function is used to study the performance of uniform scalar quantizers for the Gaussian Wyner-Ziv problem. Lastly, the derived low-rate rate-distortion function is used to provide improved low-rate bit allocation for jointly Gaussian vectors.

With increased concern for physical security, video surveillance is becoming an important business area. Similar camera-based system can also be used in such diverse applications as retail-store shopper motion analysis and casino behavioral policy monitoring. There are two aspects of video surveillance that require significant computing power: image analysis for detecting objects, and video compression for digital storage. The new STI CELL broadband engine (CBE) processor is an appealing platform for such applications because it incorporates 8 separate high-speed processing cores with an aggregate performance of 256Gflops. Moreover, this chip is the heart of the new Sony Playstation 3 and can be expected to be relatively inexpensive due to the high volume of production. In this paper we show how object detection and compression can be implemented on the CBE, discuss the difficulties encountered in porting the code, and provide performance results demonstrating significant speed-up

We consider Slepian-Wolf code design based on LDPC (low-density parity-check) coset codes for memoryless source-side information pairs. A density evolution formula, equipped with a concentration theorem, is derived for Slepian-Wolf coding based on LDPC coset codes. As a consequence, an intimate connection between Slepian-Wolf coding and channel coding is established. Specifically we show that, under density evolution, design of binary LDPC coset codes for Slepian-Wolf coding of an arbitrary memoryless source-side information pair reduces to design of binary LDPC codes for binary-input output-symmetric channels without loss of optimality. With this connection, many classic results in channel coding can be easily translated into the Slepian-Wolf setting

This paper presents a multiple description (MD) video codec based on the principles side-information coding. In particular, we highlight certain key components of the codec design that contribute significantly to the rate-distortion performance of the proposed codec. These include the use of randomized permutations of the quantization codebook in conjunction with binary LDPC codes for partitioning the available bit-rate among the coefficient bit-planes. Another key component of the proposed codec is the use of pdf estimation for improved decoder reconstruction. Lastly, we use a bank of sequential LDPC decoders to efficiently decode the transmitted coset information. Empirical evaluation demonstrates the superior performance of the proposed codec for the communication of encoded video over packet erasure channels.

This paper presents a distortion optimized streaming algorithm for on-demand streaming of multimedia. Given the pre-encoded packets of a multimedia stream, we propose a fast algorithm for selecting an appropriate subset of these packets such that the overall client distortion is minimized. This minimization is performed within the rate constraints imposed by the communication channel. In particular, at each transmission opportunity, the proposed approach uses a linear-time algorithm to select the best packet to transmit through the minimization of the expected client distortion. The time complexity of the algorithm is reduced through a factorization of the streaming policy into simpler terms and performing a greedy optimization to select the packet. Inevitably, this in itself leads to sub-optimal results. To alleviate the adverse impact of the greedy optimization, the cost function is penalized with the expected buffer occupancy at the end of the epoch of the optimization. We pose this problem as a Lagrangian minimization. We demonstrate the efficacy of the proposed approach through empirical evaluation.

The H.264 video coding standard derives much of its compression efficiency gain from the use of multiple different macroblock prediction modes for macroblock coding. In general, finding the prediction mode which gives optimal R-D performance for a given macroblock requires the encoder to completely encode the macroblock using all possible prediction modes. This results in a significant increase in encoder computational complexity. In this paper, we present a mode selection framework for H.264 which uses learning theoretic classification algorithms to discern between broad mode classes, based on the evaluation of a simple set of macroblock features. We show that the proposed mode selection framework significantly reduces encoder computational complexity, at the cost of only a small loss in compression performance.

This paper addresses the problem of video coding in a joint source-channel setting. In particular, we propose a video encoding algorithm that prevents the indefinite propagation of errors in predictively encoded video-a problem that has received considerable attention over the last decade. This is accomplished by periodically transmitting a small amount of additional information, termed coset information, to the decoder, as opposed to the popular approach of periodic insertion of intra-coded frames. Perhaps surprisingly, the coset information is capable of correcting for errors, without the encoder having a precise knowledge of the lost packets that resulted in the errors. In the context of real-time transmission, the proposed approach entails a minimal loss in performance over conventional encoding in the absence of channel losses, while simultaneously allowing error recovery in the event of channel losses. We demonstrate the efficacy of the proposed approach through experimental evaluation. In particular, the performance of the proposed framework is 3-4 dB superior to the conventional approach of periodic insertion of intra-coded frames, and 1.5-2 dB away from an ideal system, with infinite decoding delay, operating at Shannon capacity.

The predictive multiple description coding problem can be posed as a variant of the well-known Wyner-Ziv side-information problem. Predictive MD coding in this framework (termed the WYZE-PMD) eliminates the problem of predictive mismatch without requiring restrictive channel assumptions or high latency. The performance of two-channel one-step predictive MD coding was analyzed within the WYZE-PMD framework. Achievable rate-distortion (R-D) regions were obtained for the problem of MD coding in the presence of correlated decoder side-information. These were used to obtain the operational R-D performance for predictive MD coding under certain restrictions. Practical code constructions were proposed within the WYZE-PMD framework. Performance comparisons between the proposed codes and conventional approaches were presented for communication of a first-order Gauss-Markov source over two erasure channels with independent failure probabilities. Results indicated that the proposed approach significantly out-performs conventional approaches in terms of R-D performance.

A commonly encountered problem in the communication of predictively encoded video is that of predictive mismatch or drift. The problem of predictive mismatch manifests itself in numerous communication scenarios, including on-demand streaming, real-time streaming and multicast streaming. This paper proposes a state-free video encoding architecture that alleviates this problem. The main benefit of state-free encoding is that there is no need for the encoder and the decoder to maintain the same state, or equivalently, predict using the same predictor. This facilitates robust communication of causally encoded media. The proposed approach is based on the Wyner-Ziv theorem in information theory. Consequently, it leverages the superior performance of coset codes for the Wyner-Ziv problem for predictive coding. A video codec, with state-free functionality, based on the H.26L encoding standard is proposed. The performance of the proposed codec is within 1-2.5 dB of the H.26L encoder.

The main hindrance to the development of efficient low-latency multiple description (MD) video coders are the problem of predictive mismatch. In this paper, we present a two-channel predictive MD video codec architecture based on the recently proposed WYZE-PMD framework. The proposed codec transmits coset information to curtail error-propagation caused by predictive mismatch, without requiring high latency or restrictive channel assumptions. MD scalar quantizers are used to generate multiple descriptions, low-density parity check (LDPC) codes are used to generate coset information, and the H.263 video coding standard is used for efficient motion compensation. The proposed codec is used to code descriptions of CIF video for communication over two erasure channels with independent failure probabilities. Results indicate that the proposed codec provides efficient, drift-free predictive MD coding.

One-pass, variable bit-rate (VBR) rate control is ideally suited to the requirements of real-time video encoding for the purpose of digital storage. Previous MPEG one-pass VBR rate control algorithms have been based on appropriate selection of quantization scale parameters for controlling the bit rate and quality of the output bitstream. The major disadvantage of relying solely on quantization scales, for rate control, is the introduction of significant perceptual distortion when high quantization scales are used. We propose an MPEG-4, 1-pass, VBR rate control scheme that relies on the selective use of the MPEG-4 reduced resolution mode to supplement modulation of the quantization scale and provide an effective rate control strategy. Experimental results show that the proposed algorithm can encode high-complexity, standard definition (720 /spl times/ 480) video sequences at rates as low as 750 kbps without incurring significant perceptual artifacts.

We are concerned with multiple description coding of predictively encoded sequences at low rates/redundancies. The key problem to be solved is that of avoiding predictive mismatch. We propose an algorithm based on multiple description correlating transforms (MDCT), which avoids the problem of predictive mismatch while not increasing the number of transmitted coefficients. Under a general first-order, Gauss-Markov source model, carefully formulated to be applicable to the practically important case of video coding, we obtain closed-form expressions for the operational rate-distortion characteristics of the proposed algorithm and use these to optimize the algorithm encoding parameters. In the case of the residual-of-residuals technique, which is also based on MDCT, we show that incorporation of any redundancy between the transmitted descriptions is inherently suboptimal. Results show that the proposed algorithm significantly outperforms the residual-of-residuals technique at low rates.

The inherently causal nature of conventional single-pass error diffusion (ED) halftoning results in asymmetric diffusion of error. This results in the introduction of directional artifacts in the output halftone. In this paper we propose a novel two-pass algorithm which achieves symmetric error diffusion by using a zero-phase signal transfer function. We determine conditions under which isotropic diffusion of error and noise suppression are achieved. Experimental results demonstrate that the proposed algorithm breaks up worms and randomizes their direction, thus making the output halftone more visually appealing as compared to conventional error diffusion.

One-pass variable bit rate (VBR) rate control is ideally suited to the requirements of real-time video encoding for the purpose of digital storage. Previous MPEG 1-pass VBR rate control algorithms have been based on appropriate selection of quantization scale parameters for controlling the bit rate and quality of the output bitstream. The major disadvantage of relying solely on quantization scales for rate-control is the introduction of significant perceptual distortion when high quantization scales are used. In this paper we propose an MPEG-4, 1-pass, VBR rate-control scheme that relies on selective use of the MPEG-4 reduced resolution mode to supplement modulation of the quantization scale and provide an effective rate control strategy. Experimental results show that the proposed algorithm effectively can encode high-complexity, standard definition (720/spl times/480) video sequences at rates as low as 750 kbps without incurring significant perceptual artifacts.

Predictive encoding with respect to multiple possible predictors is a common scenario encountered in many digital set-top box applications, such as redundant storage of video/audio data, real-time robust communication with peripherals and Internet video/audio telephony. A key problem associated with this scenario is that of predictive mismatch or drift. In the present paper, we pose the problem of predictive encoding with multiple possible predictors as a variant of the well-known Wyner-Ziv side-information problem. We propose an approach based on the use of coset codes for predictive encoding, for mitigating the effect of drift without overly sacrificing compression efficiency. The proposed approach can be used to improve coding performance in a wide range of practical applications such as multiple description coding, scalable coding and redundant storage of video/audio streams. We illustrate the efficacy of the proposed approach through a simple example based on the application of low-delay Internet telephony. Our results indicate that the proposed approach significantly outperforms conventional predictive encoding for communication over lossy channels.

A novel solution to the problem of data embedding in images is proposed in this paper The proposed algorithm allows high capacity data embedding and is robust to JPEG image compression data is embedded in the wavelet domain which provides better perceptual masking compared to the DCT domain set partitioning in hierarchical trees (SPIHT) is used to control the distortion (in the sense of PSNR) in the embedded host. Unlike other data embedding algorithms available in literature, the proposed algorithm provides control over the BER of the embedded data by appropriately choosing the JPEG quantization matrix. Preliminary results of an implementation of the algorithm are also presented.