The upwind scheme in formulas
Optional · supplementary note 3 of 9 for IP 11 · Image Segmentation II: Active Contours — Snakes and Level Sets. Nothing in the main text depends on it; citation numbers refer to the reference list at the bottom of this page.
Navigate: this page and this track: Navigate: this page and this track
The level-set equation is discretized on the pixel grid as follows.
Let be the value at pixel after steps of size , with grid spacing . The one-sided differences
(and likewise) are combined so that information is always taken from the side the front is coming from. This is the upwind scheme of [5]:
If contains a curvature term , that part behaves like diffusion and is discretized with central differences; it adds a stricter, second-order limit of roughly in 2D. In practice you compute from the current maximum speed at each step.
References
- R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 11. publisher page
- M. Kass, A. Witkin, and D. Terzopoulos, “Snakes: Active contour models,” International Journal of Computer Vision, vol. 1, no. 4, pp. 321–331, 1988. doi:10.1007/BF00133570
- C. Xu and J. L. Prince, “Snakes, shapes, and gradient vector flow,” IEEE Transactions on Image Processing, vol. 7, no. 3, pp. 359–369, 1998; see also C. Xu, A. Yezzi Jr., and J. L. Prince, “On the relationship between parametric and geometric active contours,” Proc. 34th Asilomar Conf. on Signals, Systems, and Computers, 2000. GVF project page with both papers
- L. D. Cohen, “On active contour models and balloons,” CVGIP: Image Understanding, vol. 53, no. 2, pp. 211–218, 1991. author PDF
- S. Osher and J. A. Sethian, “Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton–Jacobi formulations,” Journal of Computational Physics, vol. 79, pp. 12–49, 1988. doi:10.1016/0021-9991(88)90002-2
- V. Caselles, R. Kimmel, and G. Sapiro, “Geodesic active contours,” International Journal of Computer Vision, vol. 22, no. 1, pp. 61–79, 1997. PDF
- D. Mumford and J. Shah, “Optimal approximations by piecewise smooth functions and associated variational problems,” Communications on Pure and Applied Mathematics, vol. 42, no. 5, pp. 577–685, 1989. doi:10.1002/cpa.3160420503
- T. F. Chan and L. A. Vese, “Active contours without edges,” IEEE Transactions on Image Processing, vol. 10, no. 2, pp. 266–277, 2001. doi:10.1109/83.902291
- D. Adalsteinsson and J. A. Sethian, “A fast level set method for propagating interfaces,” Journal of Computational Physics, vol. 118, pp. 269–277, 1995. summary page
- C. Li, C. Xu, C. Gui, and M. D. Fox, “Distance regularized level set evolution and its application to image segmentation,” IEEE Transactions on Image Processing, vol. 19, no. 12, pp. 3243–3254, 2010. doi:10.1109/TIP.2010.2069690
- P. Márquez-Neila, L. Baumela, and L. Álvarez, “A morphological approach to curvature-based evolution of curves and surfaces,” IEEE Transactions on Pattern Analysis and Machine Intelligence, 2014. doi:10.1109/TPAMI.2013.106
- scikit-image developers, “skimage.segmentation” API reference (
active_contour,chan_vese,morphological_chan_vese,morphological_geodesic_active_contour). docs - T. McInerney and D. Terzopoulos, “Deformable models in medical image analysis: A survey,” Medical Image Analysis, vol. 1, no. 2, 1996. author PDF
- D. Cremers, M. Rousson, and R. Deriche, “A review of statistical approaches to level set segmentation: Integrating color, texture, motion and shape,” International Journal of Computer Vision, vol. 72, no. 2, pp. 195–215, 2007. doi:10.1007/s11263-006-8711-1
- Y. Chen, P. Ge, G. Wang, and H. Chen, “An overview of intelligent image segmentation using active contour models,” Intelligence & Robotics, vol. 3, no. 1, pp. 23–55, 2023. open access
- S. Bohlender, I. Oksuz, and A. Mukhopadhyay, “A survey on shape-constraint deep learning for medical image segmentation,” IEEE Reviews in Biomedical Engineering, vol. 16, pp. 225–240, 2023. arXiv:2101.07721
- S. Peng, W. Jiang, H. Pi, X. Li, H. Bao, and X. Zhou, “Deep snake for real-time instance segmentation,” CVPR, 2020. arXiv:2001.01629
- X. Chen, B. M. Williams, S. R. Vallabhaneni, G. Czanner, R. Williams, and Y. Zheng, “Learning active contour models for medical image segmentation,” CVPR, 2019. CVF open access
- B. Kim and J. C. Ye, “Mumford–Shah loss functional for image segmentation with deep learning,” IEEE Transactions on Image Processing, vol. 29, pp. 1856–1866, 2020. doi · arXiv:1904.02872
- H. Kervadec, J. Bouchtiba, C. Desrosiers, E. Granger, J. Dolz, and I. Ben Ayed, “Boundary loss for highly unbalanced segmentation,” Medical Image Analysis, vol. 67, 2021 (first presented at MIDL 2019). arXiv:1812.07032