Oriental Journal of Computer Science and Technology

Open Access Open Access  Restricted Access Subscription Access

Optical Flow Estimation Using Total Least Squares Variants


Affiliations
1 Department of Telecommunications, Universidade Federal Fluminense (UFF), Rio de Janeiro, Brazil
 

The problem of recursively approximating motion resulting from the Optical Flow (OF) in video thru Total Least Squares (TLS) techniques is addressed. TLS method solves an inconsistent system Gu=z , with G and z in error due to temporal/spatial derivatives, and nonlinearity, while the Ordinary Least Squares (OLS) model has noise only in z. Sources of difficulty involve the non-stationarity of the field, the ill-posedness, and the existence of noise in the data. Three ways of applying the TLS with different noise conjectures to the end problem are observed. First, the classical TLS (cTLS) is introduced, where the entries of the error matrices of each row of the augmented matrix [G;z] have zero mean and the same standard deviation. Next, the Generalized Total Least Squares (GTLS) is defined to provide a more stable solution, but it still has some problems. The Generalized Scaled TLS (GSTLS) has G and z tainted by different sources of additive zero-mean Gaussian noise and scaling [G;z] by nonsingular D and E, that is, D[G;z]E makes the errors iid with zero mean and a diagonal covariance matrix. The scaling is computed from some knowledge on the error distribution to improve the GTLS estimate. For moderate levels of additive noise, GSTLS outperforms the OLS, and the GTLS approaches. Although any TLS variant requires more computations than the OLS, it is still applicable with proper scaling of the data matrix.

Keywords

Motion Estimation, Total Least Squares, Inverse Problems, Optical Flow, Video Processing, Computer Vision SS.
User
Notifications
Font Size

  • Biemond, J., Looijenga, L., Boekee, D. E. and Plompen, R.H.J.M. 1987. A pel-recursive Wiener-based displacement estimation algorithm. Sig. Proc., 13:399-412.

  • Mesarovic, V.Z., Galatsanos N.P. and Katsaggelos A.K. 1995. Regularized constrained total least squares image restoration. IEEE Trans Im. Proc., 1995, 4(8):1096-1108. doi: 10.1109/83.403444

  • Cadzow, J. C. 1984. Total least squares, matrix enhancement, and signal processing. Digital Sig. Proc., 4:21-39.

  • Tsai, C.J., Galatsanos, N.P., Stathaki, T. and Katsaggelos, A. K. 1999. Total least-squares disparity-assisted stereo optical flow estimation. Proc. IEEE Im. Multidimensional Dig. Signal Proc. Work..

  • Estrela, V. V., Rivera, L. A., Beggio, P.C. and Lopes, R. T. 2003. Regularized pel-recursive motion estimation using generalized cross-validation and spatial adaptation. doi: 10.1109/SIBGRA.2003.1241027

  • Golub G.H. and Van Loan. C.F. 1980. An analysis of the total least squares problem. SIAM J. Numer. Anal., 17:883-893.

  • Golub, G.H. and Van Loan, C.F. 1989. Matrix Computations. Johns Hopkins University, Maryland.

  • Van Huffel, S. and Vanderwalle. J. The Total Least Squares Problem: Computational Aspects and Analysis. SIAM, 1991; Philadelphia.

  • Coelho, A.M. and Estrela, V. V. 2012. Data-driven motion estimation with spatial adaptation. Int’l J. of Image Proc. (IJIP), 6(1):54. doi: citeulike-article-id:11966066

  • Coelho, A. M. and Estrela, V. V. 2012. A study on the effect of regularization matrices in motion estimation, Int’l J. of Comp. Applications, 51(19):17-24. doi: 10.5120/8151-1886

  • Coelho, A. M. and Estrela, Vania V. EM-based mixture models applied to video event detection. In Principal Component Analysis - Engineering Applications (Parinya Sanguansat, P. ed). IntechOpen, 2012; pp. 101-124. ISBN 978-953-51-0182-6, 2012 doi: 10.5772/38129

  • Marins, H. R. and Estrela, V. V., On the Use of Motion Vectors for 2D and 3D Error Concealment in H.264/AVC Video. In Feature Detectors and Motion Detection in Video Processing (Dey, N., Ashour, A., Patra, P. K. eds). IGI Global, 2017; pp. 164-186. doi: 10.4018/978-1-5225-1025-3.ch008

  • Fang, X. 2013. Weighted total least squares: necessary and sufficient conditions, fixed and random parameters. J. Geod., 87(8):733–749

  • Grafarend, E. and Awange, J. L. 2012. Applications of Linear and Nonlinear Models, Fixed Effects, Random Effects, and Total Least Squares. Springer, Berlin.

  • Leick, A. 2004. GPS Satellite Surveying. Wiley, New York.

  • Li, B., Shen, Y. and Lou, L. 2013. Seamless multivariate affine error-in-variables transformation and its application to map rectification. Int. J. GIS, 27(8):1572–1592.

  • Neitzel, F. 2010. Generalization of total least-squares on example of unweighted and weighted 2D similarity transformation. J. Geod., 84:751–762.

  • Schaffrin, B. and Felus, Y. 2008. On the multivariate total least-squares approach to empirical coordinate transformations: Three algorithms. J. Geod., 82:373–383.

  • Schaffrin, B. and Wieser, A. 2008. On weighted total least-squares adjustment for linear regression. J. Geod., 82:415–421.

  • Shen, Y., Li, B.F. and Chen, Y. 2010. An iterative solution of weighted total least-squares adjustment. J. Geod., 85:229–238.

  • Xu, P.L., Liu, J.N. and Shi, C. 2012. Total least squares adjustment in partial errors-in-variables models: algorithm and statistical analysis. J. Geod., 86(8):661–675.

  • Gultekin, G. K. and Saranli, A. 2013. An FPGA based high performance optical flow hardware design for computer vision applications. Microproc. & Microsystems, 37(3):270-286. doi: 10.1016/j.micpro.2013.01.001

  • Komorkiewicz, M., Kryjak, T. and Gorgon, M. 2014. Efficient hardware implementation of the Horn-Schunck algorithm for high-resolution real-time dense optical flow sensor. Sensors, 14(2):2860–2891. http://doi.org/10.3390/s140202860

  • Barron, J., Fleet, D. and Beauchemin, S. 1994. Performance of optical flow techniques, Int’l J. of Comp. Vision (IJCV), 12:43-77.

  • Chien, S.-Y. and Chen, L.-G. 2011. Reconfigurable morphological image processing accelerator for video object segmentation, J. of Sig. Proc. Systems, 62:77-96.

  • Lopich, A. and Dudek, P. 2009. Hardware implementation of skeletonization algorithm for parallel asynchronous image processing. J. of Sig. Proc. Systems, 56:91-103.

  • Horn, B. and Schunck, B. 1981. Determining optical flow. A.I., 17:185-203.

  • Lucas, B. and T. Kanade, T. 1981. An iterative image registration technique with an application to stereo vision. Proc. of Imaging Understand. Workshop, 121–130.

  • Nagel, H.-H. 1989. On a constraint equation for the estimation of displacement rates in image sequences. IEEE Trans. on Patt. Anal. and Mach. Intellig., 11:13-30.

  • Black, M. and Anandan, P. 1993. A framework for the robust estimation of optical flow. Proc. of the 4th Int’l Conf. on Comp. Vision, 231–236.

  • Proesmans, M., van Gool, L., Pauwels, E. and Oosterlinck, A. 1994. Determination of optical flow and its discontinuities using non-linear diffusion. Proc. of the 1994 Europ. Conf. on Comp. Vision, 295–304.

  • Niitsuma, H. and Maruyama, T. 2005. High-speed computation of the optical flow. Proc. of the Int’l Conf. on Image Analysis and Proc. (ICIAP), 287–295.

  • Shibuya, L. H., Sato, S. S., Saotome, O. and Nicodemos, F. G. 2010. A real-time system based on FPGA to measure the transition time between tasks in a RTOS. Proc. of the 1st Work. on Embedded Syst., 29-39. http://sbrc2010.inf.ufrgs.br/anais/data/pdf/wse/st01_03_wse.pdf

  • Strzodka, R. and Garbe, C. 2004. Real-time motion estimation and visualization on graphics cards. Proc. of the 2004 Conf. on Visualization, 545–552.

  • Mizukami, Y. and Tadamura, K. 2007. Optical flow computation on compute unified device architecture. Proc. of the 14th Int’l Conf. on Image Analysis and Proc., 179–184.

  • Chase, J., Nelson, B., Bodily, J., Wei, Z. and Lee, D.-J. 2008. Real-time optical flow calculations on FPGA and GPU architectures: a comparison study. Proc. of the 16th Int’l Symp. on Field-Programmable Custom Comp. Machines, 173–182.

  • Yu, J. J., Harley, A. W. and Derpanis. K. G. 2016. Back to basics: Unsupervised learning of optical flow via brightness constancy and motion smoothness. arXiv preprint arXiv:1608.05842

  • MPEG-7 Overview, ISO/IEC JTC1/SC29/WG11 WG11N6828, 2004.

  • Popovic, V., Seyid, K., Cogal, Ö., Akin, A., and Leblebici, Y. 2017. Real-time image registration via optical flow calculation. Design and Implementation of Real-Time Multi-Sensor Vision Systems. Springer, Cham. doi: 10.1007/978-3-319-59057-8_9


Abstract Views: 329

PDF Views: 4




  • Optical Flow Estimation Using Total Least Squares Variants

Abstract Views: 329  |  PDF Views: 4

Authors

Maria A. De Jesus
Department of Telecommunications, Universidade Federal Fluminense (UFF), Rio de Janeiro, Brazil
Vania V. Estrela
Department of Telecommunications, Universidade Federal Fluminense (UFF), Rio de Janeiro, Brazil

Abstract


The problem of recursively approximating motion resulting from the Optical Flow (OF) in video thru Total Least Squares (TLS) techniques is addressed. TLS method solves an inconsistent system Gu=z , with G and z in error due to temporal/spatial derivatives, and nonlinearity, while the Ordinary Least Squares (OLS) model has noise only in z. Sources of difficulty involve the non-stationarity of the field, the ill-posedness, and the existence of noise in the data. Three ways of applying the TLS with different noise conjectures to the end problem are observed. First, the classical TLS (cTLS) is introduced, where the entries of the error matrices of each row of the augmented matrix [G;z] have zero mean and the same standard deviation. Next, the Generalized Total Least Squares (GTLS) is defined to provide a more stable solution, but it still has some problems. The Generalized Scaled TLS (GSTLS) has G and z tainted by different sources of additive zero-mean Gaussian noise and scaling [G;z] by nonsingular D and E, that is, D[G;z]E makes the errors iid with zero mean and a diagonal covariance matrix. The scaling is computed from some knowledge on the error distribution to improve the GTLS estimate. For moderate levels of additive noise, GSTLS outperforms the OLS, and the GTLS approaches. Although any TLS variant requires more computations than the OLS, it is still applicable with proper scaling of the data matrix.

Keywords


Motion Estimation, Total Least Squares, Inverse Problems, Optical Flow, Video Processing, Computer Vision SS.

References





DOI: https://doi.org/10.13005/ojcst%2F10.03.03