Abstract
In this thesis, we propose a fast block-based motion estimation algorithm which utilizes downhill simplex search for video coding. Downhill simplex search mainly consists of two parts: initialization of simplex part and downhill simplex iterations part. In the initialization part, spatially and temporally neighboring blocks of the current block is used to help finding a good initial simplex. The initial simplex is essential to the whole process because it has great influences on the search time and accuracy. After the initial simplex is decided, the four actions of downhill simplex search are iteratively employed to check new points for substituting the high point of the simplex, until the stop criterion is satisfied. Finally, the point having the smallest distortion measure in the simplex is the motion vector. The experiment contains two parts. In the first part, only motion estimation and compensation are applied in order to see the direct influence on the estimation accuracy. In the second part, we integrate the proposed motion estimation algorithm into an MPEG-4 sample codec to see the practical effects on both the time and quality.