Exact histogram specification (EHS) is a classic image processing problem which generalises histogram equalisation. Over the years, no optimum solution to the EHS problem has been given with respect to any similarity criterion. An analytic and efficient solution to the optimum EHS problem, according to the mean squared error (MSE) criterion, is presented here. The inverse problem is also examined, and closed-form performance analyses are given in both cases.

A solution to the problem of asymptotically optimum perfect universal steganography of finite memoryless sources with a passive warden is provided, which is then extended to contemplate a distortion constraint. The solution rests on the fact that Slepian's Variant I permutation coding implements first-order perfect universal steganography of finite host signals with optimum embedding rate. The duality between perfect universal steganography with asymptotically optimum embedding rate and lossless universal source coding with asymptotically optimum compression rate is evinced in practice by showing that permutation coding can be implemented by means of adaptive arithmetic coding. Next, a distortion constraint between the host signal and the information-carrying signal is considered. Such a constraint is essential whenever real-world host signals with memory (e.g., images, audio, or video) are decorrelated to conform to the memoryless assumption. The constrained version of the problem requires trading off embedding rate and distortion. Partitioned permutation coding is shown to be a practical way to implement this trade-off, performing close to an unattainable upper bound on the rate-distortion function of the problem.

This paper exploits the connection between minimum-distortion perfect counterforensics and maximum-rate perfect steganography in order to provide the optimum solution to the first of these problems, in the case in which the forensic detector solely uses first-order statistics. The solution relies on Slepian's variant I permutation codes, which had previously been shown to implement maximum-rate perfect steganography when the host is memoryless (equivalently, when the steganographic detector only uses first-order statistics). Additionally, we demonstrate a blind counterforensic strategy made possible by permutation decoding, which may also find application in image processing.

We show that Slepian's Variant I permutation codes implement firstorder perfect steganography (i.e., histogram-preserving steganography). We give theoretical expressions for the embedding distortion, embedding rate and embedding efficiency of permutation codes in steganography, which demonstrate that these codes conform to prior analyses of the properties of capacity-achieving perfect stegosystems with a passive warden. We also propose a modification of adaptive arithmetic coding that near optimally implements permutation coding with a low complexity, confirming all our theoretical predictions. Finally we discuss how to control the embedding distortion. Permutation coding turns out to be akin to Sallee's model-based steganography, and to supersede both this method and LSB matching.

DNA data embedding is a newly emerging field aspiring to encode data in deoxyribonucleic acid (DNA). DNA is an inherently digital and noisy medium, undergoing substitution, insertion and deletion mutations. Hence, encoding information in DNA can be seen as a particular case of digital communications in which biological constraints must be observed. In this paper we propose a modification of Davey and MacKay's watermark synchronisation code (unrelated to digital watermarking) to create an encoding procedure more biocompatible with the host organism than previous methods. In addition, when combined with a low density parity check (LDPC) code, the method provides near-optimum error correction. We also obtain the theoretical embedding capacity of DNA under substitution mutations for the increased biocompatibility constraint. This result, along with an existing bound on capacity for insertion and deletion mutations, is compared to the proposed algorithm's performance by means of Monte Carlo simulations.

BACKGROUND: In recent times, the application of deoxyribonucleic acid (DNA) has diversified with the emergence of fields such as DNA computing and DNA data embedding. DNA data embedding, also known as DNA watermarking or DNA steganography, aims to develop robust algorithms for encoding non-genetic information in DNA. Inherently DNA is a digital medium whereby the nucleotide bases act as digital symbols, a fact which underpins all bioinformatics techniques, and which also makes trivial information encoding using DNA straightforward. However, the situation is more complex in methods which aim at embedding information in the genomes of living organisms. DNA is susceptible to mutations, which act as a noisy channel from the point of view of information encoded using DNA. This means that the DNA data embedding field is closely related to digital communications. Moreover it is a particularly unique digital communications area, because important biological constraints must be observed by all methods. Many DNA data embedding algorithms have been presented to date, all of which operate in one of two regions: non-coding DNA (ncDNA) or protein-coding DNA (pcDNA). RESULTS: This paper proposes two novel DNA data embedding algorithms jointly called BioCode, which operate in ncDNA and pcDNA, respectively, and which comply fully with stricter biological restrictions. Existing methods comply with some elementary biological constraints, such as preserving protein translation in pcDNA. However there exist further biological restrictions which no DNA data embedding methods to date account for. Observing these constraints is key to increasing the biocompatibility and in turn, the robustness of information encoded in DNA. CONCLUSION: The algorithms encode information in near optimal ways from a coding point of view, as we demonstrate by means of theoretical and empirical (in silico) analyses. Also, they are shown to encode information in a robust way, such that mutations have isolated effects. Furthermore, the preservation of codon statistics, while achieving a near-optimum embedding rate, implies that BioCode pcDNA is also a near-optimum first-order steganographic method.

A number of methods have been proposed over the last decade for encoding information using deoxyribonucleic acid (DNA), giving rise to the emerging area of DNA data embedding. Since a DNA sequence is conceptually equivalent to a sequence of quaternary symbols (bases), DNA data embedding (diversely called DNA watermarking or DNA steganography) can be seen as a digital communications problem where channel errors are analogous to mutations of DNA bases. Depending on the use of coding or noncoding DNA host sequences, which, respectively, denote DNA segments that can or cannot be translated into proteins, DNA data embedding is essentially a problem of communications with or without side information at the encoder. In this paper, the Shannon capacity of DNA data embedding is obtained for the case in which DNA sequences are subject to substitution mutations modeled using the Kimura model from molecular evolution studies. Inferences are also drawn with respect to the biological implications of some of the results presented.

The goal of DNA data embedding is to enable robust encoding of non-genetic information in DNA. This field straddles the areas of bioinformatics and digital communications, since DNA mutations can be seen as akin to a noisy channel from the point of view of information encoding. In this paper we present two algorithms which, building on a variant of a method proposed by Yachie et al., rely on repetition coding to effectively counteract the impact that mutations have on an embedded message. The algorithms are designed for resynchronising multiple, originally identical, information encoded DNA sequences, embedded within non-coding DNA (ncDNA) sections of a host genome. They use both BLAST and MUSCLE algorithms to accomplish this. Bit error rates at the decoder are established for mutations rates accumulated over a number of generations of the host organism. The empirical results obtained are compared to a theoretical bound for optimal decoding.

This paper firstly gives a brief overview of information embedding in deoxyribonucleic acid (DNA) sequences and its applications. DNA data embedding can be considered as a particular case of communications with or without side information, depending on the use of coding or noncoding DNA sequences, respectively. Although several DNA data embedding methods have been proposed over the last decade, it is still an open question to determine the maximum amount of information that can theoretically be embedded-that is, its Shannon capacity. This is the main question tackled in this paper.

We present a theoretical analysis of the Philips audio fingerprinting method under Gaussian white noise distortion for correlated stationary Gaussian sources. Prior analyses were for white Gaussian sources, which do not model realistically real audio signals. Our approach relies on formulating the unquantized fingerprint as a quadratic form, which affords a systematic way to compute the model parameters. We provide closed-form analytical upper bounds for the probability of bit error of the hash, and we apply these expressions to real audio signals.

We present a 2-D extension of a timing error detector (TED) originally developed by Mueller and Muller for timing recovery on multilevel pulse amplitude modulation (PAM) over 1-D channels. We provide accurate theoretical expressions of the performance of the proposed scheme, and we verify its applicability by studying a particular case. The 2-D TED thus obtained is used as the engine of a 2-D phase locked loop (PLL) for timing recovery.

We present a novel theoretical analysis of the Philips audio fingerprinting method proposed by Haitsma, Kalker, and Oostveen (2001). Although this robust hashing algorithm exhibits very good performance, the method has only been partially analyzed in the literature. Hence, there is a clear need for a more complete analysis which allows both performance prediction and systematic optimization. We examine here the theoretical performance of the method for Gaussian inputs by means of a statistical model. Our analysis relies on formulating the unquantized fingerprint as a quadratic form, which affords a systematic way to compute the model parameters. We provide closed-form analytical upperbounds for the probability of bit error of the hash for two relevant scenarios: noise addition and desynchronization. We show that these results are useful when applied to real audio signals

A new approach to synchronization recovery for signals watermarked using the dither modulation data hiding scheme is presented. The strategy followed involves the use of a digital phase-locked loop to track the offsets applied by an attacker to the sampling grid of the watermarked signal. The main element in this synchronization loop is the timing error detector which is responsible for generating an error signal, used to update the estimates of the applied offsets. It is shown how a timing error detector which has been used in digital communications may be easily adapted to extract timing information from DM watermarked signals. The performance of the proposed synchronizer is evaluated using the probability of decoding error under different models for the sampling grid offsets

Soft hashing, also known as robust hashing or perceptual hashing, consists of summarising multimedia data, so as to obtain a concise representation called a hash value. There has been an increasing interest in the soft hashing problem recently. Techniques implementing soft hashing intend to mirror the behaviour of cryptographic hashing, when the information to be hashed can be subject to different kinds of distortion. Many heuristic techniques for undertaking soft hashing of images and other multimedia data have been devised. Except for some attempts, a framework giving solid guidelines to solve the problem is largely lacking. We provide one possible approach to undertake the modelling of robust soft hashing, detailing the basic problems involved. We show how some prior schemes partly fit into our model.

In this paper, we analyze spread-spectrum and quantization projection data hiding methods from a game-theoretic point of view, using the bit error rate (BER) as the payoff, and assuming that the embedder simply follows point-by-point constraints given by a perceptual mask, whereas for the attacker an MSE-like constraint is imposed. The optimal attacking and decoding strategies are obtained by making use of a theorem that in addition states that those strategies constitute an equilibrium of the game. Experimental results supporting our analyses are also shown.

The binary distortion compensated dither-modulation (DC-DM), which can be regarded to as a baseline for quantization-based data-hiding methods, is rigorously analyzed. A novel and accurate procedure for computing the exact probability of bit error is given, as well as an approximation amenable to differentiation which allows to obtain the optimal weights in a newly proposed decoding structure, for significant improvements on performance. The results are particularized for a JPEG compression scenario which allows to show their usefulness. Experimental results validating the proposed theory are presented.

We propose a novel data hiding procedure called quantized projection (QP), that combines elements from quantization (i.e. quantization index modulation, QIM) and spread-spectrum methods. The method is based on quantizing a diversity projection of the host signal, inspired in the statistic used for detection in spread-spectrum algorithms. We carry out a theoretical analysis of QP together with its empirical validation to show rigorously that it offers an excellent performance; QP features probabilities of decoding error several orders of magnitude lower than the aforementioned families of methods for the same dimensionality (diversity) and attacking distortion level. In addition, we introduce a Costa-based improvement (see Costa, M.H.M., IEEE Trans. on Inf. Theory, vol.29, no.3, p.439-41, 1983) of the basic QP method named distortion compensated QP.

It has been claimed that quantization-based data-hiding methods offer an advantage over spread-spectrum schemes. In this paper we review this assertion by presenting a new look on the assumptions made for these claims, and we give a new performance comparison between both approaches under random additive channel distortions. The existence of a threshold in the distortion level for the goodness of each of the methods is shown.

The quantization of a linear projective transformation first proposed by Chen and Wornell is shown to allow for much better performance figures than those yielded by previous approaches. The procedure to achieve this improvement is explained through the proposal and analysis of an improved data hiding method called quantized projection (QP), based in the quantization of a statistic similar to those used at detection in spread-spectrum algorithms. Both the theoretical analysis and the empirical validation show that projection-based methods exhibit huge performance improvements over existing ones under the same conditions - i.e. same degree of diversity and level of random additive attacking distortion.