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