A video encoding apparatus determines whether to encode a key frame of a group of pictures using a bi-directional prediction mode. In one example, a video encoding apparatus includes a mode select unit configured to generate a virtual key frame for a current group of pictures based on a previous key frame of a previous group of pictures and a next key frame of a next group of pictures, calculate an error value representing error between a current key frame of the current group of pictures and the virtual key frame, and determine whether the error value exceeds a threshold value, and a video encoder configured to encode the current key frame using a bi-directional prediction encoding mode when the error value does not exceed the threshold value. The video encoder may comprise the mode select unit, or a preprocessing unit of the apparatus may comprise the mode select unit.