A reversible data hiding scheme means that the original images can be losslessly recovered from the result with secret bits embedded. In this paper, a reversible data hiding scheme based on a vector quantization (VQ) index table is proposed. This paper aims to minimize the size expansion of the embedded result. To achieve this goal, the index appearance frequency histogram was analyzed before the embedding process started. The experiment results showed that the performance of the scheme proposed in this paper outperforms that of in Chang et al.'s scheme proposed in 2009 not only in bit rate, but also in hiding capacity.