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

Peter Frolkovič; Viera Kleinová

doi:10.3934/dcdss.2020347

Article Contents

2021, Volume 14, Issue 3: 851-863. Doi: 10.3934/dcdss.2020347

This issue Previous Article Traveling wave solution for a diffusive simple epidemic model with a free boundary Next Article Flux balanced approximation with least-squares gradient for diffusion equation on polyhedral mesh

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: November 30, 2018

Revised: November 30, 2019

Early access: May 2020

Published: March 2021

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

Abstract Full Text(HTML) Figure(7) / Table(2) Related Papers Cited by

Abstract

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:

Mathematics Subject Classification: Primary: 65D18, 65M25; Secondary: 35L60.

Citation:

Full Text(HTML)

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

Download: Full-size image 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)

Download: Full-size image 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)

Download: Full-size image PowerPoint slide

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

Download: Full-size image 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)

Download: Full-size image PowerPoint slide

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

Download: Full-size image 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

Download: Full-size image 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

| Show Table

DownLoad: CSV

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

| Show Table

DownLoad: CSV

Related Papers

Cited by

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.