Skip to main content
SpringerLink
Log in

A Moving Grid Framework for Geometric Deformable Models

  • Published:
International Journal of Computer Vision Aims and scope Submit manuscript

Abstract

Geometric deformable models based on the level set method have become very popular in the last decade. To overcome an inherent limitation in accuracy while maintaining computational efficiency, adaptive grid techniques using local grid refinement have been developed for use with these models. This strategy, however, requires a very complex data structure, yields large numbers of contour points, and is inconsistent with the implementation of topology-preserving geometric deformable models (TGDMs). In this paper, we investigate the use of an alternative adaptive grid technique called the moving grid method with geometric deformable models. In addition to the development of a consistent moving grid geometric deformable model framework, our main contributions include the introduction of a new grid nondegeneracy constraint, the design of a new grid adaptation criterion, and the development of novel numerical methods and an efficient implementation scheme. The overall method is simpler to implement than using grid refinement, requiring no large, complex, hierarchical data structures. It also offers an extra benefit of automatically reducing the number of contour vertices in the final results. After presenting the algorithm, we demonstrate its performance using both simulated and real images.

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

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Adalsteinsson, D., & Sethian, J. A. (1995). A fast level set method for propagating interfaces. Journal of Computational Physics, 118, 269–277.

    Article  MATH  MathSciNet  Google Scholar 

  • Bochev, P., Liao, G., & dela Pena, G. (1996). Analysis and computation of adaptive moving grids by deformation. Numerical Methods for Partial Differential Equations, 12, 489–506.

    Article  MATH  MathSciNet  Google Scholar 

  • Cao, W., Huang, W., & Russell, R. D. (2002). A moving mesh method based on the geometric conservation law. SIAM Journal on Scientific Computing, 24, 118–142.

    Article  MATH  MathSciNet  Google Scholar 

  • Caselles, V., Catte, F., Coll, T., & Dibos, F. (1993). A geometric model for active contours in image processing. Numerische Mathematik, 66, 1–31.

    Article  MATH  MathSciNet  Google Scholar 

  • Caselles, V., Kimmel, R., & Sapiro, G. (1997). Geodesic active contours. International Journal of Computer Vision, 22, 61–79.

    Article  MATH  Google Scholar 

  • Cohen, L. D. (1991). On active contour models and balloons. CVGIP: Image Understanding, 53, 211–218.

    Article  MATH  Google Scholar 

  • Droske, M., Meyer, B., Schaller, C., & Rumpf, M. (2001). An adaptive level set method for medical image segmentation. In M. F. Insana & R. M. Leahy (Eds.), LNCS: Vol. 2082. Proc. IPMI 2001 (pp. 416–422). Berlin: Springer.

    Google Scholar 

  • Han, X., Xu, C., & Prince, J. L. (2003a). A 2D moving grid geometric deformable model. In Proc. of CVPR (CVPR’03), Madison, Wisconsin (pp. I:153–160). June 2003.

  • Han, X., Xu, C., & Prince, J. L. (2003b). Topology preserving geometric deformable models for brain reconstruction. In S. Osher & N. Paragios (Eds.), Geometric level set methods in imaging, vision and graphics. New York: Springer.

    Google Scholar 

  • Han, X., Xu, C., & Prince, J. L. (2003c). A topology preserving level set method for geometric deformable models. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25, 755–768.

    Article  Google Scholar 

  • Han, X., Pham, D., Tosun, D., Rettmann, M., Xu, C., & Prince, J. L. (2004). CRUISE: Cortical reconstruction using implicit surface evolution. NeuroImage, 23, 997–1012.

    Article  Google Scholar 

  • Han, X., Xu, C., & Prince, J. L. (2006). A moving grid framework for geometric deformable models (ECE technical report). Johns Hopkins University, Baltimore, MD. http://iacl.ece.jhu.edu/~xhan/MMGDM.pdf.

  • Ivanenko, S. A. (1999). Harmonic mappings. In J. F. Thompson & B. K. Soni (Eds.), Handbook of grid generation (pp. 81–43). Boca Raton: CRC Press.

    Google Scholar 

  • Kao, C. Y., Osher, S., & Tsai, Y. R. (2002). Fast sweeping methods for a class of static Hamilton-Jacobi equations (Technical Report UCLA-CAM-02-66). Institute for Pure and Applied Mathematics (IPAM), UCLA.

  • Karaçali, B., & Davatzikos, C. (2006). Simulation of tissue atrophy using a topology preserving transformation model. IEEE Transactions on Medical Imaging, 25, 649–652.

    Article  Google Scholar 

  • Kass, M., Witkin, A., & Terzopoulos, D. (1988). Snakes: Active contour models. International Journal of Computer Vision, 1, 312–333.

    Google Scholar 

  • Khoo, S., Wang, B., Lim, K., & Wang, M. (2007). An extended level set method for shape and topology optimization. Journal of Computational Physics, 221, 395–421.

    Article  MATH  MathSciNet  Google Scholar 

  • Knupp, P., & Steinberg, S. (1994). Fundamentals of grid generation. Boca Raton: CRC Press.

    MATH  Google Scholar 

  • Kong, T. Y., & Rosenfeld, A. (1989). Digital topology: introduction and survey. CVGIP: Image Understanding, 48, 357–393.

    Google Scholar 

  • Le Guyader, C., & Vese, L. A. (2008). Self-repelling snakes for topology-preserving segmentation models. IEEE Transactions on Image Processing, 17, 767–779.

    Article  Google Scholar 

  • Liao, G., & Xue, J. (2006). Moving meshes by the deformation method. Journal of Computational and Applied Mathematics, 83–92.

  • Liao, G., Pan, T., & Shu, J. (1994). Numerical grid generator based on Moser’s deformation method. Numerical Methods for Partial Differential Equations, 10, 21–31.

    Article  MATH  MathSciNet  Google Scholar 

  • Liao, G., de la Pena, G., & Liao, G. (1999). A deformation method for moving mesh generation. In Proc. 8th int. meshing roundtable, South Lake Tahoe, CA (pp. 155–162).

  • Liao, G., Liu, F., de la Pena, G., Peng, D., & Osher, S. (2000). Level-set-based deformation methods for adaptive grids. Journal of Computational Physics, 159, 103–122.

    Article  MATH  MathSciNet  Google Scholar 

  • Lorensen, W. E., & Cline, H. E. (1987). Marching cubes: A high-resolution 3D surface construction algorithm. ACM Computer Graphics, 21(4), 163–170.

    Article  Google Scholar 

  • Malladi, R., Sethian, J. A., & Vemuri, B. C. (1995). Shape modeling with front propagation: A level set approach. IEEE Transactions on PAMI, 17, 158–175.

    Google Scholar 

  • Milne, B. (1995). Adaptive level set methods interfaces. Ph.D. dissertation, Dept. of Math., UC Berkeley.

  • Oishi, T., Takamatsu, J., Zheng, B., Ishikawa, R., & Ikeuchi, K. (2008). 6-DOF pose estimation from single ultrasound image using 3D IP models. In Proc. IEEE comput. vision pattern recognit. workshop (pp. 1–8).

  • Osher, S., & Shu, C. (1989). Efficient implementation of essentially non-oscillatory shock-capturing schemes, II. Journal of Computational Physics, 83, 32–78.

    Article  MATH  MathSciNet  Google Scholar 

  • Peng, D., Merriman, B., Osher, S., Zhao, H., & Kang, M. (1999). A PDE-based fast local level set method. Journal of Computational Physics, 155, 410–438.

    Article  MATH  MathSciNet  Google Scholar 

  • Press, W. A., Teukolsky, S. A., Vetterling, W. T., & Flannery, B. P. (1995). Numerical recipes in C (2nd ed.). New York: Cambridge University Press.

    Google Scholar 

  • Ségonne, F. (2008). Active contours under topology control—genus preserving level sets. International Journal of Computer Vision, 79(2), 107–117.

    Google Scholar 

  • Sethian, J. A. (1999). Level set methods and fast marching methods (2nd ed.). Cambridge: Cambridge University Press.

    MATH  Google Scholar 

  • Sethian, J. A., & Vladimirsky, A. (2001). Ordered upwind methods for static Hamilton-Jacobi equations. Proceedings of National Academy of Sciences, 98(20), 11069–11074.

    Article  MATH  MathSciNet  Google Scholar 

  • Siddiqi, K., Lauziere, Y. B., Tannenbaum, A., & Zucker, S. W. (1998). Area and length minimizing flow for shape segmentation. IEEE Transactions on Image Processing, 7, 433–443.

    Article  Google Scholar 

  • Strang, G. (1986). Introduction to applied mathematics. Cambridge: Wellesley Cambridge Press.

    MATH  Google Scholar 

  • Sundaramoorthi, G., & Yezzi, A. (2007). Global regularizing flows with topology preservation for active contours and polygons. IEEE Transactions on Image Processing, 16, 803–812.

    Article  MathSciNet  Google Scholar 

  • Sussman, M., Almgren, A. S., Bell, J. B., Colella, P., Howell, L. H., & Welcome, M. L. (1999). An adaptive level set approach for incompressible two-phase flow. Journal of Computational Physics, 148, 81–124.

    Article  MATH  MathSciNet  Google Scholar 

  • Terzopoulos, D., & Vasilescu, M. (1991). Sampling and reconstruction with adaptive meshes. In Proc. CVPR’91, Lahaina, HI (pp. 70–75).

  • Tsai, Y. R., Cheng, L., Osher, S., & Zhao, H. (2001). Fast sweeping algorithms for a class of Hamilton-Jacobi equations (Technical Report UCLA-CAM-01-27). Institute for Pure and Applied Mathematics (IPAM), UCLA.

  • Ushakova, O. V. (2001). Conditions of nondegeneracy of three-dimensional cells. A formula of a volume of cells. SIAM Journal of Scientific Computation, 1274–1290.

  • Vasilescu, M., & Terzopoulos, D. (1992). Adaptive meshes and shells. In Proc. CVPR’92, Champaign, IL (pp. 829–832).

  • Xie, X., & Mirmehdi, M. (2007). Implicit active model using radial basis function interpolated level sets. In Proc. 17th British machine vision conf. (pp. 1040–1049).

  • Xu, C., & Prince, J. L. (1998). Snakes, shapes, and gradient vector flow. IEEE Transactions on Image Processing, 7(3), 359–369.

    Article  MATH  MathSciNet  Google Scholar 

  • Xu, C., Yezzi, A., & Prince, J. L. (2001). On the relationship between parametric and geometric active contours. In The 34th Asilomar conference on signals, systems, and computers, Pacific Grove, USA (pp. 483–489).

  • Xu, M., Thompson, P. M., & Toga, A. W. (2004). An adaptive level set segmentation on a triangulated mesh. IEEE Transactions on Medical Imaging, 23, 191–201.

    Article  Google Scholar 

  • Yezzi, A., Kichenassamy, S., Olver, P., & Tannenbaum, A. (1997). A geometric snake models for segmentation of medical imagery. IEEE Transactions on Medical Imaging, 16, 199–209.

    Article  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. CMS Software, Elekta Inc., St. Louis, MO, 63043, USA

    Xiao Han

  2. Siemens Corporate Research, Princeton, NJ, 08540, USA

    Chenyang Xu

  3. Center for Imaging Science, Department of Electrical and Computer Engineering, Johns Hopkins University, Baltimore, MD, 21218, USA

    Jerry L. Prince

Authors
  1. Xiao Han
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Chenyang Xu
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Jerry L. Prince
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jerry L. Prince.

Additional information

This work was supported in part by NSF/ERC Grant CISST#9731748 and by NIH/NINDS Grant R01NS37747.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Han, X., Xu, C. & Prince, J.L. A Moving Grid Framework for Geometric Deformable Models. Int J Comput Vis 84, 63–79 (2009). https://doi.org/10.1007/s11263-009-0231-3

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11263-009-0231-3

Keywords

Search

Navigation