Abstract

A watershed based on rainfall simulation is a proven technique for image segmentation. The only problem associated with it is the path regularization for pixels in the plateau. As the existing methods employ sequential techniques, the complexity of the algorithms remains high due to repetitive scanning of pixels. We propose an iterative method for finding the shortest and steepest path based on Breadth first search (BFS), which addresses the path regularization problem eliminating the repetitive scans. Experiments show, that the proposed algorithm significantly reduces the running time without compensating the performance when compared with the fastest known algorithm.

References

• Bieniek, A. , Moga, A. , An efficient watershed algorithm based on connected components. Pattern Recogn. 33 (3), pp. 907-916,2000.
• L. Vincent and P. Soille, "Watershed in Digital Spaces: An Efficient Algorithm Based on Immersion Simulations," IEEE Trans. Pattern Analysis and Machine Intelligence, vol. 13, no. 6, pp. 583-598, June 1991.
• Han Sun, Jingyu Yang and Mingwu Ren "A fast watershed algorithm based on chain code and its application in image segmentation", Pattern Recognition Letters 26, pp. 1266-1274, (2005).
• Ramesh Jain, Rangachari Kasturi and Brian G. Schunck, " Machine Vision", McGraw Hill, Inc. , 1995.
• J. Serra, Image Analysis and Mathematical Morphology. London: Academic,1982.
• F. Maisonneuve, "Surle partage des eaux," School of Mines, Paris, France, Internal Rep. CMM, 1982
• S. Beucher and F. Meyer, "The Morphological Approach of Segmentation: The Watershed Transformation," Mathematical Morphology in Image Processing, E. Dougherty, ed. , chapter 12, pp. 43-481, New York: Marcel Dekker, 1992
• A. Bleu, L. J. Leon, "Watershed-based segmentation and region merging", Computer vision and Image Understanding, 77, (3), (2000), pp 317 – 370.
• Víctor Osma-Ruiz, Juan I. Godino-Llorente, Nicolás Sáenz-Lechón, Pedro Gómez-Vilda," An improved Watershed algorithm based on efficient computation of shortest paths", The Journal Of Pattern Recognition Society, 40, June 2006, pp1078 – 1091.
• R. C. Gonzalez, R. E. Woods, S. L. Eddins, "Segmentation using the watershed transform" R. C. Gonzalez, R. E. Woods, S. L. Eddins (Eds. ), Digital Image Processing Using MATLAB, Pearson Prentice- Hall, NJ, USA, 2004, pp. 417–425.
• Bleau, J. De Guise, R. LeBlanc, "A new set of fast algorithms for mathematical morphology: I-Idempotent geodesic transforms", CVGIP: Image Understanding 56 (2) (1992) pp. 178–209.
• Freeman H, On The Encoding of Arbitrary Geometric ConFig. urations. IRE Trans EC-10 (2), 1961, pp. 260-268
• F. Meyer and S. Beucher, "Morphological Segmentation," J. Visual Comm. and Image Representation, vol. 1, no. 1, pp. 21-46, Sept. 1990.
• V. Grau, A. U. J. Mewes, M. Alcañiz, R. Kikinis, S. K. Warfield, Improved watershed transform for medical image segmentation using prior information, IEEE Trans. Med. Imaging 23 (4) (2004) pp. 447–458.
• A. N. Moga, M. Gabbouj, Parallel image component labeling with watershed transformation, IEEE Trans. Pattern Anal. ach. Intell. 19 (5) (1997) pp. 441–450.
• J. B. T. M. Roerdink, A. Meijster, The watershed transform: definitions, algorithms and parallelization strategies, undamenta Informaticae 41 (2000), pp. 187–228.
• S. Y. Chien, Y. W. Huang, S. Y. Ma, L. G. Chen, Predictive watershed for image sequences segmentation, in: Proceedings of IEEE ICASSP'02, vol. 3, Orlando, FL, USA, May 2002, pp. 3196–3199.
• ZHOU Kai-jun , YANG Chun-hua , GUI Wei-hua and XU Can-hui "Clustering-driven watershed adaptive segmentation of bubble image", J. Cent. South Univ. Technol. (2010) 17: 1049?1057 , Central South University Press and Springer-Verlag Berlin Heidelberg 2010
• J. Cousty, G. Bertrand, M. Couprie, L. Najman, "Fusion Graphs: Merging Properties and Watersheds", J Math Imaging Vis (2008) 30: pp. 87–104.
• Erlend Hodneland , Xue-Cheng Tai, Hans-Hermann Gerdes," Four-Color Theorem and Level Set Methods for Watershed Segmentation", Int J Comput Vis (2009) 82: pp. 264–283.
• Abhinav Gupta, Bhuvan Gosain and Sunanda Kaushal, "A Comparison Of Two Algorithms For Automated Stone Detection In Clinical B-Mode Ultrasound Images Of The Abdomen", Journal of Clinical Monitoring and Computing (2010) 24:pp. 341–362.
• Guifeng Zhang, Zhaocong Wu, Lina Yi, "Marker-Based Watershed Segmentation Embedded with Edge Information" 2010 IEEE
• Qiao Sun, Wei Yang, Lina Yu, "Research and Implementation of Watershed Segmentation Algorithm Based on CCD Infrared Images", in First International Conference on Pervasive Computing, Signal Processing and Applications. 2010, pp. 648-651.
• Deren Li, Guifeng Zhang, Zhaocong Wu, and Lina Yi, An Edge Embedded Marker-Based Watershed Algorithm for High Spatial Resolution Remote Sensing Image Segmentation", IEEE Transactions On Image Processing, vol. 19, no. 10, october 2010, pp. 2781-2787.
• Shu Li, Lei Wu, Yang Sun, "Cell Image Segmentation Based on An Improved Watershed Transformation", International Conference on Computational Aspects of Social Networks, 2010, pp. 93-96.
• Lee Seng Yeong, Li-Minn Ang, Kah Phooi Seng, "3D watershed based on rainfall-simulation for volume segmentation", in International Conference on Intelligent Human-Machine Systems and Cybernetics, 2009, pp. 477-481.
• C. Rambabu & I. Chakrabarti, "An Efficient Hillclimbing-based Watershed Algorithm and its Prototype Hardware Architecture", J Sign Process Syst (2008) 52:pp. 281–295.
• Liang Li, Yingxia Fu, Peirui Bai, Wenjie Mao, "Medical ultrasound image segmentation based on improved watershed scheme", 2009, IEEE.
• Sheng Chen, Zhanfeng Shen, Jiancheng Luo, Lijing Gao, "A Fast Watershed-based Image Segmentation Algorithm Using Local Merging Strategy", in International Symposium on Intelligent Information Technology Application Workshops, 2008, pp. 126-129.