1. An image encoding apparatus which calculates a prediction error in each predetermined pixel block of an input picture by referring to a pixel in the picture and supplies the prediction error to an encoding unit, thereby encoding the picture, comprising: a storage unit which stores image data of an encoding target picture; a determination unit which determines a size of an encoding target pixel block; a plurality of predicted value calculation units corresponding to all prediction modes of the predetermined pixel block; a first prediction error calculation unit which calculates, based on a predicted value from a predicted value calculation unit in a prediction mode using one reference pixel value as a predicted value, a prediction error of a predetermined pixel in the pixel block size determined by said determination unit; a second prediction error calculation unit which calculates, based on a predicted value from a predicted value calculation unit in a prediction mode for calculating a predicted value based on a plurality of reference pixel values, a prediction error of each pixel in the pixel block size determined by said determination unit; an output unit which determines, based on a sum of the prediction errors calculated by said first prediction error calculation unit and said second prediction error calculation unit, a prediction mode which minimizes the sum of the prediction errors, and outputs, to the encoding unit, a prediction error obtained by a prediction error calculation unit corresponding to the determined prediction mode; and a control unit which controls to cause said second prediction error calculation unit to calculate the prediction error from one reference pixel value based on the block size determined by said determination unit.