Abstract: In this study, a reversible data hiding for natural images are proposed. It exploits the technique of orthogonal prediction error modification and multilevel histogram shifting. The proposed orthogonal prediction error modification strategy uses the sets of basic pixels to predict the value of non-basic pixels. A histogram is constructed based on the sequences of prediction errors, and a multilevel histogram shifting mechanism is designed for embedding secret data. In decoder, the cover image pixels and secret data are perfectly recovered. The experimental results show the effectiveness of the proposed scheme. As more embedding levels are used in data hiding, the capacity can be enhanced to about 1.0 bit per pixel. Meanwhile, the visual quality can be achieved as larger than 30 dB.