Abstract
This paper presents an application of a hierarchical social (HS) metaheuristic to region-based segmentation. The original image is modelled as a simplified image graph, which is successively partitioned into two regions, corresponding to the most significant components of the actual image, until a termination condition is met. The graph-partitioning task is solved as a variant of the min-cut problem (normalized cut) using an HS metaheuristic. The computational efficiency of the proposed algorithm for the normalized cut computation improves the performance of a standard genetic algorithm. We applied the HS approach to brightness segmentation on various synthetic and real images, with stimulating trade-off results between execution time and segmentation quality.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Gonzalez, R.C., Woods, R.: Digital Image Processing, 2nd edn. Prentice Hall, Englewood Cliffs (2002)
Ho, S.Y., Lee, K.Z.: Design and Analysis of an Efficient Evolutionary Image Segmentation Algorithm. J. VLSI Signal Processing 35, 29–42 (2003)
Parker, J.R.: Algorithms for Image Processing and Computer Vision. John Wiley, Chichester (1996)
Sonka, M., et al.: Image Processing, Analysis and Machine Vision, 2nd edn. PWS (1999)
Glover, F., Kochenberger, G.A. (eds.): Handbook of Metaheuristics. Kluwer, Dordrecht (2002)
Michalewicz, Z., Fogel, D.B.: How to Solve It: Modern Heuristics, 2nd edn. Springer, Heidelberg (2000)
Voss, S.: Meta-heuristics: The State of the Art. In: Nareyek, A. (ed.) ECAI-WS 2000. LNCS (LNAI), vol. 2148, pp. 1–23. Springer, Heidelberg (2001)
Poli, R.: Genetic programming for image analysis. In: Koza, J. (ed.) Genetic Progr. (1996)
Yoshimura, M., Oe, S.: Evolutionary Segmentation of Texture Image using Genetic Algorithms. Pattern Recognition 32, 2041–2054 (1999)
Shi, J., Malik, J.: Normalized Cuts and Image Segmentation. IEEE Trans. Pattern Analysis and Machine Intelligence 22(8), 888–905 (2000)
Dolezal, O., Hofmeister, T., Lefmann, H.: A comparison of approximation algorithms for the MAXCUT-problem. Reihe CI 57/99, Universität Dortmund (1999)
Festa, P., Pardalos, P.M., Resende, M.G., Ribeiro, C.C.: Randomized Heuristics for the Max-Cut Problem. Optimization Methods and Software 7, 1033–1058 (2002)
Karp, R.M.: Reducibility among Combinatorial Problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, New York (1972)
Wu, Z., et al.: Optimal Graph Theoretic Approach to Data Clustering: Theory and its Application to Image Segmentation. IEEE Trans. PAMI 15(11), 1101–1113 (1993)
Duarte, A., Fernández, F., Sánchez, A., Montemayor, A.S.: A Hierarchical Social Metaheuristic for the Max-Cut Problem. In: Gottlieb, J., Raidl, G.R. (eds.) EvoCOP 2004. LNCS, vol. 3004, Springer, Heidelberg (2004)
Fernández, F., Duarte, A., Sánchez, A.: A Software Pipelining Method based on a Hierarchical Social Algorithm. In: Proc. 1st MISTA 2003, pp. 382–385 (2003)
Fernández, F.: Software Pipelining using HS Metaheuristic, Tech. Rep. URJC, Spain (2003)
Michalewicz: Genetic Algorithms+Data Structures=Evolution Programs. Springer, Heidelberg (1996)
Spears, W.M.: Evolutionary Algorithms. Springer, Heidelberg (1998)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Duarte, A., Sánchez, Á., Fernández, F., Montemayor, A.S., Pantrigo, J.J. (2004). Top-Down Evolutionary Image Segmentation Using a Hierarchical Social Metaheuristic. In: Raidl, G.R., et al. Applications of Evolutionary Computing. EvoWorkshops 2004. Lecture Notes in Computer Science, vol 3005. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24653-4_31
Download citation
DOI: https://doi.org/10.1007/978-3-540-24653-4_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21378-9
Online ISBN: 978-3-540-24653-4
eBook Packages: Springer Book Archive