A Multiphase Level Set Framework for Image Segmentation Using the Mumford and Shah Model

International Journal of Computer Vision - Tập 50 Số 3 - Trang 271-293 - 2002
Vese, Luminita A.1, Chan, Tony F.1
1Department of Mathematics, University of California, Los Angeles, USA

Tóm tắt

We propose a new multiphase level set framework for image segmentation using the Mumford and Shah model, for piecewise constant and piecewise smooth optimal approximations. The proposed method is also a generalization of an active contour model without edges based 2-phase segmentation, developed by the authors earlier in T. Chan and L. Vese (1999. In Scale-Space'99, M. Nilsen et al. (Eds.), LNCS, vol. 1682, pp. 141–151) and T. Chan and L. Vese (2001. IEEE-IP, 10(2):266–277). The multiphase level set formulation is new and of interest on its own: by construction, it automatically avoids the problems of vacuum and overlap; it needs only log n level set functions for n phases in the piecewise constant case; it can represent boundaries with complex topologies, including triple junctions; in the piecewise smooth case, only two level set functions formally suffice to represent any partition, based on The Four-Color Theorem. Finally, we validate the proposed models by numerical results for signal and image denoising and segmentation, implemented using the Osher and Sethian level set method.

Từ khóa


Tài liệu tham khảo

Amadieu, O., Debreuve, E., Barlaud, M., and Aubert, G. 1999. In-ward and outward curve evolution using level set method. In Proceedings ICIP, Japan, pp. 188–192.

citation_journal_title=Boll. Un. Mat. It.; citation_title=A compactness theorem for a special class of functions of bounded variation; citation_author=L. Ambrosio; citation_volume=3; citation_issue=B; citation_publication_date=1989; citation_pages=857-881; citation_id=CR2

citation_journal_title=Comm. Pure Appl. Math.; citation_title=Approximation of functionals depending on jumps by elliptic functionals via Γ-convergence; citation_author=L. Ambrosio, V.M. Tortorelli; citation_volume=43; citation_publication_date=1990; citation_pages=999-1036; citation_id=CR3

citation_journal_title=Bolletino U.M.I.; citation_title=On the approximation of free discontinuity problems; citation_author=L. Ambrosio, V.M. Tortorelli; citation_volume=7; citation_issue=6-B; citation_publication_date=1992; citation_pages=105-123; citation_id=CR4

citation_title= . ; citation_publication_date=2001; citation_id=CR5; citation_author=G. Aubert; citation_author=P. Kornprobst; citation_publisher=Springer

Barles, G. 1994. Solutions de viscosité des équations de Hamilton-Jacobi. Mathématiques & Applications, vol. 17, Springer-Verlag.

citation_journal_title=Arch. Rational Mech. Analysis; citation_title=A new approach to front propagation problems: theory and applications; citation_author=G. Barles, P.E. Souganidis; citation_volume=141; citation_issue=3; citation_publication_date=1998; citation_pages=237-296; citation_id=CR7

citation_journal_title=M2AN Math. Model. Numer. Anal.; citation_title=Image segmentation with a finite element method; citation_author=B. Bourdin; citation_volume=33; citation_issue=2; citation_publication_date=1999; citation_pages=229-244; citation_id=CR8

citation_journal_title=Numer. Math.; citation_title=Implementation of a finite-elements approximation of the Mumford-Shah functional; citation_author=B. Bourdin, A. Chambolle; citation_volume=85; citation_issue=4; citation_publication_date=2000; citation_pages=609-646; citation_id=CR9

citation_journal_title=IEEE-IP; citation_title=An axiomatic approach to image interpolation; citation_author=V. Caselles, J.M. Morel, C. Sbert; citation_volume=7; citation_issue=3; citation_publication_date=1998; citation_pages=376-386; citation_id=CR10

citation_journal_title=C. R. Acad. Sci. Paris; citation_title=Un théoréme de-convergence pour la seg-mentation des signaux; citation_author=A. Chambolle; citation_volume=314; citation_issue=I; citation_publication_date=1992; citation_pages=191-196; citation_id=CR11

citation_journal_title=SIAM J. Appl. Math.; citation_title=Image segmentation by variational methods: Mumford and Shah functional and the discrete approximations; citation_author=A. Chambolle; citation_volume=55; citation_issue=3; citation_publication_date=1995; citation_pages=827-863; citation_id=CR12

citation_journal_title=M2AN Math. Model. Numer. Anal.; citation_title=Finite-differences discretizations of the Mumford-Shah functional; citation_author=A. Chambolle; citation_volume=33; citation_issue=2; citation_publication_date=1999; citation_pages=261-288; citation_id=CR13

citation_journal_title=M2AN Math. Model. Numer. Anal.; citation_title=Discrete approximation of the Mumford-Shah functional in dimension two; citation_author=A. Chambolle, G. Dal Maso; citation_volume=33; citation_issue=4; citation_publication_date=1999; citation_pages=651-672; citation_id=CR14

Chan, T. and Vese, L. 1999. An active contour model without edges. In Scale-Space'99, M. Nilsen et al. (Eds.), LNCS, vol. 1682, pp. 141–151.

citation_journal_title=IEEE-IP; citation_title=Active contours without edges; citation_author=T. Chan, L. Vese; citation_volume=10; citation_issue=2; citation_publication_date=2001; citation_pages=266-277; citation_id=CR16

citation_journal_title=JVCIR; citation_title=Active contours without edges for vector-valued images; citation_author=T. Chan, B.Y. Sandberg, L. Vese; citation_volume=11; citation_publication_date=2000; citation_pages=130-141; citation_id=CR17

citation_journal_title=J. Diff. Geometry; citation_title=Uniqueness and existence of viscosity solutions of generalized mean curvature flow equations; citation_author=Y.G. Chen, Y. Giga, S. Goto; citation_volume=33; citation_publication_date=1991; citation_pages=749-786; citation_id=CR18

citation_journal_title=JCP; citation_title=A simple level set method for solving Stefan problems; citation_author=S. Chen, B. Merriman, S. Osher, P. Smereka; citation_volume=135; citation_publication_date=1997; citation_pages=8-29; citation_id=CR19

Cohen, L.D. 1997. Avoiding local minima for deformable curves in image analysis. In Curves and Surfaces with Applications in CAGD,A. Le Méhauté, C. Rabut, and L.L. Schumaker (Eds.), pp. 77–84.

Cohen, L., Bardinet, E., and Ayache, N. 1993. Surface reconstruction using active contour models. In Proceedings SPIE 93 Conference on Geometric Methods in Computer Vision, San Diego, CA, July 1993.

citation_journal_title=Amer. Math. Soc. Bull.; citation_title=User's guide to viscosity solutions of second order partial differential equations; citation_author=M.G. Crandall, H. Ishii, P.-L. Lions; citation_volume=27; citation_publication_date=1992; citation_pages=1-67; citation_id=CR22

citation_journal_title=Acta Matematica; citation_title=A variational method in image segmentation: existence and approximation results; citation_author=G. Dal Maso, J.M. Morel, S. Solimini; citation_volume=168; citation_publication_date=1992; citation_pages=89-151; citation_id=CR23

citation_journal_title=Atti. Accad. Naz. Lincei Rend. Cl. Sci. Fis. Mat. Natur.; citation_title=Newfunctionals in the calculus of variations; citation_author=E. De Giorgi, L. Ambrosio; citation_volume=82; citation_issue=2; citation_publication_date=1988; citation_pages=199-210; citation_id=CR24

citation_journal_title=Arch. Rational Mech. Anal.; citation_title=Existence theorem for a minimum problem with free discontinuity set; citation_author=E. De Giorgi, M. Carriero, A. Leaci; citation_volume=108; citation_issue=3; citation_publication_date=1989; citation_pages=195-218; citation_id=CR25

citation_journal_title=Interfaces and Free Boundaries; citation_title=Segregating partition problem in competition-diffusion systems; citation_author=S.-I. Ei, R. Ikota, M. Mimura; citation_volume=1; citation_issue=1; citation_publication_date=1999; citation_pages=57-80; citation_id=CR26

citation_title=Measure Theory and Fine Properties of Functions; citation_publication_date=1992; citation_id=CR27; citation_author=L.C. Evans; citation_author=R.F. Gariepy; citation_publisher=CRC Press

citation_journal_title=J. Diff. Geometry; citation_title=Motion of level sets by mean curvature; citation_author=L.C. Evans, J. Spruck; citation_volume=33; citation_publication_date=1991; citation_pages=635-681; citation_id=CR28

Fedkiw, R.P. 1999. The ghost fluid method for discontinuities and interfaces. In Proceedings of Godunov Methods: Theory and Applications, Oxford, UK, October 1999.

citation_journal_title=JCP; citation_title=A non-oscillatory eulerian approach to interfaces in multimaterial flows (the ghost fluid method); citation_author=R.P. Fedkiw, T. Aslam, B. Merriman, S. Osher; citation_volume=152; citation_publication_date=1999; citation_pages=457-492; citation_id=CR30

Guichard, F. and Morel, J.-M. Image Analysis and P.D.E.'s (to appear).

citation_journal_title=Arch. Rat. Mech. Anal.; citation_title=Uniqueness of Lipschitz extensions: Minimizing the sup norm of the gradient; citation_author=R. Jensen; citation_volume=123; citation_publication_date=1993; citation_pages=51-74; citation_id=CR32

Kanizsa, G. 1997. La grammaire du voir. Essais sur la perception. Diderot Editeur, Arts et Sciences.

citation_journal_title=SIAM J. of Numerical Analysis; citation_title=A multiscale algorithm for image segmentation by variational method; citation_author=G. Koepfler, C. Lopez, J.M. Morel; citation_volume=31; citation_issue=1; citation_publication_date=1994; citation_pages=282-299; citation_id=CR34

citation_journal_title=Ann. Univ. Ferrara-Sez. VII-Sc. Mat.; citation_title=On minimizing partitions with infinitely many components; citation_author=G.P. Leonardi, I. Tamanini; citation_volume=XLIV; citation_publication_date=1998; citation_pages=41-57; citation_id=CR35

Lorigo, L.M., Faugeras, O., Grimson, W.E.L., Keriven, R., and Kikinis, R. 1999. Co-dimension 2 geodesic active contours for MRA segmentation. Information Processing in Medical Imaging, Proceedings, LNCS, vol. 1613, pp. 126–139.

citation_journal_title=IVC; citation_title=Visual Reconstruction with discontinuities using variational methods; citation_author=R. March; citation_volume=10; citation_publication_date=1992; citation_pages=30-38; citation_id=CR37

citation_journal_title=Ann. Univ. Ferrara-Sez. VII-Sc. Mat.; citation_title=On the finiteness of optimal partitions; citation_author=U. Massari, I. Tamanini; citation_volume=XXXIX; citation_publication_date=1993; citation_pages=167-185; citation_id=CR38

citation_journal_title=JCP; citation_title=Motion of multiple junctions: A level set approach; citation_author=B. Merriman, J.K. Bence, S. Osher; citation_volume=112; citation_issue=2; citation_publication_date=1994; citation_pages=334-363; citation_id=CR39

citation_journal_title=Revista Matematica Universidad Complutense de Madrid; citation_title=Segmentation of images by variational methods: A constructive approach; citation_author=J.M. Morel, S. Solimini; citation_volume=1; citation_publication_date=1988; citation_pages=169-182; citation_id=CR40

citation_journal_title=CRASS Paris Série I, Math.; citation_title=Segmentation d'images par méthode variationnelle: Une preuve constructive d'existence; citation_author=J.M. Morel, S. Solimini; citation_volume=308; citation_publication_date=1989; citation_pages=465-470; citation_id=CR41

citation_title=Variational Methods in Image Segmentation; citation_publication_date=1994; citation_id=CR42; citation_author=J.M. Morel; citation_author=S. Solimini; citation_publisher=Birkhäuser

citation_title=Filtering, Segmentation and Depth; citation_publication_date=1993; citation_id=CR43; citation_author=D. Mumford; citation_author=M. Nitzberg; citation_author=T. Shiota; citation_publisher=Springer-Verlag

citation_journal_title=Comm. Pure Appl. Math.; citation_title=Optimal approximation by piecewise smooth functions and associated variational problems; citation_author=D. Mumford, J. Shah; citation_volume=42; citation_publication_date=1989; citation_pages=577-685; citation_id=CR44

citation_journal_title=JCP; citation_title=Level set methods: An overview and some recent results; citation_author=S. Osher, R.P. Fedkiw; citation_volume=169; citation_issue=2; citation_publication_date=2001; citation_pages=463-502; citation_id=CR45

Osher, S.J. and Fedkiw, R. 2002. Level Set Methods and Dynamic Implicit Surfaces. Applied Mathematical Science, vol. 153, Springer.

citation_journal_title=JCP; citation_title=Fronts propagating with curvature-dependent speed: Algorithms based on Hamilton-Jacobi formulation; citation_author=S. Osher, J.A. Sethian; citation_volume=79; citation_publication_date=1988; citation_pages=12-49; citation_id=CR47

citation_journal_title=Proceedings ECCV, Dublin; citation_title=Coupled Geodesic active regions for image segmentation: A level set approach; citation_author=N. Paragios, R. Deriche; citation_volume=II; citation_publication_date=2000; citation_pages=224-240; citation_id=CR48

citation_title=A level set model for image classification; citation_inbook_title= '9 ; citation_publication_date=1999; citation_pages=306-317; citation_id=CR49; citation_author=C. Samson; citation_author=L. Blanc-Féraud; citation_author=G. Aubert; citation_author=J. Zerubia; citation_publisher=Springer-Verlag

citation_journal_title=IJCV; citation_title=A level set model for image classification; citation_author=C. Samson, L. Blanc-Féraud, G. Aubert, J. Zerubia; citation_volume=40; citation_issue=3; citation_publication_date=2000; citation_pages=187-197; citation_id=CR50

citation_title=Geometric Partial Differential Equations and Image Analysis; citation_publication_date=2001; citation_id=CR51; citation_author=G. Sapiro; citation_publisher=Cambridge University Press

citation_title=Fast Marching Methods and Level Set Methods: Evolving Interfaces in Computational Geometry, Fluid Mechan-ics, Computer Vision and Materials Sciences; citation_publication_date=1999; citation_id=CR52; citation_author=J.A. Sethian; citation_publisher=Cambridge University Press

Shah, J. 1996. A common framework for curve evolution, segmentation and anisotropic diffusion. In Proceedings CVPR, pp. 136–142.

citation_title=Riemannian Drums, Anisotropic Curve Evolution and Segmentation; citation_inbook_title= '9 ; citation_publication_date=1999; citation_pages=129-140; citation_id=CR54; citation_author=J. Shah; citation_publisher=Springer-Verlag

Sharon, E., Brandt, A., and Basri, R. 2000. Fast multiscale image segmentation. In Proceedings CVPR, South Carolina, pp. 70–77.

citation_journal_title=IEEE-PAMI; citation_title=Normalized cuts and image segmentation; citation_author=J. Shi, J. Malik; citation_volume=22; citation_issue=8; citation_publication_date=2000; citation_pages=888-905; citation_id=CR56

citation_journal_title=Interfaces and Free Boundaries; citation_title=A projection method for motion of triple junctions by level sets; citation_author=K.A. Smith, F.J. Solis, D. Chopp; citation_volume=4; citation_issue=3; citation_publication_date=2002; citation_pages=263-276; citation_id=CR57

citation_journal_title=JCP; citation_title=A level set approach for computing solutions to incompressible two-phase flows; citation_author=M. Sussman, P. Smereka, S. Osher; citation_volume=119; citation_publication_date=1994; citation_pages=146-159; citation_id=CR58

citation_journal_title=Progress in Nonlinear Differential Equations and Their Applications; citation_title=Optimal approximation by piecewise constant functions; citation_author=I. Tamanini; citation_volume=25; citation_publication_date=1996; citation_pages=73-85; citation_id=CR59

citation_journal_title=Rend. Sem. Mat. Univ. Padova; citation_title=Optimal segmentation of unbounded functions; citation_author=I. Tamanini, G. Congedo; citation_volume=95; citation_publication_date=1996; citation_pages=153-174; citation_id=CR60

citation_journal_title=IEEE-IP; citation_title=Curve evolution implementation of the Mumford-Shah functional for image segmentation, denoising, interpolation, and magnification; citation_author=A. Tsai, A. Yezzi, A.S. Willsky; citation_volume=10; citation_issue=8; citation_publication_date=2001; citation_pages=1169-1186; citation_id=CR61

Yezzi, A., Tsai, A., and Willsky, A. 1999. A statistical approach to snakes for bimodal and trimodal imagery. In Proceedings ICCV, pp. 898–903.

citation_journal_title=JCP; citation_title=Avariational level set approach to multiphase motion; citation_author=H.-K. Zhao, T. Chan, B. Merriman, S. Osher; citation_volume=127; citation_publication_date=1996; citation_pages=179-195; citation_id=CR63

Zhu, S.C., Lee, T.S., and Yuille, A.L. 1995. Region competition: Unifying snakes, region growing, Energy/Bayes/MDL for multi-band image segmentation. In Proceedings ICCV, Cambridge, pp. 416–423.

citation_journal_title=IEEE-PAMI; citation_title=Region competition: Unifying snakes, region growing, and Bayes/MDL for multi-band image segmen-tation; citation_author=S.C. Zhu, A. Yuille; citation_volume=18; citation_publication_date=1996; citation_pages=884-900; citation_id=CR65