An encoding device comprises: a dividing unit configured to divide an encoding unit of an image into a plurality of regions; a header generation unit configured to generate, for each boundary that partitions each of the plurality of regions along a direction which crosses a line, a boundary header used to identify the boundary; a trajectory generation unit configured to generate a piece of trajectory information representing a displacement of the boundary associated with progress of a line; and an aligning unit configured to, when generating encoded data including generated boundary headers and generated pieces of trajectory information, change, in accordance with the number of boundaries, a manner in which the generated boundary headers and the generated pieces of trajectory information are aligned.