A two-stage fast block matching algorithm using integral projections

Joon Seek Kim, Rae Hong Park, Byung Uk Lee

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


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.

Original languageEnglish
Pages (from-to)336-348
Number of pages13
JournalJournal of Visual Communication and Image Representation
Issue number4
StatePublished - Dec 1993


Dive into the research topics of 'A two-stage fast block matching algorithm using integral projections'. Together they form a unique fingerprint.

Cite this