An adaptive search range method for HEVC with the k-nearest neighbor algorithm

The latest video coding standard, High Efficiency Video Coding (HEVC), has a large amount of complexity in its inter coding. To reduce the complexity of the inter coding for HEVC, an adaptive searching range algorithm is proposed in this paper. The proposed method separates inter coding into a learning stage and predicting stage. In the learning stage, the relationship between the prediction units (PU) difference, the length of the motion vector prediction (MVP), and the best searching range is learned. In the predicting stage, the k-nearest neighbor algorithm is adopted to find the best searching range based on the learned data. Experiments showed that 91% of the complexity of the motion estimation is reduced compared with the full search method.