Search

An analysis of steganographic systems subject to the following perfect undetectability condition is presented in this paper. Following embedding of the message into the covertext, the resulting stegotext is required to have exactly the same probability distribution as the covertext. Then no statistical test can reliably detect the presence of the hidden message. We refer to such steganographic schemes as perfectly secure. A few such schemes have been proposed in recent literature, but they have vanishing rate. We prove that communication performance can potentially be vastly improved; specifically, our basic setup assumes independent and identically distributed (i.i.d.) covertext, and we construct perfectly secure steganographic codes from public watermarking codes using binning methods and randomized permutations of the code. The permutation is a secret key shared between encoder and decoder. We derive (positive) capacity and random-coding exponents for perfectly secure steganographic systems. The error exponents provide estimates of the code length required to achieve a target low error probability. In some applications, steganographic communication may be disrupted by an active warden, modeled here by a compound discrete memoryless channel (DMC). The transmitter and warden are subject to distortion constraints. We address the potential loss in communication performance due to the perfect-security requirement. This loss is the same as the loss obtained under a weaker order-1 steganographic requirement that would just require matching of first-order marginals of the covertext and stegotext distributions. Furthermore, no loss occurs if the covertext distribution is uniform and the distortion metric is cyclically symmetric; steganographic capacity is then achieved by randomized linear codes. Our framework may also be useful for developing computationally secure steganographic systems that have near-optimal communication performance. Index Terms--Binuing codes, capacity, error exponents, randomized codes, reliability function, secret communication, steganography, timing channels, universal codes, watermarking.

Capacity formulas and random-coding exponents are derived for a generalized family of Gerfand--Pinsker coding problems. These exponents yield asymptotic upper bounds on the achievable log probability of error. In our model, information is to be reliably transmitted through a noisy channel with finite input and output alphabets and random state sequence, and the channel is selected by a hypothetical adversary. Partial information about the state sequence is available to the encoder, adversary, and decoder. The design of the transmitter is subject to a cost constraint. Two families of channels are considered: 1) compound discrete memoryless channels (CDMC), and 2) channels with arbitrary memory, subject to an additive cost constraint, or more generally, to a hard constraint on the conditional type of the channel output given the input. Both problems are closely connected. The random-coding exponent is achieved using a stacked binning scheme and a maximum penalized mutual information decoder, which may be thought of as an empirical generalized maximum a posteriori decoder. For channels with arbitrary memory, the random-coding exponents are larger than their CDMC counterparts. Applications of this study include watermarking, data hiding, communication in presence of partially known interferers, and problems such as broadcast channels, all of which involve the fundamental idea of binning. Index Terms--Arbitrarily varying channels, broadcast channels, capacity, channel coding with side information, data hiding, error exponents, maximum a posteriori probability (MAP) decoding, method of types, random binning, randomized codes, reliability function, universal coding and decoding, watermarking.

Fundamental performance bounds for statistical estimation of parametric surfaces embedded in [R.sup.3], in which the reconstruction of the shape of binary or homogenous objects could be represented by asymptotic global confidence regions that facilitate geometric inference and optimization of the imaging system is derived. Simulation results reveal the tightness of the resulting bound and the efficiency of the three-dimensional global confidence region approach.

The Karhunen-Loeve transform (KLT) is known to be optimal for high-rate transform coding of Gaussian vectors for both fixed-rate and variable-rate encoding. The KLT is also known to be suboptimal for some non-Gaussian models. This paper proves high-rate optimality of the KLT for variable-rate encoding of a broad class of non-Gaussian vectors: Gaussian vector-scale mixtures (GVSM), which extend the Gaussian scale mixture (GSM) model of natural signals. A key concavity property of the scalar GSM (same as the scalar GVSM) is derived to complete the proof. Optimality holds under a broad class of quadratic criteria, which include mean-squared error (MSE) as well as generalized f-divergence loss in estimation and binary classification systems. Finally, the theory is illustrated using two applications: signal estimation in multiplicative noise and joint optimization of classification/reconstruction systems. Index Terms--Chernoff distance, classification, estimation, f-divergence, Gaussian scale mixture, high-resolution quantization, Karhunen-Loeve transform (KLT), mean-squared error (MSE), multiplicative noise, quadratic criterion.

Modulo lattice additive noise (MLAN) channels appear in the analysis of structured binning codes for Costa's dirty-paper channel and of nested lattice codes for the additive white Gaussian noise (AWGN) channel. In this paper, we derive a new lower bound on the error exponents of the MLAN channel. With a proper choice of the shaping lattice and the scaling parameter, the new lower bound coincides with the random-coding lower bound on the error exponents of the AWGN channel at the same signal-to-noise ratio (SNR) in the sphere-packing and straight-line regions. This result implies that, at least for rates close to channel capacity, 1) writing on dirty paper is as reliable as writing on clean paper; and 2) lattice encoding and decoding suffer no loss of error exponents relative to the optimal codes (with maximum-likelihood decoding) for the AWGN channel. Index Terms--Additive white Gaussian noise (AWGN) channel, Costa's dirty-paper channel, error exponents, lattice decoding, modulo lattice additive noise (MLAN) channel, nested lattice codes.

A broad set of sufficient conditions that guarantees the existence of the maximum entropy (maxent) distribution consistent with specified bounds on certain generalized moments is derived. Most results in the literature are either focused on the minimum cross-entropy distribution or apply only to distributions with a bounded-volume support or address only equality constraints. The results of this work hold for general moment inequality constraints for probability distributions with possibly unbounded support, and the technical conditions are explicitly on the underlying generalized moment functions. An analytical characterization of the maxent distribution is also derived using results from the theory of constrained optimization in infinite-dimensional normed linear spaces. Several auxiliary results of independent interest pertaining to certain properties of convex coercive functions are also presented. Index Terms--Coercive functions, constrained optimization, convex analysis, cross-entropy, differential entropy, maximum entropy methods.

A joint hashing/watermarking scheme is developed in which a short hash of the host signal is available to a detector and potential applications include content tracking on public networks and forensic identification. The joint hashing/watermarking scheme outperforms the traditional hashless watermarking technique.

Rates of reliable transmission of hidden information are derived for watermarking problems involving parallel Gaussian sources, which are often used to model host images and audio signals. Constraints are imposed on the average squared-error distortion that can be introduced by the information hider and by the attacker. When distortions are measured with respect to the original host data, the optimal covert and attack channels are two banks of Gaussian test channels. The solution to the watermarking game involves an optimal allocation of distortions by the information hider and by the attacker to the different channels. A fast algorithm is given for computing the optimal solution based on duality theory. For each channel, we derive analytical expressions for two asymptotic regimes: weak and strong host signals. Finally, we extend these results to the class of stationary Gaussian host signals with bounded, continuous spectral density. The analysis also provides an upper bound on watermarking capacity for non-Gaussian host signals. Index Terms--Channel capacity, game theory, parallel Gaussian channels, random processes, rate-distortion theory, watermarking.

A game-theoretic formulation of the watermark embedding problems is presented. Its solution is derived for Gaussian signals, spread-spectrum watermarks, and attacks.

An equivalence is established between two models of signal estimation under modeling uncertainty. The methods are: set-theoretic estimation; and maximum entropy (maxent) MAP estimation.

An information-theoretic analysis of information hiding is presented in this paper, forming the theoretical basis for design of information-hiding systems. Information hiding is an emerging research area which encompasses applications such as copyright protection for digital media, watermarking, fingerprinting, steganography, and data embedding. In these applications, information is hidden within a host data set and is to be reliably communicated to a receiver. The host data set is intentionally corrupted, but in a covert way, designed to be imperceptible to a casual analysis. Next, an attacker may seek to destroy this hidden information, and for this purpose, introduce additional distortion to the data set. Side information (in the form of cryptographic keys and/or information about the host signal) may be available to the information hider and to the decoder. We formalize these notions and evaluate the hiding capacity, which upper-bounds the rates of reliable transmission and quantifies the fundamental tradeoff between three quantities: the achievable information-hiding rates and the allowed distortion levels for the information hider and the attacker. The hiding capacity is the value of a game between the information hider and the attacker. The optimal attack strategy is the solution of a particular rate-distortion problem, and the optimal hiding strategy is the solution to a channel-coding problem. The hiding capacity is derived by extending the Gel'fand-Pinsker theory of communication with side information at the encoder. The extensions include the presence of distortion constraints, side information at the decoder, and unknown communication channel. Explicit formulas for capacity are given in several cases, including Bernoulli and Gaussian problems, as well as the important special case of small distortions. In some cases, including the last two above, the hiding capacity is the same whether or not the decoder knows the host data set. It is shown that many existing information-hiding systems in the literature operate far below capacity. Index Terms--Channel capacity, cryptography, fingerprinting, game theory, information hiding, network information theory, optimal jamming, randomized codes, rate-distortion theory, steganography, watermarking.

A general method is described for computing Cramer-Rao bounds for parametric shape estimation in linear inverse problems, such as computed tomography.

A model for image watermarking and data hiding is proposed. New theoretical results are used to characterize the capacity of data-hiding and image watermarking systems.

This paper derives bounds on the performance of statistical object recognition systems, wherein an image of a target is observed by a remote sensor. Detection and recognition problems are modeled as composite hypothesis testing problems involving nuisance parameters. We develop information-theoretic performance bounds on target recognition based on statistical models for sensors and data, and examine conditions under which these bounds are tight. In particular, we examine the validity of asymptotic approximations to probability of error in such imaging problems. Problems involving Gaussian, Poisson, and multiplicative noise, and random pixel deletions are considered, as well as least-favorable Gaussian clutter. A sixth application involving compressed sensor image data is considered in some detail. This study provides a systematic and computationally attractive framework for analytically characterizing target recognition performance under complicated, non-Gaussian models and optimizing system parameters. Index Terms--Object recognition, automatic target recognition, imaging sensors, multisensor data fusion, data compression, performance metrics.

An information-theoretic analysis of statistical dependencies between image wavelet coefficients is presented. Dependencies are measured using mutual information.

A study was conducted to evaluate the efficiency of the design of signal-adapted finite impulse response (FIR) paraunitary filter banks which are based on the energy compaction criterion. The innovative filter banks' optimal filters can be utilized in solving linear semi-infinite programming problems. However, the method of designing such optimal filter banks may not be appropriate in multidimensional FIR filter banks due to lack of spectral factorization.

The image sequences in many image processing and computer vision applications have problems associated with the accurate modeling and estimation of motion. The use of multiscale models is proposed as a first step towards representing, computing and encoding motion fields. A systematic approach to motion field estimation and coding is presented.

This study shows that designing an orthogonal FIR, quadrature-mirror filter (QMF) bank to maximize the coding gain is much simpler that the previous operation. The coding gain depends on the product filter which leads to a stable class of linear optimization problem termed as linear semi-infinite programming (SIP). The original filter is obtained by deflation and spectral factorization of the product filter. A comprehensive analysis of the SIP problem is also presented using numerical algorithm.

A novel technique enhances nonorthogonal multiresolution transforms for image encoding by minimizing the L(super 2) reconstruction error. This is done on the possible set of encoded images. A multiscale relaxation algorithm computes the suboptimal solutions by using intra- and inter-scale noise feedback filters, and this maximizes the signal-to-noise ratio. The coding problem involves high-dimensional discrete optimization.

The logarithm of an unknown power spectrum S(f) of a stationary random process is represented by a nonparametric method based on wavelet representation. The estimation of S(f) of a stationary random process is a nonparametric statistical estimation problem. The statistically significant constituents of the logarithm of S(f) at different resolution levels are captured by this approach. The proposed wavelet thresholding technique helps solve the nonparametric statistical estimation problem.

We present new methods for computing fundamental performance limits for two-dimensional (2-D) parametric shape estimation in nonlinear inverse scattering problems with an application to passive radar imaging. We evaluate Cramer-Rao lower bounds (CRB) on shape estimation accuracy using the domain derivative technique from nonlinear inverse scattering theory. The CRB provides an unbeatable performance limit for any unbiased estimator, and under fairly mild regularity conditions is asymptotically achieved by the maximum likelihood estimator (MLE). The resultant CRBs are used to define an asymptotic global confidence region, centered around the true boundary, in which the boundary estimate lies with a prescribed probability. These global confidence regions conveniently display the uncertainty in various geometric parameters such as shape, size, orientation, and position of the estimated target and facilitate geometric inferences. Numerical simulations are performed using the layer approach and the Nystrom method for computation of domain derivatives and using Fourier descriptors for target shape parameterization. This analysis demonstrates the accuracy and generality of the proposed methods. Index Terms--Cramer-Rao bounds, Fourier descriptors, global confidence regions, nonlinear inverse scattering, passive radar imaging, shape estimation.

Most motion-compensation methods dealt with in the literature make strong assumptions about the smoothness of the underlying motion field. For instance, block-matching algorithms assume a blockwise-constant motion field and are adequate for translational motion models; control-grid interpolation assumes a blockwise bilinear motion field and captures zooming and warping fairly well. Time-varying imagery, however, often contains both types of motion (as well as others), and hence exhibits a high degree of spatial variability of its motion-field smoothness properties. We develop a simple method to spatially adapt the smoothness of the motion field. The proposed method demonstrates substantial improvements in video quality over a wide range of bit rates. To this end, we introduce the notion of a motion field that is characterized by a set of labels. The labels provide the flexibility to adaptively switch between two different motion models locally. The individual motion models have very different smoothness properties. The switched framework for motion compensation performs significantly better than each of its constituent motion models, in terms of both visual quality and signal-to-noise ratio (0.3--0.7 dB on the average). Finally, we develop an extension of this method that enhances the overlapped block motion compensation scheme by allowing spatial adaptation of the window function. Index Terms--Block matching, interpolation methods, motion estimation, overlapped block motion compensation, video compression.

We introduce confidence region techniques for analyzing and visualizing the performance of two-dimensional parametric shape estimators. Assuming an asymptotically normal and efficient estimator for a finite parameterization of the object boundary, Cramer-Rao bounds are used to define an asymptotic confidence region, centered around the true boundary. Computation of the probability that an entire boundary estimate lies within the confidence region is a challenging problem, because the estimate is a two-dimensional nonstationary random process. We derive lower bounds on this probability using level crossing statistics. The same bounds also apply to asymptotic confidence regions formed around the estimated boundaries, lower-bounding the probability that the entire true boundary lies within the confidence region. The results make it possible to generate asymptotic confidence regions for arbitrary prescribed probabilities. These asymptotic global confidence regions conveniently display the uncertainty in various geometric parameters such as shape, size, orientation, and position of the estimated object, and facilitate geometric inferences. Numerical simulations suggest that the new bounds are quite tight. Index Terms--Confidence regions, Cramer-Rao bounds, geometric inference, imaging, level crossing probability, maximum-likelihood estimation, parametric shape estimation, random process.

We apply the complexity-regularization principle to statistical ill-posed inverse problems in imaging. The class of problems studied includes restoration of images corrupted by Gaussian or Poisson noise and nonlinear transformations. We formulate a natural distortion measure in image space and develop nonasymptotic bounds on estimation performance in terms of an index of resolvability that characterizes the compressibility of the true image. These bounds extend previous results that were obtained in the literature under simpler observational models. The notion of asymptotic imaging experiment is clarified and used to characterize consistency and convergence rates of the estimator. We present a connection between complexity-regularized estimation and rate-distortion theory, which suggests a method for constructing optimal codebooks. However, the design of computationally tractable complexity-regularized image estimators is quite challenging; we present some of the issues involved and illustrate them with a Poisson-imaging application. Index Terms--Compression, image compression, image restoration, imaging, inverse problems, maximum-likelihood estimation, minimum description length principle, nonparametric estimation, rate-distortion theory.

A new method for image denoising is proposed, based on complexity regularization, as an alternative to L2, l1 and Besov regularization techniques.

Research describing the design of subband coders is presented. In particular the coders are optimized for rate distortion and the use of scalar quantizers and computational algorithms is developed.

We consider the problems of motion-compensated frame interpolation (MCFI) and bidirectional prediction in a video coding environment. These applications generally require good motion estimates at the decoder. In this paper, we use a multiscale optical-flow-based motion estimator that provides smooth, natural motion fields under bit-rate constraints. These motion estimates scale well with change in temporal resolution and provide considerable flexibility in the design and operation of coders and decoders. In the MCFI application, this estimator provides excellent interpolated frames that are superior to those of conventional motion estimators, both visually and in terms of peak signal-to-noise ratio (PSNR). We also consider the effect of occlusions in the bidirectional prediction application and introduce a dense label field that complements our motion estimator. This label field enables us to adaptively weight the forward and backward predictions and gives us substantial visual and PSNR improvements in the covered/uncovered regions of the sequence. Index Terms - Bidirectional prediction, frame interpolation, motion compensation, motion estimation, video compression.

A new-best basis design, in which filter banks, subband tree structure and quantizers are chosen to optimize rate-distortion performance, is presented. The new design integrated two different but complementary approaches to best-basis design. One method involves the use of fast algorithms to determine the best bases in an operational rate-distortion sense, while the other method involves the design of filter banks that optimize energy compaction for a single signal or a class of signals.

Recent research on universal and minimax wavelet shrinkage and thresholding methods has demonstrated near-ideal estimation performance in various asymptotic frameworks. However, image processing practice has shown that universal thresholding methods are outperformed by simple Bayesian estimators assuming independent wavelet coefficients and heavy-tailed priors such as generalized Gaussian distributions (GGD's). In this paper, we investigate various connections between shrinkage methods and Maximum A Posteriori (MAP) estimation using such priors. In particular, we state a simple condition under which MAP estimates are sparse. We also introduce a new family of complexity priors based upon Rissanen's universal prior on integers. One particular estimator in this class outperforms conventional estimators based on earlier applications of the Minimum Description Length (MDL) principle. We develop analytical expressions for the shrinkage rules implied by GGD and complexity priors. This allows us to show the equivalence between universal hard thresholding, MAP estimation using a very heavy-tailed GGD, and MDL estimation using one of the new complexity priors. Theoretical analysis supported by numerous practical experiments shows the robustness of some of these estimates against misspecifications of the prior - a basic concern in image processing applications. Index Terms - Bayesian estimation, image processing, Minimum Description Length (MDL) principle, wavelets.