Due to the instability of and possible attacks on the networks, image files transmitted through the networks may encounter losses of data. Such losses may be recovered by retransmitting or by using image processing techniques. The latter has an obvious advantage that the network traffic could be reduced. In this paper, a self-embedding image recovery algorithm based on adaptively rearranged codebooks is proposed. The original image is characterized by a codebook based on vector quantization and each codeword in the codebook is considered as the feature data of a block in the image. The feature data of a block is embedded in another block, and if the block is damaged, the embedded feature data are extracted and used for recovery. The proposed method has two advantages: First, the codebook is adaptively rearranged so that the time searching for an appropriate codeword is reduced considerably. Second, only the type of an image block needs to be maintained; therefore the information necessary for embedding is reduced and the visual quality of the embedded image would be better. The experimental results show that our method has better performance both on computational efficiency and the visual quality of the embedded images.