As an essential component in applications such as video coding, autonomous navigation, and surveillance cameras, efficient and robust motion estimation is always required. This paper proposes a robust block-matching algorithm consisting of a rough matching step and a fine matching step for motion estimation. In the coarse matching step, an improved adaptive rood pattern search strategy combined with an anti-interference similarity criterion is developed to improve the computational efficiency and robustness. In the fine matching step, after performing a subpixel estimation procedure, a bilateral verification scheme is demonstrated to decrease the motion estimation errors caused by environmental disturbances. Experiments are carried out over popular video and image sequences, and several measurement indexes are used to quantify the performance of the proposed method and other motion estimation methods. Comparative analysis and quantitative evaluation demonstrate that the proposed method exhibits strong robustness and can achieve a good balance between computational efficiency and complexity.