Parallel image component labelling with watershed transformation
Authors:
- A.N. MogaAMA.N. Moga
- M. GabboujMGM. Gabbouj
- 1 May 1997
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 19 (5) , 441-450
Abstract
The parallel watershed transformation used in gray scale image segmentation is reconsidered in this paper on the basis of the component labeling problem. The main idea is to break the sequentiality of the watershed transformation and to correctly delimit the extent of all connected components locally, on each processor, simultaneously. The internal fragmentation of the catchment basins, due to domain decomposition, into smaller subcomponents is ulteriorly solved by employing a global connected components operator. Therefore, in a pyramidal structure of master-slave processors, internal contours of adjacent subcomponents within the same component are hierarchically removed. Global final connected areas are efficiently obtained in log(2) N steps on a logical grid of N processors. Timings and segmentation results of the algorithm built on top of the Message Passing Interface (MPI) and tested on the Gray T3D are brought forward to justify the superiority of the novel design solution compared against previous implementationsKeywords
This publication has 16 references indexed in Scilit:
- Parallel Algorithms for Image Histogramming and Connected Components with an Experimental StudyJournal of Parallel and Distributed Computing, 1996
- A Data Parallel Algorithm for Solving the Region Growing Problem on the Connection MachineJournal of Parallel and Distributed Computing, 1994
- Connected Component Labeling on Coarse Grain Parallel Computers: An Experimental StudyJournal of Parallel and Distributed Computing, 1994
- Parallel Algorithms for Gray-Scale Digitized Picture Component Labeling on a Mesh-Connected ComputerJournal of Parallel and Distributed Computing, 1994
- Parallel architectures and algorithms for image component labelingIEEE Transactions on Pattern Analysis and Machine Intelligence, 1992
- Watersheds in digital spaces: an efficient algorithm based on immersion simulationsIEEE Transactions on Pattern Analysis and Machine Intelligence, 1991
- Fast image labeling using local operators on mesh-connected computersIEEE Transactions on Pattern Analysis and Machine Intelligence, 1991
- Solving nonuniform problems on SIMD computers: Case study on region growingJournal of Parallel and Distributed Computing, 1990
- An EREW PRAM algorithm for image component labelingIEEE Transactions on Pattern Analysis and Machine Intelligence, 1989
- Efficient component labeling of images of arbitrary dimension represented by linear bintreesIEEE Transactions on Pattern Analysis and Machine Intelligence, 1988