For each block to be encoded, an image encoding device treats a region having similar image signals in the block as a subject, and sets a single pixel value representing each subject as a subject pixel value so as to be associated with a subject identifier. A subject map generation unit generates a subject map which expresses, with subject identifiers, which subject each pixel in the block belongs to. Using this map, a predicted image generation unit generates a predicted image to be used in prediction of the block to be encoded. A subject map encoding unit encodes the subject map by referring to the subject map used when encoding a reference region that has been encoded.