The invention generates encoded data that properly conforms to pre-specified image quality and suppresses a large change in image quality. An encoding unit encodes pictures block by block according to a parameter. A distortion amount calculation unit calculates a picture distortion amount between a decoded picture and a picture before being encoded. A scene distortion amount calculation unit calculates a scene encoding distortion amount from the picture distortion amounts of a plurality of pictures having been encoded. A distortion bit rate conversion unit calculates a corrected bit rate by calculating a difference between a target distortion amount and the calculated scene encoding distortion amount, and multiplying the calculated difference by a coefficient. A target bit rate calculation unit calculates a bit rate for a picture subsequent to a picture of interest by adding a current target bit rate to the corrected bit rate, and sets it as the parameter.