Abstract: With the high accuracy and low computational requirement，the UMHexagonS algorithm has been accepted for the possible implementation of the block motion estimation process in the H.264 video coding standard.In this paper，a new algorithm is proposed，which improves on the UMHexagonS algorithm in three aspects.Firstly，a new prediction vector is added into initial predictor for avoiding being trapped in a local minimum.Secondly，the 5×5 full-search is replaced by an litter octagon search and possibly two small diamond searches to reduce the computational requirement.Thirdly，the multi-octagon-grid search has taken the place of multi-hexagon-grid search to both reduce the computational complexity and better catch the direction of the optimal vector.Simulation results demonstrate that the proposed algorithm can reduce five to ten percent of the computational complexity of the UMHexagonS algorithm without loss of its accuracy.

Key words: block motion estimation, H.264, UMHexagonS algorithm, multi-octagon-grid search algorithm

摘要： 由于对编码的高精度和低复杂度的要求，H.264视频编码标准已经采用了UMHexagonS算法作为其可行的块运动估计实施方案。提出了一种新的UMHexagonS改进算法，改进主要在三个方面：第一，增加了一个新的初始预测矢量，以避免过早陷入局部最优；第二，一个小八边形搜索和两个后续的小菱形搜索取代了UMHexagonS算法中的5×5全搜索，这在一定程度上减少了计算量；第三，多八边形格点搜索取代了多六边形格点搜索，这不仅减轻了运算量负担，也在方向上能更好更快地搜索到最佳运动矢量。实验结果表明，所提出的方法不仅能保证UMHexagonS算法的编码效果，同时还能减少5%~10%的运算量，从而节省编码时间。

关键词: 块运动估计, H.264, UMHexagonS算法, 多八边形搜索算法