Analytics-as-a-service is emerging as a key offering for cloud systems, however in the petascale regime, data transfer bottlenecks are a limiting factor. Often information has to be transmitted to the cloud by physical transportation. Efficient information representations that leverage the functional purpose of data for the analytics service to be offered can serve to ameliorate many of these information flow bottlenecks. In this paper, we provide an information-theoretic view on optimal information representations for big data analytics in the cloud. We also provide some structural design principles for building a petascale analytics appliance.

We develop algorithms to provide Quality of Service (QoS) support for prioritized, bandwidth-adaptive and fair media streaming using a multimedia server cluster. We formulate the underlying related problems of prioritized client admission control, redirection to appropriate streaming server, adaptive client quality control, and server load-balancing as one combined optimization. This optimization corresponds to solving a Multiple Choice Multiple Knapsack Problem, which is in general NP hard. By partitioning this optimization into two separate related optimizations we can design several low- complexity algorithms to provide exact and approximate solutions. We select a log-linear utility function that maintains differentiability and captures the video quality to measure the derived client and system benefit. We provide bounds on the performance of these algorithms, and examine the system time evolution in terms of the number of clients supported and QoS provided to each client, over realistic simulation scenarios.

This paper describes the enterprise multimedia streaming problem and highlights its requirements and specific issues. These issues are grouped into three broad areas: infrastructure, streaming and applications. This paper also presents an overview of current research in several diverse areas that is relevant to solutions for enterprise streaming, and highlight directions for further development. Thus, it is easy to generate interest in designing novel solutions and applications for enterprise streaming.

The H.264 video coding standard derives much of its compression efficiency gain from the use of multiple different macroblock prediction modes for macroblock coding. In general, finding the prediction mode which gives optimal R-D performance for a given macroblock requires the encoder to completely encode the macroblock using all possible prediction modes. This results in a significant increase in encoder computational complexity. In this paper, we present a mode selection framework for H.264 which uses learning theoretic classification algorithms to discern between broad mode classes, based on the evaluation of a simple set of macroblock features. We show that the proposed mode selection framework significantly reduces encoder computational complexity, at the cost of only a small loss in compression performance.

One-pass, variable bit-rate (VBR) rate control is ideally suited to the requirements of real-time video encoding for the purpose of digital storage. Previous MPEG one-pass VBR rate control algorithms have been based on appropriate selection of quantization scale parameters for controlling the bit rate and quality of the output bitstream. The major disadvantage of relying solely on quantization scales, for rate control, is the introduction of significant perceptual distortion when high quantization scales are used. We propose an MPEG-4, 1-pass, VBR rate control scheme that relies on the selective use of the MPEG-4 reduced resolution mode to supplement modulation of the quantization scale and provide an effective rate control strategy. Experimental results show that the proposed algorithm can encode high-complexity, standard definition (720 /spl times/ 480) video sequences at rates as low as 750 kbps without incurring significant perceptual artifacts.

We are concerned with multiple description coding of predictively encoded sequences at low rates/redundancies. The key problem to be solved is that of avoiding predictive mismatch. We propose an algorithm based on multiple description correlating transforms (MDCT), which avoids the problem of predictive mismatch while not increasing the number of transmitted coefficients. Under a general first-order, Gauss-Markov source model, carefully formulated to be applicable to the practically important case of video coding, we obtain closed-form expressions for the operational rate-distortion characteristics of the proposed algorithm and use these to optimize the algorithm encoding parameters. In the case of the residual-of-residuals technique, which is also based on MDCT, we show that incorporation of any redundancy between the transmitted descriptions is inherently suboptimal. Results show that the proposed algorithm significantly outperforms the residual-of-residuals technique at low rates.

One-pass variable bit rate (VBR) rate control is ideally suited to the requirements of real-time video encoding for the purpose of digital storage. Previous MPEG 1-pass VBR rate control algorithms have been based on appropriate selection of quantization scale parameters for controlling the bit rate and quality of the output bitstream. The major disadvantage of relying solely on quantization scales for rate-control is the introduction of significant perceptual distortion when high quantization scales are used. In this paper we propose an MPEG-4, 1-pass, VBR rate-control scheme that relies on selective use of the MPEG-4 reduced resolution mode to supplement modulation of the quantization scale and provide an effective rate control strategy. Experimental results show that the proposed algorithm effectively can encode high-complexity, standard definition (720/spl times/480) video sequences at rates as low as 750 kbps without incurring significant perceptual artifacts.

Given a high resolution compressed video stream this paper looks at the problem of extracting video from a small window at an arbitrary, but static location, in compressed form, without having to either decode the high resolution video stream or encode the window stream. Since state of the art video compression algorithms use motion compensation in one form or the other, the compressed video stream cannot be parsed to obtain the window stream without decoding the high resolution stream to some extent and subsequent re-encoding. On the other hand storing all possible windows as separate streams on the server is clearly infeasible, at least as of today, as it would lead to an explosion of the storage space requirement. It is shown that with a comparatively small increment in the server's storage requirement, it is possible to obtain compressed window streams out of the high resolution stream with minimal parsing, no decoding or re-encoding and little quality loss. Furthermore, methods to trade off the space required on the server with the compression efficiency of the window stream are shown. Experimental results obtained from applying the proposed method on MPEG-2 compressed video sequences are also provided.

Given a high resolution compressed video, we investigate the problem of simplifying the memory and computational requirements of the decoder, when the intended playback resolution is less than the encoded resolution. We show that significant savings can be obtained in the amount of temporary storage space used, memory bandwidth between the processor and local memory, and raw computational complexity, while not incurring a significant loss in perceptual quality. Most video compression standards make special adjustments to deal with interlaced video. We explore how the proposed solution adapts to these situations and suggest modifications which improve the quality of the reconstructed video. Results from using these algorithms on a number of test sequences compressed with the MPEG-2 standard are presented.

This paper is concerned with developing a lossless image compression method which employs an optimal amount of segmentation information to exploit spatial redundancies inherent in image data. Multiscale segmentation is obtained using a previously proposed transform which provides a tree-structured segmentation of the image into regions characterized by grayscale homogeneity. In the proposed algorithm we prune the tree to control the size and number of regions thus obtaining a rate-optimal balance between the overhead inherent in coding the segmented data and the coding gain that we derive from it. Another novelty of the proposed approach is that we use an image model comprising separate descriptions of pixels lying near the edges of a region and those lying in the interior. Results show that the proposed algorithm can provide performance comparable to the best available methods and 15-20% better compression when compared with the JPEG lossless compression standard for a wide range of images.

In this paper, we propose a novel segmentation based denoising algorithm. Segmentation yields intrinsically homogeneous and extrinsically heterogeneous regions. A denoising algorithm that uses Multiple Compaction Domains (MCD) is then applied on each of the resulting segments. Such a scheme retains important perceptual information in the segment boundaries while the denoising algorithm operates only on homogeneous segments. Further, the MCD algorithm is demonstrably superior to the classical denoising algorithms using transform domain thresholding. Our algorithm yields better perceptual quality and superior PSNR as compared to MATLAB's adaptive Wiener filter.

Discusses a multiscale segmentation based video compression algorithm aimed at very low bit-rate applications such as video teleconferencing and video phones. We introduce novel techniques for multiscale segmentation based motion compensation and residual coding. Our region based forward motion compensation strategy (in terms of direction of motion vector, which is from the previous frame to the current frame) regulates the size and number of regions used, by pruning a multiscale segmentation of video frames. Since regions used for motion compensation are obtained by segmenting the previously decoded frame, the shape of the regions need not be transmitted to the decoder. Furthermore, our hierarchical motion compensation strategy refines an initial region level, coarse motion field to obtain a dense motion field which provides pixel level motion vectors. The refinement procedure does not require any additional information to be transmitted. This motion compensation technique effectively addresses the problem of dealing with "holes" and "overlapping regions" which are inherent to forward motion compensation. Residual coding is performed using a novel method which exploits the fact that the energy of the residual resulting from motion compensation is concentrated in a priori predictable positions. We show that this residual coding technique can also be extrapolated to improve the performance of coders using a block based motion compensation strategy. A fusion of these concepts leads to a gain of 2-3 dB in peak signal-to-noise ratio, apart from significant perceptual improvement, over a generic video coding algorithm using a block based motion compensation strategy (such as H.261 or H.263) for a variety of test sequences.

We present a novel framework for denoising signals from their compact representation in multiple domains. Each domain captures, uniquely, certain signal characteristics better than others. We define confidence sets around data in each domain and find sparse estimates that lie in the intersection of these sets, using a POCS algorithm. Simulations demonstrate the superior nature of the reconstruction (both in terms of mean-square error and perceptual quality) in comparison to the adaptive Wiener filter.

A new method for digital image watermarking which does not require the original image for watermark detection is presented. Assuming that we are using a transform domain spread spectrum watermarking scheme, it is important to add the watermark in select coefficients with significant image energy in the transform domain in order to ensure non-erasability of the watermark. Previous methods, which did not use the original in the detection process, could not selectively add the watermark to the significant coefficients, since the locations of such selected coefficients can change due to image manipulations. Since watermark verification typically consists of a process of correlation which is extremely sensitive to the relative order in which the watermark coefficients are placed within the image, such changes in the location of the watermarked coefficients was unacceptable. We present a scheme which overcomes this problem of "order sensitivity". Advantages of the proposed method include (i) improved resistance to attacks on the watermark, (ii) implicit visual masking utilizing the time-frequency localization property of the wavelet transform and (iii) a robust definition for the threshold which validates the watermark. We present results comparing our method with previous techniques, which clearly validate our claims.

In the literature many strategies for attacking and subverting a watermark have been presented. Such attacks suggest that the ability to embed non-erasable watermarks does not necessarily imply that the watermarking scheme can be used to establish ownership. The main aim of this paper is to formulate necessary and sufficient requirements for a watermarking scheme to be able to resolve rightful ownership. It is shown that some of the popular schemes proposed in literature for watermarking images do not satisfy these requirements. Finally, we show that a modification of a watermarking scheme in literature (Piva et al., 1997) performs satisfactorily.

We present a novel improvement to existing schemes for abrupt shot change detection. Existing schemes declare a shot change whenever the frame to frame histogram difference (FFD) value is above a particular threshold. In such an approach, a high value for the threshold results in a small number of false alarms and a large number of missed detections while a low value for the threshold decreases the number of missed detections at the expense of increasing the false alarms. We attribute this situation to the fact that the FFD cannot be reliably used as the sole indicator for the presence of a shot change. In the proposed method a two-step shot detection strategy is used which selectively uses a likelihood ratio (computed directly from the frames and not from the histograms) to confirm the presence of a shot change. Such a two-step checking increases the probability of detection without increasing the probability of false alarm. The improvement proposed is simple and computationally cheap. Tests with a wide variety of video sequences prove the efficacy of the proposed approach.

In order to apply a multi-dimensional linear transform, over an arbitrarily shaped support, the usual practice is to fill out the support to a hypercube by zero padding. This does not however yield a satisfactory definition for transforms in two or more dimensions. The problem that we tackle is: how do we redefine the transform over an arbitrary shaped region suited to a given application? We present a novel iterative approach to define any multi-dimensional linear transform over an arbitrary shape given that we know its definition over a hypercube. The proposed solution is (1) extensible to all possible shapes of support (whether connected or unconnected) (2) adaptable to the needs of a particular application. We also present results for the Fourier transform, for a specific adaptation of the general definition of the transform which is suitable for compression or segmentation algorithms.

Popular techniques employed to code the displaced frame difference (DFD) treat it no differently from an ordinary image for coding purposes. Since the DFD is generated by the process of motion compensation, such methods do not fully exploit the underlying redundancies. This paper proposes a DFD coding method which exploits such redundancies while incurring negligible information overhead. The key idea is to predict locations of high DFD concentration which occupy small portions of the image and use this predicted information (which is also available to the decoder without additional information transmission) to improve the quality of the decoded image. Two key features of the proposed approach are its compatibility with any transform based DFD coding scheme and negligible information overhead. Tests with a fully functional video coder show the efficacy of the proposed approach.

This paper proposes a novel region-based video coding technique using a multiscale image segmentation method thus obtaining better quality at the same bit rate. In most of the previous region-based video coding techniques, occlusion caused degradation in terms of both the PSNR and perceptual video quality. We propose a new motion estimation and compensation algorithm which solves occlusion related problems effectively. The proposed motion estimation and compensation is a two stage procedure. The first stage uses a coarse motion model while the second stage uses a dense motion model. The coarse motion model generates region level motion vectors which are then fine tuned by the dense motion model which produces pixel level motion vectors. A fusion of these concepts leads to a gain of 2/spl sim/3 dB in PSNR over the block-based algorithm for a variety of test sequences using a fully functional video coder.

Reversible compression of images has been the topic of considerable research as it finds applications in many fields in which the deviation of the reproduced image from the original image is intolerable, however small be the deviation. This paper is concerned with the problem of reducing spatial redundancies in gray scale images, thus providing effective lossless compression, using segmentation information. We will present new edge models that deal effectively with two issues that make such models normally unsuitable for compression applications: local applicability and large number of parameters needed for representation. Segmentation information is provided by a recent transform (1993), which we found to possess qualities making it especially suitable for compression. The final residual image is obtained using autocorrelation-based 2-D linear prediction. Different implementations providing lossless compression are presented along with results over a number of common test images. Results show that the proposed approach can be used to yield robust lossless compression, while providing consistently and significantly better results than the best possible JPEG lossless coder.