August 1, 2012

When a bunny rabbit turns into a donut

Group of IST Austria Professor Chris Wojtan prepares for presentation at top computer graphics conference SIGGRAPH’12 in L.A. from Aug 5 – 9 • Algorithm enables analysis of evolving data • May prove useful for analyzing human data from MRI scans and fluid simulations

Chris Wojtan’s group at IST Austria, together with Hao Li of Columbia University (N.Y.), will present their paper “Tracking Surfaces with Evolving Topology” at the leading computer graphics conference SIGGRAPH (Special Interest Group on GRAPHics and Interactive Techniques). Their paper is also published in the journal ACM Transactions on Graphics (TOG), the most-frequently cited software journal according to the journal impact factor analysis by Thomson Scientific. The paper will be presented by Morten Bojsen-Hansen, first year PhD student at IST Austria and first author of the paper, on August 7.

The researchers developed an algorithm enabling computers to analyze data scans in which data evolves over time or shows changes in topology. Such data is commonly produced in the sciences in the form of 3D images, point clouds or triangle meshes. In the explanatory video produced by the scientists for the illustration of such changes a bunny rabbit is turned into a donut. One very practical example of such data arising is in the analysis of MRI scans. It is clear to us that the scans taken are related to each other through time, such that a scan is related to the next scan, and the movement seen represents movement and deformation of organs. However, computers do not have an idea of the relation and correspondence between these data samples. Therefore, in order for them to make sense of the data, computer scientists need to teach the computer how to match scans and figure out surface deformation over time.

As an added complication, changes in topology often occur, such that surfaces split or merge throughout time. For example, when analyzing data from fluid simulations, splashes will cause the liquid to separate into droplets and later merge back together. The computer, however, will not “know” where these additional surfaces come from. These changes in topology make it difficult for computers to figure out how one data sample corresponds to another one in a sequence.

The algorithm presented at SIGGRAPH is the first algorithm of its kind able to find correspondences in such data, even when topology changes occur. The researchers show that the algorithm is successful in analyzing scanned human data, fluid simulation data and morphs between different shapes. The algorithm robustly finds correspondences in all these situations, and the researchers are able to measure surface deformation, track information on a surface or create a single time-evolving surface. These may be useful tools for analyzing data from biology and physics, or for tracking movements over time without manually marking individual frames. The scientists show how these ideas are also useful to computer graphics by adding color and texture to animations, and by simulating fluid dynamics on the surface of a moving object.

Information for download