Reversible watermarking has become a highly desirable subset of fragile watermarking for sensitive digital imagery in application domains such as military and medical because of the ability to embed data with zero loss of host information. This reversibility enables the recovery of the original host content upon verification of the authenticity of the received content. We propose a new reversible watermarking algorithm. The algorithm exploits the correlation inherent among the neighboring pixels in an image region using a predictor. The prediction-error at each location is calculated and, depending on the amount of information to be embedded, locations are selected for embedding. Data embedding is done by expanding the prediction-error values. A compressed location map of the embedded locations is also embedded along with the information bits. Our algorithm exploits the redundancy in the image to achieve very high data embedding rates while keeping the resulting distortion low.