Fast algorithm for shape dissimilarity metric

We developed a fast algorithm to compute the elastic shape dissimilarity metric between 2d closed planar curves. The algorithm performs the underlying optimization to find the matching starting point, rotation and diffeomorphism between two given curves in empirically subquadratic times with respect to the number of nodes. The figure below shows a 100x100 shape distance matrix computed for a subset of the MPEG7 shape data set.

Image segmentation in 2d using the Mumford Shah functional

Using a curve evolution approach to minimizing the Mumford-Shah functional allows us to segment noisy images, which can be approximated by piecewise smooth functions. This approach is very powerful, but also computationally very expensive, because it requires solving elliptic PDEs at each iteration of the curve evolution. We developed a fast Newton-type algorithm for image segmentation with the Mumford-Shah functional, using an adaptive Lagrangian shape optimization approach. Below is an example of the evolution of the segmenting curves and the evolution of the piecewise smooth approximation. See paper for more information.

These pictures show the evolution of an initial curve to capture the boundaries of cells in the given picture. The curves evolve in such a way that they stop at a minimum of the piecewise smooth Mumford-Shah energy.

These pictures show the evolution of the smooth approximations to the original image, computed from the corresponding elliptic PDEs in the domains defined by the curves.

Image segmentation in 2d using the Geodesic Active Contour model

We developed a fast Lagrangian method to segment images using the Geodesic Active Contour model. The use of a Lagrangian representation and second order energy sensitivity information results in a fast segmentation algorithm. The curve representation adapts to the image and the geometry by adjusting node density. It can also handle topological changes in a very robust manner. Note that we do not use the level set method or any other Eulerian representation to handle the topological changes.

Segmentating 3d objects using adaptive triangulated surfaces

We also developed an adaptive Lagrangian algorithm for 3d image segmentation using a minimal surface energy model. The method uses second order energy sensitivies and judicious adaptation of the surface triangulations to produce high quality segmentations fast. The low computational cost is in stark contrast with a voxel-based approach, such as the level set method.

In this example, we start with a coarse initial mesh. As the method senses that it is close to an object, it adapts the triangulation to capture the object accurately. It keeps the triangulation fine close to sharp features, such as object edges and corners, but coarse in other places, such as the smooth faces of the object, where small triangles are not needed to resolve and represent the object.

This is another example showing the use of adaptive triangulated surfaces, which do a good job in segmenting two touching balls with a cusp in between.

Reconstruction of the source of an elliptic PDE from sparse observations

In this work, we developed a multilevel inversion algorithm for reconstruction of the source of an elliptic PDE in optimal time. The algorithm is especially effective in the case of high fidelity reconstructions. High fidelity reconstructions are obtained with low regularization, which makes the inversion computationally expensive. Our iterative multilevel algorithm resulted in substantial savings in computations (see paper).

Research Gallery

The following are examples of results from some of my work in the recent years.