This work addresses the problem of jointly optimizing the binary offloading decision making and the communication resource allocation for a system using time-division multiple access (TDMA). The goal is to minimize the cost of the energy expended by all devices, while meeting individual deadlines and power budget constraints. Prior work addressing this problem proposed a suboptimal solution. We show that the problem can be solved globally optimally using an efficient dynamic programming algorithm.

This work addresses the scenario where two dis-tributed sensor nodes encode the input vectors and send their messages to a server node where a joint decoder outputs one of two possible class labels. We assume that the vector sources are discrete and conditionally independent given the class label. The problem is to design the two encoders and the joint decoder such that the probability of classification error is minimized. Up to our knowledge, the only known globally optimal solution to this prob-lem is an exhaustive search, which requires$N^{K_{1}+K_{2}}(N+K_{1}K_{2})$operations, where$N$is the size of the largest alphabet of the input vectors and$K_{k}$is the number of quantizer regions of the encoder at node$k$, for$k=1,2$. We propose a considerably faster globally optimal solution with time complexity$O(K_{1}K_{2}N^{3})$. To achieve this, we first convert the problem to a distributed scalar quantizer design problem in a transformed domain related to the likelihood ratio domain. Next, we prove that the problem is equivalent to a constrained minimum weight path problem in a certain weighted directed acyclic graph with$O(N^{3})$vertices and$O(N^{4})$edges. Further, we show that the dynamic programming solution algorithm to the latter problem can be accelerated by leveraging a fast matrix search technique in matrices with the Monge property.

This paper tackles the problem of proportional fairness-based power allocation in downlink non-orthogonal multiple access (NOMA) systems. We address the scenario where the users are divided into groups of two. NOMA technique is applied within each group with the superposition coding at the transmitter side and successive interference cancellation (SIC) at the receivers’ side, and different groups are assigned separate channels. We assume that the grouping and the channel assignment are dynamically performed, and we optimize the power allocation among users by maximizing the sum of logarithmic rates with a constraint on the total transmit power. We prove that the globally optimal solution to the optimization problem can be obtained by solving the Karush-Kuhn-Tucker (KKT) conditions and propose an efficient algorithm for this purpose. Extensive experimental results demonstrate that the proposed scheme outperforms several existing NOMA schemes in terms of system throughput and/or fairness, achieving the best trade-off between these two criteria.

This work is concerned with the design of a distributed scalar quantizer (DSQ) with two encoders, for linear classification. The objective of the optimization is to minimize the classification error of the classifier applied to the quantized inputs in the training sequence with respect to the classifier applied on unquantized inputs. We prove that the optimal DSQ design problem is equivalent to a minimum weight path problem with some constraints on the number and types of edges in a certain weighted directed acyclic graph. Further, we propose a solution algorithm with time complexity$O(K_{1}K_{2}N^{4})$, where$N$is the size of the training sequence while$K_{1}$and$K_{2}$are the numbers of cells of the two encoders, respectively. In addition, we develop faster design algorithms for the equal-rate case (i.e.,$K_{1}=K_{2}=K$). Specifically, when the training sequence is symmetric, we prove that there exists an optimal DSQ where the thresholds of the encoders' partitions are interleaved. By leveraging this property and the symmetry of the training sequence, we propose a$O(KN^{2})$time solution algorithm. For the case when the training sequence is not symmetric, we propose an algorithm with the same time complexity that minimizes an upper bound on the misclassification ratio. Experimental results prove the considerable superiority of the proposed approaches in comparison with prior work in both symmetric and asymmetric scenarios.

A common technique for the partial encryption of compressed images and videos encrypts only the sign bits of some syntax elements such as the quantized transform coefficients or the motion vector differences. The sign bit can be interpreted as the most significant bit (MSB) in the binary representation of the syntax element. Our work is motivated by the key observation that the binary code used for this representation has an impact on the quality of the reconstruction at the eavesdropper and on the size of the stream to be encrypted. Therefore, we address the problem of optimal binary code design for partial encryption. Ideally, the goal is to simultaneously maximize the eavesdropper's distortion and minimize the length of the compressed MSB stream. Since these two objectives are conflicting in general, we formulate the problem as the maximization of a weighted sum of the eavesdropper's distortion and of the probability of the MSB being 0. We cast the problem as a binary integer linear program equivalent to a maximum weight matching problem, which has a polynomial-time solution algorithm. We show that when the source to be quantized and the quantizer are symmetric, the problem can be converted to a linear program of a smaller size, for a family of distortion metrics. Extensive experiments assess the performance of the optimized binary code in comparison with existing approaches. The results reveal that certain existing partial encryption schemes could benefit from the proposed design.

This paper presents an algorithm for the optimal design of general entropy-constrained successively refinable unrestricted polar quantizer, i.e., with arbitrary number L of refinement levels, for bivariate circularly symmetric sources. The optimization problem is formulated as the minimization of a weighted sum of distortions and entropies for the scenario where the magnitude quantizers' thresholds are confined to a predefined finite set. The proposed solution algorithm is globally optimal. It involves L stages, where each stage corresponds to an unrestricted polar quantizer (UPQ) level, and includes solving the minimum-weight path problem for multiple node pairs in a series of weighted directed acyclic graphs. Additionally, we derive an upper bound Pmax(l), l ∈ [1 : L], on the possible number of phase levels in any phase quantizer of the l-th level UPQ, which grows linearly with l. The time complexity of the proposed approach is O(L2K3Pmax(l)), where K is the cardinality of the predefined set of possible magnitude thresholds. Finally, the experimental results for L = 3 demonstrate the effectiveness in practice of the proposed scheme.

This paper addresses the design of a sequential scalar quantizer (SSQ) for finite-alphabet correlated sources in the fixed-rate (FR) and entropy-constrained (EC) cases. The optimization problem is formulated as the minimization of a weighted sum of distortions and rates. The proposed solution is globally optimal for the class of SSQs with convex cells and is based on solving the minimum-weight path (MWP) problem in the EC case, respectively, a length-constrained MWP problem in the FR case, in a series of weighted directed acyclic graphs. The asymptotic time complexity is O(K12K22), where K1and K2are the respective sizes of the alphabets of the two sources. Additionally, it is proved that, by applying the proposed algorithms to discretizations of correlated sources with continuous joint probability density function, the performance approaches that of the optimal EC-SSQ, respectively, FR-SSQ, with convex cells for the original sources as the accuracy of the discretization increases. Extensive experiments performed with correlated Gaussian sources validate the effectiveness in practice of the proposed approach in approximating the optimal SSQ for the case of continuous-alphabet sources.

This paper addresses the design of two-stage successively refinable unrestricted polar quantizers for bivariate circularly symmetric sources in the entropy-constrained and fixed-rate cases. The proposed solutions are globally optimal when the thresholds of the magnitude quantizers are confined to finite discretizations of the interval [0, ∞). The algorithm developed for the entropy-constrained case involves a series of stages, including solving the minimum-weight path problem for multiple node pairs in certain weighted directed acyclic graphs. The asymptotical time complexity is O(K1K22Pmax), where K1and K2are the sizes of the sets of possible magnitude thresholds of the coarse and refined unrestricted polar quantizers (UPQs), respectively, while Pmaxis an upper bound on the number of phase levels in any phase quantizer of the coarse UPQ. The solution algorithm for the fixed-rate case is based on solving a succession of dynamic programming problems for multiple coarse quantizer bins. The time complexity in the fixed-rate case amounts to O(K1K2N2N1), where N1is the number of cells of the coarse UPQ and N is the ratio between the number of bins of the fine and coarse UPQs. The extensive experimental results on a bivariate circularly symmetric Gaussian source show the effectiveness of the proposed schemes.

This paper addresses the optimal design of a two-stage Wyner-Ziv scalar quantizer with forwardly or reversely degraded side information (SI) for finite-alphabet sources and SI. We assume that the binning is performed optimally and address the design of the quantizer partitions. The optimization problem is formulated as the minimization of a weighted sum of distortions and rates. The proposed solution is globally optimal when the cells in each partition are contiguous. The solution algorithm is based on solving the single-source or the all-pairs minimum-weight path (MWP) problem in certain weighted directed acyclic graphs. When the conventional dynamic programming technique is used to solve the underlying MWP problems, the time complexity achieved is O(N3), where N is the size of the source alphabet. A so-called partial Monge property is additionally introduced, and a faster solution algorithm exploiting this property is proposed. Experimental results assess the practical performance of the proposed scheme.

In this paper, we propose a lattice-based robust distributed source coding system for two correlated sources and provide a detailed performance analysis under the high resolution assumption. It is shown, among other things, that, in the asymptotic regime where: 1) the side distortion approaches 0 and 2) the ratio between the central and side distortions approaches 0, our scheme is capable of achieving the information-theoretic limit of quadratic multiple description coding when the two sources are identical, whereas a variant of the random coding scheme by Chen and Berger with Gaussian codes has a performance loss of 0.5 bits relative to this limit.

This paper proposes an algorithm for the design of entropy-constrained unrestricted polar quantizer (ECUPQ) for bivariate circularly symmetric sources. The algorithm is globally optimal for the class of ECUPQs with magnitude quantizer thresholds confined to a finite set. The optimization problem is formulated as the minimization of a weighted sum of the distortion and entropy and the proposed solution is based on modeling the problem as a minimum-weight path problem in a certain weighted directed acyclic graph. The proposed algorithm enables solving the overall problem in O(K2log|P̂|) time, where K is the size of the set of possible magnitude thresholds and P̂ is the set of the number of phase levels for the uniform phase quantizers.

This letter presents an algorithm for the design of fixed-rate unrestricted polar quantizer (FUPQ) for bivariate circularly symmetric sources. The proposed algorithm is globally optimal for the class of FUPQs with the magnitude quantizer thresholds restricted to some predefined finite set. The solution algorithm is based on dynamic programming, which is further accelerated by exploiting the monotonicity property of the cost function. The time complexity of the accelerated algorithm is O(KN2 ), where N is the number of target qunatizer levels and K is the size of the predefined set of possible thresholds. The experimental results show that our approach outperforms the previous tractable designs when the total number of quantizer levels ranges between 25 and 256.

In conventional multiple description coding (MDC), two descriptions of a source are generated and sent over ON/OFF channels. In this paper, we are interested in exploiting the redundancy built in MDC to additionally confer robustness against other channel errors. In particular, we consider a multiple description lattice vector quantizer (MDLVQ) whose output (a pair of side lattice points) is mapped to a pair of binary indexes and each index is sent over a binary channel. One channel is noiseless, while the other is noisy. Thus, at the decoder, one description is received error-free, while the other may carry bit errors. Then the decoder uses the error-free description as side information to improve the reconstruction. The effectiveness of the decoder in alleviating the impact of bit errors depends on the mapping -y of side lattice points to binary indexes. We propose the design of a structured bit-error resilient mapping -y. For this, the set of side lattice points is first partitioned using Voronoi regions of an appropriate coarse lattice. Next a good linear channel code is selected, each Voronoi region is assigned a coset of this channel code, and the side lattice points within each Voronoi region are mapped to binary sequences in the corresponding coset. In addition, we argue that the performance of -y is improved by assigning cosets close in Hamming distance to neighboring Voronoi regions, and propose a technique to achieve this goal. We derive a lower bound on the error correction performance of the proposed mapping -y in terms of the performance of the channel code C used in its construction. Interestingly, we prove that, as the rate of the MDLVQ grows to infinity, the mapping -y becomes as good as the code C in correcting bit errors. Simulation results show the significant superiority of the proposed index mapping versus random mappings.

This paper proposes an algorithm for the design of entropy-constrained unrestricted polar quantizer (ECUPQ) for bivariate circularly symmetric sources. The algorithm is globally optimal for the class of ECUPQs with magnitude quantizer thresholds confined to a finite set. The optimization problem is formulated as the minimization of a weighted sum of distortion and entropy, and the proposed solution is based on modeling the problem as a minimum-weight path problem in a certain weighted directed acyclic graph. Each graph edge corresponds to a possible magnitude quantizer bin and computing its weight involves solving another optimization problem. We develop a fast strategy for evaluating all edge weights, leading to a O(K2+ KPmax) time solution algorithm, where K is the size of the set of possible magnitude thresholds and Pmax is the maximum number of phase levels. The practical performance of the proposed algorithm is assessed for a bivariate circularly symmetric Gaussian source, at rates ranging from 0.5 to 6 bits/sample. Our results demonstrate that the proposed approach achieves performance very close to the asymptotically optimal ECUPQ at all rates, while at low rates it significantly outperforms all previous UPQ schemes. Notably, peak improvement of 0.755 dB can be achieved for rates below 2.5.

This work addresses the construction of bit-error resilient multiple description lattice vector quantizers (MDLVQ) by proposing the design of a structured mapping γ of side lattice points to binary indexes. We assume that the first description is correct while the second description may carry bit errors. To design the mapping γ the set of side lattice points is first partitioned into Voronoi regions of an appropriate coarse lattice. Next a good channel code C is selected, each Voronoi region is assigned a coset of this channel code and the side lattice points within each Voronoi region are mapped to binary sequences in the corresponding coset. We derive a lower bound on the error correction performance of the mapping γ in terms of the performance of the code C and we show that, as the rate of the MDLVQ grows to i, the mapping γ becomes as good as the code C. Simulation results show the significant superiority of the proposed mapping versus random mappings.

This work addresses the design of a sequential code for correlated sources using entropy-constrained scalar quantization at each encoder. We consider discrete sources and propose a globally optimal algorithm to minimize a weighted sum of distortions and rates. Our algorithm is based on solving the minimum weight path problem in a series of appropriately constructed weighted directed acyclic graphs. Its asymptotical time complexity is O(N21N22), where N1and N2denote the alphabet sizes of the two sources, respectively.

This paper addresses the design of symmetric entropy-constrained multiple description scalar quantizers (EC-MDSQ) with linear joint decoders, i.e., where some of the decoders compute the reconstruction by averaging the reconstructions of individual descriptions. Thus, the use of linear decoders reduces the space complexity at the decoder since only a subset of the codebooks needs to be stored. The proposed design algorithm locally minimizes the Lagrangian, which is a weighted sum of the expected distortion and of the side quantizers' rates. The algorithm is inspired by the EC-MDSQ design algorithm proposed by Vaishampayan and Domaszewicz, and it is adapted from two to K descriptions. Differently from the aforementioned work, the optimization of the reconstruction values can no longer be performed separately at the decoder optimization step. Interestingly, we show that the problem is a convex quadratic optimization problem, which can be efficiently solved. Moreover, the generalization of the encoder optimization step from two to K descriptions increases drastically the amount of computations. We show how to exploit the special form of the cost function conferred by the linear joint decoders to significantly reduce the time complexity at this step. We compare the performance of the proposed design with multiple description lattice vector quantizers (MDLVQ) and with the multiple description scheme based on successive refinement and unequal erasure protection (UEP). Our experiments show that the proposed approach outperforms MDLVQ with dimension 1 quantization, as expected. Additionally, when more codebooks are added our scheme even beats MDLVQ with quantization dimension approaching ∞, for rates sufficiently high. Furthermore, the proposed approach is also superior to UEP with dimension 1 quantization when the rates are low.

This work addresses the tradeoff between quality fairness and system efficiency for scalable video delivery to multiple users over OFDMA wireless networks. We consider a cross-layer optimization framework seeking to maximize the sum-PSNR corresponding to average user rates, subject to relaxed PSNR-fair constraints. More specifically, a pure quality-fairness (PF) problem is solved first to determine the maximum PSNR value obtained by imposing the same PSNR level to all users. Next the constraints in the PF problem are relaxed by allowing the relative difference between the PSNR of each video and the PF PSNR value to be within some range [0, σ]. Thus, the parameter σ controls the tradeoff between quality fairness and system efficiency. The PF problem is equivalent to the quality fairness problem proposed by Cical`o and Tralli, which was solved using a vertical decomposition approach. Further, we convert the optimization problem with the relaxed fairness constraints into a convex problem and solve it using established techniques. Our simulation results show that by varying the value of σ, a wide range, densely populated, of tradeoff points between quality fairness and efficiency can be achieved. Additionally, a subjective quality assessment reveals that while the maximum efficiency scheme (ME), i.e., when σ = ∞, may compromise the quality of the high demanding videos, the PF scheme may sacrifice the quality of the low demanding videos. On the other hand, by providing a trade-off between PF and ME, the proposed scheme has the potential of finding a middle ground where all users are satisfied.

This paper introduces a linear permutation module before the inner encoder of the iteratively decoded product coding structure, for the transmission of scalable bit streams over error-prone channels1. This can improve the error correction ability of the inner code when some source bits are known from the preceding outer code decoding stages. The product code consists of a protograph low-density parity-check code (inner code) and Reed-Solomon (RS) codes of various strengths (outer code). Further, an algorithm relying on protograph-based extrinsic information transfer analysis is devised to design good base matrices from which the linear permutations are constructed. In addition, an analytical formula for the expected fidelity of the reconstructed sequence is derived and utilized in the optimization of the RS codes redundancy assignment. The experimental results reveal that the proposed approach consistently outperforms the scheme without the linear permutation module, reaching peak improvements of 1.98 dB and 1.30 dB over binary symmetric channels (BSC) and additive white Gaussian noise (AWGN) channels, respectively.

The general approach in a noisy channel scalar quantizer design is an iterative descent algorithm, which guarantees only a locally optimal solution. While sufficient conditions under which the local optimum becomes a global optimum are known in the noiseless channel case, such sufficient conditions were not derived for the noisy counterpart. Moreover, efficient globally optimal design techniques for general discrete distributions in the noiseless case exist; however, they seem not to extend to the noisy scenario when a fixed index assignment is assumed. Recently, the design of noisy channel scalar quantizer with random index assignment (RIA) was proposed using a locally optimal iterative algorithm. In this paper, we derive sufficient conditions for the uniqueness of a local optimum, which, thus, guarantee the global optimality of the solution. These sufficient conditions are satisfied for a log-concave probability density function which is, additionally, symmetric around its mean. Furthermore, we show that, assuming an RIA, the globally optimal design for general discrete sources can also be carried out efficiently.

This paper addresses the problem of increasing the robustness to bit errors for two description scalar quantizers. Our approach is to start with an m-diagonal index assignment and further apply a permutation to the indexes of each description to increase the minimum Hamming distance dminof the set of valid index pairs. In particular, we show how to construct linear permutation pairs achieving dmin3, and establish a lower bound in terms of the description rate R, for the highest value of m for which such permutations exist. For the case when one description is known to be correct, we propose a new performance measure, denoted by dside,min. This represents the minimum Hamming distance of the set of indexes of one description, when the index of the other description is fixed. We prove the close connection between the problem of robust permutations design under the new criterion and the anti-bandwidth problem in a certain graph derived from a hypercube. Leveraging this connection, we settle the problem of existence of permutations achieving dside,min≥ 2, respectively dmin≥ 2, and show their construction. Further, we develop a technique for constructing linear permutation pairs achieving dside,min≥ h based on linear (R, ⌈log2 m⌉) channel codes of minimum Hamming distance h + 1. In addition, tight bounds in terms of R, on the maximum achievable value of dside,minare derived for m = 2, 3, 4.

A polar coding scheme is proposed for the multiple description coding (MDC) problem and is shown to be able to achieve a certain rate pair on the dominant line of the achievable rate region determined by El Gamal and Cover. This scheme is an adaptation of the one developed by ŗaşoğlu et al. for the multiple access channel (MAC) to the MDC setting. The analysis of the proposed scheme contains two new ingredients: 1) a certain MDC-MAC duality and 2) an auxiliary random process that involves both the mutual information and the Bhattacharyya parameter. The decorrelation effect of the polar transform is also investigated.

In previous work on multiple description lattice vector quantizers (MDLVQ) with L ≥ 3 descriptions, once the central and side lattice codebooks are fixed, the decoding quality is determined for all numbers k of received descriptions. Therefore, it is not possible to achieve tradeoffs between the quality of reconstruction for different values of k, 1 ≤ k ≤ L - 1. This work proposes a flexible MDLVQ capable of overcoming the above drawback. For this, a different reconstruction method is employed and a heuristic index assignment algorithm, which uses L - 2 parameters to control the distortions for 2 ≤ k ≤ L - 1, is developed. The second contribution of this work is a structured index assignment for the case L = 3 and the derivation of asymptotical expressions of the distortions at high resolution. The proposed index assignment has a simple mechanism for controlling the tradeoff between the reconstruction quality when k = 1 and when k = 2, and is able to achieve a wide range of distortion values.

A coding scheme based on polar codes is proposed for the multiple description problem. This scheme is an adaptation of the one developed by ŗaşoğlu et al. for the multiple access channel to the multiple description setting. Specifically, it is shown that the proposed scheme is able to achieve a certain rate pair on the dominant line of the achievable rate region determined by El Gamal and Cover. Due to the dependence between the descriptions, a complication arises in the performance analysis. To resolve this difficulty, a novel technique is introduced which converts dependent descriptions to independent descriptions without affecting the coding rates.

This work compares theoretically the performance of several representative practical multiple description (MD) frameworks with L ≥ 3 symmetric descriptions. The first scenario is the classic unequal erasure protection (UEP) scheme using a successively refinable code (SRC) and Reed-Solomon codes. The second scenario is an improvement upon UEP by applying domain partitioning and permuted Reed-Solomon codes. The third scenario uses a finer partitioning and erasure correction via repetition codes. Additionally, the MD lattice vector quantizer and another recent MD scheme are considered in the comparison. The aforementioned MD schemes are compared in terms of the expected squared error asymptotically achievable as the rate R of a description approaches ∞, assuming independent description losses. Our analysis reveals that the improvement of the second scenario upon the first one when R → ∞ can reach up to 1.68 dB, but it approaches 0 as the description loss rate p goes to 0 and L approaches ∞. Additionally, we find that the first two schemes outperform the third one with an unbounded gain when R → ∞, as p→ 0 or L → ∞. Further, we show that the first three scenarios achieve unbounded improvements over the other two as R → ∞ and p → 0. On the other hand, we point out that some of the results of our asymptotic analysis rely on strong assumptions and therefore an experimental validation is needed before applying them to practical situations.

In the previous work on multiple description lattice vector quantizers (MDLVQs) with L ≥ 3 descriptions, once the central and side lattice codebooks are fixed, the decoding quality is determined for all numbers k of received descriptions. Therefore, it is not possible to achieve tradeoffs between the quality of reconstruction for different values of k, 1 k ≤ L - 1. This paper proposes a flexible MDLVQ capable of overcoming the above drawback. For this, a different reconstruction method is employed and a heuristic index assignment (IA) algorithm, which uses L - 2 parameters to control the distortions for 2 k ≤ L - 1, is developed. Experimental results show that the proposed MDLVQ, in addition to achieving the desired tradeoffs, significantly outperforms the classic MD scheme based on unequal erasure protection. The second contribution of this paper is a structured IA for the case of L = 3 and the derivation of the corresponding expressions of the distortions at high resolution. The proposed IA has a simple mechanism for controlling the tradeoff between the reconstruction quality for k = 1, 2. The IA is able to achieve a wide range of distortion values, while keeping the product of the distortions for k = 1, 2 the same as in the prior work.

In many scientific, medical and defense applications of image/video compression, an ℓ∞error bound is required. However, pure ℓ∞-optimized image coding, colloquially known as near-lossless image coding, is prone to structured errors such as contours and speckles if the bit rate is not sufficiently high; moreover, previous ℓ∞-based image coding methods suffer from poor rate control. In contrast, the ℓ2error metric aims for average fidelity and hence preserves the subtlety of smooth waveforms better than the ℓ∞error metric and it offers fine granularity in rate control; but pure ℓ2-based image coding methods (e.g., JPEG 2000) cannot bound individual errors as the ℓ∞-based methods can. This paper presents a new compression approach to retain the benefits and circumvent the pitfalls of the two error metrics.

This work addresses the problem of increasing the robustness to bit errors for two description scalar quantizers. To this aim a permutation is applied to the indices of each description. We show how to construct permutation pairs that increase the minimum Hamming distance of the set of valid index pairs to 3 when the redundancy is sufficiently high. Additionally, for the case when one description is known to be correct we propose a new performance criterion, denoted by dside,min. This represents the minimum Hamming distance of the set of valid indices of one description, when the index of the other description is fixed. We develop a technique for constructing permutation pairs achieving dside,min≥ h based on a linear (R, [log2m]) channel code of minimum Hamming distance h + 1, where R is the rate of each description and m is the number of diagonals occupied by the valid index pairs in the matrix of the initial index assignment.

In many scientific, medical, and defense applications of image/video compression, an [Symbol: see text]∞ error bound is required. However, pure[Symbol: see text]∞-optimized image coding, colloquially known as near-lossless image coding, is prone to structured errors such as contours and speckles if the bit rate is not sufficiently high; moreover, most of the previous [Symbol: see text]∞-based image coding methods suffer from poor rate control. In contrast, the [Symbol: see text]2 error metric aims for average fidelity and hence preserves the subtlety of smooth waveforms better than the ∞ error metric and it offers fine granularity in rate control, but pure [Symbol: see text]2-based image coding methods (e.g., JPEG 2000) cannot bound individual errors as the [Symbol: see text]∞-based methods can. This paper presents a new compression approach to retain the benefits and circumvent the pitfalls of the two error metrics. A common approach of near-lossless image coding is to embed into a DPCM prediction loop a uniform scalar quantizer of residual errors. The said uniform scalar quantizer is replaced, in the proposed new approach, by a set of context-based [Symbol: see text]2-optimized quantizers. The optimization criterion is to minimize a weighted sum of the [Symbol: see text]2 distortion and the entropy while maintaining a strict [Symbol: see text]∞ error bound. The resulting method obtains good rate-distortion performance in both [Symbol: see text]2 and [Symbol: see text]∞ metrics and also increases the rate granularity. Compared with JPEG 2000, the new method not only guarantees lower [Symbol: see text]∞ error for all bit rates, but also it achieves higher PSNR for relatively high bit rates.

In this paper, a novel concept called a uniquely factorable constellation pair (UFCP) is proposed for the systematic design of a noncoherent full diversity collaborative unitary space-time block code by normalizing two Alamouti codes for a wireless communication system having two transmitter antennas and a single receiver antenna. It is proved that such a unitary UFCP code assures the unique identification of both channel coefficients and transmitted signals in a noise-free case as well as full diversity for the noncoherent maximum likelihood receiver in a noise case. To further improve error performance, an optimal unitary UFCP code is designed by appropriately and uniquely factorizing a pair of energy-efficient cross quadrature amplitude modulation (QAM) constellations to maximize the coding gain subject to a transmission bit rate constraint. After a deep investigation of the fractional coding gain function, a technical approach developed in this paper to maximizing the coding gain is to carefully design an energy scale to compress the first three largest energy points in the corner of the QAM constellations in the denominator of the objective as well as carefully design a constellation triple forming two UFCPs, with one collaborating with the other two so as to make the accumulated minimum Euclidean distance along the two transmitter antennas in the numerator of the objective as large as possible, and at the same time, to avoid as many corner points of the QAM constellations with the largest energy as possible to achieve the minimum of the numerator. In other words, the optimal coding gain is attained by intelligent constellations collaboration and efficient energy compression. Computer simulations demonstrate that error performance of the optimal unitary UFCP code presented in this paper outperforms those of the differential code and the signal-to-noise-ratio-efficient training code.

It is shown that the coding problem for an arbitrary point on the dominant face of an L-description El Gamal-Cover (EGC) region can be converted to that for a vertex of a K-description EGC region for some K≤ 2L-1, where the latter problem can be solved via successive coding. A practical scheme is proposed for the quadratic Gaussian case by reducing each step in successive coding to a Gaussian quantization operation and implementing such an operation using low-density generator matrix codes. The effectiveness of this scheme is verified through extensive simulation experiments.

This work presents an LDGM-based practical successive coding scheme for the multiple description (MD) problem for finite alphabet sources. The scheme, which targets the Zhang-Berger (ZB) rate-distortion region, is shown to be asymptotically optimal with joint typicality encoding, while as a practical encoding solution a message passing algorithm is adopted. We further discuss in more detail the application of the coding scheme in three cases of the MD problem with the Hamming distortion measure: 1) no excess sum-rate for binary sources, 2) successive refinement, and 3) no excess marginal rate for the uniform binary source. In the no excess sum-rate case some progress is made in the characterization of fundamental limits by deriving the analytical expression of the distortion region for general binary sources, and of the auxiliary variables needed to achieve its boundary. The exact expression of the Zhang-Berger upper bound to the central distortion is also provided for the case of no excess marginal rate for the uniform binary source. The proposed LDGM-based coding scheme is tested in practice for all three aforementioned cases. The experimental results show very good performance, demonstrating its ability to approach the theoretical rate-distortion limits or the available upper bounds.

This paper addresses the rate-distortion (R-D) optimal packetization (RDOP) of embedded bitstreams into independent source packets, in order to limit error propagation in transmission of images over packet noisy channels. The input embedded stream is assumed to be an interleaving of K independently decodable basic streams. To form independent source packets, the set of basic streams is partitioned into N groups. The streams within each group are then interleaved to generate a source packet. Error/erasure protection may be further applied along/across source packets, to produce the channel packets to be transmitted. The RDOP problem previously formulated by Wu et at. has the goal of finding the partitioning that minimizes the distortion when all source packets are decoded. We extend the problem formulation such that to also include the minimization of the expected distortion for general transmission scenarios that may apply uneven erasure/ error protection. Further, we show that the dynamic programming (DP) algorithm of Wu et al. can be extended to solve the general RDOP problem. The main contribution of this paper is a fast divide-and-conquer algorithm (D&C) to find the globally optimal solution, under the assumption that all basic streams have convex R-D curves. Instrumental in obtaining the fast solution is our result which proves that the problem can be formulated as a series of matrix search problems in totally monotone matrices. The proposed D&C reduces the running time from O(K(2)LN) where L is the size of each packet achieved by the DP solution to O(NKL log K). Experiments on SPIHT coded images demonstrate that the speedup is significant in practice.

This work addresses the rate-distortion (R-D) optimal packetization (OP) of embedded bitstreams into independent source packets, in order to limit error propagation in transmission over packet lossy channels. The input embedded stream is assumed to be an interleaving of K independently decodable basic streams. To form N independent source packets, each of L symbols, the set of basic streams is partitioned into N groups. The objective of R-D OP is to find the partitioning which minimizes the distortion when all packets are decoded. We present a fast divide and conquer algorithm to find the globally optimal solution, under the assumption that all basic streams have convex R-D curves. The proposed algorithm reduces the running time from O(K2(L + N)) achieved by the existing dynamic programming solution, to O(NKL log K). Experiments on SPIHT coded images show that the speed up is much higher than predicted theoretically, thus rendering the R-D OP feasible in practice.

The design of optimal multi-resolution scalar quantizers using the generalized Lloyd method was proposed by Brunk and Farvardin for the case of squared error distortion. Since the algorithm details heavily rely on the quadratic expression of the error function, its extension to general error functions faces some challenges, especially at the encoder optimization step. In this work we show how these challenges can be overcome for any convex difference distortion measure, under the assumption that all quantizer cells are convex (i.e., intervals), and present an efficient algorithm for optimal encoder partition computation. The proposed algorithm is faster than the algorithm used by Brunk and Farvardin. Moreover, it can also be applied to channel-optimized and to multiple description scalar quantizer design with squared error distortion, and it outperforms in speed the previous encoder optimization algorithms proposed for these problems.

Multirate multicast is a powerful methodology of multimedia communication in heterogenous networks. A variant of multirate multicast motivated by scalable multimedia streaming is layered multicast, where the transmitted signal is presented in successive data layers. With recent advances of network coding theory, many layered multicast schemes using network coding have been proposed to improve the performance of traditional routing-based layered multicast. They divide the network into different layers and construct a unirate multicast network code for each layer. However, these schemes do not perform network coding between data layers, and consequently cannot realize the full potential of network coding. In this paper, we propose a novel approach to layered multicast that allows network coding of data in different layers. This relaxation lends the proposed scheme greater flexibility in optimizing the data flow than previous layered solutions, and thus achieves higher throughput.

In multiresolution coding a source sequence is encoded into a base layer and a refinement layer. The refinement layer, constructed using a conditional codebook, is in general not decodable without the correct reception of the base layer. By relating multiresolution coding with multiple description coding, we show that it is in fact possible to construct multiresolution codes in certain ways so that the refinement layer alone can be used to reconstruct the source to achieve a nontrivial distortion. As a consequence, one can improve the robustness of the existing multiresolution coding schemes without sacrificing the efficiency. Specifically, we obtain an explicit expression of the minimum distortion achievable by the refinement layer for arbitrary finite alphabet sources with Hamming distortion measure. Experimental results show that the information-theoretic limits can be approached using practical robust multiresolution coding schemes based on low-density generator matrix codes.

In multiresolution coding a source sequence is encoded into a base layer and a refinement layer. The refinement layer, constructed using a conditional codebook, is in general not decodable without the correct reception of the base layer. By relating multiresolution coding with multiple description coding, we show that it is in fact possible to construct multiresolution codes in certain ways so that the refinement layer alone can be used to reconstruct the source to achieve a nontrivial distortion. As a consequence, one can improve the robustness of the existing multiresolution coding schemes without sacrificing the efficiency. Specifically, we obtain an explicit expression of the minimum distortion achievable by the refinement layer for arbitrary finite alphabet sources with Hamming distortion measure. Experimental results show that the information-theoretic limits can be approached using a practical robust multiresolution coding scheme based on low-density generator matrix codes.

This work addresses the problem of joint source-channel decoding of a Markov sequence which is first encoded by a source code, then encoded by a convolutional code, and sent through a noisy memoryless channel. It is shown that for Markov sources satisfying the so-called Monge property, both the maximum a posteriori probability (MAP) sequence decoding, as well as the soft output Max-Log-MAP decoding can be accelerated by a factor of K without compromising the optimality, where K is the size of the Markov source alphabet. The key to achieve a higher decoding speed is a convenient organization of computations at the decoder combined with a fast matrix search technique enabled by the Monge property. The same decrease in complexity follows, as a by-product of the development, for the soft output Max-Log-MAP joint source channel decoding in the case when the convolutional coder is absent, result which was not known previously.

This paper presents a novel unequal erasure protection (UEP) strategy for the transmission of scalable data, formed by interleaving independently decodable and scalable streams, over packet erasure networks. The technique, termed multistream UEP (M-UEP), differs from the traditional UEP strategy by: 1) placing separate streams in separate packets to establish independence and 2) using permuted systematic Reed-Solomon codes to enhance the distribution of message symbols amongst the packets. M-UEP improves upon UEP by ensuring that all received source symbols are decoded. The R-D optimal redundancy allocation problem for M-UEP is formulated and its globally optimal solution is shown to have a time complexity of O(2(N)N(L+1)(N+1)) , where N is the number of packets and L is the packet length. To address the high complexity of the globally optimal solution, an efficient suboptimal algorithm is proposed which runs in O(N(2)L(2)) time. The proposed M-UEP algorithm is applied on SPIHT coded images in conjunction with an appropriate grouping of wavelet coefficients into streams. The experimental results reveal that M-UEP consistently outperforms the traditional UEP reaching peak improvements of 0.6 dB. Moreover, our tests show that M-UEP is more robust than UEP in adverse channel conditions.

Multirate multicast is a powerful methodology of multimedia communication in heterogenous networks. A variant of multirate multicast motivated by scalable multimedia streaming is layered multicast, where the transmitted signal is presented in successive data layers. With recent advances of network coding theory, many layered multicast schemes using network coding have been proposed to improve the performance of traditional routing based layered multicast. They divide the network into different layers and construct a unirate multicast network code for each layer. However, these schemes do not perform network coding between data layers, and consequently cannot realize the full potential of network coding. In this paper, we propose a novel approach to layered multicast that allows network coding of data in different layers. This relaxation lends the proposed scheme greater flexibility in optimizing the data flow than previous layered solutions, and thus achieves higher throughput.

Efficient delivery scheme for multimedia content is critical for the quality of various multimedia network services. It has been shown that the joint design of the source coding techniques and network communication strategies for multimedia streaming can outperform the traditional separate design in a rate-distortion measure. In this paper, we show that current joint design framework in which a data flow optimization followed by a balanced multiple description coding (MDC) can be further improved by allowing more general MDC techniques. A new general MDC construction algorithm is proposed, and the simulation results show a significant performance improvement over the previous balanced MDC based algorithm.

In order to prove a key result for their development (Lemma 2), Taubman and Thie need the assumption that the upper boundary of the convex hull of the channel coding probability-redundancy characteristic is sufficiently dense. Since a floor value for the density level for which the claim to hold is not specified, it is not clear whether their lemma applies to practical situations. In this correspondence, we show that the constraint of sufficient density can be removed, and, thus, we validate the conclusion of the lemma for any scenario encountered in practice.

It is known that the generalized Lloyd method is applicable to locally optimal multiple description scalar quantizer (MDSQ) design. However, it remains unsettled when the resulting MDSQ is also globally optimal. We partially answer the above question by proving that for a fixed index assignment there is a unique locally optimal fixed-rate MDSQ of convex cells under Trushkin's sufficient conditions for the uniqueness of locally optimal fixed-rate single description scalar quantizer. This result holds for fixed-rate multiresolution scalar quantizer (MRSQ) of convex cells as well. Thus, the well-known log-concave probability density function (pdf) condition can be extended to the multiple description and multiresolution cases.

The design of optimal multiple description scalar quantizers was pioneered by Vaishampayan with a generalization of Lloyd's algorithm, which alternatively optimizes the decoder, respectively the encoder, while the other component is fixed. We propose an algorithm which speeds up the encoder optimization step from O(N^2) to O(N\log N) time complexity, where N is the number of cells in the central partition.

A method to produce balanced multiple descriptions (MD) of a source is by successively refinable quantization (SRQ) in conjunction with uneven erasure protection (UEP) (Goyal, 2001; and Tian and Hemami, 2004). This work proposes an improvement to this balanced MD coding framework. In order to generate L descriptions, the set of source samples is first partitioned into L subsets of equal size, then each subset is quantized separately. Further, interleaved systematic Reed Solomon codes of codelength L and decreasing strengths are applied across the streams output by the SRQs. The improvement over the previous UEP-based MD code is evaluated using the expected distortion of the source reconstruction at the decoder as a performance measure. For a Gaussian memory-less source, the asymptotical improvement in performance, as the rate and code block length approach infin, can attain as much as 1.68 dB (for L = 3 and very low probability of description loss), with a tendency to decrease as the number of descriptions and the rate of description loss increase. In the practical setting using scalar SRQ, small rates and small L, the observed improvement generally matches the asymptotical values.

Multirate multicast is a powerful methodology of multimedia communication in heterogenous networks. With recent advances of network coding theory, many multirate multicast techniques using network coding have been proposed and they hold promises of improving information multicast efficiency over the traditional application-layer multicast protocols. However, all these network coding based multirate multicast solutions adopted a layered coding technique and involves computationally expensive optimization to decide the amount of information transmitted in each multicast layer. In this paper, we propose a novel multirate multicast framework for lossy networks, which uses both the uneven erasure protection (UEP) technique and linear network codes. The new multicast framework not only simplifies the construction of the multicast codes, but also guarantees the strict fairness among clients of different bandwidths.

This paper presents a novel uneven erasure-protection (UEP) strategy for scalable data formed by interleaving independently decodable and scalable sub-streams. The main differences between UEP and the proposed novel strategy are: 1) the placement of separate sub-streams in separate packets to establish independence and 2) the use of permuted systematic Reed-Solomon (RS) codes to enhance the distribution of message symbols amongst the packets. To maximize the performance of this transmission scheme, we optimize the erasure protection assignment in a rate-distortion sense. Our experiments demonstrate the net superiority of the new UEP strategy over the traditional UEP for moderate numbers of packets (up to 42). Peak performance improvements (0.3-0.7 dB) occur between 4-10 packets for various transmission rates and packet erasure rates.

We investigate the complexity of joint source- channel maximum a posteriori (MAP) decoding of a Markov sequence which is first encoded by a source code, then encoded by a convolutional code, and sent through a noisy memoryless channel. As established previously the MAP decoding can be performed by a Viterbi-like algorithm on a trellis whose states are triples of the states of the Markov source, source coder and convolutional coder. The large size of the product space (in the order of K2N, where K is the number of source symbols and N is the number of states of the convolutional coder) appears to prohibit such a scheme. We show that for finite impulse response convolutional codes, the state space size of joint source-channel decoding can be reduced to O(K2+N log N), hence the decoding time becomes O(TK2+TN log N), where T is the length in bits of the decoded bitstream. We further prove that an additional complexity reduction can be achieved when K > N, if the logarithm of the source transition probabilities satisfy the so- called Monge property. This decrease becomes more significant as the tree structure of the source code is more unbalanced. The reduction factor ranges between O(K/N) (for a fixed-length source code) and O(K / log N) (for Golomb-Rice code).

In this paper, we study the problem of optimal design of balanced two-description fixed-rate scalar quantizer (2DSQ) under the constraint of convex codecells. Using a graph-based approach to model the problem, we show that the minimum expected distortion of the 2DSQ is a convex function of the number of codecells in the side quantizers. This property allows the problem to be solved by Lagrangian minimization for which the optimal Lagrangian multiplier exists. Given a trial multiplier, we exploit a monotonicity of the objective function, and develop a simple and fast dynamic programming technique to solve the parameterized problem. To further improve the algorithm efficiency, we propose an RD-guided search strategy to find the optimal Lagrangian multiplier. In our experiments on distributions of interest for signal compression applications the proposed algorithm improves the speed of the fastest algorithm so far, by a factor ofO(K/logK), whereKis the number of codecells in each side quantizer. We also assess the impact on the optimality of the convex codecell constraint. Using a published performance analysis of 2DSQ at high rates, we show that asymptotically this constraint does not preclude optimality forL2distortion measure, when channels have a higher than 0.12 loss rate.

we study algorithmic approaches for rate-fidelity optimal packetization of a single and multiple scalable source code streams with uneven erasure protection (UEP). A new algorithm is developed to obtain the globally optimal solution for scalable source codes of convex rate-fidelity function and for a wide class of erasure channels, including channels for which the probability of losing packets is monotonically nonincreasing in , and independent erasure channels with packet erasure rate smaller than 0.5. This is achieved at linear space complexity and near-linear time complexity in the transmission budget, representing significant improvement over the known globally optimal algorithm. When applied to SPIHT compressed images, the results of the proposed algorithm are virtually the same as the global optima. The above success is also extended to UEP packetization of multiple scalable code streams. We improve the existing algorithms in both speed and performance.

Summary form only given. A new approach to solving the optimal prefix-free coding problem for the case of binary encoding alphabet has been proposed. The new approach, however, is limited to the binary case because the techniques employed seemed not to extend to the r-ary case. This paper proves that, on the contrary, the approach can be generalized to the r-ary case as well, thus leading to an O(nc) time solution for general r

A new algorithm is presented for rate-fidelity optimal packetization of scalable source bit streams with uneven erasure protection. It provides the globally optimal solution for input sources of convex rate-fidelity function and for a wide class of erasure channels, including channels for which the probability of losing n packets is monotonically decreasing in n, and independent erasure channels with packet erasure rate smaller than 0.5. The time and space complexities of the new algorithm are both O(NL), where N is the number of packets and L is the packet payload size, comparing to the O(NL2) time and space complexities of the existing globally optimal solution. When applied to SPIHT compressed images, the results of the proposed algorithm are virtually the same as the globally optima

This research is motivated by the needs of robust streaming of vector graphics contents over the Internet, wireless and other lossy networks. We present a multiple description coding (MDC) technique for error resilient compression and transmission of 2D vector graphics contents. An object is coded into two or more so-called co-descriptors, which are transmitted in separate data packets and generally via different network routes from a server to a client. Each co-descriptor can autonomously provide an approximation of the input object, and it can collaborate with other co-descriptors, if also available at the decoder, to refine the approximation

Index assignment and maximum a posteriori (MAP) decoding are two well-known techniques for error-resilient multimedia communications. If the two techniques are used in tandem, how they interact with each other will greatly affect the system performance. An important problem in this regard is, which has seemingly evaded attention, the design of index assignment to achieve the best possible performance of joint source-channel MAP decoding, given the source and channel statistics and given a distortion metric. In a first attempt on this design challenge, we pose the index assignment of a scalar quantizer for MAP decoding of Markov sequences coded by this quantizer as a quadratic programming problem. For Gaussian Markov sequences we derive a locally optimal index assignment by exploring some properties of the objective function. Experimental results show that the proposed scheme can find optimal or near-optimal solutions. The optimized index assignment can achieve much lower average symbol error rate than conventional schemes

We prove that Trushkin's (1982) sufficient conditions for the global optimality of a locally optimal fixed-rate scalar quantizer also ensure the global optimality of a locally optimal fixed-rate multiple description scalar quantizer of convex codecells, with respect to a fixed index assignment. This result also holds for the fixed-rate multiresolution scalar quantizer of convex codecells. As a consequence the well-known log-concave pdf condition can be extended to the multiple description and multiresolution case.

We study the problem of rate-distortion optimal packetization with uneven erasure protection (UEP) of scalable source sequence, into multiple groups of packets. The grouping of packets is needed when the length of the channel code, hence the number of packets, has to be modest for low decoding complexity. The problem was previously addressed in the literature but only locally optimal solution was proposed. We develop an algorithm for globally optimal solution and show that it has the same complexity as optimal UEP packetization into a single group of packets, i. e., quadratic in transmission budget.

We investigate the complexity of joint source-channel maximum a posteriori (MAP) decoding of a Markov sequence which is first encoded by a source code, then encoded by a convolutional code, and sent through a noisy memoryless channel. As established previously the MAP decoding can be performed by a Viterbi-like algorithm on a trellis whose states are triples of the states of the Markov source, the source coder and convolutional coder. The large size of the product space (in the order of K2N, where K is the number of source symbols and N is the number of states of the convolutional coder) appears to prohibit such a scheme. We show that in the case of finite impulse response convolutional codes the state space size can be reduced to O(K2+ NlogN), hence the decoding time becomes O(TK2+ TNlogN), where T is the length in bits of the decoded bitstream. We further show that an additional complexity reduction can be achieved when K > N, if the source satisfies a certain property, which is the case for a scalar quantized Gaussian-Markov source. This decrease becomes more significant as the tree structure of the source code is more unbalanced. The reduction factor ranges between O(K/N) (for a fixed-length source code) and O(K/logN) (for Golomb-Rice code)

Arguably, the most important and defining feature of the JPEG2000 image compression standard is its R-D optimized code stream of multiple progressive layers. This code stream is an interleaving of many scalable code streams of different sample blocks. In this paper, we reexamine the R-D optimality of JPEG2000 scalable code streams under an expected multirate distortion measure (EMRD), which is defined to be the average distortion weighted by a probability distribution of operational rates in a given range, rather than for one or few fixed rates. We prove that the JPEG2000 code stream constructed by embedded block coding of optimal truncation is almost optimal in the EMRD sense for uniform rate distribution function, even if the individual scalable code streams have nonconvex operational R-D curves. We also develop algorithms to optimize the JPEG2000 code stream for exponential and Laplacian rate distribution functions while maintaining compatibility with the JPEG2000 standard. Both of our analytical and experimental results lend strong support to JPEG2000 as a near-optimal scalable image codec in a fairly general setting.

New efficient algorithms are presented to design globally optimal two-description quantizers of fixed rate. The optimization objective is to minimize the expected distortion at the receiver side. We formulate the problem as one of shortest path in a directed acyclic graph. The fixed rate requirement puts constraints on the number and type of edges of the shortest path, which leads to an O(K/sub 1/K/sub 2/N/sup 3/) time design algorithm, where N is the cardinality of the source alphabet, and K/sub 1/, K/sub 2/ are the number of codecells, respectively, of the two side quantizers. This complexity is reduced to O(K/sub 1/K/sub 2/N/sup 2/) by exploiting a so-called Monge property of the objective function. Furthermore, if K/sub 1/=K/sub 2/=K and the two descriptions are subject to the same channel statistics, then the optimal description quantizer design problem can be solved in O(KN/sup 2/) time.

The problem of maximum a posterior probability (MAP) decoding of a Markov sequence that is variable length coded and transmitted over a binary symmetric channel (BSC) is considered. The number of source symbols in the sequence, if made known to the decoder, can improve MAP decoding performance. But adding a sequence length constraint to MAP decoding problem increases its complexity and also converts the length-constrained MAP decoding problem into one of maximum-weight k-link path in a weighted directed acyclic graph. The corresponding graph optimization problem can be solved by a fast parameterized search algorithm that finds either the exact solution with high probability or a good approximate solution otherwise. The proposed algorithm has lower complexity and superior performance than the previous heuristic algorithms.

We consider the problem of length-constrained maximum a posteriori (MAP) decoding of a Markov sequence that is variable length encoded and transmitted over a binary symmetric channel. We convert this problem into one of maximum-weight k-link path in a weighted directed acyclic graph. The induced graph optimization problem can be solved by a fast parameterized search algorithm that finds either the optimal solution with high probability or a good approximate solution otherwise. The proposed algorithm has lower complexity and superior performance than previous heuristic algorithms.

We develop an efficient Lagrangian-type algorithm for optimal two-description fixed-rate scalar quantizer design, for a very large class of distortion measures. Our key result is the discovery that the Lagrangian multiplier for the globally optimal solution exists. Although Lagrangian optimization is a method of choice for quantizer design, none of the previous algorithms using this method was shown to guarantee the global optimality for any instance of the problem

In this correspondence, we study algorithmic approach to solving the problem of maximum a posteriori (MAP) estimation of Markov sequences transmitted over noisy channels, which is also known as the MAP decoding problem. For the class of memoryless binary channels that produce independent substitution and erasure errors, the MAP sequence estimation problem can be formulated and solved as one of the longest path in a weighted directed acyclic graph. But for algorithm efficiency, we transform the graph problem to one of matrix search. If the underlying matrix is totally monotone, then the complexity of MAP sequence estimation can be greatly reduced. We give a sufficient condition for the matrix induced by MAP sequence estimation to be totally monotone, which is indeed the case if the input sequence is Gaussian Markov. Under this condition, the complexity of MAP decoding can be reduced from O(N/sup 2/M) to O(NM), where N is the size of source alphabet and M is the length of input sequence. Furthermore, for Markov sequences of fixed-length code we propose a block parsing strategy to reduce the complexity of MAP sequence estimation to O(M+N/sup 2/M/logM) or to O(M+NM/logM), depending on if the total monotonicity holds. Another significance of this correspondence lies in the applicability of the presented algorithmic approach, which has been thoroughly studied in computer science literature, to many other discrete optimization problems encountered in both source and channel coding, ranging from optimal multiresolution and multiple-description quantizer design, to context quantization for minimum conditional entropy, and to optimal packetization with uneven error protection.

In this paper, we present a family of new algorithms for rate-fidelity optimal packetization of scalable source bit streams with uneven error protection. In the most general setting where no assumption is made on the probability function of packet loss or on the rate-fidelity function of the scalable code stream, one of our algorithms can find the globally optimal solution to the problem in O(N/sup 2/L/sup 2/) time, compared to a previously obtained O(N/sup 3/L/sup 2/) complexity, where N is the number of packets and L is the packet payload size. If the rate-fidelity function of the input is convex, the time complexity can be reduced to O(NL/sup 2/) for a class of erasure channels, including channels for which the probability function of losing n packets is monotonically decreasing in n and independent erasure channels with packet erasure rate no larger than N/2(N + 1). Furthermore, our O(NL/sup 2/) algorithm for the convex case can be modified to rind an approximation solution for the general case. All of our algorithms do away with the expediency of fractional bit allocation, a limitation of some existing algorithms.

Summary form only given. The problem of multiplexing of several rate-distortion scalable multimedia code streams to be transmitted via a variable-rate channel is investigated. The aim is to minimize the expected distortion at the receiver, weighted by the probability distribution of the truncation point, P(l). Firstly, a very simple algorithm is presented which solves the problem in the case when the distribution of the truncation point is uniform or exponential. Secondly, the problem of constructing the optimal code stream is treated with the side information included. In order to reduce the amount of side information, a trade off between the optimal order of the /spl alpha/-atom strings described and a predefined order is proposed. Finally, a dynamic programming algorithm is presented to determine the optimal number of refinement stages. The time complexity of this algorithm is quadratic in the total number of /spl alpha/-atom strings.

Arguably the most important and defining feature of JPEG 2000 image compression standard is its R-D optimized code stream of multiple progressive layers. This code stream is an interleaving of many scalable code streams of different sample blocks. In this paper we investigate the algorithms of optimizing the interleaving to minimize the expected distortion weighted by the probability distribution of operational rates in a given range, rather than for one or few fixed rates. We prove that the JPEG 2000 code stream constructed by EBCOT (embedded block coding of optimal truncation) is indeed optimal for uniform rate distribution function even if the individual scalable code streams have non-convex operational R-D curves. We also develop algorithms to optimize the JPEG 2000 code stream for exponential and Laplacian rate distribution functions.

In this extended abstract we present a family of new algorithms for rate-fidelity optimal packetization of scalable source bit stream with uneven error protection. In the most general setting where no assumption is made on the probability function of packet loss or on the rate-fidelity function of the scalable code stream, one of our algorithms can find the globally optimal solution to the problem in O(N/sup 2/L/sup 2/) time, compared to a previously claimed O(N/sup 3/L/sup 2/) complexity, where N is the number of packets and L is the packet payload size. The time complexity can be reduced to O(NL/sup 2/) if the rate-fidelity function of the input is convex and under the reasonable assumption that the probability function of packet loss is monotonically decreasing. In the convex case the algorithm of Mohr et al. (2000) has complexity O(N/sup 2/L log N). Furthermore, our O(NL/sup 2/) algorithm for the convex case can be modified to find an approximation solution for the general case that is better than the results of other algorithms in the prior literature. All of our algorithms do away with the expediency of fractional redundancy allocation, a limitation of some existing algorithms. To our best knowledge this work offers for the first time globally optimal solutions to the important problem of optimal UEP packetization.

Any scalar quantizer of 2/sup h/ bins, where h is a positive integer, can be structured by a balanced binary quantizer tree T of h levels. Any pruned subtree /spl tau/ of T corresponds to an operational rate R(/spl tau/) and distortion D(/spl tau/) pair. Denote by S/sub n/ the set of all pruned subtrees of n leaf nodes, 1/spl les/n/spl les/2/sup h/. We consider the problem of designing a 2/sup h/-bin scalar quantizer that minimizes the weighted average distortion D~=/spl Sigma//sub n=1//sup 2(h)/ D(/spl tau/)W(n), where W(n) is a weighting function in the size of pruned subtrees (or the resolution of the underlying quantizer). We present an O(hN/sup 3/) algorithm to solve the underlying optimization problem (N is the number of points of the histogram that represents the source probability mass function), and call the resulting quantizer optimal multi-resolution scalar quantizer in the sense that it minimizes a global distortion measure averaged over all quantization resolutions of T. Interestingly, a similar quantizer design problem studied by Brunk et al. (1996) is a special case of our formulation, and can thus be solved exactly and efficiently using our algorithm. Furthermore, we present an algorithm to generate a sequence of 2/sup h/ nested pruned subtrees of T, from the root of T to the entire tree T itself, which minimizes an expected distortion over a range of operational rates. The resulting nested pruned subtree sequence generates an optimized embedded (rate-distortion scalable) code stream with maximum granularity of 2/sup h/ quantization stages, as opposed to existing successively refinable quantizers, such as the popular bit-plane coding scheme, which offer only h stages.

We present an LSB steganalysis technique that can detect the existence of hidden messages that are randomly embedded in the least significant bits of natural continuous-tone images. The technique is inspired by the recent work of J. Fridrich et al. (see Proc. ACM Workshop on Multimedia and Security, p.27-30, 2001) and just like their work, it can also precisely measure the length of the embedded message, even when the hidden message is very short relative to the image size. The key to our success is the formation of some subsets of pixels whose cardinalities change with LSB embedding, and such changes can be precisely quantified under the assumption that the embedded bits are randomly scattered. Interestingly, our study on steganalysis of LSB embedding sheds light on the work of Fridrich et al. on the detection of LSB embedding, and offers an analytical proof of an observation made by them.

We present a new, principled steganalytic approach to estimate the length of messages, if any, hidden in the least significant bits of digitized continuous signals such as images and audio. Our estimates of LSB-embedded messages are based on some intrinsic statistical properties of sample pairs drawn from the signal. We also give bounds on the estimation errors. Furthermore, possible attacks on our new steganalytic approach and our countermeasures are also discussed.

We have investigated the problem of designing an optimal entropy-constrained multiresolution scalar quantizer under the criterion of minimizing the expected distortion weighted by the probability of transmission rate and for arbitrary probability mass function of signal amplitude. An O(LN/sup 3/) algorithm is proposed to solve the optimization problem, where L is the number of refinement stages, and N is the size of input symbol alphabet. The proposed algorithm is globally optimal, and furthermore, it is more general than its locally optimal predecessors in terms of quantizer structures.