A massively parallel implementation of the watershed based on cellular automata
Author: 
D. NoguetAuthors Info & Claims
Abstract
The watershed transform is a very powerful segmentation tool which comes directly from the idea of watershed line in geohydrology. It has proved its efficiency in many computer vision application fields. This paper presents a new implementation of the watershed which is optimal according to computation time. The flooding algorithm is reminded. Then, a massively parallel cellular automaton is proposed to propagate data using this approach. We discuss the pros and cons of a hardware implementation and give an example of application. A comparison between the results obtained and theoretical limit cases is also presented.
References
[1]
P.T. Balsara and M.J. Irwin. Intermediate-level vision tasks on a memory array architecture. Machine Vision and Applications, 6:50-65, June 1993.
[2]
S. Beucher. Segmentation d'images et morphologie mathéematique. June, Ecole Nationale Supérieure des Mines de Paris, 1990.
[3]
S. Beucher. Segmentation tools in mathematical morphology. In SPIE on Image Algebra and Morphological Image Processing, volume 1350, 1990.
[4]
A. Biancardi, V. Cantoni, U. Cei, and M. Mosconi. Computer Vision: Specialised Processors for Real-Time Image Analysis, chapter Morphological operators on a massively parallel fine grained architecture. Springer-Verlag, 1991.
[5]
G. Borgefors. Distance transformations in digital images. Computer Vision Graphics and Image Processing, 34, 1986.
[6]
P.E. Danielson. Euclidean distance mapping. Computer Vision Graphics and Image Processing, 14:287- 248, 1980.
[7]
M. Grimaud. A new measure of contrast: the dynamics. In SPIE on Image algebra and morphological image processing III. volume 1769, 1992.
[8]
J.E. Hopcroft and J.D. Ullmann. Introduction to automata theory, languages and computation. Addison-Wesley, 1979.
[9]
W.H. Kautz. Cellular logic-in-memory arrays. In IEEE Transaction on Computers, volume c-18, August 1969.
[10]
C. Lantuejoul and F. Maisonneuve. Geodesic methods in quantitative image analysis. Pattern Recognition , 17(2):177-187, 1984.
[11]
P. Maragos and R.W. Schafer. Morphological filters-part ii: their relations to median, order-statistics. and stack filters. In IEEE Transaction on Acoustics, Speech, and Signal Processing, volume 35. pages 1170-1184, August 1987.
[12]
P. Maragos and R.D. Ziff. Threshold superposition in morphological image analysis system. IEEE Transaction on Pattern Analysis and Machine Intelligence, 12(5). May 1990.
[13]
A. Meijster and J.B.T.M. Roerdink. A proposal for the implementation of a parallel watershed algorithm. In Proceedings of the CAIP'95. pages 790-795. September 1995.
[14]
F. Meyer. An optimal algorihtm for the watershed line. In RFIA, pages 847-857, 1991.
[15]
F. Meyer and S. Beucher. Morphologicai segmentation. Journal of Visual Communication and Image Representation, 1(1):21-46. 1990.
[16]
A. Moga. B. Cramariuc, and M. Gabbouj. An efficient watershed segmentation algorithm suitable for parallel implementation. In International Conference on Image Processing, volume 2, pages 101-104, October 1995.
[17]
D. Noguet, A. Merle and D. Lattard. Mathematical Morphology and its applications to Image and Signal Processing, chapter A data dependent architecture based on seeded region growing strategy for advanced morphological operators, pages 235-243. Kluwer Academic Publishers, 1996.
[18]
D. Noguet, A. Merle, D. Lattard, D. David, and R. Lionti. Queues for advanced morphological operators: from algorithms to a data dependent architecture. In QCAV'95 (Quality Control by Artificial Viszon), pages 141-149, Le Creusot (France), May 1995.
[19]
R. Peyrard. Conception et mise en oeuvre d'un ASIC de morphologie Mothématique à architecture programmable. PhD thesis. Université Blaise Pascal Clermont-Ferrand II, Ecole Nationale Supéieure des Mines de Paris, 1992.
[20]
F.Y.C. Shih and O.R. Mitchell. Threshold decomposition of greyscale morphology into binary morphology. IEEE Transaction on Pattern Analysis and Machine Intelligence. 11(1), January 1989.
[21]
M.H. Sunwoo, S. Ong, B. Ahn, and K. Lee. Design and implementation of a parallel image processor chip for a simd array processor. In Conference on Application Specific Array Processors, pages 66-75, 1995.
[22]
P. Tzionas, Ph. Tsalides, and A. Thanailakis. A parallel skeletonization algorithm based on two-dimensional cellular automata and its vlsi implementation. Real-time Imaging, (1):105-117, 1995.
[23]
L. Vincent. Algorithmes morphologiques à base de files d'attentes et de lacets. Extension aux graphes. PhD thesis, Ecole Nationale Supérieure des Mines de Paris, Mai 1990.
[24]
L. Vincent. Morphological grayscale reconstruction in image analysis: applications and efficient algorithms. IEEE Transaction on Image Processing. 2(2), 1993.
[25]
M. Willebeek-LeMair. Region growing on a higly parallel mesh-connected simd computer. In The second symposium on the frontiers of massively parrallel computation, pages 93-100. 1989.
[26]
M. Willebeek-Lemair and A.P. Reeves. Solving nonuniform problems on simd computers: case study on region growing. Journal of Parallel and Distributed Computing, (8):135-149, 1990.
Index Terms
- A massively parallel implementation of the watershed based on cellular automata
Recommendations
Descriptional complexity of cellular automata and decidability questions
Third international workshop on descriptional complexity of automata, grammars and related structuresWe study the descriptional complexity of cellular automata (CA) which are a parallel model of computation. We show that between one of the simplest cellular models, the realtime one-way CA (realtime-OCA), and "classical" models like deterministic finite ...
Closure properties of cellular automata
Concerning the power of one-dimensional cellular automata recognizers, Ibarra and Jiang have proved that real time cellular automata (CA) and linear time CA are equivalent if and only if real time CA is closed under reverse. In this paper we investigate ...
Expanding the Cellular Automata Topologies Library for Parallel Implementation of Synchronous Cellular Automata
Parallel Computing TechnologiesAbstractThe paper discusses the implementation of cellular automata on supercomputers. It outlines the requirements for the software: ease of program construction and usability, ability to handle a wide range of transition functions, compatibility with ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 1997
ISBN:0818679581
Copyright © Copyright (c) 1997 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.
Publisher
IEEE Computer Society
United States
Publication History
Published: 14 July 1997
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 25 Nov 2024