American Institute of Mathematical Sciences

Advanced
March  2021, 14(3): 851-863. doi: 10.3934/dcdss.2020347

A new numerical method for level set motion in normal direction used in optical flow estimation

Peter Frolkovič and  Viera Kleinová

Faculty of Civil Engineering, Slovak University of Technology, Department of Mathematics and Descriptive Geometry, Radlinského 11,810 05 Bratislava, Slovak Republic

Received  December 2018 Revised  December 2019 Published  May 2020

Fund Project: Work supported by grants VEGA 1/0728/15, APVV-15-0522 and APVV-16-0431. The authors are grateful for a support of company Tatramed in Bratislava, Slovakia

We present a new numerical method for the solution of level set advection equation describing a motion in normal direction for which the speed is given by the sign function of the difference of two given functions. Taking one function as the initial condition, the solution evolves towards the second given function. One of possible applications is an optical flow estimation to find a deformation between two images in a video sequence. The new numerical method is based on a bilinear interpolation of discrete values as used for the representation of images. Under natural assumptions, it ensures a monotone decrease of the absolute difference between the numerical solution and the target function, and it handles properly the discontinuity in the speed due to the dependence on the sign function. To find the deformation between two functions (or images), the backward tracking of characteristics is used. Two numerical experiments are presented, one with an exact solution to show an experimental order of convergence and one based on two images of lungs to illustrate a possible application of the method for the optical flow estimation.

Keywords: Optical flow estimation, level set equation, motion in normal direction.
Mathematics Subject Classification: Primary: 65D18, 65M25; Secondary: 35L60.
Citation: Peter Frolkovič, Viera Kleinová. A new numerical method for level set motion in normal direction used in optical flow estimation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 851-863. doi: 10.3934/dcdss.2020347
References:
[1]

M. Bertalmío, G. Sapiro and G. Randall, Morphing active contours, IEEE Trans. PAMI, 22 (2000), 733-737.  doi: 10.1109/34.865191.  Google Scholar

[2]

A. Bruhn, J. Weickert and C. Schnörr, Lucas/Kanade meets Horn/Schunck: Combining local and global optic flow methods, Int. J. Comput. Vis., 61 (2005), 211-231.  doi: 10.1023/B:VISI.0000045324.43199.43.  Google Scholar

[3]

M. Burger, H. Dirks and C.-B. Schönlieb, A variational model for joint motion estimation and image reconstruction, SIAM J. Imaging Sci., 11 (2018), 94-128.  doi: 10.1137/16M1084183.  Google Scholar

[4]

P. Colella, Multidimensional upwind methods for hyperbolic conservation laws, J. Comput. Phys., 87 (1990), 171-200.  doi: 10.1016/0021-9991(90)90233-Q.  Google Scholar

[5]

V. Duay, N. Houhou and J.-P. Thiran, Atlas-based segmentation of medical images locally constrained by level sets, IEEE International Conference on Image Processing, Genova, Italy, 2005. doi: 10.1109/ICIP.2005.1530298.  Google Scholar

[6]

P. Frolkovič and K. Mikula, Semi-implicit second order schemes for numerical solution of level set advection equation on Cartesian grids, Appl. Math. Comput., 329 (2018), 129-142.  doi: 10.1016/j.amc.2018.01.065.  Google Scholar

[7]

F. Gibou, R. Fedkiw and S. Osher, A review of level-set methods and some recent applications, J. Comput. Phys., 353 (2018), 82-109.  doi: 10.1016/j.jcp.2017.10.006.  Google Scholar

[8]

B. Horn and B. Schunck, Determining optical flow, Artificial Intelligence, 17 (1981), 185-203.  doi: 10.1016/0004-3702(81)90024-2.  Google Scholar

[9]

C.-O. Lee, K. Jeon, Y. Ha and J. Hahn, A variational approach to blending based on warping for non-overlapped images, Comput. Vis. Image Und., 105 (2007), 112-120.  doi: 10.1016/j.cviu.2006.09.001.  Google Scholar

[10]

R. J. LeVeque, Finite Volume Methods for Hyperbolic Problems, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 2002. doi: 10.1017/CBO9780511791253.  Google Scholar

[11]

S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Applied Mathematical Sciences, 153, Springer-Verlag, New York, 2003. doi: 10.1007/b98879.  Google Scholar

[12]

E. Rouy and A. Tourin, A viscosity solutions approach to shape-from-shading, SIAM J. Numer. Anal., 29 (1992), 867-884.  doi: 10.1137/0729053.  Google Scholar

[13]

J. Sethian, Level Set Methods and Fast Marching Methods, Cambridge Monographs on Applied and Computational Mathematics, 3, Cambridge University Press, Cambridge, 1999.  Google Scholar

[14]

B. C. Vemuri, J. Ye, Y. Chen and C. M. Leonard, Image registration via level-set motion: Applications to atlas-based segmentation, Medical Image Anal., 7 (2003), 1-20.  doi: 10.1016/S1361-8415(02)00063-4.  Google Scholar

show all references

References:
[1]

M. Bertalmío, G. Sapiro and G. Randall, Morphing active contours, IEEE Trans. PAMI, 22 (2000), 733-737.  doi: 10.1109/34.865191.  Google Scholar

[2]

A. Bruhn, J. Weickert and C. Schnörr, Lucas/Kanade meets Horn/Schunck: Combining local and global optic flow methods, Int. J. Comput. Vis., 61 (2005), 211-231.  doi: 10.1023/B:VISI.0000045324.43199.43.  Google Scholar

[3]

M. Burger, H. Dirks and C.-B. Schönlieb, A variational model for joint motion estimation and image reconstruction, SIAM J. Imaging Sci., 11 (2018), 94-128.  doi: 10.1137/16M1084183.  Google Scholar

[4]

P. Colella, Multidimensional upwind methods for hyperbolic conservation laws, J. Comput. Phys., 87 (1990), 171-200.  doi: 10.1016/0021-9991(90)90233-Q.  Google Scholar

[5]

V. Duay, N. Houhou and J.-P. Thiran, Atlas-based segmentation of medical images locally constrained by level sets, IEEE International Conference on Image Processing, Genova, Italy, 2005. doi: 10.1109/ICIP.2005.1530298.  Google Scholar

[6]

P. Frolkovič and K. Mikula, Semi-implicit second order schemes for numerical solution of level set advection equation on Cartesian grids, Appl. Math. Comput., 329 (2018), 129-142.  doi: 10.1016/j.amc.2018.01.065.  Google Scholar

[7]

F. Gibou, R. Fedkiw and S. Osher, A review of level-set methods and some recent applications, J. Comput. Phys., 353 (2018), 82-109.  doi: 10.1016/j.jcp.2017.10.006.  Google Scholar

[8]

B. Horn and B. Schunck, Determining optical flow, Artificial Intelligence, 17 (1981), 185-203.  doi: 10.1016/0004-3702(81)90024-2.  Google Scholar

[9]

C.-O. Lee, K. Jeon, Y. Ha and J. Hahn, A variational approach to blending based on warping for non-overlapped images, Comput. Vis. Image Und., 105 (2007), 112-120.  doi: 10.1016/j.cviu.2006.09.001.  Google Scholar

[10]

R. J. LeVeque, Finite Volume Methods for Hyperbolic Problems, Cambridge Texts in Applied Mathematics, Cambridge University Press, Cambridge, 2002. doi: 10.1017/CBO9780511791253.  Google Scholar

[11]

S. Osher and R. Fedkiw, Level Set Methods and Dynamic Implicit Surfaces, Applied Mathematical Sciences, 153, Springer-Verlag, New York, 2003. doi: 10.1007/b98879.  Google Scholar

[12]

E. Rouy and A. Tourin, A viscosity solutions approach to shape-from-shading, SIAM J. Numer. Anal., 29 (1992), 867-884.  doi: 10.1137/0729053.  Google Scholar

[13]

J. Sethian, Level Set Methods and Fast Marching Methods, Cambridge Monographs on Applied and Computational Mathematics, 3, Cambridge University Press, Cambridge, 1999.  Google Scholar

[14]

B. C. Vemuri, J. Ye, Y. Chen and C. M. Leonard, Image registration via level-set motion: Applications to atlas-based segmentation, Medical Image Anal., 7 (2003), 1-20.  doi: 10.1016/S1361-8415(02)00063-4.  Google Scholar

Figure 1.  The example with exact solution: the function $ F $ (left), the function $ G $ (middle), and the deformation $ -\vec{D}^{ex} $ (right)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 2.  Comparison of the exact deformation $ \vec{D}^{ex} $ (the blue arrows) with the numerical one $ \vec{D} $ (the red arrows) for the discretization steps $ h = 0.1 $ (top left), $ h = 0.05 $ (top right), $ h = 0.025 $ (bottom left), and $ h = 0.0125 $ (bottom right)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 3.  The images of lungs scan: the source image $ F $ (left), the target image $ G $ (middle), the difference image $ |G-F| $ (right)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 4.  The plot and the table of the normalized norm $ e^n $ in (36)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 5.  The image given by the values $ F(x_{ij}-\vec{D}_{ij}) $ (left) and the difference image given by the values $ |G_{ij}-F(x_{ij}-\vec{D}_{ij})| $ (right)
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 6.  The plot of deformation $ \vec{D} $ for the example with the images of lungs
Figure Options

Download full-size image

Download as PowerPoint slide

Figure 7.  The plot of deformation $ \vec{D} $ for the example with the images of lungs. Only arrows in the points where $ |G_{ij}-F_{ij}| > E_{crit} $ are plotted
Figure Options

Download full-size image

Download as PowerPoint slide

Table 1.  The error norm (35) and the corresponding $ EOC $ for the example with exact solution
$ I $ $ N $ $ E_{RT} $ EOC $ E_{CTU} $ EOC
10 1 0.00703 - 0.00312 -
20 2 0.00401 0.81 0.00171 0.87
40 4 0.00235 0.77 0.000893 0.94
80 8 0.00160 0.55 0.000458 0.96
160 16 0.00281 -0.81 0.000232 0.98
Table Options

Download as excel

$ I $ $ N $ $ E_{RT} $ EOC $ E_{CTU} $ EOC
10 1 0.00703 - 0.00312 -
20 2 0.00401 0.81 0.00171 0.87
40 4 0.00235 0.77 0.000893 0.94
80 8 0.00160 0.55 0.000458 0.96
160 16 0.00281 -0.81 0.000232 0.98
Table 2.  The $ \text{L}_1 $-norms and the experimental rates of convergence for the example with exact solution
$ I $ $ N $ $ E_L $ EOC $ E_D $ EOC
10 1 0.003120 - 0.004433 -
20 2 0.001307 1.2556 0.002379 0.8985
40 4 0.000528 1.3075 0.001259 0.9175
80 8 0.000220 1.2667 0.000659 0.9339
160 16 0.000096 1.1947 0.000339 0.9590
Table Options

Download as excel

$ I $ $ N $ $ E_L $ EOC $ E_D $ EOC
10 1 0.003120 - 0.004433 -
20 2 0.001307 1.2556 0.002379 0.8985
40 4 0.000528 1.3075 0.001259 0.9175
80 8 0.000220 1.2667 0.000659 0.9339
160 16 0.000096 1.1947 0.000339 0.9590
[1]

Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, 2021, 15 (3) : 387-413. doi: 10.3934/ipi.2020073
[2]

Jicheng Liu, Meiling Zhao. Normal deviation of synchronization of stochastic coupled systems. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021079
[3]

Jie-Wen He, Chi-Chon Lei, Chen-Yang Shi, Seak-Weng Vong. An inexact alternating direction method of multipliers for a kind of nonlinear complementarity problems. Numerical Algebra, Control & Optimization, 2021, 11 (3) : 353-362. doi: 10.3934/naco.2020030
[4]

Annalisa Cesaroni, Valerio Pagliari. Convergence of nonlocal geometric flows to anisotropic mean curvature motion. Discrete & Continuous Dynamical Systems, 2021  doi: 10.3934/dcds.2021065
[5]

Soonki Hong, Seonhee Lim. Martin boundary of brownian motion on Gromov hyperbolic metric graphs. Discrete & Continuous Dynamical Systems, 2021, 41 (8) : 3725-3757. doi: 10.3934/dcds.2021014
[6]

Alexey Yulin, Alan Champneys. Snake-to-isola transition and moving solitons via symmetry-breaking in discrete optical cavities. Discrete & Continuous Dynamical Systems - S, 2011, 4 (5) : 1341-1357. doi: 10.3934/dcdss.2011.4.1341
[7]

Shu-Yu Hsu. Existence and properties of ancient solutions of the Yamabe flow. Discrete & Continuous Dynamical Systems, 2018, 38 (1) : 91-129. doi: 10.3934/dcds.2018005
[8]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355
[9]

Zhengchao Ji. Cylindrical estimates for mean curvature flow in hyperbolic spaces. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1199-1211. doi: 10.3934/cpaa.2021016
[10]

Guido De Philippis, Antonio De Rosa, Jonas Hirsch. The area blow up set for bounded mean curvature submanifolds with respect to elliptic surface energy functionals. Discrete & Continuous Dynamical Systems, 2019, 39 (12) : 7031-7056. doi: 10.3934/dcds.2019243
[11]

Ling-Bing He, Li Xu. On the compressible Navier-Stokes equations in the whole space: From non-isentropic flow to isentropic flow. Discrete & Continuous Dynamical Systems, 2021, 41 (7) : 3489-3530. doi: 10.3934/dcds.2021005
[12]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213
[13]

Feng Luo. A combinatorial curvature flow for compact 3-manifolds with boundary. Electronic Research Announcements, 2005, 11: 12-20.

[14]

Pablo D. Carrasco, Túlio Vales. A symmetric Random Walk defined by the time-one map of a geodesic flow. Discrete & Continuous Dynamical Systems, 2021, 41 (6) : 2891-2905. doi: 10.3934/dcds.2020390
[15]

Peter Benner, Jens Saak, M. Monir Uddin. Balancing based model reduction for structured index-2 unstable descriptor systems with application to flow control. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 1-20. doi: 10.3934/naco.2016.6.1
[16]

G. Deugoué, B. Jidjou Moghomye, T. Tachim Medjo. Approximation of a stochastic two-phase flow model by a splitting-up method. Communications on Pure & Applied Analysis, 2021, 20 (3) : 1135-1170. doi: 10.3934/cpaa.2021010
[17]

Haodong Chen, Hongchun Sun, Yiju Wang. A complementarity model and algorithm for direct multi-commodity flow supply chain network equilibrium problem. Journal of Industrial & Management Optimization, 2021, 17 (4) : 2217-2242. doi: 10.3934/jimo.2020066
[18]

Lifen Jia, Wei Dai. Uncertain spring vibration equation. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021073
[19]

Vladimir Georgiev, Sandra Lucente. Focusing nlkg equation with singular potential. Communications on Pure & Applied Analysis, 2018, 17 (4) : 1387-1406. doi: 10.3934/cpaa.2018068
[20]

Daoyin He, Ingo Witt, Huicheng Yin. On the strauss index of semilinear tricomi equation. Communications on Pure & Applied Analysis, 2020, 19 (10) : 4817-4838. doi: 10.3934/cpaa.2020213

2019 Impact Factor: 1.233

Tools

Metrics

  • PDF downloads (91)
  • HTML views (299)
  • Cited by (0)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences