Topological Data Analysis: Applications to Computer Vision

Vitaliy Kurlin (Durham)

Monday 8th December, 2014 16:00-17:00 Maths 326

Abstract

Topological Data Analysis is a new research area on the interface between algebraic topology, computational geometry, machine learning and statistics. The key aims are to efficiently represent real-life shapes and to measure shapes by using topological invariants such as homology groups. The usual input is a big unstructured point cloud, which is a finite metric space. The desired outputs are persistent topological structures hidden in the cloud. The flagship method is persistent homology describing the evolution of homology classes in the filtration on data points over all possible scales. After reviewing basic concepts and results, we consider two applications.

The first result is presented at CVPR 2014: Computer Vision and Pattern Recognition. We study the problem of counting holes in noisy 2D clouds. Such clouds emerge as laser scans of building facades with holes representing windows. We design a fast algorithm to count holes that are most persistent in the filtration of neighbourhoods around points in the given cloud. We prove theoretical guarantees when the algorithm finds the correct number of holes (components in the complement) of an unknown shape approximated by a cloud in the plane. 

The second result is presented at CTIC 2014: Computational Topology in Image Context. We extend the previous approach to auto-complete closed contours in 2D clouds emerging from hand-drawn sketches or scans of maps. The new algorithm requires more complicated data structures to maintain adjacency relations of persistent regions, but has the same running time O(n log n) and memory space O(n) for any n points in the plane. For a noisy sample C of a `good' graph G in the plane, the algorithm correctly finds all contours of the graph within a small neighbourhood of G using only the cloud C without any extra input parameters.  

Add to your calendar

Download event information as iCalendar file (only this event)