The vulnerability of deep neural networks against adversarial attacks,i.e., imperceptible adversarial perturbations can easily give rise to wrong predictions, poses a huge threat to the security of their real-world deployments. In this paper, a novel Adversarial Detection method via Disentangling Natural images and Perturbations (ADDNP) is proposed. Compared to natural images that can typically be modeled by lower-dimensional subspaces or manifolds, the distributions of adversarial perturbations are much more complex,e.g., one normal example’s adversarial counterparts generated by different attack strategies can be significantly distinct. The proposed ADDNP exploits such distinct properties for the detection of adversarial attacks amongst normal examples. Specifically, we use a dual-branch disentangling framework to encode natural images and perturbations of inputs separately, followed by joint reconstruction. During inference, the reconstruction discrepancy (RD) measured in the learned latent feature space is used as an indicator of adversarial perturbations. The proposed ADDNP algorithm is evaluated on three popular datasets,i.e., CIFAR-10, CIFAR-100, andminiImageNet with increasing data complexity, across multiple popular attack strategies. Compared to the existing and state-of-the-art detection methods, ADDNP has demonstrated promising performance on adversarial detection, with significant improvements on more challenging datasets.

Metric learning requires the identification of far-apart similar pairs and close dissimilar pairs during training, and this is difficult to achieve with unlabeled data because pairs are typically assumed to be similar if they are close. We present a novel metric learning method which circumvents this issue by identifying hard negative pairs as those which obtain dissimilar labels via label propagation (LP), when the edge linking the pair of data is removed in the affinity matrix. In so doing, the negative pairs can be identified despite their proximity, and we are able to utilize this information to significantly improve LP’ s ability to identify far-apart positive pairs and close negative pairs. This results in a considerable improvement in semi-supervised metric learning performance as evidenced by recall, precision and Normalized Mutual Information (NMI) performance metrics on Content-based Information Retrieval (CBIR) applications.

We present a supervised semantic hashing framework, named Label-Consistent Generalized Hashing (LCGH). The main novelty of LCGH is the explicit retention of information which may be irrelevant in training, but possibly useful for generalizing to unseen test classes. This is in stark contrast to typical semantic hashing methods which seek to remove redundant feature information from their hash codes in order to maximize the margin between hash codes of dissimilar data. This typical strategy leaves hash codes narrowly viable for discerning between training classes, and inadequate in discriminating between unseen test classes. Instead of limiting the information content of hash codes to those provided by the training labels, LCGH enhances its codes with information content from both supervised and unsupervised sources, improving their ability to discriminate across a wider range of data. To do so, LCGH builds upon the foundation of first agreeing with the provided training labels (label-consistency) and then incorporating possibly useful information using a reconstruction loss. In this way, LCGH respects the reliably given label information before exploring the addition of possibly useful ones. The outcome is a hashing scheme with slightly weaker within-domain (training and test classes are the same) retrieval performance, but much stronger cross-domain (training and test classes are disjoint) performance.

This paper proposes a locally-optimal generalized likelihood ratio test (LO-GLRT) for detecting targeted attacks on a classifier, where the attacks add a norm-bounded targeted universal adversarial perturbation (UAP) to the classifier’s input. The paper includes both an analysis of the test as well as its empirical evaluation. The analysis provides an expression for the approximate lower bound of the detection probability, and the empirical evaluation shows this approximation to be similar to the actual detection probability. Since the LO-GLRT requires the score function of the input distribution, which is usually unknown in practice, we study the LO-GLRT for a learned surrogate input distribution. Specifically, we use a Gaussian distribution over the input subvectors as the surrogate distribution, for its mathematical tractability and computational efficiency. We evaluate the detector for several popular image classifiers and datasets, and compare the statistical and computational performance with the perturbation rectifying network (PRN) detector, another successful approach for detecting the UAPs. The LO-GLRT outperforms the PRN detector on both counts, with a running time at least 100 times lower than that of the PRN detector.

Deep learning image classifiers are known to be vulnerable to small adversarial perturbations of input images. In this paper, we derive the locally optimal generalized likelihood ratio test based detector for detecting stochastic targeted universal adversarial perturbations to a classifier’s input. We employ a two-stage process to learn the detector’s parameters, which involves unsupervised maximum likelihood estimation followed by supervised training and demonstrates better performance of the detector compared to other detection methods on several popular image classification datasets.

Three of the key challenges in semi-supervised metric learning are the difficulty in sampling loss-producing triplets, the difficulty in locating similar data which are faraway from the anchor points, and the difficulty in making the model robust to noisy predicted pseudolabels. We propose a method which allows the use of class-representative anchors (proxies), and avoids the computational costs associated with triplet sampling. Our new semi-supervised metric learning method propagates labels along mutual nearest neighbor pairs, so that faraway similar data can be drawn to the anchors, while data which are not along these paths (and hence not on the same manifold as the anchors) can be pushed away from these anchors. By assessing the number of different labels which were propagated to the same point, we obtain an estimate of the probability that our prediction of the pseudolabel is accurate, and hence able to attenuate the effect of uncertain pseudolabels on our model by factoring in the confidence of these predictions. We show the superiority of our method over various state-of-the-art methods on four diverse public datasets.

Robust machine learning formulations have emerged to address the prevalent vulnerability of deep neural networks to adversarial examples. Our work draws the connection between optimal robust learning and the privacy-utility tradeoff problem, which is a generalization of the rate-distortion problem. The saddle point of the game between a robust classifier and an adversarial perturbation can be found via the solution of a maximum conditional entropy problem. This information-theoretic perspective sheds light on the fundamental tradeoff between robustness and clean data performance, which ultimately arises from the geometric structure of the underlying data distribution and perturbation constraints.

Adversarial examples have recently exposed the severe vulnerability of neural network models. However, most of the existing attacks require some form of target model information (i.e., weights/model inquiry/architecture) to improve the efficacy of the attack. We leverage the information-theoretic connections between robust learning and generalized rate-distortion theory to formulate a universal adversarial example (UAE) generation algorithm. Our algorithm trains an offline adversarial generator to minimize the mutual information between the label and perturbed data. At the inference phase, our UAE method can efficiently generate effective adversarial examples without high computation cost. These adversarial examples in turn allow for developing universal defenses through adversarial training. Our experiments demonstrate promising gains in improving the training efficiency of conventional adversarial training.

We present a supervised semantic hashing method which uses a variational autoencoder to represent each database image sample as a product Bernoulli distribution. We show that the probability parameters approach extreme values during training, allowing them to be used directly as hash bits. We show how our method allows balanced bits to be directly specified, and is superior to state-of-the-art methods across four datasets.

Various adversarial audio attacks have recently been developed to fool automatic speech recognition (ASR) systems. We here propose a defense against such attacks based on the uncertainty introduced by dropout in neural networks. We show that our defense is able to detect attacks created through optimized perturbations and frequency masking on a state-of-the-art end-to-end ASR system. Furthermore, the defense can be made robust against attacks that are immune to noise reduction. We test our defense on Mozilla's CommonVoice dataset, the UrbanSound dataset, and an excerpt of the LibriSpeech dataset, showing that it achieves high detection accuracy in a wide range of scenarios.

High-quality video frame interpolation often necessitates accurate motion estimation, which can be obtained using modern optical flow methods. In this paper, we use the recently proposed Local All-Pass (LAP) algorithm to compute the optical flow between two consecutive frames. The resulting flow field is used to perform interpolation using cubic splines. We compare the interpolation results against a well-known optical flow estimation algorithm as well as against a recent con-volutional neural network scheme for video frame interpolation. Qualitative and quantitative results show that the LAP algorithm performs fast, high-quality video frame interpolation, and perceptually outperforms the neural network and the Lucas-Kanade method on a variety of test sequences.

In this article, we deal with the problem of understanding human-to-human interactions as a fundamental component of social events analysis. Inspired by the recent success of multi-modal visual data in many recognition tasks, we propose a novel approach to model dyadic interaction by means of features extracted from synchronized 3D skeleton coordinates, depth, and Red Green Blue (RGB) sequences. From skeleton data, we extract new view-invariant proxemic features, named Unified Proxemic Descriptor (UProD), which is able to incorporate intrinsic and extrinsic distances between two interacting subjects. A novel key frame selection method is introduced to identify salient instants of the interaction sequence based on the joints’ energy. From Red Green Blue Depth (RGBD) videos, more holistic CNN features are extracted by applying an adaptive pre-trained Convolutional Neural Networks (CNNs) on optical flow frames. For better understanding the dynamics of interactions, we expand the boundaries of dyadic interactions analysis by proposing a fundamentally new modeling for non-treated problem aiming to discern the active from the passive interactor. Extensive experiments have been carried out on four multi-modal and multi-view interactions datasets. The experimental results demonstrate the superiority of our proposed techniques against the state-of-the-art approaches.

Random forest has emerged as a powerful classification technique with promising results in various vision tasks including image classification, pose estimation and object detection. However, current techniques have shown little improvements in visual tracking as they mostly rely on piece wise orthogonal hyperplanes to create decision nodes and lack a robust incremental learning mechanism that is much needed for online tracking. In this paper, we propose a discriminative tracker based on a novel incremental oblique random forest. Unlike conventional orthogonal decision trees that use a single feature and heuristic measures to obtain a split at each node, we propose to use a more powerful proximal SVM to obtain oblique hyperplanes to capture the geometric structure of the data better. The resulting decision surface is not restricted to be axis aligned and hence has the ability to represent and classify the input data better. Furthermore, in order to generalize to online tracking scenarios, we derive incremental update steps that enable the hyperplanes in each node to be updated recursively, efficiently and in a closed-form fashion. We demonstrate the effectiveness of our method using two large scale benchmark datasets (OTB-51 and OTB-100) and show that our method gives competitive results on several challenging cases by relying on simple HOG features as well as in combination with more sophisticated deep neural network based models. The implementations of the proposed random forest are available at https://github.com/ZhangLeUestc/ Incremental-Oblique-Random-Forest.

We study the convergence properties of a general inertial first-order proximal splitting algorithm for solving nonconvex nonsmooth optimization problems. Using the Kurdyka-Łojaziewicz (KL) inequality we establish new convergence rates which apply to several inertial algorithms in the literature. Our basic assumption is that the objective function is semialgebraic, which lends our results broad applicability in the fields of signal processing and machine learning. The convergence rates depend on the exponent of the “desingularizing function” arising in the KL inequality. Depending on this exponent, convergence may be finite, linear, or sublinear and of the form O(k-p) for p > 1.

In rate-distortion theory, three main types of distortion constraints have been popular: average, pointwise, and excess probability (aka ϵ-fidelity). A new setup is proposed here, which is suitable for fixed-length codes and constrains the distribution (profile) of distortions. This is accomplished by imposing multiple constraints on excess-distortion probabilities as well as an optional constraint on average distortion. We show that coding redundancy for compressing discrete memoryless sources is upper-bounded by R2/√n + log n/2n + O(log log n/n) + R4+ o(1) where n is the block length, R2the second-order coding rate, and R4a constant. For the special case of coding with a single ϵ-fidelity constraint, R2= √V Q-1(ϵ) where V is the source rate-dispersion function, and Q is the tail probability of a normal random variable. The upper bound is proved using a random coding scheme and deriving exact asymptotics for the probability of distortion balls with input type dependent radius.

This paper studies lossy coding of discrete memoryless sources and derives new asymptotic lower bounds on the rate of optimal fixed-length codes. Both average and excess-probability distortion constraints are studied. We show that in each case the rate of optimal codes is lower bounded by R(D) + R2/ √ n + (log n)/(2n) + R4/n + o(1) where n is the block length, R(D) is Shannon's rate-distortion function, R2is the second-order coding rate, and R4a constant that is explicitly identified.

Let Xi, i E V form a Markov random field (MRF) represented by an undirected graph G = (V, E), and V' be a subset of V. We determine the smallest graph that can always represent the subfield Xi, i E V' as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When G is a path so that Xi, i E V form a Markov chain, it is known that the I-Measure is always nonnegative (Kawabata and Yeung in 1992). We prove that Markov chain is essentially the only MRF such that the I-Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF (Yeung et al. in 2002).

We present a novel anomaly detection (AD) system for streaming videos. Different from prior methods that rely on unsupervised learning of clip representations, that are usually coarse in nature, and batch-mode learning, we propose the combination of two non-parametric models for our task: (i) Dirichlet process mixture models (DPMM) based modeling of object motion and directions in each cell, and (ii) Gaussian process based active learning paradigm involving labeling by a domain expert. Whereas conventional clip representation methods adopt quantizing only motion directions leading to a lossy, coarse representation that are inadequate, our clip representation approach results in fine grained clusters at each cell that model the scene activities (both direction and speed) more effectively. For active anomaly detection, we adapt a Gaussian Process framework to process incoming samples (video snippets) sequentially, seek labels for confusing or informative samples and and update the AD model online. Furthermore, the proposed video representation along with a novel query criterion to select informative samples for labeling that incorporates both exploration and exploitation criteria is proposed, and is found to outperform competing criteria on two challenging traffic scene datasets.

Shannon's analysis of the fundamental capacity limits for memoryless communication channels has been refined over time. In this paper, the maximum volume M*avg(n, ∈) of length-n codes subject to an average decoding error probability ∈ is shown to satisfy the following tight asymptotic lower and upper bounds as n → ∞: A∈+ o(1) ≤ log M*avg(n, ∈) - [nC - √nV∈Q-1(∈)+ (1/2)log n] ≤ A∈+ o(1), where C is the Shannon capacity, V∈is the ∈-channel dispersion, or secondorder coding rate, Q is the tail probability of the normal distribution, and the constants AE and AE are explicitly identified. This expression holds under mild regularity assumptions on the channel, including nonsingularity. The gap A∈- A∈is one nat for weakly symmetric channels in the Cover-Thomas sense, and typically a few nats for other symmetric channels, for the binary symmetric channel, and for the Z channel. The derivation is based on strong large-deviations analysis and refined central limit asymptotics. A random coding scheme that achieves the lower bound is presented. The codewords are drawn from a capacityachieving input distribution modified by an O(1/√n) correction term.

The region of achievable error probabilities for k-ary hypothesis tests is studied in the asymptotic setting with n independent and identically distributed observations. We identify a k2- k - 1 dimensional parametric family of optimal (non-dominated) tests and relate it to a family of Bayes tests whose loss function depends exponentially on n. We asymptotically characterize the conditional error probabilities for these tests within O(1) as n → ∞, using strong large deviations analysis.

This paper presents a new approach to image-set-based face recognition, where each training and testing example is a set of face images captured from varying poses, illuminations, expressions, and resolutions. While a number of image set based face recognition methods have been proposed in recent years, most of them model each face image set as a single linear subspace or as the union of linear subspaces, which may lose some discriminative information for face image set representation. To address this shortcoming, we propose exploiting statistics information as feature representations for face image sets and develop a localized multikernel metric learning algorithm to effectively combine different statistics for recognition. Moreover, we propose a localized multikernel multimetric learning method to jointly learn multiple feature-specific distance metrics in the kernel spaces, one for each statistic feature, to better exploit complementary information for recognition. Our methods achieve state-of-the-art performance on four widely used video face datasets including the Honda, MoBo, YouTube Celebrities, and YouTube Face datasets.

In this paper, we propose a new deep hashing (DH) approach to learn compact binary codes for large scale visual search. Unlike most existing binary codes learning methods which seek a single linear projection to map each sample into a binary vector, we develop a deep neural network to seek multiple hierarchical non-linear transformations to learn these binary codes, so that the nonlinear relationship of samples can be well exploited. Our model is learned under three constraints at the top layer of the deep network: 1) the loss between the original real-valued feature descriptor and the learned binary vector is minimized, 2) the binary codes distribute evenly on each bit, and 3) different bits are as independent as possible. To further improve the discriminative power of the learned binary codes, we extend DH into supervised DH (SDH) by including one discriminative term into the objective function of DH which simultaneously maximizes the inter-class variations and minimizes the intra-class variations of the learned binary codes. Experimental results show the superiority of the proposed approach over the state-of-the-arts.

In this paper, we propose a multi-manifold deep metric learning (MMDML) method for image set classification, which aims to recognize an object of interest from a set of image instances captured from varying viewpoints or under varying illuminations. Motivated by the fact that manifold can be effectively used to model the nonlinearity of samples in each image set and deep learning has demonstrated superb capability to model the nonlinearity of samples, we propose a MMDML method to learn multiple sets of nonlinear transformations, one set for each object class, to nonlinearly map multiple sets of image instances into a shared feature subspace, under which the manifold margin of different class is maximized, so that both discriminative and class-specific information can be exploited, simultaneously. Our method achieves the state-of-the-art performance on five widely used datasets.

Dense local trajectories have been successfully used in action recognition. However, for most actions only a few local motion features (e.g., critical movement of hand, arm, leg etc.) are responsible for the action label. Therefore, highlighting the local features which are associated with important motion parts will lead to a more discriminative action representation. Inspired by recent advances in sentence regularization for text classification, we introduce a Motion Part Regularization framework to mine for discriminative groups of dense trajectories which form important motion parts. First, motion part candidates are generated by spatio-temporal grouping of densely extracted trajectories. Second, an objective function which encourages sparse selection for these trajectory groups is formulated together with an action class discriminative term. Then, we propose an alternative optimization algorithm to efficiently solve this objective function by introducing a set of auxiliary variables which correspond to the discriminativeness weights of each motion part (trajectory group). These learned motion part weights are further utilized to form a discriminativeness weighted Fisher vector representation for each action sample for final classification. The proposed motion part regularization framework achieves the state-of-the-art performances on several action recognition benchmarks.

A fast, low-complexity, algorithm for solving the ℓ1-regularized least-squares problem is devised and analyzed. Our algorithm, which we call the Inertial Iterative Soft-Thresholding Algorithm (I-ISTA), incorporates inertia into a forward-backward proximal splitting framework. We show that the iterates of I-ISTA converge linearly to a minimum with a better rate of convergence than the well-known Iterative Shrinkage/Soft-Thresholding Algorithm (ISTA) for solving ℓ1-regularized least-squares. The improvement in convergence rate over ISTA is significant on ill-conditioned problems and is gained with minor additional computations. We conduct numerical experiments which show that I-ISTA converges more quickly than ISTA and two other computationally comparable algorithms on compressed sensing and deconvolution problems.

In this paper, we propose a novel robust hashing algorithm based on signal-to-noise ratio (SNR) maximization to learn binary codes. We first motivate SNR maximization for robust hashing in a statistical model, under which maximizing SNR minimizes the robust hashing error probability. A globally optimal solution can be obtained by solving a generalized eigenvalue problem. The proposed algorithm is tested on both synthetic and real datasets, showing significant performance gain over existing hashing algorithms.

Estimating the displacements between two images is often addressed using a small displacement assumption, which leads to what is known as the optical flow equation. We study the quality of the underlying approximation for the recently developed Local All-Pass (LAP) optical flow algorithm, which is based on another approach - displacements result from filtering. While the simplest version of LAP computes only first-order differences, we show that the order of LAP approximation is quadratic, unlike standard optical flow equation based algorithms for which this approximation is only linear. More generally, the order of approximation of the LAP algorithm is twice larger than the differentiation order involved. The key step in the derivation is the use of Padé approximants.

Hashing algorithms which encode signal content into compact binary codes to preserve similarity, have been extensively studied for applications such as large-scale visual search. However, most existing hashing algorithms work with a single feature type, while combining multiple features is helpful in many vision tasks. In this paper, we propose two multi-feature hashing algorithms based on signal-to-noise ratio (SNR) maximization, where a globally optimal solution is obtained by solving a generalized eigenvalue problem. The first one jointly considers all feature correlations and learns uncorrelated hash functions that maximize SNR, and the second algorithm separately learns hash functions on each individual feature and selects the final hash functions based on the SNR associated with each hash function. The proposed algorithms perform favorably compared to other state-of-the-art multi-feature hashing algorithms on several benchmark datasets.

This paper studies MMSE estimation on the basis of quantized noisy observations. It presents nonasymptotic bounds on MMSE regret due to quantization for two settings: (1) estimation of a scalar random variable given a quantized vector of n conditionally independent observations, and (2) estimation of a p-dimensional random vector given a quantized vector of n observations (not necessarily independent) when the full MMSE estimator has a subgaussian concentration property.

Exact asymptotics are derived for composite hypothesis testing between two product probability measures Pnvs Qn, subject to a type-I error-probability constraint ε. Here P is known but Q is an unknown element of a given d-dimensional regular exponential family. We study the Rao score test, which is a quadratic approximation to the GLRT. The type-II error probability is shown to vanish as equation where D and V are respectively the Kullback-Leibler divergence and the variance of information divergence between P and Q; τ(ε; d) is the 1 - ε quantile for the χd2distribution; and the constants βd> 0 and γdare explicitly identified. The asymptotic regret relative to the Neyman-Pearson test (which knows Q) is reflected in the coefficient τ(ε; d), as is the cost of dimensionality. Looser asymptotics (with O(1) in place of εd) are obtained for the GLRT.

In this paper, we investigate order-preserving sparse coding for classifying structured data whose atomic features possess ordering relationships. Examples include time sequences where individual frame-wise features are temporally ordered, as well as still images (landscape, street view, etc.) where different regions of the image are spatially ordered. Classification of these structured data is often tackled by first decomposing the input data into individual atomic features, then performing sparse coding or other processing for each atomic feature vector independently, and finally aggregating individual responses to classify the input data. However, this heuristic approach ignores the underlying order of the individual atomic features within the input data, and results in suboptimal discriminative capability. In this work, we introduce an order preserving regularizer which aims to preserve the ordering structure of the reconstruction coefficients within the sparse coding framework. An efficient Nesterov-type smooth approximation method is developed for optimization of the new regularization criterion, with theoretically guaranteed error bound. We perform extensive experiments for time series classification on a synthetic dataset, several machine learning benchmarks, and an RGB-D human activity dataset. We also report experiments for scene classification on a benchmark image dataset. The encoded representation is discriminative and robust, and our classifier outperforms state-of-the-art methods on these tasks.

This paper presents a new joint feature learning (JFL) approach to automatically learn feature representation from raw pixels for face recognition. Unlike many existing face recognition systems, where conventional feature descriptors, such as local binary patterns and Gabor features, are used for face representation, we propose an unsupervised feature learning method to learn hierarchical feature representation. Since different face regions have different physical characteristics, we propose to use different feature dictionaries to represent them, and to learn multiple yet related feature projection matrices for these regions simultaneously. Hence position-specific discriminative information can be exploited for face representation. Having learned these feature projections for different face regions, we perform spatial pooling for face patches within each region to enhance the representative power of the learned features. Moreover, we stack our JFL model into a deep architecture to exploit hierarchical information for feature representation and further improve the recognition performance. Experimental results on five widely used face data sets show the effectiveness of our proposed approach.

We propose a novel robust hashing algorithm based on signal-to-noise ratio (SNR) maximization to learn compact binary codes, where the SNR metric is used to select a set of projection directions, and one hash bit is extracted from each projection direction. We first motivate this approach under a Gaussian model for the underlying signals, in which case maximizing SNR is equivalent to minimizing the robust hashing error probability. A globally optimal solution can be obtained by solving a generalized eigenvalue problem. We also develop a multibit per projection algorithm to learn longer hash codes when the number of high-SNR projections is limited. The proposed algorithms are tested on both synthetic and real data sets, showing significant performance gains over existing hashing algorithms.

In kernel based learning, the kernel trick transforms the original representation of a feature instance into a vector of similarities with the training feature instances, known as kernel representation. However, feature instances are sometimes ambiguous and the kernel representation calculated based on them do not possess any discriminative information, which can eventually harm the trained classifier. To address this issue, we propose to automatically select good feature instances when calculating the kernel representation in multiple kernel learning. Specifically, for the kernel representation calculated for each input feature instance, we multiply it element-wise with a latent binary vector named as instance selection variables, which targets at selecting good instances and attenuate the effect of ambiguous ones in the resulting new kernel representation. Beta process is employed for generating the prior distribution for the latent instance selection variables. We then propose a Bayesian graphical model which integrates both MKL learning and inference for the distribution of the latent instance selection variables. Variational inference is derived for model learning under a max-margin principle. Our method is called Beta process multiple kernel learning. Extensive experiments demonstrate the effectiveness of our method on instance selection and its high discriminative capability for various classification problems in vision.

We propose to decompose the fine-grained human activ- ity analysis problem into two sequential tasks with increas- ing granularity. Firstly, we infer the coarse interaction sta- tus, i.e., which object is being manipulated and where it is. Knowing that the major challenge is frequent mutual oc- clusions during manipulation, we propose an "interaction tracking" framework in which hand/object position and in- teraction status are jointly tracked by explicitly modeling the contextual information between mutual occlusion and interaction status. Secondly, the inferred hand/object posi- tion and interaction status are utilized to provide 1) more compact feature pooling by effectively pruning large num- ber of motion features from irrelevant spatio-temporal po- sitions and 2) discriminative action detection by a granu- larity fusion strategy. Comprehensive experiments on two challenging fine-grained activity datasets (i.e., cooking ac- tion) show that the proposed framework achieves high ac- curacy/robustness in tracking multiple mutually occluded hands/objects during manipulation as well as significant performance improvement on fine-grained action detection over state-of-the-art methods.

Traditional compression techniques optimize signal fidelity under a bit rate constraint. However, signals are often not only reconstructed for human evaluation purposes but also analyzed by machines. This paper introduces a two-part predictive (2PP) coding architecture intended for signal compression with the dual purposes of preserving signal fidelity and feature fidelity. First we introduce the architecture of the 2PP coder, then we apply and evaluate it on two problems: scene classification and pedestrian detection. Tradeoffs between compression rate, mean-squared reconstruction error, and classification accuracy, are explored.

This paper presents a novel design of content fingerprints based on maximization of the mutual information across the distortion channel. We use the information bottleneck method to optimize the filters and quantizers that generate these fingerprints. A greedy optimization scheme is used to select filters from a dictionary and allocate fingerprint bits. We test the performance of this method for audio fingerprinting and show substantial improvements over existing learning based fingerprints.

A simple hypothesis P is tested against a composite hypothesis ℚj, j ∈ {1,2, ...,k}, each ℚjbeing a product of n probability distributions. We consider the set of achievable false-positive error probability vectors for a generalized Neyman-Pearson test under a constraint on the probability of correct detection under P. Exact asymptotics (as n → ∞) are derived for this set, in particular the set is determined within an O(1) term.

We derive the second-order capacities (supremum of second-order coding rates) for erasure and list decoding. Fpor erasure decoding, we show that second-order capacity is √VΦ-1(εt) where V is the channel dispersion and (εtis the total error probability, i.e. the sum of the erasure and undetected errors. We show numerically that the expected rate at finite blocklength for erasures decoding can exceed the finite blocklength channel coding rate. For list decoding, we consider list codes of deterministic size 2√nland show that the second-order capacity is l+ √VΦ-1(ε) where ε is the permissible error probability. Both coding schemes use the threshold decoder and converses are proved using variants of the meta-converse.

The fingerprinting capacity has recently been derived as the value of a two-person zero-sum game. In this paper, we study the fingerprinting capacity games with k pirates in a new collusion model called the mixed digit model, which is inspired by the combined digit model of Škorić et al. For small k, the capacities along with optimal strategies for both players of the game are obtained explicitly. For large k, we extend our earlier asymptotic analysis for the binary alphabet with the marking assumption to q-ary alphabets with this general model and show that the capacity is asymptotic to A/(2k2ln q) where the constant A is specified as the maximin value of a functional game. Saddle-point solutions to the game are obtained using methods of variational calculus. For the special case of q-ary fingerprinting in the restricted digit model, we show that the interleaving attack is asymptotically optimal, a property that has motivated the design of optimized practical codes.

We investigate the problem of human identity and gender recognition from gait sequences with arbitrary walking directions. Most current approaches make the unrealistic assumption that persons walk along a fixed direction or a pre-defined path. Given a gait sequence collected from arbitrary walking directions, we first obtain human silhouettes by background subtraction and cluster them into several clusters. For each cluster, we compute the cluster-based averaged gait image as features. Then, we propose a sparse reconstruction based metric learning method to learn a distance metric to minimize the intra-class sparse reconstruction errors and maximize the inter-class sparse reconstruction errors simultaneously, so that discriminative information can be exploited for recognition. The experimental results show the efficacy of our approach.

This paper proposes a regularized Adaboost algorithm to learn and extract binary fingerprints of time-varying content by filtering and quantizing perceptually significant features. The proposed algorithm extends the recent symmetric pairwise boosting (SPB) algorithm by taking feature sequence correlation into account. An information-theoretic analysis of the SPB algorithm is given, showing that each iteration of SPB maximizes a lower bound on the mutual information between matching fingerprint pairs. Based on the analysis, two practical regularizers are proposed to penalize those filters generating highly correlated filter responses. A learning-theoretic analysis of the regularized Adaboost algorithm is given. The proposed algorithm demonstrates significant performance gains over SPB for both audio and video content identification systems.

This paper proposes a regularized Adaboost learning algorithm to extract binary fingerprints by filtering and quantizing perceptually significant features. The proposed algorithm extends the recent symmetric pairwise boosting (SPB) algorithm by taking feature sequence correlation into account. Information and learning theoretic analysis is given. Significant performance gains over SPB are demonstrated for both audio and video fingerprinting.

This paper proposes the first content identification (ID) system for depth video as well as a first hybrid content ID system for synchronized RGB and depth (RGB-D) video. The proposed systems are tested on a public RGB-D dataset. The hybrid system demonstrates significant performance gains over RGB-alone or depth-alone systems, while depth and RGB perform comparably. Moreover, a statistical interpretation of the hybrid system's superior performance is provided.

This paper presents a new approach for image set classification, where each training and testing example contains a set of image instances of an object captured from varying viewpoints or under varying illuminations. While a number of image set classification methods have been proposed in recent years, most of them model each image set as a single linear subspace or mixture of linear subspaces, which may lose some discriminative information for classification. To address this, we propose exploring multiple order statistics as features of image sets, and develop a localized multi-kernel metric learning (LMKML) algorithm to effectively combine different order statistics information for classification. Our method achieves the state-of-the-art performance on four widely used databases including the Honda/UCSD, CMU Mobo, and Youtube face datasets, and the ETH-80 object dataset.

We aim to unsupervisedly discover human's action (motion) patterns of manipulating various objects in scenarios such as assisted living. We are motivated by two key observations. First, large variation exists in motion patterns associated with various types of objects being manipulated, thus manually defining motion primitives is infeasible. Second, some motion patterns are shared among different objects being manipulated while others are object specific. We therefore propose a nonparametric Bayesian method that adopts a hierarchical Dirichlet process prior to learn representative manipulation (motion) patterns in an unsupervised manner. Taking easy-to-obtain object detection score maps and dense motion trajectories as inputs, the proposed probabilistic model can discover motion pattern groups associated with different types of objects being manipulated with a shared manipulation pattern dictionary. The size of the learned dictionary is automatically inferred. Comprehensive experiments on two assisted living benchmarks and a cooking motion dataset demonstrate superiority of our learned manipulation pattern dictionary in representing manipulation actions for recognition.

We propose a heterogeneous information network mining algorithm: feature-enhanced Rank Class (F-Rank Class). F-Rank Class extends Rank Class to a unified classification framework that can be applied to binary or multiclass classification of unimodal or multimodal data. We experimented on a multimodal document dataset, 2008/9 Wikipedia Selection for Schools. For unimodal classification, F-Rank Class is compared to support vector machines (SVMs). F-Rank Class provides improvements up to 27.3% on the Wikipedia dataset. For multimodal document classification, F-Rank Class shows improvements up to 19.7% in accuracy when compared to SVM-based meta-classifiers. We also study 1) how the structure of the network and 2) how the choice of parameters affect the classification results.

Upper bounds have recently been derived on the maximum volume of length-n codes for memoryless channels subject to either a maximum or an average decoding error probability ε. These bounds are expressed in terms of a minmax game whose variables are n-dimensional probability distributions and whose payoff function is the power of a Neyman-Pearson test at significance level 1 - ε. We derive the exact asymptotics (as n → ∞) of this game by relating it to a problem that admits an asymptotic saddlepoint with an equalizer property.

Recognizing complex human activities usually requires the detection and modeling of individual visual features and the interactions between them. Current methods only rely on the visual features extracted from 2-D images, and therefore often lead to unreliable salient visual feature detection and inaccurate modeling of the interaction context between individual features. In this paper, we show that these problems can be addressed by combining data from a conventional camera and a depth sensor (e.g., Microsoft Kinect). We propose a novel complex activity recognition and localization framework that effectively fuses information from both grayscale and depth image channels at multiple levels of the video processing pipeline. In the individual visual feature detection level, depth-based filters are applied to the detected human/object rectangles to remove false detections. In the next level of interaction modeling, 3-D spatial and temporal contexts among human subjects or objects are extracted by integrating information from both grayscale and depth images. Depth information is also utilized to distinguish different types of indoor scenes. Finally, a latent structural model is developed to integrate the information from multiple levels of video processing for an activity detection. Extensive experiments on two activity recognition benchmarks (one with depth information) and a challenging grayscale + depth human activity database that contains complex interactions between human-human, human-object, and human-surroundings demonstrate the effectiveness of the proposed multilevel grayscale + depth fusion scheme. Higher recognition and localization accuracies are obtained relative to the previous methods.

Spatial contexts encode rich discriminative information for visual classification. However, as object shapes and scales vary significantly among images, spatial contexts with manually specified distance ranges are not guaranteed with optimality. In this work, we investigate how to automatically select discriminative and stable distance bin groups for modeling image spatial contexts to improve classification performance. We make two observations. First, the number of distance bins for context modeling can be arbitrarily large, and discriminative contexts are only from a small subset of distance bins. Second, adjacent distance bins for contexts modeling often show similar characteristics, thus encouraging grouping them together can result in more stable representation. Utilizing these two observations, we propose an omni-range spatial context mining framework for image classification. A sparse selection and grouping regularizer is employed along with an empirical risk, to discover discriminative and stable distance bin groups for context modeling. To facilitate efficient optimization, the objective function is approximated by a smooth convex function with theoretically guaranteed error bounds. The selected and grouped image spatial contexts, which are applied in food and national flag recognition, are demonstrated to be discriminative, compact and robust.

In this paper, decoding metrics are designed for statistical fingerprint-based content identification. A fairly general class of structured codes is considered, and a statistical model for the resulting fingerprints and their degraded versions (following miscellaneous content distortions) is proposed and validated. The Maximum-Likelihood fingerprint decoder derived from this model is shown to considerably improve upon previous decoders based on the Hamming metric. A GLRT test is also proposed and evaluated to deal with unknown distortion channels.

In this work, we develop a computer vision based fall prevention system for hospital ward application. To prevent potential falls, once the event of patient get up from the bed is automatically detected, nursing staffs are alarmed immediately for assistance. For the detection task, we use a RGBD sensor (Microsoft Kinect). The geometric prior knowledge is exploited by identifying a set of task-specific feature channels, e.g., regions of interest. Extensive motion and shape features from both color and depth image sequences are extracted. Features from multiple modalities and channels are fused via a multiple kernel learning framework for training the event detector. Experimental results demonstrate the high accuracy and efficiency achieved by the proposed system.

This paper studies the maximum achievable rate region of multiple access channels (MAC) for a given blocklength n and a desired error probability ϵ. The inner region for the discrete memoryless MAC is approximated by a single-lettered expression I - 1/√n Qinv(V, ϵ) where I is associated with the capacity pentagon bounds by Ahlswede and Liao, V is the MAC dispersion matrix, and Qinvis the complementary multivariate Gaussian cumulative distribution region. For outer regions, we provide general converse bounds for both average error probability and maximum error probability criteria, and a single-lettered approximation for the discrete memoryless MAC.

Fingerprinting capacity has recently been derived as the value of a two-person zero-sum game. In this work, we study fingerprinting capacity games with k pirates under the combined digit model proposed by Škorić et al. For small k, capacities along with optimal strategies for both players of the game are obtained explicitly. For large k, we extend our earlier asymptotic analysis for the binary alphabet to this general model and show that capacity is asymptotic to A/k2where the constant A is identified. Saddle-point solutions to the functional maximin game are obtained using methods of variational calculus.

This paper derives a tight asymptotic upper bound on the maximum volume M*cc(n, ϵ) of length-n constant-composition codes subject to an average decoding error probability ϵ: Mbb(n, ϵ) = exp{nC - √nV Φ-(1 - ϵ) + 1/2 log n + An, ϵ+ o(1)} where Φ is the cdf of the standard normal distribution, and An, ϵis a bounded sequence that can be explicitly identified and reduces to a constant in the nonlattice case. A lower bound is presented, differing from the upper bound by an easily computable multiplying constant. These expressions hold under certain regularity assumptions on the channel.

We study a fingerprinting game in which the number of colluders and the collusion channel are unknown. The encoder embeds fingerprints into a host sequence and provides the decoder with the capability to trace back pirated copies to the colluders. Fingerprinting capacity has recently been derived as the limit value of a sequence of maximin games with mutual information as their payoff functions. However, these games generally do not admit saddle-point solutions and are very hard to solve numerically. Here under the so-called Boneh-Shaw marking assumption, we reformulate the capacity as the value of a single two-person zero-sum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is k and the fingerprinting alphabet is binary, we show that capacity decays quadratically with k. Furthermore, we prove rigorously that the asymptotic capacity is 1/(k221n2) and we confirm our earlier conjecture that Tardos' choice of the arcsine distribution asymptotically maximizes the mutual information payoff function while the interleaving attack minimizes it. Along with the asymptotics, numerical solutions to the game for small k are also presented.

We propose a new paradigm for blind watermark decoding in the presence of desynchronization attacks. Employing Forney-style factor graphs to model the watermarking system, we cast the blind watermark decoding problem as a probabilistic inference problem on a graph, and solve it via message-passing. We study a wide range of moderate to strong attacks including scaling, amplitude modulation, fractional shift, arbitrary linear and shift-invariant filtering, and blockwise filtering, and show that the graph-based iterative decoders perform almost as well as if they had exact knowledge of the desynchronization attack parameters. Other desirable features of the graph-based decoders include the flexibility to adapt to other types of attacks and the ability to cope with the “curse of dimensionality” problem that seemingly results when the desynchronization parameter space has high dimensionality. These properties are unlike most blind watermark decoders proposed to date.

Traitor-tracing (aka fingerprinting) has received much attention as a possible solution for protecting media copyrights. However, all the current schemes for image and video lack robustness against geometric attacks. We propose a novel semi-blind algorithm that can cope with such attacks. The algorithm uses compressed SURF features as side information in order to estimate and invert the geometric attack. Moreover the algorithm is highly robust against cropping and additive white noise.

This paper proposes codes that achieve the fundamental capacity limits of digital fingerprinting subject to mean-squared distortion constraints on the fingerprint embedder and the colluders. We first show that the traditional method of fingerprint decoding by thresholding correlation statistics falls short of this goal: reliable performance is impossible at code rates greater than some value C1that is strictly less than capacity. To bridge the gap to capacity, a more powerful decoding method is needed. The maximum penalized Gaussian mutual information decoder presented here meets this requirement. Finally, a mathematical framework and a capacity expression for fingerprinting of social networks are presented.

We address the question of constructing practical blind watermark decoders that are resilient to scaling and amplitude modulation attacks. We cast the watermark decoding problem as a probabilistic inference problem on a factor graph and solve it via message passing. Our decoder performs nearly as well as a decoder that has exact knowledge of the desynchronization parameters. Experimental results, on both synthetic and natural images, suggest that the decoding algorithm is capable of handling moderate to strong desynchronization attacks very well.

We study a fingerprinting game in which the collusion channel is unknown. The encoder embeds fingerprints into a host sequence and provides the decoder with the capability to trace back pirated copies to the colluders. Fingerprinting capacity has recently been derived as the limit value of a sequence of maxmin games with mutual information as the payoff function. However, these games generally do not admit saddle-point solutions and are very hard to solve numerically. Here under the so-called Boneh-Shaw marking assumption, we reformulate the capacity as the value of a single two-person zero-sum game, and show that it is achieved by a saddle-point solution. If the maximal coalition size is k and the fingerprint alphabet is binary, we derive equations that can numerically solve the capacity game for arbitrary k. We also provide tight upper and lower bounds on the capacity. Finally, we discuss the asymptotic behavior of the fingerprinting game for large k and practical implementation issues.

A strong converse for the Gel'fand-Pinsker channel is established in this paper. The method is then extended to a multiuser scenario. A strong converse is established for the multiple-access Gel'fand-Pinsker channel under the maximum error criterion, and the capacity region is determined.

This paper proposes learning algorithms for the problem of multimodal document classification. Specifically, we develop classifiers that automatically assign documents to categories by exploiting features from both text as well as image content. In particular, we use meta-classifiers that combine state-of-the-art text and image based classifiers into making joint decisions. The two meta classifiers we choose are based on support vector machines and Adaboost. Experiments on real-world databases from Wikipedia demonstrate the benefits of a joint exploitation of these modalities.

Despite their popularity, spread spectrum schemes are vulnerable against sensitivity analysis attacks on standard deterministic watermark detectors. A possible defense is to use a randomized watermark detector. While randomization sacrifices some detection performance, it might be expected to improve detector security to some extent. This paper presents a framework to design randomized detectors with exponentially large randomization space and controllable loss in detection reliability. We also devise a general procedure to attack such detectors by reducing them into equivalent deterministic detectors. We conclude that, contrary to prior belief, randomization of the detector is not the ultimate answer for providing security against sensitivity analysis attacks in spread spectrum systems. Instead, the randomized detector inherits the weaknesses of the equivalent deterministic detector.

The rate of a fingerprinting code is defined as R = (1/N) log2M, where N is the code length and M the number of users. Capacity is the supremum of achievable rates for a given class of collusion attacks. Most fingerprinting codes in current literature are algebraic constructions with high minimum distance. These codes have low rate (relative to capacity) and thus long fingerprints for a given number of users and colluders. However, short fingerprints are valuable in media fingerprinting due to the limited number of robust features available for embedding. This paper proposes a framework to build high-rate fingerprinting codes operating near the fundamental capacity limit by concatenating short, random, and statistically independent subcodes. A practical implementation based on the turbo code construction is presented. Each subcode is decoded by a list Viterbi decoding algorithm, which outputs a list of suspect users. These lists are then processed using a matched filter, which extracts the most suspect user and declares him or her guilty. We provide examples of codes that are short, accommodate millions of users, and withstand (with an error probability of the order of 1%) dozens of colluders against the averaging or interleaving attack followed by additive white Gaussian noise. Our fingerprinting codes operate reliably at rates within 30% to 50% of capacity, which are substantially higher than any other existing code. The decoding complexity is linear in N, or, equivalently, in log M.

We study the effect of the noise distribution on the error probability of the detection test when a class of randomly rotated spherical fingerprints is used. The detection test is performed by a focused correlation detector, and the spherical codes studied here form a randomized orthogonal constellation. The colluders create a noise-free forgery by uniform averaging of their individual copies, and then add a noise sequence to form the actual forgery. We derive the noise distribution that maximizes the error probability of the detector under average and almost-sure distortion constraints. Moreover, we characterize the noise distribution that minimizes the decoder's error exponent under a large-deviations distortion constraint.

This paper addresses the design of additive fingerprints that are maximally resilient against linear collusion attacks on a focused correlation detector, as defined below. LetNbe the length of the host vector andMlesN+ 1 the number of users. The focused detector performs a correlation test in order to decide whether a user of interest is among the colluders. Both the fingerprint embedder and the colluders are subject to squared-error distortion constraints. We show that simplex fingerprints maximize a geometric figure of merit for this detector. In that sense they outperform orthogonal fingerprints but the advantage vanishes asMrarr infin. They are also optimal in terms of minimizing the probability of error of the focused detector when the attack is a uniform averaging of the marked copies followed by the addition of white Gaussian noise. Reliable detection is guaranteed provided that the number of colludersKLt radic(N). Moreover, we study the probability of error performance of simplex fingerprints for the focused correlation detector when the colluders use nonuniform averaging plus white Gaussian noise attacks.

In this paper, we study some fundamental performance limits of blind data hiding against desynchronization attacks. These attacks are modeled in addition to independent Gaussian noise to the marked signal, followed by linear, time-invariant filtering. We study a joint estimator-decoder which estimates the desynchronization attack parameters and uses these estimates in the decoding step. We propose a coding scheme based on distortion-compensated quantization index modulation and derive the estimation accuracy of the attack parameters via Fisher information and a Cramer-Rao type bound. For illustration purposes, we report estimation and decoding results on several attacks, including classical ones (scaling and fractional shifts) and some new ones. The results are in close agreement with our bounds and tightly quantify the performance loss due to desynchronization and the influence of code block length. Thus our results demonstrate the high performance of a joint estimation-decoding approach.

When information is to be transmitted over an unknown, possibly unreliable channel, an erasure option at the decoder is desirable. Using constant-composition random codes, we propose a generalization of Csiszar and Korner's maximum mutual information (MMI) decoder with an erasure option for discrete memoryless channels. The new decoder is parameterized by a weighting function that is designed to optimize the fundamental tradeoff between undetected-error and erasure exponents for a compound class of channels. The class of weighting functions may be further enlarged to optimize a similar tradeoff for list decodersin that case, undetected-error probability is replaced with average number of incorrect messages in the list. Explicit solutions are identified. The optimal exponents admit simple expressions in terms of the sphere-packing exponent, at all rates below capacity. For small erasure exponents, these expressions coincide with those derived by Forney (1968) for symmetric channels, using maximum a posteriori decoding. Thus, for those channels at least, ignorance of the channel law is inconsequential. Conditions for optimality of the Csiszar-Korner rule and of the simpler empirical-mutual-information thresholding rule are identified. The error exponents are evaluated numerically for the binary symmetric channel.

Digital fingerprinting aims at protecting multimedia contents from illegal redistribution by embedding imperceptible fingerprints identifying the users. We propose two approaches for building fingerprinting codes that accommodate millions of users and resist tens of colluders. These approaches are based on recent information-theoretic analyses of good fingerprinting codes in two regimes: (1) very low rates, and (2) rates near capacity. Good low-rate codes have high minimum distance. Good high-rate codes are short and random-like. Simulation results are presented to assess decoding performance.

We study communication over an unknown, possibly unreliable, discrete memoryless channel. For such problems, an erasure option at the decoder is desirable. We use constant-composition random codes and propose a generalization of the Maximum Mutual Information decoder. The proposed decoder is parameterized by a weighting function that can be designed to optimize the fundamental tradeoff between undetected-error and erasure exponents. Explicit solutions are identified. The class of functions can be further enlarged to optimize a similar tradeoff for list decoders. The optimal exponents admit simple expressions in terms of the sphere-packing exponent, at all rates below capacity. For small erasure exponents, these expressions coincide with those derived by Forney (1968) for symmetric channels, using Maximum a Posteriori decoding. Thus for those channels at least, ignorance of the channel law is inconsequential.

Bounds on fingerprinting capacity have been derived in recent literature. In this paper we present an exact capacity formula and a universal fingerprinting scheme. Our problem setup unifies the signal-distortion and Boneh-Shaw formulations of fingerprinting. The proposed scheme has four useful properties: (1) the receiver does not need to know the coalition size and collusion channel; (2) a tunable parameter Delta trades off false-positive and false-negative error exponents; (3) the receiver provides a reliability metric for its decision; and (4) the decoder is capacity-achieving when the false-positive exponent Delta tends to zero. The new random coding scheme uses a "time-sharing" randomized sequence and produces conditionally constant-composition fingerprints. The decoder is a minimum penalized equivocation decoder, where the penalty term is proportional to coalition size.

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.

This paper analyzes the performance of arbitrary nonlinear collusion attacks on random fingerprinting codes. We derive the error exponent of the fingerprinting system, which determines the exponential decay of the error probability. A Gaussian ensemble and an expurgated Gaussian ensemble of codes are considered. The collusion attacks include order-statistics attacks as special cases. In our model, a correlation detector is used. The colluders create a noise-free forgery by applying an arbitrary nonlinear mapping to their individual copies, and next they add a Gaussian noise sequence to form the final forgery. The colluders are subject to a mean-squared distortion constraint between host and forgery. We prove that the uniform linear averaging attack outperforms all others.

Sensitivity analysis attacks present a serious threat to the security of popular spread spectrum watermarking schemes. Randomization of the detector is thought to increase the immunity of such schemes against cryptanalysis. In this paper, we introduce a new attack against randomized detectors. This attack is successful, which implies that spread spectrum schemes still lack security.

The performance of current blind watermark decoders against desynchronization attacks is rather poor. Such attacks include filtering, amplitude modulation, gamma correction, time-varying delays, and spatial warping. We propose a new family of watermark decoders based on modern methods for iterative decoding using graphical models. This approach addresses the "curse of dimensionality" problem that seemingly results when the desynchronization parameter space has high dimensionality.

This paper analyzes the performance of collusion attacks on random fingerprinting codes, when the colluders are subject to an almost sure squared distortion constraint and a list decoder is used. We derive an exact characterization of the type-I and type-II error exponents of the fingerprinting system. A Gaussian ensemble and an expurgated Gaussian ensemble of codes are considered, and the corresponding random-coding exponents are derived. Explicit optimal strategies for the colluders are derived as well.

Sensitivity analysis attacks constitute a powerful family of watermark "removal" attacks. They exploit vulnerability in some watermarking protocols: the attacker's unlimited access to the watermark detector. This paper proposes a mathematical framework for designing sensitivity analysis attacks and focuses on additive spread-spectrum embedding schemes. The detectors under attack range in complexity from basic correlation detectors to normalized correlation detectors and maximum-likelihood (ML) detectors. The new algorithms precisely estimate and then eliminate the watermark from the watermarked signal. This is accomplished by exploiting geometric properties of the detection boundary and the information leaked by the detector. Several important extensions are presented, including the case of a partially unknown detection function, and the case of constrained detector inputs. In contrast with previous art, our algorithms are noniterative and require, at most, O(n) detection operations in order to precisely estimate the watermark, where n is the dimension of the signal. The cost of each detection operation is O(n); hence, the algorithms can be executed in quadratic time. The method is illustrated with an application to image watermarking using an ML detector based on a generalized Gaussian model for images

The purpose of image steganalysis is to detect the presence of hidden messages in cover photographic images. Supervised learning is an effective and universal approach to cope with the twin difficulties of unknown image statistics and unknown steganographic codes. A crucial part of the learning process is the selection of low-dimensional informative features. We investigate this problem from three angles and propose a three-level optimization of the classifier. First, we select a subband image representation that provides better discrimination ability than a conventional wavelet transform. Second, we analyze two types of features-empirical moments of probability density functions (PDFs) and empirical moments of characteristic functions of the PDFs-and compare their merits. Third, we address the problem of feature dimensionality reduction, which strongly impacts classification accuracy. Experiments show that our method outperforms previous steganalysis methods. For instance, when the probability of false alarm is fixed at 1%, the stegoimage detection probability of our algorithm exceeds that of its closest competitor by at least 15% and up to 50%

Capacity formulas and random-coding exponents are derived for a generalized family of Gel'fand-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

We study the theoretical performance of linear and nonlinear collusion attacks under the assumptions that orthogonal or regular-simplex fingerprints are used, and that the detector performs a linear correlation test in order to decide whether a user of interest is among the colluders. The colluders create a noise-free forgery by applying a mapping / to their individual copies, and then add a noise sequence e to form the actual forgery. They seek the mapping / and the distribution of e that maximize the probability of error of the detector. The performance of mappings such as linear-averaging and interleaving can be compared in this framework. It is also shown that impulsive noise attacks are far more effective than Gaussian attacks

This paper presents a classifier built for differentiating digital photorealistic images from digital photographs. Results show that our 144-dimensional (144-D) feature vector extracted from characteristic functions of wavelet histograms is more efficient than Lyu and Farid's 216-D feature vector (S. Lyu and H. Farid), and Ng et al.'s 192-D feature vector (2005). Our classifier outperforms Lyu and Farid's state-of-art method while only requiring half of their feature extraction and testing time

Designing watermarking codes that can withstand geometric and other desynchronization attacks is a notoriously difficult problem. One may ask whether these difficulties are due to limitations of current codes, or rather to fundamental limitations on achievable performance. This paper describes our recent results on this problem for blind and nonblind watermarking, and provides examples for which the theory applies.

Designing watermarking codes that can with stand geometric and other desynchronization attacks is a notoriously difficult problem. One may ask whether these difficulties are due to limitations of current codes, or rather to fundamental limitations on achievable performance. We model the attack channel as the cascade of a memoryless channel and a smooth, invertible mapping Tthetas, thetas isin thetasn, representing the geometric attack. The decoder does not known the value of thetas. We show that under regularity conditions, there exists a universal decoder for this problem, and we explicitly identify it

We consider the problem of jamming in non-coherent wideband fading channels. While the problem is well understood for coherent channels, the results for the coherent case do not generalize in the non-coherent regime. We show that energy-limited jammers do not affect capacity in the wideband regime. We also propose a training based transmission scheme that is able to achieve the wideband limit in the presence of a jammer

Capacity and random-coding error exponent formulas are derived for a public fingerprinting (traitor tracing) game. The original media copy is available to the encoder, but not to the decoder. We derive the random-coding error exponent for a stacked binning scheme. The exponent is strictly positive at all rates below capacity. The converse part of the capacity proof is based on the Gel'fand-Pinsker technique

While binning is a fundamental approach to blind data embedding and watermarking, an attacker may devise various strategies to reduce the effectiveness of practical binning schemes. The problem analyzed in this paper is design of worst-case noise distributions against L-dimensional lattice quantization index modulation (QIM) watermarking codes. The cost functions considered are 1) probability of error of the maximum-likelihood decoder, and 2) the more tractable Bhattacharyya upper bound on error probability, which is tight at low embedding rates. Both problems are addressed under the following constraints on the attacker's strategy: the noise is independent of the marked signal, blockwise memoryless with block length L, and may not exceed a specified quadratic-distortion level. The embedder's quadratic distortion is limited as well. Three strategies are considered for the embedder: optimization of the lattice inflation parameter (also known as Costa parameter), dithering, and randomized lattice rotation. Critical in this analysis are the symmetry properties of QIM nested lattices and convexity properties of probability of error and related functionals of the noise distribution. We derive the minmax optimal embedding and attack strategies and obtain explicit solutions as well as numerical solutions for the worst-case noise. The role of the attacker's memory is investigated; in particular, we demonstrate the remarkable effectiveness of impulsive-noise attacks as L increases. The formulation proposed in this paper is also used to evaluate the capacity of lattice QIM under worst-noise conditions.

This paper derives fundamental performance bounds for statistical estimation of parametric surfaces embedded in R3. Unlike conventional pixel-based image reconstruction approaches, our problem is reconstruction of the shape of binary or homogeneous objects. The fundamental uncertainty of such estimation problems can be represented by global confidenceregions, which facilitate geometric inference and optimization ofthe imaging system. Compared to our previous work on global confidence region analysis for curves [two-dimensional (2-D) shapes], computation of the probability that the entire surface estimate lies within the confidence region is more challenging because a surface estimate is an inhomogeneous random field continuously indexed by a 2-D variable. We derive an asymptotic lower bound to this probability by relating it to the exceedence probability of a higher dimensional Gaussian random field, which can, in turn, be evaluated using the tube formula due to Sun. Simulation results demonstrate the tightness of the resulting bound and the usefulness of the three-dimensional global confidence region approach.

The Karhunen-Loeacuteve 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

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.

This paper examines the role of attacker's memory in quantization index modulation (QIM) watermarking systems. First we derive the attacker's noise distribution that maximizes probability of error of the detector. Next, we derive QIM code parameters that are minmax optimal. The minmax optimal embedding strategy involves randomized lattice rotations, and the corresponding worst noise distributions are isotropic.

This tutorial paper reviews the theory and design of codes for hiding or embedding information in signals such as images, video, audio, graphics,and text. Such codes have also been called watermarking codes; they can be used in a variety of applications, including copyright protection for digital media, content authentication, media forensics, data binding, and covert communications. Some of these applications imply the presence of an adversary attempting to disrupt the transmission of information to the receiver; other applications involve a noisy, generally unknown, communication channel. Our focus is on the mathematical models, fundamental principles, and code design techniques that are applicable to data hiding. The approach draws from basic concepts in information theory, coding theory, game theory, and signal processing,and is illustrated with applications to the problem of hiding data in images.

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.

Perceptual watermarking methods are designed to be transparent and robust to attacks. A perceptual model based on just noticeable difference levels introduces amplitude constraints on the watermark and the noise generated by an attacker. Two problems are considered: (1) detection performance for embedding a single bit in n data; (2) Shannon capacity. In both cases, the original host data are known to the receiver. Both problems are formulated as games involving a suitable cost function (Bhattacharyya distance and mutual information, respectively). The watermarker and the attacker design probability distributions in order to maximize and minimize, respectively, the cost function. The optimal distributions are quite different from the uniform distributions that have been previously used in the watermarking literature.

The problem of blind watermarking of an arbitrary host signal in /spl Ropf//sup n/ under squared-error distortion constraints and Gaussian attacks is considered in this paper. While distortion-compensated lattice quantization index modulation (QIM), using nearly spherical Voronoi cells, is known to be asymptotically capacity-achieving in this setup, our results suggest that such schemes are suboptimal in terms of error probability when the number of possible messages is subexponential in n. Our conjecture is substantiated by examples involving low-dimensional lattices and is related to the simplex conjecture in coding theory.

Quantization Index Modulation (QIM) methods are widely used for blind data embedding and watermarking. Given a QIM watermarking code, we ask what is the attacker's noise distribution that maximizes probability of error of the detector. For memoryless attacks, the problem is reduced to a convex programming problem. Next, we derive QIM code parameters that are minmax optimal.

We propose a blind image watermarking algorithm that has three main features: (1) it satisfies an undetectability constraint with respect to a statistical image model, (2) it rejects host-signal interference and (3) it is robust against additive and multiplicative noise, filtering, cropping, and random bending.

We present a new lower bound for the error exponents of nested lattice codes for the additive white Gaussian noise (AWGN) channel. The exponents are closely related to those of an unconstrained additive noise channel where the noise is a weighted sum of a white Gaussian and a spherically uniform random vector. The new lower bound improves the previous result derived by Erez and Zamir (2002) and stated in terms of the Poltyrev exponents. More surprisingly, the new lower bound coincides with the random coding error exponents of the optimal Gaussian codes for the AWGN channel in the nonexpurgated regime. One implication of this result is that minimum mean squared error (MMSE) scaling, despite its key role in achieving capacity of the AWGN channel, is no longer fundamental in achieving the best error exponents for rates below channel capacity. These exponents are achieved using a lattice inflation parameter derived from a large-deviation analysis.

Capacity formulas and random-coding and sphere-packing exponents are derived for a generalized family of Gel'fand-Pinsker coding problems. Information is to be reliably transmitted through a noisy channel with random state sequence. Partial information about the state sequence is available to the encoder and decoder. Two families of channels are considered: (1) compound discrete memoryless channels (C-DMC); and (2) channels with arbitrary memory, subject to an additive cost constraint, or more generally to a constraint on the conditional type of the channel output given the input. Both problems are closely connected. For the C-DMC case, our random-coding and sphere-packing exponents coincide at high rates, thereby determining the reliability function of the channel family. The random-coding exponent is achieved using a 3D binning scheme and a maximum penalized mutual information decoder. In the case of arbitrary channels, with memory, a larger random-coding error exponent than in the C-DMC case is obtained. 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.

This paper develops a joint hashing/watermarking scheme in which a short hash of the host signal is available to a detector. Potential applications include content tracking on public networks and forensic identification. The host data into which the watermark is embedded are selected from a secret subset of the full-frame discrete cosine transform of an image, and the watermark is inserted through multiplicative embedding. The hash is a binary version of selected original image coefficients. We propose a maximum likelihood watermark detector based on a statistical image model. The availability of a hash as side information to the detector modifies the posterior distribution of the marked coefficients. We derive Chernoff bounds on the receiver operating characteristic performance of the detector. We show that host-signal interference can be rejected if the hash function is suitably designed. The relative difficulty of an eavesdropper's detection problem is also determined; the eavesdropper does not know the secret key used. Monte Carlo simulations are performed using photographic test images. Finally, various attacks on the watermarked image are introduced to study the robustness of the derived detectors. 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 nonGaussian host signals.

In a variety of applications, classification systems operate on compressed signals. The design of optimal transform coders optimizing a joint classification/reconstruction criterion was explored, where classification accuracy is measured using the Chernoff bound on probability of misclassification and reconstruction quality is measured using mean-squared error (MSE) distortion. Under a high-rate assumption, local optimality properties of the Karhunen-Loeve transform (KLT) for a certain class of Gaussian mixtures under a joint classification/MSE measure was shown. Analytical expressions for optimal bit-allocation were derived. This generalizes classical optimality properties of the KLT for Gaussian sources under the MSE criterion.

This paper studies the effects of desynchronization attacks such as delay and warping on the performance of blind spread-spectrum watermark detection systems. The host signal is modeled as a colored Gaussian signal. Evaluation of the optimal likelihood ratio test is often computationally expensive, so as a practical alternative, we propose a family of quadratic detectors and construct the detector and family of watermarks that maximize the deflection criterion. Experiments are carried out to verify the suitability of the deflection as a performance index. Substantial improvements over conventional watermark designs are demonstrated.

Quantization index modulation (QIM) is a powerful host-interference rejecting method for data hiding. The paper applies QIM to one-bit watermarking and proposes a simple but powerful watermark detector. We derive lower bounds on the error exponents for the detector under a quadratic distortion constraint for the watermarker and additive white Gaussian noise attacks. These bounds are independent of the host-signal distribution and are substantially better than recently derived bounds for public (blind) spread-spectrum watermarking.

We address the problem of computing fundamental performance bounds for estimation of object boundaries from noisy measurements in inverse problems, when the boundaries are parameterized by a finite number of unknown variables. Our model applies to multiple unknown objects, each with its own unknown gray level, or color, and boundary parameterization, on an arbitrary known background. While such fundamental bounds on the performance of shape estimation algorithms can in principle be derived from the Cramér-Rao lower bounds, very few results have been reported due to the difficulty of computing the derivatives of a functional with respect to shape deformation. We provide a general formula for computing Cramér-Rao lower bounds in inverse problems where the observations are related to the object by a general linear transform, followed by a possibly nonlinear and noisy measurement system. As an illustration, we derive explicit formulas for computed tomography, Fourier imaging, and deconvolution problems. The bounds reveal that highly accurate parametric reconstructions are possible in these examples, using severely limited and noisy data.

An information-theoretic analysis of information hiding is presented, 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 (1980) 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.

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 have designed a practical information embedding code for images. The method assumes a locally i.i.d. (independent identically distributed) Gaussian source model for wavelet image coefficients. The proposed algorithm is developed based on this model and recent information theoretic results on information hiding for parallel Gaussian channels. Promising results have been obtained on test images.

This paper extends our game-theoretic approach to design and embed watermarks in Gaussian signals in the presence of an adversary. The detector solves a binary hypothesis testing problem. The system is designed to minimize probability of error under the worst-case attack in a prescribed class of attacks. The embedder is allowed to filter the host signal and add a watermark, thereby making the scheme nonadditive. The theory is applied to wavelet-based image watermarking. We find that, in this framework, additive watermarks are clearly suboptimal.

We consider the estimation of an unknown arbitrary 2D object shape from sparse noisy samples of its Fourier transform. The estimate of the closed boundary curve is parametrized by normalized Fourier descriptors (FDs). We use Rissanen's (1998) MDL criterion. to regularize this ill-posed non-linear inverse problem and determine an optimum tradeoff between approximation and estimation errors by picking an optimum order for the FD parametrization. The performance of the proposed estimator is quantified in terms of the area discrepancy between the true and estimated object. Numerical results demonstrate the effectiveness of the proposed approach.

We address the problem of computing fundamental performance bounds for estimation of object boundaries from noisy measurements in inverse problems, when the boundaries are parameterized by a finite number of unknown variables. Our model applies to multiple unknown objects, each with its own unknown gray level, or color, and boundary parameterization, on an arbitrary known background. While such fundamental bounds on the performance of shape estimation algorithms can in principle be derived from the Cramer-Rao lower bounds, very few results have been reported due to the difficulty of computing the derivatives of a functional with respect to shape deformation. We provide a general formula for computing Cramer-Rao lower bounds in inverse problems where the observations are related to the object by a general linear transform, followed by a possibly nonlinear and noisy measurement system.

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.

An information-theoretic model for image watermarking and data hiding is presented in this paper. Previous theoretical results are used to characterize the fundamental capacity limits of image watermarking and data-hiding systems. Capacity is determined by the statistical model used for the host image, by the distortion constraints on the data hider and the attacker, and by the information available to the data hider, to the attacker, and to the decoder. We consider autoregressive, block-DCT, and wavelet statistical models for images and compute data-hiding capacity for compressed and uncompressed host-image sources. Closed-form expressions are obtained under sparse-model approximations. Models for geometric attacks and distortion measures that are invariant to such attacks are considered.

It has been observed from image denoising experiments that translation invariant (TI) wavelet transforms often outperform orthogonal wavelet transforms. This paper compares the two transforms from the viewpoint of approximation theory, extending previous results based on Haar wavelets. The advantages of the TI expansion over orthogonal expansion are twofold: the TI expansion produces smaller approximation error when approximating a smooth function, and it mitigates Gibbs artifacts when approximating a discontinuous function.

We propose image restoration algorithms based on adaptive wavelet-domain statistical models. We present a method to estimate the model parameters from the observations, and solve the restoration problem in orthonormal and translation-invariant wavelet domains. Substantial improvements over previous wavelet-based restoration methods are obtained. The use of a translation-invariant basis further enhances the restoration performance.

This paper describes a game-theoretic methodology to design and embed watermarks in images. The optimality criterion is the decoder error probability. Analytical solutions are presented for problems involving Gaussian host images and illustrated with examples. Significant improvements over previous designs are obtained.

This paper develops an optimization methodology for designing and embedding synchronization patterns in images, for watermarking applications in which the host image is not available the decoder. Optimality is in the sense of a certain Fisher information game between the embedder and the attacker. Analytical solutions are derived for problems involving translation, rotation, linear filtering, and additive Gaussian noise attacks.

We address image estimation from sparse Fourier samples. The problem is formulated as joint estimation of the supports of unknown sparse objects in the image, and pixel values on these supports. The domain and the pixel values are alternately estimated using the level-set method and the conjugate gradient method, respectively. Our level-set evolution shows a unique switching behavior, which stabilizes the level-set evolution and removes the re-initialization steps in conventional level set approaches.

We study a new approach to image denoising based on complexity regularization. This technique presents a flexible alternative to the more conventional l/sup 2/,l/sup 1/, and Besov regularization methods. Different complexity measures are considered, in particular those induced by state-of-the-art image coders. We focus on a Gaussian denoising problem and derive a connection between complexity-regularized denoising and operational rate-distortion optimization. This connection suggests the use of efficient algorithms for computing complexity-regularized estimates. Bounds on denoising performance are derived in terms of an index of resolvability that characterizes the compressibility of the true image. Comparisons with state-of-the-art denoising algorithms are given.

This paper presents an information-theoretic analysis of statistical dependencies between image wavelet coefficients. The dependencies are measured using mutual information, which has a fundamental relationship to data compression, estimation, and classification performance. Mutual information is computed analytically for several statistical image models, and depends strongly on the choice of wavelet filters. In the absence of an explicit statistical model, a method is studied for reliably estimating mutual information from image data. The validity of the model-based and data-driven approaches is assessed on representative real-world photographic images. Our results are consistent with empirical observations that coding schemes exploiting inter- and intrascale dependencies alone perform very well, whereas taking both into account does not significantly improve coding performance. A similar observation applies to other image processing applications.

Several powerful, but heuristic techniques in the image denoising literature have used overcomplete image representations. A general framework for incorporating information from multiple representations based on fundamental statistical estimation principles was presented in Ishwar and Moulin (1999) where, information about image attributes from multiple wavelet transforms was incorporated as moment constraints on the underlying image prior. In this paper we explore the fundamental equivalence between the stochastic setting of multiple-domain restoration in Ishwar and Moulin and its deterministic set-theoretic counterpart. The main technical tool is the Lagrange multiplier theory of constrained optimization. The insights gained by this analysis allow us to derive a state-of-the-art denoising algorithm.

An information-theoretic analysis of watermarking is presented in this paper. We formulate watermarking as a communication problem with side information at the encoder and decoder and determine the hiding capacity, which upper-bounds the rates of reliable transmission and quantifies the fundamental tradeoff between three quantities: the achievable watermarking 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. For several important problems, the hiding capacity is the same whether or not the decoder knows the host data set. It is also shown that existing watermarking systems in the literature operate far below capacity.

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 a 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 results make it possible to generate confidence regions for arbitrary prescribed probabilities. These 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.

Translation-invariant denoising was introduced by Coifman and Donoho (1995) to overcome Gibbs-type phenomena produced by transform-domain shrinkage estimators in the vicinity of signal discontinuities. Shrinkage estimators are in general not shift-invariant. Shift-invariant denoising consists of a simple averaging of the shrinkage estimates over a family of cyclic spatial-shifts of the image. Shift-invariant denoising is denoising in an overcomplete basis, and work in this area has been devoted towards finding a best basis in the overcomplete family. This paper presents a maximum a posteriori (MAP) framework for shift-invariant restoration of images using the maximum-entropy prior consistent with moment constraints on the transform coefficients in different subbands. The simple averaging of estimates in the classical shift-invariant denoising can then be shown to be a certain limiting case within this framework.

In a variety of applications (including automatic target recognition) image classification algorithms operate on compressed image data. This paper explores the design of optimal transform coders and scalar quantizers using Chernoff bounds on probability of misclassification as the measure of classification accuracy. This design improves the classification performance but the mean square error (as well as the visual quality) of the coded image degrades. However, by appropriately combining classification accuracy and mean square error in the cost function, one can achieve good classification with low (visual) distortion, which is desirable in classification systems requiring visual authentication.

We develop an information-theoretic analysis of dependencies between image wavelet coefficients. The dependencies are measured using mutual information, which has a direct link with data compression and estimation performance. Mutual information can be computed analytically for the special case where the image is a stationary autoregressive (AR)-1 Gaussian process. We have also developed methods to compute mutual information experimentally from wavelet domain image data. Our mutual-information analysis provides a mechanism for model evaluation and comparison.

We apply the complexity-regularization principle to Poisson imaging. We formulate a natural distortion measure in the image space, and present a connection between complexity-regularized estimation and rate-distortion theory. For computational tractability, we apply constrained coders such as JPEG or SPIHT to solve the optimization problem approximately. Also, we design a simple predictive coder which lends itself well to our optimization problem.

We introduce a new wavelet image coder which is the forward-adaptive counterpart of the state-of-the-art backward-adaptive estimation-quantization coder. The variance field associated with the wavelet coefficients is estimated, lossily compressed, and transmitted as side information. Next, the wavelet coefficients are compressed using that side information. We optimize the resulting two-part coder based on an information-theoretic analysis. The performance of the forward-and backward-adaptive compression algorithms is compared based on several numerical experiments.

An information-theoretic model for image watermarking and data hiding systems is presented. The fundamental capacity limits of these systems are determined by the statistical model used for the host image, by the distortion constraints on the data hider and the attacker, and by the information available to the data hider, to the attacker, and to the decoder. We consider wavelet statistical models for images and compute the data hiding capacity for compressed and uncompressed host image sources. Closed form expressions are obtained under sparse-model approximations.

The proliferation of digital images creates problems for managing large image databases, indexing individual images, and protecting intellectual property. This paper introduces a novel image indexing technique that may be called an image hash function. The algorithm uses randomized signal processing strategies for a non-reversible compression of images into random binary strings, and is shown to be robust against image changes due to compression, geometric distortions, and other attacks. This algorithm brings to images a direct analog of message authentication codes (MACs) from cryptography, in which a main goal is to make hash values on a set of distinct inputs pairwise independent. This minimizes the probability that two hash values collide, even, when inputs are generated by an adversary.

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.

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

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.

Several powerful, but heuristic techniques in recent image denoising literature have used multiple (typically overcomplete) image representations. This paper presents a framework for multiple-domain image modeling and restoration, based on fundamental statistical estimation principles. Information about image attributes from multiple wavelet transforms is incorporated as moment constraints on the underlying image prior. Our method constructs the maximum entropy distribution consistent with these moment constraints. A maximum a posteriori probability (MAP) image restoration algorithm based on this maximum entropy prior is developed. Unlike previous multiple-domain algorithms, ours satisfies certain desirable optimality properties and provides an information-theoretic figure of merit for the choice of domains. Simulation results show that the estimator is vastly superior to single-domain image restoration both in terms of mean squared error and perceptual quality.

In this paper, we propose a novel hierarchical statistical model for image wavelet coefficients. A simple classification scheme is used to construct a model that captures interscale and intrascale dependencies of wavelet coefficients. Applications to image denoising are presented. We develop a simple algorithm that outperforms other wavelet denoising schemes that exploit first order statistics, or inter- or intra-scale dependencies alone.

We introduce a simple spatially adaptive statistical model for wavelet image coefficients and apply it to image denoising. Our model is inspired by a recent wavelet image compression algorithm, the estimation-quantization (EQ) coder. We model wavelet image coefficients as zero-mean Gaussian random variables with high local correlation. We assume a marginal prior distribution on wavelet coefficients variances and estimate them using an approximate maximum a posteriori probability rule. Then we apply an approximate minimum mean squared error estimation procedure to restore the noisy wavelet image coefficients. Despite the simplicity of our method, both in its concept and implementation, our denoising results are among the best reported in the literature.

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

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 (GGDs). 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 mis-specifications of the prior-a basic concern in image processing applications.

We present a novel framework for denoising signals from their compact representation in multiple domains. Each domain captures, uniquely, certain signal characteristics better than others. We define confidence sets around data in each domain and find sparse estimates that lie in the intersection of these sets, using a POCS algorithm. Simulations demonstrate the superior nature of the reconstruction (both in terms of mean-square error and perceptual quality) in comparison to the adaptive Wiener filter.

We propose the use of complexity regularization in image restoration. This is a flexible estimation method which borrows from previous developments in nonparametric estimation theory. The regularized estimation problem is formulated in the wavelet domain and solved using a computationally efficient multiscale relaxation algorithm.

We extend the statistical model-based estimation-quantization (EQ) wavelet image coding algorithm introduced by LoPresto, Ramchandran and Orchard (see Proceedings of the Data Compression Conference, Snowbird, UT, 1997) to include an adaptive transform component. For this, we resort to the rich, space-frequency diverse, and easy-to-search library of transforms provided by the family of wavelet packet (WP) bases and their adaptive extensions. We use rate-distortion criteria to find the best basis jointly with the statistical model-based best adaptive quantization and entropy coding strategy of LoPresto et al. based on an efficient and fast tree pruning algorithm. A key underlying attribute of our paradigm is that the spatially-varying generalized Gaussian mixture model for wavelet coefficients introduced by LoPresto et al. is also applicable to the more arbitrary framework of (adaptive) wavelet packet transform coefficients as well. Our WP-EQ framework produces excellent results on standard test images. The most attractive property of our paradigm is its "universality" and robustness: based on an overall performance criterion that considers diverse classes of input test images that have varying space-frequency characteristics, it is more powerful than most of the existing image coding algorithms, using reasonable complexity, and a generic, integrated, non-training based framework.

In this paper, fundamental limitations of the control grid interpolation and block matching schemes for motion compensation are remedied by a novel idea which embodies positive features of both schemes. The enhanced scheme performs both consistently and significantly better than either method does individually.

We introduce a new complexity regularization method for image denoising and explore the use of sophisticated complexity penalties. We have found improvements of the order of 2 dB in reconstructed image mean-squared error over existing complexity-regularized estimators.

We present a systematic approach to forward-motion-compensated predictive video coding. The first step is the definition of a flexible model that compactly represents motion fields. The inhomogeneity and spatial coherence properties of motion fields are captured using linear multiscale models. One possible design is based on linear finite elements and yields a multiscale extension of the triangle motion compensation (TMC) method. The second step is the choice of a computational technique that identifies the coefficients of the linear model. We study a modified optical flow technique and minimize a cost function closely related to Horn and Schunck's (1981) criterion. The cost function balances accuracy and complexity of the motion compensated predictor and is viewed as a measure of goodness of the motion field. It determines not only the coefficients of the model, but also the quantization method. We formulate the estimation and quantization problems jointly as a discrete optimization problem and solve it using a fast multiscale relaxation algorithm. A hierarchical extension of the algorithm allows proper handling of large displacements. Simulations on a variety of video sequences have produced improvements over TMC and over the half-pel-accuracy, full-search block matching algorithm, in excess of 0.5 dB in average. The results are visually superior as well. In particular, the reconstructed video is entirely free of blocking artifacts.

The design of a M-band FIR paraunitary filter bank adapted to input signal statistics is considered. The adaptation criterion is energy compaction. A simple, efficient technique for computing globally optimal filter banks of arbitrary, finite degree is presented.

Motion estimation is an important component of video coding systems because it enables us to exploit the temporal redundancy in the sequence. The popular block-matching algorithms (BMAs) produce unnatural, piecewise constant motion fields that do not correspond to "true" motion. In contrast, our focus here is on high-quality motion estimates that produce a video representation that is less dependent on the specific frame-rate or resolution. To this end, we present an iterated registration algorithm that extends previous work on multiscale motion models and gradient-based estimation for coding applications. We obtain improved motion estimates and higher overall coding performance. Promising applications are found in temporally-scalable video coding with motion-compensated frame interpolation at the decoder. We obtain excellent interpolation performance and video quality; in contrast, BMA leads to annoying artifacts near moving image edges.

Recent work on filter banks and related expansions has revealed an interesting insight: different filter bank trees can be regarded as different ways of constructing orthonormal bases for linear signal expansion. In particular, fast algorithms for finding best bases in an operational rate-distortion sense have been successfully used in image coding. Independently of this work, recent research has also explored the design of filter banks that optimize energy compaction for a single signal or a class of signals. In this paper we integrate these two different but complementary approaches to best-basis design and propose an image coder in which subband filter banks, tree structure and quantizers are chosen so as to optimize rate-distortion performance. These optimal filter banks, tree structure and quantizers represent side information. They are selected from a codebook designed from training data, using a rate-distortion criterion.

The design of a quadrature-mirror filter (QMF) bank (H,G) adapted to the input signal statistics is considered. The adaptation criterion is the maximization of the coding gain and has so far been viewed as a difficult nonlinear constrained optimization problem. It is shown that in fact the coding gain depends only upon the product filter P(z)=H(z)H(z/sup -1/). The optimization problem formulated in terms of the coefficients of P(z) gives rise to a linear semi-infinite program (SIP). A simple SIP algorithm using a discretization method is presented. The filter H(z) is obtained by deflation and spectral factorization of P(z).

Motion estimation is an important part of most video coding schemes because it enables us to exploit the high degree of temporal redundancy present. Though block matching algorithms (BMA) yield coarse and piecewise-constant fields, they are very popular due to their simplicity and low bit overhead. In this paper, we propose to use a more advanced gradient-based technique to overcome the disadvantages of BMA. A dense motion field is estimated and compressed using a hierarchical finite element (HFE) representation, leading to an efficient, highly parallel, iterative, multiresolution optimization algorithm. The scheme also uses multiresolution measurements and a coarse-to-fine strategy to estimate large displacements. At comparable bit rates, the motion fields are much smoother and more natural than those produced by BMA. Coding gains of about 0.6 dB were obtained on Claire. More importantly, substantial visual improvements were obtained, mainly due to improved performance near the edges.

Develops a technique for improving the applicability of complete, nonorthogonal, multiresolution transforms to image coding. As is well known, the L(2) norm of the quantization errors is not preserved by nonorthogonal transforms, so the L(2) reconstruction error may be unacceptably large. However, given the quantizers and synthesis filters, the authors show that this artifact can be eliminated by formulating the coding problem as that of minimizing the L(2) reconstruction error over the set of possible encoded images. With this new formulation, the coding problem becomes a high-dimensional, discrete optimization problem and features a coupling between the redundancy-removing and quantization operations. A practical solution to the optimization problem is presented in the form of a multiscale relaxation algorithm, using inter- and intrascale quantization noise feedback filters. Bounds on the coding gain over the standard coding technique are derived. A simple extension of the algorithm allows for the use of a weighted L(2) error criterion and deadband (non-MMSE) quantizers. Experiments using biorthogonal spline filter banks demonstrate appreciable SNR gains over the standard coding technique, and comparable visual improvements.

We present a technique for improving the applicability of complete, nonorthogonal, multiresolution transforms to image coding. As is well known, the L/sup 2/ norm of the quantization error is not preserved by nonorthogonal transforms, so the L/sup 2/ reconstruction error may be unacceptably large. However, given the quantizers and synthesis filters, we show that this artifact can be eliminated by formulating the coding problem as that of minimizing the L/sup 2/ reconstruction error over the set of possible encoded images. This high-dimensional, discrete optimization problem is solved using a multiscale relaxation algorithm. Bounds on the coding gain over the standard coding technique are derived. Experiments using biorthogonal spline filters demonstrate appreciable SNR gains over the standard coding technique, and comparable visual improvements.>

The author considers the classical problem of estimating a signal f, given noisy samples of a linear transformation of f. A nonlinear regression method is proposed for estimating f in the class of polynomial B-splines defined over nonuniform grids. This type of approximation offers great flexibility, as the number of knots, knot locations, and knot coefficients are free parameters. Estimates are obtained using a simple iterative algorithm derived by application of a multistage hypothesis-testing procedure.>

A multiresolution image representation is proposed as a basis for constructing an approximation to an original image. The method is based on adaptive finite elements, a technique used in applied mathematics to solve numerically partial differential equations while preserving important features of the solution at different scales. Theory and experiments suggest that adaptive finite elements is a natural and computationally-powerful approach to image approximation problems. The particular representation is based on hierarchical finite elements. A multiresolution algorithm computes the solution to the approximation problem in O(N) time on a sequential machine and in O(logN) time on a single-instruction, multiple-data, fine-grain parallel architecture, where N is the number of pixels in the image. Applications to the problems of image compression and restoration are given.>

A method of sieves using splines is proposed for regularizing maximum-likelihood estimates of power spectra. This method has several important properties, including the flexibility to be used at multiple resolution levels. The resolution level is defined in terms of the support of the polynomial B-splines used. An expression for the optimal rate of growth of the sieve is derived using a discrepancy measure derived from the Kullback-Leibler divergence of parameterized density functions. While the sieves may be defined on nonuniform grids, in the case of uniform grids the optimal sieve size corresponds to an optimal resolution. Iterative algorithms for obtaining the maximum-likelihood sieve estimates are derived. Applications to spectrum estimation and radar imaging are proposed.>

A novel approach is developed for forming high-resolution images of radar targets from delay Doppler spotlight-mode radar data. This approach is based on a model for the target's reflectivity in terms of wide-sense stationary, uncorrelated scatterers having complex-valued Gaussian statistics. The imaging problem is to estimate the target's scattering function in terms of radar-echo data acquired with a series of target illuminations. A method is developed for solving this multidimensional spectrum estimation problem through the use of maximum-likelihood estimation implemented using the expectation-maximization algorithm.>