This paper proposes a reversible data embedding scheme based on a VQ image compression technique which emphasizes that the original VQ compressed codes can be recovered after data extraction. In this proposed scheme, a VQ codebook, which had already been clustered into three groups, was adopted to achieve secret concealment and data recovery. In order to embed more secret data, the concepts of frequency clustering and trio extension were also introduced. Experimental results showed that the proposed scheme with the lossless recovery facility could work well.