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.

A well-trained Convolutional Neural Network can easily be pruned without significant loss of performance. This is because of unnecessary overlap in the features captured by the network's filters. Innovations in network architecture such as skip/dense connections and inception units have mitigated this problem to some extent, but these improvements come with increased computation and memory requirements at run-time. We attempt to address this problem from another angle - not by changing the network structure but by altering the training method. We show that by temporarily pruning and then restoring a subset of the model's filters, and repeating this process cyclically, overlap in the learned features is reduced, producing improved generalization. We show that the existing model-pruning criteria are not optimal for selecting filters to prune in this context, and introduce inter-filter orthogonality as the ranking criteria to determine under-expressive filters. Our method is applicable both to vanilla convolutional networks and more complex modern architectures, and improves the performance across a variety of tasks, especially when applied to smaller networks.

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.

In this paper, we consider the edit distance with block moves, block copies and block deletions, which is shown to be NP-hard, and employ a simple left-to-right greedy sliding window algorithm that achieves a constant factor approximation ratio of 5. This is an improvement on the constant approximation of 12 presented by Ergun and Sahinalp (Ergün, F., Muthukrishnan, S., and Sahinalp, S. C. Comparing sequences with segment rearrangements. FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science), and is achieved by a proof that introduces two non-trivial kinds of substrings for different purposes, so recursive and non-recursive operations can be treated at the same time.

CNNs are poised to become integral parts of many critical systems. Despite their robustness to natural variations, image pixel values can be manipulated, via small, carefully crafted, imperceptible perturbations, to cause a model to misclassify images. We present an algorithm to process an image so that classification accuracy is significantly preserved in the presence of such adversarial manipulations. Image classifiers tend to be robust to natural noise, and adversarial attacks tend to be agnostic to object location. These observations motivate our strategy, which leverages model robustness to defend against adversarial perturbations by forcing the image to match natural image statistics. Our algorithm locally corrupts the image by redistributing pixel values via a process we term pixel deflection. A subsequent wavelet-based denoising operation softens this corruption, as well as some of the adversarial changes. We demonstrate experimentally that the combination of these techniques enables the effective recovery of the true class, against a variety of robust attacks. Our results compare favorably with current state-of-the-art defenses, without requiring retraining or modifying the CNN.

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 new tool to help students make use of video recordings of traditional chalkboard and whiteboard lectures. Our tool provides a compact summary of a chalkboard lecture in the form of a set of slides, and an interactive environment for electronic note-taking in real time while watching a lecture in class or during review. Key to the processing of a chalkboard video by our system is the removal of the lecturer from the video (now no longer present to occlude the board) and segmentation of the resulting video to produce a set of slides comprising a compact presentation of the content written on the board during the lecture. Our method enhances learning in a number of ways. Students can focus on taking notes to supplement the material, rather than rote transcription. In addition, notes are aligned temporally with the lecture video and thus provide a useful way for students to index into the important parts of the video. Our system can be easily integrated into courses with a recorded lecture video component to help students organize their notes and quickly navigate the lectures from a given course for particular topics.

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 address the problem of retrieving the silhouettes of objects from a database of shapes with a translation and rotation invariant feature extractor. We retrieve silhouettes by using a “soft” classification based on the Euclidean distance. Experiments show significant gains in retrieval accuracy over the existing literature. This work extends the use of our previously employed feature extractor and shows that the same descriptor can be used 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.

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. In this work, a feature extraction method is presented which employs a discrete Fourier transform in the polar space, followed by a dimensionality reduction. Selected features are then processed with vector quantization for the supervised segmentation of images into uniformly textured regions. Experiments performed on a standard test suite show that this method compares favorably to the state-of-the-art and improves over previously studied frequency-domain based methods.

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

We present algorithms for in-place differential file compression, where a target file T of size n is compressed with respect to a source file S of size m using no additional space in addition to the that used to replace S by T; that is, it is possible to encode using m + n + O(1) space and decode using MAX(m,n) + O(1) space (so that when decoding the source file is overwritten by the decompressed target file). From a theoretical point of view, an optimal solution (best possible compression) to this problem is known to be NP-hard, and in previous work we have presented a factor of 4 approximation (not in-place) algorithm based on a sliding window approach. Here we consider practical in-place algorithms based on sliding window compression where our focus is on decoding; that is, although in-place encoding is possible, we will allow O(m + n) space for the encoder so as to improve its speed and present very fast decoding with only MAX(m, n) + O(1) space. Although NP-hardness implies that these algorithms cannot always be optimal, the asymptotic optimality of sliding window methods along with their ability for constant-factor approximation is evidence that they should work well for this problem in practice. We introduce the IPSW algorithm (in-place sliding window) and present experiments that indicate that it compares favorably with traditional practical approaches, even those that do not decode in-place, while at the same time having low encoding complexity and extremely low decoding complexity. IPSW is most effective when S and T are reasonably well aligned (most large common substrings occur in approximately the same order). We also present a preprocessing step for string alignment that can be employed when the encoder determines significant gains will be achieved.

We present a new low-complexity algorithm for hyperspectral image compression that uses linear prediction in the spectral domain. We introduce a simple heuristic to estimate the performance of the linear predictor from a pixel spatial context and a context modeling mechanism with one-band look-ahead capability, which improves the overall compression with marginal usage of additional memory. The proposed method is suitable to spacecraft on-board implementation, where limited hardware and low power consumption are key requirements. Finally, we present a least-squares optimized linear prediction technique that achieves better compression on data cubes acquired by the NASA JPL Airborne Visible/Infrared Imaging Spectrometer (AVIRIS).

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.

A novel design for a vector quantizer that uses multiple codebooks of variable dimensionality is proposed. High dimensional source vectors are first partitioned into two or more subvectors of (possibly) different length and then, each subvector is individually encoded with an appropriate codebook. Further redundancy is exploited by conditional entropy coding of the subvectors indices. This scheme allows practical quantization of high dimensional vectors in which each vector component is allowed to have different alphabet and distribution. This is typically the case of the pixels representing a hyperspectral image. We present experimental results in the lossless and near-lossless encoding of such images. The method can be easily adapted to lossy coding.

A novel design for a vector quantizer that uses multiple codebooks of variable dimensionality is proposed. High dimensional source vectors are first partitioned into two or more subvectors of (possibly) different length and then, each subvector is individually encoded with an appropriate codebook. Further redundancy is exploited by conditional entropy coding of the subvectors indices. This scheme allows practical quantization of high dimensional vectors in which each vector component is allowed to have different alphabet and distribution. This is typically the case of the pixels representing a hyperspectral image. We present experimental results in the lossless and near-lossless encoding of such images. The method can be easily adapted to lossy coding.

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.

In past years, there have been several improvements in lossless image compression. All the recently proposed state-of-the-art lossless image compressors can be roughly divided into two categories: single and double-pass compressors. Linear prediction is rarely used in the first category, while TMW, a state-of-the-art double-pass image compressor, relies on linear prediction for its performance. We propose a single-pass adaptive algorithm that uses context classification and multiple linear predictors, locally optimized on a pixel-by-pixel basis. Locality is also exploited in the entropy coding of the prediction error. The results we obtained on a test set of several standard images are encouraging. On the average, our ALPC obtains a compression ratio comparable to CALIC while improving on some images.

In earlier work, we presented the k-error protocol, a technique for protecting a dynamic dictionary lossless data compression method from error propagation as a result of errors in the communication channel or compressed file. In the worst case, the protocol only protects against k errors in total; however, it gives a very high probability protection against a sustained error rate. Here, we further develop this protocol and present experiments showing that in practice this approach is both fast and highly effective against a noisy channel or faulty storage medium. We also 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.

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.

Constantinescu and Storer (1994) introduced a single-pass vector quantization algorithm that with no specific training or prior knowledge of the data was able to achieve better compression results with respect to the JPEG standard, along with a number of computational advances such as: adjustable fidelity/compression tradeoff, precise guarantees on any l/spl times/l sub-block of the image, and fast table-lookup decoding. We improve that basic algorithm by blending it with the mean shape-gain vector quantization (MSGVQ) compression scheme. This blending allows a slightly better performance in terms of compression and a clear improvement in visual quality.

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).

The problem of communication and computation in the presence of errors is difficult, and general solutions can be time consuming and inflexible (particularly when implemented with a prescribed error detection/correction). A reasonable approach is to investigate reliable communication in carefully selected areas of fundamental interest where specific solutions may be more practical than general purpose techniques. In this paper, we study the problem of error-resilient communication and computation in a particularly challenging area, adaptive lossless data compression, where the devastating effect of error propagation is a long-standing open problem that was posed in the papers of Lempel and Ziv in the late 1970s. In fact, the non-error resilience of adaptive data compression has been a practical drawback of its use in many applications. Protocols that require the receiver to request retransmission from the sender when an error is detected can be impractical for many applications where such two-way communication is not possible or is self-defeating (e.g., with data compression, retransmission may be tantamount to losing the data that could have been transmitted in the mean time). In addition, bits of encoded data that are corrupted while data is in storage will in general not be recoverable and may corrupt the entire decompressed file. By error resilience, we mean that even though errors may not be detected, there are strong guarantees that their effects will not propagate. Our main result is a provable error-resilient adaptive lossless data-compression algorithm which nevertheless maintains optimal compression over the usual input distributions (e.g., stationary ergodic sources). We state our result in the context of a more general model that we call dynamic dictionary communication, where a sender and receiver work in a "lock-step" cooperation to maintain identical copies of a dictionary D that is constantly changing. For lossless data compression, the dictionary stores a set of strings that have been seen in the past and data is compressed by sending only indices of strings over the channel. Other applications of our model include robotics (e.g., remote terrain mapping) and computational learning theory.

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.

We derive a single-exponential time upper bound for finding the shortest path between two points in 3-dimensional Euclidean space with (nonnecessarily convex) polyhedral obstacles. Prior to this work, the best known algorithm required double-exponential time. Given that the problem is known to be PSPACE-hard, the bound we present is essentially the best (in the worst-case sense) that can reasonably be expected.

We present a practical algorithm for finding minimum-length paths between points in the Euclidean plane with (not necessarily convex) polygonal obstacles. Prior to this work, the best known algorithm for finding the shortest path between two points in the plane required Ω(n 2 log n) time and O (n 2 ) space, where n denotes the number of obstacle edges. Assuming that a triangulation or a Voronoi diagram for the obstacle space is provided with the input (if is not, either one can be precomputed in O ( n log n) time), we present an O(kn) time algorithm, where k denotes the number of “islands” (connected components) in the obstacle space. The algorithm uses only O(n) space and, given a source point s , produces an O(n) size data structure such that the distance between s and any other point x in the plane ( x ) is not necessarily an obstacle vertex or a point on an obstacle edge) can be computed in O (1) time. The algorithm can also be used to compute shortest paths for the movement of a disk (so that optimal movement for arbitrary objects can be computed to the accuracy of enclosing them with the smallest possible disk).

Motion Compensation is one of the most effective techniques used in interframe data compression. In this paper we present a parallel block-matching algorithm for estimating interframe displacement of blocks with minimum error. The algorithm is designed for a simple parallel architecture to process video in real time. The blocks may have variable size and shape 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. This segmentation identifies the part of the frame "active" with respect to the previous frame and preserves some of the spatial correlation between blocks.>

Constantinescu and Storer presented a new single-pass adaptive vector quantization algorithm that learns a codebook of variable size and shape entries; they presented experiments on a set of test images showing that with no training or prior knowledge of the data, for a given fidelity, the compression achieved typically equals or exceeds that of the JPEG standard. This paper presents improvements in speed (by employing K-D trees), simplicity of codebook entries, and visual quality with no loss in either the amount of compression or the SNR as compared to the original full-search version.>

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.>

The problem of movement in two-dimensional Euclidean space that is bounded by a (not necessarily convex) polygon is considered. Movement is restricted to be along straight line segments, and the objective is to minimize the number of bends or "turns" in a path. Most past work on this problem has addressed the movement between a source point and a destination point. An O(n \ast \log (n)) time algorithm is presented for computing a data structure that represents the minimal-turn paths from a source point to all other points in the polygon. An advantage of this algorithm is that it uses relatively simple data structures and is practical to implement. Another advantage is that it is easily generalized to accommodate the movement of a disk of radius r > 0.

Parallel algorithms for data compression by textual substitution that are suitable for VLSI implementation are studied. Both “static” and “dynamic” dictionary schemes are considered.

Abstract The problem of embedding an undirected graph on the planar grid is considered. Two common cost measures for this sort of problem are the area consumed by the embedding and the total length of edges in the embedding. This paper considers a third cost measure, called thenode cost measure, which is the total number of bends that are present along edges of the embedding. The node cost measure has applications to light or microwave circuits where it requires a separate device each time a corner is turned. In addition, this problem has limited applications to traditional circuit and VLSI layout. Although it is shown that finding a minimal node‐code embedding is in general an NP‐complete problem, three good approximation strategies are given along with worst‐case bounds on their performance; one of the strategies is shown to be nearly optimal for a large class of graphs.

A general model for data compression which includes most data compression systems in the fiterature as special cases is presented.Macro schemes are based on the principle of finding redundant strings or patterns and replacing them by pointers to a common copy.Different varieties of macro schemes may be defmed by specifying the meaning of a pointer; that is, a pointer may indicate a substring of the compressed string, a substring of the original string, or a substring of some other string such as an external dictionary.Other varieties of macro schemes may be defined by restricting the type of overlapping or recursion that may be used.Trade-offs between different varieties of macro schemes, exact lower bounds on the amount of compression obtainable, and the complexity of encoding and decoding are discussed, as well as how the work of other authors relates to this model.

The two major cost measures used in the past for grid embeddings are area (or the area of the smallest square or rectangle that contains the embedding) and total edge length. This paper is primarily concerned with a third measure, total number of nodes. To embed a graph on the planar grid, it may be necessary to “bend” edges. This can be modeled by allowing the insertion of nodes along edges of the graph and then insisting that the embedding may not bend edges.

For audio/communication/ image requirements a 16-bit floating point format provides a memory-efficient word size for representation and processing. Fixed-point is marginally suitable for representation (recording and reproduction) but has neither the uniformity of resolution nor the dynamic range needed for simple digital processing. An octal floating point format with 13-bit sign-mantissa and 3-bit exponent is shown to be an excellent one for both range and resolution.

A general model for data compression is presented which includes most data compression systems in the literature as special cases. All macro schemes are based on the principle of finding redundant strings or patterns and replacing them by pointers to a common copy. Different varieties of macro schemes may be defined by varying the interpretation of pointers, for instance, a pointer may indicate a substring of the compressed string, a substring of the original string, or a substring of some other string such as an external dictionary. Other varieties of macros schemes may be defined by restricting the type of overlapping or recursion that may be used. Trade-offs between different varieties of macro schemes, exact lower bounds on the amount of compression obtainable, and the complexity of encoding and decoding are discussed as well as how the work of other authors (such as Lempel-Ziv) relates to this model.