NEIGHBORHOOD HYPERGRAPH PARTITIONING FOR IMAGE SEGMENTATION

Soufiane Rital, Hocine Cherifi, Serge Miguet

2006

Abstract

The aim of this paper is to introduce a multilevel neighborhood hypergraph partitioning for image segmentation. Our proposed approach uses the image neighborhood hypergraph model introduced in our last works and the algorithm of multilevel hypergraph partitioning introduced by George Karypis. To evaluate the algo- rithm performance, experiments were carried out on a group of gray scale images. The results show that the proposed segmentation approach find the region properly from images as compared to image segmentation algorithm using normalized cut criteria.

References

  1. Alpert, C. J. and Kahng, A. B. (1995). Recent developments in netlist partitioning: A survey. Integration: the VLSI Journal, 19(1-2):1-81.
  2. Catalyurek, U. and Aykanat., C. (1999). Hypergraphpartitioning-based decomposition for parallel sparsematrix vector multiplication. IEEE Transactions on Parallel and Distributed Systems, 10(7):673-693.
  3. Cox, I., Rao, S., and Zhong, Y. (1996). Ratio regions: A technique for image segmentation. In 13th International Conference on Pattern Recognition (ICPR'96).
  4. Fan, J., Yau, D. K., Elmagarmid, A. K., and Aref, W. G. (2001). Automatic image segmentation by integrating color edge detection and seeded region growing. IEEE Trans. on Image Processing., 10(10):1454-1466.
  5. Fiduccia, C. M. and Mattheyses, R. M. (1982). A lineartime heuristic for improving network partitions. In Proceedings of the 19th ACM/IEEE Design Automation Conference DAC 82, pages 175-181.
  6. Garey, M. and Johnson, D. (1979). Computers and Intractability: A Guide to the Theory of NPCompleteness. W.H. Freeman and Co.
  7. Gdalyahu, Y., Weinshall, D., and Werman, M. (2001). Selforganization in vision : stochastic clustering for image segmentation, perceptual grouping, and image database organization. IEEE Trans. Pattern Anal. Mach. Intell., 23(10):1053-1074.
  8. Hadley, S., Mark, B., and Vannelli, A. (1992). An efficient eigenvector approach for finding netlist partitions. IEEE Trans. CAD, 11:885-892.
  9. Ihler, E., Wagner, D., and Wagner, F. (1993). Modeling hypergraphs by graphs with the same mincut properties. Inf. Process. Lett., 45(4):171-175.
  10. Karypis, G. (2002). Multilevel hypergraph partitioning. Technical report #02-25, University of Minnesota.
  11. Karypis, G., Aggarwal, R., Kumar, V., and Shekhar, S. (1999). Multilevel hypergraph partitioning: applications in vlsi domain. IEEE Trans. Very Large Scale Integr. Syst., 7(1):69-79.
  12. Karypis, G. and Kumar, V. (1998). hmetis 1.5: A hypergraph partitioning package. Technical report, University of Minnesota, Available onhttp://wwwusers.cs.umn.edu/~karypis/metis/hmetis/index.html.
  13. Kernighan, B. W. and Lin., S. (1970). An efficient heuristic procedure for partitioning graphs. The Bell system technical journal, 49(1):291-307.
  14. Koontz, W. and Fukunaga, K. (1972). A nonparametric valley-seeking technique for cluster analysis. IEEE Trans. Comput., 21:171-178.
  15. Koyutrk, M. and Aykanat, C. (2005). Iterativeimprovement-based declustering heuristics for multidisk databases. Information Systems, 30(1):47-70.
  16. Martinez, A. M., Mittrapiyanuruk, P., and Kak, A. C. (2004). On combining graph-partitioning with nonparametric clustering for image segmentation. Computer Vision and Image Understanding, 95:72-85.
  17. Navon, E., Miller, O., and Averbuch, A. (2005). Color image segmentation based on adaptive local thresholds. Image Vision Comput., 23(1):69-85.
  18. Pal, N. and Pal, S. (1993). A review on image segmentation techniques. Pattern Recognition, 26:1277-1294.
  19. Rital, S., Bretto, A., Aboutajdine, D., and Cherifi, H. (2001). Application of adaptive hypergraph model to impulsive noise detection. Lecture Notes in Computer Science, 2124:555-562.
  20. Rital, S. and Cherifi, H. (2004). A combinatorial color edge detector. Lecture Notes in Computer Science, 3212:289-297.
  21. Sanchis, L. A. (1989). Multiple-way network partitioning. IEEE Transactions on Computers, pages 62-81.
  22. Sarkar, S. and Boyer, K. (1996). Quantitative measures of change based on feature organization: eigenvalues and eigenvectors. Proc. IEEE Conf. Comput. Vis. Patt. Recogn., pages 478-483.
  23. Shi, J. and Malik, J. (2000). Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intellignece, 22(8):888-905.
  24. Soundararajan, P. and Sarkar, S. (2001). Analysis of mincut, average cut, and normalized cut measures. Proc. Third Workshop Perceptual Organization in Computer Vision.
  25. Soundararajan, P. and Sarkar, S. (2003). An in-depth study of graph partitioning measures for perceptual organization. IEEE Trans. Pattern Anal. Mach. Intell., 25(6):642-660.
  26. Tal, D. and Malik, J. (2001). Combining color, texture and contour cues for image segmentation. Preprint.
  27. Trifunovic, A. and Knottenbelt, W. (2004a). A parallel algorithm for multilevel k-way hypergraph partitioning. In Proceedings of 3rd International Symposium on Parallel and Distributed Computing.
  28. Trifunovic, A. and Knottenbelt, W. (2004b). Parkway 2.0: A parallel multilevel hypergraph partitioning tool. In Proceedings of 19th International Symposium on Computer and Information Sciences (ISCIS 2004), volume 3280, pages 789-800.
  29. Wang, S. and Siskind, J. M. (2003). Image segmentation with ratio cut - supplemental material. IEEE Trans. Pattern Anal. Mach. Intell., 25(6):675-690.
  30. Wu, Z. and Leahy, R. (1993). An optimal graph theoretical approach to data clustering: theory and its application to image segmentation. IEEE Trans. Patt. Anal. Mach. Intell., 15:1101-1113.
Download


Paper Citation


in Harvard Style

Rital S., Cherifi H. and Miguet S. (2006). NEIGHBORHOOD HYPERGRAPH PARTITIONING FOR IMAGE SEGMENTATION . In Proceedings of the First International Conference on Computer Vision Theory and Applications - Volume 1: VISAPP, ISBN 972-8865-40-6, pages 331-337. DOI: 10.5220/0001376003310337


in Bibtex Style

@conference{visapp06,
author={Soufiane Rital and Hocine Cherifi and Serge Miguet},
title={NEIGHBORHOOD HYPERGRAPH PARTITIONING FOR IMAGE SEGMENTATION},
booktitle={Proceedings of the First International Conference on Computer Vision Theory and Applications - Volume 1: VISAPP,},
year={2006},
pages={331-337},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001376003310337},
isbn={972-8865-40-6},
}


in EndNote Style

TY - CONF
JO - Proceedings of the First International Conference on Computer Vision Theory and Applications - Volume 1: VISAPP,
TI - NEIGHBORHOOD HYPERGRAPH PARTITIONING FOR IMAGE SEGMENTATION
SN - 972-8865-40-6
AU - Rital S.
AU - Cherifi H.
AU - Miguet S.
PY - 2006
SP - 331
EP - 337
DO - 10.5220/0001376003310337