Digital watermarks have previously been proposed for the purposes of copy protection and copy deterrence for multimedia content. In copy deterrence, a content owner (seller) inserts a unique watermark into a copy of the content before it is sold to a buyer. If the buyer sells unauthorized copies of the watermarked content, then these copies can be traced to the unlawful reseller (original buyer) using a watermark detection algorithm. One problem with such an approach is that the original buyer whose watermark has been found on unauthorized copies can claim that the unauthorized copy was created or caused (for example, by a security breach) by the original seller. In this paper, we propose an interactive buyer-seller protocol for invisible watermarking in which the seller does not get to know the exact watermarked copy that the buyer receives. Hence the seller cannot create copies of the original content containing the buyer's watermark. In cases where the seller finds an unauthorized copy, the seller can identify the buyer from a watermark in the unauthorized copy and furthermore the seller can prove this fact to a third party using a dispute resolution protocol. This prevents the buyer from claiming that an unauthorized copy may have originated from the seller.

We describe a watermarking scheme for ownership verification and authentication. Depending on the desire of the user, the watermark can be either visible or invisible. The scheme can detect any modification made to the image and indicate the specific locations that have been modified. If the correct key is specified in the watermark extraction procedure, then an output image is returned showing a proper watermark, indicating the image is authentic and has not been changed since the insertion of the watermark. Any modification would be reflected in a corresponding error in the watermark. If the key is incorrect, or if the image was not watermarked, or if the watermarked image is cropped, the watermark extraction algorithm will return an image that resembles random noise. Since it requires a user key during both the insertion and the extraction procedures, it is not possible for an unauthorized user to insert a new watermark or alter the existing watermark so that the resulting image will pass the test. We present secret key and public key versions of the technique.

We describe a procedure by which Joint Photographic Experts Group (JPEG) compression may be customized for gray-scale images that are to be compressed before they are scaled, halftoned, and printed. Our technique maintains 100% compatibility with the JPEG standard, and is applicable with all scaling and halftoning methods. The JPEG quantization table is designed using frequency-domain characteristics of the scaling and halftoning operations, as well as the frequency sensitivity of the human visual system. In addition, the Huffman tables are optimized for low-rate coding. Compression artifacts are significantly reduced because they are masked by the halftoning patterns, and pushed into frequency bands where the eye is less sensitive. We describe how the frequency-domain effects of scaling and halftoning may be measured, and how to account for those effects in an iterative design procedure for the JPEG quantization table. We also present experimental results suggesting that the customized JPEG encoder typically maintains "near visually lossless" image quality at rates below 0.5 b/pixel (with reference to the number of pixels in the original image) when it is used with bilinear interpolation and either error diffusion or ordered dithering. Based on these results, we believe that in terms of the achieved bit rate, the performance of our encoder is typically at least 20% better than that of a JPEG encoder using the suggested baseline tables.

We examine the question of reconstruction of signals from periodic nonuniform samples. This involves discarding samples from a uniformly sampled signal in some periodic fashion. We give a characterization of the signals that can be reconstructed at exactly the minimum rate once a nonuniform sampling pattern has been fixed. We give an implicit characterization of the reconstruction system, and a design method by which the ideal reconstruction filters may be approximated. We demonstrate that for certain spectral supports the minimum rate can be approached or achieved using reconstruction schemes of much lower complexity than those arrived at by using spectral slicing, as in earlier work. Previous work on multiband signals have typically been those for which restrictive assumptions on the sizes and positions of the bands have been made, or where the minimum rate was approached asymptotically. We show that the class of multiband signals which can be reconstructed exactly is shown to be far larger than previously considered. When approaching the minimum rate, this freedom allows us, in certain cases to have a far less complex reconstruction system.

We propose a public key watermarking algorithm for image integrity verification. This watermark is capable of detecting any change made to an image, including changes in pixel values and image size. This watermark is important for several imaging applications, including trusted camera, legal usage of images, medical archiving of images, news reporting, commercial image transaction, and others. In each of these applications, it is important to verify that the image has not been manipulated and that the image was originated by either a specific camera or a specific user. The verification (the watermark extraction) procedure uses a public key as in public key cryptography, and hence it can be performed by any person without the secure exchange of a secret key. This is very important in many applications (e.g., trusted camera, news reporting) where the exchange of a secret key is either not possible or undesirable.

Digital watermarks have previously been proposed for the purpose of copy protection and copy deterrence for multimedia content. Copy deterrence using digital watermarks is achieved by inserting a unique watermark into each copy of the watermark content sold which could be used to trace unauthorized copies to the erring buyer. One problem with such an approach is the fact that the buyer whose watermark has been found on unauthorized copies can claim that the unauthorized copy was created or caused (for example, by a security breach) by the seller. In this paper we propose an interactive buyer-seller protocol for invisible watermarking in which the seller does not get to know the exact watermarked copy that the buyer receives. Hence the seller cannot create copies of the original content containing the buyers watermark. However, in case the seller finds an unauthorized copy, he/she can identify the buyer from whom this unauthorized copy has originated and furthermore can also prove this fact to a third party by means of a dispute resolution protocol. Hence, the buyer cannot claim that an unauthorized copy may have originated from the seller.

We describe a method for scaling images which have been acquired with a charge coupled device (CCD) sensor. This method produces enlarged images which are sharper than those produced by bilinear interpolation, for comparable complexity. It is based on the observation that the sampling process of a CCD is not a point sampling process, but instead can be modelled as an averaging filter followed by sampling.

We present an algorithm for image browsing systems that embeds the output of binary Floyd-Steinberg (1975) error diffusion, or a low bit-depth gray-scale or color error diffused image into higher bit-depth gray-scale or color error diffused images. The benefits of this algorithm are that a low bit-depth halftoned image can be directly obtained from a higher bit-depth halftone for printing or progressive transmission simply by masking one or more bits off of the higher bit-depth image. The embedding can be done in any bits of the output, although the most significant or the least significant bits are most convenient. Due to constraints on the palette introduced by embedding, the image quality for the higher bit-depth halftone may be reduced. To preserve the image quality, we present algorithms for color palette organization, or binary index assignment, to be used as a preprocessing step to the embedding algorithm.

We suggest an optimization-based method for halftoning that involves looking ahead before a decision for each binary output pixel is made. We first define a mixture distortion criterion that is a combination of a frequency-weighted mean square error (MSE) and a measure depending on the distances between minority pixels in the halftone. A tree-coding approach with the ML-algorithm is used for minimizing the distortion criterion to generate a halftone. While this approach generates halftones of high quality, these halftones are not very amenable to lossless compression. We introduce an entropy constraint into the cost function of the tree-coding algorithm that optimally trades off between image quality and compression performance in the output halftones.

Traditional subband coding, where each subband is encoded independently, has been shown by Fischer (1992) to be suboptimum for encoding Gaussian sources in the rate-distortion sense. We show here that if we use prediction across subbands when encoding Gaussian sources, the resulting coder is asymptotically rate-distortion-optimum at high rate. We also show for Gauss-Markov sources that although the crossband prediction filter in this case is of infinite impulse response, the filter can be implemented very efficiently to high accuracy due to the fast decay of the filter coefficients.

An N-level scalar quantization system for continuous alphabet i.i.d. sources with a pre- and post-filter as suggested by Popat and Zeger (see IEEE Trans. Commun., vol.40, no.11, p.1670, 1992) is considered. The idea is that the pre-filter changes the distribution of the source to approximately Gaussian, which is then quantized by a Lloyd-Max (1960, 1982) quantizer for Gaussian random variables. For many sources, the overall system outperforms one that directly quantizes the sources. We propose an iterative algorithm for designing the optimum filters, to minimize the overall mean squared error between the input and output of the quantization system. It is found experimentally that the design algorithm always converges very rapidly to a solution where the optimum pre- and post-filters are all pass filters. We prove the convergence of the design algorithm for the N=2 case, and conjecture that convergence to the same solution always holds for any N.

We present a new method for digitally interpolating images to higher resolution. It consists of two phases: rendering and correction. The rendering phase is edge-directed. From the low resolution image data, we generate a high resolution edge map by first filtering with a rectangular center-on-surround-off filter and then performing piecewise linear interpolation between the zero crossings in the filter output. The rendering phase is based on bilinear interpolation modified to prevent interpolation across edges, as determined from the estimated high resolution edge map. During the correction phase, we modify the mesh values on which the rendering is based to account for the disparity between the true low resolution data, and that predicted by a sensor model operating on the high resolution output of the rendering phase. The overall process is repeated iteratively. We show experimental results which demonstrate the efficacy of our interpolation method.

We present an algorithm for image browsing systems that embeds a color halftone into another color halftone of a higher bit depth, as well as embedding a grayscale or binary halftone into a grayscale or color halftone. The benefit of this algorithm is that a low bit-depth halftone can be directly obtained from a higher bit-depth halftone for printing of progressive transmission simply by masking one or more bits off of the color halftone. The embedding can be done in any bit of the output depending on the organization of the image palettes, although the most significant or the least significant bits are most convenient. The embedding algorithm that we describe requires the use of scalar quantizers and ordered vector quantizers. We present several methods for color palette organization, or binary index assignment, to be used in conjunction with the embedded color error diffusion algorithm.

We examine the problem of reconstructing a signal from periodic non-uniform samples, i.e. a uniform train from which samples are deleted in some periodic fashion. We develop the necessary and sufficient conditions for reconstruction, both for one and multiple dimensions. We prove that one-dimensional multiband signals which have arbitrary frequency support can be sampled without loss arbitrarily close to the theoretically minimum rate. An important advantage of our approach is the existence of an efficient design procedure for the reconstruction system. We show that the algorithm of projection on convex sets can be used to design the reconstruction filters efficiently. Once the filters are designed, the reconstruction algorithm is non-iterative. We give illustrative examples.

We describe an automated edge enhancement procedure that operates in conjunction with clustered-dot dithering. The goal is not to make weak edges more noticeable, but rather to give the strong edges in the halftoned image a sharper and more natural appearance. Our technique uses a well-known gradient-based edge detection scheme, augmented by pre-smoothing of the input image and post-processing of the resulting edge map. Enhancement is accomplished by means of local adjustments to the dithering threshold values, which result in a tradeoff of grayscale resolution for improved spatial resolution in the vicinity of edges. A rule-based compensation scheme is used to identify and eliminate objectionable pixel patterns caused by the threshold modifications. Experimental results show that our method is successful in improving the appearance of text, line art, and natural scenes rendered by clustered-dot dithering.

We consider a progressively adaptive scalar quantization scheme where the quantizer is adjusted as input samples are processed. The quantizer adjustments are based on an estimated probability density function (pdf) consisting of piecewise polynomials. This pdf is calculated from the bin probabilities that are estimated from quantized samples. The effect of the support of the pdf on the performance of Lloyd-Max quantizers is also examined. Experimental results on the progressively adaptive quantizer for non-stationary sources are shown.

Error diffusion is a procedure for generating high quality bilevel images from continuous-tone images so that both the continuous and halftone images appear similar when observed from a distance. It is well known that certain objectionable patterning artifacts can occur in error-diffused images. Here, we consider a method for adjusting the error-diffusion filter concurrently with the error-diffusion process so that an error criterion is minimized. The minimization is performed using the least mean squares (LMS) algorithm in adaptive signal processing. Using both raster and serpentine scanning, we show that such an algorithm produces better halftone image quality compared to traditional error diffusion with a fixed filter. Based on the adaptive error-diffusion algorithm, we propose a method for constructing a halftone image that can be rendered at multiple resolutions. Specifically, the method generates a halftone from a continuous tone image such that if the halftone is down-sampled, a binary image would result that is also a high quality rendition of the continuous-tone image at a reduced resolution. Such a halftone image is suitable for progressive transmission, and for cases where rendition at several resolutions is required. Cases for noninteger scaling factors are also considered.

An entropy constraint is introduced into a tree coding halftoner, so that one can control the degree of compressibility of the bi-level output images. The algorithm essentially trades image quality with compressibility as indicated by rate distortion theory. We demonstrate that this algorithm can generate halftone images that are of higher quality than error diffusion, and yet are also more amenable to compression than error diffused images.

Discusses the convergence properties of an iterative design algorithm for JPEG quantization tables. The algorithm is useful for generating tables that control, to a specified amount, the proportion of quantization error produced (on average) by the JPEG encoder in each of the 64 DCT frequency bins. An initial table is iteratively improved in such a way that the achieved quantization error profile more closely approximates the desired profile, which might be based on a human vision model or various other criteria. The convergence of the design algorithm is relatively easy to ensure if the desired error profile is modified at each iteration to account for changes in the achieved error values. Adjustments to the quantization table entries may be made according to several different schemes. We propose a successive approximation method that is guaranteed to converge after no more than eight iterations, and also discuss some alternative strategies.

We propose a new halftoning approach that ensures the average graylevels in a grayscale image to be equal to that of a halftone over corresponding local neighborhoods, where the neighborhoods are taken with respect to a quad-tree structure. The halftoning algorithm first determines the total number of black and white dots in the entire halftone using a global mean requirement. It then distributes the dots to various local neighborhoods of the halftone using a multiscale dot distribution technique over the nodes of a quad-tree. We show that such a halftoning method produces high quality halftones particularly in the rendering of details.

Two different approaches in the inverse halftoning of error-diffused images are considered. The first approach uses linear filtering and statistical smoothing that reconstructs a gray-scale image from a given error-diffused image. The second approach can be viewed as a projection operation, where one assumes the error diffusion kernel is known, and finds a gray-scale image that will be halftoned into the same binary image. Two projection algorithms, viz., minimum mean square error (MMSE) projection and maximum a posteriori probability (MAP) projection, that differ on the way an inverse quantization step is performed, are developed. Among the filtering and the two projection algorithms, MAP projection provides the best performance for inverse halftoning. Using techniques from adaptive signal processing, we suggest a method for estimating the error diffusion kernel from the given halftone. This means that the projection algorithms can be applied in the inverse halftoning of any error-diffused image without requiring any a priori information on the error diffusion kernel. It is shown that the kernel estimation algorithm combined with MAP projection provide the same performance in inverse halftoning compared to the case where the error diffusion kernel is known.

Describes a procedure by which JPEG compression may be customized for grayscale images that are to be compressed, halftoned, and printed. The technique maintains 100% compatibility with the JPEG standard, and is applicable with any halftoning algorithm. The JPEG quantization table is designed using frequency-domain characteristics of the halftoning patterns and the human visual system, and the Huffman tables are optimized for low-rate coding. The authors present experimental results demonstrating that the customized JPEG encoder offers a significant performance advantage over a coder that uses the default quantization and Huffman tables. The results also show that the customized encoder typically achieves rates in the range 0.13-0.25 bits per pixel (image dependent) with practically no visible compression artifacts in the printed images.>

Error diffusion is a method for generating high quality bi-level images from continuous tone images. It is well known that certain objectionable patterning artifacts can occur in error diffused images. The author considers a method for adjusting the error diffusion kernel dynamically so that a local frequency weighted square error criterion is minimized. It can be shown that such an error criterion can be expressed as a linear function of the error diffusion filter. One can then use, for example, the LMS algorithm to adjust the filter coefficients concurrently with the halftoning process so that the distortion is minimized. Such an algorithm produces better halftone image quality compared to traditional error diffusion with a fixed filter.>

We suggest an optimization based method for halftoning that involves looking ahead into the future before a decision for each binary output pixel is made. We first define a mixture distortion criterion that is a combination of a frequency weighted mean square error and a measure depending on the distances between minority pixels in the halftone. A tree coding approach with the ML-algorithm is used for minimizing the distortion criterion and generate a halftone.>

Subband and wavelet-based image compression can be viewed as frequency oriented techniques because each subimage in the decomposition is essentially a band-pass version of the original image. The authors suggest a space-frequency partition scheme to fully exploit the excellent localization properties of wavelets in both the spatial and frequency domains. Due to the relatively large number of blocks in this partition compared with traditional subband coders, the rate required for communicating the quantizer configurations must be taken into account. An iterative bit allocation algorithm is suggested that minimizes the mean square error given the overall rate for specifying the quantization configuration and for quantizing the wavelet coefficients. Images encoded using scalar quantization under this scheme show improvements in PSNR versus rate over traditional subband and wavelet-based methods.

The discrete wavelet decomposition of second-order harmonizable random processes is considered. The deterministic wavelet decomposition of a complex exponential function is examined, where its pointwise and bounded convergence to the function is proved. This result is then used for establishing the stochastic wavelet decomposition of harmonizable processes. The similarities and differences between the wavelet decompositions of general harmonizable processes and a subclass of processes having no spectral mass at zero frequency, e.g., those that are wide-sense stationary and have continuous power spectral densities, are also investigated. The relationships between the harmonization of a process and that of its wavelet decomposition are examined. Finally, certain linear operations such as addition, differentiation, and linear filtering on stochastic wavelet decompositions are considered. It is shown that certain linear operations can be performed term by term with the decomposition.>

A differential chain code implementation of the basic eight-directional and N-ring chain code for the encoding of line drawings is considered. Several distortion and rate criteria are considered, and they are evaluated for the special case of encoding infinite straight lines. These results indicate that the differential code outperforms ring codes and the ring delta code. Using a linear decoding filter for reconstructing a smoothed approximation to the original line is also considered. Optimal reconstruction filters for infinite straight lines at various angles are derived. An angle-invariant reconstruction filter that minimizes the expected square distortion taken over all angles is derived. The overall performance using this filter is close to that of the optimum filter. Furthermore, the impulse response of the angle-invariant filter is approximately rectangular, which can lead to simple hardware implementations.>

The author considers the error resulting in the computation of multivariable functions h(X/sub 1/, X, . . ., X/sub n/), where all the X/sub i/s are only available in the quantized form. In image processing and computer vision problems, the variables are typically a mixture of the spatial coordinates and the intensity levels of objects in an image. A method is introduced using a first-order Taylor series expansion together with a periodic extension of the resulting expression and its Fourier series representation so that the moments and the probability distribution function of the error can be computed in closed form. This method only requires that the joint probability density function of X/sub i/s be known and makes no assumption on the behavior on the quantization errors of the variables. Examples are also given where these results are applied.>

A method is suggested for implementing finite impulse response (FIR) digital filters where both the input signal and the impulse response are encoded using sigma-delta modulation. This filter structure can be built using simple hardware and hence can lead to efficient implementations. The error spectrum due to the encoding/decoding processes in the filter structure is derived. The implementation issues for this filter structure are also discussed.>

The response of a single-loop sigma-delta modulator to an independent identically distributed (i.i.d.) Gaussian input signal is analyzed. A continuous-time stochastic model is developed and the connection of the model to the system is described. A condition is given so that the difference between the behavior of the model and that of the true system can be made arbitrarily small. Theories from renewal and Wiener processes are applied to show the convergence and mixing properties of the output sequence. Also derived is the power spectrum of the quantization noise. Compared to the spectrum when the input is DC, the i.i.d. Gaussian random process smears the discrete spectrum into band structures.>

An exact nonlinear difference equation is derived and solved for a simple sigma-delta modulator consisting of a discrete-time integrator and a binary quantizer inside a single feedback loop and an arbitrary input signal. It is shown that the system can be represented as an affine operation (discrete-time integration of a biased input) followed by a memoryless nonlinearity. An extension of the transform method for the analysis of nonlinear systems is applied to obtain formulas for first- and second-order time-average moments of the binary quantization noise, including the sample mean, energy, and autocorrelation. The results are applied to the special case of a sinusoidal input signal to evaluate these time averages and the power spectrum. In the limit of large oversampling ratios, the marginal moments behave as if the quantization noise had a uniform distribution. The spectrum is neither white nor continuous, however, even in the limit of large oversampling ratios.>

A theoretical basis is provided for multistage sigma-delta modulation (MSM), which is a cascade realization of several single-loop sigma-delta modulators with a linear combinatorial network. Equations are derived describing the output and the quantization noise of MSM for an arbitrary input signal, and the noise-shaping characteristic of MSM is investigated. The spectral characteristics of an m-stage sigma-delta modulator with both DC and sinusoidal inputs are developed. For both types of inputs the binary quantizer noise of the mth (m>or=3) quantizer, which appears at the output as an mth order difference, is asymptotically white, uniformly distributed, and uncorrelated with the input level. It is also found that for an m-stage sigma-delta quantizer with either an ideal low-pass filter or a sinc/sup m+1/ filter decoder, the average quantization noise of the system is inversely proportional to the (2m+1)th power of the oversampling ratio. This implies that the high-order systems are favourable in terms of the trade-off between the quantization noise and oversampling ratio. Simulation results are presented to support the theoretical analysis.>