A video decoding device includes a demultiplexer which demultiplexes a video bitstream including video data of an encoded slice, Supplemental-Enhancement-Information having first information indicating a leading picture in gradual refresh, and Supplemental-Enhancement-Information having second information indicating segments where a refresh has completed in a current picture; an extractor which extracts the second information from a message which is part of the demultiplexed Supplemental-Enhancement-Information; and a video decoder which decodes image data from the demultiplexed video bitstream by using at least inter prediction, wherein the video decoder starts decoding based on the leading picture in gradual refresh.