Many studies have indicated the importance of capturing scaling properties when modeling traffic loads; however, the influence of long-range dependence (LRD) and marginal statistics still remains on an unsure footing. In this paper, we study these two issues by introducing a multiscale traffic model and a novel multiscale approach to queuing analysis. The multifractal wavelet model (MWM) is a multiplicative, wavelet-based model that captures the positivity, LRD, and "spikiness" of non-Gaussian traffic. Using a binary tree, the model synthesizes an N-point data set with only O(N) computations. Leveraging the tree structure of the model, we derive a multiscale queuing analysis that provides a simple closed form approximation to the tail queue probability, valid for any given buffer size. The analysis is applicable not only to the MWM but to tree-based models in general, including fractional Gaussian noise. Simulated queuing experiments demonstrate the accuracy of the MWM for matching real data traces and the precision of our theoretical queuing formula. Thus, the MWM is useful not only for fast synthesis of data for simulation purposes but also for applications requiring accurate queuing formulas such as call admission control. Our results clearly indicate that the marginal distribution of traffic at different time-resolutions affects queuing and that a Gaussian assumption can lead to over-optimistic predictions of tail queue probability even when taking LRD into account.

In this paper, we develop a simple and powerful multiscale model for the synthesis of nonGaussian, long-range dependent (LRD) network traffic. Although wavelets effectively decorrelate LRD data, wavelet-based models have generally been restricted by a Gaussianity assumption that can be unrealistic for traffic. Using a multiplicative superstructure on top of the Haar wavelet transform, we exploit the decorrelating properties of wavelets while simultaneously capturing the positivity and "spikiness" of nonGaussian traffic. This leads to a swift O(N) algorithm for fitting and synthesizing N-point data sets. The resulting model belongs to the class of multifractal cascades, a set of processes with rich statistical properties. We elucidate our model's ability to capture the covariance structure of real data and then fit it to real traffic traces. Queueing experiments demonstrate the accuracy of the model for matching real data. Our results indicate that the nonGaussian nature of traffic has a significant effect on queuing.

We develop a new multiscale modeling framework for characterizing positive-valued data with long-range-dependent correlations (1/f noise). Using the Haar wavelet transform and a special multiplicative structure on the wavelet and scaling coefficients to ensure positive results, the model provides a rapid O(N) cascade algorithm for synthesizing N-point data sets. We study both the second-order and multifractal properties of the model, the latter after a tutorial overview of multifractal analysis. We derive a scheme for matching the model to real data observations and, to demonstrate its effectiveness, apply the model to network traffic synthesis. The flexibility and accuracy of the model and fitting procedure result in a close fit to the real data statistics (variance-time plots and moment scaling) and queuing behavior. Although for illustrative purposes we focus on applications in network traffic modeling, the multifractal wavelet model could be useful in a number of other areas involving positive data, including image processing, finance, and geophysics.

Wavelet-domain hidden Markov models (HMMs) are a potent new tool for modeling the statistical properties of wavelet transforms. In addition to characterizing the statistics of individual wavelet coefficients, HMMs capture the salient interactions between wavelet coefficients. However, as we model an increasing number of wavelet coefficient interactions, HMM-based signal processing becomes increasingly complicated. In this paper, we propose a new approach to HMMs based on the notion of context. By modeling wavelet coefficient inter-dependencies via contexts, we retain the approximation capabilities of HMMs, yet substantially reduce their complexity. To illustrate the power of this approach, we develop new algorithms for signal estimation and for efficient synthesis of nonGaussian, long-range-dependent network traffic.

Despite their widespread popularity, the JPEG and MPEG compression standards can lead to noticeable "blocking" artifacts-artifical rectangular discontinuities in the decoded image. Powerful postprocessing algorithms have been developed to remove blocking artifacts without destroying key image information. However, all but the simplest algorithms can be too complex for real-time applications such as video and still image decoding. We introduce a fast, easy-to-implement algorithm that removes blockiness by performing a simple nonlinear smoothing of pixels. This approach significantly improves visual quality and achieves subjective and objective (PSNR) gains that are competitive with the best deblocking algorithms reported in the literature at much reduced computational complexity.

Despite their widespread popularity, the Joint Photographers Expert Group (JPEG) and Motion Pictures Expert Group (MPEG) compression standards can lead to noticeable "blocking" artifacts-artificial rectangular discontinuities in the decoded image. Powerful postprocessing algorithms have been developed to remove blocking artifacts without destroying key image information. However, all but the simplest algorithms can be too complex for real-time applications such as video and still image decoding. We introduce a fast, easy-to-implement algorithm that removes blockiness by performing a simple nonlinear smoothing of pixels. This approach significantly improves visual quality and achieves subjective and objective (PSNR) gains that are competitive with the best deblocking algorithms reported in the literature at much reduced computational complexity.

Current wavelet-based statistical signal and image processing techniques such as shrinkage and filtering treat the wavelet coefficients as though they were statistically independent. This assumption is unrealistic; considering the statistical dependencies between wavelet coefficients can yield substantial performance improvements. We develop a new framework for wavelet-based signal processing that employs hidden Markov models to characterize the dependencies between wavelet coefficients. To illustrate the power of the new framework, we derive a new algorithm for signal estimation in nonGaussian noise.

Striving to maximize baseline (Joint Photographers Expert Group-JPEG) image quality without compromising compatibility of current JPEG decoders, we develop an image-adaptive JPEG encoding algorithm that jointly optimizes quantizer selection, coefficient "thresholding", and Huffman coding within a rate-distortion (R-D) framework. Practically speaking, our algorithm unifies two previous approaches to image-adaptive JPEG encoding: R-D optimized quantizer selection and R-D optimal thresholding. Conceptually speaking, our algorithm is a logical consequence of entropy-constrained vector quantization (ECVQ) design principles in the severely constrained instance of JPEG-compatible encoding. We explore both viewpoints: the practical, to concretely derive our algorithm, and the conceptual, to justify the claim that our algorithm approaches the best performance that a JPEG encoder can achieve. This performance includes significant objective peak signal-to-noise ratio (PSNR) improvement over previous work and at high rates gives results comparable to state-of-the-art image coders. For example, coding the Lena image at 1.0 b/pixel, our JPEG encoder achieves a PSNR performance of 39.6 dB that slightly exceeds the quoted PSNR results of Shapiro's wavelet-based zero-tree coder. Using a visually based distortion metric, we can achieve noticeable subjective improvement as well. Furthermore, our algorithm may be applied to other systems that use run-length encoding, including intraframe MPEG and subband or wavelet coding.

Previous works, including adaptive quantizer selection and adaptive coefficient thresholding, have addressed the optimization of a baseline-decodable JPEG coder in a rate-distortion (R-D) sense. In this work, by developing an entropy-constrained quantization framework, we show that these previous works do not fully realize the attainable coding gain, and then formulate a computationally efficient way that attempts to fully realize this gain for baseline-JPEG-decodable systems. Interestingly, we find that the gains obtained using the previous algorithms are almost additive. The framework involves viewing a scalar-quantized system with fixed quantizers as a special type of vector quantizer (VQ), and then to use techniques akin to entropy-constrained vector quantization (ECVQ) to optimize the system. In the JPEG case, a computationally efficient algorithm can be derived, without training, by jointly performing coefficient thresholding, quantizer selection, and Huffman table customization, all compatible with the baseline JPEG syntax. Our algorithm achieves significant R-D improvement over standard JPEG (about 2 dB for typical images) with performance comparable to that of more complex "state-of-the-art" coders. For example, for the Lenna image coded at 1.0 bits per pixel, our JPEG-compatible coder achieves a PSNR of 39.6 dB, which even slightly exceeds the published performance of Shapiro's wavelet coder. Although PSNR does not guarantee subjective performance, our algorithm can be applied with a flexible range of visually-based distortion metrics.

This paper introduces a novel, image-adaptive, encoding scheme for the baseline JPEG standard. In particular, coefficient thresholding, JPEG quantization matrix (Q-matrix) optimization, and adaptive Huffman entropy-coding are jointly performed to maximize coded still-image quality within the constraints of the baseline JPEG syntax. Adaptive JPEG coding has been addressed in earlier works: by Ramchandran and Vetterli (see IEEE Trans. on Image Processing, Special Issue on Image Compression, vol.3, p.700-704, September 1994), where fast rate-distortion (R-D) optimal coefficient thresholding was described, and by Wu and Gersho (see Proc. Inter. Conf. Acoustics, Speech and Signal Processing, vol.5, p.389-392, April 1993) and Hung and Meng (1991), where R-D optimized Q-matrix selection was performed. By formulating an algorithm which optimizes these two operations jointly, we have obtained performance comparable to more complex, "state-of-the-art" coding schemes: for the "Lenna" image at 1 bpp, our algorithm has achieved a PSNR of 39.6 dB. This result represents a gain of 1.7 dB over JPEG with a customized Huffman entropy coder, and even slightly exceeds the published performance of Shapiro's (see IEEE Trans. on Signal Processing, vol.41, p.3445-3462, December 1993) wavelet-based scheme. Furthermore, with the choice of appropriate visually-based error metrics, noticeable subjective improvement has been achieved as well.

This paper introduces a novel estimation scheme for reducing blocking artifacts in highly compressed, block-transformed images, such as those in JPEG or MPEG. We tackle the blockiness problem by performing constrained least squares (CLS) in the transform domain. Although the CLS approach has been addressed in previous work, we introduce a different approach with many desirable properties, including simple nonlinear processing to protect edges, efficient characterization of blockiness, and fast convergence. Using this new approach, we have obtained significant objective PSNR improvement over previous CLS work. Perceptually, we find significantly reduced blockiness by estimating only a few key transform coefficients per block, giving good visual quality with quick estimation.