Presented here is a description and analysis of the N-point sparse discrete cosine transform (SDCT), where N is a power of two, which retains all of the properties of the parent DCT such as linearity, energy compaction, and having a fast transform implementation, while allowing arbitrarily-many known zeros, i.e., masked elements, in the input. It has application to image and video compression in that arbitrarily shaped regions may be transformed by the two-dimensional (2D) SDCT with approximately the same resulting compression efficiency as the standard 2D DCT applied to square blocks. The solution is based on a systematic application of symmetry and additive symmetry to the input elements. The four- and eight-point solutions are presented first, with emphasis on development of a set of generating matrices, and finally a general N-point solution is described. The 8×8 SDCT was implemented in VP9 and as expected the transform was found to be perfect and also improved compression efficiency for video objects with a known mask.

In this paper we develop an effective method for arbitrary shape coding based on a four-point DCT. The improvements results from two sources: (1) an effective use of the DCT by efficiently inducing zero-valued transform coefficients, and (2) a novel method of ordering the coefficients allowing the decoder to skip the locations of induced zeros. The algorithm is low complexity, as it only requires only arithmetic and shifting operations in the encoder, and shifting and masking operations in the decoder. The performance is comparable to published techniques in the literature, with the added benefit of low complexity and good performance at both high and low bit rates.

Generally speaking, rate scalable video systems today are evaluated operationally, meaning that the algorithm is implemented and the rate-distortion performance is evaluated for an example set of inputs. However, in these cases it is difficult to separate the artifacts caused by the compression algorithm and data set with general trends associated with scalability. In this paper, we derive and evaluate theoretical rate-distortion performance bounds for both layered and continuously rate scalable video compression algorithms which use a single motion-compensated prediction (MCP) loop. These bounds are derived using rate-distortion theory based on an optimum mean-square error (MSE) quantizer, and are thus applicable to all methods of intraframe encoding which use MSE as a distortion measure. By specifying translatory motion and using an approximation of the predicted error frame power spectral density, it is possible to derive parametric versions of the rate-distortion functions which are based solely on the input power spectral density and the accuracy of the motion-compensated prediction. The theory is applicable to systems which allow prediction drift, such as the data-partitioning and SNR-scalability schemes in MPEG-2, as well as those with zero prediction drift such as fine granularity scalability MPEG-4. For systems which allow prediction drift we show that optimum motion compensation is a sufficient condition for stability of the decoding system.

In this paper, we analyze the efficiency of three signal-to-noise scalable strategies for video coders using single-loop motion-compensated prediction (MCP). In our analysis, we assume the video sequences have uniform and constant translational motion and we model MCP as a stochastic filter. We also assume an exponential model for the distortion-rate function of the intraframe coding. The analysis is divided into two parts: the steady-state analysis and the transient analysis. In the first part, only the steady-state response of the coders is taken into account, and, thus, this analysis allows us to asses approximately the efficiency of coders with long input sequences. The transitory analysis considers both the transient and the steady-state responses of the coders, which makes it appropriate to analyze coders using periodic intraframes or with short input sequences. To validate our analysis, theoretical results have been compared to results from encodings of real video sequences using the scalable adaptive motion compensated wavelet video coder. We show that our theoretical analysis effectively describes qualitatively the main trends of every video coding strategy.

In SNR-scalable motion compensated video coders, prediction drift is introduced when decoding below the rate at which the encoder loop operates. Prediction drift reduces the coding efficiency and changes the quality of the video over time which is very annoying visually. In this paper, we propose a rate allocation algorithm to reduce these quality variations. By modeling both the video signal and the coder, we analyze the efficiency of the coder and find the rate allocation which creates frames which have the same distortion when decoded. We have compared numerical simulations of our algorithm with experimental results from real video encodings. The results show that by using a proper rate allocation algorithm quality fluctuations can be reduced.

In this paper, we present two rate allocation algorithms for embedded motion compensated video coders. The algorithms are based on the modeling of both the video signal and the coder which allow us to express the coding distortion with a recurrence equation. Our algorithms assign rates to the frames of each group of pictures (GOP) of a video sequence in an optimum way. In the first algorithm, the criterion is to minimize the average (MENAVE) distortion and in the second to achieve constant distortion (CD) in all frames. Numerical simulations show the MENAVE criterion can introduce large variations in quality with no significant gains in average distortion with respect to the CD criterion. We also show how the motion estimation accuracy and the GOP length influence in both strategies.

In this paper, we derive and evaluate theoretical rate-distortion performance bounds for scalable video compression algorithms which use a single motion-compensated prediction (MCP) loop. These bounds are derived using rate-distortion theory based on an optimum mean-square error (MSE) quantizer. By specifying translatory motion and using an approximation of the predicted error frame power spectral density, it is possible to derive parametric versions of the rate-distortion functions which are based solely on the input power spectral density and the accuracy of the motion-compensated prediction. The theory is applicable to systems which allow prediction drift, such as the SNR-scalability in MPEG-2, as well as those with zero prediction drift such as the MPEG-4 fine grained scalable standard.

In this paper, an analysis of the efficiency of three signal-to-noise ratio (SNR) scalable strategies for motion compensated video coders and their non-scalable counterpart is presented. After assuming some models and hypotheses with respect to the signals and systems involved, we have obtained the SNR of each coding strategy as a function of the decoding rate. To validate our analysis, we have compared our theoretical results with data from encodings of real video sequences. Results show that our analysis describes qualitatively the performance of each scalable strategy, and therefore, it can be useful to understand main features of each scalable technique and what factors influence their efficiency.

Leaky prediction layered video coding (LPLC) partially includes the enhancement layer in the motion compensated prediction loop, by using a leaky factor between 0 and 1, to balance the coding efficiency and error resilience performance. In this paper, rate distortion functions are derived for LPLC from rate distortion theory. Closed form expressions are obtained for two scenarios of LPLC, one where the enhancement layer stays intact and the other where the enhancement layer suffers from data rate truncation. The rate distortion performance of LPLC is then evaluated with respect to different choices of the leaky factor, demonstrating that the theoretical analysis well conforms with the operational results.

In this paper, we present an analysis of the performance of three predictive fine granular SNR-scalable coders and compare them with their non-scalable version. In our study, we assume an exponential model for the quantization noise and the use of linear prediction. Coders efficiency is assessed through the signal-to-noise ratio as a function of rate (SNR(R)) and the mean SNR. Validity of our analysis is tested by comparing theoretical results with simulations of the encoding of realizations of first order autoregressive processes. Results show that the use of coders which tolerate some prediction drift provides better results than other conventional scalable schemes.

We present a new stochastic model for pixels in an edge-enhanced image. The model is robust because it allows for the possibilities of false and multiple edges, and may be efficiently estimated using a expectation-maximization technique with a minimum description length metric. The direct applicability of the model for the sequential edge linking algorithm is investigated.

We describe a multiresolution approach to edge detection using a sequential search algorithm. The use of a multiresolution image pyramid allows the integration of global edge information contained in lower resolutions to guide the sequential search at higher resolutions. As a consequence, the dependence on a priori knowledge of the image edges is greatly reduced. Estimating the sequential search parameters from lower resolution images provides for a more accurate and less costly search of edge paths in the image.

The problem inherent with any digital image (or digital video) system is the large amount of bandwidth required for transmission or storage. This has driven the research area of image compression to develop more complex algorithms that compress images to lower data rates with better fidelity. One approach that can be used to increase the execution speed of these complex algorithms is through the use of parallel processing. In this paper we address one aspect of the parallel implementation of the JPEG still image compression standard on the MasPar MP-1, a massively parallel SIMD computer. We develop a novel byte alignment algorithm used to efficiently output compressed data from the parallel system.>

We describe a project that integrates applications requirements, parallel algorithm design, models of parallel computing, and software tools in order to improve the ability of applications researchers in the fields of computer vision and image processing (CVIP) to realize the performance potential of high performance parallel computers. This objective is achieved by pursuing four directions of research: the development of efficient and practical scalable algorithms for fundamental CVIP problems; the implementation of realistic CVIP scenarios on high performance computers; the development of a scalable, architecture-independent parallel model and a metric for estimating the performance of an algorithm on an existing parallel machine; and the development of prototype software tools. In this paper we describe work in each of these areas.

In this paper, we present efficient parallel solutions for structural indexing-based object recognition on coarse-grained parallel machines. Based on the analysis using the C/sup 6/-model, the parallel algorithm proposed in this paper takes O(Sk/p) computation units and O(p/sup 3/2/) communication units on a p processor coarse-grained machine such that 1/spl les/p/spl les/S, whereas the sequential solution takes O(Sk). The proposed solution is implemented on the Intel Touchstone Delta and performance results are shown. For a scene consisting of 160 feature points, the recognition phase takes 258 ms on a 64 processor Delta when the model database contains 256 models. The sequential algorithm takes approximately 4 seconds on a single node of the Delta.