A binary image I is Ba, Wb-connected, where a, b ∈ {4, 8}, if its foreground is a-connected and its background is b-connected. We consider a local modification of a Ba, wb-connected image I in which a black pixel can be interchanged with an adjacent white pixel provided that this preserves the connectivity of both the foreground and the background of I. We have shown that for any (a, b) ∈ {(4, 8), (8, 4), (8, 8)}, any two Ba, wb-connected images I and J each with n black pixels differ by a sequence of Θ(n2) interchanges. We have also shown that any two B4, W4-connected images I and J each with n black pixels differ by a sequence of O(n4) interchanges.

Additional Metadata
Keywords Binary images, Connectivity, Digital topology, Interchanges, IP-equivalence, Transforming images
Persistent URL dx.doi.org/10.1016/j.cviu.2007.06.003
Journal Computer Vision and Image Understanding
Citation
Bose, P, Dujmović, V, Hurtado, F. (Ferran), & Morin, P. (2009). Connectivity-preserving transformations of binary images. Computer Vision and Image Understanding, 113(10), 1027–1038. doi:10.1016/j.cviu.2007.06.003