Skip to main content
Springer Nature Link
Log in

Composite finite elements for 3D image based computing

  • Regular article
  • Published:
Save article
View saved research
Computing and Visualization in Science

Abstract

We present an algorithmical concept for modeling and simulation with partial differential equations (PDEs) in image based computing where the computational geometry is defined through previously segmented image data. Such problems occur in applications from biology and medicine where the underlying image data has been acquired through, e.g. computed tomography (CT), magnetic resonance imaging (MRI) or electron microscopy (EM). Based on a level-set description of the computational domain, our approach is capable of automatically providing suitable composite finite element functions that resolve the complicated shapes in the medical/biological data set. It is efficient in the sense that the traversal of the grid (and thus assembling matrices for finite element computations) inherits the efficiency of uniform grids away from complicated structures. The method’s efficiency heavily depends on precomputed lookup tables in the vicinity of the domain boundary or interface. A suitable multigrid method is used for an efficient solution of the systems of equations resulting from the composite finite element discretization. The paper focuses on both algorithmical and implementational details. Scalar and vector valued model problems as well as real applications underline the usability of our approach.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  1. Adams, L., Li, Z.: The immersed interface/multigrid methods for interface problems. SIAM J. Sci. Comput. 24(2), 463–479 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  2. Ambrosio, L., Tortorelli, V.M.: On the approximation of free discontinuity problems. Boll. dell’Unione Matematica Ital. B 6(7), 105–123 (1992)

    MATH  MathSciNet  Google Scholar 

  3. Babuška, I., Melenk, J.: The partition of unity method. Int. J. Numer. Methods Eng. 40, 727–758 (1997)

    Article  MATH  Google Scholar 

  4. Belytschko, T., Moës, N., Usui, S., Parimi, C.: Arbitrary discontinuities in finite elements. Int. J. Numer. Methods Eng. 50(4), 993–1013 (2001)

    Article  MATH  Google Scholar 

  5. Beyer, R.P., LeVeque, R.J.: Analysis of a one-dimensional model for the immersed boundary method. SIAM J. Numer. Anal. 29(2), 332–364 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  6. Bornemann, F., Rasch, C.: Finite-element discretization of static Hamilton–Jacobi equations based on a local variation principle. Comput. Vis. Sci. 9(2), 57–69 (2004) arXiv:math.NA/0403517

    Google Scholar 

  7. Calhoun, D.: A Cartesian grid method for solving the two-dimensional streamfunction-vorticity equations in irregular regions. J. Comput. Phys. 176, 231–275 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  8. Calhoun, D., LeVeque, R.J.: A Cartesian grid finite-volume method for the advection-diffusion equation in irregular geometries. J. Comput. Phys. 157, 143–180 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  9. Caselles, V., Catté, F., Coll, T., Dibos, F.: A geometric model for active contours in image processing. Numerische Mathematik 66, 1–31 (1993)

    Article  MATH  MathSciNet  Google Scholar 

  10. Caselles, V., Kimmel, R., Sapiro, G.: Geodesic active contours. Int. J. Comput. Vis. 22(1), 61–79 (1997)

    Article  MATH  Google Scholar 

  11. Chan, T., Vese, L.: A level set algorithm for minimizing the Mumford–Shah functional in image processing. In: Proceedings of the 1st IEEE Workshop on Variational and Level Set Methods in Computer Vision, pp. 161–168 (2001)

  12. Cheng, S.-W., Dey, T.K., Edelsbrunner, H., Facello, M.A., Teng, S.-H.: Sliver exudation. J. ACM 47(5), 883–904 (2000)

    Article  MathSciNet  Google Scholar 

  13. Ciarlet, P.G.: The finite element method for elliptic problems. Number 40 in Classics in applied mathematics. SIAM (2002)

  14. Cremers, D., Schnörr, C., Weickert, J.: Diffusion-snakes: combining statistical shape knowledge and image information in a variational framework. IEEE Workshop on Variational and Levelset Methods, pp. 137–144 (2001)

  15. Deuflhard, P., Weiser, M., Seebaß, M.: A new nonlinear elliptic multilevel FEM applied to regional hyperthermia. Comput. Vis. Sci. 3(3), 115–120 (2000)

    Article  MATH  Google Scholar 

  16. Droske, M., Preusser, T., Rumpf, M.: A multilevel segmentation method. In: Proceedings of Vision, Modeling and Visualization (VMV), pp. 327–336. Saarbrücken, Germany (2000)

  17. Frauböse, N., Sauter, S.: Composite finite elements and multi-grid. Part I: Convergence theory in 1-d. In: Proceedings of the 17th GAMM-Seminar Leipzig on Construction of Grid Generation Algorithms, pp. 69–86 (2001)

  18. Goméz-Benito, M., García-Aznar, J., Doblaré, M.: Finite element prediction of proximal femoral fracture patterns under different loads. J. Biomech. Eng. 127(1), 9–14 (2005)

    Article  Google Scholar 

  19. Hackbusch, W.: Multi-Grid Methods and Applications. Springer Series in Computational Mathematics, vol. 4. Springer, Heidelberg (1985)

  20. Hackbusch, W., Sauter, S.: Composite finite elements for the approximation of PDEs on domains with complicated micro-structures. Numerische Mathematik 75, 447–472 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  21. Hahn, H.K., Lentschig, M.G., Deimling, M., Terwey, B., Peitgen, H.-O.: MRI-based volumetry of intra- and extracerebral liquor spaces. In: CARS, pp. 401–407 (2001)

  22. Höllig, K., Reif, U., Wipper, J.: Weighted extended B-spline approximation of Dirichlet problems. SIAM J. Numer. Anal. 39(2), 442–462 (2001)

    Article  MATH  MathSciNet  Google Scholar 

  23. Kass, M., Witkin, A., Terzopoulos, D.: Snakes: active contour models. Int. J. Comput. Vis. 1, 321–331 (1988)

    Article  Google Scholar 

  24. Kornhuber, R., Krause, R., Sander, O., Deuflhard, P., Ertel, S.: A monotone multigrid solver for two body contact problems in biomechanics. Comput. Vis. Sci. 11(1), 3–15 (2008)

    Google Scholar 

  25. Kröger, T., Altrogge, I., Preusser, T., et al.: Numerical simulation of radio frequency ablation with state dependent material parameters in three space dimensions. In: MICCAI 2006. Lecture Notes in Computer Science, vol. 4191, pp. 380–388. Springer, Heidelberg (2006)

  26. Kuhnigk, J.M., Dicken, V., Bornemann, L., Bakai, A., Wormanns, D., Krass, S., Peitgen, H.O.: Morphological segmentation and partial volume analysis for volumetry of solid pulmonary lesions in thoracic CT scans. IEEE Trans. Med. Imaging 25(4), 417–434 (2006)

    Article  Google Scholar 

  27. LeVeque, R.J., Li, Z.L.: The immersed interface method for elliptic equations with discontinuous coefficients and singular sources. SIAM J. Numer. Anal. 31(4), 1019–1044 (1994)

    Article  MATH  MathSciNet  Google Scholar 

  28. Li, Z.: A fast iterative algorithm for elliptic interface problems. SIAM J. Numer. Anal. 35(1), 230–254 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  29. Li, Z.: The immersed interface method using a finite element formulation. Appl. Numer. Math. 27, 253–267 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  30. Li, Z., Lin, T., Wu, X.: New Cartesian grid methods for interface problems using the finite element formulation. Numerische Mathematik 1996(1), 61–98 (2003)

    Article  MathSciNet  Google Scholar 

  31. Lorensen, W.E., Cline, H.E.: Marching cube: a high resolution 3D surface construction algorithm. Comput. Graph. 21(4), 163–169 (1987)

    Google Scholar 

  32. Melenk, J.M., Babuška, I.: The partition of unity finite element method. Research Report 96-01, Eidgenössische Technische Hochschule Zürich, Seminar für angewandte Mathematik (1996)

  33. Müller, H., Wehle, M.: Visualization of implicit surfaces using adaptive tetrahedrizations. In: Proceedings of Scientific Visualization Conference (Dagstuhl ’97) (1997)

  34. Osher, S., Sethian, J.A.: Fronts propagating with curvature-dependent speed: algorithms based on Hamilton–Jacobi formulations. J. Comput. Phys. 79, 12–49 (1988)

    Article  MATH  MathSciNet  Google Scholar 

  35. Parvizian, J., Düster, A., Rank, E.: Finite cell method. Comput. Mech. 41(1), 121–133 (2007)

    Article  MathSciNet  Google Scholar 

  36. Preusser, T., Rumpf, M.: An adaptive finite element method for large scale image processing. J. Vis Commun. Image Representation 11, 183–195 (2000)

    Article  Google Scholar 

  37. Preusser, T., Rumpf, M., Sauter, S., Schwen, L.O., et al.: Three-dimensional composite finite elements for scalar problems with jumping coefficients. In preparation (2007)

  38. Preusser, T., Rumpf, M., Schwen, L.O.: Finite element simulation of bone microstructures. In: Proceedings of the 14th Finite Element Workshop. University of Ulm (2007, to appear)

  39. Rech, M., Sauter, S., Smolianski, A.: Two-scale composite finite element method for the Dirichlet problem on complicated domains. Numerische Mathematik 102, 681–708 (2006)

    Google Scholar 

  40. Russo, G., Smereka, P.: A remark on computing distance functions. J. Comput. Phys. 163(1), 51–67 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  41. Sauter, S.A., Warnke, R.: Composite finite elements for elliptic boundary value problems with discontinuous coefficients. Computing 77, 29–55 (2006)

    Article  MATH  MathSciNet  Google Scholar 

  42. Schenk, A., Prause, G., Peitgen, H.-O.: Efficient semiautomatic segmentation of 3D objects in medical images. In: Proceedings of MICCAI. Lecture Notes in Computer Science, vol. 1935, pp. 186–195. Springer, Heidelberg (2000)

  43. Schwen, L.O., et al.: Computing elastic deformation of vertebrae using composite finite elements. In preparation (2007)

  44. Segonne, F., Dale, A.M., Busa, E., Glessner, M., Salat, D., Hahn, H.K., Fischl, B.: A hybrid approach to the skull stripping problem in MRI. Neuroimage 22(3), 1060–1075 (2004)

    Article  Google Scholar 

  45. Sethian, J.A., Wiegmann, A.: Structural boundary design via level set and immersed interface methods. J. Comput. Phys. 163(2), 489–528 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  46. Stazi, F.L., Budyn, E., Chessa, J., Belytschko, T.: An extended finite element method with higher-order elements for curved cracks. Comput. Mech. 31, 38–48 (2003)

    Article  MATH  Google Scholar 

  47. Strang, G., Fix, G.J.: An Analysis of the Finite Element Method. Wellesley-Cambridge Press, Wellesley (1973)

    MATH  Google Scholar 

  48. Strouboulis, T., Copps, K., Babuška, I.: The generalized finite element method. Comput. Methods Appl. Mech. Eng. 190, 4081–4193 (2001)

    Article  MATH  Google Scholar 

  49. Teng, S.-H., Wong, C.W.: Unstructured mesh generation: theory, practice and applications. Int. J. Comput. Geometry Appl. 10(3), 227–266 (2000)

    Article  MATH  MathSciNet  Google Scholar 

  50. Wiegmann, A., Bube, K.P.: The immersed interface method for nonlinear differential equations with discontinuous coefficients and singular sources. SIAM J. Numer. Anal. 35(1), 177–200 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  51. Wittek, A., Kikinis, R., Warfield, S.K., Brain, M.K.: Shift computation using a fully nonlinear biomechanical model. In: Proceedings of MICCAI, LNCS, pp. 583–590. Springer, Heidelberg (2005)

  52. Xu, C., Prince, J.L.: Snakes, shapes, and gradient vector flow. IEEE Trans. Image Proces. 7(3), 359–369 (1998)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. INS, Institute for Numerical Simulation, University of Bonn, 53115, Bonn, Germany

    Florian Liehr, Martin Rumpf & Lars Ole Schwen

  2. CeVis, Center of Complex Systems and Visualization, University of Bremen, Universitätsallee 29, 28359, Bremen, Germany

    Tobias Preusser

  3. Institute for Mathematics, University of Zurich, 8057, Zurich, Switzerland

    Stefan Sauter

Authors
  1. Florian Liehr
    View author publications

    Search author on:PubMed Google Scholar

  2. Tobias Preusser
    View author publications

    Search author on:PubMed Google Scholar

  3. Martin Rumpf
    View author publications

    Search author on:PubMed Google Scholar

  4. Stefan Sauter
    View author publications

    Search author on:PubMed Google Scholar

  5. Lars Ole Schwen
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Tobias Preusser.

Additional information

Communicated by G. Wittum.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Liehr, F., Preusser, T., Rumpf, M. et al. Composite finite elements for 3D image based computing. Comput. Visual Sci. 12, 171–188 (2009). https://doi.org/10.1007/s00791-008-0093-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue date:

  • DOI: https://doi.org/10.1007/s00791-008-0093-1

Keywords

Profiles

  1. Lars Ole Schwen View author profile