This paper presents a novel data hiding scheme for VQ compression images. This scheme first uses SMVQ prediction to classify encoding blocks into different types, then uses different codebooks and encoding strategies to perform encoding and data hiding simultaneously. In using SMVQ prediction, no extra data is required to identify the combination of encoding strategies and codebook, which helps improve compression performance. Furthermore, the proposed scheme adaptively combines VQ and SMVQ encoding characteristics to provide higher image quality of stego-images while size of the hidden payload remains the same. Experimental results show that the proposed scheme indeed outperforms other previously proposed schemes in image quality of the stego-images and compression performance.