The depth of exploitation of electromagnetic spectrum for connecting people has reached a new pinnacle with the name internet which has equally increased the spectrum of demand for secrecy. In this context, steganography plays a key role in secret communication to hide not just information, but the communication itself. Among several embedding approaches in digital images, least significant bit technique has been widely used to embed huge secret data. But maintaining the imperceptibility of the stego image is a serious concern. In this paper, an adaptive random (AR) k-bit embedding approach has been proposed to enhance the quality of stego image. The original cover is divided into non-overlapping blocks of equal size and encrypted secret data has been embedded in each block to cover the entire image by adapting four different random walks. During this process, the proposed method identifies the best random walk among the four for a particular block, which provides minimum degradation and fix the same walk for that block. The decision on the fixed random walk for each block is recorded and the same can be kept as secret key. The proposed AR method has also been combined with the Inverted Pattern approach to be called as Adaptive Random Inverted Pattern (ARIP) approach to further enhance the quality of stego-image. The estimated PSNR value for ARIP method proves 1dB enhancement than the existing results.
Key Words: LSB embedding, IP LSB, Space Filling Curves SFC, Information Hiding, Image Steganography
Military secrets revealed have led to wars being fought and battles being lost. Diplomatic secrets if revealed can lead to disastrous confusion in the world. For a long time now, keeping secrets has been a major concern of human kind and this scenario has still been worsened by the latest developments in the field of digital communication. Internet makes communication easy and fast but at the same time anyone at any time can sneak into the privacy of the participants. In order to fight against this insecurity, steganography has emerged as a modern savior which puts the secret data out of sight in the open book of internet. Steganography plays a smart role in sharing secret data by hiding the encrypted form of the same into images, audio files or even videos in such a way that eavesdroppers cannot even suspect the very existence of the concealed messages [1-5].
In the recent past, many steganography methods have been proposed and they are classified into two major types based on the cover image domains; namely spatial [5-7] and frequency [8,9]. In the spatial domain the encrypted secret data is hidden in the pixels of cover image by employing Least Significant Bit (LSB) , pixel value differencing [10, 11], mod [11- 12] and lossless data hiding [6, 13] based schemes. These schemes have been adapted by many authors to achieve good imperceptibility with higher pay load . In the frequency domain methods, the secret data is hidden in the transformed coefficients of the cover image where Discrete Cosine Transform (DCT)  and Discrete Wavelet Transform (DWT)  act as domain converters.
In spatial domain stego methods, LSB embedding scheme has been widely used to hide secret data because of its simplicity and speed of implementation. In addition this technique offers higher hiding capacity  and at the same time quality of the stego image can be well-controlled [5, 17, 18]. In LSB embedding process, authors have adapted raster scan [5, 10-14] as well as random scan [19, 20] to hide the secret data in each pixel. Between these two scans, random is preferred over raster to increase the level of complexity against the eavesdroppers. But the real challenge is on maintaining good imperceptibility of the stego image and sharing the secret key for retrieving the original message.
Chi-Kwong Chan et.al. have proposed an optimal pixel adjustment process (OPAP) to enhance the quality of the stego-image by the simple LSB substitution method through raster scan. In this method, the OPAP tries to vary the value of Most Significant Bit (MSBi) next to kth bit up to which the secret data is embedded. C. H. Yang  has proposed an LSB substitution method using raster scan to improve the stego image quality by adapting an inverted pattern (IP) approach. In this technique, secret message has been processed prior to embedding i.e., some secret data are inverted and some are kept as such. The author has claimed that IP approach has better image quality than that of OPAP. Even though OPAP and IP approaches have claimed higher image quality and payload, the complexity against hackers is still under serious concern because they have adapted simple raster scan.
Provos et.al  has proposed a hide and seek software not technique for random selection of pixels for embedding secret data and hence generating stego image. In these random approaches all the pixels of the cover image have not been used for hiding secret data which in turn affect the payload besides good imperceptibility. Tuomas Aura  has proposed a stego method by adapting random embedding procedure in which stego key and a secure hash function are used to generate a sequence of unique pixel addresses for embedding.
From the literature it is obvious that obtaining maximum stego-image quality as well as payload, minimum key length with more complexity against hackers through either random or raster scan based stego technique is found to be seldom considered. It is also observed that many proposed stego methods have computed stego-image quality by considering a particular type of secret data. The secret data may be complete text or full of numbers or even mixed but the available stego methods have not considered the nature of the secret data for enhancing the quality of stego-image. Hence in this paper, the authors have proposed and implemented an adaptive random k-bit embedding stego method with an aim of achieving higher imperceptibility, payload, optimized key length and mammoth complexity against hackers by significantly considering the nature of the secret text.
In the proposed method, four different random walks namely Z scan SFC, Hilbert SFC, Zigzag SFC and Moore SFC based on Space Filling Curves [21, 22] have been considered for k-bit LSB embedding. Before embedding the secret data, the cover image considered has been divided into an equal number of repeated smaller blocks. During the embedding procedure, all the four random scan have been tried for k-it embedding in each smaller block and the scan which results in minimum mean square error and maximum peak signal to noise ratio (PSNR) for that particular block has been finally adapted for embedding. In the same way optimum random walk for each block of the entire image is identified and fixed. Consequently the pattern of each fixed random walk has been recorded and kept as secret key. In this way, the nature of the text and its matching with each block for minimum error and maximum PSNR has been taken care of.
For implementing the adaptive random k-bit embedding, four different cover images of 256 x 256 pixels of gray level have been selected and are shown in Figures 1a, 1b, 1c and 1d. Before considering the entire cover image for secret bit embedding, each cover image has been divided into multiple blocks of 8 x 8 pixels to cover up the entire 28X28 pixels.
Initially the encrypted secret message has been embedded by adapting all the four random traversing paths namely Z scan SFC, Hilbert SFC and, Zigzag SFC and Moore SFC in the first 8x8 block. After performing this process for a single 8 x 8 block for each traversing path, the path which provides minimum error and maximum PSNR has been identified and the same random path has been fixed for final embedding for that particular block.
Since the four random walks Z scan SFC, Hilbert SFC, Zigzag SFC and Moore SFC are allotted the pattern key 00,01,10,11 respectively, a particular pattern key will be fixed for each block based on the best walk for that particular block. In this way all the 28x28 pixels of the entire cover have been considered for full embedding capacity. In case of full embedding capacity the total key size has been estimated to be 2048. The same procedure has been performed by considering the fundamental block size as 4 x 4 pixels also.
The four random walks adapted to embed the encrypted secret data for 8x8 pixels are shown in Figs. 2a, 2b, 2c and 2d.
SFC [21, 22] is a one dimensional curve which traverses through each and every point within a two dimensional space or image. SFC scans a pixel array which has a size of M x N pixels and while scanning, it will not retain the same direction but will turn around to embrace all the pixels at least and at most once. Hence the unpredictable traversing path of SFC through the image has been chosen to hide the secret message in the cover. In general, random embedding scheme requires a specific key with variable size to retrieve the embedded secret data at the receiving end. In order to overcome this drawback, the concept of space filling curve (SFC) has been adapted for embedding the secret data in the image where Z scan SFC, Hilbert SFC, Zigzag SFC and Moore SFC methods can been used. Since the proposed stego method adapts all the four SFCs in the cover image, two bit pattern is required as key.
Results and Discussion
The proposed AR k-bit embedding approach-based stego process has been implemented in four different cover images and the quality of the stego-images have been evaluated and the results are given in Table 1. Initially the stego image quality has been estimated by adapting the Z scan SFC, Hilbert SFC, Zigzag SFC and Moore SFC scan individually for k bit embedding by considering all the 8x8 blocks of a cover image. In order to prove the enhanced quality of the stego image by AR approach, the estimated MSE and PSNR values of the same are compared with the results of individual random traversing path approaches.
From Table-1 it is observed that, the MSE and PSNR values of AR approach for all the four cover images are found to be better than the values of individual random traversing path approaches. This significant enhancement is due to the adaptive selection of a particular random traversing path for a particular block which is in turn fixed based on the nature of the secret message. Since the cover image has totally 1024 blocks of 8x8 pixels, the required key size would be 2048 bits. A similar procedure has been adapted by considering the fundamental block size as 4x4 pixels. From the estimated results, it is obvious that the quality of stego cover is still improved with one limitation on key size which is 8192 bits. Even though the key size is increased considerably, this AR approach offers a rock solid security along with enhanced imperceptibility.
In addition to AR method, ARIP method has also been implemented in all the cover images and the estimated evaluation parameters are given in Table 2. In order to show the enhanced quality of stego-image through ARIP method, its results are compared with the estimated results of OPAP  and IP approach  as given in Table 2. To have a common platform for fair comparison, the IP scheme of 1024 key size and the 8x8 block based ARIP method have been considered. Similarly 4096 key size of IP approach is compared with 4x4 block based ARIP method. The stego-images for the ARIP case with k=4 bit full embedding capacity are shown in Figures 3a, 3b, 3c and 3d.
Even though the security level is increased manifold in the AR approach because of multi type random traversing paths, the estimated PSNR value is found to be lesser than IP approach. Hence the IP and AR are combined to form ARIP method. From Table 2, it is observed that the estimated MSE and PSNR values of ARIP approach for all the four cover images are found to be better than the values of simple IP and OPAP approaches. This performance is still bettered in the case of 4x4 block pixels besides the larger key size. For ARIP approach the required key size is 3 bits per one 8x8 block i.e. two bits for the selected random traversing path and one bit for IP approach and hence the total key size is 3072 bits. Except this bottleneck, ARIP method has shown dominant over the existing random approaches in enhancing the stego image quality and complexity against the hackers.
In this overall adaptive stego process, the secret message is first of all encrypted using data encryption standard and secondly, intelligent chaotic walk has been employed for embedding the encrypted secret data and as a third step, inverted pattern approach has been super-positioned for additional crypto effect. From the computed results of MSE and PSNR values of the stego-image generated by ARIP method, it is obvious that the proposed adaptive stego technique supersedes the IP LSB and OPAP stego techniques in enhancing quality of the stego-image. Moreover the ARIP approach offers significantly improved security without compromising the pay load. Besides all these merits, ARIP approach significantly considers the nature of the text while embedding the data which emphasizes the quality enhancement.
- S. Katzenbeisser, F.A.P. Petitcolas, Information Hiding Techniques for Steganography and Digital Watermarking, Artech House, Norwood, MA, 2000.
- F.A.P. Petitcolas, R.J. Anderson, M.G. Kuhn, Information hiding a survey, Proc. IEEE 87 (7) (1999) 1062-1078.
- W. Bender, D. Gruhl, N. Morimoto, A. Lu, Techniques for data hiding, IBM Syst. J. 35 (3&4) (1996) 313-336.
- W. Bender, W. Butera, D. Gruhl, R. Hwang, F. J. Paiz, S. Pogreb, Applications for data hiding IBM Syst. J. 39 (3&4) (2000) 547-568.
- C.K.Chan, L.M. Chen, Hiding data in images by simple LSB substitution, Pattern Recognition 37 (3) (2004) 469-474.
- Chin-Chen Chang, Chih-Yang Lin, Yi-Hsuan Fan, Lossless data hiding for color images based on block truncation coding , Pattern Recognition 41 (7) 2008 2347-2357
- A. Ker, Improved detection of LSB steganography in grayscale images, in: Proceedings of the Information Hiding Workshop, in: LNCS 3200 (2004) 97-11.
- Santi P. Maity, Malay K. Kundu, Tirtha S. Das, Robust SS watermarking with improved capacity, Pattern Recognition Letters 28 (3) 2007 350-356
- Chin-Shiuh Shieh, Hsiang-Cheh Huang, Feng-Hsing Wang, Jeng-Shyang Pan, Genetic watermarking based on transform-domain techniques, Pattern Recognition Letters 37 (3) 2004 555-565
- Young-Ran Park, Hyun-Ho Kang, Sang-Uk Shin, and Ki-Ryong Kwon, An Image Steganography Using Pixel Characteristics Y. Hao et al. (Eds.): CIS 2005, Part II, Springer-Verlag Berlin Heidelberg LNAI 3802, (2005) 581- 588.
- C.M. Wang, N.I. Wu, C.S. Tsai, M.S. Hwang, A high quality steganography method with pixel-value differencing and modulus function, J. Syst. Software 81 (1) (2008) 150-158.
- C.C. Thien, J.C. Lin, A simple and high-hiding capacity method for hiding digit-by-digit data in images based on modulus function, Pattern Recognition 36 (11) (2003) 2875-2881.
- Chih-Chiang Lee, Hsien-Chu Wu, Chwei-Shyong Tsai, Yen-Ping Chu Adaptive lossless steganographic scheme with centralized difference expansion, Pattern Recognition 41 (6) (2008) 2097-2106
- Yu-Chen Hu, High-capacity image hiding scheme based on vector quantization, Pattern Recognition 39 (9) (2006) 1715-1724
- Chiang-Lung Liu, Shiang-Rong Liao, High-performance JPEGsteganographyusing complementary embedding strategy, Pattern Recognition 41 (9) (2008) 2945-2955
- Po-Yueh Chen, Hung-Ju Lin, A DWT Based Approach for Image Steganography, International Journal of Applied Science and Engineering 4(3) (2006) 275-290
- R.Z. Wang, C.F. Lin, J.C. Lin, Image hiding by optimal LSB substitution and genetic algorithm, Pattern Recognition 34 (3) (2000) 671-683.
- C.H. Yang, Inverted pattern approach to improve image quality of information hiding by LSB substitution Pattern Recognition 41 (2008) 2674-2683.
- Provos, N., Honeyman, P, Hide and seek: An introduction to steganography, IEEE Security & Privacy Magazine 1 (2003) 32-44
- Tuomas Aura, Practical invisibility in digital communication, in proceedings of the Workshop on Information Hiding, LNCS 1174 (1996) 265-278
- Hans Sagan, Space-Filling Curves, Springer-Verlag, New York, (1994). ISBN: 0-387-94265-3.
- A. Westfeld Space filling curves in steganalysis in E.J Delp III & P.W. Wong(Eds), Security, steganography and watermarking of multimedia contents VII SPIE 5681, (2005) 28-37