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

Kurlin, Vitaliy

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

Kurlin, Vitaliy

Authors

Vitaliy Kurlin

Abstract

Preprocessing a 2D image often produces a noisy cloud of interest points. We study the problem of counting holes in noisy 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 a near linear time and a linear space O(n). 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.

Citation

Kurlin, V. (2014). A fast and robust algorithm to count topologically persistent holes in noisy clouds.

Conference Name	CVPR : Computer Vision and Pattern Recognition
Conference Location	Columbus, Ohio, USA
Start Date	Jun 24, 2023
Publication Date	2014
Deposit Date	May 14, 2014
Publicly Available Date	Jul 24, 2014
Series Title	Proceedings of IEEE Conference CVPR
Publisher URL	http://www.cv-foundation.org/openaccess/CVPR2014.py