Drawing on Merritt's divide-and-conquer sorting taxonomy [1], we model comparison-based sorting as an abstract class with a template method to perform the sort by relegating the splitting and joining of arrays to ...
详细信息
ISBN:
(纸本)1581133294
Drawing on Merritt's divide-and-conquer sorting taxonomy [1], we model comparison-based sorting as an abstract class with a template method to perform the sort by relegating the splitting and joining of arrays to its concrete subclasses. Comparison on objects is carried out via an abstract ordering strategy. This reduces code complexity and simplifies the analyses of the various concrete sorting algorithms. Performance measurements and visualizations can be added without modifying any code by utilizing the decorator design pattern. This object-oriented design not only provides the student a concrete way of unifying seemingly disparate sorting algorithms but also help him/her differentiate them at the proper level of abstraction.
Many MPEG-2 encoding applications are realtime;this implies that the video signal must be encoded with no significant lookahead. However, there exist non-real-time applications that do enable us to first analyze a vid...
详细信息
Many MPEG-2 encoding applications are realtime;this implies that the video signal must be encoded with no significant lookahead. However, there exist non-real-time applications that do enable us to first analyze a video sequence entirely, and, using the analysis results, to optimize a second encoding pass of the same data. One example of such an application is the digital video disk (DVD), which is designed to facilitate a variable-bit-rate (VBR) output stream. In that case, it is possible to let the MPEG-2 encoder produce a video sequence with a constant visual quality over time. This is in contrast to constant-bit-rate (CBR) systems, where the rate is constant but the visual quality Varies with the coding difficulty. This paper describes a two-pass encoding system that has as its objective to produce an optimized VER data stream in a second pass. In a first pass, the video sequence is encoded with CBR, while statistics concerning coding complexity are gathered. Next, the first-pass data is processed to prepare the control parameters for the second pass, which performs the actual VER compression. In this off-line processing stage, we determine the target number of bits for each picture in the sequence, such that we realize the VER objective. This means that the available bits are appropriately distributed over the different Video segments such that constant visual quality is obtained. To be able to quantify the constant visual quality, perceptual experiments are described and a practical model is fitted to them. Exceptional cases such as scene changes and fades are detected and dealt with appropriately. We also ensure that the second-pass compression process does not violate the decoder buffer boundaries. Finally, the encoding is performed again, but now under control of the processed first-pass data. During the running of this second pass, a run-time bit-production control mechanism monitors the accuracy and validity of the first-pass data, correcting errors in pr
VQ-BTC is a recent technique used in the coding of image data to combat edge degradation produced by vector quantisation (VQ) or block truncation coding (BTC). However, it has high encoding complexity and needs a larg...
详细信息
VQ-BTC is a recent technique used in the coding of image data to combat edge degradation produced by vector quantisation (VQ) or block truncation coding (BTC). However, it has high encoding complexity and needs a large amount of memory to store 31 codebooks at both the encoder and decoder. A modified VQ-BTC (MVQ-BTC) algorithm is presented which achieves a performance close to that of VQ-BTC, but needs only three codebooks, and requires less computation time than VQ-BTC.
The rate of increase of quantization complexity, as rate of quantization increases, is investigated under a Turing machine framework. It is shown that the problem of asymptotically optimal scalar quantization has poly...
详细信息
ISBN:
(纸本)0780344081
The rate of increase of quantization complexity, as rate of quantization increases, is investigated under a Turing machine framework. It is shown that the problem of asymptotically optimal scalar quantization has polynomial encoding complexity if the distribution function corresponding to the one-third power of the source density is polynomially computable with high probability.
作者：
Immink, KASLaboratory of Chromatography
DEPg.Fac.Quimica Universidad Nacional Autonoma de Mexico Circuito interior Cd Universitaria/CP 04510 Mexico D.F.Mexico
Runlength-limited (RLL) codes have found widespread usage in optical and magnetic recording products. Specifically, the RLL codes EFM and its successor, EFMPlus, are used in the Compact Disc (CD) and the Digital Versa...
详细信息
Runlength-limited (RLL) codes have found widespread usage in optical and magnetic recording products. Specifically, the RLL codes EFM and its successor, EFMPlus, are used in the Compact Disc (CD) and the Digital Versatile Disc (DVD), respectively. EFMPlus offers a 6% increase in storage capacity with respect to EFM. The work reports on the feasibility and limits of EFM-like codes that offer an even larger capacity. To this end, we will provide an overview of the various limiting factors, such as runlength constraint, dc-content, and code complexity, and outline their relative effect on the code rate. In the second part of the article we will show how the performance predicted by the tenets of information theory can be realized in practice. A worked example of a code whose rate is 7.5% larger than EFMPlus, namely a rate 256/476, (d = 2, k = 15) code, showing a 13 dB attenuation at f(b) = 10(-3), will be given to illustrate the theory.
This paper addresses the problem of encoder optimization in a macroblock-based multimode video compression system, An efficient solution is proposed in which, for a given image region, the optimum combination of macro...
详细信息
This paper addresses the problem of encoder optimization in a macroblock-based multimode video compression system, An efficient solution is proposed in which, for a given image region, the optimum combination of macroblock modes and the associated mode parameters are jointly selected so as to minimize the over;dl distortion for a given bit-rate budget, Conditions for optimizing the encoder operation are derived within a rate-constrained product code framework using a Lagrangian formulation, The instantaneous rate of the encoder is controlled by a single Lagrange multiplier that makes the method amenable to mobile wireless networks with time-varying capacity, When rate and distortion dependencies are introduced between adjacent blocks (as is the case when the motion vectors are differentially encoded and/or overlapped block motion compensation is employed), the ensuing encoder complexity is surmounted using dynamic programming. Due to the generic nature of the algorithm, it can be successfully applied to the problem of encoder control in numerous video coding standards, including H.261, MPEG-1, and MPEG-2, Moreover, the strategy is especially relevant for very low bit rate coding over wireless communication channels where the low dimensionality of the images associated with these bit rates makes real-time implementation very feasible, Accordingly, in this paper, the method is successfully applied to the emerging H.263 video coding standard with excellent results at rates as low as 8.0 Kb per second. Direct comparisons with the H.263 test model, TMN5, demonstrate that gains in peak signal-to-noise ratios (PSNR) are achievable over a wide range of rates.
Subband coding with vector quantization is addressed in this paper. Forming the data vectors from both between and within the subbands is considered. The former of these two schemes is referred to as interband coding ...
详细信息
Subband coding with vector quantization is addressed in this paper. Forming the data vectors from both between and within the subbands is considered. The former of these two schemes is referred to as interband coding and the latter as intraband coding. Interband coder design is relatively straightforward since the design of the single codebook involved follows readily from a representative set of interband data vectors. Intraband coder design is more complicated since it entails the selection of a vector dimension and a bit-rate for each subband. The main contribution of this work is an optimal methodology for intraband subband vector quantizer design. The problem formulation includes constraints on the bit-rate and the encoding complexity and is solved with nonlinear programming methods. Subband vector quantization image coding in conjunction with a human visual system model is thoroughly investigated. Results of a large number of experiments indicate that the optimal intraband coder yields superior results from quantitative as well as' subjective points of view than the interband coder for comparable bit-rates. This improvement becomes more pronounced as the computational complexity of the intraband encoder is allowed to increase.
The design of efficient multidimensional signal sets has gained importance with the development of coset codes. We derive a procedure to send r bits on M parallel channels. A decomposition of the best constellation in...
详细信息
The design of efficient multidimensional signal sets has gained importance with the development of coset codes. We derive a procedure to send r bits on M parallel channels. A decomposition of the best constellation in Z(M) + (1/2,..., 1/2) is given in terms of the cross-products of lower dimensional shells of points. The proposed scheme can be used with good known coset codes to provide an alternate method of coded modulation. Our results indicate that we can get good shaping gains for low encoder complexity. The method is also generalized for channels with unequal gains. We also find a significant performance advantage at fixed shaping gain, in certain cases, with respect to the recent Voronoi Constellations in terms of peak-to-average power and constellation expansion.
The performance and complexity of channel-optimized vector quantizers are studied for the Gauss-Markov source. Observations on the geometric structure of these quantizers are made, which have an important implication ...
详细信息
The performance and complexity of channel-optimized vector quantizers are studied for the Gauss-Markov source. Observations on the geometric structure of these quantizers are made, which have an important implication on the encoding complexity. For the squared-error distortion measure, it is shown that an operation equivalent to a Euclidean distance measurement with respect to an appropriately defined set of points (used to identify the encoding regions) can be used to perform the encoding. This implies that the encoding complexity is proportional to the number of encoding regions. It is then demonstrated that for very noisy channels and a heavily correlated source, when the codebook size is large, the number of encoding regions is considerably smaller than the codebook size-implying a reduction in encoding complexity.
暂无评论