Team 5: Size and shape comparisons from noisy, unlabeled,<br/><br/>incomplete configurations of landmarks in three-dimensional<br/><br/>space

Wednesday, August 8, 2007 - 11:20am - 11:40am
EE/CS 3-180
Mark Stuff (Michigan Technological University)
Traditional non-invasive sensing technologies have generated information about only one or two dimensional projections of objects of interest. But the use of arrays of sensor components, and opportunities to rapidly move such arrays around objects of interest are enabling the practical generation of many forms of three-dimensional data. For example, in acoustics there has been steady progression from one-dimensional echo trains, to two-dimensional acoustic images, to modern three-dimensional reconstructions, on scales from ultrasound wavelengths to global seismic surveys. Similarly, three-dimensional tomographic reconstructions from x-rays are now commonly used to resolve ambiguities in traditional two-dimensional x-ray images.

As more three-dimensional data becomes available, the value of automatic tools for utilizing such data increases. Several desired applications need methods by which to automate the finding of correspondences between three-dimensional data sets. These three-dimensional data sets frequently share many geometric characteristics, but also have significant differences, due to differences in data collection geometries, changes in sensor capabilities, temporal changes in the object of interest, and noise in the data.

One approach to finding unknown coordinate transformations, which are needed to align multi-dimensional data sets, is to require an expert to examine each set and label certain common landmarks. If sufficient landmarks, having the same unique labels can be found in both sets, the three-dimensional coordinates of the landmarks enable the coordinate transformation to be estimated. This is like aligning images of faces, by first extracting the coordinates the tips of the noses, the left corners of the mouths, the bases of the right earlobes, etc.

But when no prior expertise is available, we need methods of estimating the transformation from set of automatically generated coordinates of 'interesting' locations (unlabeled landmarks). We expect that a significant subset of corresponding unlabeled landmarks may exist somewhere in the data set to which we need to compare. To solve our alignment problems, we need to devise automated methods to robustly find a pair of large subsets from a pair of sets of unlabeled landmarks, such that the subsets have similar geometric characteristics.


Does there exist a rigid motion mapping the
configuration of red points onto a subset of the blue points?
If so, what is the blue subset, and what is the rigid motion?
If not, how much deformation of the red configuration is needed
to make it so?

In principle, these problems can be solved by exhaustively comparing every possibility, but the level of effort grows exponentially fast with the number of landmarks. Our goal will be to find and test new approaches to this problem, seeking to devise algorithms which are robust and far more efficient.


  1. Oliver Faugeraus, Three-Dimensional Computer
    , MIT Press, 2001

  2. Ian L. Dyrden, Kanti V. Mardia, {Statistical Shape Analysis}, Wiley, 1998

  3. D. G. Kendall, D. Barden, T. K. Carne, H. Le, Shape and
    Shape Theory
    , Wiley Series in Probability and Statistics, 1999

  4. Gene H. Golub, Charles Van Loan, Matrix
    , Johns Hopkins University Press, 1996


Basics of linear algebra and matrix theory, basic computer programming skills, elementary Euclidean geometry

Desired: Ability to bring relevant ideas from one or more of geometry, invariant theory, optimization theory, graph theory, combinatorics, or something else.