We present a novel lossless universal source coding algorithm that uses parallel computational units to increase the throughput. The length-N input sequence is partitioned into B blocks. Processing each block independently of the other blocks can accelerate the computation by a factor of B, but degrades the compression quality. Instead, our approach is to first estimate the minimum description length (MDL) source underlying the entire input, and then encode each of the B blocks in parallel based on the MDL source. With this two-pass approach, the compression loss incurred by using more parallel units is insignificant. Our algorithm is work-efficient, i.e., its computational complexity is O(N=B). Its redundancy is approximately B log(N=B) bits above Rissanen's lower bound on universal coding performance, with respect to any tree source whose maximal depth is at most log(N=B).

Robust image hashing has been actively researched over the last decade with varied applications in image content authentication and identification under distortions. In the existing literature on robust image hashing, hash algorithms are ignorant of the class of images being hashed. There are however significant application domains such as that of face image hashing where apriori knowledge of the image class as well as permissible distortions can benefit hash algorithm design. In this paper, we present a two stage cascade of dimensionality reduction constructs for face image hashing. The first stage aims to project the face image to a space where geometric distortions manifest approximately as additive noise. For this purpose, we use the non-negative matrix approximations based hash vector developed by Monga et al. which is known to possess excellent geometric attack robustness. In the second stage, we employ oriented principal component analysis (OPCA) based on estimating signal as well as noise statistics in a learning phase and deriving a projection that mitigates the effect of noise. We obtain both experimentally based ROC curves as well as analytical ones via a detection theoretic analysis of the proposed framework. The ROC curves reveal clearly that incorporating such a learning phase greatly reduces error probabilities.

We consider the digital fingerprinting (FP) problem and model it as a multiuser communications problem and develop a detection theoretic framework. In the general case, colluders apply uniform linear averaging followed by additive colored Gaussian noise. For each user, the receiver computes the correlation between the attacked signal and a linear-transformed version of that user's fingerprint, and performs thresholding (focused detection). Assuming independent colluders with potentially unequal priors, we derive generic exact bit-error probability (BEP) expressions, together with tight bounds, for arbitrary FP codes. Then, we specialize our results to orthogonal, simplex and Gaussian codes in the presence of additive white Gaussian noise; under mean squared error distortion constraints on the embedder and the colluders, we analytically quantify the optimal detection rule, the resulting minimum BEP and its asymptotic behavior, the collusion resistance, and the error exponent for the aforementioned codes, and compare their performances. We show that the minimum BEP expressions for these codes obey the same functional form and that they can be ordered as simplex, orthogonal, and Gaussian in terms of increasing BEP.

In this work, we consider the ISS (improved spread spectrum) watermarking [1] framework, and propose a generalized version of it, termed “Generalized Improved Spread Spectrum” (GISS), where we achieve both host-interference cancelation and robustness to “translation” attacks up to some tolerance. In particular, we reduce the correlation between the watermark and the host, not only at the embedding location, but also within an a-priori-defined neighborhood around it. We show that the resulting framework leads to a constrained quadratic optimization problem, where the cost function and the constraint represent the amount of host interference on the watermark and the norm of the resulting “host interference cancelation sequence” (HICS), respectively. We provide a closed-form analytical solution to this optimization problem and experimentally demonstrate its effectiveness for 1D signals.

We introduce a lightweight biometric solution for user authentication over networks using online handwritten signatures. The algorithm proposed is based on a modified Hausdorff distance and has favorable characteristics such as low computational cost and minimal training requirements. Furthermore, we investigate an information theoretic model for capacity and performance analysis for biometric authentication which brings additional theoretical insights to the problem. A fully functional proof-of-concept prototype that relies on commonly available off-the-shelf hardware is developed as a client-server system that supports Web services. Initial experimental results show that the algorithm performs well despite its low computational requirements and is resilient against over-the-shoulder attacks.

In this paper, the bit-search type irregular decimation algorithms, that are used within linear-feedback shift register (LFSR)-based stream ciphers, are investigated. In particular, bit-search generator (BSG) and and its variant ABSG are concentrated on and two different setups are considered for the analysis. In the first case, the input is assumed to be an$m$-sequence; it is shown that all possible output sequences can be classified into two sets, each of which is characterized by the equivalence of their elements up to shifts. Furthermore, it is proved that the cardinality of each of these sets is equal to the period of one of its elements and subsequently the (upper and lower) bounds on the expected output period (assuming that no subperiods exist) are derived. In the second setup, we work in a probabilistic framework and assume that the input sequence is evenly distributed (i.e., independent and identically distributed (i.i.d.) Bernoulli process with probability$1/2$). Under these assumptions, closed-form expressions are derived for the distribution of the output length and the output rate, which is shown to be asymptotically Gaussian-distributed and concentrated around the mean with exponential tightness.

In this paper, we propose a novel method for watermarking compressed video for streaming. The proposed method performs motion compensated watermarking. There are two consequences of this; first we see that the impact of the watermark on the final bitrate is negligible, and the proposed method has inherent robustness to mild packet losses in the channel. Experimental results show that the proposed method operates at lower distortion levels and has higher watermark detection rates compared to current watermarking methods. We observe 20% bitrate reduction for the same watermark detection rate. We also show that when data partitioning is used over a packet loss channel the proposed method performs at acceptable watermark detection rates.

Abstract—In this paper, we propose the use of non-negative matrix factorization (NMF) for image hashing. In particular, we view images as matrices and the goal of hashing as a randomized dimensionality reduction that retains the essence of the original image matrix while preventing intentional attacks of guessing and forgery. Our work is motivated by the fact that standard-rank reduction techniques, such as QR and singular value decomposition, produce low-rank bases which do not respect the structure (i.e., non-negativity for images) of the original data. We observe that NMFs have two very desirable properties for secure image hashing applications: 1) The additivity property resulting from the non-negativity constraints results in bases that capture local components of the image, thereby significantly reducing misclassification and 2) the effect of geometric attacks on images in the spatial domain manifests (approximately) as independent identically distributed noise on NMF vectors, allowing the design of detectors that are both computationally simple and, at the same time, optimal in the sense of minimizing error probabilities. Receiver operating characteristics analysis over a large image database reveals that the proposed algorithms significantly outperform existing approaches for image hashing. Index Terms—Authentication, matrix approximations, robust hashing. I.

In this paper, we propose the use of non-negative matrix factorization (NMF) for robust image hashing. In particular, we view images as matrices and the goal of hashing as a randomized dimensionality reduction that retains the essence of the original image matrix while preventing against intentional attacks of guessing and forgery. Our work is motivated by the fact that standard-rank reduction techniques such as the QR, and singular value decomposition (SVD), produce low rank bases which do not respect the structure (i.e. non-negativity for images) of the original data. We observe that NMFs have two very desirable properties for secure image hashing applications: 1) The additivity property resulting from the non-negativity constraints results in bases that capture local characteristics of the image, thereby significantly reducing misclassification, and 2) the effect of geometric attacks on images in the spatial domain manifests (approximately) as independent identically distributed noise on NMF vectors, allowing design of detectors that are both computationally simple and at the same time optimal in the sense of minimizing error probabilities. ROC (receiver operating characteristics) analysis over a large image database reveals that the proposed algorithms significantly outperform existing approaches for robust image hashing

We consider the problem of blind watermark detection from an image, when the image has undergone a geometric attack. Existing schemes for solving this problem involve insertion of periodic marks or templates, invariant properties of transforms, and feature point based techniques. A major deficiency of these approaches is either a security leak (owing to redundancy in the mark) and/or poor watermark detection performance esp. under lossy geometric attacks, e.g. cropping. In this paper, we introduce a novel watermark synchronization paradigm by using perceptual image hashes. We exploit the fact that a perceptual hash acts as a robust as well as randomized digest of image content, and use it to embed a synchronization mark into the image. Unlike existing synchronization schemes, our synchronization mark has favorable security and robustness to adversarial attacks and hence, cannot be easily removed. Experimental results confirm that our proposed algorithm has significantly lower watermark detection error probabilities than existing methods.

The difficulty of building an effective digital rights management system stems from the fact that traditional cryptographic primitives such as encryption or scrambling do not protect audio or video signals once they are played in plain-text. This fact, commonly referred to as "the analog hole," has been responsible for the popularity of multimedia file sharing which cannot be controlled, at least technically, by content's copyright owners. In this paper, we explore a specific issue in multimedia fingerprinting as an answer to "the analog hole" problem. We analyze the collusion resistance of three large classes of spread-spectrum fingerprints using a recently introduced collusion procedure, the gradient attack. Surprisingly, we show that the collusion resistance of direct-sequence and uniformly distributed spread spectrum fingerprints is a small constant that does not depend on the object size, whereas bounded Gaussian fingerprints demonstrate significantly better robustness to the gradient attack.

A powerful class of attacks in multimedia fingerprinting is known as collusion attacks, where a clique of colluders, each having a copy of the same multimedia content with different fingerprint, combine their copies to form a colluded copy. In this paper, we propose a countermeasure against collusion attacks for digital video: pseudo-random intentional de-synchronization techniques. Each user's copy of video is slightly pseudo-randomly changed (de-synchronized) in such a way that these changes will not be noticeable for an individual copy, but will be significant enough to produce perceptual artifacts when multiple copies are combined (e.g., via averaging, replacement attacks, etc.). To achieve this task, we propose several novel effective techniques, including constrained random temporal and spatial sampling. We discuss feasibility issues and limitations of video de-synchronization, and present several examples.

In this paper we suggest viewing images (as well as attacks on them) as a sequence of linear operators and propose novel hashing algorithms employing transforms that are based on matrix invariants. To derive this sequence, we simply cover a two dimensional representation of an image by a sequence of (possibly overlapping) rectangles R/sub i/ whose sizes and locations are chosen randomly/sup 1/ from a suitable distribution. The restriction of the image (representation) to each R/sub i/ gives rise to a matrix A/sub i/. The fact that A/sub i/'s will overlap and are random, makes the sequence (respectively) a redundant and non-standard representation of images, but is crucial for our purposes. Our algorithms first construct a secondary image, derived from input image by pseudo-randomly extracting features that approximately capture semi-global geometric characteristics. From the secondary image (which does not perceptually resemble the input), we further extract the final features which can be used as a hash value (and can be further suitably quantized). In this paper, we use spectral matrix invariants as embodied by singular value decomposition. Surprisingly, formation of the secondary image turns out be quite important since it not only introduces further robustness (i.e., resistance against standard signal processing transformations), but also enhances the security properties (i.e. resistance against intentional attacks). Indeed, our experiments reveal that our hashing algorithms extract most of the geometric information from the images and hence are robust to severe perturbations (e.g. up to %50 cropping by area with 20 degree rotations) on images while avoiding misclassification. Our methods are general enough to yield a watermark embedding scheme, which will be studied in another paper.

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.

We introduce a new approach for blind image watermarking: We derive robust semi-global features in wavelet domain and quantize them in order to embed the watermark. Quantization of statistics is carried out by adding scaled pseudo-random sequences that are visually unnoticeable. Our algorithm exhibits increased robustness against various attacks and it withstands standard benchmark attacks of wider trange than earlier methods (e.g., Stirmark, random bending etc.) and modifications such as compression, provided they do not cause too severe visual distortions.

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.

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.

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.

This paper deals with the application to denoising of a very simple but effective "local" spatially adaptive statistical model for the wavelet image representation that was previously introduced successfully in a compression context. Motivated by the intimate connection between compression and denoising, this paper explores the significant role of the underlying statistical wavelet image model. The model used here, a simplified version of the one proposed by LoPresto, Ramchandran and Orchard (see Proc. IEEE Data Compression Conf., 1997), is that of a mixture process of independent component fields having a zero-mean Gaussian distribution with unknown variances /spl sigma//sub s//sup 2/ that are slowly spatially-varying with the wavelet coefficient location s. We propose to use this model for image denoising by initially estimating the underlying variance field using a maximum likelihood (ML) rule and then applying the minimum mean squared error (MMSE) estimation procedure. In the process of variance estimation, we assume that the variance field is "locally" smooth to allow its reliable estimation, and use an adaptive window-based estimation procedure to capture the effect of edges. Despite the simplicity of our method, our denoising results compare favorably with the best reported results in the denoising literature.

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