Reversible data hiding embeds information in a host media in a visually plausible way such that both the embedded message and the original host media can be exactly recovered. In this paper we present a new reversible data hiding framework based on prediction error histogram modification. This framework is general and flexible that includes some of the state-of-the-art methods as special cases. In addition, we propose a new adaptive prediction method using the autoregression model. In this method, a threshold is adjusted for each image to divide all pixels into two regions: the smooth region and the texture region. Then the proposed method optimally estimates the coefficients of the autoregression model for pixel value prediction through least-squares minimization. Experimental results show that the proposed reversible data hiding framework and the adaptive prediction algorithm offer valuable advantages over state-of-the-art methods in general.