An video encoding apparatus includes a dividing unit 101 to divide an input image signal into to-be-encoded pixel blocks, a reblocking unit 102 to reblock each of the to-be-encoded pixel blocks to generate a first pixel block and a second pixel block, a first prediction unit 108A to perform prediction for the first pixel block using a first local decoded image corresponding to an encoded pixel to generate a first predicted image, a generation unit to generate a second local decoded image corresponding to the first pixel block using a first prediction error representing the difference between the first pixel block and the first predicted image, a second prediction unit 108B to perform prediction for the second pixel block using the first local decoded image and the second local decoded image to generate a second predicted image, an encoding unit 103-105 to transform and encode the first prediction error and a second prediction error representing the difference between the second pixel block and the second predicted image to generate first encoded data and second encoded data, and a multiplexing unit 111 to multiplex the first encoded data and the second encoded data to generate an encoded bitstream.