Hamiltonian path based image steganography scheme with improved imperceptibility and undetectability

Steganography is the art of concealing secret information in some cover medium (picture, text etc.) which is being used at large scale in different security systems. Various schemes of data hiding in images have been proposed over the last two decades that focus on improving the visual quality of the cover image. But there is always a trade-off between imperceptibility and payload. Another important issue is data security. It is known that histograms can reveal the existence and quantum of data hidden in a stego image. So, the main challenge of high capacity data embedding schemes is to reduce the image distortion as well as to keep the data secure by making use of alternate mechanisms such as secret keys. In this paper, we propose a novel data hiding scheme with two-fold objective. Data security is ensured by making use of a Hamiltonian path to generate a secret key for accessing data embedding patterns. Due to the complexity of Hamiltonian path generation, the embedding patterns become almost impossible to guess, even if the presence of secret data is observed using steganographic attacks. Secondly, two optimization strategies are proposed to minimize the embedding effect on the stego image. While the first strategy focuses on reducing the bit-flipping cost, the other strategy improves histogram distortion. The proposed method is shown to outperform some of the existing and recent approaches both in terms of payload and imperceptibility.