Video sharing (e.g., YouTube, Vimeo, Facebook, TikTok) accounts for the majority of internet traffic, and video processing is also foundational to several other key workloads (video conferencing, virtual/augmented reality, cloud gaming, video in Internet-of-Things devices, etc.). The importance of these workloads motivates larger video processing infrastructures and – with the slowing of Moore’s law – specialized hardware accelerators to deliver more computing at higher efficiencies. This paper describes the design and deployment, at scale, of a new accelerator targeted at warehouse-scale video transcoding. We present our hardware design including a new accelerator building block – the video coding unit (VCU) – and discuss key design trade-offs for balanced systems at data center scale and co-designing accelerators with large-scale distributed software systems. We evaluate these accelerators “in the wild" serving live data center jobs, demonstrating 20-33x improved efficiency over our prior well-tuned non-accelerated baseline. Our design also enables effective adaptation to changing bottlenecks and improved failure management, and new workload capabilities not otherwise possible with prior systems. To the best of our knowledge, this is the first work to discuss video acceleration at scale in large warehouse-scale environments.

Machine learning based classifiers are often a black box when considering the contribution of inputs to the output probability of a label, especially with complex non-linear models such as neural networks. A popular way to explain machine learning model outputs in a model agnostic manner is through the use of Shapley values. For our use case of abuse fighting in digital advertisements, one primary impediment of using Shapley values in explanations was a problem of instability. Specifically, the instability problem manifests as explanations for the same example varying greatly due to random sampling in the algorithm. We found it useful to view this problem explicitly as Monte Carlo integration in the form of averaging the model output while varying only a subset of features in the example to be explained. In turn, this guides the number of samples needed to achieve a stable estimate of individual Shapley values and unlocked the use of Shapley value based explainers for our models as well as classifiers in general, including neural networks.

Automatic epilepsy seizure detection based on electroencephalography (EEG) signals has been a hot topic in the bioinformatics community. Recently, graph representations named complex networks have been increasingly utilized to characterize EEG signals. However, existing time-domain complex networks often suffer from undesired intra-class variance due to phase shift. Addressing this problem, we propose to obtain complex network representations in frequency domain where perfect data alignment can be achieved. The transformation to frequency domain highlights the urgency to retain sequential information in the signals. To this end, we propose to further extract features from the complex network representation using a novel deep model called Sequential Graph Convolutional Network (SGCN). Specifically, we incorporate state-of-the-art graph neural network (GNN) architecture with a novel sequential convolution operation which is key to preserving sequential information. Extensive experiments demonstrate the effectiveness and interpretability of our method. Our source code is available at https://github.com/JL-Wang-source-code/SGCN-for-epilepsy-detection.

Absence epilepsy is one of the most common types of epilepsy. The diagnosis of absence epilepsy is among the greatest challenges faced by clinical neurologists due to a lack of easily observable symptoms that are present in conventional epilepsy (e.g. spasm and convulsion), and highly relies on the detection of Spike and Slow Waves (SSWs) in Electroencephalogram (EEG) signals. Recently, graph representations called complex networks have been increasingly applied to characterizing 1D EEG signals. However, existing methods often fail to effectively represent SSWs, struggling to capture the differences between SSW waveforms and their non-SSW counterparts, such as minute differences and distinct shapes. Addressing this issue, in this work, we propose two simple yet effective complex networks, Overlook Graph (OG) and Weighted Overlook Graph (WOG), which have been customized to expressively represent SSWs. Built upon OG and WOG, we then develop a 2D Convolutional Neural Network (2D-CNN) to further learn latent features from the graph representations and accomplish the detection task. Extensive experiments on a real-world absence epilepsy EEG dataset show that the proposed OG/WOG-2D-CNN method can accurately detect SSWs. Additional experiments on the well-known Bonn dataset further show that our method can generalize to the conventional epilepsy seizure detection task with highly competitive performances.

This paper revisits the problem of rate distortion optimization (RDO) with focus on inter-picture dependence. A joint RDO framework which incorporates the Lagrange multiplier as one of parameters to be optimized is proposed. Simplification strategies are demonstrated for practical applications. To make the problem tractable, we consider an approach where prediction residuals of pictures in a video sequence are assumed to be emitted from a finite set of sources. Consequently the RDO problem is formulated as finding optimal coding parameters for a finite number of sources, regardless of the length of the video sequence. Specifically, in cases where a hierarchical prediction structure is used, prediction residuals of pictures at the same prediction layer are assumed to be emitted from a common source. Following this approach, we propose an iterative algorithm to alternatively optimize the selections of quantization parameters (QPs) and the corresponding Lagrange multipliers. Based on the results of the iterative algorithm, we further propose two practical algorithms to compute QPs and the Lagrange multipliers for the RA(random access) hierarchical video coding: the first practical algorithm uses a fixed formula to compute QPs and the Lagrange multipliers, and the second practical algorithm adaptively adjusts both QPs and the Lagrange multipliers. Experimental results show that these three algorithms, integrated into the HM 16.20 reference software of HEVC, can achieve considerable RD improvements over the standard HM 16.20 encoder, in the common RA test configuration.

Bi-geometric transparent composite models (BGTCM) are used to model distributions of transform coefficients in HEVC (High efficiency video coding). Both Kullback-Leibler divergence and χ2test show that, for both original and quantized transform coefficients in HEVC, BGTCMs provide better modelling performance than popular Laplacian and Cauchy models. Based on BGTCMs, a rate control algorithm is proposed for HEVC. Experimental results using the HEVC reference software show that the proposed algorithm achieves better performance in constant-bit-rate control than previous rate control algorithms based on Laplacian models.

This paper considers the problem of quantization in image coding where quality loss is measured by weighted mean squared error (WMSE) in an attempt to maintain structural similarity (SSIM). A rate distortion optimized quantization (RDOQ) scheme based on the WMSE is described and integrated in libjpeg. Experimental results on standard test images show that libjpeg with the RDOQ scheme achieves superior rate-SSIM performance against libjpeg (with or without MSE-based RDOQ) and the more recent WebP, while maintaining full JPEG compatibility.

Causal video coding is a coding paradigm where video source frames X1, X2,..., XNare encoded in a frame-by-frame manner, the encoder for each frame can use all previous source frames and all previous encoded frames, and the corresponding decoder can use only all previous encoded frames. In the special case where the encoder for each frame Xkis further restricted to enlist help only from all previous encoded frames, causal video coding is reduced to predictive video coding, which all MPEG-series and H-series video coding standards proposed so far are based upon. In this paper, we compare the rate distortion performance of causal video coding with that of predictive video coding from an information theoretic perspective by modeling each frame Xkitself as a source Xk={Xk(i)}i=1∞. Let Rc*(D1,...,DN) (Rp*(D1,...,DN), respectively) denote the minimum total rate required to achieve a given distortion level D1,...,DNin causal video coding (predictive video coding, respectively). We first show that like Rc*(D1,..., DN), for jointly stationary and totally ergodic sources X1, X2,..., XN, Rp*(D1,...,DN) is equal to the infimum of the nth order total rate distortion function Rp,n(D1,...,DN) over all n, where Rp,n(D1,...,DN) itself is given by the minimum of an information quantity over a set of auxiliary random variables. We then prove that if the jointly stationary and totally ergodic sources X1,..., XNform a (first-order) Markov chain, we have Rp*(D1,...,DN)=Rc*(D1,...,DN). However, this is not true in general if X1,..., XNdo not form a (first-order) Markov chain. Specifically, we demonstrate that for independent and identically distributed vector source (X1,..., XN), if X1,..., XNdo not form a (first-order) Markov chain, then under some conditions on source frames and distortion, Rc*(D1,..., DN) is strictly less than Rp*(D1,..., DN) in general. Our techniques allow us to compare Rp*(D1,..., DN) with Rc*(D1,..., DN) even when the single-letter characterization of Rp*(D1,..., DN), if any, is unknown.

AVS2 is a next-generation audio and video coding standard currently under development by the Audio Video Coding Standard Workgroup of China. In this paper, a coefficient-group based transform coefficient coding design for AVS2 video coding standard is presented, which includes two main coding tools, namely, two-level coefficient coding and intra-mode based context design. The two-level coefficient coding scheme allows accurate coefficient position information to be used in the context model design and improves the coding efficiency. It also helps increase the entropy coding throughput and facilitate parallel implementation. The intra-mode based context design further improves coding performance by utilizing the intra-prediction mode information in the context model. The two coding tools combined provide consistent rate-distortion performance gains under standard test conditions. Both tools were adopted into the AVS2 working draft. Furthermore, an improved rate-distortion optimized quantization algorithm is designed based on the proposed scheme, which significantly reduces the encoder complexity.

In this paper, a novel adaptive post-filtering method is introduced for effective video coding. Specifically, an enhanced filtering capability is obtained by partitioning a reconstructed video frame into non-overlapping segments based on local pattern information. Experimental results show that the proposed approach has the potential to produce an enhanced video frame reconstruction with more implementable filters when compared to existing adaptive post-filtering.

High Efficiency Video Coding (HEVC) is the next-generation video coding standard currently under development, which has demonstrated substantial bit savings (rate reduction by approximately half) compared to H.264/AVC. This paper presents the multiple sign bits hiding scheme that was adopted into the committee draft of HEVC at the 8th JCT-VC meeting. In HEVC, the quantized transform coefficients are entropy-coded in groups of 16 coefficients for each transform unit. With multiple sign bits hiding, for coefficient groups that satisfy certain conditions, the sign of the first non-zero coefficient along the scanning path is not explicitly transmitted in the bitstream and instead is inferred from the parity of the sum of all non-zero coefficients in that coefficient group at the decoder. To ensure the matching between the hidden sign and the parity of the sum of all non-zero coefficients, a parity adjustment method is employed at the encoder based on rate-distortion optimization or distortion minimization. Compared with conventional video coding schemes where quantization and coefficient coding are separately designed, the multiple sign bits hiding scheme in HEVC represents a joint quantization and coefficient coding design and provides consistent rate-distortion performance gains for all standard test sequences under standard test conditions.

Linear interactive encoding and decoding (IED) for near lossless source coding with decoder only side information is considered, where the interactive encoder uses linear codes (described by parity-check matrices over a finite fieldX) for encoding. It is first demonstrated how to convert any classical universal lossless codeCn(with block lengthnand with side information available to both the encoder and decoder) into a universal random linear IED scheme based on Gallager's parity check ensemble. It is then shown that there is no performance loss by restricting IED to linear IED, and that the universal random linear IED scheme based on Gallager's parity check ensemble achieves essentially the same rate performance as doesCnfor each and every individual sequence pair (xn,yn) while the word decoding error probability goes to 0 asn→ ∞ . Define the density of a linear IED scheme as the percentage of nonzero entries in its parity-check matrix. To reduce the encoding complexity of linear IED, low density linear IED is further investigated in terms of the trade-off among its rate, decoding error probability, and density.

Causal video coding is considered from an information theoretic point of view, where video source frames X1, X2, ..., XNare encoded in a frame by frame manner, the encoder for each frame Xkcan use all previous frames and all previous encoded frames while the corresponding decoder can use only all previous encoded frames, and each frame Xkitself is modeled as a source Xk= {Xk(i) }i=1∞. A novel computation approach is proposed to analytically characterize, numerically compute, and compare the minimum total rate of causal video coding Rc*(D1, ...,DN) required to achieve a given distortion (quality) level D1, ...,DN>; 0. Among many other things, the computation approach includes an iterative algorithm with global convergence for computing Rc*(D1, ...,DN) . The global convergence of the algorithm further enables us to demonstrate a somewhat surprising result (dubbed the more and less coding theorem)-under some conditions on source frames and distortion, the more frames need to be encoded and transmitted, the less amount of data after encoding has to be actually sent. With the help of the algorithm, it is also shown by example that Rc*(D1, ...,DN) is in general much smaller than the total rate offered by the traditional greedy coding method. As a by-product, an extended Markov lemma is established for correlated ergodic sources.

This paper considers the problem of downsampling H.264 compressed video, where a full-resolution compressed video sequence conforming to H.264 is transcoded into another compressed video sequence conforming to H.264 at a lower target resolution. A transcoding framework that makes efficient use of full-resolution information is proposed. In this framework, residuals and motion vectors at the target resolution are first predicted from their full-resolution counterparts. These predicted residuals and motion vectors are then applied to optimize the actual rate-distortion (RD) performance. Experimental results show that, compared against the benchmark system, which cascades an H.264 decoder, a spatial downsampler, and an H.264 encoder, and is generally regarded having the best possible RD performance, the proposed framework, surprisingly, provides consistently superior RD performance with up to 0.7 dB gain. Furthermore, the framework has the desired feature of being configurable to strike the right balance between rate-distortion performance and computational complexity according to application requirements.

A source coding paradigm called interactive encoding and decoding (IED) is considered for a source network where a finite alphabet sourceXis to be encoded, and another finite alphabet sourceYcorrelated withXis available only to the decoder as a helper. The optimal performance achievable asymptotically (OPAA) by IED is investigated, where the performance is measured as the average number of bits per symbol exchanged by the encoder and decoder until the decoder learnsXwith high probability. First, it is shown that for any stationary(X,Y), the OPAA by IED is given by the conditional entropy rateH(X|Y) ofXgivenY. This is in contrast with noninteractive Slepian-Wolf (SW) coding, where the OPAA is shown in general to be strictly greater thanH(X|Y) when(X,Y) is not ergodic. Second, for a memoryless source pair (X, Y), it is shown that IED approachesH(X|Y) faster than SW coding does. Finally, it is demonstrated that one can convert any classical universal data compression algorithm with side information to a universal IED algorithm for the class¿of all stationary ergodic source pairs. In contrast, universal SW coding algorithms for the class¿do not exist.

Using fixed rate uniform vector quantization, in this paper, we consider how to design a joint watermarking and compression (JWC) system for Gaussian and Laplacian sources to maximize the robustness in the presence of additive Gaussian attacks under constraints on the compression rate and quantization distortion. Firstly, we construct vector quantizers shaped to match the multidimensional distribution of source signals. Then we scale codebooks corresponding to the vector quantizers to maximize the robustness of the watermarks against the additive Gaussian attacks. Simulation results show that the proposed scheme can achieve up to 0.92 dB distortion-to-noise ratio (DNR) gain over JWC schemes using uniform scalar quantization while maintaining the simplicity of implementation with uniform quantization.

Quantization in H.264 is achieved in the DCT domain using scalar quantizers, which assume a sum distortion constraint and often produce considerably larger distortions on block boundaries than inside a block in the pixel domain. This biased distortion distribution degrades the rate distortion (RD) performance of H.264 intra coding whose prediction is exclusively based on boundary pixels. This paper considers the problem of designing balanced distortion quantizers (BDQs) in the DCT domain, which, in addition to the sum distortion constraint, require evenly distributed distortions in the pixel domain. In a special case where DCT coefficients are independent Gaussian, the problem is solved as a convex optimization problem. Using this approach, we design BDQs and apply them to improve H.264 intra coding. Experimental results on typical frames show that the improved intra coding scheme consistently outperforms its counterpart in H.264 main-profile, averaging 5–9% rate reduction for QCIF frames, and 7–12% for CIF frames with aligned distortions.

Causal video coding is considered from an information theoretic point of view, where video source frames X1, X2, ? ? ? XNare encoded in a frame by frame manner, the encoder for each frame Xk, k = 1, ? ? ?, N, can use all previous frames and all previous encoded frames while the corresponding decoder can use only all previous encoded frames, and each frame Xkitself is modeled as a source Xk= {Xk(i)}i=1?. A novel computation approach is proposed to analytically characterize and numerically compute the minimum total rate Rc(D1, ? ? ?, DN) required to achieve a given distortion (quality) level D1, ? ? ?, DN? 0. Specifically, we first show that for jointly stationary ergodic sources X1, X2, ? ? ?, XN, Rc(D1, ? ? ?, DN) is equal to the infimum of the nthorder total rate distortion function Rc,n(D1, ? ? ?, DN) over all n, where Rc,n(D1, ? ? ?, DN) itself is given by the minimum of an information quantity over a set of auxiliary random variables. We then present an iterative algorithm for computing Rc,n(D1, ? ? ?, DN) and demonstrate the convergence of the algorithm to the global minimum. The global convergence of the algorithm further enables us to establish a single-letter characterization of Rc(D1, ? ? ?, DN) in a novel way when the N sources are an independent and identically distributed vector source. Deep insights from the algorithm are also gained regarding how each frame should be encoded in order to achieve Rc(D1, ? ? ?, DN); it is demonstrated by example that Rc(D1, ? ? ?, DN) is in general much smaller than the total rate offered by the traditional greedy coding method by which each frame is encoded in a local optimum manner based on all information available to the encoder of the frame. In addition, a tight achievable rate distortion region is also derived.

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.

In this paper, we consider a paradigm of source coding called interactive encoding and decoding (IED). It illustrates this paradigm for a source network with one encoder and one decoder. Contrasting IED with SW coding, we see that in this new paradigm, information flows in both ways, and thus the encoder and decoder are allowed to interact with each other to accomplish a certain task.

Consider a source network in which a finite alphabet source X = {Xi}i=0infinis to be encoded and transmitted, and another finite alphabet source Y = {Xi}i=0infincorrelated with X is available only to the decoder as side information. Traditionally, the channel between the encoder and decoder in the source network is assumed to be one-way. This, together with the fact that the encoder does not have access to Y, implies that the encoder has to know the achievable rates before encoding. In this paper, we consider universal source coding for a feedback source network in which the channel between the encoder and decoder is two-way and asymmetric. Assume that the encoder and decoder share a random database that is independent of both X and Y. A string matching-based (variable-rate) block coding algorithm with simple progressive encoding and joint typicality decoding is first proposed for the feedback source network. The simple progressive encoder does not need to know the achievable rates at the beginning of encoding. It is proven that for any (X, Y) in a large class of sources satisfying some mixing conditions, the average number of bits per letter transmitted from the encoder to the decoder (compression rate) goes to the conditional entropy H(X | Y) of X given Y asymptotically, and at the same time the average number of bits per letter transmitted from the decoder to the encoder (feedback rate) goes to 0 asymptotically. The algorithm and the corresponding analysis results are then extended to the case where both X and Y are to be encoded separately, but decoded jointly. Finally, a universal decoding algorithm is proposed to replace the joint typicality decoding, and the resulting universal compression algorithm consisting of the simple progressive encoder and the universal decoding algorithm is further shown to be asymptotically optimal for the class of all jointly memoryless source-side information pairs (X,Y).

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.

The performance of uniform threshold quantization subject to an entropy constraint is studied for a sum of two and three independent zero-mean memoryless Laplacian sources. Both symmetric and asymmetric quantizers are considered, and approximate parametric expressions for the operational rate-distortion function R(D) are obtained for all rates. In particular, the low rate regime (rates below 1 bit per sample) is considered and simpler expressions for R(D) are derived. It is envisioned that these expressions will facilitate rate estimation in practical Wyner-Ziv coding with low complexity encoder.

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.

The Slepian-Wolf coding problem is often viewed as a channel coding problem for the purpose of gaining insight into its properties. In this perspective, source sequences are associated with balls of side information sequences, and then one packs in each bin as many of these balls as possible with little or no overlap. Alternatively, one can treat the problem as a source coding problem in which for a given side information sequence, the set of conditionally probable source sequences is distributed in as many bins as required by a fidelity criterion. In an earlier series of publications we developed the theory of redundancy of variable rate Slepian-Wolf codes using the first viewpoint. In this work, we obtain similar results from the second viewpoint; this direction has unique technical challenges but also reinforces the fundamental role of our previously introduced notion of intrinsic entropy. In one of our key technical contributions, we use an averaging argument resembling Shannon's random coding idea that we expect will be useful in studying other problems of source coding with side information.

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.

In this paper we investigate universal data compression with side information at the decoder by leveraging traditional universal data compression algorithms. Specifically, consider a source network with feedback in which a finite alphabet source X = {Xi}i=0infinis to be encoded and transmitted, and another finite alphabet source Y = {Yi}i=0infinavailable only to the decoder as the side information correlated with X. Assuming that the encoder and decoder share a uniform i.i.d. (independent and identically distributed) random database that is independent of (X, Y), we propose a string matching-based (variable-rate) block coding algorithm with a simple progressive encoder for the feedback source network. Instead of using standard joint typicality decoding, this algorithm derives its decoding rule from the codeword length function of a traditional universal lossless coding algorithm. As a result, neither the encoder nor the decoder assumes any prior knowledge of the joint distribution of (X, Y) or even the achievable rates. It is proven that for any (X, Y) in the class of all stationary, ergodic source-side information pairs with finite alphabet, the average number of bits per letter transmitted from the encoder to the decoder (compression rate) goes arbitrarily close to the conditional entropy rate H(X|Y) of X given Y asymptotically, and the average number of bits per letter transmitted from the decoder to the encoder (feedback rate) goes to 0 asymptotically.

A typical arithmetic coder consists of three steps: range calculation, renormalization, and probability model updating. In this paper, we propose and analyze from an information theoretic point of view a greedy renormalization method, which has two components: greedy thresholding and greedy outputting. The method significantly reduces the computational complexity of the renormalization step of arithmetic coding by (1) using the greedy thresholding to minimize the number of renormalizations required to encode a sequence and (2) using the greedy outputting to minimize the number of operations within each renormalization. The method is particularly suitable for binary arithmetic coding (BAC). Two BAC algorithms based on this method are presented. The first algorithm replaces the renormalization method in the TOIS BAC with the greedy renormalization method, and keeps other parts of the TOIS BAC unchanged. For binary independent and identically distributed (i.i.d.) sources with the probability of the less probable symbol ranging from --, over gain in speed (on average), and less than loss in compression rate (in the worst case) are observed in the experiments. The second algorithm combines the greedy renormalization method with the QM-Coder. On an average, gain in speed and gain in compression rate are observed in the experiments.

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

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

In this paper we analyze the redundancy of variable rate Slepian-Wolf coding. For any memoryless source-side information pair (X, Y) = {(Xi,Yi)}Einfini=1with finite alphabet, the redundancy Rn(epsin) of variable rate Slepian-Wolf coding is defined as the minimum of the difference between the compression rate of any variable-rate Slepian-Wolf code resulting from coding XEn1with decoding error probability epsin, and the conditional entropy H(X|Y). It is proved that under mild assumptions, for sufficiently large n, Rn(epsin) is lower bounded by dradiclog n/n, where d > 0 is a constant

In this paper we investigate the relationship between Slepian-Wolf (S-W) coding and channel coding. It is shown that any S-W coding problem is dual to a channel coding problem for a semi-symmetric channel. This result holds for any stationary, ergodic source-side information pair with finite alphabet

In distributed networks, the signer wants his signature to be verified by anyone in the same group with him and the recipient wants to verify the signature independently. Motivated by this consideration, a certificateless group inside signature is presented in this paper. The signature scheme has the following properties: despite being without certificate, it can provide an assurance to the user about the relationship between a public key and the identity of the holder of the corresponding private key; a signature can be verified independently by any member in the same group with the signer; nobody outside the group can verify a signature. It is only the signer who knows his private key, even the PKG (private key generator) doesn't; any one in or outside the group can't forge a signature of others.

Consider a source network in which a finite alphabet source X = {Xi}iinfin=0is to be encoded and transmitted, and another finite alphabet source Y = {Yi}iinfin=0available only to the decoder as the side information correlated with X. Traditionally the channel between the encoder and decoder in the source network is assumed to be one-way. This, together with that the encoder does not have access to Y, necessitates that the encoder knows the achievable rates before encoding. In this paper we consider universal source coding for a feedback source network in which the channel between the encoder and decoder is two-way and asymmetric. Assuming that the encoder and decoder share a random database that is independent of both X and Y, we propose a string matching-based (variable-rate) block coding algorithm with a simple progressive encoder for the feedback source network. This algorithm does not need to know the achievable rates at the beginning of encoding. It is proven that for any (X, Y) in a large class of sources which includes the class of all memoryless sources, the class of all aperiodic Markov sources, and a large class of finite-state sources as special subclasses, the average number of bits per letter transmitted from the encoder to the decoder (compression rate) goes arbitrarily close to the conditional entropy H(X|Y) of X given Y asymptotically, and the average number of bits per letter transmitted from the decoder to the encoder (feedback rate) goes to 0 asymptotically

SVK-lattices, in which the shortest vector is known, are proposed for the first time. Two theorems on the relationship between cyclic lattices and SVK-lattices are proposed and proved. By these constructive theorems, SVK-lattices can be simply generated. Pseudo-cyclic lattices, whose random properties are better than cyclic lattice, are also investigated for the first time. Two algorithms are designed for generating random SVK-lattices from pseudo-cyclic lattices. A general algorithm for randomizing a lattice basis is presented at the end of this paper.

In this paper security requirements and security architecture for 4G systems are presented with the consideration of Trusted Computing (TC) for mobile equipment (ME). The security framework based on Trusted Mobile Platform (TMP) and PKI is proposed to provide a considerable robust platform for user’s access to sensitive service and data in the scenario of 4G systems. Over this framework, with the combination of password and biometric identification (BI) as well as public key-based identification, an efficient hybrid authentication and key agreement (HAKA) scheme is presented to resist the possible attacks, particularly the attacks on/from ME. Compared with 3G architecture and other security schemes for 4G mobile networks, our architecture and corresponding HAKA is more secure, scalable and convenient to support globe mobility and capable of being employed to handle the complicated security issues in 4G mobile networks.

In this paper, we investigate the performance of grammar-based codes for sources with countably infinite alphabets. Let /spl Lambda/ denote an arbitrary class of stationary, ergodic sources with a countably infinite alphabet. It is shown that grammar-based codes can be modified so that they are universal with respect to any /spl Lambda/ if and only if there exists a universal code for /spl Lambda/. Moreover, upper bounds on the worst case redundancies of grammar-based codes among large sets of length-n individual sequences from a countably infinite alphabet are established. Depending upon the conditions satisfied by length-n individual sequences, these bounds range from O(loglogn/logn) to O(1/log/sup 1-/spl alpha//n) for some 0</spl alpha/<1. These results complement the previous universality and redundancy results in the literature on the performance of grammar-based codes for sources with finite alphabets.

Grammar-based coding is investigated from three new perspectives. First, we revisit the performance analysis of grammar-based codes by proposing context-based run-length encoding algorithms as new performance benchmarks. A redundancy result stronger than all previous corresponding results is established. We then extend the analysis of grammar-based codes to sources with countably infinite alphabets. Let /spl Lambda/ denote an arbitrary class of stationary, ergodic sources with a countably infinite alphabet. It is shown that grammar-based codes can be modified so that they are universal with respect to any /spl Lambda/ for which there exists a universal code. Moreover, upper bounds on the worst-case redundancies of grammar-based codes among large sets of length-n individual sequences from a countably infinite alphabet are established. Finally, we propose a new theoretic framework for compression in which grammars rather than sequential stochastic processes are used as source generating models, and point out some open problems in the framework.

The compression performance of grammar-based codes is revisited from a new perspective. Previously, the compression performance of grammar-based codes was evaluated against that of the best arithmetic coding algorithm with finite contexts. In this correspondence, we first define semifinite-state sources and finite-order semi-Markov sources. Based on the definitions of semifinite-state sources and finite-order semi-Markov sources, and the idea of run-length encoding (RLE), we then extend traditional RLE algorithms to context-based RLE algorithms: RLE algorithms with k contexts and RLE algorithms of order k, where k is a nonnegative integer. For each individual sequence x, let r/sup *//sub sr,k/(x) and r/sup *//sub sr|k/(x) be the best compression rate given by RLE algorithms with k contexts and by RLE algorithms of order k, respectively. It is proved that for any x, r/sup *//sub sr,k/ is no greater than the best compression rate among all arithmetic coding algorithms with k contexts. Furthermore, it is shown that there exist stationary, ergodic semi-Markov sources for which the best RLE algorithms without any context outperform the best arithmetic coding algorithms with any finite number of contexts. Finally, we show that the worst case redundancies of grammar-based codes against r/sup *//sub sr,k/(x) and r/sup *//sub sr|k/(x) among all length- n individual sequences x from a finite alphabet are upper-bounded by d/sub 1/loglogn/logn and d/sub 2/loglogn/logn, respectively, where d/sub 1/ and d/sub 2/ are constants. This redundancy result is stronger than all previous corresponding results.

Summary form only given. A novel method that significantly reduces the computational complexity of the re-normalization step of arithmetic coding is described. Called greedy re-normalization, the method involves a reduction to both the number of re-normalizations required to encode and the number of operations within each re-normalization. To reduce the number of re-normalizations in the encoding sequence, the method adopts a dynamic re-normalization criterion. Experimental results show that the proposed greedy re-normalization method indeed improved the speed of arithmetic coding.

For pt. I see ibid., vol.46, p.755-88 (2000). The concept of context-free grammar (CFG)-based coding is extended to the case of countable-context models, yielding context-dependent grammar (CDG)-based coding. Given a countable-context model, a greedy CDG transform is proposed. Based on this greedy CDG transform, two universal lossless data compression algorithms, an improved sequential context-dependent algorithm and a hierarchical context-dependent algorithm, are then developed. It is shown that these algorithms are all universal in the sense that they can achieve asymptotically the entropy rate of any stationary, ergodic source with a finite alphabet. Moreover, it is proved that these algorithms' worst case redundancies among all individual sequences of length n from a finite alphabet are upper-bounded by d log log n/log n, as long as the number of distinct contexts grows with the sequence length n in the order of O(n/sup a/), where 0 < /spl alpha/ < 1 and d are positive constants. It is further shown that for some nonstationary sources, the proposed context-dependent algorithms can achieve better expected redundancies than any existing CFG-based codes, including the Lempel-Ziv (1978) algorithm, the multilevel pattern matching algorithm, and the context-free algorithms in Part I of this series of papers.