The proposed watermark embedding algorithm uses histogram of difference image between a modified original image and predicted image. To increase the prediction performance of the predicted image, the reference pixels for prediction are adaptively selected and the other pixels are directionally interpolated with the reference pixels. The simulation result shows that the proposed algorithm gives good performances in the embedding capacity and the PSNR values.