Retracing extended sudoku matrix for high-capacity image steganography

Numerous data hiding algorithms have been devised for imperceptibly embedding secret messages into the cover media so as to securely transmit user privacy information over the public communication channels. Among them, the reference matrix-based schemes in spatial domain draw extensive concern on account of the simple but efficient embedding and extraction procedure. The core idea of the planar matrix-based method is let two contiguous cover pixels conceal a base-N secret digit with the guidance of reference matrix, such as Sudoku, Turtle Shell, and so on. A novel image data hiding scheme with great embedding efficiency is presented in this paper, which is based on retracing extended Sudoku (RE-Sudoku) reference matrix. Owing to the number of Sudoku solutions and various extension directions, viz., the multiformity of RE-Sudoku matrix, this scheme is exceedingly more secure than the previous methods. More momentously, the proposed two-dimensional reference matrix can guide two 9-ary notational system secret digits to be embedded into each cover pixel pair simultaneously; thereby resulting in a larger embedding rate which converges to 3.169 bits per pixel. The experimental results reveal that this image steganography outperforms the other related works in terms of hiding capacity while maintaining a desirable image quality around 40 dB. Furthermore, the security of our proposed scheme is verified by demonstrating its resistance to the pixel-value difference histogram (PDH) and regular/singular (RS) steganalysis.