A macroblock level adaptive search range algorithm for variable block size motion estimation in H.264/AVC

Compared with previous video standards, the computational complexity of H.264/AVC is extraordinarily high due to newly adopted tools such as variable block size motion estimation (VBSME). In VBSME, to each macroblock (MB) there are at all 41 blocks corresponded. These 41 blocks are sized from 4x4 through 16x16. As each block of these 41 blocks accounts for one independent search window (SW), thus to each MB there exist 41 SWs corresponded. In the other hand, adaptive search range (ASR) algorithms are defined as algorithms which adaptively adjust the search ranges (SRs) and hence result in dynamically reduced SWs. While considering whether 41 SWs got changed in the same way or not, "macroblock level ASR (MB-ASR) algorithms" are defined as algorithms which adaptively change the search range all- in-once and hence result in the 41 SWs got changed in the same way. "41 blocks level ASR (block-ASR) algorithms" are defined as algorithms that the changing ways of the SRs are specific to each block of the 41 blocks. Since in MB-ASR algorithms for each MB the SR is changed in same way, it is reasonable to consider that the control overhead of MB-ASR is less than that of block-ASR. In this paper, a MB-ASR algorithm is proposed and assessed from being compared with a previously proposed block-ASR algorithm. According to experimental results, it is proved the proposed algorithm provides almost the same encoding quality and even a little better SW reducing efficiency (SW-RE). Meanwhile, as a MB-ASR one, the proposed algorithm is considered having less control overhead than block-ASR one.