A multiple hexagon search algorithm for motion and disparity estimation in multiview video coding

In single viewpoint video coding, there are many fast block matching motion estimation algorithms proposed, such as three-step search, four-step search, diamond search as well as hexagon-based search and so on. However, experimental analysis show that these algorithms are not suitable for using directly in Multiview View Coding (MVC). Since the increased search range, the larger format of multiview video as well as the correlations between inter-view frames are not considered by these algorithms, they may easy led the block matching search into local minimum, the Rate-Distortion (R-D) performance will degrade dramatically. In this paper, we propose a novel multiple hexagon search algorithm to address this problem. Firstly, according to the original initial search point, four sub-search windows are constructed. Then, the hexagon based search algorithm will be performed respectively in the four sub-search windows. The final result is the best search point with the minimum R-D cost among the best points in the four sub-search windows. In order to trade off the computational complexity and R-D performance, two adaptive early termination strategies are proposed. The experimental results show that the proposed algorithm yields a quite promising coding performance in terms of R-D performance and computational complexity. Especially, the proposed algorithm can work well in multiview video sequences with various motion and disparity activities.