A provisional region dividing unit 101 divides a block to be encoded into a plurality of provisional regions on a predetermined provisional boundary. A motion vector detecting unit 102 detects a motion vector with respect to each provisional region. An actual region dividing·motion compensating unit 103 generates a synthesized prediction block by generating a plurality of prediction blocks corresponding to the block to be encoded from a reference image by using the motion vector of each provisional region, deciding an actual boundary based on activities of the plurality of prediction blocks, and joining regions acquired by dividing the each prediction block on the actual boundary among the respective prediction blocks. A variable length encoding unit 105 encodes a prediction difference block acquired by subtracting a synthesized prediction block from the block to be encoded, and the motion vector of each provisional region.