Minimal Paths and Deformable Models for Image Analysis
Chemins Minimaux et Modèles Déformables en Analyse d’Images
OPEN ACCESS
We present an overview of part of our work on minimal paths. Introduced first in order to find the global minimum of active contours' energy using Fast Marching [18], we have then used minimal paths for finding multiple contours for contour completion from points, curves or regions in 2D or 3D images. Some variations allow to decrease computation time, make easier initialization and centering a path in a tubular structure. Fast Marching is also an efficient way to solve balloon model evolution using level sets. We show applications like for road and vessel segmentation and for virtual endoscopy.
Résumé
Nous présentons une synthèse d'une partie de nos travaux sur les chemins minimaux. Introduits au départ pour trouver le minimum global de l'énergie pour les contours actifs à l'aide du Fast Marching [18], nous les avons utilisés par la suite pour la recherche de contours multiples pour compléter des points, des courbes ou des régions dans des images 2D et 3D. Plusieurs variantes permettent d'améliorer le temps de calcul, de simplifier l'initialisation ou de centrer le chemin dans une structure tubulaire. Le Fast Marching est aussi un moyen efficace de résoudre l'évolution d'un modèle de contour actif ballon par « level sets ». Nous montrons des applications notamment pour la segmentation de routes et vaisseaux et pour l'endoscopie virtuelle.
Minimal paths, active contours, deformable models, fast marching, Eikonal Equation, level sets, weighted distance, reconstruction, energy minimization, Perceptual grouping, salient curve detection, 2D and 3D medical images, aerial images.
Mots clés
Chemins minimaux, contours actifs, modèles déformables, fast marching, Equation Eikonale, Ensembles de niveaux, distance pondérée, minimisation d'énergie, Groupement perceptuel, imagerie médicale 2D et 3D, Imagerie aérienne.
[1] Andres Almensa and L.D. Cohen. Fingerprint image matching by minimization of a thin-plate energy using a two-step algorithm with auxiliary variables. In Proc. IEEE Workshop on Applications of Computer Vision (WACV’00), Palm Springs, California, December 2000.
[2] Pablo Arbelaez and Laurent D. Cohen. Minimal paths and image segmentation. Journal of Mathematical Imaging and Vision, 2003. To appear.
[3] E. Bardinet, Laurent D. Cohen, and N. Ayache. Tracking and motion analysis of the left ventricle with deformable superquadrics. Medical Image Analysis, 1(2):129-149, November 1996. Comes with a video in the CD version of the journal.
[4] E. Bardinet, Laurent D. Cohen, and N. Ayache. A parametric deformable model to fit unstructured 3D data. Computer Vision and Image Understanding, 71(1):39-54, July 1998.
[5] V. Caselles, F. Catté, T. Coll, and F. Dibos. A geometric model for active contours. Numerische Mathematik, 66:1-31, 1993.
[6] V. Caselles, R. Kimmel, and G. Sapiro. Geodesic active contours. International Journal of Computer Vision, 22(1):61-79, 1997.
[7] Isaac Cohen and Laurent D. Cohen. A hybrid hyperquadric model for 2-D and 3-D data fitting. Computer Vision and Image Understanding, 63(3):527-541, May 1996.
[8] Laurent D. Cohen. On active contour models and balloons. Computer Vision, Graphics, and Image Processing: Image Understanding, 53(2):211-218, March 1991.
[9] Laurent D. Cohen. Avoiding local minima for deformable curves in image analysis. In Curves and Surfaces with Applications in CAGD, pages 7784. A. Le Méhauté, C. Rabut, and L. L. Schumaker (eds.), 1997.
[10] Laurent D. Cohen. Modèles déformables. Conférence plénière invitée. In Actes de l’Ecole Thématique ISIS, pages 1-20, Marly le Roy, April 1997.
[11] Laurent D. Cohen. Multiple contour finding and perceptual grouping using minimal paths. In Proc. IEEE Workshop on Variational and Level Set Methods in Computer Vision, Vancouver, Canada, July 2001. IEEE.
[12] Laurent D. Cohen. Multiple contour finding and perceptual grouping using minimal paths. Journal of Mathematical Imaging and Vision, 14(3), 2001. CEREMADE TR 0101, Jan 2001.
[13] Laurent D. Cohen, Eric Bardinet, and Nicholas Ayache. Surface reconstruction using active contour models. In Proceedings SPIE 93 Conference on Geometric Methods in Computer Vision, Vol. 2031, pages 38-50, San Diego, CA, July 1993. INRIA TR 1824, December 1992.
[14] Laurent D. Cohen and Isaac Cohen. Finite element methods for active contour models and balloons for 2-D and 3-D images. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-15(11):1131-1147, November 1993.
[15] Laurent D. Cohen and Thomas Deschamps. Grouping connected components using minimal path techniques. In Proc. IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR’01), Kauai, Hawai, December 2001.
[16] Laurent D. Cohen and Thomas Deschamps. Multiple contour finding and perceptual grouping as a set of energy minimizing paths. In Springer, editor, Proc. Third International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR -2001), 2001.
[17] Laurent D. Cohen and R. Kimmel. Fast marching the global minimum of active contours. Conférence invitée à la session Partial Differential Equations. In IEEE International Conference on Image Processing (ICIP’96), pages I:473-476, Lausanne, Suisse, September 1996.
[18] Laurent D. Cohen and R. Kimmel. Global minimum for active contour models: A minimal path approach. International Journal of Computer Vision, 24(1):57-78, August 1997.
[19] T. Deschamps. Curve and Shape Extraction with Minimal Path and LevelSets techniques – Applications to 3D Medical Imaging. PhD thesis, Université Paris-IX Dauphine, Paris, December 2001.
[20] T. Deschamps and L.D. Cohen. Minimal paths in 3D images and application to virtual endoscopy. In Proc. sixth European Conference on Computer Vision (ECCV’00), Dublin, Ireland, 26th June – 1st July 2000.
[21] T. Deschamps and L.D. Cohen. Fast extraction of minimal paths in 3D images and applications to virtual endoscopy. Medical Image Analysis, 5(4):281-299, December 2001. Video in the web version of the journal.
[22] T. Deschamps, S.M. Ebeid, and L.D. Cohen. Image processing method, system and apparatus for processing an image representing a tubular structure and for constructing a path related to said structure. Patent Pending, March 1999.
[23] Thomas Deschamps and Laurent D. Cohen. Fast extraction of tubular and tree 3D surfaces with front propagation methods. In Proc. 16th IEEE International Conference on Pattern Recognition (ICPR’02), Quebec, Canada, August 2002.
[24] Thomas Deschamps and Laurent D. Cohen. Grouping connected components using minimal path techniques. In Springer, editor, Geometrical Method in Biomedical image processing. R. Malladi (ed.), 2002.
[25] E. W. Dijkstra. A note on two problems in connection with graphs. Numerische Mathematic, 1:269-271, 1959.
[26] A. Frangi, W. Niessen, K. L. Vincken, and M. A. Viergever. Multiscale vessel enhancement filtering. In Proc. Medical Image Computing and Computer-Assisted Intervention, MICCAI’98, Cambridge, pages 130137, 1998.
[27] D. Geiger,A. Gupta, L. Costa, and J. Vlontzos. Dynamic programming for detecting, tracking, and matching deformable contours. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(3):294302, March 1995.
[28] G. Guy and G. Medioni. Inferring global perceptual contours from local features. International Journal of Computer Vision, 20(1/2):113-133, October 1996.
[29] Michael Kass, Andrew Witkin, and Demetri Terzopoulos. Snakes: Active contour models. International Journal of Computer Vision, 1(4):321-331, January 1988.
[30] R. Kimmel,A. Amir, and A. Bruckstein. Finding shortest paths on surfaces using level sets propagation. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-17(6):635-640, June 1995.
[31] R. Kimmel, N. Kiryati, and A. M. Bruckstein. Distance maps and weighted distance transforms. Journal of Mathematical Imaging and Vision, 6:223-233, May 1996. Special Issue on Topology and Geometry in Computer Vision.
[32] M. Lefebure and L. D. Cohen. Image registration, optical flow and local rigidity. Journal of Mathematical Imaging and Vision, 14(2), 2001. CEREMADE TR 0102, Jan 2001.
[33] R. Malladi, J. A. Sethian, and B. C. Vemuri. Evolutionary fronts for topology-independent shape modeling and recovery. In Proc. Third European Conference on Computer Vision, pages 3-13, Stockholm, Sweden, May 1994.
[34] R. Malladi, J. A. Sethian, and B. C. Vemuri. Shape modeling with front propagation: A level set approach. IEEE Trans. on PAMI, 17(2):158-175, February 1995.
[35] R. Malladi and J.A. Sethian. A real-time algorithm for medical shape recovery. In Proceedings of the IEEE International Conference on Computer Vision (ICCV’98), pages 304-310, January 1998.
[36] Frédéric Richard and Laurent D. Cohen. Une nouvelle technique de recalage d’images avec des contraintes aux bords libres : applications aux mammographies. In Actes de la conférence Reconnaissance des Formes et Intelligence Artificielle, RFIA’02, pages 453-462, Angers, Janvier 2002.
[37] Patrick Sayd, Sylvie Naudet, Marc Viala, Laurent Cohen, and A. Dumont. AOMS un outil de releve 3D d’environnements industriels. In Actes du congrès de Vision ORASIS 2001, Cahors, Juin 2001.
[38] Zakaria Ben Sbeh, Laurent D. Cohen, Gérard Mimoun, and Gabriel Coscas. A new approach of geodesic reconstruction for drusen segmentation in eye fundus images. IEEE Transactions on Medical Imaging, 20(12):1321-1333, December 2001.
[39] J. A. Sethian. Level Set Methods: Evolving Interfaces in Geometry, Fluid Mechanics, Computer Vision and Materials Sciences. Cambridge Univ. Press, 1996.
[40] A. Shaashua and S. Ullman. Structural saliency: The detection of globally salient structures using a locally connected network. In Proc. Second IEEE International Conference on Computer Vision (ICCV’88), pages 321-327, December 1988.
[41] H. Tek and B. Kimia. Image segmentation by reaction-diffusion bubbles. In Proceedings of the IEEE International Conference on Computer Vision (ICCV’95), pages 156-162, Cambridge, USA, June 1995.
[42] Samuel Vinson and Laurent D. Cohen. Extraction des bâtiments complexes à partir d’images aériennes et de MNE. In Actes de la conférence Reconnaissance des Formes et Intelligence Artificielle, RFIA’02, pages 125-134, Angers, Janvier 2002.
[43] L. R. Williams and D. W. Jacobs. stochastic completion fields: a neural model of illusory contour shape and salience. In Proc. Fifth IEEE International Conference on Computer Vision (ICCV’95), pages 408-415, Cambridge, USA, June 1995.