Minimal test patterns for connectivity preservation in parallel thinning algorithms for binary digital images (Q1115212)

In successive deletion stages of parallel thinning algorithms for binary digital images, one usually checks the preservation of connectivity by verifying that: (a) every removed pixel is individually deletable without modifying connectivity (well-known criteria, such as those of Rosenfeld and Yokoi, exist for that purpose); (b) every pair of 8-adjacent removed pixels is deletable without connectivity modification. In the case of the 8-connectivity for the figure (and the 4-connectivity for the background), two more patterns must be tested for connectivity preservation: an isolated triple or quadruple of mutually 8-adjacent pixels. We give a formal characterization of these patterns for testing connectivity preservation by what we call minimal non-x-deletable sets (x-MND sets), where \(x=4\), 8, or \(\{\) 4,8\(\}\) (the type of connectivity considered for the figure). A parallel thinning algorithmg whose deletion stage cannot remove an x-MND set is guaranteed to preserve the connectivity properties of any figure. We show that an x-MND set consists in either (1) a single pixel; or (2) a pair of 8-adjacent pixels; or (3) an isolated triple or quadruple of mutually 8-adjacent pixels (for \(x=8\) only).