Project Automatic cloud analysis based on papers in PRL 2016 CVPR 2014 CTIC 2014
Paper: A fast persistencebased segmentation of noisy 2D clouds with provable guarantees.

@article{Kur16PRL, author = {Kurlin, V.}, title = {A fast persistencebased segmentation of noisy 2D clouds with provable guarantees}, journal = {Pattern Recognition Letters}, year = {2016}, volume = {83}, pages = {312} }
 DOI : 10.1016/j.patrec.2015.11.025
 Input : a sparse noisy cloud of boundary points near unknown contours.
 Output : a segmentation into most persistent regions bounded by contours.
 Run time : O(n log n) for any n points with real coordinates in the plane.
 Abstract. We design a new fast algorithm to automatically segment a 2D cloud of points into regions. The only input is a dotted image without any extra parameters, say a scanned blackandwhite map with almost closed curves or any image with detected edge points. The output is a hierarchy of segmentations into regions whose boundary contours have a long enough life span (persistence) in a sequence of nested neighborhoods of the input points. We give conditions on a noisy sample of a graph, when the boundaries of resulting regions are geometrically close to all original cycles in the unknown graph.
Back to Top of this page  Back to Research & papers  Back to Home page
Paper: A fast and robust algorithm to count topologically persistent holes in noisy clouds.

@inproceedings{Kur14CVPR, author = {Kurlin, V.}, title = {A fast and robust algorithm to count topologically persistent holes in noisy clouds}, booktitle = {Proceedings of CVPR 2014: Computer Vision and Pattern Recognition}, publisher = {IEEE}, year = {2014}, pages = {14581463} }
 DOI : 10.1109/CVPR.2014.189 Publisher : IEEE
 Input : a cloud of any points in the plane without extra parameters.
 Output : numbers of most persistent holes with associated probabilities.
 Run time : O(n log n) for any n points with real coordinates in the plane.
 Abstract. Preprocessing a 2D image often produces a noisy cloud of interest points. We study the problem of counting holes in unstructured 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 userdefined parameters. The algorithm has the running time O(n log n) and 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.
 C++ code : cloudanalysis.cpp (a betaversion, please email vitaliy.kurlin(at)gmail.com for support).
Back to Top of this page  Back to Research & papers  Back to Home page
Paper: Autocompletion of contours in sketches, maps and sparse 2D images based on topological persistence.
@inproceedings{Kur14CTIC, author = {Kurlin, V.}, title = {Autocompletion of contours in sketches, maps and sparse 2D Images based on topological persistence}, booktitle = {Proceedings of SYNASC 2014 workshop CTIC: Computational Topology in Image Context}, publisher = {IEEE}, year = {2014}, pages = {594601} }
 DOI : 10.1109/SYNASC.2014.85 Print ISBN : 9781479984473
 Input : a cloud of any points in the plane without extra parameters.
 Output : regions that are enclosed by most persistent closed contours.
 Run time : O(n log n) for any n points with real coordinates in the plane.
 Abstract. We design a new fast algorithm to automatically complete closed contours in a finite point cloud on the plane. The only input can be a scanned map with almost closed curves, a handdrawn artistic sketch or any sparse dotted image in 2D without any extra parameters. The output is a hierarchy of closed contours that have a long enough life span (persistence) in a sequence of nested neighbourhoods of the input points. We prove theoretical guarantees when, for a given noisy sample of a graph in the plane, the output contours geometrically approximate the original contours in the unknown graph.
 C++ code : cloudanalysis.cpp (a betaversion, please email vitaliy.kurlin(at)gmail.com for support).
Back to Top of this page  Back to Research & papers  Back to Home page