A Block Permutational Steganographic Algorithm for Scanned Documents and other Images

Steganography studies the embedding of messages into cover mediums, while obscuring the fact that any message exists. A supplement to encryption, steganographic methods help to avoid attention from adversaries, who may take additional measures if made aware of such messages. Common forms of image steganography, such as Least Significant Bit steganography, alter the first-order statistics of a cover image, allowing for easier detection by methods such as the Wavelet Motion Analyzer. We study steganographic methods based on permutation of pixels in grayscale images, which do not share this disadvantage. A generalization of pixel-swapping methods, our algorithm identifies invariant sets of pixels and intensities, called Permissible Sets, within an image block, and allow their full permutation in the encoding or decoding of messages. This increase in the number of permissible permutations serves to reduce the detectability of our method, while increasing the bit-per-pixel embedding rate. Through direct implementation and comparison, we find our method to be an improvement over previous swap-based steganography for the Microsoft Research Cambridge dataset of general images, and a large improvement for the higher-resolution NoisyOffice dataset of scanned images.