Videocalling has become a popular form of communication in the world today, with many companies providing free services for it. However, there are still millions of people around the world that experience poor quality videocalls due to limitations in bandwidth. This despite, most people having the required hardware. In this paper we present a novel framework for enhancing highly compressed videocalls. We show, that with as little as 10 frames of the face, we can rapidly (in under 100 seconds) train a model to enhance that instance of the videocall. The model can be trained either prior to or during the call, enhancing the rest of the call by producing better quality video. The video conferencing application need not be modified - it can be off the shelf with our system as a layer on top that trains quickly then simply lets the video conferencing application (e.g. Zoom) run as usual, where our system intercepts and improves images before they are displayed. The model is designed to run in realtime on low-compute devices such as a typical laptop CPU. Experimentally, we show that the model significantly improves quality of compressed face video both quantitatively as well as perceptually. Code can be found at https://github.com/varun-jois/FSFVE.

We present a technique for very low rate encoding of videos with semantically salient foregrounds and dynamic background motion, such as an outdoor sports game. Our technique uses a MaskRCNN semantic segmentation neural network to separate video into foreground and background. Foreground is stored using a traditional video codec, along with a small semantic mask video which is upsampled during decoding. Missing regions of the background are filled using nearby frames, and the resulting video is stored using dynamic video motion sprites, a technique for good visual quality compression of dynamic backgrounds using static sprites, static vibration modes, and a small number of per-frame global motion parameters. By representing the backgrounds using static descriptors, our technique achieves higher visual background quality while preserving fidelity of important foreground regions. Our technique can target lower bitrates than may be appropriate for traditional codecs such as AVC and HEVC.

We present a method to extend the idea of sprite coding to videos containing a wide variety of naturally occurring background motion, which could potentially be incorporated into existing and future video standards. The existing MPEG-4 part 2 standard, now almost 20 years old, provides the ability to store objects in separate layers, and includes a sprite mode where the background layer is generated by cropping a still image based on frame-wide global motion parameters, but videos containing more general background motion cannot be effectively encoded with sprite mode. We propose a perceptually motivated lossy compression algorithm, where oscillatory background motion can be compactly encoded. Our model achieves a low bit rate by referencing a time-invariant representation of the optical flow with only a few added parameters per frame. At very low bit rates, our technique can provide dynamic backgrounds at a visual quality that may not be achievable by traditional methods which are known to produce unacceptable blocking and ringing artifacts.

As deep neural networks (DNNs) have been integrated into critical systems, several methods to attack these systems have been developed. These adversarial attacks make imperceptible modifications to an image that fool DNN classifiers. We present an adaptive JPEG encoder which defends against many of these attacks. Experimentally, we show that our method produces images with high visual quality while greatly reducing the potency of state-of- the-art attacks. Our algorithm requires only a modest increase in encoding time, produces a compressed image which can be decompressed by an off-the-shelf JPEG decoder, and classified by an unmodified classifier.

It has long been considered a significant problem to improve the visual quality of lossy image and video compression. Recent advances in computing power together with the availability of large training data sets has increased interest in the application of deep learning CNNs to address image recognition and image processing tasks. Here, we present a powerful CNN tailored to the specific task of semantic image understanding to achieve higher visual quality in lossy compression. A modest increase in complexity is incorporated to the encoder which allows a standard, off-the-shelf JPEG decoder to be used. While JPEG encoding may be optimized for generic images, the process is ultimately unaware of the specific content of the image to be compressed. Our technique makes JPEG content-aware by designing and training a model to identify multiple semantic regions in a given image. Unlike object detection techniques, our model does not require labeling of object positions and is able to identify objects in a single pass. We present a new CNN architecture directed specifically to image compression, which generates a map that highlights semantically-salient regions so that they can be encoded at higher quality as compared to background regions. By adding a complete set of features for every class, and then taking a threshold over the sum of all feature activations, we generate a map that highlights semantically-salient regions so that they can be encoded at a better quality compared to background regions. Experiments are presented on the Kodak PhotoCD dataset and the MIT Saliency Benchmark dataset, in which our algorithm achieves higher visual quality for the same compressed size while preserving PSNR.

We present a framework to recognize objects in images based on their silhouettes. In previous work we developed translation and rotation invariant classification algorithms for textures based on Fourier transforms in the polar space followed by dimensionality reduction. Here we present a new approach to recognizing shapes by following a similar classification step with a "soft" retrieval algorithm where the search of a shape database is based on the VQ centroids found by the classification step. Experiments presented on the MPEG-7 CE-Shape 1 database show significant gains in retrieval accuracy over previous work. An interesting aspect of this recognition algorithm is that the first phase of classification seems to be a powerful tool for both texture and shape recognition.

We present a new lower complexity approach for content based image retrieval based on a relative compressibility similarity measure using VQ codebooks employing feature vectors based on color and position. In previous work we have developed a system that employs feature vectors that are a combination of color and position. In this paper, we present a new approach that decouples color and position. We present this approach as two methods. The first trains separate codebooks for color and position features, eliminating the need for potentially application specific feature weightings during training. The second method achieves nearly the same performance at greatly reduced complexity by partitioning images into regions and training high-rate TSVQ codebooks for each region (i.e., position information is made implicit). Features extracted from query regions are encoded with the corresponding database region codebooks. The maximum number of codewords that a database region codebook may contain is determined at runtime and is a function of the query features. Region codebooks are then pruned appropriately before encoding query features. Experiments performed on the COREL image database show this new approach to provide almost equivalent retrieval precision to our previous method of jointly trained codebooks (and an improvement over previous methods) at much lower complexity.

Texture identification can be a key component in content based image retrieval systems. Although formal definitions of texture vary in the literature, it is commonly accepted that textures are naturally extracted and recognized as such by the human visual system, and that this analysis is performed in the frequency domain. The vast majority of the methods proposed in the literature provide good characterization of texture in controlled environments. In order to better describe textures, features must capture the nature of the texture, invariant to rotational, shift, and scale transformations. In this work, a rotation-invariant feature extraction technique is presented, extending our previous work (A. Di Lillo et al., 2007), which was not rotation-invariant. The technique demonstrated here similarly employs a discrete Fourier transform in the polar space followed by a dimensionality reduction, but achieves rotational invariance by incorporating an additional transform into the process. Selected features are then processed with vector quantization for the classification of textures. Experiments performed on a standard test suite show that this method improves over previous methods.

Texture identification can be a key component in CBIR (Content Based Image Recognition) systems. It can also be a tool for separation of video object planes in MPEG4 video compression systems. Although formal definitions of texture vary in the literature, it is commonly accepted that textures are naturally extracted and recognized as such by the human visual system, and that this analysis is performed in the frequency domain.

We present a low complexity approach for content-based image retrieval (CBIR) using vector quantization (VQ). The VQ codebooks serve as generative image models and are used to represent images while computing their similarity. The hope is that encoding an image with a codebook of a similar image will yield a better representation than when a codebook of a dissimilar image is used. Experiments performed on a color image database support this hypothesis, and retrieval based on this method compares well with previous work. Our basic method "tags" each image with a thumbnail and a small VQ codebook of only 8 entries, where each entry is a 6 element color feature vector. In addition, we consider augmenting feature vectors with x-y coordinates associated with the entry

In previous work we considered LPVQ, a compression algorithm based on locally optimal partitioned vector quantization that can be used to compress hyperspectral images by applying partitioned VQ to the spectral signatures (e.g., to the 224 16-bit values of a NASA AVIRIS pixel) and then encoding error information with a threshold that can be varied from high quality lossy to near lossless to lossless (e.g., 50-to-1 lossy, 10-to-1 near lossless, or 3-to-1 lossless). An advantage of LPVQ is extremely fast decoding (table lookup followed by entropy decoding), but it is at the cost of more complex encoding. Here we present a new low complexity algorithm for hyperspectral image compression, called SLSQ, that employs linear prediction targeted at spectral correlation followed by entropy coding of the prediction error. We then consider how SLSQ can be combined with LPVQ in a scenario commonly arising in practice. In this scenario, a low-complexity lossless encoder on the remote acquisition platform compresses the data for transmission to a central computing facility, where it is processed and re-coded using LPVQ, so that the compressed data can be distributed to the final users at various quality levels. The VQ indices of the LPVQ form a lossy compressed image of only about 2% of the original size; this small image can be employed to greatly reduce the time for browsing and classification.

We consider in-place differential file compression; that is, compressing a file T of size n with respect to an existing file S of size m, where decompression is in-place by overwriting S with T, using at most MAX(m,n)+O(1) space. In previous work we presented the IPSW algorithm (in-place sliding window). IPSW is fast and the compression achieved compares well with other existing methods, including those that are not in-place. IPSW is most effective when S and T are reasonably well aligned (most large common substrings occur in approximately the same order). Here we present a preprocessing step for string alignment that can be employed when the encoder determines significant gains will be achieved.

High dimensional source vectors, such as those that occur in hyperspectral imagery, are partitioned into a number of subvectors of different length and then each subvector is vector quantized (VQ) individually with an appropriate codebook. A locally adaptive partitioning algorithm is introduced that performs comparably in this application to a more expensive globally optimal one that employs dynamic programming. The VQ indices are entropy coded and used to condition the lossless or near-lossless coding of the residual error. Motivated by the need for maintaining uniform quality across all vector components, a percentage maximum absolute error distortion measure is employed. Experiments on the lossless and near-lossless compression of NASA AVIRIS images are presented. A key advantage of the approach is the use of independent small VQ codebooks that allow fast encoding and decoding.

Algorithms for in-place differential file compression were presented, where a target file of size n is compressed with respect to a source file of size m using no additional space; that is, the space for the source file is overwritten by the decompressed target file so that at no time is more than a total of MAX(m,n) space is used. From a theoretical point of view, an optimal solution (best possible compression) to this problem is known to be NP-hard. The constant-factor approximation algorithm is presented. Although NP-hardness implies that these algorithms cannot always be optimal, the asymptotic optimality for an information source of sliding window methods along with their ability for constant-factor approximation is evidence that they should work well for this problem in practice. The experiments indicate that these algorithms compare favorably with traditional approaches, even those that are not in-place, while at the same time having low encoding complexity and extremely low decoding complexity.

Constantinescu and Storer (1994) introduced an adaptive single-pass vector quantization algorithm (AVQ) that employs variable size and shaped codebook entries that are "learned" as an image is processed (no specific training or prior knowledge of the data is used). The approach allows the tradeoff between compression and fidelity to be continuously adjusted from lossless (with less compression) to highly lossy (with greater compression). Although practical performance compares favorably with the JPEG standard as well as standard trained vector quantization implementations, analysis of its performance appears difficult. A key aspect of AVQ is that matches are allowed to overlap, and it is not necessary to perform some sort of bin packing in order to cover the image with variable size and shape matches. Here we show that the AVQ approach is in some sense optimal asymptotically, module the overlapping factor which is defined to be the average number of times that a pixel is covered. We also present experiments that study the relationship of overlapping to performance.

We address the problem of improving the scene cut quality in fixed bit-rate real-time video decoding such as is used in the H.263 and MPEG standards. In low bandwidth applications, scene cuts can cause the bits required to encode a single frame to greatly exceed the target average bits per frame, and necessitate the skipping of other frames to provide sufficient time to transmit the scene cut frame. We present an optimal algorithm for minimizing the number of skipped frames and keep the decoding synchronized. Although the algorithm requires additional encoding complexity, there is no change in decoding complexity (in fact, no change to the decoder at all). Experimental results, obtained with a simplified strategy within the framework of H.263+ video encoding, confirm that the method provides an effective alternative to current frame skipping strategies. The overall quality in the presence of scene cuts is improved with respect the TMN-8 rate control. Although the overall bit rate benefits from our method, our focus is to improve the quality of the video where scene cuts occur (by reducing skipped frames and improving decoder synchronization). The approach here can be combined with more sophisticated rate controls, as, for example, the newer rate-distortion optimized TMN-10 and TMN-11.

The practical lossless digital image compressors that achieve the best results in terms of compression ratio are also simple and fast algorithms with low complexity both in terms of memory usage and running time. Surprisingly, the compression ratio achieved by these systems cannot be substantially improved even by using image-by-image optimization techniques or more sophisticate and complex algorithms. Meyer and Tischer (1998) were able, with their TMW, to improve some current best results (they do not report results for all test images) by using global optimization techniques and multiple blended linear predictors. Our investigation is directed to determine the effectiveness of an algorithm that uses multiple adaptive linear predictors, locally optimized on a pixel-by-pixel basis. The results we obtained on a test set of nine standard images are encouraging, where we improve over CALIC on some images.

Summary form only given. Constantinescu and Storer (1994) introduced an adaptive vector quantization algorithm (AVQ) that combines adaptive dictionary techniques with vector quantization (VQ). The algorithm typically equals or exceeds the compression of the JPEG standard on different classes of images and it often outperforms traditional trained VQ. We show how it is possible to improve AVQ on the class of images on which JPEG does best (i.e., "magazine photographs"). The improvement is possible by exploring the similarities in the dictionary built by AVQ. This is achieved by transforming the input vectors in a way similar to the one used in mean-shape-gain VQ (Oehler and Gray, 1993). In MSGVQ each vector x~/spl isin/R/sup n/ is decomposed as x~=g/spl middot/s~+E/sub x//spl middot/1~, where g=/spl par/x~-E/sub x//spl middot/1~/spl par/ and s~=(x~-E/sub x//spl middot/1~)/g; mean, gain and shapeare quantized separately. We apply this idea to AVQ, changing the match heuristic: letandbe respectively theof the dictionary block b and of the one anchored in p. The entry b is the best match if d(x~/sub p/,x/spl circ/)/spl les/T (x/spl circ/=g/sub p//spl middot/s~/sub b/+E/sub p//spl middot/1~) and its size is maximum. The tripleis entropy coded and sent to the decoder. This simple modification of the match heuristic allows AVQ to improve the compression ratio on many images. In some cases this improvement is as high as 60%. Along with the better compression results, there is also an improvement in the overall visual quality of the decoded image, especially at high compression rate.

The usual assumption for proofs of the optimality of lossless encoding is a stationary ergodic source. Dynamic sources with non-stationary probability distributions occur in many practical situations where the data source is constructed by a composition of distinct sources, for example, a document with multiple authors, a multimedia document, or the composition of distinct packets sent over a communication channel. There is a vast literature of adaptive methods used to tailor the compression to dynamic sources. However, little is known about optimal or near optimal methods for lossless compression of strings generated by sources that are not stationary ergodic. We present a number of asymptotically efficient algorithms that address, at least from the theoretical point of view, optimal lossless compression of dynamic sources. We assume the source produces an infinite sequence of concatenated finite strings generated by sampling a stationary ergodic source.

In earlier work we presented the k-error protocol, a technique for protecting a dynamic dictionary lossless compression method from error propagation as the result of errors on the communication channel or compressed file. Experiments showed that in practice this approach is both fast and highly effective against a noisy channel or faulty storage medium. This past work addressed dictionary-based methods where new strings are added over time. Here we address the issue of dynamically deleting strings. Although without modification most standard methods used in practice (e.g., LRU strategies) perform poorly with respect to error propagation, we propose and analyze some that are very robust, including a strategy based on leaf pruning.

In earlier work we presented the k-error protocol, a technique for protecting a dynamic dictionary method from error propagation as the result of any k errors on the communication channel or compressed file. Here we further develop this approach and provide experimental evidence that this approach is highly effective in practice against a noisy channel or faulty storage medium. That is, for LZ2-based methods that "blow up" as a result of a single error, with the protocol in place, high error rates (with far more than the k errors for which the protocol was previously designed) can be sustained with no error propagation (the only corrupted bytes decoded are those that are part of the string represented by a pointer that was corrupted).

Lossless image compression has traditionally employed techniques quite separate from those used for text compression or lossy image compression; most standards employ modeling followed by coding (e.g., the JBIG standard, the IBM Q-coder, CCITT Group 4). Constantinescu and Storer [1994] presented a lossy image compression scheme that can be viewed as a generalization of lossless dynamic dictionary compression ("LZ2" type methods) to two dimensions with approximate matching; Constantinescu and Storer [1995] have experimented with this approach for lossless image compression with great success. Here we generalize "LZ1" type methods to lossless image compression. We examine complexity issues and 2D implementations.

We consider sublinear massively parallel algorithms for compressing text with respect to a static dictionary. Algorithms for the PRAM model can do this optimally in O(m+log(n)) time with n processors, where m is the length of the longest entry in the dictionary and n is the length of the input string. We consider what is perhaps the most practical model of massively parallel computation imaginable: a linear array of processors where each processor is connected only to its left and right neighbors. We present an algorithm which in time O(km+mlog(m)) with n/(km) processors is guaranteed to be within a factor of (k+1)/k of optimal, for any integer k/spl ges/1. We also present experiments indicating that performance may be even better in practice.

A new image compression algorithm employs some of the most successful approaches to adaptive lossless compression to perform adaptive on-line (single pass) vector quantization. The authors have tested this algorithm with a host of standard test images (e.g. gray scale magazine images, medical images, space and scientific images, fingerprint images, and handwriting images) and with no prior knowledge of the data or training, for a given fidelity the compression achieved typically equals or exceeds that of the JPEG standard. The only information that must be specified in advance is the fidelity criterion.>

This paper considers optimal vector quantizers which minimize the expected distortion subject to a cost such as the number of leaves (storage cost), the leaf entropy (lossless encoding rate), the expected depth (average quantization time), or the maximum depth (maximum quantization time). It analyzes the heuristic of successive partitioning, and develops a class of strategies subsuming most of those used in the past. Experimental results show that these strategies are more efficient than existing methods, and achieve comparable or better compression. The relationship among different cost functions is considered and ways of combining multiple cost constraints are proposed.>

The authors study parallel algorithms for lossless data compression via textual substitution. Dynamic dictionary compression is known to be P-complete, however, if the dictionary is given in advance, they show that compression can be efficiently parallelized and a computational advantage is obtained when the dictionary has the prefix property. The approach can be generalized to the sliding window method where the dictionary is a window that passes continuously from left to right over the input string.>

Motion compensation is one of the most effective techniques used in interframe data compression. The authors present a parallel block-matching algorithm for estimating interframe displacement of small blocks with minimum error. The algorithm is designed for a grid architecture to process video in real time. The blocks may have variable size depending on a split-and-merge technique. The algorithm performs a segmentation of the image into regions (objects) moving in the same direction and uses this knowledge to improve the transmission of the displacement vectors.>

The authors analyze the approximate performance of tree search and provide tight upper bounds on the amount of error resulting from tree search and for a single input vector. These bounds are not encouraging but fortunately, the performance of tree-structured VQ in practice does not seem to be as bad. From the analysis, they derive a simple heuristic to improve the approximation of tree search. The strategy is to identify for each code vector some of its closest neighboring code vectors determined by the partition. After a code vector is found for an input vector by tree search, the closest neighboring code vectors are then searched for the best match. Unfortunately, the average number of neighboring code vectors of a given code vector can be as many as the total number of code vectors. Thus, the performance improvement of the strategy depends on the number of code vectors that are searched. Experimental results show that a number logarithmic in the size of the codebook provides significant performance gain while preserving the asymptotic search time complexity.>

Tree-structured vector quantization is a technique to represent a codebook that simplifies encoding as well as quantizer design. The authors define the notion of an optimal pruned tree subject to a cost constraint, and study the computational complexity of finding such a tree. Under the assumption that all trees are equally probable, it is shown that on average the number of pruned trees in a given tree is exponential in the number of leaves. Finding an optimal pruned tree subject to constraints such as entropy or the expected depth is NP-hard. However, when the constraint is the number of leaves, the problem can be solved in O(nk) time, where n is the size of the initial tree and k the constraint size. Experimental results for image compression show the performance of the optimal pruned tree to be comparable with that of full-search vector quantizers.>