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

 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.

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, doi: 10.3934/dcdss.2020347
##### References:
  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  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  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  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  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  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  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  B. Horn and B. Schunck, Determining optical flow, Artificial Intelligence, 17 (1981), 185-203.  doi: 10.1016/0004-3702(81)90024-2. Google Scholar  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  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  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  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  J. Sethian, Level Set Methods and Fast Marching Methods, Cambridge Monographs on Applied and Computational Mathematics, 3, Cambridge University Press, Cambridge, 1999. Google Scholar  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:
  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  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  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  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  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  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  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  B. Horn and B. Schunck, Determining optical flow, Artificial Intelligence, 17 (1981), 185-203.  doi: 10.1016/0004-3702(81)90024-2. Google Scholar  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  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  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  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  J. Sethian, Level Set Methods and Fast Marching Methods, Cambridge Monographs on Applied and Computational Mathematics, 3, Cambridge University Press, Cambridge, 1999. Google Scholar  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 The example with exact solution: the function $F$ (left), the function $G$ (middle), and the deformation $-\vec{D}^{ex}$ (right) 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) The images of lungs scan: the source image $F$ (left), the target image $G$ (middle), the difference image $|G-F|$ (right) 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) The plot of deformation $\vec{D}$ for the example with the images of lungs 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
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
 $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
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
 $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
  Tetsuya Ishiwata, Takeshi Ohtsuka. Numerical analysis of an ODE and a level set methods for evolving spirals by crystalline eikonal-curvature flow. Discrete & Continuous Dynamical Systems - S, 2020  doi: 10.3934/dcdss.2020390  Yoshikazu Giga, Hiroyoshi Mitake, Hung V. Tran. Remarks on large time behavior of level-set mean curvature flow equations with driving and source terms. Discrete & Continuous Dynamical Systems - B, 2020, 25 (10) : 3983-3999. doi: 10.3934/dcdsb.2019228  Peter Frolkovič, Karol Mikula, Jozef Urbán. Distance function and extension in normal direction for implicitly defined interfaces. Discrete & Continuous Dynamical Systems - S, 2015, 8 (5) : 871-880. doi: 10.3934/dcdss.2015.8.871  Lukas F. Lang, Otmar Scherzer. Optical flow on evolving sphere-like surfaces. Inverse Problems & Imaging, 2017, 11 (2) : 305-338. doi: 10.3934/ipi.2017015  Thomas Schuster, Joachim Weickert. On the application of projection methods for computing optical flow fields. Inverse Problems & Imaging, 2007, 1 (4) : 673-690. doi: 10.3934/ipi.2007.1.673  Aniello Raffaele Patrone, Otmar Scherzer. On a spatial-temporal decomposition of optical flow. Inverse Problems & Imaging, 2017, 11 (4) : 761-781. doi: 10.3934/ipi.2017036  Abraão D. C. Nascimento, Leandro C. Rêgo, Raphaela L. B. A. Nascimento. Compound truncated Poisson normal distribution: Mathematical properties and Moment estimation. Inverse Problems & Imaging, 2019, 13 (4) : 787-803. doi: 10.3934/ipi.2019036  Tom Goldstein, Xavier Bresson, Stan Osher. Global minimization of Markov random fields with applications to optical flow. Inverse Problems & Imaging, 2012, 6 (4) : 623-644. doi: 10.3934/ipi.2012.6.623  Letizia Stefanelli, Ugo Locatelli. Kolmogorov's normal form for equations of motion with dissipative effects. Discrete & Continuous Dynamical Systems - B, 2012, 17 (7) : 2561-2593. doi: 10.3934/dcdsb.2012.17.2561  Andrei Fursikov. Stabilization of the simplest normal parabolic equation. Communications on Pure & Applied Analysis, 2014, 13 (5) : 1815-1854. doi: 10.3934/cpaa.2014.13.1815  Alexander Bobylev, Åsa Windfäll. Boltzmann equation and hydrodynamics at the Burnett level. Kinetic & Related Models, 2012, 5 (2) : 237-260. doi: 10.3934/krm.2012.5.237  Bin Dong, Aichi Chien, Yu Mao, Jian Ye, Fernando Vinuela, Stanley Osher. Level set based brain aneurysm capturing in 3D. Inverse Problems & Imaging, 2010, 4 (2) : 241-255. doi: 10.3934/ipi.2010.4.241  Andreas Widder. On the usefulness of set-membership estimation in the epidemiology of infectious diseases. Mathematical Biosciences & Engineering, 2018, 15 (1) : 141-152. doi: 10.3934/mbe.2018006  Yuan Li, Lei Yan, Lingbo Wang, Wei Hou. Estimation of normal distribution parameters and its application to carbonation depth of concrete girder bridges. Discrete & Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1091-1100. doi: 10.3934/dcdss.2019075  Wenqing Hu, Chris Junchi Li. A convergence analysis of the perturbed compositional gradient flow: Averaging principle and normal deviations. Discrete & Continuous Dynamical Systems - A, 2018, 38 (10) : 4951-4977. doi: 10.3934/dcds.2018216  Andrei Fursikov. The simplest semilinear parabolic equation of normal type. Mathematical Control & Related Fields, 2012, 2 (2) : 141-170. doi: 10.3934/mcrf.2012.2.141  Dario Bambusi, A. Carati, A. Ponno. The nonlinear Schrödinger equation as a resonant normal form. Discrete & Continuous Dynamical Systems - B, 2002, 2 (1) : 109-128. doi: 10.3934/dcdsb.2002.2.109  Alexandre M. Bayen, Hélène Frankowska, Jean-Patrick Lebacque, Benedetto Piccoli, H. Michael Zhang. Special issue on Mathematics of Traffic Flow Modeling, Estimation and Control. Networks & Heterogeneous Media, 2013, 8 (3) : i-ii. doi: 10.3934/nhm.2013.8.3i  Bertram Düring, Ansgar Jüngel, Lara Trussardi. A kinetic equation for economic value estimation with irrationality and herding. Kinetic & Related Models, 2017, 10 (1) : 239-261. doi: 10.3934/krm.2017010  Yutian Lei, Congming Li, Chao Ma. Decay estimation for positive solutions of a $\gamma$-Laplace equation. Discrete & Continuous Dynamical Systems - A, 2011, 30 (2) : 547-558. doi: 10.3934/dcds.2011.30.547

2019 Impact Factor: 1.233