Connectivity preserving transformations for higher dimensional binary images

An NN-dimensional digital binary image (II) is a function I:ZN→{0,1}I:ZN→{0,1}. II is B3N−1,W3N−1 connected if and only if its black pixels and white pixels are each (3N−13N−1)-connected. II is only B3N−1 connected if and only if its black pixels are (3N−13N−1)-connected. For a 3-D binary image, the respective connectivity models are B26,W26 and B26. A pair of (3N−13N−1)-neighboring opposite-valued pixels is called interchangeable   in a NN-D binary image II, if reversing their values preserves the original connectedness. We call such an interchange to be a (3N−1)(3N−1)-local interchange. Under the above connectivity models, we show that given two binary images of nn pixels/voxels each, we can transform one to the other using a sequence of (3N−1)(3N−1)-local interchanges. The specific results are as follows. Any two B26-connected 3-dimensional images II and JJ each having nn black voxels are transformable using a sequence of O((c1+c2)n2)O((c1+c2)n2) 26-local interchanges. Here, c1c1 and c2c2 are the total number of 8-connected components in all 2-dimensional layers of II and JJ respectively. We also show bounds on B26 connectivity under a different interchange model as proposed in [A. Dumitrescu, J. Pach, Pushing squares around, Graphs and Combinatorics 22 (1) (2006) 37–50]. Next, we show that any two simply connected   images under the B26, W26 connectivity model and each having nn black voxels are transformable using a sequence of O(n2)O(n2) 26-local interchanges. We generalize this result to show that any two B3N−1, W3N−1-connected NN-dimensional simply connected   images each having nn black pixels are transformable using a sequence of O(Nn2)(3N−1)O(Nn2)(3N−1)-local interchanges, where N>1N>1.