In scalable video encoding, incidence rates of combinations of optimum prediction modes to be selected for spatially corresponding blocks of an upper layer and a lower layer are determined based on an optimum prediction mode that was selected in a conventional encoding, and then a correspondence table that describes relationships therebetween is created. Subsequently, the combinations of the selected optimum prediction modes described in the correspondence table are narrowed down based on the value of the incidence rate so as to create prediction mode correspondence information that describes the combinations of the optimum prediction mode narrowed down. When encoding the upper layer block, the prediction mode search candidate that is to be searched in the encoding is decided by referring to the prediction mode correspondence information using as a key the optimum prediction mode selected in the encoding of the spatially corresponding lower layer block and thereby reducing the number of the prediction mode search candidates.