Reversible steganography allows an original image that has gone through the embedding process to be completely restored after the extraction of the embedded data. In this paper, we propose a reversible scheme with a high embedding capacity for VQ compressed images. Our reversible method is based on a prediction strategy and takes advantage of the local characteristics of the image. Since the location map is usually a necessary part of a reversible scheme, two methods, shifting and relocating, are also proposed to reduce the size of the location map. As the experimental results show later, our method outperforms previous schemes in terms of embedding capacity and image quality. To be more specific, with low distortion, the embedding capacity of the proposed methods can be higher than one bit per index value.
