DocumentCode :
3274236
Title :
Parallel algorithms for determining k-width- connectivity in binary images
Author :
Dehne, Frank ; Hambrusch, Susanne E.
Author_Institution :
Sch. of Comput. Sci., Carleton Univ., Ottawa, Ont., Canada
fYear :
1990
fDate :
9-13 Dec 1990
Firstpage :
488
Lastpage :
496
Abstract :
The authors consider a new form of connectivity in binary images, called k-width-connectivity. Two pixels a and b of value `1´ are in the same k-width-component if and only if there exists a path of width k such that a is one of the k start pixels and b is one of the k end pixels of this path. The authors present characterisations of the k-width-components and show how to determine the k-width-components of an n× n image in O(n) and O(log2 n) time on a mesh of processors and hypercube, respectively, when the image is stored with one pixel per processor. The methods use a reduction of the k-width-connectivity problem to the 1-width-connectivity problem. A distributed, space-efficient encoding of the k-width-components of small size allows the solution to be represented using O(l) registers per processor. The hypercube algorithm also implies an algorithm for the shuffle-exchange network
Keywords :
computational complexity; computerised picture processing; graph theory; hypercube networks; multiprocessor interconnection networks; parallel algorithms; 1-width-connectivity; binary images; computational complexity; encoding; graph theory; hypercube algorithm; k-width-connectivity; parallel algorithms; shuffle-exchange network; Computer science; Concurrent computing; Contracts; Councils; Encoding; Fault tolerance; Hypercubes; Parallel algorithms; Pixel; Registers;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Parallel and Distributed Processing, 1990. Proceedings of the Second IEEE Symposium on
Conference_Location :
Dallas, TX
Print_ISBN :
0-8186-2087-0
Type :
conf
DOI :
10.1109/SPDP.1990.143589
Filename :
143589
Link To Document :
بازگشت