Hypergraph Cuts & Unsupervised Representation for Image Segmentation

• Autorzy: Rital S.
• Języki publikacji: EN

Abstrakty

EN

This paper presents a novel approach to image segmentation based on hypergraph cut techniques. Natural images contain more components: Edge, homogeneous region, noise. So, to facilitate the natural image analysis, we introduce an Image Neighborhood Hypergraph representation (INH). This representation extracts all features and their consistencies in the image data and its mode of use is close to the perceptual grouping. Then, we formulate an image segmentation problem as a hypergraph partitioning problem and we use the recent k-way hypergraph techniques to find the partitions of the image into regions of coherent brightness/color. Experimental results of image segmentation on a wide range of images from Berkeley Database show that the proposed method provides a significant performance improvement compared with the stat-of-the-art graph partitioning strategy based on Normalized Cut (Ncut) criteria.

Słowa kluczowe

EN

hypergraph partitioning algorithms; image segmentation; image neighborhood hypergraph representation (INH); normalized cuts

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2009
• Tom: Vol. 96, nr 1/2
• Strony: 153--179
• Opis fizyczny: Bibliogr. 56 poz., fot., wykr.

Twórcy

autor

Rital S.

• Soufiane RITAL, Institut TELECOM; TELECOM ParisTech; CNRS LTCI, 46, rue Barrault -75634 Paris Cedex 13, France,

Bibliografia

• [1] Alpert, C. J., Kahng, A. B.: Recent Developments in Netlist Partitioning: A Survey, Integration: the VLSI Journal, 19(1-2), 1995, 1-81.
• [2] Berge, C.: Graphs and Hypergraphs, Elsevier Science Ltd, 1985.
• [3] Boykov, Y., Funka-Lea, G.: Graph Cuts and Efficient N-D Image Segmentation, International Journal of Computer Vision, 70(2), 2006, 109-131, ISSN 0920-5691.
• [4] Bretto, A.: Comparability Graphs and Digital Topology, Computer Vision and Image Understanding, 82(1), 2001, 33 - 41, ISSN 1077-3142.
• [5] Bretto, A., Gillibert, L.: Hypergraph-Based Image Representation, Lecture Notes in Computer Science (S. B. . Heidelberg, Ed.), 3434, 2005, ISSN 0302-9743.
• [6] Brglez, F.: A D&T Special Report on ACM/SIGDA Design Automation Benchmarks: Catalyst or Anathema?, IEEE Des. Test, 10(3), 1993, 87-91, ISSN 0740-7475.
• [7] Brun, L., Vento, M., Eds.: Graph-Based Representations in Pattern Recognition, 5th IAPR International-Workshop, GbRPR 2005, Poitiers, France, April 11-13, 2005, Proceedings, vol. 3434 of Lecture Notes in Computer Science, Springer, 2005, ISBN 3-540-25270-3.
• [8] Bui, T., Jones, C., Heigham, C., Leighton, T.: Improving the Performance of the Kernighan-Lin and Simulated Annealing Graph Bisection Algorithms, Design Automation, 1989. 26th Conference on, June 1989, ISSN 0738-100X.
• [9] Catalyurek, U. V., Aykanat, C.: Hypergraph-Partitioning-Based Decomposition for Parallel Sparse-Matrix VectorMultiplication, IEEE Transactions on Parallel and Distributed Systems, 10(7), 1999, 673-693, ISSN 1045-9219.
• [10] Chein, M., Mugnier, M. L.: Graph-based Knowledge Representation. Computational Foundations of Conceptual Graphs, Advanced Information and Knowledge Processing, Springer London, 2008.
• [11] Chevalier, C., Pellegrini, F.: PT-Scotch: A tool for efficient parallel graph ordering, Parallel Comput., 34(6-8), 2008, 318-331, ISSN 0167-8191.
• [12] Cox, I., Rao, S., Zhong, Y.: Ratio regions: a technique for image segmentation, Pattern Recognition, 1996., Proceedings of the 13th International Conference on, 2, Aug 1996.
• [13] Eckhardt, U.: Digital lines and digital convexity, Springer-Verlag New York, Inc., New York, NY, USA, 2001, ISBN 3-540-43079-2.
• [14] Fana, J., Zengb, G., Bodyc,M., Hacidc,M.-S.: Seeded region growing: an extensive and comparative study, Pattern Recognition Letters, 26(8), June 2005, 1139-1156.
• [15] Fiduccia, C., Mattheyses, R.: A Linear-Time Heuristic for Improving Network Partitions, Design Automation, 1982. 19th Conference on, June 1982, ISSN 0146-7123.
• [16] Garey, M. R., Johnson, D. S.: Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, USA, 1990, ISBN 0716710455.
• [17] Gdalyahu, Y., Weinshall, D., Werman, M.: Self-organization in vision : stochastic clustering for image segmentation, perceptual grouping, and image database organization, IEEE Trans. Pattern Anal. Mach. Intell., 23(10), 2001, 1053-1074.
• [18] Gillibert, L., Bretto, A.: Hypergraphs for Generic Lossless Image Compression, Fundamenta Informaticae, 91(3-4), 2009, 533-546.
• [19] Hadley, S., Mark, B., Vannelli, A.: An efficient eigenvector approach for finding netlist partitions, Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 11(7), Jul 1992, 885-892, ISSN 0278-0070.
• [20] Hagen, L., Kahng, A. B.: A new approach to effective circuit clustering, ICCAD '92: Proceedings of the 1992 IEEE/ACM international conference on Computer-aided design, IEEE Computer Society Press, Los Alamitos, CA, USA, 1992, ISBN 0-89791-540-2.
• [21] Hébert, C., Bretto, A., Crémilleux, B.: A Data Mining Formalization to Improve Hypergraph Minimal Transversal Computation, Fundam. Inform., 80(4), 2007, 415-433.
• [22] Hendrickson, B., Leland, R.: A multilevel algorithm for partitioning graphs, Supercomputing '95: Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), ACM Press, New York, NY, USA, 1995, ISBN 0-89791-816-9.
• [23] Ihler, E., Wagner, D., Wagner, F.: Modeling hypergraphs by graphs with the same mincut properties, Information Processing Letters, 45(4), 1993, 171-175, ISSN 0020-0190.
• [24] Jermyn, I., Ishikawa, H.: Globally Optimal Regions and Boundaries as Minimum Ratio Cycles, IEEE Trans. Pattern Analysis and Machine Intelligence, 23(10), Oct 2001, 1075-1088.
• [25] Karypis, G.: Multilevel Hypergraph Partitioning, Technical report #02-25, University of Minnesota, 2002.
• [26] Karypis, G., Aggarwal, R., Kumar, V., Shekhar, S.: Multilevel hypergraph partitioning: applications in VLSI domain, IEEE Trans. Very Large Scale Integr. Syst., 7(1), 1999, 69-79, ISSN 1063-8210.
• [27] Karypis, G., Kumar, V.: hMETIS 1.5: A hypergraph partitioning package, Technical report, University of Minnesota, Available on http://www.cs.umn.edu/hmetis, 1998.
• [28] Kernighan, B. W., Lin., S.: An efficient heuristic procedure for partitioning graphs., The Bell system technical journal, 49(1), 1970, 291-307.
• [29] Kim, J.-S., Hong, K.-S.: Color-texture segmentation using unsupervised graph cuts, Pattern Recognition, 42(5), 2009, 735 - 750, ISSN 0031-3203.
• [30] Koontz, W., Fukunaga, K.: A nonparametric valley-seeking technique for cluster analysis, IEEE Trans. Comput., 21, 1972, 171-178.
• [31] Koyutrk, M., Aykanat, C.: Iterative-improvement-based declustering heuristics for multi-disk databases, Information Systems, 30(1),March 2005, 47-70.
• [32] Lengauer, T.: Combinatorial Optimization: Networks and Matroids, Holt, Rinehart, and Winston, 1976.
• [33] Lengauer, T.: Combinatorial algorithms for integrated circuit layout, Wiley & Sons, New York, New York, 1990.
• [34] Lincke, C., Wthrich, C. A.: Surface digitizations by dilations which are tunnel-free, Discrete Appl. Math., 125(1), 2003, 81-91, ISSN 0166-218X.
• [35] Martin, D., Fowlkes, C., Tal, D., Malik, J.: A Database of Human Segmented Natural Images and its Application to Evaluating Segmentation Algorithms and Measuring Ecological Statistics, Proc. 8th Int'l Conf. Computer Vision, 2, July 2001.
• [36] 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, 2004, 72-85.
• [37] Navon, E., Miller, O., Averbuch, A.: Color image segmentation based on adaptive local thresholds., Image Vision Comput., 23(1), 2005, 69-85.
• [38] Papa, D., Markov, I.: Hypergraph Partitioning and Clustering, chapter Approximation Algorithms and Metaheuristics, CRC Press, 2007, 1-61.
• [39] Pothen, A., Simon, H. D., Liou, K.-P.: Partitioning sparse matrices with eigenvectors of graphs, SIAM J. Matrix Anal. Appl., 11(3), 1990, 430-452, ISSN 0895-4798.
• [40] Rijsbergen, C. V.: Information retrieval, Second edition, Butterworths, 1979.
• [41] Rosenfeld, A.: Digital Image Processing and Recognition, Digital Bildverarbeitung - Digital Image Processing, GI/NTG Fachtagung, Springer-Verlag, London, UK, 1977, ISBN 3-540-08169-0.
• [42] Sanchis, L.: Multiple-way network partitioning, Computers, IEEE Transactions on, 38(1), Jan 1989, 62-81, ISSN 0018-9340.
• [43] Sarkar, S., Boyer, K.: Quantitative measures of change based on feature organization: eigenvalues and eigenvectors, Proc. IEEE Conf. Comput. Vis. Patt. Recogn., 1996, 478-483.
• [44] Schweikert, D. G., Kernighan, B. W.: A proper model for the partitioning of electrical circuits, ACM/IEEE Design Automation Conference, 1972.
• [45] Scotney, B., McClean, S., Rodgers, M.: Optimal and efficient integration of heterogeneous summary tables in a distributed database, Data & Knowledge Engineering, 29(3), March 1999, 337-350.
• [46] Serra, J.: Image analysis and mathematical morphology: theoretical advances, vol. 2, Academic Press, 1988.
• [47] Shi, J., Malik, J.: Normalized Cuts and Image Segmentation, IEEE Transactions on Pattern Analysis and Machine Intellignece, 22(8), AUGUST 2000.
• [48] Soundararajan, P., Sarkar, S.: Analysis ofMincut, Average Cut, and Normalized Cut Measures, Proc. Third Workshop Perceptual Organization in Computer Vision, 2001.
• [49] Soundararajan, P., Sarkar, S.: An In-Depth Study of Graph Partitioning Measures for Perceptual Organization., IEEE Trans. Pattern Anal. Mach. Intell., 25(6), 2003, 642-660.
• [50] Tal, D.: Normalized Cuts Software for Image Segmentation, http://www.cs.berkeley.edu/doron/software/ncuts, December 2000.
• [51] Tal, D., Malik, J.: Combining color, texture and contour cues for image segmentation., Preprint, 2001.
• [52] Trifunovic, A., Knottenbelt, W.: A Parallel Algorithm for Multilevel k-way Hypergraph Partitioning, Proceedings of 3rd International Symposium on Parallel and Distributed Computing, July 2004.
• [53] Trifunovic, A., Knottenbelt, W. J.: Parkway 2.0: A Parallel Multilevel Hypergraph Partitioning Tool, 19th International Symposium on Computer and Information Sciences (ISCIS 2004), 3280, October 2004.
• [54] Veksler, O.: Image Segmentation by Nested Cuts, Computer Vision and Pattern Recognition, IEEE Computer Society Conference on, 1, 2000, 1339, ISSN 1063-6919.
• [55] Wang, S., Siskind, J. M.: Image Segmentation with Ratio Cut, IEEE Trans. Pattern Anal. Mach. Intell., 25(6), June 2003, 675-690.
• [56] Wu, Z., Leahy, R.: An optimal graph theoretical approach to data clustering: theory and its application to image segmentation, IEEE Trans. Patt. Anal. Mach. Intell., 15, 1993, 1101-1113.