Among the various information hiding schemes,the reversible data hiding has achieved substantial attention in the recent years.In order to improve the performance o f embedding algorithm,this paper proposes a reversible data hiding scheme based on optimal p rediction of block.The premise of this algorithm is that a histogram is constructed from the optimal pr ediction of block. In accordance with the priority principle of embedding capacity,the optim al prediction is chosen for every block.In the data embedding process,a histogram shifting scheme is used to embed a secret message into pixels whose prediction error is located in embedding area within the histogram. Experimental results show that the proposed algorithm can achieve higher embeddi ng capacity and imperceptible distortion.Performance comparisons with other existing algori thms are also provided to demonstrate the feasibility of our proposed algorithm.