.png){kind=icon}
Return
Parallel asynchronous watershed algorithm-architecture
.png){kind=icon}
PRE
AI
DOI：10.1109/TPDS.2007.253280.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
A joint algorithm-architecture study has resulted into a new version of a picture segmentation system complying with multimedia mobile terminal constraints, i.e., real-time computing, and low power consumption. Previously published watershed segmentation algorithms required at least three global synchronization points: minima detection, labeling and flooding. This paper presents a new fully asynchronous algorithm, where pixels can compute their local data in parallel and independently from one another, and which requires only a unique final global synchronization point. This paper provides a formal demonstration of the convergence and correctness of this new parallel asynchronous algorithm using a mathematical model of data propagation in a graph: the associative net formalism. We demonstrate the simplicity of implementation of this algorithm on parallel processor arrays. We explore, simulate, and validate several configurations of the algorithm-architecture using a SystemC model. Simulations reveal an image segmentation rate up to 66,000 QCIF images/sec, i.e., a speed-up factor of more than 1,000 times compared with state of the art watershed algorithms. A fine grain processor array design using ST microelectronics 0.18 mu m CMOS technology confirms that this new approach is a breakthrough in the domain of real-time image segmentation.
Keywords:
asynchronous algorithm-architecture
image segmentation
watershed
hill-climbing
parallel processors
correctness proof
performance evaluation
Journal
IF:
6
Papers:
5.2K
Citations:
1.2W
Organization
No organization information available
Cited Papers
Affinity labeling of bovine carboxypeptidase A γLeu by N-bromoacetyl-N-methyl-L-phenylalanine. I. Kinetics of inactivation.png)
Biochemistry
BiochemistryIF0
PREAI
ShareSave
ShareSaveShareSaveShareSaveShareSave
View more