1. A method of decoding video bitstream, comprising: reconstructing successive images from a video bitstream; extracting a plurality of syntax elements from said video bitstream, wherein the syntax elements are selected from a macroblock type, a macroblock partition, a motion vector, a distance from a reference frame, existence of non-zero transform coefficients, or a distribution of transform coefficients; deciding a de-interlacing algorithm from an algorithm set for each image region in a video frame based on said plurality of syntax elements, the deciding of the de-interlacing algorithm comprising one of: adopting motion compensation as the de-interlacing algorithm for inter-coded macroblocks in neither direct mode nor skip mode, wherein the macroblock partition is larger than 8×8, and wherein the macroblocks are 8×8 transformed and prediction errors of content of the macroblocks are vertically smooth; adopting edge-based line averaging as the de-interlacing algorithm for inter-coded macroblocks in neither direct mode nor skip mode, wherein the macroblock partition is larger than 8×8, and wherein prediction errors of content of the macroblocks are neither 8×8 transformed nor vertically smooth; or adopting edge-based line averaging as the de-interlacing algorithm for inter-coded macroblocks in neither direct mode nor skip mode, wherein the macroblock partition is not larger than 8×8; and interpolating each said image region using said de-interlacing algorithm and complementary motion compensation; wherein said complementary motion compensation de-interlaces said image region using an inverse of motion vectors extracted from a bitstream clip representing neighboring frames.