EE 5359 Project Report Spring 2008 Comparative study of Motion Estimation ME Algorithms Khyati Mistry 1000552796 1 ABSTRACT Motion estimation refers to the process of determining motion vectors representing the transition motion of objects in successive video frames Motion estimation finds its applications in two main areas reduction of temporal redundancy in video coders and representation of true motion of objects in real time video applications This project focuses on the comparative study of the different motion estimation techniques and search algorithms that have been proposed for interframe coding in moving video sequences taking into consideration the different kinds of motion of the moving objects in successive frames translational rotational zooming etc This is very important because it helps in bandwidth conservation by reducing temporal redundancy and reduction in power consumption by reducing computational complexity A broad classification of motion estimation algorithms is presented and different time domain and frequency domain algorithms are studied and compared Some of the block matching time domain algorithms like full search three step search new three step search four step search diamond search are implemented and their performance is compared based on their computational complexity and error function 2 1 Introduction Motion estimation is the process of determining motion vectors that describe the transformation from one 2D image to another usually from adjacent frames in a video sequence Fig 1 shows the block diagram for motion estimation 1 Fig 1 Motion estimation block diagram 1 The motion estimation module will create a model for the current frame by modifying the reference frames such that it is a very close match to the current frame This estimated current frame is then motion compensated and the compensated residual image is then encoded and transmitted The objective is to estimate the motion vectors from two time sequential frames of the video The motion of an object in the 3 d object space is translated into two successive frames in the image space at time instants t 1 and t2 as shown in Fig 2 Translational and rotational motion of objects can be defined in temporal frames using this model 3 Fig 2 Basic geometry 2 where t1 t2 represent the time axis such that t2 t1 X Y Imagespace coordinates of P in the scene at time t1 X Y Image space coordinates of P at time t2 t1 x y z Object space coordinates at a point P in the scene at time t 1 The output of the motion estimation algorithm comprises the motion vector for each block and the pixel value differences between the blocks in the current frame and the matched blocks in the reference frame 1 1 Broad classification of motion estimation algorithms 4 Fig 3 Motion estimation algorithms 10 Frequency domain algorithms In these algorithms the algorithm is applied on the transformed coefficients The different algorithms techniques used are Phase correlation matching in wavelet and DCT domains 17 However due to the computational complexity involved in these algorithms time domain block matching algorithms are preferred Time domain algorithms These comprise of matching algorithms and gradientbased algorithms 1 16 Block matching algorithms match all or some pixels in the current block with the block in the search area of reference frame based on some cost function 1 15 Feature based algorithms match the meta information data of the current block with that of the block in reference frame 16 1 1 1 Frequency domain motion estimation algorithms In the frequency domain the phase correlation algorithm provides accurate predictions but is based on the fast Fourier transform FFT which is 5 incompatible with current DCT based video coding standards and which has high computational complexity since a large search window is necessary In implementation the current frame is divided into 16x16 blocks and phase correlation calculation is performed for each block In order to correctly estimate the cross correlation of the corresponding blocks in respective frames blocks are extended to 32x32 in size centered around the formerly defined 16x16 blocks to calculate phase correlation If only 16x16 blocks are considered their correlation might be very low for particular motion due to the small overlapping area as shown in Fig 4 a Once the block size is extended to 32x32 the overlapping area is increased for better correlation estimation as is shown in Fig 4 b The highest peak in the correlation map usually corresponds to the best match between a large area while not necessarily the best match for 16x16 object block If there are several moving objects in the block with different displacement there can be several peaks appearing in the correlation map as shown in Fig 5 where there are two peaks In this case several candidates are selected instead of just one highest peak and then the peak which best represents the displacement vector for the object block is selected Once the candidates are selected they are examined one by one using image correlation For each candidate the motion vector is already found hence the 16x16 object block can be placed in the 32x32 window of the previous frame to measure the extent of correlation The candidate resulting in the highest image correlation is chosen and its displacement is the right motion vector for the object block Fig 4 Correlation area using a 16x16 and b 32x32 blocks 21 6 Fig 5 Phase Correlation between Two Blocks 21 DCT based motion estimation simplifies the conventional DCT based video coders achieving spatial redundancy reduction through DCT and temporal redundancy reduction through motion estimation and compensation In the conventional DCT based video coder the feedback loop has the following functional blocks DCT inverse DCT IDCT quantizer inverse quantizer and spatial domain motion estimation and compensation Fig 6a However if motion estimation and compensation are performed entirely in the DCT domain IDCT can be removed from the feedback loop Therefore the feedback loop contains the reduced functional blocks quantizer inverse quantizer and transform domain motion estimation and compensation Fig 6b The conventional DCT based video coder and the simplified DCT based video coder are shown in Fig 6 17 However high computational complexity is still the main drawback of the DCTbased motion estimation and compensation approach 7 Fig 6 a Conventional video encoder with motion estimation and
View Full Document
Unlocking...