Efficient motion estimation is an important problem because it determines the compression efficiency and complexity of a video encoder. Motion estimation can be formulated as an optimization problem; most motion estimation algorithms use mean squared error (MSE), sum of absolute differences (SAD) or maximum a posteriori probability (MAP) as the optimization criterion and apply search-based techniques (e.g., exhaustive search or three-step search) to find the optimum motion vector. However, most of these algorithms do not effectively utilize the knowledge gained in the search process for future search efforts and hence are computationally inefficient. This paper addresses this inefficiency problem by introducing an adaptive motion estimation scheme that substantially reduces computational complexity while yet providing comparable compression efficiency, as compared to existing fast-search methods.……