This paper explores the modeling and exploitation of semi-local similarity in natural images to address the ill-posed nature of image interpolation. Our approach distinguishes itself from prior approaches by direct and careful use of semi-local similar patches to interpolate each individual patch. Our work uses a simple, parallelizable algorithm without the need to solve complicated optimization problems. Experimental results demonstrate that our interpolated images achieve significantly higher objective and subjective quality compared with those from state-of-the-art algorithms.

This paper combines spatially-variant filtering and non-local low-rank regularization (NLR) to exploit non-local similarity in natural images in addressing the problem of image interpolation. We propose to build a carefully designed spatially-variant, non-local filtering scheme to generate a reliable estimate of the interpolated image and utilize NLR to refine the estimation. Our work uses a simple, parallelizable algorithm without the need to solve complicated optimization problems. Experiment results demonstrate that our algorithm significantly improves PSNR and SSIM of the interpolated images compared with state-of-the-art algorithms.

This paper introduces a new approach for determining accurate locations of edges in natural images based on a location-directed image modeling framework. The inability to identify accurate locations follows from the inability to characterize the continuous location variation of edges. We exploit the linear phase-location characteristics in a complex-valued image representation, which guarantees even minuscule location variation be captured by changes in phases. In each band of complex-valued coefficients, the fields of phases represent the locations of edges with particular resolution and along particular direction, and thereby the representation offers a nonparametric framework for gathering multiresolution and multi-directional pieces of evidence about an edge's locations to jointly locate the edge. Our approach quantifies an edge's spatial shift that is less than 0.01 pixel and demonstrates its periodic movement within 0.35-pixel range in a series of natural images. This remarkable performance verifies our framework's ability in identifying accurate locations of edges and opens the door to unveil imperceptible phenomena that are not previously detected.

This paper explores the development and the use of a complex-valued, multi-resolution image representation to model and exploit local image structures in image-processing applications. Our approach distinguishes itself from prior approaches by constructing and exploiting the direct relationship between the locations of local structures and representation coefficients. Coefficients of our representation have magnitudes that measure the image energy within a specific region in both space and frequency, and phases that carry information about the distance of that energy from a local reference position. Our work proposes to model relationships, both across spatial regions and across different frequency bands, among the field of coefficient magnitudes, and among the field of coefficient phases. To illustrate the advantages of modeling these relationships, we present an algorithm for interpolating a natural image by a factor of two, both horizontally and vertically. Relationships among magnitudes and phases of available bands of coefficients are exploited to estimate local edge parameters (e.g. location, orientation, sharpness) that provide information about higher-frequency coefficients that are not available in the original image. Our work produces PSNR results that are competitive with state-of-the-art single image interpolation algorithms around edges and preserves both edge sharpness and contour smoothness.

In recent literature, there exist many high-performance wavelet coders that use different spatially adaptive coding techniques in order to exploit the spatial energy compaction property of the wavelet transform. Two crucial issues in adaptive methods are the level of flexibility and the coding efficiency achieved while modeling different image regions and allocating bitrate within the wavelet subbands. In this paper, we introduce the "spherical coder," which provides a new adaptive framework for handling these issues in a simple and effective manner. The coder uses local energy as a direct measure to differentiate between parts of the wavelet subband and to decide how to allocate the available bitrate. As local energy becomes available at finer resolutions, i.e., in smaller size windows, the coder automatically updates its decisions about how to spend the bitrate. We use a hierarchical set of variables to specify and code the local energy up to the highest resolution, i.e., the energy of individual wavelet coefficients. The overall scheme is nonredundant, meaning that the subband information is conveyed using this equivalent set of variables without the need for any side parameters. Despite its simplicity, the algorithm produces PSNR results that are competitive with the state-of-art coders in literature.

This paper investigates the reconstruction of an image from the phase or magnitude of its complex wavelet transform (CWT). We view the CWT as an approximation to the analytic representation of some real wavelet coefficients and develop the conditions under which a 1D signal is uniquely specified by its analytic phase or magnitude. Then, we extend the uniqueness conditions to multi-resolution and higher dimensions in order to match the situation of the CWT. In the development of the uniqueness conditions, we also gain some insights about the quality of reconstructed images and the geometrical structure of the CWT phase and magnitude representation. Our results for the CWT may also be applied to other localized phase and magnitude representations.

The restoration of missing regions in images (inpainting) is mathematically an interpolation problem and has many important applications. This paper proposes a novel iterative inpainting algorithm based on the interpolation of the complex wavelet transform (CWT) coefficients with simple geometrical models on the magnitude and phase of the coefficients. The geometrical models describe the directionality and uniformity of the CWT magnitudes and the linearity of the CWT phases around edges and within texture areas. Both piecewise smooth signals and structured textures can be interpolated accurately with the proposed models. Motivated by the iterative reconstruction of an image from its CWT magnitude or phase, we propose an inpainting algorithm with iterative magnitude and phase estimation and CWT reconstruction. Simulation results show that the proposed algorithm achieves high PSNR and appealing visual quality with low computation complexity.

In this paper, we introduce the "spherical representation", which provides a new adaptive framework for modeling and coding the image information in wavelet subbands. Based on this representation, a practical coding algorithm is developed. This coder uses local energy as a direct measure to differentiate between parts of the wavelet subband and to decide how to allocate the available bitrate. As local energy becomes available at finer resolutions, i.e. in smaller size windows, the coder automatically updates its decisions about how to spend the bitrate. We use a hierarchical set of variables to specify and code the local energy up to the highest resolution, i.e. the energy of individual wavelet coefficients. The overall scheme is nonredundant, meaning that the subband information is conveyed using this equivalent set of variables without the need for any side parameters. Despite its simplicity, the algorithm produces PSNR results that are competitive with the state-of-art coders in literature.

Translation invariant (TI) image denoising outperforms orthogonal wavelet thresholding by averaging a collection of denoised estimates from different orthogonal bases. The paper proposes a new perspective of TI processing as an average of a collection of cyclic-basis frame reconstructions, each a stationary signal estimate, contrasting with the nonstationary estimates of orthogonal wavelet thresholding. This viewpoint clarifies that certain characteristics of TI (i.e. reduced edge contour artifacts) are inherited from each cyclic-basis reconstruction, rather than from the process of averaging. We relate performance advantages of TI in smooth areas of images to statistical relationships of the cyclic-basis reconstructions. In edge regions, the quality of cyclic-basis reconstructions varies significantly with pixel position relative to the edge contour. These differences couple with convexity arguments to explain the large performance gains of TI in edge regions. They also suggest an improved approach to frame reconstruction, based on estimating relative location information, and identifying the best cyclic-basis reconstruction for the estimated pixel location.

Successful image interpolation requires proper enhancement of high frequency content of image pixels around edges. We introduce a simple edge model to estimate high resolution edge profiles from lower resolution values. Pixels around edges are viewed as samples taken from one dimensional (1D) continuous edge profiles according to 1D smooth edge contours defining the sampling instants. The image is highpass filtered by wavelets and subpixel edge locations are estimated by minimizing the modeling error in the wavelet domain. Interpolation is carried out by applying the model, wherever applicable, together with a baseline interpolator (here, bilinear) in order to make edges look sharper without introducing artifacts. The results are compared to bilinear interpolation, and significant improvement in terms of SNR, edge sharpness and contour smoothness is observed.

State of the art image coders make use of various methods to exploit intra and inter-band dependencies of wavelet coefficients in order to improve performance. While these efforts achieve considerable bitrate reduction for coding clusters of insignificant coefficients in smooth areas, most of the bitrate is spent on coding wavelet coefficients that are localized around edges in images. Recent research in literature is focused on developing new (linear or nonlinear) representations that deal with the rich and varying structures of pixel values around edges. In this paper, we use a simplified edge model to investigate the nonlinear dependencies that exist among wavelet coefficients, and introduce a nonlinear representation that is geared towards exploiting such dependencies for improved coding performance. Simulations support the relevance of the model, and we discuss our current efforts to incorporate these ideas into an actual image coder.

Successful image interpolation requires proper enhancement of high frequency content of image pixels around edges. In this paper, we introduce a simple edge model to estimate high resolution edge profiles from lower resolution values. Pixels around edges are viewed as samples taken from one dimensional (1-D) continuous edge profiles according to 1-D smooth edge contours defining the sampling instants. The image is highpass filtered by wavelets and subpixel edge locations are estimated by minimizing the modeling error in the wavelet domain. Interpolation is carried out by applying the model, wherever applicable, together with a baseline interpolator (here, bilinear) in order to make edges look sharper without introducing artifacts. The results are compared to bilinear interpolation, and significant improvement in terms of SNR, edge sharpness and contour smoothness is observed.

For data communications in time-varying channels such as wireless channels, the dynamic channel fluctuations often cause high frame-error rates. When the link layer detects that a frame is in error, conventionally, the frame is dropped and retransmission of the frame is requested. Based on the fact that the erroneous frames still contain useful information, several schemes have been proposed, such as packet combining and incremental redundancy, which retain and utilize the erroneous frames to improve retransmission performance. In this paper, we address two questions: 1) how much information is still useful in the erroneous frame; and 2) how to design a retransmission scheme to make efficient use of such information. We model this scenario (retransmission with an erroneous frame available at the receiver) as communication with side information at the receiver, and for a class of time-varying channels, the compound block interference channels, we derive with information-theoretic arguments the minimum information rate sufficient for retransmission to recover the erroneous frame. Motivated by the theoretical results, we propose an embedded channel coding/modulation structure together with a rate-adaptive retransmission scheme. Performance results indicate significant improvements over existing retransmission schemes in both additive white Gaussian noise and quasi-static Rayleigh fading channels.

This paper describes our efforts in developing and updating a senior-level course in image and video processing at the University of Illinois. This course was introduced in the mid nineties.

We present an adaptive feature selection scheme to jointly optimize the detector performance and the computational efficiency for statistical object detection. From the statistical distribution of wavelet coefficients, we construct an error-bound-tree (EBT) to analyze the error probability of the Bayes test. The wavelet features put into test are adaptively selected to minimize the detection error. The selected features are more discriminative than others and allow the detector to reach a decision faster without jeopardizing its accuracy. The proposed scheme is demonstrated in face detection.

This paper introduces a new framework for error concealment in block-based image coding systems: sequential recovery. Unlike previous approaches that simultaneously recover the pixels inside a missing block, we propose to recover them in a sequential fashion such that the previously-recovered pixels can be used in the recovery process afterwards. The principal advantage of the sequential approach is the improved capability of recovering important image features brought by the reduction in the complexity of statistical modeling, i.e., from blockwise to pixelwise. Under the framework of sequential recovery, we present an orientation adaptive interpolation scheme derived from the pixelwise statistical model. We also investigate the problem of error propagation with sequential recovery and propose a linear merge strategy to alleviate it. Extensive experimental results are used to demonstrate the improvement of the proposed sequential error-concealment technique over previous techniques in the literature.

We propose multiple description (MD) video coders which use motion-compensated predictions. Our MD video coders utilize MD transform coding and three separate prediction paths at the encoder to mimic the three possible scenarios at the decoder: both descriptions received or either of the single descriptions received. We provide three different algorithms to control the mismatch between the prediction loops at the encoder and decoder. We present simulation results comparing the three approaches to two standards-based approaches to MD video coding. We show that when the main prediction loop at the encoder uses a two-channel reconstruction, it is important to have side prediction loops and transmit some redundancy information to control mismatch. We also examine the performance of our MD video coder with partial mismatch control in the presence of random packet loss, and demonstrate a significant improvement compared to more traditional approaches.

Temporal relationships (motion fields) have been widely exploited by researchers for video processing. Their primary use has been to group pixels in spatiotemporal neighborhoods. Examples include coding and noise reduction. Typically, video processing is achieved by filtering, modeling, or analyzing pixels in these neighborhoods. In spite of the widespread use of motion information to process video, rarely are the fields treated as signals, i.e., the temporal relationships are seldom considered as a distinct time series. A notable exception is the generalized autoregressive modeling of these relationships in Rajagopalan et al. (1997). In this work, we present a generalization of finite impulse response filtering applicable to temporal relationships and continue the spirit of the work of treating motion fields as a distinct signal (albeit one that is closely tied to the pixel intensities). Applications presented are preprocessing of video for coding and for noise reduction. Instead of filtering pixels in spatiotemporal neighborhoods directly, we argue that it may be more beneficial to filter the temporal relationships first and then synthesize processed video. Simulations shows MPEG-1 rate gains of up to 20% for coding processed video compared to unprocessed ones where processing leaves the original perceptually unchanged. Noise reduction experiments demonstrate a gain of 0.5 dB at high signal to noise ratios over the best results in the published literature while at low to moderate SNRs, improvements are 0.3 dB lower.

This paper provides a mathematical analysis of transform compression in its relationship to linear and nonlinear approximation theory. Contrasting linear and nonlinear approximation spaces, we show that there are interesting classes of functions/random processes which are much more compactly represented by wavelet-based nonlinear approximation. These classes include locally smooth signals that have singularities, and provide a model for many signals encountered in practice, in particular for images. However, we also show that nonlinear approximation results do not always translate to efficient compress on strategies in a rate-distortion sense. Based on this observation, we construct compression techniques and formulate the family of functions/stochastic processes for which they provide efficient descriptions in a rate-distortion sense. We show that this family invariably leads to Besov spaces, yielding a natural relationship among Besov smoothness, linear/nonlinear approximation order, and compression performance in a rate-distortion sense. The designed compression techniques show similarities to modern high-performance transform codecs, allowing us to establish relevant rate-distortion estimates and identify performance limits.

The problem of source coding with side information at the decoder arises in many practical scenarios. Although this problem has been well characterized in information theory, particularly by the work of Wyner and Ziv (1976), there is still lack of successful algorithms for it. In this paper, we use trellis codes to approach the theoretical limit. An embedded trellis code structure is proposed, and its properties are examined. Using this structure, we can achieve the granular gain at the encoder as well as the coding gain at the decoder. Simulation results show that the proposed scheme outperforms the algorithms reported in the literature. It is also indicated that the performance of the proposed algorithm can approach the information-theoretic limit at high rate as the trellis complexity increases.

We propose a directional smoothness measure for block-based error concealment through spatial correlation. Image structures revealed by consistent edge profiles are very important for subjective visual quality. We treat the problem of block reconstruction as consistent recovery of local image structures. The directional smoothness measure evaluates structural consistency along an edge elongation and is used as the object function for block reconstruction. Corrupted DCT coefficients are recovered by smoothly extending various edge profiles from surrounding areas to missing blocks. The reconstruction is adaptive to local image structures. Consistent cross-edge sharpness and along-edge smoothness are maximally preserved during the reconstruction. The proposed concealment method demonstrates encouraging improvement both in the subjective image quality and in the reconstruction PSNR over conventional schemes. It is applicable to various spatial and spectral interleaving systems and a fast implementation is also proposed.

For multimedia communications in wireless channels, it is desirable that the quality of the multimedia service is gracefully degraded when the channel conditions deteriorate. To that end, unequal error protection (UEP) plays an essential role, by which the coded bit streams of different significance are given different levels of protection. We design power- and bandwidth-efficient coded modulation scheme for UEP. Motivated by the information-theoretic results, a superposition coded modulation scheme is designed by using shaping techniques. The carefully-designed shaping can successfully reduce the interference between the fine-level code and the coarse-level code. The performance of the proposed scheme is evaluated through both analysis and simulations. Simulation results indicate that the proposed scheme outperforms those without shaping by more than 3 dB in the region of interest for UEP.

Summary form only given. The vast majority of signal processing research studies linear operations on vectors of samples from one-, two-, or higher dimensional signals. While linear operators can be very successful at exploiting many types of relationships among signal samples, they are ineffective for processing a very common form of uncertainty in images and video: location uncertainty. The locations of edges in images sketch 1-D contours which constitute an important part of the information in most images. Thisarticle shows how signals imbedded in location uncertainty of image contours induce a nonlinear manifold structure to the probability of images. Due to this nonlinear manifold structure to the space of images, no linear decomposition of images (e.g. transforms, wavelets, etc.) can fully exploit the dependencies within images. Based on these observations, we point to new directions for developing improved image processing tools.

We consider a simple multiple description (MD) video coder, that uses redundancy-rate-distortion criteria to split a one-layer stream generated by a standard video coder into two correlated streams. Our simulation results demonstrate that this MD coder has much better performance for large redundancies than our previous MDTC video coder, although it cannot perform as well at low redundancies. This MD video coder is very simple to implement and is compatible with H.263 to the extent that each description can be decoded by a standard H.263 decoder. This MD coder was used in a previous study on the transport of MD and layered video over an EGPRS wireless network, where the fact that it creates two streams with very balanced rates was a strong advantage.

We propose a new wavelet domain image interpolation scheme based on statistical signal estimation. A linear composite MMSE estimator is constructed to synthesize the detailed wavelet coefficients as well as to minimize the mean squared error for high-resolution signal recovery. Based on a discrete time edge model, we use low-resolution information to characterize local intensity changes and perform resolution enhancement accordingly. A linear MMSE estimator follows to minimize the estimation error. Local image statistics are involved in determining the spatially adaptive optimal estimator. With knowledge of edge behavior and local signal statistics, the composite estimation is able to enhance important edges and to maintain the intensity consistency along edges. Strong improvement in both the visual quality and the PSNRs of the interpolated images has been achieved by the proposed estimation scheme.

In a standard hybrid video coder, there are two important factors affecting motion-compensated prediction: motion uncertainty and quantization noise, motion uncertainty results from the use of block-decimated motion compensation, which cannot specify the motion for each pixel. The propagation of quantization noise results from interframe prediction. We analyze both these effects, and their block-structured nonstationary properties. We propose a block-adaptive linear filtering framework to reduce motion uncertainty and quantization noise propagation simultaneously. This new motion-compensated predictor can be viewed as joint application of overlapped block motion compensation and loop filtering (LF). Several system configurations are evaluated. We show that this linear filtering framework achieves better rate-distortion performance than the single use of either overlapped block motion compensation or LF.

This paper presents a new direct Fourier-based algorithm for performing image-to-image registration to subpixel accuracy, where the image differences are restricted to translations and uniform changes of illumination. The algorithm detects the Fourier components that have become unreliable estimators of shift due to aliasing, and removes them from the shift-estimate computation. In the presence of aliasing, the average precision of the registration is a few hundredths of a pixel. Experimental data presented here show that the new algorithm yields superior registration precision in the presence of aliasing when compared to several earlier methods and has comparable precision to the iterative method of P. Thevenaz et al. (1998).

This paper sheds light on the least-square (LS)-based adaptive prediction schemes for lossless compression of natural images. Our analysis shows that the superiority of the LS-based adaptation is due to its edge-directed property, which enables the predictor to adapt reasonably well from smooth regions to edge areas. Recognizing that LS-based adaptation improves the prediction mainly around the edge areas, we propose a novel approach to reduce its computational complexity with negligible performance sacrifice. The lossless image coder built upon the new prediction scheme has achieved noticeably better performance than the state-of-the-art coder CALIC with moderately increased computational complexity.

This paper proposes an edge-directed interpolation algorithm for natural images. The basic idea is to first estimate local covariance coefficients from a low-resolution image and then use these covariance estimates to adapt the interpolation at a higher resolution based on the geometric duality between the low-resolution covariance and the high-resolution covariance. The edge-directed property of covariance-based adaptation attributes to its capability of tuning the interpolation coefficients to match an arbitrarily oriented step edge. A hybrid approach of switching between bilinear interpolation and covariance-based adaptive interpolation is proposed to reduce the overall computational complexity. Two important applications of the new interpolation algorithm are studied: resolution enhancement of grayscale images and reconstruction of color images from CCD samples. Simulation results demonstrate that our new interpolation algorithm substantially improves the subjective quality of the interpolated images over conventional linear interpolation.

We find the optimal window for overlapped block motion compensation (OBMC) by statistically modeling the motion field, the field of block motion estimates and their relationship. This enables us to show how the optimal OBMC window is affected by random field parameters, such as the variance of the motion field and the correlation coefficients of both the intensity field and the motion field. The OBMC window obtained in this fashion is shown to have good performance in reducing the prediction error. Furthermore, this parametric solution provides insight into motion uncertainty and the overlapped motion compensation process.

This paper analyzes the relationship between the residual frame and the previous frame in motion-compensated video coding. It is found that the variance of the residual signal depends on the gradient magnitude. On average, the variance of the residual signal is larger for pixels with larger gradient magnitude. Two applications of this analysis are presented. In the first one, the relationship between the residual signal variance and the gradient magnitude is used to model the second-order statistics of the residual field in a nonstationary way. This modeling enables more efficient residual signal coding. The other application is for pixel decimation-based fast block matching. It is proposed that pixels with the largest gradient magnitude in a block be chosen to participate in the block matching process. It is demonstrated that such a gradient-adaptive subsampling achieves great advantage over two other known subsampling methods.

The objective of multiple description coding (MDC) is to encode a source into multiple bitstreams supporting multiple quality levels of decoding. In this paper, we only consider the two-description case, where the requirement is that a high-quality reconstruction should be decodable from the two bitstreams together, while lower, but still acceptable, quality reconstructions should be decodable from either of the two individual bitstreams. This paper describes techniques for meeting MDC objectives in the framework of standard transform-based image coding through the design of pairwise correlating transforms. The correlation introduced by the transform helps to reduce the distortion when only a single description is received, but it also increases the bit rate beyond that prescribed by the rate-distortion function of the source. We analyze the relation between the redundancy (i.e., the extra bit rate) and the single description distortion using this transform-based framework. We also describe an image coder that incorporates the pairwise transform and show its redundancy-rate-distortion performance for real images.

Differential pulse-coded modulation (DPCM) encoding of Gaussian autoregressive (AR) sequences is considered. It is pointed out that DPCM is rate-distortion inefficient at low bit rates. Simple filtering modifications are proposed and incorporated into DPCM. A rate-distortion optimization framework that results in optimal filters is presented. It is shown that the designed filters take advantage of "less significant" process spectral components in order to achieve superior rate-distortion performance. Design equations are derived, issues related to optimization and complexity addressed. It is shown that simple DPCM systems with the proposed modifications significantly outperform their standard counterparts.

Computation complexity is an important issue for current face detection systems. This paper proposes a subspace approach to capture local discriminative features in the space-frequency domain for fast face detection. Based on orthonormal wavelet packet analysis, we develop a discriminant subspace algorithm to search for the "minimum cost" subspace of the high-dimensional signal space, which leads to a set of wavelet features with maximum class discrimination and dimensionality reduction. Detailed (high frequency) information within local facial areas shows noticeable discrimination ability for face detection problem. We demonstrate the algorithm in the context of detecting frontal view faces in a complex background. Discrete pattern distribution functions and fast likelihood ratio detection are adopted by the system. Because of the reduced dimensionality, feature discrimination and the discrete stochastic model, our face detection system consumes much less computation while the performance is comparable with other reported leading systems.

Block matching motion compensation achieves savings in residual error energy at the cost of motion vector bit rate. While this tradeoff has proven valuable for many video sequences, there are many obvious examples of blocks for which the cost of motion vectors is not offset by the gains of motion compensation. This paper proposes a multiresolution framework for motion compensated prediction that offers a richer set of options for trading off motion compensation accuracy against the cost of motion vectors. The method improves the prediction at motion boundaries and on covered/uncovered regions, while reducing the bit rate by using less accurate motion vectors in smoother regions. The new algorithm is compared to the full-search block matching in various simulations, and the results show that the algorithm achieves a 10 to 30% reduction in motion vector bit rate. These saving are particularly important in low bit rate applications where motion overhead constitutes a significant percentage of overall bit rate.

A variety of image watermarking schemes have been proposed using orthogonal transformations, projections, and coding techniques to embed imperceptible watermarks into images. Analytical studies of the watermarking problem have typically been based on studying the performance limits of these known algorithms. In contrast, this paper formalizes the watermarking problem in an "algorithm independent" framework, representing any watermarking algorithm as a partition of the image space into a collection of sets, and defining requirements of these sets that must be met by any solution to the watermarking problem. Specifically, these requirements define and constrain the false-alarm ratio, distortion, robustness and security of a watermarking system. Using this formalism, we first characterize common features of algorithms that solve the watermarking problem. We show how the requirements defined earlier force important differences between watermarking signal sets and classical communication systems signal sets. Next, we show how common components of existing watermarking algorithms (e.g. transformations, projections, and coding) can be associated with specific requirements of the watermarking definition. Finally, we show how our new formalism of the watermarking problem provides a procedure for optimal design of watermarking systems to target specified false-alarm, distortion, and robustness objectives.

This paper presents a novel edge orientation adaptive interpolation scheme for resolution enhancement of still images. In order to achieve ideal orientation adaptation, we propose to estimate the local covariance characteristics at low resolution but cleverly use them to direct the interpolation at high resolution based on the resolution invariant property of edge orientation. The orientation adaptive property guarantees the interpolation always go along the edge orientation but not across it. Our new interpolation scheme can generate images with dramatically higher visual quality than linear interpolation techniques while keeping the computational complexity still modest.

This paper presents a novel wavelet-based image denoising algorithm under overcomplete expansion. In order to optimize the denoising performance, we make a systematic study of both signal and noise characteristics under overcomplete expansion. High-band coefficients are viewed as the mixture of non-edge class and edge class observing different probability models. Based on improved statistical modeling of wavelet coefficients, we derive optimal MMSE estimation strategies to suppress noise for both non-edge and edge coefficients. We have achieved fairly better objective performance than most recently-published wavelet denoising schemes.

Multiple description coding is posed as a source coding problem that uses diversity to overcome channel impairments. In this paper, we use trellis coded quantization (TCQ) to obtain granular gain over the multiple description scalar quantizer. Several algorithms are proposed, aiming for different level of channel reliability. By investigating the relationship of the Voronoi regions of the side and central quantizers, we are able to achieve the TCQ performance at the central receiver with little sacrifice at the side receivers. On the other hand, with the side receivers both having the TCQ performance and approaching the rate distortion bound, the performance at the central receiver can get close to the multiple description rate distortion limit.

We explore the ability of multiple description (MD) source coders to achieve good performance on channels other than ideal MD channels. We examine both the overall system design and compare the performance of a system with MD source coder to that of a more traditional system using a layered source coder. For the memoryless channels we consider, MD source coding cannot achieve acceptable performance for a memoryless Gaussian source without appropriate channel coding. Also, in memoryless channels, a system with MD source coding outperforms a layered source coding system only in very poor channels. The introduction of memory in the channel degrades the performance of both systems equally. Using interleaving to reduce the impact of memory in the channel has more influence on performance than the choice of source coder.

Natural images are populated with edges characterized by abrupt changes of local statistics. They put severe challenges on probability modeling of image sources. This paper proposes to employ recursive least square (RLS)-based predictive modeling to characterize local statistics for edges. It can be viewed as estimating the covariance matrix from a local causal neighborhood and selecting the MMSE optimal predictor for the local covariance estimate. We demonstrate how the RLS-based adaptation can produce predictor with support ideally aligned along an arbitrarily-oriented edge and therefore we call it "Edge Directed Prediction"(EDP). When applied to lossless image compression, the EDP substantially outperforms former context-based prediction schemes for natural images. Based on our high-level understanding of EDP, we dramatically reduce its complexity with little sacrifice on the performance, thus facilitating its application in practice.

We propose multiple description (MD) video coders which use motion compensated predictions. Our MD video coders utilize MD transform coding and three separate prediction paths at the encoder, to mimic the three possible scenarios at the decoder: both descriptions received or either of the single descriptions received. We provide three different algorithms to control the mismatch between the prediction loops at the encoder and decoder. The results show that when the main prediction loop is the central loop, it is important to have side prediction loops and transmit some redundancy information to control mismatch.

In most current video coders, a block is first predicted from its best matching block in a previous frame, and the prediction error is then coded using discrete transform coding (DCT). Because of the inadequacy of the block-wise translational motion model, edges in the predicted block are often shifted from their true positions, leading to errors that are clustered around edges in the predicted block. DCT is inefficient for coding such errors. Independent searching of block motion vectors also lead to discontinuities of edges across block boundaries. Existing coders ignore such correlation between error location and edge discontinuity. We describe a coder that corrects edge-misalignment before applying DCT coding. The correlation between edge-discontinuity and edge-misalignment is exploited in the coding of the misalignment parameters.

We undertake a study of the performance difference of the discrete cosine transform (DCT) and the wavelet transform for both image and video coding, while comparing other aspects of the coding system on an equal footing based on the state-of-the-art coding techniques. The studies reveal that, for still images, the wavelet transform outperforms the DCT typically by the order of about 1 dB in peak signal-to-noise ratio. For video coding, the advantage of wavelet schemes is less obvious. We believe that the image and video compression algorithm should be addressed from the overall system viewpoint: quantization, entropy coding, and the complex interplay among elements of the coding system are more important than spending all the efforts on optimizing the transform.

In this paper, an experimental study of the statistical properties of wavelet coefficients of image data is presented, as well as the design of two different morphology-based image coding algorithms that make use of these statistics. A salient feature of the proposed methods is that, by a simple change of quantizers, the same basic algorithm yields high performance embedded or fixed rate coders. Another important feature is that the shape information of morphological sets used in this coder is encoded implicitly by the values of wavelet coefficients, thus avoiding the use of explicit and rate expensive shape descriptors. These proposed algorithms, while achieving nearly the same objective performance of state-of-the-art zerotree based methods, are able to produce reconstructions of a somewhat superior perceptual quality, due to a property of joint compression and noise reduction they exhibit.

This work introduces a new approach to inverse halftoning using nonorthogonal wavelets. The distinct features of this wavelet-based approach are: 1) edge information in the highpass wavelet images of a halftone image is extracted and used to assist inverse halftoning, 2) cross-scale correlations in the multiscale wavelet decomposition are used for removing background halftoning noise while preserving important edges in the wavelet lowpass image, and 3) experiments show that our simple wavelet-based approach outperforms the best results obtained from inverse halftoning methods published in the literature, which are iterative in nature.

Multiple description coding (MDC) addresses the problem of encoding a source into two (or more) bitstreams such that a high-quality reconstruction is decodable from the two bitstreams together, while a lower, but still acceptable, quality reconstruction is decodable if either of the two bitstreams is lost. Recent research has proposed using transforms to introduce a controlled amount of correlation between the two bitstreams in order to achieve MDC objectives. This paper considers several optimality issues related to such transform based MDC methods. Redundancy rate-distortion (RRD) performance of a general class of transforms is derived and used to identify the optimal transform for achieving any given amount of redundancy. Then, the paper introduces a more general transform-based MDC framework incorporating both the transform mode of redundancy and a second mode of redundancy. The optimal allocation of redundancy among these two modes is analyzed.

While overlapped block motion compensation (OBMC) with block matching motion vectors yields better estimation accuracy than standard block matching, these estimates may be significantly improved by optimizing the motion vectors. Optimal motion vectors may be determined by an iterative and computationally intensive process. However, for a low-cost system (e.g., videoconferencing), such an approach is not feasible. An analysis of the compensation errors after motion optimization reveals that most gains in estimation accuracy result from the optimization of a fraction of the total number of blocks in a frame. It is thus conceivable that, by defining suitable ordering algorithms for blocks, coding systems could see improved performance by optimizing some number of blocks based on the ordering depending on available computational resources. With the aid of simulations we first show that most improvements by optimizing motion are limited to a few motion vectors. Then we present simple and intuitive algorithms based on compensation error after OBMC with block matching vectors to order blocks. Simulation results using these algorithms for ordering and optimizing motion are presented for two video sequences. The results reveal improvements obtained by optimizing the motion of the blocks from the ordering are reasonable; however, the improvements are not limited to the first fraction of blocks from the ordering, suggesting that better ordering algorithms be investigated in the future.

We extend our previous work on space-frequency quantization (SFQ) for image coding from wavelet transforms to the more general wavelet packet transforms. The resulting wavelet packet coder offers a universal transform coding framework within the constraints of filterbank structures by allowing joint transform and quantizer design without assuming a priori statistics of the input image. In other words, the new coder adaptively chooses the representation to suit the image and the quantization to suit the representation. Experimental results show that, for some image classes, our new coder gives excellent coding performance.

We introduce a new image compression paradigm that combines compression efficiency with speed, and is based on an independent "infinite" mixture model which accurately captures the space-frequency characterization of the wavelet image representation. Specifically, we model image wavelet coefficients as being drawn from an independent generalized Gaussian distribution field, of fixed unknown shape for each subband, having zero mean and unknown slowly spatially-varying variances. Based on this model, we develop a powerful "on the fly" estimation-quantization (EQ) framework that consists of: (i) first finding the maximum-likelihood estimate of the individual spatially-varying coefficient field variances based on causal and quantized spatial neighborhood contexts; and (ii) then applying an off-line rate-distortion (R-D) optimized quantization/entropy coding strategy, implemented as a fast lookup table, that is optimally matched to the derived variance estimates. A distinctive feature of our paradigm is the dynamic switching between forward and backward adaptation modes based on the reliability of causal prediction contexts. The performance of our coder is extremely competitive with the best published results in the literature across diverse classes of images and target bitrates of interest, in both compression efficiency and processing speed. For example, our coder exceeds the objective performance of the best zerotree-based wavelet coder based on space-frequency-quantization at all bit rates for all tested images at a fraction of its complexity.

Motion uncertainty and image quantization noise are two important factors affecting the performance of block motion compensation in a standard hybrid video coder. This paper models both these effects, and analyzes their nonstationary property. It proposes a strategy that jointly applies space-varying overlapped block motion compensation and loop filtering, achieving better rate-distortion performance than either method alone.

The objective of multiple description coding (MDC) is to encode a source into two (or more) bitstreams supporting two quality levels of decoding. A high-quality reconstruction should be decodable from the two bitstreams together, while lower, but still acceptable, quality reconstructions should be decodable from either of the two individual bitstreams. This paper describes techniques for meeting MDC objectives in the framework of standard transform-based image coding through the design of pairwise transforms.

Multiple description coding (MDC) is a way of trading off coding gain with robustness to channel errors. This paper presents a new method for MDC using the framework of transform coding. Instead of using the Karhunen-Loeve transform (KLT) that decorrelates all the coefficients, we choose the transform bases so that the coefficients are correlated pair-wise. This is accomplished by rotating every two basis vectors in the KLT. Each pair of correlated coefficients are then split between two descriptions. Only 45/spl deg/ rotation is considered which leads to two balanced streams. In the actual implementation, the DCT is employed in place of the KLT and the rotation of transform bases is accomplished by rotating the DCT coefficients. Experimental results show that this method can lead to satisfactory image reconstruction from any one description with a relatively small (20% for "lena") overhead over a standard JPEG coder.

This paper introduces a new approach to deblocking of JPEG compressed images using overcomplete wavelet representations. By exploiting cross-scale correlations among wavelet coefficients, edge information in the JPEG compressed images is extracted and protected, while blocky noise in the smooth background regions is smoothed out in the wavelet domain. Compared with the iterative methods reported in the literature, our simple wavelet-based method has much lower computational complexity, yet it is capable of achieving the same peak signal-to-noise ratio (PSNR) improvement as the best iterative method and giving visually very pleasing images as well.

The transform coding of images is analyzed from a common standpoint in order to generate a framework for the design of optimal transforms. It is argued that all transform coders are alike in the way they manipulate the data structure formed by transform coefficients. A general energy compaction measure is proposed to generate optimized transforms with desirable characteristics particularly suited to the simple transform coding operation of scalar quantization and entropy coding. It is shown that the optimal linear decoder (inverse transform) must be an optimal linear estimator, independent of the structure of the transform generating the coefficients. A formulation that sequentially optimizes the transforms is presented, and design equations and algorithms for its computation provided. The properties of the resulting transform systems are investigated. In particular, it is shown that the resulting basis are nonorthogonal and complete, producing energy compaction optimized, decorrelated transform coefficients. Quantization issues related to nonorthogonal expansion coefficients are addressed with a simple, efficient algorithm. Two implementations are discussed, and image coding examples are given. It is shown that the proposed design framework results in systems with superior energy compaction properties and excellent coding results.

We examine the question of how to choose a space varying filterbank tree representation that minimizes some additive cost function for an image. The idea is that for a particular cost function, e.g., energy compaction or quantization distortion, some tree structures perform better than others. While the wavelet tree represents a good choice for many signals, it is generally outperformed by the best tree from the library of wavelet packet frequency-selective trees. The double-tree library of bases performs better still, by allowing different wavelet packet trees over all binary spatial segments of the image. We build on this foundation and present efficient new pruning algorithms for both one- and two-dimensional (1-D and 2-D) trees that will find the best basis from a library that is many times larger than the library of the single-tree or double-tree algorithms. The augmentation of the library of bases overcomes the constrained nature of the spatial variation in the double-tree bases, and is a significant enhancement in practice. Use of these algorithms to select the least-cost expansion for images with a rate-distortion cost function gives a very effective signal adaptive compression scheme. This scheme is universal in the sense that, without assuming a model for the signal or making use of training data, it performs very well over a large class of signal types. In experiments it achieves compression rates that are competitive with the best training-based schemes.

We propose a model for the interframe correspondences existing between pixels of an image sequence. These correspondences form the elements of a field called the motion field. In our model, spatial neighborhoods of motion elements are related based on a generalization of autoregressive (AR) modeling of the time-series. We also propose a joint spatio-temporal model by including spatial neighborhoods of pixel intensities in the motion model. A fundamental difference of our approach with most previous approaches to modeling motion is in basing our model on concepts from statistical signal processing. The developments in this paper give rise to the promise of extending well-understood tools of signal processing (e.g., filtering) to the analysis and processing of motion fields. Simulation results presented show the performance of our models in interframe prediction; specifically, on average the motion model performs 29% better in terms of the mean squared error energy over a commonly used pel-recursive approach. The spatio-temporal model improves the prediction efficiencies by 8% over the motion model. Our model can also be used to obtain estimates of the optical flow field as the simulations demonstrate.

A new class of image coding algorithms coupling standard scalar quantization of frequency coefficients with tree-structured quantization (related to spatial structures) has attracted wide attention because its good performance appears to confirm the promised efficiencies of hierarchical representation. This paper addresses the problem of how spatial quantization modes and standard scalar quantization can be applied in a jointly optimal fashion in an image coder. We consider zerotree quantization (zeroing out tree-structured sets of wavelet coefficients) and the simplest form of scalar quantization (a single common uniform scalar quantizer applied to all nonzeroed coefficients), and we formalize the problem of optimizing their joint application. We develop an image coding algorithm for solving the resulting optimization problem. Despite the basic form of the two quantizers considered, the resulting algorithm demonstrates coding performance that is competitive, often outperforming the very best coding algorithms in the literature.

We consider the temporal DPCM loop at the heart of most modern high performance video coders. Targeting low bitrate-low complexity video applications, it is shown that DPCM is inefficient in this region. The DPCM codec is analyzed in the low bitrate region and rate-distortion optimal modifications are proposed that do not violate the low complexity requirement. The proposed modifications involve negligible added complexity at the encoder and no added complexity at the decoder and are thus compatible with standard coders and bit streams.

Warping, also known as control grid interpolation, estimates intensities in the present frame through an interpolation of motion vectors-typically with bilinear interpolation. This paper presents a method for computing optimal interpolation parameters for warping prediction. Conventional bilinear warping, while mostly effective, has been known to exhibit unreliable performance in certain situations. Since both block-matching (BMA) and bilinear warping are candidate solutions for optimal warping, the performance of optimal warping is lower bounded by both bilinear warping and BMA, therefore vastly reducing the inconsistency problem. Furthermore, this optimality criterion is applicable to any category of motion vector, including that of block-matching. Thus we are able to demonstrate the optimal usage, under linear operations in the motion domain, of BMA motion vectors.

This paper introduces a new approach to inverse halftoning using nonorthogonal wavelets. The distinct features of this wavelet-based approach are: a) edge information in the highpass wavelet images of a halftone is extracted and used to assist inverse halftoning, b) cross-scale correlations in the multiscale wavelet decomposition are used for removing background halftoning noise while preserving important edges in the wavelet lowpass image, c) experiments show that our simple wavelet-based approach outperforms the best results obtained from inverse halftoning methods published in the literature, which are iterative in nature.

Since Shapiro (see ibid., vol.41, no.12, p. 445, 1993) published his work on embedded zerotree wavelet (EZW) image coding, there have been increased research activities in image coding centered around wavelets. We first point out that the wavelet transform is just one member in a family of linear transformations, and the discrete cosine transform (DCT) can also be coupled with an embedded zerotree quantizer. We then present such an image coder that outperforms any other DCT-based coder published in the literature, including that of the Joint Photographers Expert Group (JPEG). Moreover, our DCT-based embedded image coder gives higher peak signal-to-noise ratios (PSNR) than the quoted results of Shapiro's EZW coder.

Presents a new interframe coding method for medical images, in particular magnetic resonance (MR) images. Until now, attempts in using interframe redundancies for coding MR images have been unsuccessful. The authors believe that the main reason for this is twofold: unsuitable interframe estimation models and the thermal noise inherent in magnetic resonance imaging (MRI). The interframe model used here is a continuous affine mapping based on (and optimized by) deforming triangles. The inherent noise of MRI is dealt with by using a median filter within the estimation loop. The residue frames are quantized with a zero-tree wavelet coder, which includes arithmetic entropy coding. This particular method of quantization allows for progressive transmission, which aside from avoiding buffer control problems is very attractive in medical imaging applications.

A new video coding scheme in which an image sequence is fully represented through its motion field is introduced. The motivation behind the new coding scheme is that motion fields are generally more efficient representations of image sequences. We describe the new coding scheme, and present a new generalized and optimized representation through the motion field. An important aspect of the new coding approach is that we are free to choose parameters in the representation of the motion field. Our goal is to choose those parameters so that the motion field can be coded most efficiently. We describe our definition of the motion field, and illustrate how the parameters of the motion model can be chosen. We also present the results of applying those parameters to the coding procedure.

The transmission and storage of digital video at reduced bit rates requires a source coding scheme, which generally contains motion compensated prediction as an essential part. The class of motion estimation algorithms known as backward methods have the advantage of dense motion field sampling, and in coding applications the decoder needs no motion information from the coder. In this paper, we first present an overview of operator based motion compensators with interpolative and non-interpolative kernels. We then proceed with two new results. The first offers a new perspective on the classical pel-recursive methods; one that exposes the weaknesses of traditional approaches and offers an explanation for the improved performance of operator-based algorithms. The second result introduces a minimum norm intra-frame operator and establishes an equivalence relationship between this and the original (least squares) operator. This equivalence induces interesting duality properties that, in addition to offering insights into operator-based motion estimators, can be used to relax either the maximum needed computational power or the frame buffer length.

We examine the question of how to choose a time-varying filter bank representation for a signal which is optimal with respect to an additive cost function. We present in detail an efficient algorithm for the Haar filter set which finds the optimal basis, given the constraint that the time and frequency segmentations are binary. Extension to multiple dimensions is simple, and the use of arbitrary filter sets is also possible. We verify that the algorithm indeed produces a lower cost representation than any of the wavelet packet representations for compression of images using a simple rate-distortion cost.

Proposes an improved statistical characterization of the field of wavelet coefficients of natural images. Based on this characterization, the authors introduce morphological representation of wavelet data (MRWD), a novel coding framework for both image and video coding applications. MRWD departs from existing wavelet-based coders in its use of a radically different set of primitive operations-non-linear, morphological operations-for efficiently encoding the wavelet data field. Simulation results are very encouraging: a preliminary algorithm based on the morphological data structure is able to achieve about 0.5 dB of gain in SNR over Shapiro's (1993) state-of-the-art zerotree-based wavelet coder at a coding rate of 1 bpp for the "Lena" image.

Hierarchical decomposition of images and their relationship with motion fields continues to be a hotly pursued topic, and the role of backward motion information in coding is beginning to capture the interest of video coding community. This paper simultaneously addresses some of the fundamental issues in multi-resolution and backward motion systems. From a coding viewpoint, a multi-resolution motion hierarchy should be coupled with an estimation system that deals with a maximally subsampled wavelet decomposition of the frames, to avoid redundancy of representation. Given the known difficulties of band-to-band motion compensated estimation in a wavelet domain, we use an alternative approach for estimation of detail bands, using lowpass bands of the anchor frames at higher resolutions. The resulting estimation errors are coded through a zerotree quantizer. Simulations show that a prototype coder of this type is very competitive, with a performance better than conventional forward (block-based) coders.

Volumetric medical imaging data presents a special challenge in terms of storage and communication. Even the smallest sets of volumetric data are many times larger than most single medical images, and the onset of new applications that link data-sharing with video conferencing and multi-media make efficient and flexible coding of volumetric data an important task. Here the authors explore motion-like models for the coding of volumetric data. They first visit the affine interframe model, which was recently used to code MRI sequences effectively. Motivated by the encouraging results from the affine coder, the authors performed a comparative study of motion vs. 3-D spatial optimal autoregressive predictors. The results of this study indicate that motion analysis indeed leads to improved predictor performance in volumetric medical images, compared to the optimal 3-D predictor.

In previous work, we introduced a new image representation for the field of wavelet coefficients (dubbed MRWD), based on morphological operators. This work extends the MRWD framework, by addressing the effective design of image coding algorithms. First, we design an encoder with the goal of being optimal in the operational rate-distortion sense. Second, based on the same (morphological) techniques, we design a successively refinable version of the single rate coder. Simulation results are reported.

We introduce a new image coding algorithm which exploits the idea of space-varying wavelet packets, where the best filter bank representation is chosen from a large library. The filter bank tree representations in the library are free to vary in structure over different segments of the image, and a fast search algorithm is given. In addition we employ the idea of space-frequency quantization, which is a rate-distortion optimized extension of the zero-tree wavelet coder of Shapiro to wavelet packets. The coder thus adaptively chooses the representation to suit the image and adaptively chooses the quantization to suit the representation. We present coding results that confirm the excellent performance of the scheme.

Wavelet image decompositions generate a tree-structured set of coefficients, providing an hierarchical data-structure for representing images. Several recently proposed image compression algorithms have focused on new ways for exploiting dependencies between this hierarchy of wavelet coefficients. This paper presents a new framework for understanding the efficiency of one such algorithm as a simplified attempt to a global entropy-constrained image quantizer. The principle insight offered by the new framework is that improved performance is achieved by more accurately characterizing the joint probabilities of arbitrary sets of wavelet coefficients. The specific algorithm described is designed around one conveniently structured collection of such sets. The efficiency of hierarchical wavelet coding algorithms derives from their success at identifying and exploiting dependencies between coefficients in the hierarchical structure. The second part of the paper presents an empirical study of the distribution of high-band wavelet coefficients, the band responsible for most of the performance improvements of the new algorithms.>

Presents the results of using the new MATLAB image processing toolbox and the C programming language in a senior-level image processing course at the University of Illinois. The course includes for the first time a formal lab component, so more time and effort have been devoted to computer algorithm implementation than previously. Students are expected to implement and test image processing algorithms in both MATLAB and C. The authors explore the benefits of using MATLAB and C to teach image processing, and evaluate the students' results in the lab.>

Video compression standards are all based on a hybrid coding approach, where the video frames are represented partially as motion information and partially as (residual) intensity information. In this paper we present a new approach to video coding, where the video sequences are represented through motion information only. The new coding approach builds upon the traditional block-based motion compensation scheme, with the residual information coded as motion rather than intensity. Simulations show that the new approach allows video sequences to be coded more efficiently than with the standard hybrid approach. Moreover, the new coding scheme results in significantly clearer images than the standard coding approach.>

We present a new inter-frame coding for medical images, in particular magnetic resonance (MR) images. Until now, attempts in using inter-frame redundancies for coding MR images have been unsuccessful. We contend that the main reason for this is twofold: bad inter-frame estimation models and ignoring the thermal noise inherent in MRI. Our inter-frame model is a continuous affine mapping based on (and optimized by) deforming triangles. The inherent noise of MRI is dealt with by using a median filter within the estimation loop. Simulations demonstrate the viability of this algorithm.>

Linear predictive models seek to optimally extract information about a sample of a signal based on some subset of its causal past. Very little work has been done in investigating the importance and choice of this subset (support) in the prediction process. The paper addresses the problem of finding the optimal support for use by a linear predictive model. The authors derive a general result relating the distortion incurred in predicting a sample of a stationary signal based on a causal support in terms of the Wiener coefficients of a larger support and the autocorrelation matrix. Based on the above result, they derive an algorithm which optimally reduces the size of the support by one at each stage. The algorithm is tested on the Barbara image for image estimation and on the football image sequence for pel-recursive motion compensation and is shown to outperform (by large margins in some cases) conventionally chosen supports.>

Overlapped block motion compensation (OBMC) can significantly improve upon the prediction performance of conventional block motion compensation, though at the cost of increased decoder computational complexity. This paper analyzes the complexity costs of OBMC, and offers several modifications to OBMC that significantly reduce its decoder complexity while retaining most of the OBMC performance gain.>

A novel quantization scheme targeted at jointly optimizing the spatial and frequency characterization of the wavelet representation of images was introduced in Xiong et al. (1993) for image compression applications. The present authors extend the concept of joint space-frequency quantization (SFQ) to the more flexible class of wavelet packet representations (Coifman and Wickerhauser, 1992), which are a generalization of the multiresolution decomposition using the wavelet transform. They propose a fast algorithm to jointly search for the best wavelet packet basis and space-frequency quantizer, presenting empirical evidence of its high performance (e.g., for the "Barbara" image coded at 0.5 b/p, they get a 0.7 dB gain in PSNR over the fixed-wavelet based SFQ of Xiong et al. and 1.5 dB over Shapiro's embedded wavelet coder (Shapiro, 1993)).>

We present in this paper two parallel algorithms for the two-dimensional discrete wavelet transform. A mathematical model for the computation vs. communication tradeoff for these algorithms is presented and the scalability of the algorithms is analyzed. The wormhole routing model was used to model the communication costs involved. The algorithms were implemented on the Connection Machine-5 (CM-5^{a}). The theoretical results obtained were validated by the simulations on the CM-5.

We present an estimation-theoretic analysis of motion compensation that, when used with fields of block-based motion vectors, leads to the development of overlapped block algorithms with improved compensation accuracy. Overlapped block motion compensation (OBMC) is formulated as a probabilistic linear estimator of pixel intensities given the limited block motion information available to the decoder. Although overlapped techniques have been observed to reduce blocking artifacts in video coding, this analysis establishes for the first time how (and why) OBMC can offer substantial reductions in prediction error as well, even with no change in the encoder's search and no extra side information. Performance can be further enhanced with the use of state variable conditioning in the compensation process. We describe the design of optimized windows for OBMC. We also demonstrate how, with additional encoder complexity, a motion estimation algorithm optimized for OBMC offers further significant gains in compensation accuracy. Overall mean-square prediction improvements in the range of 16 to 40% (0.8 to 2.2 dB) are demonstrated.

A technique is presented for improving motion field accuracy, while transmitting the same amount of motion information as standard block-based methods (a small amount of additional side information is needed). The approach is developed within the framework of standard block-based methods, but the constraints of the block-based motion field model are relaxed. The method improves motion compensation along boundaries of moving objects by segmenting the motion field of previous frames of the sequence, and using the segmentation to predict the location of motion-field discontinuities in the current frame. Simulations show significant improvement in the accuracy of the motion-compensated frame compared with the standard block-based method and a corresponding decrease in the bit rate required to achieved a fixed image quality.>

A method for determining the optimal linear filters for use in pyramidal decompositions under the minimum mean square error criterion is presented. The pyramidal structure has analysis and interpolation filters. The equations describing the optimal filters are nonlinear in the filter coefficients, making direct solution intractable. However, the optimal filters can be determined by iteratively solving for the optimal analysis and interpolation filters. This leads to a linear system of equations that can be solved using least squares or QR factorization. The optimization is valid in a data dependent or stochastic setting. Convergence and computational complexity of the algorithm are discussed. Some results of optimal linear filters applied to images are presented.>

A fast nearest-neighbor search algorithm is developed which incorporates prior information about input vectors. The prior information comes in the form of a vector from the codebook which is known to be near the input vector, though it may not be the nearest codebook vector. A number of applications are described for which such prior information is available. The algorithm has a very simple structure and can be designed to have very low memory requirements. The new algorithm requires much less computation for constructing precomputed tables than previously proposed algorithms with comparable performance. Simulations show dramatic saving over conventional full search methods.>

A method is described for improving block-based motion-compensation techniques by segmenting blocks into regions corresponding to objects moving with distinct velocities. The method uses standard block motion-estimation techniques and assumes that each distinct velocity within a block is approximated by one of the motion estimates in a neighborhood of that block. A multiresolution approach to segmenting each block is taken. It is based on a Markov random-field model of the segmentation field and incorporates additional constraints which reflect an assumption that the blocks are small relative to objects in the scene. In order to avoid transmitting the segmentation, the method computes the segmentation of previous frames at the receiver and transmitter and predicts the current segmentation from past ones. Experimental results show that the method eliminates most artifacts due to block motion compensation at edges of moving objects and achieves 30-50% reductions in displaced frame-difference energy in frames where reliable motion estimates are available.>