Data Hiding Method Based on Graph Coloring and Pixel Block‘s Correlation in Color Image

Document Type : Research Article


1 Dept. of Electrical Engineering, Emam Ali University, Tehran, Iran

2 Dept. of Electrical Engineering, Shahid Sattary Aeronautical University of Science and Technology, Tehran, Iran

3 Dept. of Electrical Engineering, Ahar University, Ahar, Iran

4 Department of Electrical and Electronic Engineering, Amirkabir University of Technology, Tehran, Iran


An optimized method for data hiding into a digital color image in spatial domain
is provided. The graph coloring theory with different color numbers is applied. To enhance the
security of this method, block correlations method in an image is used. Experimental results show
that with the same PSNR, the capacity is improved by %8, and also security has increased in the
method compared with other methods. In the correlation block-based image method, data hiding
capacity of the host image varies according to image type and defined threshold level. In the
proposed algorithm, during graph explanation, independent pixels placed side by side were colored.
Then, based on “pixel block correlation data hiding” process is done. This method grows the
security and capacity of hiding process. Besides, this increases the effects of image format and
correlation threshold on security and capacity.


[1] R.-Z. Wang, C.-F. Lin, J.-C. Lin, Image hiding by optimal LSB substitution and genetic algorithm, Pattern recognition, 34(3) (2001) 671-683.
[2] M.A. Abdel-Wahab, H. Selim, U. Sayed, A new method for digital image watermarking based on Vector Quantization (VQ).
[3] C.-C. Chang, W.-L. Tai, C.-C. Lin, A reversible data hiding scheme based on side match vector quantization, IEEE Transactions on Circuits and Systems for Video Technology, 16(10) (2006) 1301-1308.
[4 N.J. Hopper, Toward a theory of Steganography, CARNEGIE-MELLON UNIV PITTSBURGH PA SCHOOL OF COMPUTER SCIENCE, 2004.
[5] M.S. Shahreza, An improved method for steganography on mobile phone, WSEAS Transactions on Systems, 4(7) (2005) 955-957.
[6] J. Fridrich, P. Lisonek, Grid colorings in steganography, IEEE Transactions on Information Theory, 53(4) (2007) 1547-1549.
[7] W. Zhang, X. Zhang, S. Wang, Twice Gric Colorings in Steganography, in: Intelligent Information Hiding and Multimedia Signal Processing, 2008. IIHMSP’08 International Conference on, IEEE, 2008, pp. 1301-1304.
[8] S. Yue, Z.-H. Wang, C.-Y. Chang, C.-C. Chang, M.-C. Li, Image data hiding schemes based on graph coloring, Ubiquitous Intelligence and Computing, (2011) 476-489.
[9] M. Nafari, G.H. Sheisi, M.N. Jahromi, New data hiding method based on neighboring correlation of blocked image, in: International Conference on Digital Information and Communication Technology and Its Applications, Springer, 2011, pp. 787-801.
[10] S.M. Douiri, M.O. Medeni, S. Elbernoussi, New steganography scheme using graphs product, in: Interactive Collaborative Learning (ICL), 2014 International Conference on, IEEE, 2014, pp. 525-528.
[11] W. Astuti, U.N. Wisety, Data Hiding Scheme on Medical Image using Graph Coloring, in: Journal of Physics: Conference Series, IOP Publishing, 2015, pp. 012028.
[12] S.-H. Chiang, J.-H. Yan, On L (d, 1)-labeling of Cartesian product of a cycle and a path, Discrete Applied Mathematics, 156(15) (2008) 2867-2881.
[13] D.B. West, Introduction to graph theory, Prentice hall Upper Saddle River, 2001.