Автор: Guy Rosman
Active contours is a catch-all name for finding the curve that best segments an image.
This is known as segmentation.
Segmentation is highly related to tracking.
In 3D - active surfaces.
Many segmentation functionals can be divided into two groups
Edge-based - the object to be segmented should have its boundary visible in the image, as some sort of prominent edge.
Region-based - the region of the object in the image should have a different statistic in some feature space, compared to its surroundings.
Often, these functionals are combined with information on the shape of the region being extracted.
Edge-based segmentation - Snakes (Terzopolous-Kass-Witkin ’87), Geometric active contours (Caselles-Catte-Coll-Dibos ’93, Malladi-Sethian-Vemuri ’95), Geodesic active contours (Caselles-Kimmel-Sapiro ’98).
Region-based - (Cohen-Bardinet-Ayache ’93), Chan-Vese (’01), Bhattacharyya (Freedman-Zhang ’04, Rathi-Michailovich-Tannenbaum ’06).
Various shape priors are available:
Geometry-based - Curvature based (Sethian ’85, Osher-Sethian ’88), affine curvature based (Angenent-Sapiro-Tannenbaum ’98) and many more.
Shape-Spaces - Leventon-Grimson-Faugeras ’00, Cremers-Tischhauser-Weickert-Schnorr ’02, and many more.
Projective geometry based -Damberville-Sandhu-Yezzi-Tannenbaum ’08, Sandhu-Damberville-Yezzi-Tannenbaum ’08.
The snakes model try to segment the image based on the following energy:
Esnake = Eint+Eext
Optimization is done using splines.
Geometric active contours attempt to segment an object based on its edges, in a level-set framework. The initial contour is chosen to include the object. The contour evolves according to ct = g(I)kN, where g(…) is a function which should drop to zero at edges.
The contour evolution tends to smooth the contour, if no other information is available. The contour according to this evolution will shrink to a point. Hence, a balloon force (Cohen ’91) may be added ct = (g(I)k - b)N.
However the choice of a balloon force is arbitrary. It is not clear if we actually minimize some functional, and the global minimizer is not clear either. The geodesic active contour tries to remedy this by minimizing the following weighted length functional: g(I) constitutes an (inverse) edge indicator. Geodesic active contours (cont.) The functional states that curves segmenting the object should try and surround it with a minimal weighted arclength.
This can be given a physical interpretation: We are looking for the trajectory of a particle on a map, where the potential energy at each point is -Xg(I)
The potential energy of the particle is given by u(c) = -Xg(I)
The E-L equation will simply state conservation of energy for this particle under the chosen trajectory. The trajectory chosen should corresponde to the Hamiltonian.
Maupertuis principle: Curves in Euclidean space which are extremal corresponding to the Hamiltonian, and have an energy level E0, are geodesics with respect to the metric
gij = 2m (E0 -U(c))
The initial energy level E0 is arbitrary.
We now choose E0 = 0 (for an ideal edge we want Eext = Eint = 0), and obtain min.
Which is an intrinsic, Euclidean-invariant functional with need for additional parameters.The resulting curve evolution is given by
ct = (g(I)k - (Vg, N) )
Note the geodesic interpretation also works for parts of the curve (Cohen and Kimmel, ’97).Geodesic active contours (implementation)
Two main techniques are available for efficiently implementing the geodesic active contours model Narrow band (Chopp ’ 93, Adalsteinsson and Sethian ’ 95) methods compute the levelset function on only part of the image, where relevant.
Semi-implicit schemes allow us to take large time steps and converge faster. Multigrid methods may also be used (Kenigsberg et. al. ’ 04, Papandreou and Maragos ’ 07). Narrow band and splitting schemes may be combined! (Goldenberg, Kimmel, Rivlin, Rudzsky ’ 01)
Looking only locally at the gradient for segmentation is quite limited, in terms of basin of attraction and robustness to noise. Region statistics give us a lot more information.
The Mumford-Shah model of image description (’89) partitions the image into:
Smooth parts, which we can approximate by smooth functions, and a small amount of edges.
The resulting functional is the term H (r) denotes the measure of boundary curves, at which discontinuities are allowed.
The functional is defined both in terms of a 2-dimensional function, and a set of 1-dimensional curves. The optimization is not trivial.The Mumford-Shah model (Cont.) Among other schemes, a well-known scheme has been suggested by Ambrosio and Tortorelli ( ’ 92) which replaces the discontinuities with an indicator function.
With optimization carried out on both u and v (EL ’ s are given in their papers). One term states the measure of the discontinuity. Another term is a viscosity term, favoring smooth solutions. Taking P converges to the original MS problem in a r-convergence process.
Many other schemes are available.
Chan and Vese (’00) took the Mumford-Shah model and used it to create a region-statistics based segmentation algorithm.
Similar to a more specific, single-region, approach presented by Cohen et. al. in ’93. The image is assumed to be made of an object and a background, replacing the H(T) term with the length of a closed curve. Inside and outside the object, the image intensity is assumed to be a Gaussian around a certain mean. This suggests a simplified model of the image, where the object has color and the background has color, and a separating contour is assumed to be closed and simple.
Optimization is done on both discrete parameters, and on the levelset function.The levelset formulation involves a smoothed Heaviside approximation H(0)
Obviously, some sort of regularization is needed for the shape of the contour. For example, without the curve length term, the Chan-Vese model simplifies into the k-means algorithm. A natural choice of regularization for curves is to use some measure of the curve:
Often, the length of the contour is added to the functional, resulting in the addition of a curvature flow term.
Another possibility is affine curvature.
The geodesic active contours model contains its own shape regularization.
However, the silhouette or boundary of most objects we try to segment should be based on more than Occam’s razor.
Given the current levelset, its representation in the linear shape space is given by a = Ul(u - v) , where Uk is the matrix of vectors (read: SDMs) spanning the examples of SDMs, obtained by PCA.
All of the above discussion assumes that the contour is registered using the pose parameter p.
Given a current contour, its “correct” representation is given by a maximum a-posteriori (MAP) estimation. As often happens, a is assumed to be Gaussian.
a ~ N(0, Z), where Za is computed from the given examples.
U is connected to a, P using U.
I is only statistically linked to u in the model, P(I|a, p, u) = P(I|u)
Later works have extended the model:
Chen et. al. ’01, Tsai et. al. ’01, Rousson and Paragios ’02, Cremers ’02, Damberville ’06, Yezzi et. al. ’07, Riklin-Raviv et. al. ’07, Etyngier et. al. ’07, Randall et. al. ’07, Thorstensen et. al. ’08 - extended the work to nonlinear dimensionality reduction algorithms, including treatment of the pre-image problem.
NLDR Algorithms in use: KPCA, LLE, Diffusion maps - and more. Extensions by different solutions to the pre-image problem, incorporation of dynamics, different assumption on the transformations allowed and more. Projective Geometry Shape Priors Damberville, Sandhu ’08.
As always in computer vision - if your model is accurate, you can expect much better results shape spaces work fine in medical images, where you really have complete information of the object (once reconstructed.)
Doesn’t work as well for 3D object and a single viewpoint.
Different object poses are not approximated well by a linear space, or by close-to-linear spaces.
If the shape is variable, the variations should be in terms of the 3D object, not its projected silhouette.