1. A moving image encoding apparatus for dividing an image into a plurality of image blocks and performing intra-prediction encoding of an encoding target image block using pixel values of an image block adjacent to the encoding target image block, comprising: a prediction unit configured to perform intra-prediction in accordance with one of a plurality of intra-prediction modes corresponding to a plurality of divided block sizes and outputting intra-predicted image data for the encoding target image block; a determination unit configured to, when the encoding target image block is a low frequency band image, determine by detecting a change in the pixel value in the image block whether the encoding target image block includes a gradation image; and a block size decision unit configured to, when said determination unit determines that the encoding target image block includes the gradation image, decide a block size of the intra-prediction so as to cause said prediction unit to preferentially select a minimum block size of the plurality of divided block sizes.