A video encoding device including a region division section for dividing a frame image constituting video data into a plurality of regions as encoding target regions, an encoding section for encoding an image of each region, an inverse transformation section and an addition section for generating reproduced image of the encoded image, a storage section for storing reproduced images, a prediction generation section for searching a region which is highly correlated to a reproduced image of a template region, which is adjacent to the region of the encoding target image in a predetermined positional relationship and is a part of the reproduced image, from the reproduced image, and determining a prediction signal based on the searched region and the above-mentioned positional relationship, and a subtraction section for generating a difference signal between the prediction signal and the encoding target image as a signal for encoding.