Computation of crowded geodesics on the universal Teichmueller space for planar shape matching in computer vision

University Of Utah, Salt Lake City UT

Investigators

Abstract

Quantifying the (dis)similarity between two shapes is a central problem in computer vision. One distance metric on the space of planar shapes is realized by identifying this space as a subset of the Universal Teichmueller Space, and equipping it with the Weil-Petersson metric. This results in a metric that is scale- and translation-invariant on shapes, and has unique geodesic flow between two shape endpoints. The work of this proposal develops robust computational methods for the computation of metric distances and geodesics between shapes on this space. The major difficulty lies in computations involving "crowded" shapes, i.e., those with elongated, winding, or extended protrusions. Such shapes stymie finite-precision computations because direct algorithms suffer from severe roundoff error. The major thrusts of this proposal develop algorithmic methodologies to address roundoff error and related issues: The Zipper conformal mapping algorithm will be augmented to produce accurate conformal maps for crowded shapes. The velocity field representation on a geodesic will be rewritten into a form that is resistant to roundoff error. The geodesic equation will be transformed into a expression that takes advantage of the aforementioned velocity field transformation, and can effectively flow between crowded shapes. The final phase of this project will demonstrate accurate geodesic flow and distance computations between crowded shapes. The methods developed under this project can be applied to several related problems in scientific computing: solutions to differential equations on irregular geometries through conformal mapping, conservative integration methods with ill-conditioned particle systems, and moving-mesh kernel approximations. The work of this project can contribute to far-reaching applications in scientific and computer vision problems: automated object recognition (e.g. projectile identification), outline classification (determination of an animal's species), medical imaging (usage of MRI to diagnose dementia and related diseases), and artificial intelligence (visual recognition and interpretation) to name a few. All computational deliverables (computer code, example simulations, documentation) will be made publicly available. Through the engagement of students in related research tasks, this project will contribute to the educational development of future engineers, mathematicians, and computer scientists.