A video encoding device includes: a quantization step size encoding unit 11 for encoding a quantization step size for controlling quantization granularity; and a quantization step size downsampling unit 12 for downsampling one or more encoded quantization step sizes to generate a quantization step size representative value. The quantization step size encoding unit 11 predicts the quantization step size using the quantization step size representative value.