An encoding apparatus for encoding progressive image data and interlace image data corresponding to this progressive image data, having a first encoding unit configured to encode picture data composing the interlace image data to generate first encoded data and decoding and recomposing the first encoded data to generate recomposed image data, an up sample processing unit configured to up sample the generated recomposed image data to generate image data having the same resolution as that of the progressive image data, and a second encoding unit configured to encode the picture data composing the progressive image data to generate second encoded data using the generated image data as predictive image data.