Study And Optimization On Fast Motion Estimation Algorithm In H.264

H.264/AVC has become the hot spots of current study of compression coding, which is published by ITU-T/ISO. This standard has got attentions and is worldwide welcome by the researchers because of its significant performance compared with former video coding standards and was named the new generation video coding stan-dard. H.264/AVC encoder has achieved significant performance by many useful vid-eo encoding tools, but the motion estimation process concerns greatly on computa-tional complexity. Due to this, a lot of fast block motion estimation algorithms have been proposed in the literature. Such as Three Step Search, Four Step Search, Di-amond Search, Hexagon Based Search and so on. One of these motion estimation al-gorithms -- the UMHexagonS algorithm has been accepted in the H.264 video coding standard due to its high accuracy and low computational requirement.In this paper, we first discuss the basic structure, key technologies and coding layer of H.264 video coding standard. Then the principle of block matching motion estimation is introduced. Besides, 8 classical fast block matching search algorithms are being studied in the search strategy and search steps, meanwhile the strengths and weaknesses of these algorithms are pointed out. Whereafter, we analyze UMHex-agonS algorithm in detail and propose the optimized algorithm based on UMHex-agonS. According to motion rule of the real world video sequences, a new optimized algorithm is proposed which include three steps: first, four predicted motion vetors is adopted to initial the search point; then a big multi-flat hexagon search pattern was adopted to catch the strong motion points and last the predict hexagon search pattern was used to get the best points. Meanwhile, an optimized dynamic search range is used in our reference software JM12.4. The optimized algorithm largely reduces the number of search points and computation complexity as well as speeds up motion es-timation time.Experimenting with some typical video sequences proves that, compared to UMHexagonS algorithm, the optimized one can save about up to 40.84% of motion estimation time with almost no change in PSNR and bit rate, and consequently en-hance the real-time performance of the encoder. So this optimized algorithm could be useful in those real-time situations such as video call or video conference.