A novel data hiding scheme for color images using a BSP tree

In this paper, we propose a novel data hiding technique for color images using a BSP (Binary Space Partitioning) tree. First, we treat the RGB values at each pixel as a three-dimensional (3D) virtual point in the XYZ coordinates and a bounding volume is employed to enclose them. Using predefined termination criteria, we construct a BSP tree by recursively decomposing the bounding volume into voxels containing one or several 3D virtual points. The voxels are then further categorized into eight subspaces, each of which is numbered and represented as three-digit binary characters. In the embedding process, we first traverse the BSP tree, locating a leaf voxel; then we embed every three bits of the secret message into the points inside the leaf voxel. This is realized by translating a point's current position to the corresponding numbered subspace. Finally, we transform the data-embedded 3D points to the stego color image. Our technique is a blind extraction scheme, where embedded messages can be extracted without the aid of the original cover image. It achieves high data capacity, equivalent to at least three times the number of pixels in the cover image. The stego image causes insignificant visual distortion under this high data capacity embedding scheme. In addition, we can take advantage of the properties of tree data structure to improve the security of the embedding process, making it difficult to extract the secret message without the secret key provided. Finally, when we adaptively modify the thresholds used to construct the BSP tree, our technique can be robust against attacks including image cropping, pixel value perturbation, and pixel reordering. But, the scheme is not robust against image compression, blurring, scaling, sharpening, and rotation attacks. (C) 2006 Elsevier Inc. All rights reserved.