Abstract—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 STmicroelectronics 0.18\mu m CMOS technology confirms that this new approach is a breakthrough in the domain of real-time image segmentation.