Ph. D. Defense

Shape Reconstruction with Topological Priors

Speaker:Ying Zheng
yuanqi at cs.duke.edu
Date: Monday, June 11, 2012
Time: 3:00pm - 5:00pm
Location: North 311, Duke

Abstract

We show topological priors play an important role in solving the inverse problem of shape reconstruction. We classify the applications into 1D, 2D, and 3D cases:

In 1D, we show that the persistent extrema of the curvature function of a closed curve are useful for shape simplication. In 2D, we study how to label a scene into multiple tiers to approximate the actual scene layout. We use the number of extrema as a topological prior to bound the complexity of the shape of tiers and study 2D labeling under symmetry shape priors. In 3D, we recover the detailed 3D root shape using multiple 2D images. Three novel ideas are presented. First, we propose the use of harmonic images for background subtraction. Second, we develop the regularized visual hull to preserve the details of an example image in reconstruction. Third, we enforce the topological connectedness by an ecient algorithm that is inspired by the recent development of persistent homology.

Computational efficiency is emphasized throughout the thesis. We show that 1D topological persistence can be computed in O(n) time on a closed curve of n nodes. For 2D tiered labeling, we give an approximation algorithm to compute it in O(nK) time for K tiers on an image of n pixels. For 3D root reconstruction, we accelerate the computation using oct-trees and minimal spanning trees. With these ingredients, it takes only a few seconds to reconstruct a detailed root shape from 40 images of resolution 1600*1200 on a laptop.

Advisor(s): Herbert Edelsbrunner
Carlo Tomasi, Xiaobai Sun, John Harer