Based on the characteristics of difference histograms

we propose a reversible data hiding algorithm using difference expansion. In order to decrease the embedding distortion

we present three schemes

including interleavingly shifting the outer regions of the histogram

dividing the outer regions into segments by using zero points

and a payload-dependent overflow location map. This first scheme is used to control the number of selected differences; the second one is used to decrease the shifting distance of the region movement; the last one is used to generate a compact compressed overflow location map. The experimental results verify that

compared with other typical reversible algorithms in the literature (e.g.

Thodi et al′s and Tian′s algorithms)

the proposed algorithm has better overall performance. In particular

our algorithm has more advantages at low- and middle-embedding rates.