An image decoding apparatus (100; 10) which decodes a bit stream including coded image data, said apparatus (100; 10) comprising: an obtainment unit configured to obtain the bit stream; a stream segmentation unit (130; 12) configured to generate N segment streams by segmenting each of coded pictures included in the bit stream obtained by said obtainment unit into a plurality of structural units, and assigning, as a portion, each of the plurality of structural units to one of the N segment streams to be generated, N being an integer equal to or greater than 2; and N decoding units (120; 13) configured to decode, in parallel, the respective N segment streams generated by said stream segmentation unit (130; 12), wherein each structural unit includes one slice portion of at least one slice of the coded picture and wherein, when said stream segmentation unit (130; 12) segments the coded pictures into structural units and assigns the structural units to the N segment streams in generating the N segment streams and when the stream segmentation unit (130; 12) assigns to at least one segment stream a plurality of structural units including slice portions of the same slice, the slice portions of the same slice forming a slice portion group, said stream segmentation unit (130; 12) (i) determines, for each of the N segment streams, whether or not a beginning of a slice portion group to be assigned to the respective one of the N segment streams corresponds to a beginning of a slice in the coded picture, said slice portion group including the slice portions of the same slice to be assigned to the respective one of the N segment streams, and (ii) in the case of determining that the beginning of the slice portion group does not correspond to the beginning of the slice, inserts, only at the beginning of the slice portion group, supplemental information including an address of a starting macroblock in the slice portion group. an obtainment unit configured to obtain the bit stream; a stream segmentation unit (130; 12) configured to generate N segment streams by segmenting each of coded pictures included in the bit stream obtained by said obtainment unit into a plurality of structural units, and assigning, as a portion, each of the plurality of structural units to one of the N segment streams to be generated, N being an integer equal to or greater than 2; and N decoding units (120; 13) configured to decode, in parallel, the respective N segment streams generated by said stream segmentation unit (130; 12), wherein each structural unit includes one slice portion of at least one slice of the coded picture and wherein, when said stream segmentation unit (130; 12) segments the coded pictures into structural units and assigns the structural units to the N segment streams in generating the N segment streams and when the stream segmentation unit (130; 12) assigns to at least one segment stream a plurality of structural units including slice portions of the same slice, the slice portions of the same slice forming a slice portion group, said stream segmentation unit (130; 12) (i) determines, for each of the N segment streams, whether or not a beginning of a slice portion group to be assigned to the respective one of the N segment streams corresponds to a beginning of a slice in the coded picture, said slice portion group including the slice portions of the same slice to be assigned to the respective one of the N segment streams, and (ii) in the case of determining that the beginning of the slice portion group does not correspond to the beginning of the slice, inserts, only at the beginning of the slice portion group, supplemental information including an address of a starting macroblock in the slice portion group. (i) determines, for each of the N segment streams, whether or not a beginning of a slice portion group to be assigned to the respective one of the N segment streams corresponds to a beginning of a slice in the coded picture, said slice portion group including the slice portions of the same slice to be assigned to the respective one of the N segment streams, and (ii) in the case of determining that the beginning of the slice portion group does not correspond to the beginning of the slice, inserts, only at the beginning of the slice portion group, supplemental information including an address of a starting macroblock in the slice portion group.