A fast and robust algorithm to count topologically persistent holes in noisy clouds

Kurlin, Vitaliy ORCID: 0000-0001-5328-5351 (2014) A fast and robust algorithm to count topologically persistent holes in noisy clouds. In: 2014 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2014-6-23 - 2014-6-28.

Text counting-holes-in-noisy-clouds-full.pdf - Author Accepted Manuscript Download (2MB)

Abstract

Preprocessing a 2D image often produces a noisy cloud of interest points. We study the problem of counting holes in unorganized clouds in the plane. The holes in a given cloud are quantified by the topological persistence of their boundary contours when the cloud is analyzed at all possible scales. We design the algorithm to count holes that are most persistent in the filtration of offsets (neighborhoods) around given points. The input is a cloud of $n$ points in the plane without any user-defined parameters. The algorithm has $O(n\log n)$ time and $O(n)$ space. The output is the array (number of holes, relative persistence in the filtration). 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.

Item Type:	Conference or Workshop Item (Unspecified)
Additional Information:	Full version of the paper that has appeared in Proceedings of IEEE conference CVPR 2014: Computer Vision and Pattern Recognition, Columbus, Ohio, USA (10 pages, 20 figures, 3 appendices, more examples will be at http://kurlin.org)
Uncontrolled Keywords:	cs.CG, cs.CG, cs.CV, math.AT, 68U05 (Primary) 65D18, 68U10 (Secondary)
Depositing User:	Symplectic Admin
Date Deposited:	15 Dec 2016 16:25
Last Modified:	19 Jan 2023 07:24
DOI:	10.1109/CVPR.2014.189
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3004879