An efficient graph-based image segmentation algorithm (EGBIS) is considered. The aspects of an efficient algorithm implementation, in particular the use of “Disjoint sets union” data structure with its heuristics “path compression” and “union be rank”, are investigated. A suitability of the algorithm for the use in automated systems is reviewed. An applicability of cluster validity measures for image segmentation quality assessment is analyzed.
1. Вихарев Д. Эффективная сегментация изображений на графах. — [Електронний ресурс]: http://habrahabr.ru/blogs/algorithm/81279/.
2. Нікольський Ю.В., Пасічник В. В., Щербина Ю.М. Дискретна математика. — К.: Видавнича група BHV, 2007. — 368 с.
3. Daniel Rakos. Efficient Gaussian blur with linear sampling. — [Електронний ресурс]: http://rastergrid.com/blog/2010/09/efficient-gaussian-blur-with-linear-s....
4. Felzenszwalb P, Huttenlocher D. Efficient Graph-Based Image Segmentation // International Journal of Computer Vision. — 2004. — Vol. 59, no. 2. — P. 167–181.
5. Mitzenmacher M. Lecture 6: Disjoint set (Union-Find). — [Електронний ресурс]: http://www.fas.harvard.edu/~libcs124/CS/lec6.pdf.
6. Stein B., Niggemann O. On the Nature of Structure and its Identification // P. Widmayer, G. Neyer, S. Eidenbenz (eds.). Graph-Theoretic Concepts in Computer Science. LNCS 1665. — Springer-Verlag, 1999. — P. 122–134.
7. Stein В., Meyer zu Eissen S., Wißbrock F. On Cluster Validity and the Information Need of Users // Proceedings of the 3rd IASTED International Conference on Artificial Intelligence and Applications (AIA’03). — Benalmadena, Spain: September 8-10, 2003. — P. 216–221.
8. Wassenberg J., Middelmann W., Sanders P. An Efficient Parallel Algorithm for Graph-Based Image Segmentation // Proceedings of the 13th International Conference on Computer Analysis of Images and Patterns (CAIP’09). — Münster, Germany: September 2–4, 2009. — P. 1003–1010.