An encoder (103) encodes image data using a first parameter Q1, and a re-encoder (107) re-encodes the encoded result of the encoder (103) using a second parameter Q2. When the encoded data size obtained by the encoder (103) exceeds a predetermined size, Q1 is replaced by Q2, and encoded data streams previously encoded by the re-encoder (107) are saved in a buffer (108) as those encoded by the encoder (103) after the parameter is changed. Upon executing a re-encoding process, the re-encoder (107) re-encodes encoded data streams previously encoded by the re-encoder (107) using a parameter that can assure a higher compression ratio than Q2.