An encoding device to encode an object image to be encoded includes a reference information generating unit that generates reference information with respect to a key image different from the object image, and a code generating unit that generates code data of the reference information generated by the reference information generating unit as code data of at least a portion of the object image.