JEI Letters

Extrapolation-free arbitrary-shape motion estimation using phase correlation

[+] Author Affiliations
Vasileios Argyriou, Theodore Vlachos

University of Surrey, Centre for Vision, Speech and Signal Processing, School of Electronics and Physical Sciences, GU2 7XH United Kingdom

J. Electron. Imaging. 15(1), 010501 (February 28, 2006). doi:10.1117/1.2170582
History: Received October 04, 2005; Revised December 09, 2005; Accepted December 19, 2005; Published February 28, 2006
Text Size: A A A

Open Access Open Access

We propose a frequency domain scheme for obtaining subpixel estimates of interframe motion for arbitrary shaped regions. Our scheme is based on phase correlation and the shape adaptive discrete Fourier transform and one of its key features is that it does not require extrapolation, which requires extra complexity and can dilute the accuracy of the estimated motion parameters. We demonstrate that our method outperforms in terms of subpixel accuracy and motion-compensated prediction error both conventional phase correlation but also shape adaptive techniques operating in the frequency domain and requiring extrapolation.

Figures in this Article

Motion estimation is a critical component of various video processing tasks, especially video compression, allowing redundancy reduction in the temporal domain. International standards for video communications such as MPEG-12 and H.26134 employ the well-established hybrid two-component architecture, which relies on motion estimation and compensation as well as on the lossy compression of the motion-compensated prediction error. Motion estimation in such standards is carried out by means of block matching in the data domain with one motion vector portraying the motion of each block. Such block-based approaches offer well-documented implementation advantages such as low complexity and low overheads mainly due to their regularity. On the other hand, they have a number of well-known disadvantages. A block may contain more moving objects than just one, in which case a single motion vector derived from the most dominant object will cause large motion compensation errors in areas occupied by the other objects. Conversely, a moving object may be contained in more blocks than one. Any errors in estimating motion vectors for those blocks are likely to cause blocking artefacts. Various attempts at departing from established block-based approaches have been made, most notably in video coding systems like MPEG-4, while in H.264 a variable block size approach was preferred to shape coding. While motion estimation is not a normative element, most compliant architectures implement arbitrary shape motion estimation in the pixel domain using suitable modifications to the well-known block-matching algorithm, such as extrapolation of the arbitrary shaped area until the limits of a bounding rectangle are reached. Such pixel-domain modifications inherit some of the disadvantages of baseline block matching such as complexity, assuming an exhaustive search strategy for the identification of the minimum error location. In the wider literature, object-based motion estimation is well represented albeit most approaches operate in the pixel domain. An exhaustive review would be outside the scope of this paper but it is worth mentioning Refs. 14 to name but a few.

Recently there has been a lot of interest in motion estimation techniques operating in the frequency domain because they offer well-documented advantages in terms of computational efficiency due to the employment of fast algorithms. Perhaps the best-known method in this class is phase correlation (PC),5 which has become one of the motion estimation methods of choice for a wide range of nonconsumer applications.6 In addition to computational efficiency, PC offers key advantages in terms of its strong response to edges and salient picture features, its immunity to illumination changes and moving shadows, and its ability to measure large displacements without sacrificing subpixel accuracy.

In this letter we propose an arbitrary-shape motion estimation algorithm based on PC. While in Ref. 7 we proposed a solution using conventional extrapolation, i.e., by padding with the average (mean) intensity of the arbitrary-shaped object, in this work we present an extrapolation-free algorithm using the shape adaptive discrete Fourier transform (SA-DFT) methodology.8

This letter is organized as follows. In Sec. 2 we briefly review the principles underlying subpixel motion estimation using PC. In Sec. 3 we present the arbitrary-shape phase correlation algorithm. In Sec. 4 we report experimental results while in Sec. 5 we draw conclusions arising from this work.

Baseline PC operates on a pair of images (or cosited blocks) ft and ft+1 of identical dimensions belonging to consecutive frames or fields of a moving sequence sampled at t, t+1. The estimation of motion relies on the detection of the maximum of the cross-correlation function between ft and ft+1. Since all functions involved are discrete, cross-correlation is circular and can be carried out as a multiplication in the frequency domain using fast implementations. The real-valued correlation surface is defined asDisplay Formula

1ct,t+1(k,l)=F1(Ft*Ft+1Ft*Ft+1)
where Ft and Ft+1 are respectively the two-dimensional discrete Fourier transforms of ft and ft+1; F1 denotes the inverse Fourier transform, and * denotes complex conjugate. The coordinates (km,lm) of the maximum of the real-valued array ct,t+1 can be used as an estimate of the horizontal and vertical components of motion at integer-pixel precision between ft and ft+1 as follows:Display Formula
2(km,lm)=argmax{ct,t+1(k,l)}.
Subpixel accuracy of motion measurements is obtained by variable-separable fitting performed in the neighborhood of the maximum using one-dimensional quadratic functions.6 Using the notation in Eq. 2 above, prototype functions are fitted to the triplets:Display Formula
3{ct,t+1(km1,lm),ct,t+1(km,lm),ct,t+1(km+1,lm)}and{ct,t+1(km,lm1),ct,t+1(km,lm),ct,t+1(km,lm+1)}.
The location of the maximum of the fitted function provides the required subpixel motion estimate (dx,dy). For example, fitting a parabolic function horizontally to the left-hand side of Eq. 3 yields a closed-form solution for the horizontal component of the motion estimate dx as follows:Display Formula
4dx=ct,t+1(km+1,lm)ct,t+1(km1,lm)2(2ct,t+1(km,lm)ct,t+1(km+1,lm)ct,t+1(km1,lm)).
The fractional part dy of the vertical component can be obtained in a similar way using the right-hand side of Eq. 3.

The proposed arbitrary shape phase correlation (ASPC) scheme assumes that an object is available (i.e., obtained using segmentation) for an object of interest in the target (i.e., next) frame. The motion of this object needs to be estimated relative to a reference (i.e., current) frame. The ASPC algorithm consists of two main steps. First, SA-DFT is applied to pixel values inside the object both in the target and reference frames. Then, PC is applied using Eqs. 14 in order to obtain motion estimates of subpixel accuracy.

Shape Adaptive Discrete Fourier Transform

SA-DFT is based on the notion that the DFT of a vector can be interpreted as the transform of a periodic signal, one period of which is processed. The signal doesn’t need to be shifted, it suffices to extend it periodically and to compute the DFT starting from the beginning of a row/column.

We consider a one-dimensional vector of data samples x(n) of size N with n=0,1,,N. We assume that NS samples belong to the object of interest with n=m, m+1,,Ns+m1 while the remaining samples are considered to belong to another object or the background. The application of SA-DFT consists of the following steps:

  • Periodic extension of the NS object samples to span the entire range of values n=0,1,,N, i.e., set x(n+kNS)=x(n) with k=,2,1,0,1,2,, and 0<n+kNS<N.
  • Computation of the NS-point DFT.
  • Scaling of the results. In this case the scaling factor is 1NS, which makes the 2-D transform orthogonal.9
The above can be extended to two dimensions in a variable-separable fashion (i.e., application of the above steps first horizontally then vertically). This allows the computation of SA-DFT for any arbitrary shaped region.

  • Periodic extension of the NS object samples to span the entire range of values n=0,1,,N, i.e., set x(n+kNS)=x(n) with k=,2,1,0,1,2,, and 0<n+kNS<N.
  • Computation of the NS-point DFT.
  • Scaling of the results. In this case the scaling factor is 1NS, which makes the 2-D transform orthogonal.9

Given an arbitrary-shaped region in frame t+1 (i.e., the next frame) motion is estimated between the image data ft+1 inside this region and image data ft inside a cosited region in frame t (i.e., the current frame). If Ft and Ft+1 denote respectively the SA-DFT of ft and ft+1, the final step is to apply the phase correlation method using Eqs. 14.

In our experiments we used the well-known broadcast resolution (720×576pixels, 50 fields per second) MPEG test sequences ‘Mobcal’ and ‘Basketball.’ Only the luminance component was considered and to avoid complications due to interlacing, only even-parity field data were retained. We highlight the principles underlying our scheme using an artificial example. We manually segment the ‘ball’ object from a single frame of ‘Mobcal’ and superimpose it on the ‘calendar’ object from the same sequence without low-pass filtering object boundaries. We then create an artificial sequence by displacing the two objects relative to each other by progressively varying shifts of subpixel accuracy. These shifts are then used as ground truth. We consider two cases (shown in Fig. 1) corresponding respectively to accurate and inaccurate segmentation of the ‘ball’ object to reflect the real possibility of a segmentation algorithm providing variable quality results. In Fig. 2 we show a magnified portion of the correlation surface for the proposed ASPC scheme. While for conventional phase correlation two peaks would have emerged (each corresponding to the motion of each of the two objects ‘ball’ and ‘calendar’), for ASPC only a single peak emerges corresponding to the motion of the ‘ball’ object. This becomes a critical consideration when the motion parameters of two (or more) objects are similar (but not identical) and hence the proximity of the corresponding peaks on the correlation surface may prevent the accurate extraction of the dominant motion parameters.

Graphic Jump LocationF1 :

Artificial example: (a) original, (b) showing accurate segmentation mask, and (c) showing inaccurate segmentation mask relative to the new object location.

Graphic Jump LocationF2 :

Correlation surface using proposed ASPC (inaccurate mask).

Next, we compare the proposed scheme with conventional PC and the shape adaptive phase correlation (SAPC) algorithm presented in Ref. 7, which is based on padding using the average intensity of the object of interest. In Table 1 we show the average MSE relative to the ground truth subpixel displacement parameters (computed over the total number of frames) obtained for both accurate and inaccurate segmentation scenarios of object ‘calendar.’ Overall, these results demonstrate (best cases underlined) that the proposed scheme achieves consistently higher accuracy compared to both alternative schemes.

Table Grahic Jump Location
Average ground truth MSE performance comparison for artificial motion.

Next we turn our attention to the estimation of real motion. We identify arbitrary-shaped objects of interest such as the ‘train’ object in ‘Mobcal’ and the ‘player’ object in ‘Basketball.’ The objects are determined manually and are shown in Fig. 3. We have deliberately allowed the objects to be inaccurate, i.e., not following closely the outline of the object under consideration or even omitting part(s) of it. This is a reflection of the fact that object definition will occasionally be inaccurate in a practical situation if this is obtained from automatic segmentation while this may not be true for manual segmentation. Performance is compared to conventional PC using a rectangular block (of the same size in pixels as the arbitrary-shaped object), which includes a large section of the object. Performance is assessed either using the motion-compensated prediction MSE (average values computed over the total number of frames are shown in Table 2) or the peak signal-to-noise ratio (PSNR) as a function of frame number (shown in Fig. 4) for the two sequences under consideration. It is worth noting that Table 2 includes a comparison with spatial-domain block-matching, which further underlines the potential of our method. Our results confirm the superiority of the proposed scheme, i.e., by as much as 4dB compared to conventional phase correlation.

Table Grahic Jump Location
Average motion-compensated prediction MSE performance comparison for real motion.
Graphic Jump LocationF3 :

Object masks for ‘train’ (a) and ‘player’ (b).

Graphic Jump LocationF4 :

PSNR vs frame number for conventional phase correlation and ASPC for objects ‘player’ (Basketball) and ‘train’ (Mobcal).

In this letter an arbitrary shape motion estimation algorithm based on phase correlation was presented. Owing to the fact that the scheme operates in the frequency domain it enjoys a high degree of computational efficiency and can be implemented by fast algorithms such as the FFT. Our approach avoids extrapolation and uses information only from moving objects of interest thereby yielding higher accuracy motion estimates. Our results have shown that the proposed method outperforms conventional phase correlation as well as shape adaptive phase correlation using extrapolation both for artificially-induced motion using manually extracted objects as well as actual interframe motion.

Kauff  P., and Schüür  K., “ Fast motion estimation for real-time shape-adaptive MPEG-4 encoding. ,”  Proc. 2000 ACM Workshops on Multimedia.  (Nov. (2000)).
Stiller  C., “ Object-based estimation of dense motion fields. ,” IEEE Trans. Image Process..  1057-7149 6, (2 ), 234–250  (Feb. (1997)).
Delopoulos  A N., and Constantinides  A. G., “ Object oriented motion and deformation estimation using composite segmentation. ,”  Proc. IEEE-ICIP. , 2217–2220  ((1995)).
Panis  S., and Cosmas  J. P., “ Motion estimation with object based regularisation. ,” Electron. Lett..  0013-5194 32, (9 ), 872–873  (May (1996)).
Pearson  J. J., , Hines  D. C., , Goldsman  S., , and Kuglin  C. D., “ Video rate image correlation processor. ,”  Proc. SPIE. 119, , 197–205  ((1977)).
Thomas  G. A., “ Television motion measurement for DATV and other applications. ,” BBC Res. Dept. Rep. ((1987)).
Hill  L., and Vlachos  T., “ Motion measurement using shape adaptive phase correlation. ,” Electron. Lett..  0013-5194 37, (25 ), 1512–1513  (Dec. (2001)).
Stasinski  R., “ Shape adaptive discrete Fourier transform for coding of irregular image segments. ,” NORSIG-99 (Sept. (1999)).
Stasinski  R., and Konrad  J., “ A new class of fast shape-adaptive orthogonal transforms and their application to region-based image compression. ,” IEEE Trans. Circuits Syst. Video Technol..  1051-8215 9, , 16–34  (Feb. (1999)).
© 2006 SPIE and IS&T

Citation

Vasileios Argyriou and Theodore Vlachos
"Extrapolation-free arbitrary-shape motion estimation using phase correlation", J. Electron. Imaging. 15(1), 010501 (February 28, 2006). ; http://dx.doi.org/10.1117/1.2170582


Figures

Graphic Jump LocationF1 :

Artificial example: (a) original, (b) showing accurate segmentation mask, and (c) showing inaccurate segmentation mask relative to the new object location.

Graphic Jump LocationF2 :

Correlation surface using proposed ASPC (inaccurate mask).

Graphic Jump LocationF3 :

Object masks for ‘train’ (a) and ‘player’ (b).

Graphic Jump LocationF4 :

PSNR vs frame number for conventional phase correlation and ASPC for objects ‘player’ (Basketball) and ‘train’ (Mobcal).

Tables

Table Grahic Jump Location
Average ground truth MSE performance comparison for artificial motion.
Table Grahic Jump Location
Average motion-compensated prediction MSE performance comparison for real motion.

References

Kauff  P., and Schüür  K., “ Fast motion estimation for real-time shape-adaptive MPEG-4 encoding. ,”  Proc. 2000 ACM Workshops on Multimedia.  (Nov. (2000)).
Stiller  C., “ Object-based estimation of dense motion fields. ,” IEEE Trans. Image Process..  1057-7149 6, (2 ), 234–250  (Feb. (1997)).
Delopoulos  A N., and Constantinides  A. G., “ Object oriented motion and deformation estimation using composite segmentation. ,”  Proc. IEEE-ICIP. , 2217–2220  ((1995)).
Panis  S., and Cosmas  J. P., “ Motion estimation with object based regularisation. ,” Electron. Lett..  0013-5194 32, (9 ), 872–873  (May (1996)).
Pearson  J. J., , Hines  D. C., , Goldsman  S., , and Kuglin  C. D., “ Video rate image correlation processor. ,”  Proc. SPIE. 119, , 197–205  ((1977)).
Thomas  G. A., “ Television motion measurement for DATV and other applications. ,” BBC Res. Dept. Rep. ((1987)).
Hill  L., and Vlachos  T., “ Motion measurement using shape adaptive phase correlation. ,” Electron. Lett..  0013-5194 37, (25 ), 1512–1513  (Dec. (2001)).
Stasinski  R., “ Shape adaptive discrete Fourier transform for coding of irregular image segments. ,” NORSIG-99 (Sept. (1999)).
Stasinski  R., and Konrad  J., “ A new class of fast shape-adaptive orthogonal transforms and their application to region-based image compression. ,” IEEE Trans. Circuits Syst. Video Technol..  1051-8215 9, , 16–34  (Feb. (1999)).

Some tools below are only available to our subscribers or users with an online account.

Related Content

Customize your page view by dragging & repositioning the boxes below.

Related Book Chapters

Topic Collections

PubMed Articles
Advertisement
  • Don't have an account?
  • Subscribe to the SPIE Digital Library
  • Create a FREE account to sign up for Digital Library content alerts and gain access to institutional subscriptions remotely.
Access This Article
Sign in or Create a personal account to Buy this article ($20 for members, $25 for non-members).
Access This Proceeding
Sign in or Create a personal account to Buy this article ($15 for members, $18 for non-members).
Access This Chapter

Access to SPIE eBooks is limited to subscribing institutions and is not available as part of a personal subscription. Print or electronic versions of individual SPIE books may be purchased via SPIE.org.