
-
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] |
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, 2021, 14 (3) : 893-907. doi: 10.3934/dcdss.2020390 |
[2] |
Wenbin Li, Jianliang Qian. Simultaneously recovering both domain and varying density in inverse gravimetry by efficient level-set methods. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020073 |
[3] |
Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070 |
[4] |
Chongyang Liu, Meijia Han, Zhaohua Gong, Kok Lay Teo. Robust parameter estimation for constrained time-delay systems with inexact measurements. Journal of Industrial & Management Optimization, 2021, 17 (1) : 317-337. doi: 10.3934/jimo.2019113 |
[5] |
Hua Zhong, Xiaolin Fan, Shuyu Sun. The effect of surface pattern property on the advancing motion of three-dimensional droplets. Discrete & Continuous Dynamical Systems - B, 2020 doi: 10.3934/dcdsb.2020366 |
[6] |
Dominique Chapelle, Philippe Moireau, Patrick Le Tallec. Robust filtering for joint state-parameter estimation in distributed mechanical systems. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 65-84. doi: 10.3934/dcds.2009.23.65 |
[7] |
Soonki Hong, Seonhee Lim. Martin boundary of brownian motion on gromov hyperbolic metric graphs. Discrete & Continuous Dynamical Systems - A, 2021 doi: 10.3934/dcds.2021014 |
[8] |
Karol Mikula, Jozef Urbán, Michal Kollár, Martin Ambroz, Ivan Jarolímek, Jozef Šibík, Mária Šibíková. An automated segmentation of NATURA 2000 habitats from Sentinel-2 optical data. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1017-1032. doi: 10.3934/dcdss.2020348 |
[9] |
Shuxing Chen, Jianzhong Min, Yongqian Zhang. Weak shock solution in supersonic flow past a wedge. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 115-132. doi: 10.3934/dcds.2009.23.115 |
[10] |
Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020169 |
[11] |
Sumit Kumar Debnath, Pantelimon Stǎnicǎ, Nibedita Kundu, Tanmay Choudhury. Secure and efficient multiparty private set intersection cardinality. Advances in Mathematics of Communications, 2021, 15 (2) : 365-386. doi: 10.3934/amc.2020071 |
[12] |
Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363 |
[13] |
Shin-Ichiro Ei, Hiroshi Ishii. The motion of weakly interacting localized patterns for reaction-diffusion systems with nonlocal effect. Discrete & Continuous Dynamical Systems - B, 2021, 26 (1) : 173-190. doi: 10.3934/dcdsb.2020329 |
[14] |
Caterina Balzotti, Simone Göttlich. A two-dimensional multi-class traffic flow model. Networks & Heterogeneous Media, 2020 doi: 10.3934/nhm.2020034 |
[15] |
Shuang Liu, Yuan Lou. A functional approach towards eigenvalue problems associated with incompressible flow. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 3715-3736. doi: 10.3934/dcds.2020028 |
[16] |
Pablo D. Carrasco, Túlio Vales. A symmetric Random Walk defined by the time-one map of a geodesic flow. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020390 |
[17] |
Joan Carles Tatjer, Arturo Vieiro. Dynamics of the QR-flow for upper Hessenberg real matrices. Discrete & Continuous Dynamical Systems - B, 2021, 26 (3) : 1359-1403. doi: 10.3934/dcdsb.2020166 |
[18] |
Petr Pauš, Shigetoshi Yazaki. Segmentation of color images using mean curvature flow and parametric curves. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1123-1132. doi: 10.3934/dcdss.2020389 |
[19] |
Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102 |
[20] |
Masaru Hamano, Satoshi Masaki. A sharp scattering threshold level for mass-subcritical nonlinear Schrödinger system. Discrete & Continuous Dynamical Systems - A, 2021, 41 (3) : 1415-1447. doi: 10.3934/dcds.2020323 |
2019 Impact Factor: 1.233
Tools
Metrics
Other articles
by authors
[Back to Top]