H.264/MPEG-4 AVC is the coding standard jointly developed by the Video Coding Experts Group (VCEG) of ITU-T and Moving Picture Experts Group (MPEG) of ISO/IEC. Motion estimation is one of the most time-consuming in H.264/MPEG-4 AVC. In this paper, some of the classic motion estimation algorithms are first analyzed, and then motion vector distribution characteristics is discussed, and a sub-regional UMHexagonS motion estimation Algorithm is proposed. In this algorithm, searching area is divided into nine sub-regions, including one detailed searching region and eight coarse searching regions. Simulation results indicate that the time complexity of the improved algorithm is significantly improved, while the SNR and bit rates are essentially kept invariant compared with UMHexagonS.