A moving image encoding apparatus for dividing a moving image into a plurality of rectangular regions and encoding the moving image in a unit of the rectangular region. There is a rectangular region size determiner which determines a variable size of the rectangular region, a rectangular region divider which divides an inputted image into the rectangular region, and a rectangular region encoder which determines a coding mode for the rectangular region, and encodes pixel values in the rectangular region.