Optimum Perfect Steganography of Memoryless Sources as a Rate-Distortion Problem

Slepian’s variant I permutation coding has been recently shown to be a fundamental steganographic tool, as it implements optimum perfect steganography of memoryless sources. Although real host signals are not memoryless, a decorrelating energy-preserving transform can always be applied before a method that assumes a memoryless source, as is usually done in the dual problem of source coding. A further constraint is needed in practice: the information-carrying signal must be close to the host, according to some distance measure. Thus steganography of memoryless sources using permutation coding is a rate-distortion problem. Here we delve deeper in the study of the embedding distortion of permutation coding, and we show that the rate-distortion tradeoff for partitioned permutation coding is nearoptimum according to the Gel’fand and Pinsker capacity formula.