The H.264/AVC standard achieves significantly high coding efficiency if multiple block size Motion Estimation is adopted. However, the complexity of Motion Estimation and DCT is dramatically increased as a result. In previous work we propose an early mode decision algorithm to control the complexity, based on all-zero-blocks detection in 16×16 size. In this paper, we improve the algorithm. Firstly, we propose to detect all-zero blocks in 16×16, 8×8 and 4×4 sizes to simplify the course of mode decision. Secondly, we define the thresholds which are used to terminate motion estimation and mode decision in advance for these sizes. Last, we present the whole proposed algorithm. Experiments show that about 77% encoding time and 85% motion estimation time can be saved on average, which is better than state-of-the-art approaches.