Full search page →

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 ϕt+F∣∇ϕ∣=0\phi_t + F\lvert\nabla\phi\rvert = 0 is discretized on the pixel grid as follows.

Let ϕijn\phi^n_{ij} be the value at pixel (i,j)(i, j) after nn steps of size Δt\Delta t, with grid spacing Δx=1\Delta x = 1. The one-sided differences

Dij−x=ϕij−ϕi−1,j,Dij+x=ϕi+1,j−ϕijD^{-x}_{ij} = \phi_{ij} - \phi_{i-1,j}, \qquad D^{+x}_{ij} = \phi_{i+1,j} - \phi_{ij}

(and D±yD^{\pm y} likewise) are combined so that information is always taken from the side the front is coming from. This is the upwind scheme of [5]:

ϕijn+1=ϕijn−Δt [max⁡(Fij,0) ∇ij++min⁡(Fij,0) ∇ij−],\phi^{n+1}_{ij} = \phi^n_{ij} - \Delta t\,\Big[\max(F_{ij}, 0)\,\nabla^{+}_{ij} + \min(F_{ij}, 0)\,\nabla^{-}_{ij}\Big], ∇+=max⁡(D−x,0)2+min⁡(D+x,0)2+max⁡(D−y,0)2+min⁡(D+y,0)2,\nabla^{+} = \sqrt{\max(D^{-x}, 0)^2 + \min(D^{+x}, 0)^2 + \max(D^{-y}, 0)^2 + \min(D^{+y}, 0)^2}, ∇−=min⁡(D−x,0)2+max⁡(D+x,0)2+min⁡(D−y,0)2+max⁡(D+y,0)2.\nabla^{-} = \sqrt{\min(D^{-x}, 0)^2 + \max(D^{+x}, 0)^2 + \min(D^{-y}, 0)^2 + \max(D^{+y}, 0)^2}.

If FF contains a curvature term b κb\,\kappa, that part behaves like diffusion and is discretized with central differences; it adds a stricter, second-order limit of roughly Δt≤Δx2/(4b)\Delta t \le \Delta x^2 / (4b) in 2D. In practice you compute Δt\Delta t from the current maximum speed at each step.

References

  1. R. C. Gonzalez and R. E. Woods, Digital Image Processing, 4th ed., Pearson, 2018, Ch. 11. publisher page
  2. 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
  3. 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
  4. L. D. Cohen, “On active contour models and balloons,” CVGIP: Image Understanding, vol. 53, no. 2, pp. 211–218, 1991. author PDF
  5. 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
  6. V. Caselles, R. Kimmel, and G. Sapiro, “Geodesic active contours,” International Journal of Computer Vision, vol. 22, no. 1, pp. 61–79, 1997. PDF
  7. 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
  8. 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
  9. 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
  10. 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
  11. 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
  12. scikit-image developers, “skimage.segmentation” API reference (active_contour, chan_vese, morphological_chan_vese, morphological_geodesic_active_contour). docs
  13. T. McInerney and D. Terzopoulos, “Deformable models in medical image analysis: A survey,” Medical Image Analysis, vol. 1, no. 2, 1996. author PDF
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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