In this paper, we present a novel, reversible steganographic method, which can reconstruct an original image effectively after extracting the embedded secret data. The proposed reversible hiding method aims at BTC (block truncation coding)-compressed color images. Conventionally, each block of a color image compressed by BTC requires three bitmaps and three pairs of quantization levels for reconstruction. In order to improve the compression rate, a genetic algorithm (GA) is applied to find an approximate optimal common bitmap to replace the original three. The secret data then are embedded in the common bitmap and the quantization levels of each block use the properties of side matching and the order of these quantization levels to achieve reversibility. The experimental results demonstrate that the proposed method is practical for BTC-compressed color images and can embed more than three bits in each BTC-encoded block on average.