Question

The key to the high performance of video compression lies in an efficient reduction of the temporal redundancy. For this purpose, the block-based motion estimation (BBME) technique has been successfully applied in the video compression standards from H.261 to H.264 [1]. The Exhaustive Search (ES) algorithm is the most computationally expensive block matching algorithm of all. It is also known as the Full Search Algorithm (FSA). This algorithm calculates the cost function at each possible location in the search window. Consequently, many fast motion estimation algorithms with a reduced number of search locations have been proposed. In this project, you are required to make a summary within 200 words to explain one (1) fast motion estimation algorithm of your choice.

Answer 1

Block motion estimation is broadly adopted in many video compression standards from H.261 to H.264 to remove the temporal redundancy within the successive frames. In ME process, firstly, a frame is partitioned into many nonoverlapping blocks with different block sizes according to the motion contents, secondly, the target block in the current frame is compared with the candidate blocks in the reference frame; under the constraint of criterion function such as the Sum of Absolute Difference(SAD), we can obtain the bestmatched block by minimizing the criterion function, and finally, the motion vector(MV), which represents the displacement between the current block and the bestmatched block, together with the residual signal, which is the pixel difference between the current block and the bestmatched block, are transported to the next process to be coded.

The newest video compression standard H.2641 A VC is developed by the Joint Video Team (JVT). Similar to the previous standards, H.2641 A VC is also based on the framework which is composed by the block-based ME and discrete cosine transform (OCT). In order to archive higher coding efficiency, H.264 adopts variable block size motion estimation (VBSME). As specified in [1, 2], a macro-block (MB) can be divided into seven partitions with different block sizes for inter-frame prediction according to motion complexity in the MB. Moreover, H.264 supports multiple reference frames. All the block sizes are investigated throughout all the reference frames based on the matching criterion and the one with minimum error is selected as the optimum. Furthermore, H.264 supports the quarter-pixel motion estimation to archive the MV with more accuracy.

The most straightforward searching strategy is exhaustive search i.e. FS. The FS searches every candidate point within the search window. It can archive the MV with the highest accuracy and the residua with the lowest energy. But the computational complexity is extremely high. Its huge computational requirements have ignited many research activities. The FS is used as an important assessment to evaluate the proposed fast algorithms on three aspects separately, namely, l.computional complexity, 2.compression efficiency, 3.compression quality.