A two-stage fast block matching algorithm using integral projections

In this paper, a two-stage block matching algorithm (BMA) is proposed. In its first stage, a one-dimensinal distortion measure based on integral projections is introduced to determine the candidate motion vectors, then among which a final motion vector is detected based on the conventional two-dimensional distortion measure. Due to the one-dimensional calculation of a distortion measure, the proposed algorithm combined with the conventional full search (FS) method with a 16 x 16 subblock can reduce computational complexity of the conventional one by a factor of about 4, with its performance almost comparable to that of the conventional one. Simulation results based on the original and noisy image sequences are shown. Also the simulation results of the proposed method combined with the three-step search (TSS) method and Moving Picture Experts Group (MPEG) Simulation Model Three (SM3) are presented. Computer simulation shows that the proposed algorithms combined with conventional ones can reduce computation time significantly with their performances comparable to those of conventional ones.