Advanced Search
Article Contents
Article Contents
Early Access

Early Access articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Early Access publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Early Access articles via the “Early Access” tab for the selected journal.

Variational image motion estimation by preconditioned dual optimization

  • *Corresponding author: Hongpeng Sun

    *Corresponding author: Hongpeng Sun 
Abstract Full Text(HTML) Figure(2) / Table(2) Related Papers Cited by
  • Estimating optical flows is one of the most interesting problems in computer vision, which estimates the essential information about pixel-wise displacements between two consecutive images. This work introduces an efficient dual optimization framework with accelerated preconditioners to the challenging nonsmooth optimization problem of total-variation regularized optical-flow estimation. In theory, the proposed dual optimization framework brings an elegant variational analysis to the given difficult optimization problem, while presenting an efficient algorithmic scheme without directly tackling the corresponding nonsmoothness in numeric. By introducing efficient preconditioners with a multi-scale implementation, the proposed preconditioned dual optimization approaches achieve competitive estimation results of image motion, compared to the state-of-the-art methods. Moreover, we show that the proposed preconditioners can guarantee convergence of the implemented numerical schemes with high efficiency.

    Mathematics Subject Classification: Primary: 65K10, 49K35; Secondary: 90C25.


    \begin{equation} \\ \end{equation}
  • 加载中
  • Figure 1.  The results of the optical flow estimates. The images on the left column are the Frame 10 image from the Middlebury test sequences. The images in the middle column are the optical flow estimates by pADMM. The images on the right column are the optical flow estimates by Zach-O

    Figure 2.  The results of the optical flow estimates. The images on the left and the middle columns are the corresponding image sequences. The images on the right column are the optical flow estimates by pADMM

    Table 1.  Numerical results for the TV-$ L^1 $ optical flow estimates. In the table, we use $ s|l(t) $ with $ s $ representing the average angular error (AAE), $ l $ denoting the average endpoint error (EPE), and $ s $ representing the computation time with second. The best results of AAE or EPE are underlined

    Average angular error|Average end point error: (Seconds)
    Dimetrodon Hydrangea Rubberwhale
    ALG1 2.85|0.15(12.91s) 2.42|0.21(25.91s) 4.16|0.13(23.55s)
    PDR 3.18|0.17(15.03s) 2.07|0.17(33.34s) 3.13|0.10(30.35s)
    pADMM 2.62| 0.13(8.90s) 2.08|0.17(25.97s) 3.46|0.11(24.12s)
    rpADMMI 2.68|0.14(8.90s) 2.07|0.18(25.68s) 3.60|0.12(26.56s)
    rpADMMII 2.71|0.14(8.90s) 2.06|0.18(26.01s) 3.76|0.12(24.98s)
    Zach-pADMM 2.96|0.16(6.76s) 2.65|0.21(13.69s) 5.11|0.16(13.57s)
     | Show Table
    DownLoad: CSV

    Table 2.  Numerical results for the TV-$ L^1 $ optical flow estimates. In the table, we use $ s|l $ with $ s $ representing the average angular error (AAE) and $ l $ denoting the average endpoint error (EPE). The best results of AAE or EPE are underlined

    Average angular error|Average end point error
    Urban2 Grove2 Urban3 Venus Grove3
    pADMM 2.60|0.36 2.25|0.15 4.24|0.54 4.36|0.29 6.27|0.66
    rpADMMI 2.78|0.36 2.25|0.15 4.25|0.52 4.47|0.29 6.24|0.65
    rpADMMII 2.89|0.37 2.28|0.16 4.24|0.52 4.53|0.30 6.21|0.65
    Zach-pADMM 2.60|0.36 2.28|0.16 4.87|0.54 4.36|0.29 6.55|0.64
    Zach-O 3.06|0.38 2.31|0.16 6.63|0.71 5.25|0.35 6.60|0.72
     | Show Table
    DownLoad: CSV
  • [1] G. AubertR. Deriche and P. Kornprobst, Computing optical flow via variational techniques, SIAM J. Appl. Math., 60 (1999), 156-182.  doi: 10.1137/S0036139998340170.
    [2] F. Becker, S. Petra and C. Schnörr, Optical Flow, In: Scherzer O. (eds), Handbook of Mathematical Methods in Imaging, Springer, New York, NY, 2015, 1945-2004.
    [3] M. J. Black and P. Anandan, The robust estimation of multiple motions: Parametric and piecewise-smooth flow fields, Comp. Vision Image Underst., 63 (1996), 75-104.  doi: 10.1006/cviu.1996.0006.
    [4] M. J. Black and A. Rangarajan, The outlier process: Unifying line processes and robust statistics, 1994 Proceedings of IEEE CVPR, Seattle, WA, USA, (1994) 15-22. doi: 10.1109/CVPR.1994.323805.
    [5] S. Boyd, N. Parikh, E. Chu, B. Peleato and J. Eckstein, Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers, Found. Trends Mach. Learn., 3 2011. doi: 10.1561/9781601984616.
    [6] K. Bredies and H. Sun, Preconditioned Douglas-Rachford algorithms for TV and TGV regularized variational imaging problems, J. Math. Imaging Vis., 52 (2015), 317-344.  doi: 10.1007/s10851-015-0564-1.
    [7] K. Bredies and H. Sun, A proximal point analysis of the preconditioned alternating direction method of multipliers, J. Optim. Theory Appl., 173 (2017), 878-907.  doi: 10.1007/s10957-017-1112-5.
    [8] K. Bredies and H. Sun, Accelerated Douglas-Rachford methods for the solution of convex-concave saddle-point problems, arXiv eprints, arXiv: 1604.06282, 2016.
    [9] A. Chambolle, An algorithm for total variation minimization and applications, J. Math. Imaging and Vis., 20 (2004), 89-97.  doi: 10.1023/B:JMIV.0000011325.36760.1e.
    [10] A. Chambolle and T. Pock, A first-order primal-dual algorithm for convex problems with applications to imaging, J. Math. Imaging and Vis., 40 (2011), 120-145.  doi: 10.1007/s10851-010-0251-1.
    [11] A. Chambolle and T. Pock, On the ergodic convergence rates of a first-order primal-dual algorithm, Math. Program., 159 (2016), 253-287.  doi: 10.1007/s10107-015-0957-3.
    [12] C. ChenB. HeY. Ye and X. Yuan, The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent, Math. Program., 155 (2016), 57-79.  doi: 10.1007/s10107-014-0826-5.
    [13] W. Deng and W. Yin, On the global and linear convergence of the generalized alternating direction method of multipliers, J. Sci. Comput., 66 (2016), 889-916.  doi: 10.1007/s10915-015-0048-x.
    [14] J. Douglas and H. H. Rachford, On the numerical solution of heat conduction problems in two and three space variables, Trans. Amer. Math. Soc., 82 (1956), 421-439.  doi: 10.1090/S0002-9947-1956-0084194-4.
    [15] J. Eckstein and D. P. Bertsekas, On the Douglas–Rachford splitting method and the proximal algorithm for maximal monotone operators, Math. Program., 55 (1992), 293-318.  doi: 10.1007/BF01581204.
    [16] D. Fleet and Y. Weiss, Optical Flow Estimation, In Paragios, Nikos; Chen, Yunmei; Faugeras, Olivier D. (eds.), Handbook of Mathematical Models in Computer Vision, Springer, (2006) 237-257.
    [17] D. FortunP. Bouthemy and C. Kervrann, Optical flow modeling and computation: A survey, Computer Vision and Image Understanding, 134 (2015), 1-21.  doi: 10.1016/j.cviu.2015.02.008.
    [18] D. FortunM. StorathD. RickertA. Weinmann and M. Unser, Fast piecewise-affine motion estimation without segmentation, IEEE Transactions on Image Processing, 27 (2018), 5612-5624.  doi: 10.1109/TIP.2018.2856399.
    [19] M. Fortin and R. Glowinski, On decomposition-coordination methods using an augmented Lagrangian, in: M. Fortin and R. Glowinski, eds., Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems, North-Holland, Amsterdam, 1983. doi: 10.1016/S0168-2024(08)70028-6.
    [20] D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., 2 (1976), 17-40.  doi: 10.1016/0898-1221(76)90003-1.
    [21] R. Glowinski and A. Marrocco, Sur l'approximation, par éléments finis d'ordre un, et la résolution, par pénalisation-dualité d'une classe de problèmes de Dirichlet non linéaires, Revue Française d'Automatique Informatique Recherche Opérationnelle, Analyse Numérique, 9 (1975), 41-76. doi: 10.1051/m2an/197509R200411.
    [22] B. K. P. Horn and B. G. Schunck, Determining optical flow, Artificial Intelligence, 17 (1981), 185-203.  doi: 10.1016/0004-3702(81)90024-2.
    [23] K. Ito and K. Kunisch, Lagrange Multiplier Approach to Variational Problems and Applications, Advances in Design and Control, 15, Philadelphia, SIAM, 2008. doi: 10.1137/1.9780898718614.
    [24] P. Krähenbühl and V. Koltun, Efficient nonlocal regularization for optical flow, In: Fitzgibbon A., Lazebnik S., Perona P., Sato Y., Schmid C. (eds), Computer Vision - ECCV 2012, Lecture Notes in Computer Science, vol 7572, Springer, Berlin, Heidelberg, 2012.
    [25] M. LiD. Sun and K.-C. Toh, A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization, SIAM J. Optim., 26 (2016), 922-950.  doi: 10.1137/140999025.
    [26] J. Nocedal and S. J. Wright, Numerical Optimization, Springer, New York, NY, second edition, 2006
    [27] N. PapenbergA. BruhnT. BroxS. Didas and J. Weickert, Highly accurate optic flow computation with theoretically justified warping, IJCV, 67 (2006), 141-158.  doi: 10.1007/s11263-005-3960-y.
    [28] J. S. PérezE. Meinhardt-Llopis and G. Facciolo, TV-L1 optical flow estimation, Image Processing On Line, 3 (2013), 137-150.  doi: 10.5201/ipol.2013.26.
    [29] R. Ranftl, K. Bredies and T. Pock, Non-local total generalized variation for optical flow estimation, In: Fleet D., Pajdla T., Schiele B., Tuytelaars T. (eds), Computer Vision - ECCV 2014, Lecture Notes in Computer Science, vol 8689. Springer, Cham, 2004. doi: 10.1007/978-3-319-10590-1_29.
    [30] D. Shulman and J.-Y. Hervé, Regularization of discontinuous flow fields, In: Proceedings Workshop on Visual Motion, 1989, 81-86. doi: 10.1109/WVM.1989.47097.
    [31] D. Sun, S. Roth and M. J. Black, Secrets of optical flow estimation and their principles, In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2010, 2432-2439. doi: 10.1109/CVPR.2010.5539939.
    [32] H. Sun, Analysis of fully preconditioned alternating direction method of multipliers with relaxation in Hilbert spaces, J. Optim. Theory Appl., 183 (2019), 199-229.  doi: 10.1007/s10957-019-01535-6.
    [33] H. SunX.-C. Tai and J. Yuan, Efficient and convergent preconditioned ADMM for the Potts models, SIAM J. Sci. Comput., 43 (2021), B455-B478.  doi: 10.1137/20M1343956.
    [34] R. Szeliski, Computer Vision: Algorithms and Applications, Springer-Verlag, Berlin, Heidelberg, 2010. doi: 10.1007/978-3-030-34372-9.
    [35] V. Vishnevskiy, T. Gass, G. Székely and O. Goksel, Total variation regularization of displacements in parametric image registration, In: Yoshida H., Näppi J., Saini S. (eds), Abdominal Imaging. Computational and Clinical Applications. ABD-MICCAI 2014. Lecture Notes in Computer Science, vol 8676. Springer, Cham, 2014. doi: 10.1007/978-3-319-13692-9_20.
    [36] V. VishnevskiyT. GassG. SzekelyC. Tanner and O. Goksel, Isotropic total variation regularization of displacements in parametric image registration, IEEE Transactions on Medical Imaging, 36 (2017), 385-395.  doi: 10.1109/TMI.2016.2610583.
    [37] A. Wedel, T. Pock, C. Zach, H. Bischof and D. Cremers, An improved algorithm for TV-L1 optical flow, In: Cremers D., Rosenhahn B., Yuille A.L., Schmidt F.R. (eds), Statistical and Geometrical Approaches to Visual Motion Analysis, Lecture Notes in Computer Science, vol 5604. Springer, Berlin, Heidelberg, 2009.
    [38] M. Werlberger, T. Pock and H. Bischof, Motion estimation with non-local total variation regularization, 2010 IEEE Computer Society Conference on CVPR, San Francisco, CA, 2010, 2464-2471. doi: 10.1109/CVPR.2010.5539945.
    [39] C. Zach, T. Pock and H. Bischof, A Duality Based Approach for Realtime TV-L1 Optical Flow, In: F.A., Hamprecht, C. Schnörr, B. Jähne, (eds) Pattern Recognition. DAGM 2007. Lecture Notes in Computer Science, vol 4713. Springer, Berlin, Heidelberg.
    [40] N. Zon and N. Kiryati, An alternating direction method for optical flow estimation with lp regularization, 2016 IEEE International Conference on the Science of Electrical Engineering (ICSEE), Eilat, 2016, 1-5. doi: 10.1109/ICSEE.2016.7806158.
  • 加载中




Article Metrics

HTML views(202) PDF downloads(129) Cited by(0)

Access History

Other Articles By Authors



    DownLoad:  Full-Size Img  PowerPoint