中文摘要：

针对UMHexagonS算法存在重复搜索和搜索点数较多的问题，提出了一种UMHexagonS改进算法。算法利用模版间的互补性以及模版搜索规律分别对UMHexagonS算法中的5×5模版和小六边形模版进行了改进，避免了模版间的重复搜索；设计了一种只与搜索过程相关的提前终止策略，减少了非对称多六边形格点模版不必要的搜索点。实验结果表明，在输出码流码率及峰值信噪比基本不变的前提下，改进算法能有效提升各类视频序列的编码效率，特别是对复杂背景、复杂运动及剧烈运动视频序列编码效率的提升较显著，可以减少20％左右的运动估计时间。

英文摘要：

Aiming at the problem of repeating search and more search points in UMHexagonS algorithm, an improved UMHexagonS algorithm is proposed. The algorithm improves on 5 ×5 pattern and small hexagon pattern of UMHexagonS algorithm by using the complementarity and the search rules between search patterns, so as to avoid the repeating search between patterns, then designs an early termination strategy which is only related to search process, it can reduce unnecessary search points of uneven multi-hexagon-grid search pattern. The experimental results show that, with only negligible change of PSNR and output stream hit rate, the improved algorithm can effectively enhance coding efficiency for the various types of video sequences, especially for complex background, complex motion and high motion video sequences, it can reduce about 20% motion estimation time.