[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ Skip to main content
Springer Nature Link
Log in

An Efficient Hillclimbing-based Watershed Algorithm and its Prototype Hardware Architecture

  • Published:
Journal of Signal Processing Systems Aims and scope Submit manuscript

    We’re sorry, something doesn't seem to be working properly.

    Please try refreshing the page. If that doesn't work, please contact support so we can address the problem.

Abstract

Image segmentation is the process of isolating objects in an input image, that is, partitioning the image into disjoint regions, such that each region is homogeneous with respect to some property, such as gray value or texture. Watershed-based image segmentation has gained much popularity in the field of biomedical image processing and computer vision where large images are not uncommon. Time-critical applications like road traffic monitoring, and steel fissure analysis require fast realization of the segmentation results. The present paper proposes a fast watershed transform based on hillclimbing technique. The complexity of the algorithm has been reduced by doing away with multiplication normally required to form a lower complete image in an intermediate step of the overall segmentation. The reduced complexity makes the algorithm suitable for dedicated hardware implementation. An FPGA-based architecture has been developed to implement the proposed algorithm involving moderate hardware complexity. This architecture enhances the applicability of this algorithm for real-time applications.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
£29.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (United Kingdom)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Haralick, R. & Shapiro, L. (1985). Image segmentation techniques. Computer Vision, Graphics, Image Processing, 29(1), 100–132, January.

    Article  Google Scholar 

  2. Pal, N. R., & Pal, S. K. (1993). A review on image segmentation techniques. Pattern Recognition, 26(9), 1277–1294.

    Article  Google Scholar 

  3. Pratt, W. K. (2003). Image segmentation (3rd Ed., ch. 17 pp. 551–588). John Willey and sons, INC.

  4. Weska, J. S. (1978). A survey of threshold selection techniques. Computer Graphics and Image Processing, 7(2), 259–265, April.

    Article  Google Scholar 

  5. Mardia, K. & Hainsworth, T. (1988). A spatial thresholding method for image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10, 919–927.

    Article  Google Scholar 

  6. Sankur, B., Abak, A. T., & Baris, U. (1999). Assessment of thresholding algorithms for document processing,” in Proceedings of IEEE International Conference on Image Processing, 1 (pp. 580–584). Japan: Kobe, October.

  7. Prager, J. M. (1980). Extracting and labeling boundary segments in natural scenes. IEEE Transactions on Pattern Recognition and Machine Intelligence, 2(1), 16–27.

    Google Scholar 

  8. Perkins, W. A. (1980). Area segmentation of images using edge points. IEEE Transactions on Pattern Recognition and Machine Intelligence, 2(1), 8–15.

    Google Scholar 

  9. Canny, J. (1986). A computational approach to edge detection. IEEE Transactions on Pattern Analysis and Machine Intelligence, PAMI-8, 679–698.

    Article  Google Scholar 

  10. Beaulieu, J. M., & Goldberg, M. (1989). Hierarchy in picture segmentation: a stepwise optimization approach. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(2), 150–163.

    Article  Google Scholar 

  11. Wu, X. (1993). Adaptive split-and-merge segmentation based on piecewise least-square approximation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 15, 808–815, August.

    Article  Google Scholar 

  12. Beucher, S. & Meyer, F. (1993). The morphological approach to segmentation: The watershed transformation. In E. R. Dougherty (Ed.), Mathematical morphology in image processing (pp. 433–481). New York: Marcel Dekker Inc.

    Google Scholar 

  13. Chang, Y. L., & Li, X. (1994). Adaptive image region growing. IEEE Transactions on Image Processing, 3(6), 868–873.

    Article  MathSciNet  Google Scholar 

  14. Moga, A. N. (1997). Parallel watershed algorithms for image segmentation. Ph.D. dissertation, Tampere University of Technology, Tampere, Finland, February.

  15. Roerdink, J. B. T. M., & Meijster, A. (2001). The watershed transform: Definitions, algorithms and parallelization strategies. Fundamenta Informaticae, 41, 187–228.

    MathSciNet  Google Scholar 

  16. Derin, H., & Elliott, H. (1987). Modeling and segmentation of noisy and textured images using gibbs random fields. IEEE Transactions on Pattern Analysis and Machine Intelligence, 9, 39–55.

    Google Scholar 

  17. Srinivas, C., & Srinath, M. D. (1989). Compound gaussian markov random field model for image segmentation,” in International Conference on Acoustics, Speech, and Signal Processing, vol. 3 (pp. 1586–1589). UK: Glasgow, May.

  18. Dubes, R. C., Jain, A. K., Nadabar, S. G., & Chen, C. C. (1990). MRF model-based algorithms for image segmentation,” in Proceedings of 10th International Conference on Pattern Recognition, 1 (pp. 808–814). Atlantic City, NJ, USA, June.

  19. Kuria, T. (1991). An efficient agglomerative clustering algorithm using a heap. Pattern Recognition, 24(3), 205–209.

    Article  MathSciNet  Google Scholar 

  20. Ohm, J. R., & Ma, P. (1997). Feature-based cluster segmentation of image sequences. in Proc. IEEE international Conference on Image Processing (pp. 178–181).

  21. Pauwels, J., & Frederix, G. (1999). Finding salient regions in images. Computer Vision and Image Understanding, 75, 73–85.

    Article  Google Scholar 

  22. Vincent, L., & Soillé, P. (1991). Watersheds in digital spaces: An efficient algorithm based on immersion simulations. IEEE Transactions on Pattern Analysis and Machine Intelligence, 13(6), 583–598.

    Article  Google Scholar 

  23. Meyer, F., & Beucher, S. (1990). Morphological segmentation. Journal of Visual Communication and Image Representation, 1(1), 21–45.

    Article  Google Scholar 

  24. Meyer, F. (1994). Topographic distance and watershed lines. Signal Processing, 38(1), 113–125, July.

    Article  MATH  Google Scholar 

  25. Viero, T. (1996). Algorithms for image sequence filtering, coding and image segmentation. Ph.D. dissertation, Tampere University of Technology. Finland: Tampere, January.

  26. Rambabu, C., Chakrabarti, I. & Mahanta, A. (2004). A novel flooding-based watershed algorithm and its prototype hardware architecture. IEE Proceedings - Vision, Image and Signal Processing, 151(3), 224–234, June.

    Article  Google Scholar 

  27. Wang, D. (1997). A multiscale gradient algorithm for image segmentation using watersheds. Pattern Recognition, 30(12), 2043–2052, January.

    Article  Google Scholar 

  28. Huang, Q., & Dom, B. (1995). Quantitative methods for evaluating image segmentation. in IEEE International conference on Image Processing, 3 (pp. 53–56). Washington D. C., October.

  29. Bhaskar, J. (1999). VHDL primer (3rd Ed). Prentice Hall.

  30. Perry, D. L. (2001). VHDL (3rd Ed). Tata McGraw-Hill Publishing Company Limited.

Download references

Author information

Authors and Affiliations

  1. Imaging Informatics Group, Bioinformatics Institute, Singapore, 138671, Singapore

    C. Rambabu

  2. Electronics and Electrical Communication Engineering Department, Indian Institute of Technology, Kharagpur, 721 302, India

    I. Chakrabarti

Authors
  1. C. Rambabu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. I. Chakrabarti
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to C. Rambabu.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Rambabu, C., Chakrabarti, I. An Efficient Hillclimbing-based Watershed Algorithm and its Prototype Hardware Architecture. J Sign Process Syst Sign Image Video Technol 52, 281–295 (2008). https://doi.org/10.1007/s11265-007-0157-3

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11265-007-0157-3

Keywords

Search

Navigation