A fast motion estimation algorithm used in H.264，UMhexagonS, is optimized to improve the efficiency of video compression. Firstly, a stop-search technique is used to judge whether the motion estimation of current macro block should be stopped after the initial search point is predicted. Then,the original algorithm is improved in two respects for macro blocks which need further motion estimation. One improvement is that fewer search points are used in motion estimation by the proposed partition method when multi-hexagon-grid pattern or cross pattern are adopted, and the other improvement is that the search points of square search pattern and extended-hexagon search pattern are reduced according to statistical characteristics of motion vectors. Moreover, the rationality of the partition method is proved. Experimental results show that the average time of motion estimation is reduced by 15.59% compared with that of the original algorithm, whereas, the Peak Signal to Noise Ratio (PSNR) and bit rate remain almost unchanged. The proposed algorithm improves the coding performance and is suitable for various types of video sequences.