A highly adaptive de-blocking algorithm is proposed for MPEG video, which is improved in three ways compared to previous algorithms. First of all, the proposed algorithm is adaptive to quantization parameter (QP) change. Since blocking artifacts between two blocks encoded with different QPs tend to be more visible due to quality difference, filters should be able to dynamically adapt to QP change between blocks. Secondly, the proposed algorithm classifies block boundary into three different region modes based on local region characteristics. The three region modes include active, smooth and dormant region. By applying different filters of different smoothing strengths to each region mode, the proposed algorithm can minimize undesirable blur so that both subjective and objective qualities improve for various type of sequences at a wide range of bitrates. Finally, the proposed algorithm also provides threshold determination methods. Adaptive de-blocking algorithms require several thresholds for mode decision as well as filtering decision. Since quality of video sequences after filtering depends largely on them, each threshold should be determined carefully. In the proposed algorithm, thresholds are determined adaptively to strength of blocking artifact, therefore adaptively to various encoding parameters such as QP, absolute difference between QPs, and block coding type, which are closely related to strength of blocking artifact. The experimental results show the proposed algorithm can achieve 0.2-0.4 dB gain for I- and P-frames, and 0.1-0.3 dB gain for the B-frames when bitstreams are encoded by using the TM5 rate control algorithm.