Flexible triangle search algorithm for block based motion estimation

A new fast technique for block-based motion estimation, the flexible triangle search (FTS) algorithm is presented. The FTS is based on the simplex algorithm for optimization adapted to an integer grid. The proposed algorithm is highly flexible due to its ability to quickly change its search direction and to move toward the target of the search criterion. Unlike other fast search algorithms, the FTS can skip local minima and converge towards a better matching position. The FTS algorithm was implemented as part of an H.263 encoder and was compared with several other block matching algorithms. The results obtained show that the FTS has much better performance over other techniques in terms of computation complexity and motion estimation accuracy.