PA170 Digital Geometry Lecture 10: Skeletonization Martin Maska (xmaska@f i .muni . cz) Centre for Biomedical Image Analysis Faculty of Informatics, Masaryk University, Brno Autumn 2023 Motivation: Skeletonization • Skeletonization is a process that simplifies general shapes of objects • Skeleton-derived structures are often exploited as region-based shape descriptors o Skeletons shall ideally be unique, centrally located, topologically equivalent to the original objects, and translation-, rotation-, and scale-invariant 2/19 INTRODUCTION TO SKELETONS Skeleton: Different Definitions • Fire analogy: The boundary is set on fire and skeleton is formed by the loci where the fire fronts meet and quench one another • Skeleton corresponds to the result of medial axis transform defined as the object points having at least two closest boundary points • Skeleton is formed by the centers of all the largest inscribed hyperspheres Source: Kalman Palagyi 4/19 Skeleton: Uniqueness • One skeleton may belong to different objects, which complicates reconstruction of the original object • Original objects can be reconstructed, if the information about the largest hypersphere radius is assigned to individual skeletal points 9 However, such a requirement is barely possible to meet in digital spaces 5/19 Skeleton: Stability • Skeletons are sensitive to minor shape perturbations (e.g., caused by noise or digitization artifacts) • Their simplifications, such as centerlines and topological kernels, may thus lead to more robust shape descriptors • Centerlines are line-like 1D representations of general shapes of objects • Topological kernels are minimal subsets of centerline points topologically equivalent to the original objects centerline topological kernel 6/19 Centerline vs. Topological Kernel in 2D Application of Centerline Extraction in 2D Application of Centerline Extraction in 3D Source: Kálmán Palágyi 9/19 SKELETONIZATION TECHNIQUES Distance-Based Skeletonization o A linear-time approach that can produce inner and outer skeletons O Identification of foreground border points in the input binary image O Calculation of a distance transform from these points O Detection of ridges in the distance transform Input binary image Border points Distance transform (cfe) Voronoi-Based Skeletonization: Voronoi Diagrams • Let S = {pi,..., pn} be a set of points in Ed 9 The Voronoi cell of p\ e S is the closure of its zone of influence defined as the set of all points in Ed that are closer (with respect de) to p\ than to any other point of S: Ve{Pi) = {q : q e ed a de{q, pi) < de(q, pj) for j e {1,..., n}J^ /} • The Voronoi diagram of S is the union of the frontiers of Ve(p^),..., Ve(pn) Voronoi diagram in 2D Voronoi diagram in 3D 12/19 Voronoi-Based Skeletonization: Digital Voronoi Diagrams • In digital grids, S typically consists of grid points, and grid points are assigned to Voronoi cells based on a regular metric da 9 Such an assignment can easily be carried out by propagating distinct labels, initially assigned to the grid points in S, during the calculation of distance transform for a regular metric da using the two-pass algorithm (see Lecture 04) Digital Voronoi diagram (c/4) Digital Voronoi diagram (c/8) 13/19 Voronoi-Based Skeletonization: Procedure O Identification of foreground border points in the input binary image O Calculation of a digital Voronoi diagram for these points O Detection of polygonal arcs between neighboring Voronoi cells, which are fully contained in the foreground of the input binary image Thinning-Based Skeletonization: Main Idea • Thinning algorithms shrink the foreground of the input binary image by repeatedly switching simple foreground points to background until no further change is possible • To have skeletons centrally located, simple foreground points must be deleted from all directions. However, this property cannot always be guaranteed (e.g., rectangles with sides of even lengths) 9 Simply connected components are shrunk into isolated points • Connected components with holes are shrunk into closed curves • Centerlines can be extracted when not allowing switching of endpoints (points with branching index 1) • Sequential (one deletion per iteration) and parallel (multiple deletions per iteration) thinning algorithms exist in both 2D and 3D 15/19 Thinning-Based Skeletonization: Parallel Shrinking Strategy A 0 A (4,8)-simple foreground point is deletable if g or 0 p 0 and its neighborhood 1 ■ -th n ° ? n 0 ? 0 is neither 0 p 1 0 nor n „ 0 0 0 g 0 10 a ■ 11 10 4 ^ 5 s 5 9 8 7 e 5 4 3 2 3 4 4 4 A 4 3 i 1 1 1 1 2 7 3 3 3 3 3 2 1 6 2 2 2 2 2 1 5 1 1 1 1 3 4 2 3 4 5 6 ■ 5 4 3 1 1 2 2 2 2 2 2 2 ■ t 1 1 1 1 1 1 1 1 1 16/19 Thinning-Based Skeletonization: Parallel Shrinking Strategy B • Odd iterations follow Parallel Shrinking Strategy A • In even iterations, a (4,8)-simple foreground point is deletable if ^ q or p 0 ancl 0 its neighborhood's not g p 1 ^ 0 Thinning-Based Skeletonization: Parallel Shrinking Strategy C • The pixels are partitioned into "subfields" (e.g., based on the parity pairs of their coordinates), and only one subfield is processed in each iteration • In each iteration, (o^, a2)-simple foreground points, which belong to the currently processed subfield, are deleted The result of thinning when considering (4,8)-adjacency 18/19 Skeletonization Techniques: Summary Approach Geometrical Topological Centerline Distance-based Yes No No Voronoi-based Yes Yes No Thinning-based No Yes Yes Geometrical Is the skeleton approximately centrally located and invariant to translation, rotation, and scaling? Topological Does the skeleton retain the topology of the original object? Centerline Can the centerline directly be extracted? o Skeletons are simplified, yet not unique representations of digital shapes • They are routinely used in a broad range of applications in 2D (e.g., recognition of handwritten text or verification of fingerprints and signatures) as well as in 3D (e.g., reconstruction and quantification of tubular structures, such as blood vessels, airways, or colons) 19/19