Block motion estimation using fast full search and candidate position subsampling for video encoder system

Abstract

Motion estimation via a block-matching algorithm (BMA) has been used in almost all the video coding standards, including ITU-T H.263/H.264 and ISO/IEC MPEG-1/2/4, because it efficiently removes temporal redundancy between frames. The BMA divides frames into non-overlapped blocks and finds the displacement of the best-matched block from the reference frame within a search window, which is considered to be the motion vector (MV) of the block in the current frame. The measures that are widely used for determination of the best-matched block are the sum of the absolute differences (SAD) and the sum of the squared errors (SSE). The SAD is preferred due to the simplicity of its implementation. Although the full-search (FS) algorithm is the optimal BMA with regard to motion estimation accuracy, its computational complexity limits practical usage. Hence, many BMAs have been developed to reduce the complexity. The methods used in BMAs can be divided into two categories: 1) reducing the number of search points and 2) reducing the load for the matching-criterion. One approach in the second category uses lower bounds (also called boundary values) for the complete matching error, SAD. Before calculating the SAD of the current candidate, lower bound values (BVs) are obtained, and the necessity of calculating the SAD is determined by comparing lower bound values with the minimum SAD obtained from the previous candidates. The famous set of lower bound values of the SAD is derived from the well-known triangular inequality. With a set of lower bound values, the temporal minimum SAD is compared with BVs from the smallest BV to the largest BV to reject non-best candidates. In this thesis, a new scheme to obtain a BVs set is proposed. It is derived from a concept of block division gain (BDG), which is defined as the difference between the adjacent boundary values. The proposed scheme successively reduces the number of computations needed to compute the next BV from the previous BV....