Abstract
The aim of this paper is to present an improvement of a previously published algorithm. The proposed approach is performed in two steps. In the first step, we generate the Weighted Adaptive Neighborhood Hypergraph (WAINH) of the given gray-scale image. In the second step, we partition the WAINH using a multilevel hypergraph partitioning technique. To evaluate the algorithm performances, experiments were carried out on medical and natural images. The results show that the proposed segmentation approach is more accurate than the graph based segmentation algorithm using normalized cut criteria.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intellignece 22 (2000)
Soundararajan, P., Sarkar, S.: An in-depth study of graph partitioning measures for perceptual organization. IEEE Trans. Pattern Anal. Mach. Intell. 25, 642–660 (2003)
Martinez, A.M., Mittrapiyanuruk, P., Kak, A.C.: On combining graph-partitioning with non-parametric clustering for image segmentation. Computer Vision and Image Understanding 95, 72–85 (2004)
Wang, S., Siskind, J.M.: Image segmentation with ratio cut - supplemental material. IEEE Trans. Pattern Anal. Mach. Intell. 25 (2003)
Soundararajan, P., Sarkar, S.: Analysis of mincut, average cut, and normalized cut measures. In: Proc. Third Workshop Perceptual Organization in Computer Vision (2001)
Cour, T., Florence Benzit, J.S.: Spectral segmentation with multiscale graph decomposition. In: IEEE International Conference on Computer Vision and Pattern Recognition (2005) (to appear)
Rital, S., Bretto, A., Aboutajdine, D., Cherifi, H.: Application of adaptive hy-pergraph model to impulsive noise detection. In: Skarbek, W. (ed.) CAIP 2001. LNCS, vol. 2124, pp. 555–562. Springer, Heidelberg (2001)
Rital, S., Cherifi, H.: A combinatorial color edge detector. In: Campilho, A.C., Kamel, M.S. (eds.) ICIAR 2004. LNCS, vol. 3212, pp. 289–297. Springer, Heidelberg (2004)
Rital, S., Cherifi, H., Miguet, S.: Neighborhood hypergraph partitioning for image segmentation. In: First International Conference on Pattern Recognition and Machine Intelligence, pp. 18–22 (2005)
Bretto, A., Azema, J., Cherifi, H., Laget, B.: Combinatorics and image processing. Graphical Models and Image Processing 5, 265–372 (1997)
Catalyurek, U., Aykanat, C.: Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication. IEEE Trans. Parallel Distrib. Syst. 10, 673–693 (1999)
Trifunovic, A., Knottenbelt, W.: A parallel algorithm for multilevel k-way hyper-graph partitioning. In: Proceedings of 3rd International Symposium on Parallel and Distributed Computing (2004)
Ihler, E., Wagner, D., Wagner, F.: Modeling hypergraphs by graphs with the same mincut properties. Inf. Process. Lett. 45, 171–175 (1993)
Sanchis, L.A.: Multiple-way network partitioning. IEEE Transactions on Computers, 62–81 (1989)
Karypis, G., Aggarwal, R., Kumar, V., Shekhar, S.: Multilevel hypergraph partitioning: applications in vlsi domain. IEEE Trans. Very Large Scale Integr. Syst. 7, 69–79 (1999)
Karypis, G., Kumar, V.: hmetis 1.5: A hypergraph partitioning package. Technical report, University of Minnesota (1998), Available on http://www.cs.umn.edu/hmetis
Trifunovic, A., Knottenbelt, W.: Parkway 2.0: A parallel multilevel hypergraph partitioning tool. In: Aykanat, C., Dayar, T., Körpeoğlu, İ. (eds.) ISCIS 2004. LNCS, vol. 3280, pp. 789–800. Springer, Heidelberg (2004)
Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman and Co., New York (1979)
Karypis, G.: Multilevel hypergraph partitioning. Technical report #02-25, University of Minnesota (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Rital, S., Cherifi, H., Miguet, S. (2005). Weighted Adaptive Neighborhood Hypergraph Partitioning for Image Segmentation. In: Singh, S., Singh, M., Apte, C., Perner, P. (eds) Pattern Recognition and Image Analysis. ICAPR 2005. Lecture Notes in Computer Science, vol 3687. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11552499_58
Download citation
DOI: https://doi.org/10.1007/11552499_58
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-28833-6
Online ISBN: 978-3-540-31999-3
eBook Packages: Computer ScienceComputer Science (R0)