A temporary prediction mode determining unit temporarily determines a prediction mode used to code a coding target pixel, based on a relation between the decoded value of a locally decoded pixel neighboring at least one line above the coding target pixel and the decoded values of locally decoded pixels surrounding the neighboring pixel, and then sets a temporary prediction mode index. A final prediction mode determining unit finally determines a prediction mode used to code the coding target pixel, based on the temporary prediction mode index of the coding target pixel and the relation between the decoded value of a locally decoded pixel located at least to the left of the coding target pixel and the decoded values of locally decoded pixels surrounding the pixel located to the left.