1. A video encoding apparatus comprising motion compensation prediction means for generating a predicted image of a coding target frame by dividing the coding target frame into a plurality of blocks, generating a prediction reference image that are formed by providing interpolated pixels which are produced by interpolation between integer pixels from integer neighborhood pixels in a predetermined region of a reference frame, and determining a motion vector for the prediction reference images for each of the plurality of blocks, the motion compensation prediction means having: complexity extraction means for extracting complexity information which indicates a degree of complexity of movement from the reference frame for each of the plurality of blocks; and predicted image generating means for generating the predicted image by using the prediction reference image to which filtering pixels are provided in accordance with the complexity information on the basis of a predetermined rule which increases the number of the filtering pixels which have pixel values produced by applying a low-pass filter of which spectral band-pass in low frequency band is narrow among a plurality of low-pass filters with different high-frequency cutoff characteristics to neighborhood integer pixels.