A Connected Component Labeling Algorithm for Implicitly-Defined Domains

2022/05/30 by Robert I. Saye, Saye, Robert I.
Computer Science · Engineering · #14P10 (secondary) #65D18 #65D99 (primary) #Advanced Measurement and Metrology Techniques #Advanced Numerical Analysis Techniques #Digital Image Processing Techniques #FOS: Mathematics #Numerical Analysis (math.NA)

paper · pdf · doi:10.48550/arxiv.2205.14885

openalex publication_date 2022/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A connected component labeling algorithm is developed for implicitly-defined domains specified by multivariate polynomials. The algorithm operates by recursively subdividing the constraint domain into hyperrectangular subcells until the topology thereon is sufficiently simple; in particular, we devise a topology test using properties of Bernstein polynomials. In many cases the algorithm produces a certificate guaranteeing its correctness, i.e., two points yield the same label if and only if they are path-connected. To robustly handle various kinds of edge cases, the algorithm may assign identical labels to distinct components, but only when they are exactly or nearly touching, relative to a user-controlled length scale. A variety of numerical experiments assess the effectiveness of the overall approach, including statistical analyses on randomly generated multi-component geometry in 2D and 3D, as well as specific examples involving cusps, self-intersections, junctions, and other kinds of singularities.

Related

• Simple Concurrent Labeling Algorithms for Connected Components
• A New Run-based Connected Component Labeling for Efficiently Analyzing and Processing Holes
• Computing points in connected components defined by a real inequation: algorithms, complexity and implementations, Part I
• A generalized GPU-based connected component labeling algorithm
• Optimal component labeling algorithms for mesh-connected computers and VLSI