MEPI

(Motion Estimation based on Phase Information)

by V. Bruni, D. de Canditiis, and D. Vitulano

Idea: the average B of K blocks b_k aligned in K successive frames {f_k}_k=0,1,..,K is equivalent to the convolution of the reference block b₀ (i.e. lying in the reference frame f₀) with a Dirac comb kernel:

that yields:

Advantages:

simultaneous processing of an arbitrary number of frames
motion estimation is solved without search, as happens using PCA (search of the best peak) and BMA (search of the best block)
drastic reduction of the computational effort (the inversion of the DFT is avoided).

Under Noise

The equality above becomes:

where

but

MEPI model cannot be directly used

MEPI is invariant to linear operators

non linear operations are expensive (not suitable for real-time applications).

We can then associate an error to the horizontal motion component d_y (and similarly an error to the vertical motion component d_x). The latter is a derived measure of the noisy blocks (see references for details). It can be proven that the error can be upperbounded by the quantity:

Example

But SNR at low frequencies can be further increased using a space-filling curve.

A space-filling curve passes through each point of a 2D region producing a more correlated 1D signal!

Typical examples are:

However, each block of the image has to be modelled through a suitable curve, that accounts for the presence of a main edge inside the block.

The aim is to increase the clean signal correlation without performing denoising. Hence, we propose the two following curves

Bearing in mind the example above, we then have the two following 1D signals using respectively (from left to right) the vertical and horizontal scan:

The Algorithm

Experimental Results

Quality

Mepi's performance on Footbal, Foreman and Flower are listed below. Mepi [1,2] has been also compared with classical Phase Correlation Algorithm (PCA)[3], Phase Difference Method (PDM) [4], 2bit (2BT) [5] and Block Matching Algorithm [6].

Comparison in terms of PSNR and standard deviation

Look at the original and (MEPI) motion compensated sequences

FOREMAN

Comparison in terms of PSNR and standard deviation

Look at the original and (MEPI) motion compensated sequences

FLOWER

Comparison in terms of PSNR and standard deviation

Look at the original and (MEPI) motion compensated sequences

Some comparisons in terms of PSNR and no. of frame

Complexity

Without noise, MEPI has a complexity lower than available motion estimation approaches:

In case of noise, the computation is still lower than alternative methods. The complexity is:

0((K+6)M²)

if K=2 then 8.4414 operations per pixel are required

Detailed decription about MEPI's complexity

Summing up:

References:

V. Bruni, D. De Canditiis, D. Vitulano, Fast Motion Estimation using Spatio Temporal Filtering, Proc. of ICIAR 2006, vol. 1, pp. 105-110, Special Issue in Lecture Notes in Computer Science.
V. Bruni, D. De Canditiis, D. Vitulano, Phase based estimation for noisy sequences, Proceedings of (IEEE) IWSSIP 2007, Maribor, Slovenia, pp. 399-402, June 2007.
C. D. Kughlin, D.C. Hines, The phase correlation image alignment method, Proceedings of IEEE Int. Conf. Systems, Man. and Cybernetics, pp. 163-165, September 1975.
M. Balci, H. Foroosh, Inferring motion from the rank constraint of the phase matrix, Proc. of ICASSP, Vol. 2, pp. 925-928, March, 2005.
A. Erturk, S. Erturk, Two-Bit Transform for Binary Block Motion Estimation, IEEE Transactions on Circuits ans Systems for Video Technology, Vol. 15, No. 7, pp. 938-946, July 2005.
J. M. Jou, P.-Y. Chen and J.-M. Sun, The Gray Prediction Search Algorithm for Block Motion Estimation, IEEE Trans. Circuits Syst. Video Technol., vol 9, no. 6, pp. 843-848, September 1999.

Download MEPI's (.m) code