According to one embodiment, a video encoding apparatus includes a motion vector calculation module, a motion boundary detection module, and a quantization parameter setting module. The motion vector calculation module calculates motion vectors for respective blocks in an input image. The motion boundary detection module detects a motion boundary between a motion region and a still region in the input image based on the motion vectors of the respective blocks. The quantization parameter setting module sets a value of a quantization parameter used to quantize a block that borders the detected motion boundary to a value smaller than a value which is set when the block does not border the motion boundary in accordance with a detection result of the motion boundary.