Steganographic methods usually produce distortions in cover images due to the process of embedding secret bits. These distortions are hard to remove, and thus the cover image cannot be recovered. Although the distortions are always small, they cannot be allowed for some sensitive applications. In this paper, we propose a reversible embedding scheme for VQ-compressed images, which allows the original cover image to be completely recovered after the extraction of the secret bits. The embedded payload in the proposed method comprises the secret bits plus the restoration information. In order to reduce the size of payload, we utilized the spatial correlations in the image as the restoration information and then compressed the correlations by a lossless compression method. In addition, an alternative pairing method for codewords was proposed to improve the stegoed image quality and control the embedding capacity. Experimental results showed that the proposed method has the benefit of high efficiency of the steganographic process, high image quality, and adaptive embedding capacity compared with other schemes.