Fast block-matching motion estimation search on FPGA

Abstract

This work presents an implementation of the Diamond Search Block Matching Algorithm. A Block Matching Algorithm is a method of finding the similarities between two consecutive video frames. One of the most efficient algorithms under the category of block matching is the Diamond Search which uses a diamond shape search point pattern to find the similarities between one frame and another. Such an algorithm exploits temporal redundancies which refers to having pixels in two video frames with the same values at the same location. A Block Matching Algorithm falls under Motion Estimation which is an essential component of video compression. Motion Estimation is the most expensive procedure in the compression process which implies that efficient algorithms are required to efficiently compress videos. The objective of this work was to implement the Diamond Search on an FPGA. The outcome was a set of motion vectors which describe the motion transformation from one video frame to another. The algorithm was first implemented on MATLAB and the resulting motion vectors were examined and confirmed to be correct. The algorithm was then ported to VHDL code to be used on an FPGA. The FPGA’s LEDs were used to check if all the resulting motion vectors matched with the vectors obtained from MATLAB. Frames from different video sequences were used and the motion vectors from MATLAB were also altered to check if the FPGA implementation would detect the mismatch. All of the results were correct.