Adaptive deformable models

( Benjamin Taton , J.-O. Lachaud )

In image analysis, it is widely assumed that the number of parameters of deformable models is strongly dependent of the image resolution. For highly deformable models, which adapts their topology to their geometrical changes, all explicit and implicit methods have a number of parameters and a time complexity at least linear with the number of pixels or voxels of the component to extract. We show here that a preprocessing of the image can emphasize interesting parts of the image while diminishing the apparent significance of noisy or homogoneous image regions. This zooming effect focuses model parameters and computations on the interesting part of the images. As a consequence, about five time less vertices in 2D and ten times less vertices in 3D are sufficient to extract image components with the same accuracy. Running times are also sped up by a factor ten in 3D.

Embedding the deformable model into a Riemanian metric

In order to have an adaptive deformable model which can still adapt its topology automatically wrt its geometry, we keep the same idea as the explicit model proposed here but the Euclidean distance is replaced by a Riemanian distance computed from the image of interest. All distance constraints are replaced by riemanian distance constraints. The model dynamic is replaced by a riemanian dynamic. As a result, the model density is regular in the Riemanian space but adaptive in the Euclidean space.

Image analysis with the gradient structure tensor

We use a classical tool to detect interesting parts in the image, especially contour information. It is the gradient structure tensor. From this tensor, the riemanian structure tensor is almost readily computed.

Complexity independent from image resolution

For further information, you may consult the PhD thesis of Benjamin Taton [ PhD Thesis PDF | Abstract PDF ].

Lachaud05b , Lachaud04a , Lachaud03d , Taton02b

J.-O. Lachaud and B. Taton. Deformable Model with a Complexity Independent from Image Resolution. Computer Vision and Image Understanding, 99(3): 453-475. 2005.

[BibTeX reference] [article PDF] [Elsevier Sciencedirect]

Abstract:
We present a parametric deformable model which recovers image components with a complexity independent from the resolution of input images. The proposed model also automatically changes its topology and remains fully compatible with the general framework of deformable models. More precisely, the image space is equipped with a metric that expands salient image details according to their strength and their curvature. During the whole evolution of the model, the sampling of the contour is kept regular with respect to this metric. By this way, the vertex density is reduced along most parts of the curve while a high quality of shape representation is preserved. The complexity of the deformable model is thus improved and is no longer influenced by feature-preserving changes in the resolution of input images. Building the metric requires a prior estimation of contour curvature. It is obtained using a robust estimator which investigates the local variations in the orientation of image gradient. Experimental results on both computer generated and biomedical images are presented to illustrate the advantages of our approach.

Keywords:
deformable model, topology adaptation, resolution adaptation, curvature estimation, segmentation/reconstruction.

J.-O. Lachaud and B. Taton. Resolution Independent Deformable Model. In Proc. 17th int. Conf. on Pattern Recognition (ICPR'2004), Cambridge, United Kingdom, 23-26 August, volume II, pages 237-240, 2004. IEEE Computer Society Press.

[BibTeX reference] [paper PS gzipped] [IEEE]

Abstract:
In this paper we propose a parametric deformable model that automatically adapts its topology and that recovers accurately image components with a complexity independent from the resolution of input image. The main idea is to equip the image space with a metric that expands interesting features in the image depending on their geometry.

Keywords:
3D image segmentation, shape recovery, deformable models, snakes, automated topology changes, adaptive resolution, Riemannian geometry, Lagrangian mechanics, deformable surface, structure tensor

J.-O. Lachaud and B. Taton, Deformable Model with Adaptive Mesh and Automated Topology Changes. In M. Rioux, P. Boulanger and G. Godin, editors, Proc. 4th int. Conf. 3-D Digital Imaging and Modeling (3DIM'2003), Banff, Alberta, Canada, 2003. IEEE Computer Society Press.

[BibTeX reference] [paper PS gzipped] [slides PDF] [IEEE]

Abstract:
Due to their general and robust formulation deformable models offer a very appealing approach to 3D image segmentation. However there is a trade-off between model genericity, model accuracy and computational efficiency. In general, fully generic models require a uniform sampling of either the space or their mesh. The segmentation accuracy is thus a global parameter. Recovering small image features results in heavy computational costs whereas generally only restricted parts of images require a high segmentation accuracy. This paper presents a highly deformable model that both handles fully automated topology changes and adapts its resolution locally according to the geometry of image features. The main idea is to replace the Euclidean metric with a Riemannian metric that expands interesting parts of the image. Then, a regular sampling is maintained with this new metric. This allows to automatically handle topology changes while increasing the model resolution locally according to the geometry of image components. By this way high quality segmentation is achieved with reduced computational costs.

B. Taton and J.-O. Lachaud. Deformable Model with non-Euclidean Metrics. In A. Heyden, G. Sparr, M. Nielsen, and P. Johansen, editors, Proc. 7th European Conference on Computer Vision (ECCV'2002), Copenhagen, Denmark, volume 2352 (part III) of LNCS, pages 438-453, 2002. Springer, Berlin.

[BibTeX reference] [paper PS gzipped] [poster PS gzipped] [LNCS]

Abstract:
Deformable models like snakes are a classical tool for image segmentation. Highly deformable models extend them with the ability to handle dynamic topological changes, and therefore to extract arbitrary complex shapes. However, the resolution of these models largely depends on the resolution of the image. As a consequence, their time and memory complexity increases at least as fast as the size of input data. In this paper we extend an existing highly deformable model, so that it is able to locally adapt its resolution with respect to its position. With this property, a significant precision is achieved in the interesting parts of the image, while a coarse resolution is maintained elsewhere. The general idea is to replace the Euclidean metric of the image space by a deformed non-Euclidean metric, which geometrically expands areas of interest. With this approach, we obtain a new model that follows the robust framework of classical deformable models, while offering a significant independence from both the size of input data and the geometric complexity of image components.

Keywords:
image segmentation, deformable model, non-Euclidean geometry, topology adaptation, optimization