A fast motion estimation for software based real-time video coding

Many modified three-step search (TSS) algorithms have been studied for the speed up of computation and the improved error performance over the origina l TSS algorithm. In this work, an efficient and fast TSS algorithm is propo sed, which is based on unimodal error search assumption (UESA), properties of error surface, threshold of matching error and partial sum of matching e rror. For the search strategy, we propose a new and efficient search method , which shows good performance in terms of computational reduction and pred iction error compared with other search algorithms. Also, we add half-stop algorithms to above algorithm with little degradation of predicted image qu ality while obtaining more computational reduction. One of them is based on the assumption that if a small amount of motion compensation error is prod uced, we can consider the matching block as matched block and the motion ve ctor as global one. The other removes the computational redundancy by stopp ing the useless calculation of matching error in a matching block. With the added algorithms, we can reduce significantly the computation for motion v ector with small degradation of predicted image quality with a proper thres hold. Experimentally, it is shown that the proposed algorithm is very effic ient in terms of speed up of computation and error performance compared,vit h other conventional modified TSS algorithms.