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.

, , , , ,
doi.org/10.1016/j.cviu.2007.06.003
Computer Vision and Image Understanding
School of Computer Science

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