Searching an optimal quantization step size at high speed when controlling the coding rate of an image sequence. A skip binary search section determines quantization step size Δskip by binary search, using a frame out of every m [0] frames of an image sequence. A quantization step size correcting section determines quantization step size Δa that can achieve the target bit rate R by linear approximation from Δskip, generated bit rate at that time, quantization step size Δlast of the immediately preceding loop and the generated bit rate at that time. A first coding section encodes the every m [1]-th frame of the image sequence with quantization step size Δa and a quantization step size forecasting section determines quantization step size Δe that can achieve the target bit rate R by linear approximation. A second coding section encodes all the frames with the quantization step size Δe.