Connectivity preserving transformations for higher dimensional binary images |
| |
Authors: | Anvesh Komuravelli |
| |
Affiliation: | a Computer Science and Engineering Department, Indian Institute of Technology, Kharagpur, Kharagpur-721302, India b Department of Electrical Engineering, Princeton University, Princeton, NJ 08544, USA c Advanced Computing and Microelectronics Unit, Indian Statistical Institute, 203 B. T. Road, Kolkata-700108, India |
| |
Abstract: | An N-dimensional digital binary image (I) is a function I:ZN→{0,1}. I is connected if and only if its black pixels and white pixels are each (3N−1)-connected. I is only connected if and only if its black pixels are (3N−1)-connected. For a 3-D binary image, the respective connectivity models are and . A pair of (3N−1)-neighboring opposite-valued pixels is called interchangeable in a N-D binary image I, if reversing their values preserves the original connectedness. We call such an interchange to be a (3N−1)-local interchange. Under the above connectivity models, we show that given two binary images of n pixels/voxels each, we can transform one to the other using a sequence of (3N−1)-local interchanges. The specific results are as follows. Any two -connected 3-dimensional images I and J each having n black voxels are transformable using a sequence of O((c1+c2)n2) 26-local interchanges. Here, c1 and c2 are the total number of 8-connected components in all 2-dimensional layers of I and J respectively. We also show bounds on 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 , connectivity model and each having n black voxels are transformable using a sequence of O(n2) 26-local interchanges. We generalize this result to show that any two , -connected N-dimensional simply connected images each having n black pixels are transformable using a sequence of O(Nn2)(3N−1)-local interchanges, where N>1. |
| |
Keywords: | Binary image transformation Connectivity models Local interchange IP-equivalence |
本文献已被 ScienceDirect 等数据库收录! |
|