H.264 motion estimation and flexible triangle search

Motion estimation (ME) in H.264 can account for 90% of the encoding time. As such, ME optimization techniques are extensively researched. In this project, we studied and implemented ME technique called Flexible Triangle Search (FTS). Its performance is compared to other ME techniques found in the Joint Video Team (JVT) reference software. Results show the FTS rate-distortion (R-D) curve is very close to the R-D curves of other ME techniques and in turn is close to the optimum Full Search (FS) R-D curve. The benefit of the FTS technique is its complexity which is shown to be significantly less than FS and up to 30% savings from other techniques. FTS is then implemented as a quarter-pixel ME technique while full-pixel ME is completely bypassed. Experimental results show 41% savings in complexity is possible over other sub-pixel ME techniques. The results make FTS an attractive ME technique.