
-
Previous Article
Flux balanced approximation with least-squares gradient for diffusion equation on polyhedral mesh
- DCDS-S Home
- This Issue
-
Next Article
Traveling wave solution for a diffusive simple epidemic model with a free boundary
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 |
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.
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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[8] |
B. Horn and B. Schunck,
Determining optical flow, Artificial Intelligence, 17 (1981), 185-203.
doi: 10.1016/0004-3702(81)90024-2. |
[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. |
[10] |
R. J. LeVeque, Finite Volume Methods for Hyperbolic Problems, Cambridge Texts in Applied
Mathematics, Cambridge University Press, Cambridge, 2002.
doi: 10.1017/CBO9780511791253. |
[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. |
[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. |
[13] |
J. Sethian, Level Set Methods and Fast Marching Methods, Cambridge Monographs on Applied and Computational Mathematics, 3, Cambridge University Press, Cambridge, 1999. |
[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. |
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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[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. |
[8] |
B. Horn and B. Schunck,
Determining optical flow, Artificial Intelligence, 17 (1981), 185-203.
doi: 10.1016/0004-3702(81)90024-2. |
[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. |
[10] |
R. J. LeVeque, Finite Volume Methods for Hyperbolic Problems, Cambridge Texts in Applied
Mathematics, Cambridge University Press, Cambridge, 2002.
doi: 10.1017/CBO9780511791253. |
[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. |
[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. |
[13] |
J. Sethian, Level Set Methods and Fast Marching Methods, Cambridge Monographs on Applied and Computational Mathematics, 3, Cambridge University Press, Cambridge, 1999. |
[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. |







EOC | 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 |
EOC | 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 |
EOC | 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 |
EOC | 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] |
Shu-Yu Hsu. Existence and properties of ancient solutions of the Yamabe flow. Discrete & Continuous Dynamical Systems - A, 2018, 38 (1) : 91-129. doi: 10.3934/dcds.2018005 |
[2] |
Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355 |
[3] |
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 - A, 2019, 39 (12) : 7031-7056. doi: 10.3934/dcds.2019243 |
[4] |
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 |
[5] |
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 |
[6] |
Feng Luo. A combinatorial curvature flow for compact 3-manifolds with boundary. Electronic Research Announcements, 2005, 11: 12-20. |
[7] |
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 |
[8] |
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 |
[9] |
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 |
[10] |
Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437 |
[11] |
Simone Cacace, Maurizio Falcone. A dynamic domain decomposition for the eikonal-diffusion equation. Discrete & Continuous Dynamical Systems - S, 2016, 9 (1) : 109-123. doi: 10.3934/dcdss.2016.9.109 |
[12] |
Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems - A, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25 |
[13] |
Jumpei Inoue, Kousuke Kuto. On the unboundedness of the ratio of species and resources for the diffusive logistic equation. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2441-2450. doi: 10.3934/dcdsb.2020186 |
[14] |
Wentao Huang, Jianlin Xiang. Soliton solutions for a quasilinear Schrödinger equation with critical exponent. Communications on Pure & Applied Analysis, 2016, 15 (4) : 1309-1333. doi: 10.3934/cpaa.2016.15.1309 |
[15] |
Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258 |
[16] |
Thierry Cazenave, Ivan Naumkin. Local smooth solutions of the nonlinear Klein-gordon equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1649-1672. doi: 10.3934/dcdss.2020448 |
[17] |
Jiaquan Liu, Xiangqing Liu, Zhi-Qiang Wang. Sign-changing solutions for a parameter-dependent quasilinear equation. Discrete & Continuous Dynamical Systems - S, 2021, 14 (5) : 1779-1799. doi: 10.3934/dcdss.2020454 |
[18] |
Murat Uzunca, Ayşe Sarıaydın-Filibelioǧlu. Adaptive discontinuous galerkin finite elements for advective Allen-Cahn equation. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 269-281. doi: 10.3934/naco.2020025 |
[19] |
Amit Goswami, Sushila Rathore, Jagdev Singh, Devendra Kumar. Analytical study of fractional nonlinear Schrödinger equation with harmonic oscillator. Discrete & Continuous Dynamical Systems - S, 2021 doi: 10.3934/dcdss.2021021 |
[20] |
Nhu N. Nguyen, George Yin. Stochastic partial differential equation models for spatially dependent predator-prey equations. Discrete & Continuous Dynamical Systems - B, 2020, 25 (1) : 117-139. doi: 10.3934/dcdsb.2019175 |
2019 Impact Factor: 1.233
Tools
Metrics
Other articles
by authors
[Back to Top]