1. An image encoding apparatus which encodes image data, comprising: region image cut-out unit which cuts out a plurality of region images from the image data, and outputs the plurality of cut-out region images and position information associated with the cut-out region images; rearrangement unit which rearranges the plurality of region images which are cut out by the region images cut-out unit; position information updating unit which updates the position information of the plurality of region images which are rearranged by the rearrangement unit; region image synthesis unit which generates synthesis image by synthesizing the plurality of region images which are rearranged by the rearrangement unit; and encode generating unit which encodes the synthesis image and the position information which is updated by the position information updating unit.