The presently claimed invention adaptively selects a local de-interlacing method according to information from a compressed video bitstream. According to one embodiment, successive images from a video bitstream are first reconstructed. Syntax elements, selected from a macroblock type, a macroblock partition, a motion vector, a distance from a reference frame, the existence of non-zero transform coefficients and the distribution of transform coefficients, are then extracted from this bitstream. Based on the syntax elements, a de-interlacing algorithm is decided from an algorithm set for each image region in a video frame. Algorithms in the algorithm set include motion compensation, edge-based line averaging, and line averaging. Each image region is thereby interpolated using the de-interlacing algorithm and complementary motion compensation. The complementary motion compensation de-interlaces the image region using an inverse of motion vectors extracted from a bitstream clip representing neighboring frames.