Adaptive Multi-pattern Search Algorithm for Motion Estimation

A novel fast integer-pixel multi-pattern search algorithm is proposed in this paper. The Cross Search Pattern (CSP) is used to get the coarse position of the best matching point, then Small Diamond Search Pattern (SDSP) or Small Square Search Pattern (SSSP) is chosen to locate the best matching point accurately according to the size of the partitioned block. In order to reduce the number of search points, the judging threshold is applied, which is determined by the compensation value and the Sum of Absolute Difference (SAD) values of three adjacent blocks. Experimental results show that, compared to Unsymmetrical cross Multi-Hexagon grid Search Algorithm (UMHSA) and Diamond Search Algorithm (DSA), the proposed algorithm reduces search time greatly, and keeps the generated bytes and the PSNR of luminance signals in similar levels.