Predictive Three Step Search (PTSS) algorithm for motion estimation

Motion estimation is a vital task in videocompression and many algorithms are proposed to reduce itscomputational complexity. In a conventional Full Search (FS)algorithm, all blocks are searched for a match in the searchwindow, resulting in a very acceptable PSNR compared to theother methods. However it suffers from heavy computationaloverhead. Three Step Search (TSS) algorithm which limits thesearch space adaptively, is used in many applications for itssimplicity and effectiveness. The PTSS algorithm proposed in thispaper decreases the number of search blocks even more, usingmotion information obtained from its neighboring blocks.Experimental and simulation results show approximately a 20%speed enhancement with the same or slightly improved PSNR incomparison to TSS.

Keywords:

video compression , motion estimation , block matching , Three step search , Predictive