A video encoding device includes a planar prediction unit using planar prediction, and a noise injecting unit for injecting pseudo-random noise into a prediction image of a planar prediction block when a reconstructed prediction error value for planar prediction is less than a threshold determined by the size of the planar prediction block. The video encoding device then uses the pseudo-random noise in linear interpolation for calculating the prediction image, based on the conditions under which a gradient distortion occurs, to suppress the gradient distortion.