A video decoding device includes a demultiplexing unit which demultiplexes a video bitstream including video data of an encoded slice, Supplemental-Enhancement-Information having first information indicating a refresh group of segments in gradual refresh, and Supplemental-Enhancement-Information having second information indicating segments where a refresh has completed in a current picture, an extracting unit which extracts the second information from a message which is part of the demultiplexed Supplemental-Enhancement-Information, and a video decoding unit which decodes image data from the demultiplexed video bitstream by using at least inter picture prediction.