PI, NSF Career Award
Combined Shape- and Intensity-Based Methods for Visual Tracking
Award Value: $350K

co-PI, NIH (NIBIB-NCI)
Virtual Patients for Computing Radiation Doses
Award Value: $2.5M

Optical Flow under Varying Illumination

Optical flow measures the motion of pixels in an image based on the assumption that their brightness remains fixed between frames. But what if the illumination changes -- possibly severely? We formulate an algorithm that can compute flow fields even under large changes in illumination. Rather than preserve brightness, this algorithm preserves a weak relationship between pairs of pixels in the same frame.

Graph Cuts for Multi-Pixel Interactions

Recently, techniques from combinatorial optimization have become widespread in computer vision algorithms; this is particularly true of the technique of transforming such problems to finding the minimum cut of a graph. At the same time, many vision problems are naturally modeled as having multiple (ie. more than 2) pixels interacting. We derive a set of sufficient conditions under which such multi-pixel problems can be optimized using graph cuts.

3D Model-Based Multi-Object Segmentation

A common problem in medical imaging is to extract a set of organs from a 3D image; this is a critical aspect of image-guided radiotherapy. This can be quite challenging in CT images, due to the diffuse appearance of the organs. We derive a general method for multi-object segmentation, and apply it to the problem of finding the prostate, bladder, and rectum.

Combining Geometric and Photometric Models in Tracking and Segmentation

Pure photometric tracking and segmentation schemes can be improved by allowing the algorithm to take into account the shape of the object. We propose an energy function which incorporates both geometric and photometric terms in a natural way, using level-sets. Minimizing this energy leads to flows which improve on purely photometric algorithms.

Tracking and Segmentation via Density-Matching

Can you find an object just based on colour or texture? It seems that humans do this all the time, and simple, task-specific algorithms do too: if you want to find lips, look for the reddish pixels. We formulate a general purpose scheme which follows this basic logic: curves flow in a direction so as to make their interior as close as possible to a "photometric model" of the object of interest.

Contour Tracking through Tree-Search  

Contour tracking can be made robust by posing it as a mixed continuous-combinatorial optimization problem. The combinatorial part derives from the very large number of curves that can be formed from edge-points in the image. The continuous piece enforces the constraint that the curve must lie on a low-dimensional manifold, which describes the object of interest. We find efficient, tree-like algorithms whose output are provably close to the global optimum.

Subspace-Based Contour Tracking

Contour tracking uses only edge information in order to achieve reliable tracking through video streams. In scenes with a large number of objects, it is often difficult to distinguish between the object of interest and extraneous clutter. We propose characterizing the shape of the object of interest by a linear subspace of curve-space, and using this information to disambiguate the focal object from the clutter.

The Hardness of Finding the Optimal Homological Cycle

If one wishes to measure the size of a cycle in a homology class, there are several natural ways; these include the volume and the diameter of a cycle (both defined for Z2 homology). A natural problem is then to try to find the smallest cycle in a class. We show that such a problem is NP-complete for both the volume and diameter measures; whereas, it is polynomially computable for a measure which is analogous to the radius of the cycle.

Finding Natural Generators for a Homology Group

A very important set of algebraic invariants of a topological space is its homology groups. From the strictly topological point of view, there is no reason to prefer one set of generators of this group to another. However, if some geometry is introduced into the problem, it is seen that in a certain precise sense, some generators are more "natural" than others. We show how to compute such natural generators in roughly cubic time.

Incremental Surface Reconstruction

Surface reconstruction is, by now, a classic problem in computational geometry. However, all existing algorithms require the surface to be embedded in R^3. We propose an incremental algorithm which allows the surface to be of arbitrary codimension. This development allows for the reconstruction of the class of non-orientable surfaces.

Combinatorial Manifold Reconstruction

Given unorganized points drawn from an unknown manifold, can you reconstruct the manifold? This problem is of interest theoretically, and also has potential applications in machine learning. We propose a method which constructs a simplicial manifold; the method is designed to work for abitrary dimension and codimension. Unlike the Isomap and LLE family of algorithms, the proposed technique does not depend on the manifold having the topology of a ball.

Provable Curve Reconstruction with a New Sampling Condition

Amenta et al introduced the medial axis sampling condition to the curve- and surface-reconstruction community. We examine a new sampling condition, based on the notion of "visible points," and show that this leads to a feature size which can be up to twice as large as the medial axis based feature size. We give a novel proof of the homeomorphism of the nearest-neighbour crust (with the original) for 1/3-sampling using this sampling condition.

Compression of Protein Conformational Space

Ab initio prediction of protein structure is a difficult task, and is generally formulated as an energy minimization problem. One of the difficulties is the high dimensionality of the search space. We describe a method for compressing this conformational space, which may be useful in energy minimization as well as other tasks.