Image coding having high coding efficiency is provided with a small computational complexity by properly determining a prediction mode and a quantization parameter. When an image is coded by a prediction mode selected from plural prediction modes every any coding unit, an undetermined multiplier λ is first calculated from a quantization parameter (function S301). Subsequently, the cost of each of R-D points (pairs of number of coded bits and coding distortion that correspond to plural combinations of prediction modes and quantization parameters) is calculated (function S305) on the basis of the undetermined multiplier λ while generation and estimation of the R-D points and deletion of the points (functions S302-S304) are repeated every coding unit, for example, every macroblock, and the optimal combination of the prediction mode and the quantization parameter is determined on the basis of the R-D point providing the minimum cost.