To reduce the computation cost of rate/distortion optimization in image compression, the rate/distortion gradient of a frame of interest is classified to m categories. A category information creating unit acquires a threshold .lamda. for a preceding frame as a predictive value .lamda.' for the frame of interest that is to be coded, and further finely segments a category in which the predictive value .lamda.' is included. A code amount is then calculated for each of n categories that include the predictive value .lamda.'. A code sequence forming unit selects a category having a target rate, and searches for a threshold between an upper and a lower limit value of the category. A value (S) at the end of the processing is selected as the threshold .lamda., and a code sequence is formed by using the threshold .lamda..