Geometric Active Contours Ron Kimmel www.cs.technion.ac.il/~ron Computer Science Department Technion-Israel Institute of Technology Geometric Image Processing LabEdge Detection q Edge Detection: u The process of labeling the locations in the image where the gray level’s “rate of change” is high. n OUTPUT: “edgels” locations, direction, strength q Edge Integration: u The process of combining “local” and perhaps sparse and non-contiguous “edgel”-data into meaningful, long edge curves (or closed contours) for segmentation n OUTPUT: edges/curves consistent with the local dataThe Classics q Edge detection: u Sobel, Prewitt, Other gradient estimators u Marr Hildreth zero crossings of u Haralick/Canny/Deriche et al. “optimal” directional local max of derivative q Edge Integration: u tensor voting (Rom, Medioni, Williams, …) u dynamic programming (Shashua & Ullman) u generalized “grouping” processes (Lindenbaum et al.)The “New-Wave” q Snakes q Geodesic Active Contours q Model Driven Edge Detection!Edge Curves!“nice” curves that optimize a functional of g( ), i.e. nice: “regularized”, smooth, fit some prior information!Image!Edge Indicator Function!Geodesic Active Contours q Snakes Terzopoulos-Witkin-Kass 88 u Linear functional efficient implementation u non-geometric depends on parameterization q Open geometric scaling invariant, Fua-Leclerc 90 q Non-variational geometric flow Caselles et al. 93, Malladi et al. 93 u Geometric, yet does not minimize any functional q Geodesic active contours Caselles-Kimmel-Sapiro 95 u derived from geometric functional u non-linear inefficient implementations: n Explicit Euler schemes limit numerical step for stability q Level set method Ohta-Jansow-Karasaki 82, Osher-Sethian 88 u automatically handles contour topology q Fast geodesic active contours Goldenberg-Kimmel-Rivlin-Rudzsky 99 u no limitation on the time step u efficient computations in a narrow bandLaplacian Active Contours q Closed contours on vector fields u Non-variational models Xu-Prince 98, Paragios et al. 01 u A variational model Vasilevskiy-Siddiqi 01 q Laplacian active contours open/closed/robust Kimmel-Bruckstein 01 Most recent: variational measures for good old operators Kimmel-Bruckstein 03 !SegmentationSegmentation q Ultrasound images!Caselles,Kimmel, Sapiro ICCV’95Segmentation PintosWoodland Encounter Bev Doolittle 1985 q With a good prior who needs the data…!Segmentation Caselles,Kimmel, Sapiro ICCV’95Prior knowledge…Prior knowledge…SegmentationSegmentationSegmentation Caselles,Kimmel, Sapiro ICCV’95Segmentation q With a good prior who needs the data…!Wrong Prior???Wrong Prior???Curves in the Plane q C(p)={x(p),y(p)}, p [0,1]!y x C(0) C(0.1) C(0.2) C(0.4) C(0.7) C(0.95) C(0.9) C(0.8) p C =tangentArc-length and Curvature s(p)= | |dp !CCalculus of Variations Find C for which is an extremum Euler-Lagrange: !Calculus of Variations Important Example ⇒ Euler-Lagrange: , setting ⇒ ⇒ Curvature flowPotential Functions (g) x I(x,y) I(x) x g(x) x x g(x,y) Image EdgesSnakes & Geodesic Active Contours q Snake model Terzopoulos-Witkin-Kass 88 q Euler Lagrange as a gradient descent q Geodesic active contour model Caselles-Kimmel-Sapiro 95 q Euler Lagrange gradient descentMaupertuis Principle of Least Action Snake = Geodesic active contour up to some , i.e ⇒ Snakes depend on parameterization. ⇒ Different initial parameterizations yield solutions for different geometric functionals x y p 1 0 Caselles Kimmel Sapiro, IJCV 97Geodesic Active Contours in 1D Geodesic active contours are reparameterization invariant I(x) x g(x) xGeodesic Active Contours in 2D g(x)= G *I sControlling -max I g Smoothness Cohen Kimmel, IJCV 97Fermat’s Principle In an isotropic medium, the paths taken by light rays are extremal geodesics w.r.t. i.e., Cohen Kimmel, IJCV 97Experiments - Color Segmentation Goldenberg, Kimmel, Rivlin, Rudzsky, IEEE T-IP 2001Tumor in 3D MRI Caselles,Kimmel, Sapiro, Sbert, IEEE T-PAMI 97Segmentation in 4D Malladi, Kimmel, Adalsteinsson, !Caselles, Sapiro, Sethian SIAM Biomedical workshop 96Tracking in Color Movies Goldenberg, Kimmel, Rivlin, Rudzsky, IEEE T-IP 2001Tracking in Color Movies Goldenberg, Kimmel, Rivlin, Rudzsky, IEEE T-IP